levenshtein()

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

计算两个字符串之间的编辑距离

说明

编辑距离，是指两个字串之间，通过替换、插入、删除等操作将字符串$str1转换成$str2所需要操作的最少字符数量。该算法的复杂度是O(m*n)，其中n和m分别是$str1 和$str2的长度（当和算法复杂度为O(max(n,m)**3)的similar_text()相比时，此函数还是相当不错的，尽管仍然很耗时。）。

在最简单的形式中，该函数只以两个字符串作为参数，并计算通过插入、替换和删除等操作将$str1转换成$str2所需要的操作次数。

第二种变体将采用三个额外的参数来定义插入、替换和删除操作的次数。此变体比第一种更加通用和适应，但效率不高。

参数

求编辑距离中的其中一个字符串

求编辑距离中的另一个字符串

定义插入次数

定义替换次数

定义删除次数

返回值

此函数返回两个字符串参数之间的编辑距离，如果其中一个字符串参数长度大于限制的255个字符时，返回-1。

范例

levenshtein()例子：

以上例程会输出：

Input word: carrrot
Did you mean: carrot?

参见

• soundex()Calculate the soundex key of a string
• similar_text()计算两个字符串的相似度
• metaphone()Calculate the metaphone key of a string

The levenshtein function processes each byte of the input string individually. Then for multibyte encodings, such as UTF-8, it may give misleading results.
Example with a french accented word :
- levenshtein('notre', 'votre') = 1
- levenshtein('notre', 'nôtre') = 2 (huh ?!)
You can easily find a multibyte compliant PHP implementation of the levenshtein function but it will be of course much slower than the C implementation.
Another option is to convert the strings to a single-byte (lossless) encoding so that they can feed the fast core levenshtein function.
Here is the conversion function I used with a search engine storing UTF-8 strings, and a quick benchmark. I hope it will help.

Results (for about 6000 calls)
- reference time core C function (single-byte) : 30 ms
- utf8 to ext-ascii conversion + core function : 90 ms
- full php implementation : 3000 ms

Please, be aware that:

This is a classic implentation in which several tricks are used:
1. the strings are exploded into multi-byte characters in O(n lg n) time
2. instead of searching for the longest path in a precomputed two-dimensional array, we search for the best point which lays in the middle column. This is achieved by spliting the second string in half, and recursively calling the algorithm twice. The only thing we need from the recursive call are the values in the middle column. The trick is to return the last column from each recursive call, which is what we need for the left part, but requires one more trick for the right part - we simply mirror the strings and the array so that the last column is the first column. Then we just find the row which maximizes the sum of lenghts in each part.
3. one can prove that the time consumed by the algorithm is proportional to the area of the (imaginary) two-dimensional array, thus it is O(n*m).

Simple levenshtein function without string length limit ...

I have made a function that removes the length-limit of levenshtein function and ajust the result with similar_text:

Here is a string resynch function:

鹏仔微信 15129739599 鹏仔QQ344225443 鹏仔前端 pjxi.com 共享博客 sharedbk.com