43、PHP 原生魅力 - 字符串 - 计算两个字符串之间的距离
计算两个字符串之间的距离： levenshtein()
Levenshtein 距离是计算两个文本字符串之间的差异或相似性的度量。它以苏联数学家弗拉基米尔·莱文施泰因的名字命名，他提出了这个概念。此距离表示将一个字符串转换为第二个字符串所需的最小操作数。允许的操作是插入单个字符、删除单个字符或将一个字符替换为另一个字符。
例如，考虑单词 “halo” 和 “hallo”。要把 “halo” 变成 “hallo”，必须加上 “l”。因此，这两个单词之间的 Levenshtein 距离是 1。
这种测量方法用于各种应用，例如拼写校正，搜索 DNA 序列之间的相似性，比较文件以检测差异等等。Levenshtein 距离是一个有用的工具，可以根据将一个字符串转换为另一个字符串所需的最小操作来评估两个字符串的相似或不同程度。
| 第一文本字符串 | 第二个文本字符串 | Levenshtein 距离 | 操作 |
|---|---|---|---|
| hello | hallo | 1 | 用字母 “a” 代替 “e” |
| hello | halo | 2 | 用字母 “a” 代替 “e”，并删除字母 “l” |
| table | tablet | 1 | 在末尾加上字母 t |
| kitten | sitting | 3 | 把 “k ”字母换成 “s” 字母，把 “e” 字母换成 “i” 字母，最后加上 “g”。 |
PHP语言为我们提供了 levenshtein() 函数。
<?php
echo levenshtein("hello", "hallo") . PHP_EOL;
echo levenshtein("hello", "halo") . PHP_EOL;
echo levenshtein("table", "tablet") . PHP_EOL;
echo levenshtein("kitten", "sitting") . PHP_EOL;
输出如下：
$ php 43-levenshtein.php
1
2
1
3
业务费用
使用 levenshtein() 功能，你可以设置每个操作的成本。插入、替换和删除操作的成本为1。这意味着所有的操作都有相同的成本。成本用于计算数量。您可以设置 $insertion_cost 、 $replacement_cost 和 $deletion_cost 。
将成本分配给业务的能力可能导致这样的情况，即通过一系列不一定代表最低数量的业务可以实现较低的总成本。举例来说：
<?php
levenshtein("hello", "halo", replacement_cost: 4)
// 3
最小总成本通过以下操作计算：
- 删除 e（成本 1）
- 添加 a（成本 1）
- 删除 l（成本 1），所以总成本是 3
这 3 个操作的成本低于 2 个操作（成本较高，因为重置成本设置为 4）：
- 将 e 替换为 a（成本 4）
- 删除l（成本 1）所以总成本是 5
Levenshtein 距离的实际应用
我在实现一个命令行工具时使用了 levenshtein() 函数来定位拼写错误的选项/参数，并尝试建议最相似的有效选项。一般来说，当你有一个值列表并希望识别与给定输入最相似的值时，它可能很有用。与有效路径列表相比，纠正拼写错误的路径也是一个很好的例子。
此外，它在结构可以追溯并编码为字符序列的情况下证明是有价值的，类似于简化的 DNA 比较。另一个应用是使用字母编码游戏的步骤序列，允许您识别最相似的序列。
总而言之，Levenshtein 距离是一个实用的工具，有助于理解和测量单词的相似性或不同性，使其在各种 PHP 应用程序中非常有用。