算法模式匹配

Question

背景

我设计这将文本转换从一种语言到其他的应用程序。例如，输入文本hello将被转换为指定的语言文本。这是通过为每种语言设置查找表完成的。转换算法有以下步骤。

1. 查找完全匹配。整个字hello将是该模式。如果发现任何匹配，请停止处理并返回匹配。
2. 否则从左到右从每个角色开始查找，直到完成所有组合。例如：Iteration1：pattern = h，2nd - he，3rd - hel等等。匹配的令牌将保存在临时缓冲区中，并在没有更多匹配时返回。这工作像最大蒙克规则。
3. 如果找到匹配项，匹配的文本将从原始文本中删除，并继续处理剩余的文本。

该算法将不得不遍历输入文本多次，并导致二次复杂性。我试图通过在树结构中安排查找表来优化这一点（非常类似于后缀树）。如果没有查找文本h，hel，lo，将举办类似

root 
--h 
----hel 
--lo 

这将帮助我避免不必要的查找。匹配h后，只有当h节点有孩子时，我才需要转到下一个字符。这大大减少了迭代的次数。

问题

1. 这是什么样的数据结构的名字吗？是否有可用于C或C++的现成实现？
2. 您是否看到上述算法或数据结构有任何可能的改进？

有什么想法......？

Answer 1

看看'Trie'数据结构。

为什么不利用Lucene索引的那个文本非常快速的方式，甚至更多 - 索引包括算法

• steming
• 保险丝匹配

等。

Answer 2

一个三元搜索树可能是你在说什么。它类似于一个trie，但从我所了解的更高的空间效率。