Full text search(FTS) 技术调研

发表于 |

主要介绍 FTS 的一些实现。

分词技术

ngram

字典结构

ngram bloomfilter

  • 生成 N-gram： 将一个输入字符串生成所有可能的 N-gram。
  • 存储到布隆过滤器： 对每个 N-gram 使用多个哈希函数，将其存储到布隆过滤器中。

查询： 对查询的字符串生成对应的 N-gram，逐个检查它们是否存在于布隆过滤器中。

  • 如果布隆过滤器判定所有 N-gram 存在，说明可能是匹配。
  • 如果至少有一个 N-gram 不存在，可以确定不匹配。

缺点：

  • 存在 FP
  • 不支持删除

BTree

跳表

KV 结构

存储分词后的倒排索引

1
2
3
4
5
6
7
"OceanBase" -> [Doc1, Doc2]
"is" -> [Doc1]
"a" -> [Doc1]
"distributed" -> [Doc1]
"supports" -> [Doc2]
"full-text" -> [Doc2]
"search" -> [Doc2]

FST(Finite-State Transducer)

FST 是一种 Trie 树的结构。

MultiValue Index