PHP中的字符串相似性:levenshtein类似于长字符串的函数

Question

levenshteinPHP中的函数适用于最大长度为255的字符串.在PHP中计算句子相似度得分的好方法是什么.

基本上我有一个句子数据库,我想找到近似重复. similar_text功能不给我预期的结果.对我来说,检测类似句子的最简单方法是:

$ss="Jack is a very nice boy, isn't he?";
$pp="jack is a very nice boy is he";

$ss=strtolower($ss);  // convert to lower case as we dont care about case
$pp=strtolower($pp);

$score=similar_text($ss, $pp);
echo "$score %\n";  // Outputs just 29 %

$score=levenshtein ( $ss, $pp );
echo "$score\n";  // Outputs '5', which indicates they are very similar. But, it does not work for more than 255 chars :(

Answer 1

该levenshtein算法具有时间复杂度O(n*m),其中n和m是两个输入字符串的长度.这是非常昂贵的并且计算长字符串的这种距离将花费很长时间.

对于整个句子,您可能希望使用diff算法,例如参见:突出显示PHP中两个字符串之间的差异

话虽如此,PHP还提供了similar_text更复杂的功能(O(max(n,m)**3)),但似乎可以在更长的字符串上工作.