記事のタイトルで表明されたトピックは新しいものではありません。 インターネットでは、その実装方法に関する多くの質問を見つけることができますが、答えはほとんどありません。 そして、まれではありませんが、サードパーティ製品（Sphinxなど）の使用に関するアドバイスを受けます。 しかし、多くの場合、このようなかさばるアドオンを使用する必要はありません。

少し前まで、次のタスクが発生しました。

• 情報システム（IP）には、俳優、ミュージシャン、DJ、さらには政治家、科学者、その他の著名人のデータベース（DB）があります。
• IPはアマチュアとアマチュアでいっぱいで、その多くはこれまたはその姓をロシア語に正しく翻訳するのが難しいと感じました。 そして時々、ロシア語で名前が外国語で書かれた方法とはかなり異なって聞こえることがありました。
• 名前はかなり自由な形式でデータベースに入力されました。 名前の語順はしばしば変更され（特にアジアの名前の場合）、さらに、ニックネームと仮名が示される（または示されない）可能性があります。
• 単純な間違いがありました-置換、省略、または文字の追加。 時には、何らかの理由で、文字の一部がラテン文字で書かれていました。
• 幸いなことに、偶然の登場人物はいませんでした。
• 名前は、UTF-8エンコーディングでMyISAM MySQLテーブルに保存されました。
• データベース内の名前の総数は約138.5千でした。

これが「与えられた」ものです。 そして、以下が「必須」でした：

データベースを自動的にスキャンすることにより、何らかの基準で類似する名前のペアを識別および形成し、それらをさらに手動分析に渡して、同じ人に属しているか異なる人に属しているかを判断します。 さらに、検索にはいくらかの妄想があったはずです。 つまり 「 おそらくあなたが念頭に置いていた... 」とは異なり、「 終わらないよりも追い越したほうがよい 」という原則に基づいて、さらにいくつかの名前を付けることになっていた 。 したがって、わずかに多くのペアを類似性について分析する必要がありました。 さらに、これをリアルタイムではなく、本当に限られた時間で行うこと。 つまり、1日や1週間ではなく、最悪の場合には数時間でです。



一般に、要するに、任意の語順、タイプミス、エラー、異なる綴りの別々のフィールド（姓、名、ミドルネームなど）に分割することなく、ほぼ15万の名前、ニックネーム、仮名があります。 さらに、名前にはさまざまな国籍があります-ロシア語、英語、ユダヤ人、ポーランド語、フランス語、韓国語、中国語、日本語、インド、ネイティブアメリカンなど。 それらの中から、同じ名前に強く似ているすべての種類のペアを見つける必要があります。







最初は、このタスクは非常に難しいようでした。 あいまい検索に不慣れな私にとって、名前の類似性や相違を判断するための正式な基準を想像することさえ困難でした。



しかし、徐々にこれらの目的に使用されるアプローチとアルゴリズムの理解が形成され始めました。 まず第一に、これらは、スペル名のエラーを探す際に特に指向された、または単にうまく機能するアルゴリズムでした：

• 音声コーディング（特に、Pyotr Kankovskyによる「ロシアのメタフォン」とその修正[1] ）。
• レーベンシュタイン編集距離[2]に基づく類似性の尺度。
• 一般形式の分離[3] 。
• Jaro-Winklerアルゴリズム[4] 。
• N-gram分析。 [5] 。

常識によると、以下が受け入れられました。

音声コーディングは、データベースにデータを入力するために適切ではありません。 音声検索では、アマチュアのアマチュアが翻訳したものではなく、耳で間違って綴られた名前を見つけることができます。 例で説明します。







ここで、第3ランクのJeannette Devereaux [6]の船長が私たちの母国のパスポートオフィスに来て、チャーターに従ってはっきりと大声で現れます。 また、パスポート担当者は、自分の姓と「Diver」、「Devir」、さらには「Divir」を耳で録音できます。 さらに、スキップする名前の子音を2倍にします。 これらすべての「聴覚幻覚」は、音声コーディングによるファジー検索アルゴリズムによって完全に追跡されます。



しかし、woeはフランス語の詳細を知らない（しかし英語に精通している）「翻訳者」であり、軍事IDからデータをコピーすることで、「Zhennett DeVerox」を簡単に書くことができます。 特に才能のある人は、コールサインを示すか、名前の前に名前を綴ることができます。



または、多くの英語を話す「翻訳者」でさえ、「Ralph Fiennes」という名前を「Ralph」ではなく「Ralph Fiennes」と読む必要があることを知りません。



したがって、この場合、誤った名前のスペルは「 CC aを聞いたとき」ではなく「 RTCRの形式のように」綴られるため、音声コーディングは適切ではありません。



耳ではなく目で認識される名前に音声アルゴリズムを適用しようとすると、名前の音声インデックスがスペルのバリエーションよりもさらに異なるという事実につながる可能性があります。

それでは、編集距離を使用するのでしょうか？

これらのメトリクスが、任意の単語順のフレーズではなく、単語を比較するように特別に設計されているという事実がなければ、良い考えです。 名前と姓を場所を入れ替えたり、それらの間にエイリアスを挿入したりする必要があり、それらは非常に不満足な結果を示します。



この場合、名前を個別の単語に分割し、それぞれをすでに比較する必要があります。 そして、これらの個々の単語を音声インデックスに最初に持って来たとしても、これはアルゴリズムの動作を著しく複雑にします（そして遅くします）。 また、名前に含まれる単語の数が可変量であるという事実は、さらに複雑になります。 単語の省略や並べ替えの可能性を考えると、このプロセスの複雑さを想像することさえすでに困難です。

その他の方法

一般的な形式を区別するためのメトリックの欠点には、不明確なインデックス機能、特に短い名前で関連性を計算する時間が非常に複雑であることが含まれます。 最大共通部分文字列の単一の割り当てでも、時間の複雑さはO（nm）です。 そして、残りの共通部分文字列の再帰的検索を継続する必要があるため、関連性関数の計算は非常に高価な操作であり、N-gram比較にさえ失われます。



繰り返しますが、場所の言葉を変えると、関連性は劇的に低下します。



Jaro-Winkler距離計算ははるかに高速に動作します。 しかし、残念ながら、言葉の変化にも抵抗しません。



そのため、名前の単語を分離して結合する必要がないように、willy-nillyはN-gram分析に専念しなければなりませんでした。 むしろ、トライグラムでも、なぜなら 短い韓国語の名前は、長すぎるN-gramを強調するのに役立ちません。

ステージ1。 正面衝撃。

まず、トライグラム比較の時間の複雑さを理解するために、データベース全体の名前をペアで比較する最も単純なバージョンのスクリプトを作成しました。



このスクリプトは、ASUS P5B-Eマザーボード上のシングルコアIntel Pentium D 925とほぼ同じ年齢の通常のハッキングされたSeagateハードドライブを搭載した8歳のコンピューターで自宅で作成およびテストされました。



彼らが言うように、このスクリプトは額で機能しました。 データベースを読み取り、以前に正規化した各名前を一意のトライグラムに分割し、以前の各名前（つまり、以前にテストしたデータベース内の名前）の出現回数をカウントしました。 2倍の一致数をこれらの各名前の一意のトリグラムの合計で除算した結果が特定のしきい値（たとえば、0.75または0.8）を超えた場合、これはファイルに記録されました。



名前の正規化は次のとおりです。

• 英語の文字といくつかの数字は、同様のスペルのロシア語の文字に置き換えられました。
• 小文字はすべて大文字に置き換えられました。
• 文字「E」は「E」に、「b」は「b」に置き換えられました。
• 他のすべての文字、記号、印刷できない文字、およびそれらのシーケンスは、2つのスペースに置き換えられました。
• 名前は二重スペースで囲まれています。

このような正規化の結果、句読点や音訳文字なしで、各単語が二重スペースで囲まれたり他の単語と区切られたりすることなく、簡略化された名前が得られました。



単語間および名前の先頭と末尾での二重スペースの使用により、トリグラム分析アルゴリズムは単語の場所の変更に完全に反応しなくなりました。



正規化された名前では、すべての種類の一意のトライグラムが際立っていました-3つの連続した文字（スペースを含む）の組み合わせ。



次に、2つの名前に対して次の関連係数が計算されました。2倍の数の一般的なトリグラムは、各名前の一意のトリグラムの合計で除算されました。



トライグラムの一意性の要件は、理由により表明されています。 一方では、名前のトライグラムの一意性を考慮せずに総数を数えると、「John Smith」と「John John Smith」などの名前を自信を持って区別できます。 また、一意のトライグラムのみを考慮すると、これらの名前は同一と見なされることになります。



一方で、第一に、そのような名前を区別する必要はほとんどありません。 そして、第二に、ユニークなものだけでなく、すべてのトライグラムの関連性の計算は、この手順を著しく複雑にします。 共通のトライグラムの数を2倍にする代わりに、2番目の名前の名からのトライグラムと、2番目の名前の名からのトライグラムの発生の合計を考慮する必要があります。 つまり、これにより、関連性の計算に費やされる時間が約2倍になります。 そして、第三に、関連性の計算手順にいくつかの最適化を適用することはできません。これについては後で説明します。



したがって、前頭アルゴリズムは、最初の数千の名前で記述およびテストされました。 結果は憂鬱でした。 予想どおり、名前の配列全体の一致の検索時間は、そのサイズに顕著な2次依存性がありました。 130〜14万の名前の配列全体を処理する傾向の予測は、約2年でした。 多すぎます！



しかし、アルゴリズムのパフォーマンスの初期評価がありました。

ステージ2。 最適化方法を検索します。

まず、最適化が必要なアルゴリズムの要素と、システム全体の速度を低下させる悪名高い「ボトルネック」を評価する必要がありました。 最適化にはいくつかの領域がありました。

1. データベースからの最初の選択では、名前の配列全体を作成するのではなく、他の操作の数を減らすために、テスト済みの名前と少なくともわずかに類似した名前のみを作成する必要があります。 コードのさまざまなセクションの実行時間を分析した結果、データベースへのクエリが「ボトルネック」であることがわかりました。 各リクエストの実行時間と各サンプルで発行される候補名の数の両方を削減する必要がありました。
2. UTF-8のマルチバイトエンコーディングの文字列を使用して実行される部分文字列の比較とコピーの操作は、シングルバイトエンコーディングの文字列を使用した同じ操作よりもパフォーマンスが数倍劣ります。
3. 合計トリグラムの割合が小さい場合、関連性係数を正確に計算する必要はありません。 この場合、明らかになるとすぐにこのプロセスを中断することが可能になります。 他のすべてのトライグラムが共通であることが判明した場合でも、必要な境界値を超えることはありません。
4. その他の詳細。

ステージ3。 実装。

まず、最も簡単な方法として、正規化されたUTF-8名のエンコードからWindows-1251のエンコードに切り替える試みが行われました。 しかし、MySQLは、異なるテーブルであっても、データベースの異なるエンコーディングで行を格納することに非常にjeしていることが判明しました。 データベースでの操作中に、ローカライズ不可能なエラーが発生します。 したがって、正規化された名前は追加の添付テーブルにUTF-8形式で保存され、必要に応じてWindows-1251にトランスコードされます。



正規化された名前を保存すると、時間を大幅に節約できます。 正規化は、各レコードに対して一度だけ実行する必要があります。



さらに、正規化された名前の一意のトライグラムの数は、同じ添付テーブルに保存されます。 この値を使用すると、名前の違いが明らかになりすぎた場合に関連性の計算を強制的に完了できます。 同時に、名前の一意のトリグラムの数を毎回計算する必要はなくなりました。



さて、そして最も重要なことには、処理された名前はトライグラムインデックスによってインデックス付けされます。 つまり 追加の表には、正規化された名前に存在するすべての一意のトライグラムがリストされています。 同時に、「遅い」UTF-8エンコーディングに格納しないために、トライグラム自体は整数ハッシュとして格納されました-数字の最下位3バイトは、Windows-1251エンコーディングの対応する文字の数値に対応していました。



しかし、同時に、完全に無効なアプローチが行われました。さらに説明されたように、検証される名前からの各トリグラムに対して、候補名の独自の選択が行われ、それが単一の配列に結合されました。 さらに、この配列の各名前にはカウンターが付いていました-いくつのサンプルに出会ったかです。 これらの名前をトリグラムに分解する必要がないため、これにより関連性の計算にいくらかの利益が得られると想定されていました-このカウンターを使用して関連性をすぐに計算するのに十分でした。



残念ながら、MySQLデータベースからの複数の選択（より広い範囲）と統一された名前の配列の形成（より少ない範囲）により、関連性の計算を単純化することによって得られるゲインよりも何倍も高いオーバーヘッドコストが発生しました。



説明した最適化の結果、時間コストの大幅な削減が達成されました。



初期サンプルにトライグラムインデックスを使用すると、結果の時間の予測が2年から3か月未満に短縮されました。 UTF-8形式の部分文字列の代わりに数値を使用すると、全体の処理時間がさらに10〜12％短縮されます。 しかし、やはり同じように、2.5か月の連続操作は長すぎるように思われました。 同様の名前の最初の選択は、わずかなスポットのままでした。

ステージ4。 さらなる改善。

トライグラムインデックスごとにデータベースに繰り返しアクセスすることはお勧めできません。 多数のサンプルが十分に長く取られただけでなく、統合された配列は非常に大きく、各要素に共通のトリグラムカウンターを使用しているにもかかわらず、処理にかなりの時間がかかりました。



このカウンターのアイデアを放棄しなければなりませんでしたが、WHERE IN SQL構造を使用して、1つのクエリで候補名の初期セット全体を取得しました。 これにより、予測を数回、1か月に減らすことができました。



次に、関連性の計算手順が変更されました。 関連性の下限と名前に含まれる一意のトライグラムの数に基づいて、「ミス」の最大許容数、つまり、検証済みの名前に含まれない申請者名のトライグラムの数が計算されました。 次に、申請者名のすべてのトリガーを検証済みの名前に入力するためにチェックしました。 「ミス」の数が許容最大数を超えるとすぐに、比較が停止されました。 これにより、時間予測を数パーセント短縮できました。 しかし、それはまだ産業的価値とはかけ離れていました。

ステージ5。 解決策。

タスクは不溶性のようでした。 一方では、初期サンプルの名前の数を大幅に減らす必要がありましたが、他方では、この削減は、関連性の許容範囲の下限に近い名前を誤って切り捨てないように、人為的すぎてはなりません。



アプローチを見つけることは、見つかった同様の名前のペアを単に調べることによって可能になりました。 このようなペアのほとんどすべてに、長さが6〜7文字の共通のサブシーケンスがありました（隣接する二重スペースを含む）。 単純な推論を使用して（これはそのゆるみのためここでは示しません）、0.75を超える関連性を実現するには、正規化された名前には5文字以上の共通部分文字列が必要であると結論付けることができます。



したがって、トライグラムによる予備検索のインデックス付けから、ペンタグラム（5文字の部分文字列）によるインデックス付けに進みます。 PHPの32ビットバージョンで32ビットを持つ整数変数に五penta星のハッシュを合わせるために、31文字（「」と「b」を除く）とスペースがあるため、各文字を5ビットとして表します。

別の小さな追加。

上記で書いたように、関連性を計算するとき、名前の1つの一意のトライグラムが比較され、2番目の名前のトライグラムと一致しました。 この場合、最大許容数の「ミス」の数を超えたときに計算が停止しました。



最初の名前の一意のトリグラムの数が2番目の名前の一意のトリグラムの数よりもはるかに少ない場合、計算されたミスの最大数は負になる可能性があります。 これは、これらの名前が関連性の特定の値に決して似ていないことを意味します。 そして、それらをチェックする必要はありません。



しかし、名の一意のトライグラムの数が2番目の名前のそれらの数よりもはるかに多い場合、このカットオフは逆の場合には機能しません。 そのため、クエリに加えて、正規化された名前の一意のトリグラムの数の境界値が導入されました。



これは幾分物議をかもす改善です。 0.75の関連性制限値が指定されている場合、それは加速につながりませんが、反対に、サンプルの複雑さの増加により3％のパフォーマンスの損失につながります。 ただし、関連性の制限を0.8に設定すると、既に3％の利益が得られます。



ただし、この手法は廃止されました。 損失は​​それほど大きくありませんが、最初に、関連性の高い類似したペアの予備検索を行うことができます。 そして、予備洗浄の後でのみ、境界値を0.75に設定します。

結果。

一般的なトライグラムによる初期選択から五penta星による選択への移行の結果、スクリプトを大幅に高速化することができました。 138.5千の名前のうち0.8ペアの関連性を持つ類似の検索は、1か月ではなく約5時間でした。 つまり 指定された名前のデータベース全体で類似した名前を1回検索すると（処理時間の2次依存性を取得する場合）約0.26秒です。 多少は多いですが、これは強力なプロセッサと高性能ディスクシステムを備えたサーバーではなく、8年前の半死状態のホームコンピューターでのテスト実行であることを覚えておく必要があります。



原則として、ヘキサグラム（6文字のインデックス部分文字列）でも初期検索を実行することが可能です。 これにより、数倍の加速が得られました。 しかし、アジアの短縮名の多くのペア（およびそれらだけではなく）を排除できるという十分に根拠のある恐怖がありました。 はい、特別な意味はありません。 その後の受信ペアの手動分析（およびそれらの1万1千以上があった）は、いずれの場合も数か月かかります。



しかし、過度の偏執狂が必要ではないが、逆に、最も適切な名前の最小数を見つける必要がある場合、ヘキサグラムを使用したインデックス付けは、「おそらく考えていた...」などのヒントに非常に適しています。



原則として、長い名前を使用する場合、7文字の部分文字列のインデックスを使用できます。 そして、それらを32ビット変数に入れるために、予備の音声コーディングを実行して、文字数を15とスペースに減らします。 しかし、その瞬間にそのようなタスクは立っていませんでした。



残念ながら、スクリプトを書いた直後に、サイトは著作権侵害のためにブロックされました。 彼はすぐに別のアドレスに移動しましたが、問題が山積していたため、重複した名前を検索する時間はありませんでした。

アルゴリズムの断片：

最初の1000レコードでのテスト実行の結果：

参照とメモ：

1.音声コーディング。

→ 音声アルゴリズム。 ハブラハブル

→ 「姓」、またはロシア語のMetaPhone（ロシア語のMetaphoneの説明）



2. レーベンシュタイン距離。 ウィキペディア



3.一般的なフォームの割り当てに基づく単語の類似性の計算は、similar_text関数でPHPに実装されています。 PHPのドキュメントには、この関数はOliverアルゴリズム[1993]に基づいていると記載されています。 ただし、当初、「Ratcliff / Obershelpパターン認識アルゴリズム」というタイトルのこのアルゴリズムは、John W. RatcliffによってDr. 1988年のDobb's（ パターンマッチング：ゲシュタルトアプローチ ）。 そして、Ian Oliverは彼の著書 『Programming Classics：Implementing the World's Best Algorithms』でそれを使用しました。



4. Jaro-Winklerアルゴリズムのソースは、たとえばここで見ることができます： Jaro-Winkler Distance



5. トライグラムインデックスまたは「タイプミスで検索」。 ハブラハブル



6. Jeannette "Angel" Devereu-カルトメディアフランチャイズ " Wing Commander "のキャラクター。コンピューター空間シミュレーター、戦略、その他の形式のゲーム、文学作品、 映画など 。 それは、フランスの姓の音を理解していないという事実だけのために、長い間、それが「デヴェロー」に聞こえると信じていたためです。 誤った翻訳の図は「耳で」ではなく「目で」です。



7.フォーマットされたSQLクエリの機能の基礎は、「SQLインジェクション：喜びの闘い」という記事からKamnev ArtemとMesilov Maximから正直に引用されています。 残念ながら、これらの人のサイトは最近読み込まれていませんが、記事のコピーはまだ見つかります。SQLインジェクション：喜びのための戦い （残念ながら、ソースなし）。 議論の余地のある機能を削除しました。 代わりに、配列を引数として渡す機能を追加しました。