PHP小技巧之计算文本相似度
- 发表于
- PHP
需求:对于内容进行相似度对比,如果有之前的内容和当前发布的内容标题相似度到达某个阈值时则禁止发布或进行其他的一些操作。
看到这个需求,可能就想到需要使用某种算法来实现,例如:TF-IDF
、基于空间向量的余弦算法、最长公共子序列、最小编辑距离算法、Jaccard
系数等等。
levenshtein 编辑距离越小相似度越高
最小编辑距离算法在 PHP 中已经有了实现:levenshtein,计算两个字符串之间的编辑距离。
1 2 3 4 5 6 7 |
levenshtein( string $string1, string $string2, int $insertion_cost = 1, int $replacement_cost = 1, int $deletion_cost = 1 ): int |
编辑距离,是指两个字符串之间,通过替换、插入、删除等操作将字符串 string1
转换成 string2
所需要操作的最少字符数量。
该算法的复杂度是 O(m*n)
,其中 n 和 m 分别是 string1
和 string2
的长度。
来点废话文学演示一下:
1 2 3 4 |
echo levenshtein('听君一席话', '听君一席话'); // 0 echo levenshtein('听君一席话', '如听一席话'); // 3 echo levenshtein('我不要你觉得', '我要我觉得'); // 6 echo levenshtein('今天的天气怎么样?', '你吃饭了吗?'); // 21 |
当编辑距离越小时,相似度就越高。
similar_text 两个字符串相似度函数
除了编辑距离,PHP 还直接提供了一个计算两个字符串相似度的函数:similar_text。
1 |
similar_text(string $string1, string $string2, float &$percent = null): int |
返回两个字符串中匹配字符的数量。
通过将引用作为第三个参数传递,similar_text()
会通过将 similar_text()
的结果除以给定字符串的平均长度,乘以百分比来计算相似度 100。
1 2 3 4 5 6 7 8 9 10 11 |
echo similar_text('听君一席话', '听君一席话', $percent); // 15 echo $percent; // 100 echo similar_text('听君一席话', '如听一席话', $percent); // 12 echo $percent; // 80 echo similar_text('我不要你觉得', '我要我觉得', $percent); // 12 echo $percent; // 72.727272727273 echo similar_text('今天的天气怎么样?', '你吃饭了吗?', $percent); // 6 echo $percent; // 26.666666666667 |
这个函数的相似程度计算依据 Programming Classics: Implementing the World's Best Algorithms by Oliver (ISBN 0-131-00413-1)
的描述进行。
这个函数的实现使用了递归调用,所以可能会导致整个过程变慢或者变快,该算法的复杂度是 O(N**3)
,N 是最长字符串的长度。
当 $percent
越大时,相似度越高。
匹配字符的数量是通过找到最长的第一个公共子字符串来计算的,然后递归地对前缀和后缀执行此操作。将所有找到的公共子字符串的长度相加。
原文连接:PHP小技巧之计算文本相似度
所有媒体,可在保留署名、
原文连接
的情况下转载,若非则不得使用我方内容。