PHPの類似度計算機能について：levenshtein_PHPの使い方入門チュートリアル-PHPチュートリアル-php.cn

PHPの類似度計算機能について：levenshtein_PHPの使い方入門チュートリアル

WBOY

リリース： 2016-07-21 15:11:45

オリジナル

1196 人が閲覧しました

使用説明
まずマニュアルの levenshtein() 関数の説明をお読みください:

levenshtein() 関数は、2 つの文字列間のレーベンシュタイン距離を返します。

編集距離とも呼ばれるレーベンシュタイン距離は、2 つの文字列を一方の文字列からもう一方の文字列に変換するために必要な編集操作の最小数を指します。許可される編集操作には、ある文字を別の文字に置き換える、文字を挿入する、文字を削除するなどがあります。

たとえば、子猫を座っている状態に変換します:

sitten (k→s)
sittin (e→i)
sitting (→g) levenshtein() 関数は、各操作 (置換、挿入、削除) に等しい重みを与えます。ただし、オプションの挿入、置換、および削除パラメータを設定することで、各操作のコストを定義できます。

文法:

レーベンシュタイン(文字列1,文字列2,挿入,置換,削除)

パラメータの説明

string1 は必須です。比較する最初の文字列。
string2 が必要です。比較する 2 番目の文字列。
オプションを挿入します。キャラクターを挿入するコスト。デフォルトは 1 です。
オプションで交換します。キャラクターを置き換えるのにかかるコスト。デフォルトは 1 です。
削除はオプションです。キャラクターを削除するコスト。デフォルトは 1 です。
ヒントとメモ

文字列の 1 つが 255 文字を超える場合、levenshtein() 関数は -1 を返します。
levenshtein() 関数は大文字と小文字を区別しません。
levenshtein() 関数は、similar_text() 関数よりも高速です。ただし、similar_text() 関数を使用すると、修正が少なくて済み、より正確な結果が得られます。
例

コードをコピーコードは次のとおりです:

echo levenshtein("Hello World","ello World");
echo "
" ;
echo levenshtein("Hello World","ello World",10,20,30);
?>

出力: 1 30

ソースコード分析
levenshtein() は標準関数であり、/ext/standard/ ディレクトリにこの関数用に特別に実装されたファイル levenshtein.c があります。

levenshtein() はパラメータの数に基づいて実装方法を選択します。パラメータが 2 の場合とパラメータが 5 の場合は、reference_levdist() 関数が呼び出されて距離が計算されます。違いは、最後の 3 つのパラメーターでは、パラメーターが 2 の場合、デフォルト値 1 が使用されることです。

そして、実装ソースコードでは、ドキュメントで説明されていない状況が見つかりました。levenshtein() 関数は 3 つのパラメーターも渡すことができ、最終的にはcustom_levdist() 関数を呼び出します。カスタム関数の実装として 3 番目のパラメーターを受け取り、その呼び出し例は次のとおりです:

コードをコピーしますコードは次のとおりです:

echo levenshtein("Hello World", "ello World ", 'strsub');

エグゼクティブレポートの警告: 一般的なレーベンシュタインのサポートはまだありません。なぜなら、この方法はまだ実装されておらず、単なる落とし穴だからです。

reference_levdist() 関数の実装アルゴリズムは、古典的な DP 問題です。

2 つの文字列 x と y が与えられた場合、x を y に変更するための最小の変更数を見つけます。変更されたルールは、削除、挿入、または変更の 3 つのタイプのいずれかのみになります。
a[i][j] を使用して、x の最初の i 文字を y の最初の j 文字に変更するために必要な操作の最小数を表します。その場合、状態遷移方程式は次のようになります。

コードをコピーしますコードは次のとおりです:

x[i]==y[j]の場合: a[i][j] = min(a[i-1][j-1], a[i-1][j] ]+1, a [i][j-1]+1);
x[i]!=y[j]の場合: a[i][j] = min(a[i-1][j-1 ]、a[ i-1][j]、a[i][j-1])+1;

状態遷移方程式を使用する前に、(n+1)(m+1)の行列dを初期化し、最初の行と列の値が0から増加するようにする必要があります。 2 つの文字列 (nm レベル) をスキャンし、文字を比較し、状態遷移方程式を使用し、最終的に $a[$l1][$l2] が結果になります。

簡単な実装プロセスは次のとおりです:

コードをコピーしますコードは次のとおりです:

 $s1 = "abcdd";
 $l1 = strlen($s1);
 $s2 = "aabbd";
 $l2 = strlen($s2);

 for ($i = 0; $ i＆$ l1; 1][$j] 1);
 + 1][$j + 1] = min($a[$i][$j], $a[$i][$j + 1], $a[ $i + 1][$j]) + ;

PHP 実装では、実装者はコメントで次のように明確に述べています: この関数は、実装アルゴリズムから判断すると、速度を考慮せずにメモリ使用量のみを最適化します。時間計算量は O(m×n) です。最適化のポイントは、上記の状態遷移方程式の2次元配列を2つの配列の集合に変更することです。簡単な実装は次のとおりです: 

 コードをコピーします 

 コードは次のとおりです: 

 $s1 = "abcjfdkslfdd";
 $l1 = strlen($s1);
 $s2 = "aab84093840932bd"; 
 $ l2 = strlen($s2);

 $dis = 0; for ($i = 0; $i  $p1[$i] = $ i;

} for（$ i = 0; $ i＆lt; $ l1; $ i ++）{
j ++）{
j]+1）;

echo " n"; echo $p1[$l2]; echo "n"; echo levenshtein($s1, $s2);

上記は、PHP カーネル開発者による以前のクラシック DP の最適化です。最適化のポイントは、2 つの 1 次元配列を継続的に再利用し、1 つは前回の結果を記録し、もう 1 つは今回の結果を記録することです。 PHPのパラメータに従って3つの操作に異なる値を割り当てる場合は、上記のアルゴリズムで、対応する1を操作に対応する値に変更するだけです。 min 関数の最初のパラメータは変更に対応し、2 番目のパラメータはソースコード sky の削除に対応し、3 番目のパラメータは追加に対応します。

レーベンシュタイン距離の説明
レーベンシュタイン距離は、1965 年にロシアの科学者ウラジーミルレーベンシュタインによって初めて発明され、彼の名前にちなんで命名されました。発音がわからない場合は、「編集距離」と呼んでください。レーベンシュタイン距離は次の目的で使用できます。
スペルチェック (スペルチェック)
音声認識 (文認識)
DNA 分析 (DNA 分析)
盗作検出 (盗作検出) LD は、mn 行列を使用して距離値を保存します。