正則表達式（glob）搜索樹

Question

任何人都知道如何適應搜索樹來處理有限的正則表達式？任務是，根據文件名，找到與該文件名匹配的所有節點。節點可能包含通常的文件名稱（*和？）。顯然，由於這是一個搜索樹，速度是關鍵。

編輯：我應該補充一點，速度最重要的情況是排除比賽的平均時間。也就是說，在大多數情況下，匹配將失敗。

個例子：假設樹包含以下節點：

FOO，酒吧，FOO *，*酒吧，酒吧富

搜索富將返回節點1和3 搜索欄？將返回節點2和4. 搜索FOB將不返回任何節點。 正在搜索fooxbar將返回節點5. 搜索foobar會返回節點3和4.

Answer 1

aho-corasick搜索樹將符合法案。 Aho-Corasick關於這樣的事情Tries一篇很好的文章，並在進化用來代替正則表達式搜索Etrie

編輯的實現：做全字符串匹配，可以添加開始和結束錨狀態，如果掃描多行數據，你可以添加新行開始和結束。您也可以刪除添加交叉鏈接的部分，從而開始不同的匹配，這也允許更快的排除。

另一種用於檢查字符串集中成員資格的算法是CritBit。這不具有正則表達式，但它很簡單，並測試完整的字符串。