levenshtein

(PHP 4 >= 4.0.1, PHP 5, PHP 7, PHP 8)

levenshtein — 计算两个字符串之间的 Levenshtein 距离

描述

levenshtein(
    string $string1,
    string $string2,
    int $insertion_cost = 1,
    int $replacement_cost = 1,
    int $deletion_cost = 1
： int

Levenshtein 距离是指将 string1 转换为 string2 所需的替换、插入或删除字符的最小数量。该算法的复杂度为 O(m*n)，其中 n 和 m 分别是 string1 和 string2 的长度（当与 similar_text() 的 O(max(n,m)**3) 相比，此算法的复杂度还是相当不错的，但仍然比较耗时）。

如果 insertion_cost、replacement_cost 和/或 deletion_cost 不等于 1，则算法会选择开销最低的转换方式。例如，如果 $insertion_cost + $deletion_cost < $replacement_cost，则不会执行替换操作，而是执行插入和删除操作。

参数

string1: 用于计算 Levenshtein 距离的字符串之一。
string2: 用于计算 Levenshtein 距离的字符串之一。
insertion_cost: 定义插入操作的开销。
replacement_cost: 定义替换操作的开销。
deletion_cost: 定义删除操作的开销。

返回值

此函数返回两个参数字符串之间的 Levenshtein 距离。

更新日志

版本	描述
8.0.0	在此版本之前，必须使用两个或五个参数调用 levenshtein()。
8.0.0	在此版本之前，如果其中一个参数字符串的长度超过 255 个字符，levenshtein() 会返回 `-1`。

示例

示例 #1 levenshtein() 示例

<?php
// 输入的拼写错误的单词
$input = 'carrrot';

// 要检查的单词数组
$words = array('apple','pineapple','banana','orange',
 'radish','carrot','pea','bean','potato');

// 尚未找到最短距离
$shortest = -1;

// 循环遍历单词以找到最接近的
foreach ($words as $word) {

 // 计算输入单词与当前单词之间的距离
 $lev = levenshtein($input, $word);

 // 检查完全匹配
 if ($lev == 0) {

 // 最接近的单词是这个（完全匹配）
 $closest = $word;
 $shortest = 0;

 // 跳出循环；我们找到了完全匹配
 break;
 }

 // 如果此距离小于下一个找到的最短距离，或者尚未找到下一个最接近的单词
 if ($lev <= $shortest || $shortest < 0) {
 // 设置最接近的匹配和最短距离
 $closest = $word;
 $shortest = $lev;
 }
}

echo "输入单词：$input\n";
if ($shortest == 0) {
 echo "找到完全匹配：$closest\n";
} else {
 echo "您是不是要找：$closest?\n";
}

?>

以上示例的输出为

Input word: carrrot
Did you mean: carrot?

参见

soundex() - 计算字符串的 soundex 键
similar_text() - 计算两个字符串的相似度
metaphone() - 计算字符串的 metaphone 键

发现问题？

了解如何改进此页面 • 提交 Pull Request • 报告错误

＋添加注释

用户贡献的注释 27 条注释

顶

踩

luciole75w 在 no 点 spam 点 gmail 点 com ¶

11 年前

levenshtein 函数单独处理输入字符串的每个字节。因此，对于多字节编码（例如 UTF-8），它可能会给出误导性的结果。

以法语重音单词为例
- levenshtein('notre', 'votre') = 1
- levenshtein('notre', 'nôtre') = 2 (嗯？！)

您可以轻松找到 levenshtein 函数的多字节兼容 PHP 实现，但它当然比 C 实现慢得多。

另一种选择是将字符串转换为单字节（无损）编码，以便它们可以馈送到快速的核心 levenshtein 函数。

以下是我与存储 UTF-8 字符串的搜索引擎一起使用的转换函数，以及一个快速基准测试。希望它会有所帮助。

<?php
// 将一个 UTF-8 编码的字符串转换为适用于诸如 levenshtein 等函数的单字节字符串。
// 
// 该函数简单地使用（并更新）一个定制的动态编码
// （输入/输出映射参数），其中非 ASCII 字符被重新映射到
// [128-255] 的范围，按出现顺序排列。
//
// 因此，它在共享此编码的所有字符串中最多支持 128 个不同的多字节码点。
//
function utf8_to_extended_ascii($str, &$map)
{
 // 查找所有多字节字符（参见 UTF-8 编码规范）
 $matches = array();
 if (!preg_match_all('/[\xC0-\xF7][\x80-\xBF]+/', $str, $matches))
 return $str; // 纯 ASCII 字符串
 
 // 使用尚未遇到的字符更新编码映射
 foreach ($matches[0] as $mbc)
 if (!isset($map[$mbc]))
 $map[$mbc] = chr(128 + count($map));
 
 // 最后重新映射非 ASCII 字符
 return strtr($str, $map);
}

// 演示示例展示了前面转换函数的用法，但是，
// 为了获得更好的性能，在实际应用中，如果将单个输入字符串
// 与数据库中的许多字符串进行匹配，您可能需要
// 只对输入进行一次预编码。
//
function levenshtein_utf8($s1, $s2)
{
 $charMap = array();
 $s1 = utf8_to_extended_ascii($s1, $charMap);
 $s2 = utf8_to_extended_ascii($s2, $charMap);
 
 return levenshtein($s1, $s2);
}
?>

结果（大约 6000 次调用）
- 核心 C 函数的参考时间（单字节）：30 毫秒
- utf8 到 ext-ascii 转换 + 核心函数：90 毫秒
- 完整的 php 实现：3000 毫秒

顶

踩

paulrowe at iname dot com ¶

16 年前

[编者注：原始帖子和 2 个更正合并为 1 个 -- mgf]


这是一个仅使用一维数组且对字符串长度没有限制的 Levenshtein 距离计算的实现。 此实现受到也仅使用一维数组的迷宫生成算法的启发。


我用两个 532 个字符的字符串测试了这个函数，它在 0.6-0.8 秒内完成。


<?php 
/* 
* 此函数首先进行几次检查以尝试节省时间。
* 1. 较短的字符串始终用作“右手”字符串（因为数组的大小基于其长度）。
* 2. 如果左字符串为空，则返回右字符串的长度。
* 3. 如果右字符串为空，则返回左字符串的长度。
* 4. 如果字符串相等，则返回零距离。
* 5. 如果左字符串包含在右字符串中，则返回长度差。
* 6. 如果右字符串包含在左字符串中，则返回长度差。
* 如果不满足上述任何条件，则使用 Levenshtein 算法。
*/ 
function LevenshteinDistance($s1, $s2) 
{ 
 $sLeft = (strlen($s1) > strlen($s2)) ? $s1 : $s2; 
 $sRight = (strlen($s1) > strlen($s2)) ? $s2 : $s1; 
 $nLeftLength = strlen($sLeft); 
 $nRightLength = strlen($sRight); 
 if ($nLeftLength == 0) 
 return $nRightLength; 
 else if ($nRightLength == 0) 
 return $nLeftLength; 
 else if ($sLeft === $sRight) 
 return 0; 
 else if (($nLeftLength < $nRightLength) && (strpos($sRight, $sLeft) !== FALSE)) 
 return $nRightLength - $nLeftLength; 
 else if (($nRightLength < $nLeftLength) && (strpos($sLeft, $sRight) !== FALSE)) 
 return $nLeftLength - $nRightLength; 
 else { 
 $nsDistance = range(1, $nRightLength + 1); 
 for ($nLeftPos = 1; $nLeftPos <= $nLeftLength; ++$nLeftPos) 
 { 
 $cLeft = $sLeft[$nLeftPos - 1]; 
 $nDiagonal = $nLeftPos - 1; 
 $nsDistance[0] = $nLeftPos; 
 for ($nRightPos = 1; $nRightPos <= $nRightLength; ++$nRightPos) 
 { 
 $cRight = $sRight[$nRightPos - 1]; 
 $nCost = ($cRight == $cLeft) ? 0 : 1; 
 $nNewDiagonal = $nsDistance[$nRightPos]; 
 $nsDistance[$nRightPos] = 
 min($nsDistance[$nRightPos] + 1, 
 $nsDistance[$nRightPos - 1] + 1, 
 $nDiagonal + $nCost); 
 $nDiagonal = $nNewDiagonal; 
 } 
 } 
 return $nsDistance[$nRightLength]; 
 } 
} 
?>

顶

踩

Johan Gennesson php at genjo dot fr ¶

8 年前

请注意，

<?php
// Levenshtein 单引号 (U+0027 &#39;) 和右单引号 (U+2019 &#8217;)
echo levenshtein("'", "’");
?>

将输出 3！

顶

踩

engineglue at gmail dot com ¶

12 年前

我真的很喜欢[手册中]使用 levenshtein 函数与数组匹配的示例。 我遇到了指定结果灵敏度的需求。 在某些情况下，如果匹配超出范围，您希望它返回 false。 我不希望“marry had a little lamb”与“saw viii”匹配，仅仅因为它是数组中最好的匹配。 因此需要灵敏度。


<?php 
 function wordMatch($words, $input, $sensitivity){ 
 $shortest = -1; 
 foreach ($words as $word) { 
 $lev = levenshtein($input, $word); 
 if ($lev == 0) { 
 $closest = $word; 
 $shortest = 0; 
 break; 
 } 
 if ($lev <= $shortest || $shortest < 0) { 
 $closest = $word; 
 $shortest = $lev; 
 } 
 } 
 if($shortest <= $sensitivity){ 
 return $closest; 
 } else { 
 return 0; 
 } 
 } 
 
 $word = 'PINEEEEAPPLE'; 
 
 $words = array('apple','pineapple','banana','orange', 
 'radish','carrot','pea','bean','potato'); 
 
 echo wordMatch($words, strtolower($word), 2); 
?>

顶

踩

fgilles at free dot fr ¶

23 年前

论坛使用示例：用户不能发布太多大写字母的消息


<?php 
if ((strlen($subject)>10) and ( ( levenshtein ($subject, strtolower ($subject) / strlen ($subject) ) > .3 ) ){ 
 $subject = strtolower($subject); 
} 
?>

顶

踩

dale3h ¶

16 年前

结合 PHP 示例和 Patrick 的比较百分比函数，我创建了一个函数，该函数返回数组中最接近的单词，并将百分比分配给引用的变量

<?php
 function closest_word($input, $words, &$percent = null) {
 $shortest = -1;
 foreach ($words as $word) {
 $lev = levenshtein($input, $word);

 if ($lev == 0) {
 $closest = $word;
 $shortest = 0;
 break;
 }

 if ($lev <= $shortest || $shortest < 0) {
 $closest = $word;
 $shortest = $lev;
 }
 }

 $percent = 1 - levenshtein($input, $closest) / max(strlen($input), strlen($closest));

 return $closest;
 }
?>

用法
<?php
 $input = 'carrrot';
 $words = array('apple','pineapple','banana','orange',
 'radish','carrot','pea','bean','potato');

 $percent = null;
 $found = closest_word($input, $words, $percent);

 printf('与 "%s" 最接近的单词：%s (%s%% 匹配)', $input, $found, round($percent * 100, 2));
?>

我发现，如果大小写不重要，在比较之前将数组转换为小写会产生更好的比较结果，例如：将用户输入的类别与现有类别列表进行比较。

我还发现，当百分比高于 75% 时，通常是我要找的匹配项。

顶

踩

june05 at tilo-hauke dot de ¶

19 年前

//数组的 levenshtein
function array_levenshtein($array1,$array2)
{ $aliases= array_flip(array_values(array_unique(array_merge($array1,$array2))));
if(count($aliases)>255) return -1;
$stringA=''; $stringB='';
foreach($array1 as $entry) $stringA.=chr($aliases[$entry]);
foreach($array2 as $entry) $stringB.=chr($aliases[$entry]);
return levenshtein($stringA,$stringB);
         }
         
// 例如，使用 array_levenshtein 检测用户输入中的特殊表达式

echo array_levenshtein(split(" ", "my name is xxx"), split(" ","my name is levenshtein"));

//输出: 1

顶

踩

yhoko at yhoko dot com ¶

8 年前

请注意，此函数在处理多字节字符（如 UTF-8 中的字符）时可能会导致问题。例如

<?php
print( similar_text( 'hä', 'hà' ) ); // 返回 2，其中只有 1 个字符匹配
?>

顶

踩

dschultz at protonic dot com ¶

24 年前

如果您想创建一个注册页面，并希望确保注册者选择的用户名与其密码不太相似，这也很有用。

顶

踩

carey at NOSPAM dot internode dot net dot au ¶

18 年前

我发现 levenshtein 实际上是区分大小写的（至少在 PHP 4.4.2 中是这样）。

<?php
$distance=levenshtein('hello','ELLO');
echo "$distance";
?>

输出："5"，而不是 "1"。如果您正在实现使用 levenshtein 的模糊搜索功能，您可能需要找到一种方法来解决这个问题。

顶

踩

"inerte" is my hotmail.com username ¶

21 年前

我正在使用此函数来避免客户数据库中的重复信息。

检索一系列行并将结果分配给数组值后，我使用 foreach 循环比较其 levenshtein() 与用户提供的字符串。

它有助于避免人们重复注册 "John Smith"、"Jon Smith" 或 "Jon Smit"。

当然，如果用户确实想这样做，我无法阻止该操作，但会显示一条建议，例如：“有一个同名客户”，后跟相似字符串的列表。

顶

踩

justin at visunet dot ie ¶

19 年前

<?php

 /*********************************************************************
 * 以下函数 btlfsa（优于莱文斯坦距离的拼写应用算法）
 * 在比较诸如 haert 与 haart 和 heart 之类的单词时
 * 产生更好的结果。
 *
 * 例如，以下是将 'haert' 与 'herat、haart、heart、harte'
 * 进行比较时，莱文斯坦距离与 btlfsa 的输出结果对比：
 *
 * btlfsa('haert','herat'); 输出为.. 3
 * btlfsa('haert','haart'); 输出为.. 3
 * btlfsa('haert','harte'); 输出为.. 3
 * btlfsa('haert','heart'); 输出为.. 2
 *
 * levenshtein('haert','herat'); 输出为.. 2
 * levenshtein('haert','haart'); 输出为.. 1
 * levenshtein('haert','harte'); 输出为.. 2
 * levenshtein('haert','heart'); 输出为.. 2
 *
 * 换句话说，如果您使用莱文斯坦距离，'haart' 将是与 'haert'
 * 最接近的匹配项。然而，btlfsa 认为应该是 'heart'
 */

 function btlfsa($word1,$word2)
 {
 $score = 0;

 // 对于每个不同的字符，将分数加 2
 // 因为这是一个很大的差异

 $remainder = preg_replace("/[".preg_replace("/[^A-Za-z0-9\']/",' ',$word1)."]/i",'',$word2);
 $remainder .= preg_replace("/[".preg_replace("/[^A-Za-z0-9\']/",' ',$word2)."]/i",'',$word1);
 $score = strlen($remainder)*2;

 // 计算字符串长度的差值并将其添加到分数中
 $w1_len = strlen($word1);
 $w2_len = strlen($word2);
 $score += $w1_len > $w2_len ? $w1_len - $w2_len : $w2_len - $w1_len;

 // 计算有多少个字母位于不同的位置
 // 并将其添加到分数中，例如：
 //
 // h e a r t
 // 1 2 3 4 5
 //
 // h a e r t a e = 2
 // 1 2 3 4 5 1 2 3 4 5
 //

 $w1 = $w1_len > $w2_len ? $word1 : $word2;
 $w2 = $w1_len > $w2_len ? $word2 : $word1;

 for($i=0; $i < strlen($w1); $i++)
 {
 if ( !isset($w2[$i]) || $w1[$i] != $w2[$i] )
 {
 $score++;
 }
 }

 return $score;
 }

 // *************************************************************
 // 以下是一个完整的代码示例，展示了两者之间的区别

 $misspelled = 'haert';

 // 假设这些是由 soundex 或 metaphone 返回的样本建议..
 $suggestions = array('herat', 'haart', 'heart', 'harte');

 // 首先根据莱文斯坦距离对数组进行排序
 $levenshtein_ordered = array();
 foreach ( $suggestions as $suggestion )
 {
 $levenshtein_ordered[$suggestion] = levenshtein($misspelled,$suggestion);
 }
 asort($levenshtein_ordered, SORT_NUMERIC );

 print "<b>根据莱文斯坦距离排序的建议...</b><ul><pre>";
 print_r($levenshtein_ordered);
 print "</pre></ul>";

 // 其次根据 btlfsa 对数组进行排序
 $btlfsa_ordered = array();
 foreach ( $suggestions as $suggestion )
 {
 $btlfsa_ordered[$suggestion] = btlfsa($misspelled,$suggestion);
 }
 asort($btlfsa_ordered, SORT_NUMERIC );

 print "<b>根据 btlfsa 排序的建议...</b><ul><pre>";
 print_r($btlfsa_ordered);
 print "</pre></ul>";

?>

顶

踩

atx dot antrax at gmail dot com ¶

16 年前

我创建了一个函数，该函数消除了莱文斯坦距离函数的长度限制，并使用 similar_text 调整结果

<?php
function _similar($str1, $str2) {
 $strlen1=strlen($str1);
 $strlen2=strlen($str2);
 $max=max($strlen1, $strlen2);

 $splitSize=250;
 if($max>$splitSize)
 {
 $lev=0;
 for($cont=0;$cont<$max;$cont+=$splitSize)
 {
 if($strlen1<=$cont || $strlen2<=$cont)
 {
 $lev=$lev/($max/min($strlen1,$strlen2));
 break;
 }
 $lev+=levenshtein(substr($str1,$cont,$splitSize), substr($str2,$cont,$splitSize));
 }
 }
 else
 $lev=levenshtein($str1, $str2);

 $porcentage= -100*$lev/$max+100;
 if($porcentage>75)// 使用 similar_text 进行调整
 similar_text($str1,$str2,$porcentage);

 return $porcentage;
}
?>

顶

踩

WiLDRAGoN ¶

9 年前

一些小的改动允许您计算多个单词。

<?php

$input = array();
$dictionary = array();
foreach ($input as $output) {
 $shortest = -1;
 foreach ($dictionary as $word) {
 $lev = levenshtein($output, $word);
 if ($lev == 0) {
 $closest = $word;
 $shortest = 0;
 }
 if ($lev <= $shortest || $shortest < 0) {
 $closest = $word;
 $shortest = $lev;
 }
 }
 echo "输入单词: $output\n";
 if ($shortest == 0) {
 echo "找到完全匹配: $closest\n";
 } else {
 echo "您是不是想输入: $closest?\n";
 }
}

?>

顶

踩

Chaim Chaikin ¶

13 年前

关于上面的示例 #1，如果在调用 levenshtein() 函数之前先使用简单的 php == 比较来检查字符串是否相等，岂不是更有效率？

类似这样：

<?php
// 输入拼写错误的单词
$input = 'carrrot';

// 要检查的单词数组
$words = array('apple','pineapple','banana','orange',
 'radish','carrot','pea','bean','potato');

// 尚未找到最短距离
$shortest = -1;

// 循环遍历单词以找到最接近的单词
foreach ($words as $word) {

 // 检查是否完全匹配
 if ($input == $word) {

 // 最接近的单词就是这个（完全匹配）
 $closest = $word;
 $shortest = 0;

 // 跳出循环；我们已经找到了完全匹配的单词
 break;
 }

 // 计算输入单词与当前单词之间的距离
 $lev = levenshtein($input, $word);

 // 如果此距离小于下一个找到的最短距离，或者尚未找到下一个最短单词
 if ($lev <= $shortest || $shortest < 0) {
 // 设置最接近的匹配和最短距离
 $closest = $word;
 $shortest = $lev;
 }
}

echo "输入单词：$input\n";
if ($shortest == 0) {
 echo "找到完全匹配：$closest\n";
} else {
 echo "您是不是想找：$closest?\n";
}

?>

顶

踩

mcreuzer at r-world dot com ¶

19 年前

我正在使用 Levenshtein 距离对我的搜索结果进行**排序**。

我有一个搜索人名的页面。我在 mysql 中对名称执行 SOUNDEX() 搜索。MySQL SOUNDEX() 将为我执行“模糊”搜索。

然后，我计算搜索词与 SOUNDEX() 搜索找到的实际名称之间的 Levenshtein 距离。这将为我提供一个分数，说明我的结果与搜索字符串的接近程度。

然后我可以对我的结果进行排序以进行显示，首先列出最接近的结果。

<?php
// 此处包含数据库查找的 PHP 代码
 usort($searchresults, "finallevenshteinsortfunction");

function finallevenshteinsortfunction($a, $b)
{
 if(($a['levenshtein'] > $b['levenshtein']) || ( $a['levenshtein'] == $b['levenshtein'] && strnatcasecmp( $a['Last_Name'], $b['Last_Name']) >= 1) ){ return $a['levenshtein'];} // 好的... Levenshtein 距离更大，或者具有相同的 Levenshtein 距离，姓氏按字母顺序排在第一位
 elseif($a['levenshtein'] == $b['levenshtein']){ return '0';} // Levenshtein 距离匹配 
 elseif($a['levenshtein'] < $b['levenshtein']){ return -$a['levenshtein'];}
 else{die("<!-- 可怕的死亡 -->");}
}
?>

顶

踩

gzink at zinkconsulting dot com ¶

21 年前

尝试将其与 metaphone() 结合使用，以获得真正令人惊叹的模糊搜索功能。稍微尝试一下，正确实施后，结果可能会非常可怕（用户会认为计算机几乎具有心灵感应）。我希望拼写检查器能像我编写的代码一样好用。


如果合理的话，我会发布我的完整代码，但由于版权问题，我不能这样做。我只希望有人能从这个小技巧中学到一些东西！

顶

踩

bisqwit at iki dot fi ¶

22 年前

在本手册说明发布时，用户定义的
levenshtein() 中的内容尚未实现。我想要类似的东西，
所以我写了我自己的函数。请注意，这不会返回
levenshtein() 差异，而是返回
将一个字符串转换为另一个字符串的操作数组。

请注意，差异查找部分 (resync)
在长字符串上可能非常慢。

<?php

/* matchlen(): 返回 $a 和 $b 开头匹配的子字符串的长度
 */
function matchlen(&$a, &$b)
{
 $c=0;
 $alen = strlen($a);
 $blen = strlen($b);
 $d = min($alen, $blen);
 while($a[$c] == $b[$c] && $c < $d)
 $c++; 
 return $c;
}

/* 返回描述 $a 和 $b 之间差异的表 */
function calcdiffer($a, $b)
{
 $alen = strlen($a);
 $blen = strlen($b);
 $aptr = 0;
 $bptr = 0;
 
 $ops = array();
 
 while($aptr < $alen && $bptr < $blen)
 {
 $matchlen = matchlen(substr($a, $aptr), substr($b, $bptr));
 if($matchlen)
 {
 $ops[] = array('=', substr($a, $aptr, $matchlen));
 $aptr += $matchlen;
 $bptr += $matchlen;
 continue;
 }
 /* 发现差异 */
 
 $bestlen=0;
 $bestpos=array(0,0); 
 for($atmp = $aptr; $atmp < $alen; $atmp++)
 {
 for($btmp = $bptr; $btmp < $blen; $btmp++)
 {
 $matchlen = matchlen(substr($a, $atmp), substr($b, $btmp));
 if($matchlen>$bestlen)
 {
 $bestlen=$matchlen; 
 $bestpos=array($atmp,$btmp);
 }
 if($matchlen >= $blen-$btmp)break;
 }
 }
 if(!$bestlen)break;
 
 $adifflen = $bestpos[0] - $aptr;
 $bdifflen = $bestpos[1] - $bptr;

 if($adifflen)
 {
 $ops[] = array('-', substr($a, $aptr, $adifflen));
 $aptr += $adifflen;
 }
 if($bdifflen)
 {
 $ops[] = array('+', substr($b, $bptr, $bdifflen));
 $bptr += $bdifflen;
 }
 $ops[] = array('=', substr($a, $aptr, $bestlen));
 $aptr += $bestlen;
 $bptr += $bestlen;
 }
 if($aptr < $alen)
 {
 /* b 中有多余的内容 */
 $ops[] = array('-', substr($a, $aptr));
 }
 if($bptr < $blen)
 {
 /* a 中缺少内容 */
 $ops[] = array('+', substr($b, $bptr));
 }
 return $ops;
}
 

示例:

$tab = calcdiffer('T?m? on jonkinlainen testi',
 'T?m? ei ole mink??nlainen testi.'); 
$ops = array('='=>'Ok', '-'=>'删除', '+'=>'添加');
foreach($tab as $k)
 echo $ops[$k[0]], " '", $k[1], "'\n";

示例输出:

Ok 'T?m? '
删除 'on jonki'
添加 'ei ole mink??'
Ok 'nlainen testi'
添加 '.'

顶

踩

hartmut at php dot net ¶

4 个月前

此函数操作的是字节，而不是字符，因此在操作 UTF-8 编码的 Unicode 字符串时，它的作用有限。

通过 Normalizer 运行输入字符串 ( https://php.net/manual/en/class.normalizer.php ) 至少可以在某种程度上解决这个问题，但您仍然需要注意，替换、插入或删除单个 UTF-8 编码的 unicode 字符可能会错误地报告 2、3 或 4 的成本，具体取决于表示它的 UTF-8 序列的长度，或者在处理组合字符修饰符时甚至更多。

顶

踩

peratik at gmail dot com ¶

7 年前

python get_close_matches 等效函数

function get_close_matches($str, $arr) {
$closest = 1000;
$word = false;
foreach($arr as $w) {
$po = levenshtein($str, $w);
if ($po<$closest) {
$closest = $po;
$word = $w;
        }
    }
return $word;
}

顶

踩

qbolec ¶

9 年前

对于极少数情况下，您需要
1. 多字节 UTF-8 字符
2. 线性内存消耗 (即 O(n+m) , 而不是 O(n*m))
3. 找出最长公共子序列的字符串
4. 合理的 (即 O(n*m)) 时间复杂度
考虑这个实现
<?php
class Strings
{
 public static function len($a){
 return mb_strlen($a,'UTF-8');
 }
 public static function substr($a,$x,$y=null){
 if($y===NULL){
 $y=self::len($a);
 }
 return mb_substr($a,$x,$y,'UTF-8');
 }
 public static function letters($a){
 $len = self::len($a);
 if($len==0){
 return array();
 }else if($len == 1){
 return array($a);
 }else{
 return Arrays::concat(
 self::letters(self::substr($a,0,$len>>1)),
 self::letters(self::substr($a,$len>>1))
 );
 }
 }
 private static function lcs_last_column(array $A,array $B){
 $al=count($A);
 $bl=count($B);
 $last_column = array();
 for($i=0;$i<=$al;++$i){
 $current_row = array();
 for($j=0;$j<=$bl;++$j){
 //$a[0,$i) vs $b[0,$j)
 if($i==0 || $j == 0){
 $v = 0;
 }else if($A[$i-1]===$B[$j-1]){
 $v = 1 + $last_row[$j-1];
 }else{
 $v = max($last_row[$j],$current_row[$j-1]);
 }
 $current_row[] = $v;
 }
 $last_column[] = $current_row[$bl];
 $last_row = $current_row;
 }
 return $last_column;
 }
 public static function lcs($a,$b){
 $A = self::letters($a);
 $B = self::letters($b);
 $bl=count($B);
 if($bl==0){
 return '';
 }else if($bl==1){
 return FALSE===array_search($B[0],$A,true)?'':$B[0];
 }
 $left=self::lcs_last_column($A,array_slice($B,0,$bl>>1));
 $right=array_reverse(self::lcs_last_column(array_reverse($A),array_reverse(array_slice($B,$bl>>1))));

 $best_i = 0;
 $best_lcs = 0;
 foreach($left as $i => $lcs_left){
 $option = $lcs_left + $right[$i];
 if($best_lcs < $option){
 $best_lcs = $option;
 $best_i = $i;
 }
 }
 return 
 self::lcs(self::substr($a,0,$best_i), self::substr($b,0,$bl>>1)).
 self::lcs(self::substr($a,$best_i), self::substr($b,$bl>>1));
 }
?>
这是一个经典的实现，其中使用了几个技巧
1. 字符串在 O(n lg n) 时间内被分解成多字节字符
2. 我们没有在预先计算的二维数组中搜索最长路径，而是在中间列中搜索最佳点。这是通过将第二个字符串分成两半，并递归调用该算法两次来实现的。我们唯一需要从递归调用中得到的是中间列中的值。诀窍是从每次递归调用返回最后一列，这是我们左半部分所需要的，但对于右半部分需要再用一个技巧 - 我们只需镜像字符串和数组，使最后一列成为第一列。然后我们只需找到使每部分长度之和最大化的行。
3. 可以证明，该算法消耗的时间与（假想的）二维数组的面积成正比，因此它是 O(n*m)。

顶

踩

luka8088 at gmail dot com ¶

16 年前

简单的莱文斯坦距离函数，没有字符串长度限制...

<?php

function levenshtein2($str1, $str2, $cost_ins = null, $cost_rep = null, $cost_del = null) {
 $d = array_fill(0, strlen($str1) + 1, array_fill(0, strlen($str2) + 1, 0));
 $ret = 0;
 
 for ($i = 1; $i < strlen($str1) + 1; $i++)
 $d[$i][0] = $i;
 for ($j = 1; $j < strlen($str2) + 1; $j++)
 $d[0][$j] = $j;
 
 for ($i = 1; $i < strlen($str1) + 1; $i++)
 for ($j = 1; $j < strlen($str2) + 1; $j++) {
 $c = 1;
 if ($str1{$i - 1} == $str2{$j - 1})
 $c = 0;
 $d[$i][$j] = min($d[$i - 1][$j] + 1, $d[$i][$j - 1] + 1, $d[$i - 1][$j - 1] + $c);
 $ret = $d[$i][$j];
 }
 
 return $ret;
}

?>

顶

踩

genialbrainmachine 在 IHATESPAM 点 tiscali 点 it ¶

21 年前

我写了这个函数，用于对要写入数据库的数据和已存在的数据进行“智能”比较。
它不仅计算距离，还对每个字段的距离进行加权平衡。
每个字段。
<?php
/*
此函数计算字符串数组“$record”与比较数组“$compared”之间的加权百分比距离，
并通过权重数组“$weight”进行平衡。这三个数组必须具有相同的索引。
对于非加权距离，请将所有权重设置为1。
使用的公式为：
百分比距离 = sum(field_levenshtein_distance * field_weight) / sum(record_field_length * field_weight) * 100
*/
function search_similar($record, $weights, $compared, $precision=2) {
 $field_names = array_keys($record);
 # “$record”的“加权长度”和“加权距离”。
 foreach ($field_names as $field_key) {
 $record_weight += strlen($record[$field_key]) * $weights[$field_key];
 $weighted_distance += levenshtein($record[$field_key],$compared[$field_key]) * $weights[$field_key];
 }
 # 构建结果..
 if ($record_weight) {
 return round(($weighted_distance / $record_weight * 100),$precision);
 } elseif ((strlen(implode("",$record)) == 0) && (strlen(implode("",$compared)) == 0)) { // 空记录
 return round(0,$precision);
 } elseif (array_sum($weights) == 0) { // 所有权重为0
 return round(0,$precision);
 } else {
 return false;
 }
 /*
 请务必区分结果0和结果false。
 在以下情况下，函数返回0（如果$precision为2，则返回'0.00'，依此类推）：
 - $record和$compared相等（即使$record和$compared为空）；
 - 所有权重均为0（含义可能是“不关心任何字段”）。
 相反，如果$record为空，但权重不全为0且$compared不为空，则函数返回false。这会导致“除以0”错误。
 我写了这种检查：
 
 if ($rel_dist = search_similar(...)) {
 print $rel_dist;
 } elseif ($rel_dist == "0.00") { // 假设$precision为2
 print $rel_dist;
 } else {
 print "无限大";
 }
 
 */
 }
?>

顶

踩

dinesh 在 dinsoft 点 net ¶

18 年前

这是一个字符串重新同步函数

<?php
// 查找将 $b 更改为 $a 所需的操作，方法是利用它们的相似性（查找将 $b 更改为 $a 所需的操作）
// 与 Hex Workshop 的 Resynch Compare 函数相同
//
// 参数：
// $a 第一个字符串（目标）
// $b 第二个字符串（源）
// $l 要被视为相似块而需要匹配的字节数
// $s 搜索相似块的最大距离（搜索窗口）
//
// 返回：
// 数组
// 数组
// [0] 操作：+ 添加，- 删除，/ 替换，= 匹配
// [1] 源偏移量
// [2] 源计数
// [3] 目标偏移量
// [4] 目标计数
//
function str_resynch($a,$b,$l=32,$s=2048) {
 $r=array();
 for($i=0,$c=strlen($a),$cc=strlen($b),$ii=0,$z=$s-1,$z2=($z<<1)+1; $i<$c; $i++) {
 $d=$i-$z;
 $d=($d<$ii)?substr($b,$ii,$z2-$ii+$d):substr($b,$d,$z2);

 $p=strpos($d,$a{$i});
 $n=0;
 while ($p!==FALSE) {
 $m=1;
 $bi=$i;
 $bp=$p;
 $p+=$ii;
 while ((++$i<$c) && (++$p<$cc)) {
 if ($a{$i}!=$b{$p}) break;
 $m++;
 }
 if ($m<$l) {
 $i=$bi;
 $n=$bp+1;
 $p=@strpos($d,$a{$i},$n);
 }
 else {
 $i--;
 $r[]=array($bi,$bp+$ii,$m); // 偏移量 a，偏移量 b，计数
 $ii=$p;
 break;
 }
 }
 }

 if (!count($r)) return ($cc)?array('/',0,$c,0,$cc):array(array('+',0,$c,0,0));

 $o=array();
 $bi=0;
 $bp=0;
 for($i=0,$m=count($r);$i<$m;$i++) {
 if ($r[$i][0]!=$bi) {
 if ($r[$i][1]!=$bp) {
 // 替换
 $o[]=array('/',$bi,$r[$i][0]-$bi,$bp,$r[$i][1]-$bp);
 $bi=$r[$i][0];
 $bp=$r[$i][1];
 }
 else {
 // 插入
 $o[]=array('+',$bi,$r[$i][0]-$bi,$bp,0);
 $bi=$r[$i][0];
 }
 }
 elseif ($r[$i][1]!=$bp) {
 // 删除
 $o[]=array('-',$bi,0,$bp,$r[$i][1]-$bp);
 $bp=$r[$i][1];
 }

 // 匹配
 $o[]=array('=',$r[$i][0],$r[$i][2],$r[$i][1],$r[$i][2]);
 $bi+=$r[$i][2];
 $bp+=$r[$i][2];
 }

 if ($c!=$bi) {
 if ($cc!=$bp) $o[]=array('/',$bi,$c-$bi,$bp,$cc-$bp);
 else $o[]=array('+',$bi,$c-$bi,$bp,0);
 }
 elseif ($cc!=$bp) $o[]=array('-',$bi,0,$bp,$cc-$bp);

 return $o;
}
?>

顶

踩

匿名 ¶

22 年前

对于拼写检查应用程序，如果您假设打字员每个单词的前两个或三个字符都正确，那么延迟可能是可以容忍的。然后，您只需要计算字典中一小部分的距离。这是一种妥协，但我认为很多拼写检查程序都会这样做。
有关使用此功能的网站搜索示例，请查看此页面上的 PHP 手册搜索按钮。它似乎正在对 PHP 函数列表执行此操作。

顶

踩

ad1n 在 dc 点 uba 点 ar ¶

24 年前

其中一个应用是当您想要查找相似匹配而不是完全匹配时。您可以对单词与字典的距离检查结果进行排序，并对它们进行排序以查看哪些更相似。当然，无论如何这都将是一项非常耗费资源的任务。

顶

踩

-1

jlsalinas 在 gmx 点 net ¶

21 年前

关于 fgilles 在 2001 年 4 月 26 日发表的文章，我建议不要使用 levenshtein() 函数来测试过度大写，除非您有足够的时间在主机中浪费。;) 无论如何，我认为这是一个有用的功能，因为当我在大写字母中阅读整个消息时，我真的很生气。

PHP 的 levenshtein() 函数只能处理最多 255 个字符，这对用户输入来说是不现实的（仅这篇文章的第一段就有 285 个字符）。如果您选择使用能够处理超过 255 个字符的自定义函数，效率是一个重要问题。

我使用这个函数，针对这种情况，但速度快得多。

function ucase_percent ($str) {
$str2 = strtolower ($str);
    
$l = strlen ($str);
$ucase = 0;

for ($i = 0; $i < $l; $i++) {
if ($str{$i} != $str2{$i}) {
$ucase++;
        }
    }
    
return $ucase / $l * 100.0;
}

我认为 10% 对于书面英语来说已经足够了（也许其他语言，如德语，使用更多的大写字母，需要更多）。对于一些大写的句子（每个人都有偶尔大声说话的权利），20% 就足够了；所以我使用 30% 的阈值。当超过这个阈值时，我会将整个消息转换为小写。

希望您觉得它有用，并且它有助于保持网络上没有不文明的人。

＋添加注释