Yskin's Blog

寻找相似文章，这真是个复杂的问题。以前想过用WordPress Related Entries，但是觉得要修改数据库，麻烦。后来有了UTW，他提供了根据tag是否相同来查找相似文章的功能。这个功能用了一段时间，觉得还不是太好用。我前几天查看了一下他的源代码，他有按照文章的相同tag数进行判断，比如一篇文章有两个tag和当前文章相同的就比只有一个tag相同的排在前面，不过如果相同tag数一样的话，他就按照发布时间顺序，最新的文章排在最前。这也不能怪UTW，他也只能按照tag的相同与否进行判断，其他的也不归他管。

6月30号开始进行了一番研究，判断两篇文章标题是否相似主要有三个方法：自行写比较代码、通过PHP提供的函数进行比较、通过MySQL提供的SQL查询语句进行比较。下面分别进行说明：

一、自行写代码

要比较两个字符串的相似度是个很复杂的命题，很多科技论文讨论了这个问题，当然大多都很深奥，可以用于搜索引擎比较两个网页的相似度以便去除相似网页用的。我们用着小小的PHP，当然不能用那么复杂的算法。

我大概的想法是，先写一个找出两个字符串的最大匹配的算法，也就是两个字符串的最大共同子串。有了这个算法后，使用这个算法找出两个字符串的前几大匹配，然后做一下加权得到相似程度，数值越大相似度越高。

在网上找到一篇论文：《串的最大匹配算法》，详细介绍了利用二维数组来找出两个字符串的最大匹配的算法。我觉得可以这样：把两个字符串标志为A、B，将A中的每个字符提出，到B串查找相同的字符，得到A,B中的一个字符相同的位置后，再从此位置开始往后找出最大的匹配。这样将所有的匹配找出，比较后就可以得到两个字符串的最大匹配了。

二、通过PHP提供的函数进行比较

PHP提供了几个比较字符串相似度的函数：similar_text(),levenshtein(),soundex(),metaphone()。

similar_text()函数原型：int similar_text ( string first, string second [, float &percent] )
返回同时存在于两个字符串中的字符的个数，通过percent参数返回两个字符串的相似度。

在PHP手册的similar_text页面有一段貌似具体的实现代码。这个函数比较简单而又方便，不过他的复杂度也有O(N**3)，N为较长字符串的长度。

levenshtein()返回从第一个字符串变换到第二个字符串需要的次数。在这个页面找到一段描述：

相似性常常用 Levenshtein 距离来衡量，指的是俄国科学家 Vladimir Levenshtein 在 1965 年发明的算法。根据 Levenshtein 距离可以计算将一个短语转化成另一个短语时需要执行的插入、删除和置换的次数。比如，要将“magazine”变成“magazines”，只需要输入一个字符（“s”）， 因此它们之间的距离是“1”。八个字母中取一就是 12.5%（距离通常相对短语来计算），因此采用这种方法的 CAT 工具用 87.5% 来表示这两个词之间的相似性。

不过这个算法也有缺陷，比较适合英语之类的拉丁语系而不适合中文。soundex()函数和metaphone()函数返回两个英文单词的发音键，显然他们也不适合中文。

三、MySQL提供的SQL查询语句

我是这样想的：为wp_posts表中的post_content项添加FULLTEXT全文索引类型的索引，然后利用SQL语言中的MATCH子句来查找相关的文章。具体可以参考MySQL手册中的《全文搜索功能》。

WordPress Related Entries插件也是用的这个办法，不过他是给post_name和post_content项添加的索引，然后根据每篇文章的post_name当做keyword去匹配。你也可以用<!--kw=keyword1 keyword2-->手工给文章添加一个keyword。