基于MySQL InnoDB全文索引的文档相似性匹配

最近写了很多MySQL全文索引的知识，是因为工作中使用到了它。由于效率以及准确率的问题，我维护的语篇查重系统一直受到编辑小伙伴的吐槽，在近一个月的苦思冥想中，终于想到了不错的解决办法，初步测试效果理想。

问题叙述

查重系统顾名思义就是将编辑们输入的文章与已经录入的文章进行匹配，如果有重复的再决定文章是否进行使用。

碰到的问题是，线上数据量80万左右，每条数据都是由一套试卷组成，里面包含各种符号，中文英文等大量的数据。我们就要在这样的数据源里面寻找是否有已经使用过的文章。系统在我接手之前使用的MySQL全文索引，关于全文索引的工作机制可以查看其他翻译篇。主要问题是如果编辑输入的检索文章特别长，那么查询会非常慢，结果非常多；如果编辑输入关键词，检索结果也特别多，没有针对性。总之就是既不准确也不高效。

思路变化

1. 首先想到的是去查看除了MySQL全文索引之外的解决方案，例如Sphinx、SimHash等。但是这些都被否定了。Sphinx搜索引擎性能可能会比较高，但是准确率不高。因为MySQL的全文索引与Sphinx是类似的，适合使用关键字搜索，而不适合整篇文章或几个段落进行比对。SimHash算法是我们领导告诉我的，我看了一下，感觉该算法入门有点难（数学比较渣），而且基于文章生成的hash值，再通过海明距离判断相似度并不太适合我们的系统，因为hash值是整篇文章的，但是编辑可能输入其中的某一个段落，这样海明距离比较大，不会被视为相似。（对Sphinx和SimHash的理解较浅，有错误请指正）。

2. 后来结识了公司的实习生，聊天聊到论文查重，我突然意识到公司需要的可能正是像论文查重这样基于段落或者句子的对比方式。 于是开始动手实现基于短句的查重方式。

3. 还是利用MySQL全文索引的相似度计算系统，我想要的只是让其分词技术不是按单词分，而是按句子进行分离。

• 首先想到的是添加专用的字符集和校对规则，将空格视为单词的一部分，这样可以利用MySQL全文索引天然的按句分词了。但是这个方法有一个问题就是需要重启MySQL，经过与运维小伙伴的沟通，得知重启数据库还是比较棘手的，所以pass掉了这个方案。

• 第二个方案就是通过php应用将单词组合成句，下划线在MySQL内置的全文引擎中会被视为单词的一部分。

4. 开始实现

• 删除原数据表的全文索引，创建一个索引表，包含一个主键id和一个全文索引列。全文索引列存储的是一个文章，文章为按下划线组成的句子组成，例如：’i_love_you，mysql_database’，那么辅助索引表就会存储形如‘i_love_you'和’mysql_database'的列。通过实验发现效果不行，因为试卷的文章结构特别乱，导致分词长度比较杂乱，中文和标点处理的也不是特别理想，有的索引特长，即使方案可行效率也不会特别高。

• 最终想出了现在使用的方案。思路与3类似，但是优化了对特殊字符的替换，核心的变化是将拆分过滤好的句子生成hash码，拼接在一起存储在新表的全文索引列，例如现在的全文索引列的内容是‘1982398349,2398203483’，MySQL的辅助索引表里面的内容就是‘1982398349’和‘2398203483’，每个hash码代表一句话，长度基本固定，对查询速率有很大提高。

结果

通过测试收到的成效不错，本地20万数据量，查询秒级，基本没有出现所查篇章在排名第二的情况。

这个解决思路主要是建立在对全文索引的理解之上。

相关代码

// 普通hash函数，函数形式并不是特别关键，碰撞几率越小越好
function myHash($str) {
    $md5 = substr(md5($str), 0, 8);
    $seed = 31;
    $hash = 0;
    
    for($i = 0; $i < 8; $i++){
        $hash = $hash * $seed + ord($md5{$i});
    }

    return $hash&0x7FFFFFFF;
}

还有影响比较大的是html标签，字母大小写，html实体，转义字符，空格的个数等，比如html实体’ '，这里面的分号会影响分词，而数据库存入的数据可能会转实体之后的数据，如果不进行过滤同一句话的hash值也不同。可以用php的stripslashes，html_entity_decode，strip_tags，str_replace等函数进行处理，目的是尽量让字符串简单，保证同一句话的hash值相同。

2018.5.12更新

近期有用户反馈系统有一些缺陷，有两方面，一个是不支持关键字检索，还有就是如果两篇文章主题类似，但是一句完全相同的话也没有，这种的检索不出来。

为了不过大的改动，还是基于全文索引，需要新增加一种方案，用来粗略对比文章主题。经过一些测试，最终实现了一种方案，如下：

1. 两句话“You can also encounter this error with applications that fork child processes, all of which try to use the same connection to the MySQL server.”。

2. 第一步通过标点将文章拆分成句子，分别拆出来两句“You can also encounter this error with applications that fork child processes”和“all of which try to use the same connection to the MySQL server”。

3. 通过定义好的非用词表对每句话进行分割，例如，如下非用词表：

you
alse
can
to
use
the
that
with
these
all
which

拆分之后，第一句话对应的关键字是“encounter”，“error”，“applications”，“fork child processes”；第二句对应的关键字是“try”，“same connection”，“MySQL server”。

4. 将第三部拆分后的文本创建全文索引，注意这里不是对单词创建的索引，而是对上面的每个单词或词组仅创建一个索引，例如“fork child processes”这是一个整体，不会被视为三个单词。进行检索。

经测试基本能满足使用，但不能做到完全准确，检索结果高度依赖非用词表。

上面的方案能解决主题匹配的问题，但是关键字呢？很遗憾的是并不能严格用它做关键字匹配，道理如上第四步所述。

上面的实现方案都是对分本进行hash处理的，分别放在单独的索引表里面，对关键字进行检索可以在原文上创建全文索引来解决。 因为关键字检索通常针对性不太强，所以可以使用MySQL的bool搜索模式，限制每个关键字必须出现来减小范围，如下sql，限制‘database’和‘mysql’必须在body字段中出现：

SELECT id, title, body, MATCH (body) AGAINST ('+database +mysql' IN BOOLEAN MODE)
AS score FROM articles ORDER BY score DESC

2018.7.16 更新

其实这段时间重新看了simhash算法，发现之前存在诸多误解。

首先，simhash算法在匹配文章重复上真的效率很高，如网上所述的如果距离定位3，计算量是可以减少很多的。虽然这点在我们的系统并不试用（我们需要的是近似，海明距离不能定太小），但匹配重复文章还是非常准确的。

其二就是如果a文章被b包含理论上说海明距离应该是0，即使有部分句子不同，距离也应该比较低才对，但是实测如果部分句子不一样，有时候距离还是很大的。（这块可能与采用的simhash实现库有关，没有过多研究）

最后真的感叹算法的神奇。

（完）