知识卡片
模糊索引与编辑距离
前面的索引都假定数据是精确的,只能查精确值或按排序查范围,不能搜索相似的键,比如拼错的单词。模糊查询需要不同技术。
全文搜索引擎通常支持:把一个词扩展为同义词、忽略语法变体、查找在同一文档中彼此靠近的词,以及各种依赖语言分析的功能。为应对拼写错误,Lucene 能在一定编辑距离内搜索(编辑距离 1 表示增、删或替换了一个字母)。
实现方式:Lucene 的词典使用类似 SSTable 的有序文件(关键词到包含它的文档 ID 列表的映射,即倒排索引,在后台合并)。查找时需要一个小的内存索引告诉查询去排序文件的哪个偏移量找键:
| 引擎 | 内存索引 |
|---|---|
| LevelDB | 一些键的稀疏集合 |
| Lucene | 键中字符的有限状态自动机,类似 trie |
这个自动机可以转换成 Levenshtein 自动机,从而在给定编辑距离内高效地搜索单词。更进一步的模糊搜索技术正走向文档分类和机器学习,属于信息检索领域。
与 [[SSTable的排序收益]] 对照可以看出:同样是有序文件加稀疏内存索引的思路,把内存索引换成自动机,就从“精确/范围查找”扩展到了“相似查找”。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第三章:存储与检索 · 查看原书依据
在LevelDB中,这个内存中的索引是一些键的稀疏集合,但在Lucene中,内存中的索引是键中字符的有限状态自动机,类似于trie 【38】。
参考来源
- 位置:《数据密集型应用系统设计》第03章《第三章:存储与检索》其他索引结构·全文搜索和模糊索引(源文件:extracted/数据密集型应用系统设计/_epub-src/ch3_split_002.html,来源项目 book-sources)
- 结论依据:第三章“全文搜索和模糊索引”说明前述索引只支持精确值与范围查询,全文引擎的同义词、语法变体、邻近搜索与编辑距离,Lucene以类SSTable结构存词典并用类似trie的有限状态自动机作内存索引,可转换为Levenshtein自动机做编辑距离搜索;“用SSTables制作LSM树”说明Lucene关键词到文档列表的映射。
- 原始内容:在LevelDB中,这个内存中的索引是一些键的稀疏集合,但在Lucene中,内存中的索引是键中字符的有限状态自动机,类似于trie 【38】。