改进单词匹配(展望未来？)算法性能

Question

我试图在http://mandarinspot.com/annotate再现文本注释的功能，并且我有一个解决方案，但我的努力在速度上远远不够。我确实看过字符串搜索算法，每个应用程序的技术各不相同，所以我在这里寻找一些指针。

这个页面取了一部分中文，并在上面添加了拼音，还有一个定义工具提示。我想复制这一页的原因是: 1.我喜欢使用另一种叫Gwoyeu Romatzyh的语音系统，2.用于重新学习编程。

我将尝试描述我正在做的事情，用英语取代基本的汉语。比方说，对于给定的字符串，"Gary吃了葡萄和葡萄柚“，程序必须输出每个单词的定义，比如”集群中生长的适当名称的水果“。现在，由于‘葡萄’和‘葡萄柚’的开头一样，程序需要将它们区分开来(在中文中，没有空格，所以拆分字符串不是一种选择，所以我真的必须解析“Garyateagrapeandagrape果树”，并让它在解析“柚子”时“向前看”)。

我的数据结构是一个树结构，每个节点都包含一个单个汉字和一个父ID。如果该字符是短语的一部分，则父节点告诉我短语的前一个字符是什么。

例如:如果"ABC“是一个中文单词，A可以有ID为1，而没有父ID，B: ID=2和parent=1，C: ID=3，parent=2。对于"ABD"，D有ID=4和parent=2 (B)。每个节点还有一个“definition”数组，它指向一个单独的数组，该数组保存了该字符或单词的英文定义。如果节点不是单词的最后一个，“定义”将为空白。

要解析字符串，

1. 将当前字符(curChar)和后面的字符(nextChar)保持为两个变量。
2. 搜索nextChar与该节点的字符匹配的节点，该节点具有curChar作为父节点。如果这是真的，我想我有两个或两个以上的长词。如果它是错误的，我的结论是curChar和nextChar之间没有任何关系，并输出到curChar之前的所有内容。

谢谢你的建议！

Answer 1

维基百科中的Aho-Corasick将为您提供一个快速算法，当字典中的所有单词出现在流中时，该算法将查找它们。在这种情况下，您可以选择最长的替代方法，就像您一直在做的那样，或者使用动态编程来通过查找包含流中所有字符的单词找到一条路径。

Answer 2

只是一个建议--用哈希表代替树怎么样？如果将其与滚动散列(如Rabin字符串seach算法中使用的哈希算法)结合使用，则会提高查找效率，因此哈希计算每个子字符串需要O(1 )，而查找则采用平均情况O(1)。