我想知道,全文搜索系统是如何实现的,能够查询 数以百万计的条目非常快? 请注意:我不是谈论通过在空格处分隔内容来标记内容的系统,而是谈论能够 甚至查询 token 中间的部分(这是一个真正的挑战)。
背景信息
我尝试了一个能够搜索的自制字符串缓存器(使用 Java)
对于字符串,给定一个子字符串作为查询。子字符串不是必需的
位于潜在检索字符串的开头。
它适用于大量字符串。
缓存是使用
完成的
TreeMap<Character,TreeSet<String>>
.
添加条目
对于待添加字符串中的每个唯一字符:
获取该字符的集合,并将字符串添加到其中。
示例:“test”首先拆分为“t”、“e”、“s”。
然后,我们检索那些集合
三个键,并为每个键添加“test”。
查询
查询是通过将查询拆分为唯一字符来完成的,
为每个字符检索一个 Set<String>
, 建立一个交叉点
所有集合,最后使用 contains()
搜索交集确保正确
查询字符的顺序。
基准
在 3GHz 机器上,我添加了 2'000'000 字符串,其平均长度
共 10 个,随机内容。
完成了 100 个查询。耗时:最小:0.4 秒,平均:0.5 秒,最大:0.6 秒。
1.5GB 的内存被浪费了。
最佳答案
一种方法是存储文本所有尾部的排序排列(从特定点到结尾的文本)。
然后为了找到一个子字符串,您可以在这些循环移位中进行二进制搜索。使用 32 位整数使用的内存将为每个原始字符 4 个字节。
p.s:我听说有一种方法可以通过存储 Burrows-Wheeler transform 来完成类似的事情。文本(每个原始字符 1 个字符),但我似乎无法找到任何对它的引用..
关于java - 全文索引器(或缓存)如何工作?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/1009868/