分词搜索的多种解决思路

分词搜索的多种解决思路

Tags
Trie树
分词算法
SQL
索引设计
ELK
倒排索引
CreatedTime
Aug 24, 2022 04:54 AM
Slug
2021-07-09-fen-ci
UpdatedTime
Last updated August 24, 2022

基础:中文分词

对于中文的全文索引,需要借助「分词算法」,将句子拆分为词语。再根据词语建立字典树。比较成熟的分词库是「jieba 分词」:

方法一:SQL的全文索引与 Like

原理

全文索引的单位是「词语」,Like 的基本单位是「字符」。比如对于“我爱中国”这句话,如果是全文索引,“我”、“中国”、“爱”都可以匹配到,但是“爱中”就不行。但是对于 Like,则都可以。
全文索引的数据结构是一棵 Trie 树,或者基于此的延伸数据结构,比如 DAT。好处就是,搜索复杂度不取决于数据量(非常牛逼的特性),而取决于字典树的深度,而字典树的深度,取决于词语的长度。

适用场景

对于 Like,适合姓名、昵称、性别等此类的小字段。
对于全文检索,适合中长文本。

方法二:全文搜索引擎

比如ELK。就能很好地解决此类场景。ELK原理是「倒排索引」。
优点是完备的解决方案,不需要手动设计实现搜索算法;缺点是开发和运维都比较复杂,对于不频繁更新的短文本,比如文章标题,有些大材小用。

方法三:分词+内存 hash

原理

将文本分词后,对词语进行 hash,根据 hash 值查询对应的文章列表 docList。
再对所有的分词 hash 的结果查询到的文章列表,进行交集运算。
在时间复杂度上,这与数据量大小无关,复杂度只与进行交集运算的结果集大小有关。

适用场景

适合不频繁更新的短文本,比如文章标题。
优点是,纯内存操作,性能高,实现简单,容易水平扩展;缺点是,不容易持久化,需要设计相关策略,防止数据丢失。

方法四:分词+ Trie / DAT

原理

将文本分词后,以词语作为路径,建立 Trie 树。树的叶子结点,就保存着对应的文章列表集合。
当 Trie 树内存消耗过多,可以考虑换用 DAT(double array trie)。但是它需要提前建立索引,不可以实时更新。

适用场景

适合不频繁更新的短文本,比如文章标题。
和「分词+内存Hash」一样,都是纯内存操作,性能高,容易水平扩展。
缺点是,不容易持久化,需要设计相关策略,防止数据丢失。

参考链接