快速搜索，無標記化

Question

我正在尋找一種方法來快速全文搜索一百萬個1千字節的字符串。

加速這類事情的流行方式（Lucene或MongoDB中的文本索引）似乎在搜索時間從分割內容字符串到索引構建時產生的令牌中獲得了很高的性能時間。這些令牌基於自然語言。不過，我想避免這種標記化，因爲我想搜索與自然語言詞無關的字符串。

我在尋找類似於SQL「LIKE'％abc％'」但不僅僅是「abc」的東西。對於諸如「a.1」的字符串來說，並且匹配諸如「.......... a.123 ........」的文檔

我得到從理論上講，這是使用suffix trees的可能，但我還沒有找到適當的Java實現這些。 「適當的」我的意思是不依賴整個後綴樹一次加載到內存中。

這個發明了嗎？

Answer 1

「適當的」我的意思是不依賴整個後綴樹一次加載到內存中。

據我所知和了解後綴樹，沒有辦法只加載後綴樹的一部分，並使用它。你可以通過使用算法，如Aho-Corasick或Boyer-Moore算法來清除這個問題，如@fge所述。

實現的一個，必須poppular是： https://github.com/abahgat/suffixtree

也有好的和簡單alghorithm找到字符串的子字符串： Aho–Corasick algorithm 這在「佈局很好編譯原理，技術和工具「例如 此algothm用於病毒數據庫中的病毒簽名和DNA處理非常令人印象深刻的抗病毒搜索。