問題タブ [fuzzy-search]

軽量のあいまいテキスト検索ライブラリを提案できますか?

私がやりたいことは、ユーザーが入力ミスのある検索語に対して正しいデータを見つけられるようにすることです。

Lucene のような全文検索エンジンを使用することもできますが、やり過ぎだと思います。

編集:
ここで質問をより明確にするために、そのライブラリの主なシナリオがあります:
文字列の大きなリストがあります。このリスト（MSVSのインテリセンスのようなもの）で検索できるようにしたいのですが、リストには存在しないがリストにある文字列に十分近い文字列でこのリストをフィルタリングできるはずです。
例：

• 赤
• 緑
• 青い

テキスト ボックスに「Gren」または「Geen」と入力すると、結果セットに「Green」が表示されます。

インデックス付きデータの主な言語は英語です。

Lucene はそのタスクに対して重すぎると思います。

更新：

条件に一致する製品が 1 つ見つかりました。シャッフルテキストです。
代替手段を知っていますか？

関連スレッドのこのコメントに従って、レーベンシュタイン距離ベースの方法がSoundexよりも優れている理由を知りたい.

ねえ、私はLevenshteinsアルゴリズムを使用して、ソース文字列とターゲット文字列の間の距離を取得しています。

また、0から1までの値を返すメソッドがあります。

しかし、これは私にとって十分ではありません。2つの文を一致させるためのより複雑な方法が必要だからです。

たとえば、いくつかの音楽に自動的にタグを付けたい、オリジナルの曲名を持っている、スーパー、クオリティ、2007、2008などの年などのゴミのある曲があります。また、一部のファイルにはhttp：//trashだけがあります。 .thash..song_name_mp3.mp3、その他は正常です。私は今よりも完璧に機能するアルゴリズムを作成したいと思っています。多分誰かが私を助けることができますか？

これが私の現在のアルゴリズムです：

これは正常に機能しますが、場合によっては、一致するはずの多くのタイトルが一致しないことがあります...ウェイトなどを操作するには、何らかの式が必要だと思いますが、1つは考えられません。

アイデア？提案？アルゴス？

ちなみに、私はすでにこのトピックを知っています（私の同僚はすでにそれを投稿していますが、この問題の適切な解決策を見つけることはできません。）： 近似文字列マッチングアルゴリズム

SSIS 2005/2008 は、ファジー ルックアップとグループ化を行います。T-SQL で同じことを行う機能はありますか?

100 万を超えるアイテム (潜在的にはそれ以上) を保持する文字列 (任意の長さ) のデータベースがあります。

ユーザーが指定した文字列をデータベース全体と比較し、存在する場合は同一の文字列を取得するか、最も近いあいまい一致 (60% 以上の類似性) を返す必要があります。検索時間は、理想的には 1 秒未満である必要があります。

私の考えは、長さに基づいてデータベースから候補を絞り込んだ後、各データベース文字列を検索文字列と比較するために編集距離を使用することです。

ただし、この操作を頻繁に実行する必要があるため、db 文字列のインデックスを構築してメモリに保持し、db を直接ではなくインデックスをクエリすることを考えています。

この問題に別の方法でアプローチする方法、またはメモリ内インデックスを構築する方法についてのアイデアはありますか?

あいまい文字列検索用の高性能 Java ライブラリを探しています。

同様の文字列、レーベンシュタイン距離、Daitch-Mokotoff Soundex、n-gram などを見つけるアルゴリズムは多数あります。

どのような Java 実装が存在しますか? それらの長所と短所は？私は Lucene を知っていますが、他のソリューションまたは Lucene が最適ですか?

私はこれらを見つけました、誰もそれらの経験がありますか？

• シムメトリクス
• NGramJ

この問題をどのように解決しますか？

あなたはブログのHTMLをスクレイピングしています。ブログのHTMLの一部はブログ投稿であり、一部は書式設定、サイドバーなどです。HTML内のどのテキストがどの投稿に属しているか（つまり、パーマリンク）を識別できるようにする必要があります。

私はあなたが何を考えているか知っています：あなたはただRSSを見て、HTMLを完全に無視することができます！ただし、RSSには非常に短い抜粋しか含まれていないか、興味のあるリンクが削除されていることがよくあります。同じページのHTMLとRSSを一緒に使用して、RSSの抜粋を本質的に無効にします。

RSSエントリは次のようになります。

HTMLのブログ投稿は次のようになります。

したがって、HTMLページには同じフィールドが含まれますが、パーマリンクの配置は事前にわかりません。フィールドは、ほとんどがHTMLと空白であるノイズテキストで区切られますが、「投稿者Johnny」などの追加のメタデータも含まれる可能性があります。 "または日付またはそのようなもの。以下で説明するように、テキストはHTMLとRSSでわずかに異なる場合もあります。

追加のルール/警告：

• タイトルは一意でない場合があります。これはあなたが思っているよりも頻繁に起こります。私が見た例：「月曜日のまとめ」、「TGIF」など。
• タイトルは空白のままにすることもできます。
• RSSの抜粋もオプションですが、少なくとも空白以外の抜粋または空白以外のタイトルが必要であると想定しています。
• RSSの抜粋には投稿コンテンツ全体が含まれている可能性がありますが、投稿本文の先頭の短い抜粋が含まれている可能性があります
• パーマリンクは一意である必要があり、HTMLとRSSの両方で同じである必要があると想定します。
• タイトルと抜粋および投稿の本文は、RSSとHTMLでわずかに異なる形式になっている場合があります。例えば：
  • RSSでは、タイトルまたは本文の内部のHTMLが削除されているか、HTMLページにHTMLが追加されているか（投稿本文の最初の文字を何かで囲むなど）、わずかに異なる形式になっている可能性があります。
  • テキストは、RSSではutf8であるのに対し、HTMLでは非ASCII文字は常にアンパサンドエンコーディングを使用してエンコードされるなど、わずかに異なる方法でエンコードされる場合があります。ただし、これは非ASCII文字がまれな英語のテキストであると想定してください。
  • 正しくエンコードされていないWindows-1252の恐ろしさがある可能性があります。これは、中引用符のような記号文字でよく発生します。ただし、ほとんどのテキストはASCIIであると想定しても問題ありません。
  • 特にタイトルでは、どちらの方向にもケースが折りたたまれている可能性があります。したがって、HTMLページではタイトルをすべて大文字にすることはできますが、RSSではできません。
• RSSフィードとHTMLページのエントリ数は同じであるとは想定されていません。古いエントリが多かれ少なかれある可能性があります。両方に表示される投稿のみを取得することを期待できます。
• RSSは遅れる可能性があります。RSSフィードにまだ表示されていない新しいエントリがHTMLページにある可能性があります。これは、RSSがFeedburnerを介してシンジケートされている場合に発生する可能性があります。繰り返しになりますが、RSSとHTMLの両方に表示される投稿のみを解決することが期待できます。
• 投稿の本文は非常に短くても長くてもかまいません。

100％の精度は制約ではありません。ただし、精度が高いほど優れています。

さて、あなたはどうしますか？

ユーザーは、会社名を含む大きな文字列をカット アンド ペーストしてインポートします。

会社名の既存の MYSQL データベースがあり、それぞれに一意の company_id があります。

文字列を解析して、ユーザーが入力した会社名のそれぞれにあいまい一致を割り当てられるようにしたいと考えています。

現在、単純な文字列マッチを行うだけでも遅いです。** Soundex のインデックス作成は高速になりますか? ユーザーが入力しているときに、ユーザーにいくつかのオプションを与えるにはどうすればよいですか? **

たとえば、誰かが次のように書いています。

この質問に似ていると思われる次のスレッドを見つけましたが、投稿者は承認しておらず、それらのユースケースが適用可能かどうかはわかりません:

大規模な文字列データベースで文字列の最もあいまいな一致を見つける方法

Java での不正確な会社名の照合

3 つのコンポーネントを含む非常に単純な SSIS パッケージがあります。

1. OLE DB ソース
2. あいまい検索
3. OLE DB 宛先

あいまい検索コンポーネントの詳細タブで、「検索ごとに出力する一致の最大数」を 1 から 2 に変更しました。

変更後にパッケージを実行すると、次のエラー メッセージが表示されます。

[OLE DB 宛先 [57]] エラー: SSIS エラー コード DTS_E_OLEDBERROR。OLE DB エラーが発生しました。エラー コード: 0x80004005。OLE DB レコードが利用可能です。ソース: "Microsoft SQL Native Client" Hresult: 0x80004005 説明: "リンク サーバー '(null)' の OLE DB プロバイダー 'STREAM' は、列 '[!BulkInsert]._Confidence' に対して無効なデータを返しました。"

数値を 1 に戻すと、再び機能します。OLE DB ソースには約 45000 行あり、ルックアップには約 580000 行あります。

この問題にさらに対処する方法がわからないので、助けていただければ幸いです。

ありがとうダニエル