algorithm - 大数据模式匹配的数据结构

Question

问题背景

我有一个有限的词汇表，其中包含 10 个符号 [A-J]。这些符号的含义与问题无关。它们可以是 DNA 碱基、音素、单词等。

一个项目是一个符号序列。在这个问题中，所有项目的长度都相同(比如 6)。例如。

A C B A D J

我有一个大 (5M) 表，其中包含从某些已知数据中采样的所有长度为 6 的项目的计数。例如

A C B A D J     55
B C B I C F     923
A B C D E G     478

给定一个带有未知符号的新序列，我的任务是猜测符号。在以下示例中，缺少的符号是 ?。

B C B ? C F

猜测 ? 的一个简单解决方案是查看我的表并找到符合模式 B C B ? C F

问题

1. 什么是存储项目频率表以便我合理有效地处理时空的良好数据结构？如果查询时的计算合理，我更愿意使用更少的内存。 (我会有很多这样的表格，所以 5M 的数字只是一个近似值。)

2. 哪些实现细节可以显着提高处理速度？

我想到的事情:

1. 将每个序列组成一个字符串并使用正则表达式进行匹配。 警告:1. O(n) 是 Not Acceptable 。 (2) 正则表达式很慢。 (3) 字符串(至少在 java 中)是臃肿的。

2. 让 Lucene 处理索引。关闭 tfidf 评分。使用短语搜索。可能使用计数值进行评分，以便 Lucene 也负责排序。

3. 使用前缀和后缀尝试为每个项目建立索引。

4. 使用 db(可能在内存中)将整个数据放在一个/单独的列中来处理搜索。

---

更新

1. 在我的实际应用中，我将处理长度分别为 5、6、7、8、9、10 的序列。我通过将其限制为固定长度来简化问题。因此限制/偏好使用较少内存的解决方案。
2. 可以假设我的词汇量在 20 以内。

Answer 1

尝试 的决定似乎是最好的决定:根据叶子上字符串出现的次数，您可以轻松设计函数，该函数将在 O(log n) 时间内返回所有可能的字符串，其中缺少一个字符，然后您只需遍历这一小部分字符串，搜索最大出现次数。如果使用从 A 到 Z 的字符，那么最多有 26 个这样的字符串，因此迭代不会花费很多时间。

据我所知，Lucene 在其 wildcards search 内部使用这种机制，因此您可以连接您的字符，使用 KeywordAnalyzer 为它们编制索引(以省略词干提取)，然后搜索“ACB?DJ”。这里唯一的限制是 Lucene 无法处理第一个“？”的搜索，但您可以通过在开头添加一个额外的字符(只是绕过 Lucene 检查的技巧)或为反向单词添加一个索引(将提高性能)来绕过它对于以通配符作为第一个字符的单词很多)。

最后，如果您无论如何都要首先计算出现次数，则可以使用一些机器学习方案(例如决策树)来处理所有工作。在某些情况下，决策树用于压缩数据库和加快搜索速度，因此您也可以这样做。使用行作为实例，字符的位置作为属性，字符本身作为属性值。然后运行一些算法，如 C4.5(您可以使用 Weka's 称为 J48 的实现)，进行最少的修剪并运行分类 - 算法将完成剩下的工作!