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

Question

问题背景

我有一个包含10个符号的有限词汇[AJ].这些符号的含义与问题无关.它们可以是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)是不可接受的.(2)正则表达速度很慢.(3)字符串(至少在java中)是膨胀的.

2. 让Lucene处理索引.关闭tfidf得分.使用短语搜索.潜在地使用计数值进行评分,以便Lucene也负责排序.

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

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

---

更新

1. 在我的实际应用中,我将使用单独存储的长度为5,6,7,8,9,10的序列.我通过将其限制为固定长度来简化问题.因此,对使用较少内存的解决方案的约束/偏好.
2. 我的词汇量可以假设不到20岁.

Answer 1

根据只有 1 个未知数的评论，您可以执行以下操作：

但是你的数据在哈希表中。当您需要查找某个模式时，请生成所有通配符组合，因为您的词汇量有限，这意味着最多查找 20 个模式。这听起来像是一种黑客攻击，但如果您考虑其他方法对性能的影响，那么它是很难被击败的。哈希表查找的时间复杂度为 O(1)，20 次查找也是 O(1)。

如果通配符的数量可能增加，则不建议使用此方法，尽管对于 2 或 3 个通配符仍可能表现良好。

双数组 trie 也可以工作，并且可能会减少存储字符串的空间量，但性能会受到影响。