cht電腦資訊LanguagePHP
adm Find login register

Levenshtein distance

eliu

joined: 2007-08-09
posted: 11474
promoted: 617
bookmarked: 187
新竹, 台灣
1subject: Levenshtein distancePromote 0 Bookmark 02007-12-18quote  

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 )

edited: 3

cht電腦資訊LanguagePHP
adm Find login register
views:5805