[解決済み] Javascriptのファジー検索が意味をなす

ですから、私が探しているもの (そして、存在しない場合は作成します) は、次のようなことを行うライブラリです。

• 異なるテキスト操作の重み付け
• 各操作が単語内のどこに現れるかによって異なる重み付けをする（初期の操作は後期の操作よりもコストが高い）
• 関連性でソートされた結果リストを返す

誰かこのようなものに出会ったことがありますか？私は、StackOverflow がソフトウェアの推奨事項を尋ねる場所ではないことを理解していますが、上記の暗黙の了解 (もうありません!) は、私がこれを正しい方法で考えているかどうかということです。

編集

を見つけたので 良い論文(pdf) を見つけました。いくつかのメモと抜粋です。

アフィン編集距離関数は、挿入または削除のシーケンスに比較的低いコストを割り当てます。

Monger-Elkan距離関数 (Monge & Elkan 1996) は、Smith-Waterman距離関数 (Durban et al. 1998) を特定のコストパラメータでアフィン変換したものです。

については スミス-ウォーターマン距離 (ウィキペディア) スミス-ウォーターマン アルゴリズムは、配列全体を見るのではなく、すべての可能な長さのセグメントを比較し、類似度測定を最適化するものです。

編集距離モデルに基づかない、よく似た指標として Jaro メトリック (Jaro 1995; 1989; Winkler 1999). レコード リンクの文献では、2 つの文字列間の共通文字の数と順序に基づくこの方法の変種を使用して、良い結果が得られています。

Winkler (1999)によるこの変形はまた、最も長い共通の接頭辞の長さPを使用します。

(主に短い文字列のために用意されたようです)

テキスト補完の目的では、Monger-Elkan と Jaro-Winkler のアプローチが最も理にかなっていると思われます。Jaro メトリックへの Winkler の追加は、効果的に単語の先頭をより重く評価します。また、Monger-Elkanのアフィン的側面は、単語を補完する必要性（これは単に一連の追加である）が、あまり大きく不利にならないことを意味します。

結論

TFIDF ランキングはいくつかのトークンベースの距離メトリックの中で最も良い結果を示した。 また、MongeとElkanによって提案された調整されたアフィンギャップ編集距離メトリックは、いくつかの文字列編集距離メトリックの中で最も良い結果を示した。 文字列編集距離メトリクスの中で最もよい結果を示した。意外にも優れた距離 Jaroによって提案され，後にWinklerによって拡張された高速な発見的スキームである． この方式はMonge-Elkan方式とほぼ同様に機能するが は1桁以上速い。 TFIDF法とJaro-Winkler法を組み合わせる簡単な方法は Jaro-Winklerを組み合わせる簡単な方法の1つは、TFIDFで使われる厳密なトークン照合を TFIDFで用いるトークン照合をJaro-Winkler方式に基づく近似的なトークン照合に置き換えることである。 ウィンクラー方式に基づく近似的なトークン・マッチに置き換えることである。この組み合わせは、平均してJaro-WinklerとTFIDFのどちらよりもわずかに性能が良く、時にははるかに性能が良くなることもある。また、この論文で検討したいくつかの最良のメトリクスの学習された組み合わせに近い性能を持つ。 この論文で検討した

どのように解決するのですか？

いい質問ですね。しかし、私の考えでは、Levenshtein-Demerau を修正しようとするよりも、別のアルゴリズムを試すか、2 つのアルゴリズムからの結果を組み合わせたり、重み付けしたりするほうがよいかもしれません。

Levenshtein-Demerau は、"starting prefix" への完全一致または近似一致を特に重視しませんが、あなたの明らかなユーザーの期待には重みを与えるだろうと思います。

私は "better than Levenshtein" で検索し、とりわけこれを見つけました。

http://www.joyofdata.de/blog/comparison-of-string-distance-algorithms/

これは、多くの文字列の距離について言及しています。あなたの要件に特に関連するように見えた 3 つは、次のとおりです。

1. Longest Common Substringの距離。 結果として得られる部分文字列が同一になるまで、両方の文字列から削除されなければならない記号の最小数。

2. q-gram距離。 両文字列のN-gramベクトル間の差の絶対値の和。

3. Jaccard距離です。 共有N-gramと全観測N-gramの商を1minで表す。

多分、Levenshteinで、これらのメトリックの重み付けされた組み合わせ（または最小値）を使用することができます -- 共通の部分文字列、共通のN-gramまたはJaccardはすべて強く好まれます。 類似 文字列を強く好みます -- あるいは Jaccard だけを使ってみるのもいいかもしれません。

リスト/データベースのサイズによりますが、これらのアルゴリズムは中程度に高価になることがあります。私が実装したファジー検索では、設定可能な数の N-gram を DB からの検索キーとして使用し、それらを優先順位でソートするために、高価な文字列距離測定を実行しました。

SQL でのファジー文字列検索について、いくつかのメモを書きました。参照してください。

• http://literatejava.com/sql/fuzzy-string-search-sql/