Geekly Articles each Day

ファジー検索の実装



Webプロジェクトが何らかの方法でユーザーへのデータの検索と提供に関連している場合、おそらく検索文字列を実装するタスクに直面するでしょう。 同時に、何らかの理由でプロジェクトでGoogleやYandexなどのスマートサービステクノロジーを使用できない場合、部分的にまたは完全に独立して検索を実装する必要があります。 サブタスクの1つは、おそらくファジー検索の実装でしょう。これは、ユーザーがしばしば間違えて、正確な用語、名前、または名前を知らないことがあるためです。

この記事では、サイトedatuda.ruでの検索に使用されたファジー検索の可能な実装について説明します。

挑戦する
レストラン、カフェ、バー検索サービスの作成の一環として、ユーザーが施設の名前を表示できる検索バーを実装するタスクが発生しました。
タスクは次のように設定されました。
  1. 検索結果は、ドロップダウンリストの選択プロセスで表示されます。
  2. 検索では、ユーザーの考えられるエラーとタイプミスを考慮する必要があります（たとえば、マクドナルドはマクドナルドのように入力したいだけです）。
  3. 各機関に対して、多くの同義語を設定できる必要があります（たとえば、mcdonalds => makdak）。

アイテム1〜3の視覚表示：



したがって、おそらくクロップされたクエリフレーズを受け取ったら、事前にコンパイルされた辞書から書面で最も近いエントリを選択する必要があります。 実際、タスクは、最新の検索エンジンが実行できるタイプミスを修正することでした。 それを解決するための一般的な方法の1つ：
  1. n-gramインデックスの構築に基づく方法。
    素晴らしく、迅速かつ簡単な方法。
  2. 距離ベースの編集方法。
    おそらく、コンテキストを考慮しない最も正確な方法の1つです。
  3. 請求項1と請求項2の結合。
    大規模な辞書での検索を高速化するには、最初にセクション2の後続のアプリケーションでn-gramインデックスに基づいて単語のグループを選択するのが理にかなっています（ ZobelおよびDarthの「大規模な辞書での近似一致の検索」を参照）

habrには、テキストと辞書のあいまい検索に関する記事がありました。 パラグラフ1と2、特に、レーベンシュタインとダメラウ-レーベンシュタインの距離を素敵な写真で説明しています。 したがって、この記事ではこれらの方法の詳細な説明は提供しません。

検索の実装
私たちの場合、辞書は（たとえば検索エンジンのように）数千エントリほどの大きさではないため、n-gramインデックスを作成せずに編集距離に基づいた方法を使用することにしました。
編集距離を計算するための従来のアルゴリズムは、行の近接度を十分に評価しますが、キーボード上の文字に対応するキー間の距離や音への近接度など、文字に関する情報（等値または不等式を除く）は使用しません。
キー間の距離を考慮することは便利です。なぜなら、すばやく入力する場合、ミスのために多数のエラーが発生する一方で、ユーザーが誤って次のキーを押した可能性がより遠くのキーよりも高いからです。
音声規則を考慮することも重要です。 たとえば、外国の名前や肩書きの場合、ユーザーは単語の正確なスペルを知らないことが多いのですが、音を覚えています。
ZobelとDarthの研究では、「音声文字列照合：情報検索からの教訓」は、編集距離の計算と一連の音声規則（フレーズ「音声規則」は完全に正確ではない）を組み合わせた文字列比較方法を説明しています。 著者は、編集距離を計算するときに1つのグループの文字を置き換える「コスト」が、1つのグループに属さない文字を置き換える「コスト」よりも低いような文字で構成される複数の音声グループを特定しました。 このアイデアを使用しました。
基本アルゴリズムとして、Wagner-Fischerアルゴリズムを採用し、いくつかの修正を加えてDamerau-Levenshtein距離を検出しました。
  1. 基本的なアルゴリズムでは、すべての操作の「コスト」は1です。挿入および削除操作の「コスト」を2に設定し、交換操作を1に設定し、1つの文字を別の文字に置き換える操作は次のように計算されます：比較された文字に対応するキーが互いに隣接している場合キーボードまたは比較文字が1つの音声グループに属している場合、置換の「コスト」は1、それ以外の場合は2です。
  2. その結果、プレフィックス距離が返されます。 クエリ単語と辞書の単語のすべての接頭辞との間の最小距離。 これが必要な理由は 辞書形式と比較するクエリ単語は通常、切り捨てられます。 つまり ユーザーが「mcd」とディクショナリ「mcdonalds」を入力して比較することができます。この場合の「mcdonalds」はクエリと非常に正確に一致しますが、長い距離（7回の挿入操作）を取得できます。

上記の作業から音声グループを取りましたが、少し変更しました。


元の作品では、グループは元の英語の単語の音に基づいて構成されていたため、音訳されたロシア語のテキストで良い結果が得られるという保証はありません。 独自の観察に基づいて、小さな変更を加えました（たとえば、元の「fpv」グループから「p」を削除しました）。

C ++での実装の結果：
{{{ class EditDistance { public: int DamerauLevenshtein(const std::string& user_str, const std::string& dict_str) { size_t user_sz = user_str.size(); size_t dict_sz = dict_str.size(); for (size_t i = 0; i <= user_sz; ++i) { trace_[i][0] = i << 1; } for (size_t j = 1; j <= dict_sz; ++j) { trace_[0][j] = j << 1; } for (size_t j = 1; j <= dict_sz; ++j) { for (size_t i = 1; i <= user_sz; ++i) { //  ,    int rcost = ReplaceCost(user_str[i - 1], dict_str[j - 1]); int dist0 = trace_[i - 1][j] + 2; int dist1 = trace_[i][j - 1] + 2; int dist2 = trace_[i - 1][j - 1] + rcost; trace_[i][j] = std::min(dist0, std::min(dist1, dist2)); //   if (i > 1 && j > 1 && user_str[i - 1] == dict_str[j - 2] && user_str[i - 2] == dict_str[j - 1]) { trace_[i][j] = std::min(trace_[i][j], trace_[i - 2][j - 2] + 1); } } } //   //   int min_dist = trace_[user_sz][0]; for (size_t i = 1; i <= dict_sz; ++i) { if (trace_[user_sz][i] < min_dist) min_dist = trace_[user_sz][i]; } return min_dist; } private: const static size_t kMaxStrLength = 255; int trace_[kMaxStrLength + 1][kMaxStrLength + 1]; private: int ReplaceCost(unsigned char first, unsigned char second); } }}}


短い言葉で言えば、ユーザーは、原則として、長いもののような失敗をしないことに注意してください。 これを行うために、クエリ単語の長さに比例する単語間の最大許容距離のしきい値を作成します。
 {{{ const double kMaxDistGrad = 1 / 3.0; ... uint32_t dist = distance_.DamerauLevenshtein(word, dict_form); if (dist <= (word.size() * kMaxDistGrad)) { // ok } }}}


索引
機関のソースレコードを次の形式にします。
<メタデータ：ID、...> <機関名> <名前の同義語形式>
次に、インデックスは次のように表すことができます。

Source: https://habr.com/ru/post/J123320/

More articles:


All Articles