c++ - 模式匹配算法

Question

背景

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

1. 寻找完全匹配。整个单词 hello 将成为模式。如果找到任何匹配项，则停止处理并返回匹配项。
2. 否则从左到右开始查找每个字符，直到完成所有组合。例如:Iteration1 : pattern = h, 2nd - he, 3rd - hel 等等。匹配的 token 将保存在临时缓冲区中，并在没有更多匹配时返回。这类似于最大咀嚼规则。
3. 如果找到匹配项，匹配的文本将从原始文本中删除并继续处理剩余文本。

该算法将不得不多次迭代输入文本并导致二次复杂度。我试图通过在树结构(非常类似于后缀树)中安排查找表来优化它。如果有 h、hel、lo 的查找文本，它将被组织为

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

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

问题

1. 这种数据结构的名称是什么？是否有适用于 C 或 C++ 的现成实现？
2. 您是否发现上述算法或数据结构有任何可能的改进？

有什么想法...？

Answer 1

您所说的可能就是三元搜索树。它类似于 trie，但据我所知，空间效率更高。