代码之家 › 专栏 › 技术社区 › ivan_ivanovich_ivanoff

全文索引器(或缓存)如何工作?

full-text-search indexing caching java

ivan_ivanovich_ivanoff · 技术社区 · 16 年前

我想知道,如何实现全文搜索系统,以便能够查询数以百万计的作品很快? 请注意:我是不讨论通过在空白处分隔内容来标记内容的系统,但讨论能够问偶数 代币中间的部分 (这是一个真正的挑战)。

背景资料
我尝试了一个自制的字符串缓存器(使用Java),它可以搜索。对于字符串,给定一个子字符串作为查询。子串不是必修的位于潜在检索字符串的开头。

它在大量的字符串上工作。缓存是使用
TreeMap<Character,TreeSet<String>> .

添加条目
对于要添加的字符串中的每个唯一字符:
获取该字符的集合,并将该字符串添加到该集合中。

示例:“test”首先在“t”、“e”、“s”中拆分。
然后,我们检索那些三个键,每一个都加上“测试”。

奎利翁
查询是通过将查询拆分为唯一字符来完成的, 检索每个字符a Set<String> ,建立所有集合,最后使用 contains() 确保正确查询字符的顺序。

基准
在一 3GHz 机器,我补充道 2万带弦 平均长度 10 ,随机内容。
多恩一百查询。它采取: 最小:0.4秒,平均:0.5秒,最大:0.6秒 .
1.5 GB 记忆被浪费了。

3 回复 | 直到 16 年前

yairchu 16 年前

一种方法是存储文本所有尾部的排序排列(从某个点到结尾的文本)。

然后为了找到一个子串,你用二进制方法在循环移位中搜索它。使用32位整数的内存为每个原始字符4字节。

我听说有一种方法可以通过存储 Burrows-Wheeler transform 文本(每一个原始的1个字母),但我似乎找不到任何参考。

eulerfx 16 年前

我实现了这样一个系统,对于其中一个网站上的建议下拉列表,使用n-gram索引,特别是3-gram。你把一个单词分成n个字母,比如“hel lo”,你会得到“hel”,“lo”。然后构建一个索引,用n个grams作为键,并用它们的单词作为值。(我用TIE速度,记忆力没那么重要)。接下来,对于一个给定的查询,您将它按照与索引期间相同的过程分解为n个gram,并对每个n个gram执行查找,以获得可能匹配的列表。从该列表中,您可以选择匹配n-grams数量最多的单词。你也可以使用各种启发式方法。一个是在单词开头的匹配通常更重要,所以你可以用一个$填充所有单词。

Thilo 16 年前

你可能想看看露西。但我认为一般来说,它们会标记输入文本。可能不只是空白,而且在单词序列中使用较短的。我不认为一个字符标记是可行的。

对于东方语言(没有空格的地方),通常使用双字符序列。与英语的主要区别在于,两个字符通常已经是一个单词,而要从中提取的基字符集要大得多,因此在双字格中已经有了大量的信息,并且有了更多独特的双字格。