改善字匹配（向前看？）算法的性能

我想在http://mandarinspot.com/annotate再现文本注释的功能，我有一个解决方案，但我的努力落在程短在速度方面。我看过字符串搜索算法，每种应用程序的技术都不相同，所以我在这里寻找一些指针。改善字匹配（向前看？）算法的性能

本页面以中国的一大块，并在上面加上拼音发音和定义提示。我想重现此页面的原因是：1.我喜欢使用一种叫做Gwoyeu Romatzyh的不同语音系统，以及2.用于重新学习编程。

我会试着描述我在做什么，用英文替换底层的中文。比方说，对于给定的字符串，“加里吃了葡萄和葡萄柚”，该程序必须为每个单词输出一个定义，例如“[专用名称] [用于摄取食物] [水果成簇生长] [大柑橘类水果]” 。现在，由于“葡萄”和“葡萄柚”开始相同，程序需要将它们区分开来（中文没有空格，所以不能将字符串分开，所以我必须解析“Garyateagrapeandagrapefruit”它在解析“葡萄柚”时“展望未来”）。

我的数据结构是一个树状结构，每个节点都有一个中文字符和一个父ID。如果该字符是短语的一部分，父母告诉我该短语的前一个字符是什么。

例如：如果 “ABC” 是中国字，A可具有的1的ID，并且没有父ID，B：ID = 2和父= 1，和C：ID = 3，父= 2。对于“ABD”，D将具有ID = 4和父母= 2（B）。每个节点还有一个'定义'数组，指向一个单独的数组，该数组拥有该字符或单词的英文定义。如果节点不是单词的最后一个，'定义'将是空白的。

解析字符串，

保持当前字符（curChar），并按照它（nextChar）的性格，两个变量。
搜索nextChar与节点字符匹配的节点，并且此节点将curChar作为父节点。如果这是真的，我认为我有两个或更多字符的单词。如果它是错误的，我得出结论curChar和nextChar之间没有关系，并输出我所有的curChar。

感谢您的咨询！

来源

2012-03-27 Heitor Chang

所以你有算法，这种算法在一种语言中运行良好，但在另一种语言中运行缓慢？ – biziclop 2012-03-27 23:39:01

两者都很慢。我认为在PHP + MySQL中重写会使其更快，但事实并非如此。 – 2012-03-27 23:58:48

Aho-Corasick in Wikipedia会给你一个快速算法，当他们出现在流，其发现从字典中的所有单词。鉴于此，您可以选择最长的替代方案，就像您一直在做的那样，或者使用动态编程来查找流中所有字符的词汇。

来源

2012-03-28 04:19:36 mcdowella

谢谢你的回答！一些初步测试表明，它比我写的快了许多倍。 – 2012-03-28 15:19:18

只是一个建议 - 如何使用散列表而不是树？如果将它与滚动哈希结合使用（比如Rabin-Karp字符串搜索算法中使用的哈希），那么它会提高查找效率，因此哈希计算每个子字符串需要O（1），查找需要平均情况O（1）。

来源

2012-03-28 04:04:10 arya

谢谢你的回答！在阅读了Rabin-Karp的常见应用程序之后，它似乎最适合在较大的文本中查找字符串，因此它不适合我的问题。 Rabin-Karp的典型用法假设你已经知道你在找什么，但在我的情况下，我需要找出文本中下一个最长的单词，并继续“匹配”文本中的所有内容到它的语音值。 – 2012-03-28 18:29:04

改善字匹配（向前看？）算法的性能

回答

相关问题