一些对模糊搜索的思考

需求

本地扫描得到一个歌曲列表，用户输入关键词/字，通过模糊搜索查询名字中包含关键词/字的歌曲

方法一：并发查找

将歌词列表平均分为几个部分，每个部分使用一个单独的线程搜索，最终搜索结果保存到一个同步容器中即完成搜索。

方法二：构造关键字与歌曲的对应关系

这个方法的难点是将歌曲名拆分成几个词语，比如“光阴的故事”->{“光阴”，“故事”},”光阴独白”->{“光阴”，“独白”}, 再将其转换成关键词->歌名

“光阴”->{"光阴的故事"，“光阴独白”}
“故事”->{“光阴的故事”}
"独白"->{"光阴独白"}
1
2
3

这样就可以构造hashmap的结构了，HashMap<String, List>, 由于关键字是独一无二的，所以hash值唯一，只需要在O(1)时间内就可以找到关键字对应的集合。

这种方法有几个问题：

1、利用分词算法将歌名分解为词语，了解到业界有不少中文分词的算法，如SCWS，ICTCLAS，HTTPCWS, 庖丁解牛分词…

2、占用内存变多，由于一首歌可能会分解出多个词语，所以会重复存储，这里优化的方法可以将歌曲编号，列表只存储歌曲编号

3、容易发生漏检，比如上面的两首歌中，我输入的是“的故事”就找不到，分解出的词语过多时占用内存会变大，过少时漏检率变高，这个分解的度不太好掌握。如果查找不到时，只能切换为方法一去查找。

方法三：排序(一个不成熟的想法)

​ 我突然想到，我们搜索一个歌曲时，一般都是从前往后输入的，比如要搜索“光阴的故事”，那么我输入的顺序应该是“光阴”，“光阴的”，“光阴的故事”,基于这种思路，我们可不可以只考虑顺序输入的情况呢？也就是说我们是可以基于某种规则对歌曲进行排序，比如基于拼音或者是ASCII码，类似关系型数据库中的多级索引的概念，我们可以对歌曲列表制作前几个字符的1-3级索引，查找时只截取输入关键词的前几个字符，使用二分查找算法查找对应的歌曲。

缺点：上面方法只考虑了顺序输入的情况，如果用户不记得完整的歌名，上面的方法就失效了。

方法四：使用三方工具

ES数据库是一个基于Lucene的搜索服务器。它提供了一个分布式多用户能力的全文搜索引擎，是当前比较流行的搜索引擎，可以将歌曲名列表数据导入数据库中，借助它的能力进行模糊搜索。（ES数据库是一个非关系型数据库，官方介绍说它非常擅长于这种类型的搜索，由于没有使用过，这里就不敢贸然的介绍它的底层原理了）