C++实现轻量级的关键词查找系统

本是古典何须时尚 2022-04-01 18:39 372阅读 0赞

多数游戏中，都会提供关键词查找的功能，即通过输入一个子串，最终返回所有包含该子串的记录；

具体的应用场景包括：陌生人查找, 公会查找，消息记录查找等等。

对于这类需求，查找的数据范围往往会很广，如果是采用遍历字符串匹配的方式查询，时间开销会非常大。

而如果存储方面使用的是类似于mysql这种支持like子句模糊搜索的数据库，实现起来简单，但具体的计算压力也全都交给了DB。

那么项目中如果没有使用支持模糊查找的数据库，怎么高效实现类似的需求呢？

*  ## 一个备选的方案 ##

提到大量字符串集合的匹配，最容易想到的解决方案是字典树(trie树), 将每一个字符作为树的节点, 而树的高度则为字符串长度的上限，整体设计思路比较直观。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0FYdWFuX0s_size_16_color_FFFFFF_t_70][]

但是trie树的缺点也很明显：

1.  树的每一层都可能出现同一个字符的节点，在每条记录中的字符均匀随机的情况下，内存开销太大。
2.  如果想减少内存消耗，则需要进行节点压缩，但是插入删除记录的时间开销会增大，代码实现也将变得复杂。
3.  如果采用的是最朴素的trie树，只能快速查找出前缀匹配或是后缀匹配的记录，如果需要快速查找关键字出现在中间的记录，则需要针对性的建立索引，进一步增加内存消耗。

总结来说，trie树是一个简单且查找效率很高的方案，但是内存消耗不可控，如果针对内存进行优化，代码实现会变得复杂。

那么还有没有简单高效同时内存开销更小的解决方案呢？

*  ## 可优化的方向 ##

我们可以将trie树理解为一张庞大的索引表，正因为它的庞大，所以将查找效率做到了极致(接近O(1))。

空间时间比例不均衡，造就了算法可优化的空间，举个栗子：

(内存消耗1G, 时间消耗0.1ms) 优化后 (内存消耗100M, 时间消耗2ms)，虽然内存消耗只减少了10倍，同时时间消耗提升了20倍，但也是及其合算的。

出于这种优化思路，我们可以考虑减少索引表的内容，扩大查找范围，达到均衡时空比的目的。

*  ## 另一种索引方案 ##

trie树最大的冗余在于，树的每一层都可能出现同一个字符的节点，由此我们可以尝试把trie树不同层的同一字符节点组合在一起：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0FYdWFuX0s_size_16_color_FFFFFF_t_70 1][]

嗯，索引建好了, 接下来应该如何查找呢?

考虑搜索字符串bda, 我们首先找到了a(0,1,2), b(0,1,2,3), d(0)三个索引节点。

发现**节点d包含的记录是最少的，接着开始遍历节点d指向的所有记录**，很快，通过**子串匹配算法**，我们找到了记录0: abda。

合理规避了内存的冗余，而且适度的缩小了查找匹配的范围，是一种可行的方案。

*  ## 插入，删除，更新 ##

插入,删除和更新的思路是一致的，找到字符串中的所有字符，在针对每个字符更新索引表中的信息。

插入deh:

1.  在原始数组中加入记录<6: deh>。
2.  在d,e,h三个索引节点中加入记录deh所在的下标6。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0FYdWFuX0s_size_16_color_FFFFFF_t_70 2][]

删除abda：

1.  在a,b,d三个索引节点中删除下标0。
2.  找到原始数组中最后一条记录<6: deh>, 在d,e,h三个索引节点中删除下标6。
3.  原始数组中交换<0: abda> 和 <6: deh>，并让原始数组长度-1。
4.  d,e,h三个索引节点中插入下标0。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0FYdWFuX0s_size_16_color_FFFFFF_t_70 3][]

至于如何在各个索引节点中删除下标，可以使用和最后一个元素交换的方式;

也可以将索引节点中的所有下标用stl::set来存储, 数组下标是不可能重复的，同时保证了logN级别的插入删除效率。

更新bebe为afaf

1.  在b,e两个索引节点中删除下标3。
2.  更新<3: bebe> 为 <3: afaf>
3.  在a,f两个索引节点中插入下标3。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0FYdWFuX0s_size_16_color_FFFFFF_t_70 4][]

*  ## 中文处理 ##

我们知道中文是没法像Ascii码一样用一个字节来表示的，那我们在代码中应该如何从一段字节流中分隔出每一个中文并且将其表示出来呢？针对大部分项目中使用的utf-8编码，可以发现如下规律：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0FYdWFuX0s_size_16_color_FFFFFF_t_70 5][]

每个UTF8字符占用1-6个字节，且首字节已经记录了该字符一共占用了多少个字节。知道这条规则后，我们就可以通过比较首字节的方法将字节流分开，并用一个int(4字节)代表每一个中文字符。

*  ## 匹配度优先，以及跨越长度不符的记录 ##

现在，我们可以搜索出包含关键字的所有记录了。

但搜索结果中排在前面的记录有可能只是最早插入的，而不是匹配度最高(搜索关键字在某条记录中所占的比重最高)的。

思考在如下索引表中查找关键字afaf的过程:

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0FYdWFuX0s_size_16_color_FFFFFF_t_70 6][]

1.  比较索引节点a和索引节点f的容量，发现f的容量最小。
2.  开始遍历索引节点f指向的所有记录。
3.  子串匹配得出<0:afafh>和<2:afaf>。

我们发现到遍历过程中一个不合理的地方：

查找的关键字afaf长度为4，记录<1: afb>的长度为3, 是不可能匹配上的。另外，应该先比较长度更小<2:afaf>而不是<0:afafh>。

由此，我们可以考虑给索引节点中的所有记录进行排序，这样每次查找即可从长度符合的字符串开始比较的，先匹配通过的刚好也是匹配度更高的。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0FYdWFuX0s_size_16_color_FFFFFF_t_70 7][]

关于实现，因为索引节点中所有下标是用stl::set存储的，我们可以将下标扩展为<长度,下标>结构体，再给该结构体定义一个比较函数，即可达到排序的目的。 另外如何快速跨越长度不符合的记录呢，我们知道set(红黑树->平衡树)是天然支持二分查找的，比如跳跃长度<4的记录: 我们可以

set.lower_bound(<4, 0>);

很快找到第一个>= <4,0>的记录 <4,2>。

*  ## 分批拉取 ##

分批拉取很简单，每次拉取完成后，记录本次拉取用到的索引节点，以及本批最后一个的后一个索引单元的<长度,下标>。

这样通过lower\_bound函数，仍然可以获取下一批拉取的开始位置。举个栗子：

搜索关键字af：

第一次拉取一条记录返回结果<1: afb>， 同时返回索引节点f ，以及后一个索引单元<4,2>

第二次直接从索引节点f的索引单元<4,2>开始匹配即可。

*  ## 匹配优化 ##

关于字符串匹配算法(BF, KMP, BM, Horspool, Sunday等)，相关文章已经很多了，在这里不展开来讲。

我们使用简洁清晰的KMP算法来加快匹配效率，同时保证整体代码足够轻量级。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0FYdWFuX0s_size_16_color_FFFFFF_t_70 8][]

*  ## 测试 ##

接近7000个UTF8常见中文字符;

随机组合出500W条包含4-7个中文字符的记录并插入索引表：89s；

插入记录, 删除记录, 更新记录 < 1ms；

关键词(1-3个中文字符)查找 < 3ms；

内存消耗<1200M。

*  ## 结语 ##

该方案仍然只是一个适用于中小规模数据的方案，对于海量数据的处理以及容灾处理，还需要思考如何将这套索引系统应用在分布式系统中，一条思路是把不同索引节点分布到多个进程中，通过网络通信选择一个最合适的节点进行查找。

对于更进一步的模糊搜索，更多的应该是思考如何分词，以及如何判断各个词语的权重。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0FYdWFuX0s_size_16_color_FFFFFF_t_70]: /images/20220401/e8cd15b01e314785976bf5517d77ddf1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0FYdWFuX0s_size_16_color_FFFFFF_t_70 1]: /images/20220401/bde05e29b9004e23b0abf7eccb1235ed.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0FYdWFuX0s_size_16_color_FFFFFF_t_70 2]: /images/20220401/87e4104050ba4256a81023588f24ab7d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0FYdWFuX0s_size_16_color_FFFFFF_t_70 3]: /images/20220401/4a702b607b144ad588711d760be672e2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0FYdWFuX0s_size_16_color_FFFFFF_t_70 4]: /images/20220401/f0180b9f74c344a5881e4707690b8b81.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0FYdWFuX0s_size_16_color_FFFFFF_t_70 5]: /images/20220401/c71c6bbd66fd41a1b6aa01fd7fb9e072.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0FYdWFuX0s_size_16_color_FFFFFF_t_70 6]: /images/20220401/9e748e9d28c743f28c77d6befc23aae0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0FYdWFuX0s_size_16_color_FFFFFF_t_70 7]: /images/20220401/901316e001404fcf9dde80473a5ae991.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0FYdWFuX0s_size_16_color_FFFFFF_t_70 8]: /images/20220401/b2931b378aa24bc5be07e74fbef87f01.png