我正在研究网页内容过滤，其中有 10000 个单词出现在页面上。我必须将它与我的 1500-2500words 词典相匹配。我必须找出页面中是否存在任何单词。
请建议我最好的数据结构来存储我的模式更快的搜索。我研究过树结构。但是让我们取一个可能有 26 种可能的下一个字符的单词 (abc)。我必须为下一个节点保留 26 个指针。（它消耗 26x4 字节）。我不能花那么多内存来存储每个单词的模式。
建议我最好的搜索和最好的记忆。
我是这个领域的初学者。
问问题
698 次
2 回答
0
最好的搜索是 trie http://en.wikipedia.org/wiki/Trie 为了最好的记忆和搜索的复杂性，我建议你使用http://en.wikipedia.org/wiki/Suffix_array或http： //en.wikipedia.org/wiki/Suffix_tree 另一种方法是通过对字典（O（NlogN））和单词 O（MlogM）进行排序，然后通过一次遍历检查每个元素是否匹配 O（N + M）。您从 2 个索引开始，并且在每一步中，您根据将一个索引处的字典字符串与您在第二个索引处的单词进行比较的结果来增加其中一个索引，如果它们匹配，则您有一个匹配项并转到下一个。您拥有的单词，否则如果您的单词低于字典单词，则转到下一个单词（因为您之前已经浏览了所有字典单词并且没有找到匹配项）否则您转到字典中的下一个元素（尝试在字典中找到一个不低于您的单词的单词）
于 2012-06-12T09:31:09.723 回答
0
Aho-Corasick完全解决了您的问题。经过一些预处理后，您可以在 O(n) 时间内处理每个网页，其中 n 是该页面的大小。您将需要与您的字典大致一样大的辅助存储量。
您的内存限制似乎非常严重，但如果您确实需要减少内存占用，您可以使用在给定状态下存在的所有字符的列表，而不是在每个状态下使用 26 个字符的数组。在处理网页时，您将需要扫描这些字符，这会大大降低您的速度，但您会节省空间。
于 2012-06-12T23:41:25.560 回答