☄️ 👩🏼‍🤝‍👨🏽 🌩️ MySQLのレーベンシュタイン距離とPHPを使用したファジー検索アルゴリズム ♈️ 🦇 👩🏼‍💼

前世紀の後半の初めに、ソビエトおよびロシアの有名な数学者ウラジミール・イオシフォビッチ・レーベンシュタイン（ちなみに、2ヶ月半前に亡くなりました）は、 編集距離の概念を導入しました。これは、検索エンジンからバイオインフォマティクスまでさまざまな分野でまだ使用されています。この記事では、MySQLのファジー検索にその原理を適用します（MySQLは組み込みのソリューションをまだ提供していないため）。インターネットで見つかったいくつかから最も効率的な（つまり高速）メソッドを計算し、そのような検索のアルゴリズムを構築して実装しますPHP

使用するもの：

レーベンシュタイン距離とダメラウ-レーベンシュタイン距離：両方とも、操作が異なる、ある行を別の行に変換するための最小操作数を表します-レーベンシュタインは、ある文字の挿入、削除、 置換を提案し、ダメラウはそれらを転置で追加しました。隣接する2つの文字が入れ替わる場合。次の実装がMySQL用に提案されました。
- Gordon Lesti によるレーベンシュタインスタイルのクエリ
- ジェイソン・ラスト著、 Get It Done With MySQL 5＆Up （ed。Peter Brawley and Arthur Fuller）で公開されたレーベンシュタイン距離を計算するためのユーザー定義関数
- Damerau-Levenshtein距離を計算するためのユーザー定義関数、 Linus Torvalds氏によって作成されたC関数に基づいて記述、著者-Diego Torres
Oliverのアルゴリズム：2行の類似度を計算します
- PHPでは、 similar_text関数で表されます
metaphone（metaphone）：単語のインデックス付けの音声原則。英語のアルファベットの文字でのみ動作します
- PHPでは、 metaphone関数で表されます

使用しないもの

soundexとそのPHP関数soundex ：アルゴリズムは時代遅れであり（前世紀の初めに提案されました）、まったく異なる単語は同じインデックスを取得します
残りのすべてのアルゴリズム PHPには対応する関数がありません

ファジー検索アルゴリズム

明らかに、各検索中に入力された単語とデータベース内の辞書からの各単語との間のレーベンシュタイン距離を計算しても意味がありません。それには多くの時間がかかります。ちなみに、数年前にハブでメソッドが説明されていました。各検索で、データベースの辞書全体がPHP配列にドライブされ、音訳され、次に、同様の単語が選択されました。交互に、levenshtein関数、metaphone、similar_text、または2つが同時に使用されました。予備のクイックフィルタリングとそれに続く見つかったオプションの改良のソリューションは、それ自体を示唆しています。

したがって、ファジー検索アルゴリズムの本質は次のように削減できます。

検索クエリのメタフォンを計算します。
データベース内の辞書内のすべての単語を、レーベンシュタイン距離（またはダメラウ-レーベンシュタイン距離）が2文字未満のmetaphoneで検索します。
何も見つからない場合、ユーザーは単語に多くの間違いを犯し、データベースの拷問を停止し、 ~~ユーザーが浴場に行って~~何も見つからないことを書きます。
1つの単語が見つかった場合、それを返します。
見つかった場合> 1単語、精製します。データベース内の辞書から見つかった各単語と検索クエリの類似性の割合を見つけます。類似度の最大パーセンテージを見つけます。この割合のすべての単語を返します（複数の単語の割合が同じで、最大になる場合）。

各検索では、レーベンシュタイン距離を計算する必要があります。これを行うには、MySQLのアルゴリズムの最速の実装を見つけます。

DBの準備

すべてのテストで、4年前にVkontakteから引き出された集落のベースが選択されました。テストでは、220万件以上のエントリが含まれ、部分的に13言語に翻訳された都市テーブルが使用されました。ロシア語に翻訳された列のみが残っており、多くの未翻訳の名前が含まれていました。 city_id列にもインデックスが作成されました。

次のステップは、各名前のメタフォンの形成でした。 metaphoneは英語のアルファベットの文字を含む行からのみ計算されるため、各名前は事前に変換する必要があります。キリル文字に音訳し、英語のアルファベットの文字に変換した発音区別文字を含むラテン文字。

したがって、metaphone列を追加するためのPHPコードは次のとおりです。

//        set_time_limit(0); ini_set('max_execution_time', 0); //   ,    $from = ['', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', 'á', 'ă', 'ắ', 'ặ', 'ằ', 'ẳ', 'ẵ', 'ǎ', 'â', 'ấ', 'ậ', 'ầ', 'ẩ', 'ẫ', 'ä', 'ǟ', 'ȧ', 'ǡ', 'ạ', 'ȁ', 'à', 'ả', 'ȃ', 'ā', 'ą', 'ᶏ', 'ẚ', 'å', 'ǻ', 'ḁ', 'ⱥ', 'ã', 'ɐ', 'ₐ', 'ḃ', 'ḅ', 'ɓ', 'ḇ', 'ᵬ', 'ᶀ', 'ƀ', 'ƃ', 'ć', 'č', 'ç', 'ḉ', 'ĉ', 'ɕ', 'ċ', 'ƈ', 'ȼ', 'ↄ', 'ꜿ', 'ď', 'ḑ', 'ḓ', 'ȡ', 'ḋ', 'ḍ', 'ɗ', 'ᶑ', 'ḏ', 'ᵭ', 'ᶁ', 'đ', 'ɖ', 'ƌ', 'ꝺ', 'é', 'ĕ', 'ě', 'ȩ', 'ḝ', 'ê', 'ế', 'ệ', 'ề', 'ể', 'ễ', 'ḙ', 'ë', 'ė', 'ẹ', 'ȅ', 'è', 'ẻ', 'ȇ', 'ē', 'ḗ', 'ḕ', 'ⱸ', 'ę', 'ᶒ', 'ɇ', 'ẽ', 'ḛ', 'ɛ', 'ᶓ', 'ɘ', 'ǝ', 'ₑ', 'ḟ', 'ƒ', 'ᵮ', 'ᶂ', 'ꝼ', 'ǵ', 'ğ', 'ǧ', 'ģ', 'ĝ', 'ġ', 'ɠ', 'ḡ', 'ᶃ', 'ǥ', 'ᵹ', 'ɡ', 'ᵷ', 'ḫ', 'ȟ', 'ḩ', 'ĥ', 'ⱨ', 'ḧ', 'ḣ', 'ḥ', 'ɦ', 'ẖ', 'ħ', 'ɥ', 'ʮ', 'ʯ', 'í', 'ĭ', 'ǐ', 'î', 'ï', 'ḯ', 'ị', 'ȉ', 'ì', 'ỉ', 'ȋ', 'ī', 'į', 'ᶖ', 'ɨ', 'ĩ', 'ḭ', 'ı', 'ᴉ', 'ᵢ', 'ǰ', 'ĵ', 'ʝ', 'ɉ', 'ȷ', 'ɟ', 'ʄ', 'ⱼ', 'ḱ', 'ǩ', 'ķ', 'ⱪ', 'ꝃ', 'ḳ', 'ƙ', 'ḵ', 'ᶄ', 'ꝁ', 'ꝅ', 'ʞ', 'ĺ', 'ƚ', 'ɬ', 'ľ', 'ļ', 'ḽ', 'ȴ', 'ḷ', 'ḹ', 'ⱡ', 'ꝉ', 'ḻ', 'ŀ', 'ɫ', 'ᶅ', 'ɭ', 'ł', 'ꞁ', 'ḿ', 'ṁ', 'ṃ', 'ɱ', 'ᵯ', 'ᶆ', 'ɯ', 'ɰ', 'ń', 'ň', 'ņ', 'ṋ', 'ȵ', 'ṅ', 'ṇ', 'ǹ', 'ɲ', 'ṉ', 'ƞ', 'ᵰ', 'ᶇ', 'ɳ', 'ñ', 'ó', 'ŏ', 'ǒ', 'ô', 'ố', 'ộ', 'ồ', 'ổ', 'ỗ', 'ö', 'ȫ', 'ȯ', 'ȱ', 'ọ', 'ő', 'ȍ', 'ò', 'ỏ', 'ơ', 'ớ', 'ợ', 'ờ', 'ở', 'ỡ', 'ȏ', 'ꝋ', 'ꝍ', 'ⱺ', 'ō', 'ṓ', 'ṑ', 'ǫ', 'ǭ', 'ø', 'ǿ', 'õ', 'ṍ', 'ṏ', 'ȭ', 'ɵ', 'ɔ', 'ᶗ', 'ᴑ', 'ᴓ', 'ₒ', 'ṕ', 'ṗ', 'ꝓ', 'ƥ', 'ᵱ', 'ᶈ', 'ꝕ', 'ᵽ', 'ꝑ', 'ʠ', 'ɋ', 'ꝙ', 'ꝗ', 'ŕ', 'ř', 'ŗ', 'ṙ', 'ṛ', 'ṝ', 'ȑ', 'ɾ', 'ᵳ', 'ȓ', 'ṟ', 'ɼ', 'ᵲ', 'ᶉ', 'ɍ', 'ɽ', 'ꞃ', 'ɿ', 'ɹ', 'ɻ', 'ɺ', 'ⱹ', 'ᵣ', 'ś', 'ṥ', 'š', 'ṧ', 'ş', 'ŝ', 'ș', 'ṡ', 'ṣ', 'ṩ', 'ʂ', 'ᵴ', 'ᶊ', 'ȿ', 'ꞅ', 'ſ', 'ẜ', 'ẛ', 'ẝ', 'ť', 'ţ', 'ṱ', 'ț', 'ȶ', 'ẗ', 'ⱦ', 'ṫ', 'ṭ', 'ƭ', 'ṯ', 'ᵵ', 'ƫ', 'ʈ', 'ŧ', 'ꞇ', 'ʇ', 'ú', 'ŭ', 'ǔ', 'û', 'ṷ', 'ü', 'ǘ', 'ǚ', 'ǜ', 'ǖ', 'ṳ', 'ụ', 'ű', 'ȕ', 'ù', 'ᴝ', 'ủ', 'ư', 'ứ', 'ự', 'ừ', 'ử', 'ữ', 'ȗ', 'ū', 'ṻ', 'ų', 'ᶙ', 'ů', 'ũ', 'ṹ', 'ṵ', 'ᵤ', 'ṿ', 'ⱴ', 'ꝟ', 'ʋ', 'ᶌ', 'ⱱ', 'ṽ', 'ʌ', 'ᵥ', 'ẃ', 'ŵ', 'ẅ', 'ẇ', 'ẉ', 'ẁ', 'ⱳ', 'ẘ', 'ʍ', 'ẍ', 'ẋ', 'ᶍ', 'ₓ', 'ý', 'ŷ', 'ÿ', 'ẏ', 'ỵ', 'ỳ', 'ƴ', 'ỷ', 'ỿ', 'ȳ', 'ẙ', 'ɏ', 'ỹ', 'ʎ', 'ź', 'ž', 'ẑ', 'ʑ', 'ⱬ', 'ż', 'ẓ', 'ȥ', 'ẕ', 'ᵶ', 'ᶎ', 'ʐ', 'ƶ', 'ɀ', 'ß' ]; //   ,     $to = ['a', 'b', 'v', 'g', 'd', 'e', 'yo', 'zh', 'z', 'i', 'y', 'k', 'l', 'm', 'n', 'o', 'p', 'r', 's', 't', 'u', 'f', 'h', 'ts', 'ch', 'sh', 'shch', '', 'y', '', 'e', 'yu', 'ya', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'b', 'b', 'b', 'b', 'b', 'b', 'b', 'b', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'd', 'd', 'd', 'd', 'd', 'd', 'd', 'd', 'd', 'd', 'd', 'd', 'd', 'd', 'd', 'e', 'e', 'e', 'e', 'e', 'e', 'e', 'e', 'e', 'e', 'e', 'e', 'e', 'e', 'e', 'e', 'e', 'e', 'e', 'e', 'e', 'e', 'e', 'e', 'e', 'e', 'e', 'e', 'e', 'e', 'e', 'e', 'e', 'f', 'f', 'f', 'f', 'f', 'g', 'g', 'g', 'g', 'g', 'g', 'g', 'g', 'g', 'g', 'g', 'g', 'g', 'h', 'h', 'h', 'h', 'h', 'h', 'h', 'h', 'h', 'h', 'h', 'h', 'h', 'h', 'i', 'i', 'i', 'i', 'i', 'i', 'i', 'i', 'i', 'i', 'i', 'i', 'i', 'i', 'i', 'i', 'i', 'i', 'i', 'i', 'j', 'j', 'j', 'j', 'j', 'j', 'j', 'j', 'k', 'k', 'k', 'k', 'k', 'k', 'k', 'k', 'k', 'k', 'k', 'k', 'l', 'l', 'l', 'l', 'l', 'l', 'l', 'l', 'l', 'l', 'l', 'l', 'l', 'l', 'l', 'l', 'l', 'l', 'm', 'm', 'm', 'm', 'm', 'm', 'm', 'm', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'o', 'o', 'o', 'o', 'o', 'o', 'o', 'o', 'o', 'o', 'o', 'o', 'o', 'o', 'o', 'o', 'o', 'o', 'o', 'o', 'o', 'o', 'o', 'o', 'o', 'o', 'o', 'o', 'o', 'o', 'o', 'o', 'o', 'o', 'o', 'o', 'o', 'o', 'o', 'o', 'o', 'o', 'o', 'o', 'o', 'p', 'p', 'p', 'p', 'p', 'p', 'p', 'p', 'p', 'q', 'q', 'q', 'q', 'r', 'r', 'r', 'r', 'r', 'r', 'r', 'r', 'r', 'r', 'r', 'r', 'r', 'r', 'r', 'r', 'r', 'r', 'r', 'r', 'r', 'r', 'r', 's', 's', 's', 's', 's', 's', 's', 's', 's', 's', 's', 's', 's', 's', 's', 's', 's', 's', 's', 't', 't', 't', 't', 't', 't', 't', 't', 't', 't', 't', 't', 't', 't', 't', 't', 't', 'u', 'u', 'u', 'u', 'u', 'u', 'u', 'u', 'u', 'u', 'u', 'u', 'u', 'u', 'u', 'u', 'u', 'u', 'u', 'u', 'u', 'u', 'u', 'u', 'u', 'u', 'u', 'u', 'u', 'u', 'u', 'u', 'u', 'u', 'u', 'u', 'u', 'v', 'v', 'v', 'v', 'v', 'w', 'w', 'w', 'w', 'w', 'w', 'w', 'w', 'w', 'x', 'x', 'x', 'x', 'y', 'y', 'y', 'y', 'y', 'y', 'y', 'y', 'y', 'y', 'y', 'y', 'y', 'y', 'z', 'z', 'z', 'z', 'z', 'z', 'z', 'z', 'z', 'z', 'z', 'z', 'z', 'z', 'ss']; //     function mtphn($s){ //        return metaphone( str_replace($from, $to, mb_strtolower($s)) ); } //     $conn = mysqli_connect('localhost','root','','test') or die(mysqli_error($conn)); //       mysqli_query($conn, "ALTER TABLE _cities ADD COLUMN metaphone VARCHAR(30) DEFAULT NULL"); //      id $q = mysqli_query($conn, "SELECT city_id, title_ru FROM _cities"); while ($row = mysqli_fetch_assoc($q)) //        mysqli_query($conn, "UPDATE _cities SET metaphone='".mtphn($row['title_ru'])."' WHERE city_id=".$row['city_id']); mysqli_close($conn); //        echo '.   '.( microtime(true) - $_SERVER["REQUEST_TIME_FLOAT"] ).' .';

2,246,813行の場合、メタフォンとその挿入の計算には約38分かかりました。

メタフォンの列にもインデックスが作成されました。それ以降の検索操作は、その中でのみ発生します。

MySQLのレーベンシュタイン距離実装の選択

前述のように、3つの実装-フラッタリーリクエスト、Rast関数、およびTorres関数の速度がチェックされます。

テストでは、5語（またはスペルミス）、3語はキリル文字、2語はラテン語を使用します。

いや	正しいつづり	彼のメタフォン	スペルミス	彼のメタフォン	レーベンシュタインメタフォン
1。	アレクサンドロフスク-サハリンスキー	ALKSNTRFSKSHLNSK	アルとザンダー、vsk-sa g olin zkiy	ALKSNTRFSKS K LNSK	1
2。	セミカラコルスク	SMKRKRSK	ckのがんについての Semik	SMKRK F SK	1
3。	シャレンタバン	XRNTSFN	シェレンツ	XRNTS F	1
4。	ブヌンブーグーラ	BNNBKL	B o n u nb o g uv a	BNNBK F	1
5。	カンポン・テナキ・カワン	KMPNKTNKKWNK	かんぽんエナキカヴァン	KMP NT NKK F NK	2

最後の言葉では、レーベンシュタインの距離が2文字になるように、意図的にさらにミスが行われました。各メソッドが正常に機能する場合、最後の単語を検索すると、毎回0行が返されます。

お世辞のリクエスト

最初のオプションは、3つすべての中で最も原始的なものです。ここでは、多数のLIKEステートメントを使用したSQLクエリでシミュレートされるレーベンシュタイン距離原理（挿入、削除、および置換操作）が基礎として採用されます。行（単語）で構成される場合

n

$n$ 文字（文字）、1文字のレーベンシュタイン距離を検索するときのLIKE演算子の数は、

3 n + 1

$3n + 1$ （または

3 n + 2

$3n + 2$ レーベンシュタイン距離<2文字を検索する場合）。

記事の最後に、著者はそのようなSQLクエリのコンパイルを自動化するPHP関数を提供しています。この機能は、メタフォン検索用に変更されましたが、原則は同じままです。

 //    $input = ''; //    $input_m = mtphn($input); //  ,     LIKE  SQL- //       $q_likes = [$input_m . '_']; //     for ($i = 0, $len = strlen($input_m); $i < $len; $i++) //     ,    for($n = 1; $n < 4; $n++) $q_likes[] = substr( $input_m, 0, $i ) . ($n & 1 ? '_' : '') . substr( $input_m, $i + ($n > 1 ? 1 : 0) ); //    $conn = mysqli_connect('localhost','root','','test') or die(mysqli_error($conn)); //   +       $q = mysqli_query($conn, "SELECT city_id, title_ru FROM _cities WHERE metaphone LIKE '".implode("' OR metaphone LIKE '",$q_likes)."'"); //   mysqli_close($conn); //     $result = []; //     while($row = mysqli_fetch_assoc($q)) $result[] = [ $row['city_id'], $row['title_ru'] ]; //    // echo'<pre>'; print_r($result); echo'</pre>'; echo '<p>.   '.( microtime(true) - $_SERVER["REQUEST_TIME_FLOAT"] ).' ';

LIKEは、両方のアンダースコアとパーセント記号の両方の検索パターンでチェックされました。

ワード番号	「_」付きのLIKEの場合はt 、sec	見つかった	「％」のあるLIKEの場合、秒	見つかった
1。	24.2	1	24.6	1
2。	14.1	1	14.8	4
3。	11.9	188	12.3	224
4。	11.9	70	12.8	87
5。	18.1	0	19.6	0

単語が長いほど、類似のメタフォンを検索するのに時間がかかります（これは明らかです）が、同時に、単語が長いほど、各文字に費やす時間が少なくなります（明らかではありません）。と仮定する

t

$t$ -同様のメタフォンの検索に費やした合計時間、および

n

$n$ -私たちが探していたメタフォンの文字の総数。最初の単語が2番目の単語より短い場合（

n_{1} < n_{2}

$n_1 <n_2$ ）したがって、最初の単語の類似したメタフォンの検索に費やされた合計時間は、2番目の単語よりも短くなります（

t_{1} < t_{2}

$t_1 <t_2$ ）その後

f r a c t_{1} n_{1} > f r a c t_{2} n_{2}

$\ frac {t_1} {n_1}> \ frac {t_2} {n_2}$

検索パターン「_」を「％」に置き換えると、時間の急激な急増も予想されましたが、合計時間は2〜8％の範囲で増加しました。

ラスタ機能

2番目のオプションは、ユーザー定義関数levenshteinで、2つのパラメーター（2つのVARCHAR行（255））を取り、数値INTを返します-レーベンシュタイン距離。補助関数levenshtein_ratioも提案されています。これは、前の関数で計算されたレーベンシュタイン距離に基づいて、2行の類似度のパーセンテージを返します（PHP関数Similar_textと同様）。最初の機能のみをテストします。

レーベンシュタイン距離が1文字のすべての単語を検索してみましょう。

 SELECT city_id, title_ru FROM _cities WHERE levenshtein("BNNBKF",metaphone)=1

4番目の名前（最短のメタフォンを持つ）の類似のメタフォンを検索すると、検索テンプレート "_"でLIKEを使用して検索した場合と同じ結果が得られましたが、約66分かかりました。

トーレス関数

3番目のオプションは、 Linus TorvaldsがCで作成した関数の実装です。この関数は3つのパラメーターを取ります-比較のために2行、整数INTは上限です。比較のために各行から取得される最大文字数。

私たちのテストからのすべての比phor-20文字の普遍的な上限を設定し、1文字のDamerau-Levenshtein距離を持つすべての単語を見つけようとします。

 SELECT city_id, title_ru FROM _cities WHERE damlevlim("BNNBKF",metaphone,20)=1

結果：

ワード番号	f-torresの場合はt 、sec	見つかった
1。	11.24	1
2。	9.25	1
3。	9.19	173
4。	8.3	86
5。	11.57	0

Torres関数は、Flattery要求と比較して、特にRast関数と比較して優れた結果を示しています。 2番目のプラス-Torresは高度なDamerau-Levenshteinアルゴリズムを使用しました。このアルゴリズムでは、転置操作が挿入、削除、および置換操作に追加されました。 Torres関数とFlatteryリクエストの結果を比較します。

ワード番号	要求のお世辞、秒	f-torresの場合はt 、sec	クエリのお世辞、単語が見つかりました	F.トレス、発見された言葉
1。	24.2	11.24	1	1
2。	14.1	9.25	1	1
3。	11.9	9.19	188	173
4。	11.9	8.3	70	86
5。	18.1	11.57	0	0

返される行の数の違いは、使用されるアルゴリズムの違いによって説明できます（それぞれ、ブラーニーとトーレス関数を照会するためのレーベンシュタインとダメラウ-レーベンシュタイン）。 5つのケースのうち5つのケースで、Torres関数が勝者となりました。そのため、PHPの最終的な実装で使用され、similar_text関数によって結果が絞り込まれます。

PHPの実装

検索クエリが音訳されていない場合、つまり、同様の単語を受け取った後、元の単語と比較されます。実験中に、similar_text関数は、同じレーベンシュタイン距離にあるキリル文字とラテン文字の単語に対して異なる結果を返すことがわかりました。そのため、計算の純度を高めるために、levenshtein PHP関数の使用時に同じ問題を解決するためにluciole75wによって元々提案されたutf8_to_extended_ascii関数が追加で使用されます。

 //   $input = ''; //     similar_text  UTF-8 function utf8_to_extended_ascii($str, &$map){ $matches = array(); if (!preg_match_all('/[\xC0-\xF7][\x80-\xBF]+/', $str, $matches)) return $str; foreach ($matches[0] as $mbc) if (!isset($map[$mbc])) $map[$mbc] = chr(128 + count($map)); return strtr($str, $map); } //     function damlev($input){ //     $input_m = mtphn($input); //    $conn = mysqli_connect('localhost','root','','test') or die(mysqli_error($conn)); //      - 0  1 $q = mysqli_query($conn, 'SELECT city_id, title_ru FROM _cities WHERE damlevlim("'.$input_m.'",metaphone,20)<2'); //   mysqli_close($conn); //     while ($row = mysqli_fetch_assoc($q)) $damlev_result[] = [ $row['city_id'], $row['title_ru'] ]; //    1 -  if (count($damlev_result) > 1){ //   foreach ($damlev_result as $v) //     //         similar_text( utf8_to_extended_ascii($input,$charMap), utf8_to_extended_ascii($v[1],$charMap), $similar_text_result[] ); //    $max_similarity = max($similar_text_result); //       $most_similar_strings = array_flip( array_keys($similar_text_result, $max_similarity) ); //      return array_intersect_key($damlev_result,$most_similar_strings); } //      1 - //       1  else return $damlev_result; } echo '<p> : '.$input; $output = damlev($input); //      if (count($output) > 0){ //     - foreach ($output as $v) //       $results_list[] = '<a href="search.php?id='.$v[0].'">' .$v[1].'</a>'; echo '<p>,  : '.implode(', ',$results_list); } else //    - ,    echo'<p>  ,  .';

結果は次のようになります。

名前を探しています：Cherentseva

おそらくあなたが探しているのは： Charentsavan 、 Cherentsovka

まとめ

最も高速なのはDamerau-Levenshtein distanceの実装で、CでLinus Torvaldsが作成し、ユーザー定義関数としてMySQL用にDiego Torresが採用しました。第二に、わずかな時間差で、多数のLIKEステートメントを持つSQLクエリの形式で、レーベンシュタイン距離の原始的な模倣があります、著者-Gordon Lesti。 3番目に、Jason RastによるMySQLのユーザー定義関数ははるかに遅れていました。

結論として、本番環境でのMySQLでのレーベンシュタイン距離計算の使用は、比較する行が短く、その行と比較される単語のあるテーブルが小さい場合にのみ必要であることを付け加えます。そうでない場合、大きな辞書を持つテーブルの場合に考えられる解決策は、たとえば最初の文字、または単語またはそのメタフォンの長さによって、いくつかのテーブルに分割することです。

ほとんどの場合、Webのファジー検索アルゴリズムの適用分野は、既存の辞書の名前と名前を検索することです。ユーザーは入力ミスをしたり、少なくとも1文字間違える可能性が高いです。いずれにせよ、スクリプトが提供するオプションがスクリーンショットの対象にならないことを予測してみてください。

PSレーベンシュタイン距離を計算するための他のカスタムMySQL関数に関する別の記事。

PPSのコメントでは、 YourChiefは、生産にはレーベンシュタインオートマトンを使用する方がはるかに効率的であると示唆しています。

MySQLのレーベンシュタイン距離とPHPを使用したファジー検索アルゴリズム