算法模式匹配

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，但從我所瞭解的更高的空間效率。