問題タブ [fuzzy-search]

さまざまなソースからの製品名（カメラ、ラップトップ、テレビなど）をデータベース内の正規名に自動的に一致させる必要があります。

たとえば、「Canon PowerShot a20IS」、「NEW powershot A20 IS from Canon」、「Digital Camera Canon PS A20IS」 は、すべて「CanonPowerShotA20IS」と一致する必要があります。私はいくつかのヒューリスティックを追加してレーベンシュタイン距離で作業しました（明白な一般的な単語を削除し、番号の変更により高いコストを割り当てるなど）。これはある程度機能しますが、残念ながら十分ではありません。

主な問題は、関連するキーワードを1文字だけ変更しても大きな違いが生じる可能性があることですが、関連するキーワードを特定するのは簡単ではありません。たとえば、次の3つの製品名を考えてみましょう
。LenovoT400
Lenovo R400
New Lenovo T-400、Core 2 Duo
最初の2つは、どの規格でもばかばかしいほど似た文字列です（この場合、soundexはTとRを区別するのに役立つかもしれませんが、名前は400Tと400Rも同様です）、1番目と3番目はストリングとして互いにかなり離れていますが、同じ製品です。

明らかに、マッチングアルゴリズムを100％正確にすることはできません。私の目標は、名前の約80％を高い信頼性で自動的にマッチングすることです。

任意のアイデアや参考文献は大歓迎です

通常提案されているもの (レーベンシュタイン距離、soundex など) よりも、可変長文字列でより良い結果をもたらす文字列類似性アルゴリズムを探しています。

例えば、

与えられた文字列 A: "Robert",

ストリング B: "Amy Robertson"

よりも良い一致だろう

文字列C：「リチャード」

また、できれば、このアルゴリズムは言語にとらわれないようにする必要があります (英語以外の言語でも機能します)。

Zend Lucene を使用して PHP Web サイトの検索機能を構築していますが、問題が発生しています。私の Web サイトはショップ ディレクター (そのようなもの) です。

たとえば、「FooBar」という名前のショップがありますが、訪問者が「Foo Bar」を検索しても結果がありません。また、お店の名前が「Foo Bar」で、訪問者が「FooBar」と検索しても何も見つかりません。

「foobar~」（あいまい検索）で検索してみましたが、「Foo Bar」という記事は見つかりませんでした。

インデックスを作成したり、クエリを作成したりする特別な方法はありますか?

あいまい文字列マッチングの分野は初めてです。

Bitapアルゴリズムの使用法を模索していますが、これまでのところ、パターンの長さが限られているために問題が発生しています。私はFlashを使用しており、32ビットの符号なし整数とIEEE-754倍精度浮動小数点数型を処理しています。これは最大53ビットを整数に使用できます。それでも、50文字より長いパターンを処理できるあいまいマッチングアルゴリズムが必要です。

Bitapアルゴリズムのウィキペディアのページにはlibbitapが記載されています。これは、アルゴリズムの無制限のパターン長の実装を示していると思われますが、そのソースからアイデアを得るのに苦労しています。

無制限の長さのパターンに対してBitapを一般化する方法、または干し草の山の提案された場所の近くで針のあいまい文字列マッチングを実行できる別のアルゴリズムについて何か提案がありますか？

カタログ番号から製品名へのマッピングがあります。

"warm cmfrter" のようなスペルミスのある混合名を検索する必要があります。

edit-distance (difflib) を使用するコードがありますが、おそらく 18000 個の名前には拡張できません。

私は Lucene で同様のことを達成しましたが、PyLuceneは Java のみをラップするため、エンド ユーザーへの展開が複雑になります。

通常、SQLite にはフルテキストやスコアリングがコンパイルされていません。

Xapian バインディングは C++ に似ており、ある程度の学習曲線があります。

Whooshはまだ十分に文書化されていませんが、悪用可能なスペルチェッカーが含まれています。

他には何があるの？

個人データなどを含むテーブルPersonsがあります。列はたくさんありますが、ここで興味深いのは次のaddressindexとおりです。したがって、「以下のように」2 人がいて、1 人が同じである場合、それらは重複している可能性が最も高いです。lastnamefirstnameaddressindexlastnamefirstnames

これらの重複をリストする方法が必要です。

すべての列で正確に一致する場合、これを行う方法はわかっていますが、(上記の例から) 次のような結果でトリックを実行するには、あいまい一致が必要です。

これをうまく解決するヒントはありますか？

約 500 万レコードの Postgres テーブルがあり、入力キーに最も近いものを見つけたいと考えています。pg_trgm モジュールでトライグラムを使用してみましたが、クエリごとに約 5 秒かかり、私のニーズには遅すぎます。

Postgres 内であいまい一致を行うより高速な方法はありますか?

提案と報酬システム用の SharePoint ポータルを開発しており、提案が重複していることを警告する必要があります。候補はフリー テキスト形式であるため、あいまい検索が必要です。「Damerau-Levenshtein アルゴリズム」があいまい検索を行うことは理解していますが、Sharepoint ポータルにどのように実装すればよいですか? Microsoft Search Server は役に立ちますか? はいの場合、どのように？

位置とサイズが最小値と最大値x、yおよびz座標で指定されている（主軸に平行であるため）多数の直方体があります。

たとえば、次の 3 つの直方体があるとします。

次にポイント (例: (25.3,10.2,90.65)) を指定した場合、自分がどの立方体にいるかをすばやく判断する方法はありますか?

• 明らかに、すべての直方体を反復処理することもできますが、潜在的に数百万の直方体が存在するため、単純な反復処理よりも高速に処理する必要があります (O(log n) またはそれ以上の値が望ましい)。

• これは「ファジー マッチング」タイプの問題のように思えます。Apache Luceneが範囲クエリをサポートしていることに気付きましたが、これは逆に機能するようです (点を含む立方体ではなく、立方体で点を見つける)。

• さらに複雑なことに、次元の数が 3 より大きくなる場合があります (20 までになる可能性があります)。つまり、立方体ではなく「超立方体」を探している可能性があります。)

ファジーがこれを表現する正しい方法かどうかわからないので、私がやりたいことを説明させてください。

多くの場合、ローカルSVN作業コピーの特定のディレクトリ内にあることがわかっているファイルを探しています。それらのファイルがどのディレクトリにあるかはわかりますが、正確なパスを考えたくない場合があります。異なるブランチにそれのいくつかのコピーである。たとえば、「trunk」ディレクトリの下のどこかに、その下の「interface」という名前のディレクトリにあることがわかっているファイル「eligibility.py」が必要だとします。

any-for-filesプロンプトで次のように入力できれば理想的です。

これに似たことができる方法はありますか？