我正在进行网页内容过滤，其中有10000个单词出现在页面上。我必须与我的1500-2500字词典匹配。而且我必须找出页面中是否有任何词语。精确的字符串模式匹配是完美的数据结构吗？
请建议我最好的数据结构来存储我的模式搜索速度更快。 我学过树结构。但让我们说一个字（abc），它可能对下一个字符有26个可能性。我必须为下一个节点保留26个点。 （它消耗26x4字节）。我无法花费那么多的内存来存储每个单词的模式。
建议我最好的搜索，最好的记忆。
我在这个领域的初学者。
你的问题是由Aho-Corasick精确求解。经过一些预处理后，您可以在O（n）时间内处理每个网页，其中n是该网页的大小。您将需要大约与字典一样大的辅助存储。
你的内存限制，似乎很严重，但如果你真的需要减少内存占用，你可以使用在给定的状态存在的所有字符的列表，而不是具有每个州的26个字符数组。在处理网页时，您需要浏览这些字符，这会使您的速度减慢一个相当显着的常数因素，但您将节省空间。
我已经为2000个模式实现了aho-corasick，每个模式由121-123个charachters组成。我创建了下一个链接和后缀链接（失败链接）以加快搜索速度。但它为293046个字符消耗4.5Mb。我们可以减少这棵树到1MB。 –
我的结构是： struct _treenode { char ch; short int child; //（为下一个孩子计数） char * value; //（用于表示模式名称） struct _treenode ** next; //（下一个子链接） struct _treenode * suffixlink; //（失败链接） }; –
如果你真的想节省空间，我会建议如下： 1. child：这个值只能和字母一样高，所以它只能是一个字节。 2.价值：不要将名称存储为指针，我假设你有这些名称躺在某处，所以只需将索引存储到该数组中。这个指针（假设你在一个32位系统上）占用四个字节，但是如果你只有2k个字，那么你只需要两个字节就可以索引到这个大小的数组中。 如果你可以做1和2，那么你将节省25％的空间，因为你的结构将从16个字节下降到12个。这至少是一个开始。 –
为了获得最佳的搜索是特里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索引开始，在每一步中，根据比较一个索引处字典的字符串与第二个索引处的字符的结果，增加其中一个，如果它们匹配，则您匹配并转到你有下一个单词，否则如果你的单词低于字典单词，你会去下一个单词（因为你之前已经通过了所有字典单词并没有找到匹配），否则你去下一个单元到字典（尝试到比你的话不低于字典中找到一个词）
使用一个trie，你不必“为下一个节点保留26个指针”。您可以动态分配一个已排序的指针数组。 – Justin