20

私はその分野に慣れていないので、最先端の技術とは何か、それについてどこで読めるのか、ほとんど疑問に思っています。

キー/値ストアがあり、距離(key1,key2) が何らかの形で定義されていると仮定しましょう (それがメトリックである必要があるかどうか、つまり、三角形の不等式が常に保持される必要があるかどうかはわかりません)。

私が欲しいのは主に、検索キーまでの特定の距離までのキーを持つすべてのアイテムを返す検索（キー）関数です。おそらく、その距離制限は構成可能です。たぶん、これも単なる怠惰なイテレータです。おそらく、カウント制限があり、アイテム (キー、値) が返されるセットの確率 P で、P = 1/距離 (キー、検索キー) 程度 (つまり、完全な一致は確かにセット内で、少なくとも高い確率でほぼ一致します)。

アプリケーションの例として、 MusicBrainzでの指紋照合があります。彼らはAcoustIdフィンガープリントを使用し、この比較関数を定義しています。彼らは PostgreSQL GIN インデックスを使用しており、(acoustid-server コードを完全には理解していない/読んでいませんが) GIN 部​​分一致アルゴリズムを使用していると思いますが、それが私が求めたものであり、それがどのように機能するかについては完全には理解していません。

テキストについては、これまでのところ、発音に基づいて単語を単純化する音声アルゴリズムを使用することがわかっています。例はこちらです。これは主に、検索スペースをより小さなスペースに分割するためです。ただし、これにはいくつかの制限があります。たとえば、狭いスペースでも完全に一致する必要があります。

とにかく、それが存在する場合、私はより一般的な解決策も探しています。

4

3 に答える 3

15

(高速な) 一般的なソリューションはありません。アプリケーションごとに異なるアプローチが必要になります。

2 つの例のどちらも、実際には従来の最近傍検索を行いません。AcoustID (私は作成者です) は完全に一致するものを探しているだけですが、いくつかのハッシュが一致することを期待して、非常に多くのハッシュを検索します。音声検索の例では、metaphone を使用して単語を音声表現に変換し、完全一致のみを探しています。

大量のデータがある場合、現実的にできることは巨大なハッシュ テーブルを使用した正確な検索だけであることがわかります。問題は、あいまい一致を完全一致検索に変換する方法になります。

一般的なアプローチは、スマート ハッシュ メソッドでローカリティ センシティブ ハッシュ(LSH) を使用することですが、2 つの例でわかるように、さらに単純なアプローチで回避できる場合もあります。

ところで、特にテキスト検索を探しているのですが、入力をNグラムに分割してインデックスを付ける最も簡単な方法です。距離関数がどのように定義されているかによっては、あまり作業をしなくても適切な候補が一致する可能性があります。

于 2012-11-23T09:00:05.763 に答える
8

FLANN Fastapproximate Nearest Neighborsをご覧になることをお勧めします。ビッグ データのあいまい検索は、近似最近傍としても知られています。

このライブラリは、ユークリッド、ハミングなどのさまざまなメトリックと、LSH または k-means などのさまざまなクラスタリング方法を提供します。

検索は常に 2 段階で行われます。最初にシステムにデータを供給してアルゴリズムをトレーニングしますが、データによっては時間がかかる可能性があります。ただし、LSH を使用して、1 分もかからずに 1,300 万のデータを正常にクラスター化しました。

次に、非常に高速な検索フェーズが始まります。最大距離および/または近傍の最大数を指定できます。

Lukas が言ったように、優れた一般的な解決策はありません。各ドメインには、使用するデータの内部プロパティを使用して、高速化またはより良い方法を見つけるためのトリックがあります。

Shazam は、幾何学的なプロジェクションを使用した特別な手法を使用して、曲をすばやく見つけます。コンピュータ ビジョンでは、もともとテキスト検索で登場した BOW: Bag of words をよく使用します。

データをグラフとして見ることができる場合、たとえばスペクトル グラフ理論を使用して近似マッチングを行う方法は他にもあります。

我々に教えてください。

于 2012-11-23T09:23:17.653 に答える