lucene使用的字符串匹配算法

Question

我想知道Apache Lucene使用的字符串匹配算法.我一直在经历着由下式给出的Lucene使用的索引文件格式在这里.似乎lucene存储文本中出现的所有单词,以及每个文档中出现的频率.但据我所知,对于有效的字符串匹配,它需要预处理文档中出现的单词.

示例:搜索"iamrohitbanga是stackoverflow的用户"(使用模糊匹配)

在一些文件中.

有可能是一个包含字符串"rohit banga"的文档

为了找到子字符串rohit和banga存在于搜索字符串中,它将使用一些有效的子字符串匹配.

我想知道它是哪种算法.如果它做了一些预处理,java api中的函数调用会触发它.

Answer 1

正如Yuval解释的那样,一般来说,Lucene适用于完全匹配(通过在索引和查询时使用分析器对术语进行规范化).

在Lucene中继代码(尚未发布任何版本)中,事实上对于不精确匹配(例如Regex,Wildcard和Fuzzy)存在后缀树使用.

这种方式的工作方式是Lucene术语词典本身实际上是后缀树的一种形式.您可以在几个地方提到的文件格式中看到这一点:

因此,如果前一个术语的文本是"骨骼"而术语是"boy",则PrefixLength为2,后缀为"y".

术语info索引通过以特定间隔(默认情况下每128个术语)索引此树为我们提供"随机访问".

如此低级别它是一个后缀树,但在更高级别,我们利用这些属性(主要是在IndexReader.terms中指定的属性将术语字典视为确定性有限状态自动机(DFA):

返回从给定术语开始的所有术语的枚举.如果给定的术语不存在,则枚举位于第一个术语大于提供的术语.枚举由Term.compareTo()排序.每个术语都大于枚举中的所有术语.

不正确的查询(如Regex,Wildcard和Fuzzy)本身也被定义为DFA,"匹配"只是DFA交集.