java - 快速搜索，无需标记化

Question

我正在寻找一种方法来对一百万个 1 KB 字符串进行快速全文搜索。

加速此类事情的流行方法(Lucene 或 MongoDB 中的文本索引)似乎是通过将内容字符串拆分为索引构建时的标记来获得搜索时的高性能。这些标记基于自然语言单词。但是我想避免这种标记化，因为我想搜索与自然语言单词无关的字符串。

我正在寻找功能类似于 SQL“LIKE '%abc%'”的东西，但不仅仅是“abc”。比如说，对于诸如“a.1”之类的字符串，并使其与诸如“.........a.123........”之类的文档相匹配

我的印象是，理论上，使用 suffix trees 是可能的但我还没有找到合适的 Java 实现。我所说的“适当”是指不依赖于立即将整个后缀树加载到内存中的后缀树。

这个已经发明了吗？

Answer 1

By "appropriate" I mean one that doesn't rely on the entire suffix tree being loaded into memory at once.

据我所知和理解后缀树，没有办法只加载后缀树的一部分并使用它。您可以通过使用算法来避免这种情况，例如 @fge 提到的 Aho-Corasick 或 Boyer-Moore 算法。

必须流行的实现之一是: https://github.com/abahgat/suffixtree

还有一个很好且简单的算法来查找字符串中的子字符串: Aho–Corasick algorithm例如，“编译器:原理、技术和工具”中对此进行了很好的阐述该算法用于防病毒软件中，用于在病毒数据库中搜索病毒签名，以及用于 DNA 处理，令人印象深刻。