Levenshtein distance

Levenshtein distance 又被稱為 edit distance，是最常被用來檢查英文單字有拼字錯誤時，那一個字最接近的 algorithm。

可以用來檢查兩個單字之間的 distance，所謂的 distance 是 string A 經過多少個 insert, delete, replace 可以變成 string B。distance  越小就相似度越高。 complexity of the algorithm is O(m*n)。

PHP 有支援  Levenshtein distance

 int levenshtein ( string $str1 , string $str2 [, int $cost_ins ], int $cost_rep , int $cost_del )