用于模式匹配的数据结构上的大数据

我有一个包含一个有限的词汇说10个符号[A-D]。这些符号的含义与这个问题无关。它们可以是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

问题

什么是一个很好的数据结构来存储我的项目，频率表，以便最大数量的项目我合理有效地处理时空？如果查询时间的计算合理，我宁愿使用更少的内存。（我会有很多这样的表格，所以5M数字只是一个近似值。）
什么是一些实现细节，可以使处理速度有很大的不同？

事情我已经想到了：

做一个串出每个序列，并使用正则表达式匹配。警告：1. O（n）是不可接受的。（2）正则表达式很慢。（3）字符串（至少在java中）膨胀。
让Lucene处理索引。关闭tfidf评分。使用短语搜索。有可能使用计数值进行评分，以便Lucene负责分类。
使用前缀和后缀尝试索引每个项目。
在一个/单独的列中使用db（可能是内存中的）整个数据来处理搜索。

更新

以我实际应用中，我将与单独存储长度-5,6,7,8,9,10-的序列来工作。我通过将问题限制在固定长度来简化问题。因此，对使用较少内存的解决方案的约束/偏好。
我的词汇尺寸可以被假定为下20.

来源

2011-05-09 hashable

我会设计它，使每个项目驻留在它自己的索引列中。因此6列+1列的频率。从数据库查询和订购应该非常快。 – arviman 2011-05-09 19:19:34

你描述中的两个常量：10个字母和长度= 6。它们只是例子还是真实的价值？长度的字母数量可以大得多吗？ – maxim1000 2011-05-09 19:24:42

@ maxim1000。常数可以被认为接近真实。新增更新1,2谢谢。 – hashable 2011-05-09 19:42:22

基础上的评价是，将只有1个未知的，你可以做到以下几点：

但在哈希表中的数据。当你需要查找一个模式，生成所有的通配符组合，因为你的词汇量有限，这意味着最多查找20个模式。这听起来像一个黑客，但如果你考虑其他方法的性能影响，它很难被击败。哈希表查找是O（1），20查找也是O（1）。

这种方法是不可取的，如果通配符的数量可能会增加，但仍可以执行以及2或3

双阵列特里也将工作和可能降低的空间量来存储你的字符串，但表现会受损。

来源

2011-05-09 21:38:38 idz

这似乎是迄今为止最好的选择。 – hashable 2011-05-09 21:48:38

如果您不经常更新表格，您还可以保留一些额外的统计信息，例如，某些符号可能不会出现在某些位置。这可能会让你挤出更多的表现。 – idz 2011-05-09 21:52:25

哈希表并不总是O（1）：对于大数据集，会发生多次冲突，从而导致更长的查找。还要注意，计算哈希值也需要一些时间。另一方面，尝试查询字符串的速度非常快（这就是为什么它们经常在像Lucene这样的字符串操作密集型应用程序中使用的原因）：对于没有通配符的6个字符串，它们将严格涉及6个字符比较， 1个通配符 - 最多（当通配符处于第一个位置时）（6-1）* N比较，其中N是字符可能值的数量。 – ffriend 2011-05-10 00:32:13

为了唯一表征一个新的序列，两条信息是必要的：五个已知符号序列（字符串），和的位置未知的符号。如果您的字母表有10个符号，则不能超过10^5 = 100000个独特的五符号字符串。

根据您的内存资源，这可能足够小以适应哈希表，其条目提供查找结构来查找最佳（位置，符号）组合。例如：

--------- 
| BCBCF | --> { 0: <heap of symbols partially ordered by frequency>, ... } 
---------

这应该允许一个相当有效的查找为一个新的序列：串接已知的符号，查找序列中的哈希表，发现未知字符的位置，然后返回符号，它位于相应堆的顶部。

如果您可以保证在执行任何查找之前查找结构将保持稳定（无新输入），那么您可以通过将每个位置索引堆替换为单个符号来提高效率本来会在堆的顶端。（只有在查找阶段才需要堆结构，如果有新信息进来可能会改变符号频率。）

来源

2011-05-09 19:49:39 Alanyst

这可能是可行的，但你需要有6个这样的散列表。每个缺少的列一个。 – btilly 2011-05-09 19:51:36

@btilly：并非如此，因为虽然“ABC？DE”和“A？BCDE”将哈希到相同的条目，但该条目的子结构提供了获取未知位置的最佳符号的方法。不需要单独的表格。 – Alanyst 2011-05-09 19:58:20

通过这样做，我不会创建6个键来为我的数据中的单个6长度值建立索引吗？例如。 ABCDEF必须通过键映射：ABCDE，ABCDF，ABCEF，ABDEF，ACDEF，BCDEF。这将大大增加索引时间和内存。也看稍微修改问题的更新。 – hashable 2011-05-09 19:59:39

我在这里是“每个人都不知道明显的”。

只需使用任何可用的快捷键/值查找。并查找所有可能的值。这是一个小集，不会花很长时间。除了存储数据6次以外的任何其他情况都会变慢。

如果你有很大的词汇量，那么我以前的答案是适当的。

这是我的旧（坏）答案。

我会坚持他们在一个数据库与多个连接索引。有多少取决于你。

至少我会有2.我会有一个索引(col1, col2, col3, col4, col5, col6)和(col4, col5, col6, col1, col2, col3)。这意味着，无论哪一列丢失，都会有一种获取数据的方法，并且只能查看最多1/1000条记录。如果您希望可以索引(col1, col2, col3, col4, col5, col6)，(col3, col4, col5, col6, col1, col2)和(col5, col6, col1, col2, col3, col4)以将搜索限制为1/10000的数据。这再次使用了一半的内存，但速度提高了10倍。（警告：我不能保证MySQL能够成功找出它应该使用的索引，我希望其他数据库能够正确使用，但是没有经过测试。）

如果你不想使用数据库，你可以使用平衡的二叉树，就像我上面提到的使用索引一样。对于任何给定的搜索，挑选具有尽可能深的缺失元素的树。做一个范围搜索。仅针对感兴趣的行筛选返回的数据。事实上，这正是一个好的数据库应该在这些索引上做的事情。

来源

2011-05-09 19:55:25 btilly

db是简单的解决方案，但另一种解决方案是树，每个节点选择一个字符，叶子将包含可能的结果和计数数组。然后，树中只需要5个步骤就可以匹配一个字符串。但创建树会花费N * C时间，其中N是项目数量，C是每个项目中的字符数量。通配符只是树中的一个节点，它将同时从输入中移除一个字符，但保持可能的结果不变。

来源

2011-05-09 20:07:37 tp1

决定与尝试似乎是最好的：叶上的字符串发生的数量，你可以很容易地设计函数，将返回所有可能的字符串与一个缺少的字符在O（log n）时间，然后你只是遍历这个少量的字符串，搜索出现的最大数量。如果你使用从A到Z的字符，最多会有26个这样的字符串，所以迭代不会花费太多。

据我所知，Lucene的使用这样的机制在内部对其wildcards search，这样你就可以连接你的字符，索引他们KeywordAnalyzer（省略词干），然后搜索为“ACB？DJ”。这里唯一的限制就是Lucene不能处理带有第一个“？”的搜索，但是你可以通过在开始处添加一个额外的char来绕过它（只是欺骗绕过Lucene检查），或者为反向词增加一个索引（将会提高性能用通配符作为第一个字符很多）。

最后，如果您首先必须计算出现次数，您可以使用一些机器学习计划，如决策树来处理所有工作。有些情况下，当使用决策树来压缩数据库并加快搜索速度时，可以这样做。使用行作为实例，将字符的位置作为属性，并将自己的字符作为属性值。然后运行一些像C4.5这样的算法（您可以使用Weka's实现，称为J48），并进行最少的修剪和运行分类 - 算法将完成剩下的工作！

来源

2011-05-09 20:28:42 ffriend

您现在可以使用通配符开始查询。请参见[QueryParser.setAllowLeadingWildcard]（http：//lucene.apache。org/java/3_0_1/api/core/org/apache/lucene/queryParser/QueryParser.html＃setAllowLeadingWildcard（boolean）） – 2011-05-15 06:19:25

用于模式匹配的数据结构上的大数据

回答

相关问题