1

非リテラル比較に基づく高速な検索方法

私はかなり大きなデータセット、基本的にすべての文字列に対する小さな検索を開発しています。比較はリテラルであってはなりませんが、テーブル フィールド間の関係は十分に単純です。つまり、「filippo」、「philippo」、「filipo」などを関連付けることができる必要があります。

レビンスタイン距離 ( this、here、here ) に頻繁に出くわしますが、それが私の特定のケースで実用的かどうかはわかりません。

簡単に言うと、2 つのテーブルがあります。「検索キー」を含む小さなテーブルと、検索を実行する大規模なテーブルです。両方のテーブルには同じフィールドがあり、どちらも同じ「意味」を持っています。例えば

KEYS_TABLE
# | NAME  | MIDNAME | SURNAME | ADDRESS         | PHONE
1 | John  | Fake    | Doe     | Sesame St.      | 333-12-32
2 | Ralph | Stue    | Michel  | Bart. Ghost St. | 778-13000
...

と

SEARCH_TABLE
#   | NAME     | MIDNAME | SURNAME | ADDRESS         | PHONE
...
532 | Jhon     | F.      | Doe     | Sesame Street   | 3331232
...
999 | Richard  | Dalas   | Doe     | Sesame St.      | 333-12-32

私がやりたいのは、ある種のメトリックを取得するか、特定のレコードごとにランク付けし、特定の関連性を超えるKEYS_TABLEすべてのレコードをレポートするSEARCH_TABLEことです (メトリックまたは単に「KNN」のような方法で定義されます)。

KEYS_TABLExのすべての行のすべてのフィールドを計算する必要があるため、レビンスタイン距離は実用的ではないかもしれませんSEARCH_TABLE。SEARCH_TABLE約 4 億件のレコードがありKEYS_TABLE、100k から 1mil まで変化することを考えると、結果の数値は大きすぎます。

以前に両方のテーブルを充実させる方法、または検索を実行するためのより簡単な (安価な) 方法があることを望んでいました。

データを自由に変換することが許可されていることに言及する価値があります。たとえば、 、 に正規化しSt.、st特殊文字などを削除します。Streetst

私の選択肢は何ですか？

4

2 に答える 2

0

私が考えることができる1つのアプローチ（ヒューリスティック！）は次のとおりです。

テーブル内の元のフィールドに加えて、各フィールドには、何らかのステミングアルゴリズムによって取得された正規化された形式も格納されます。Java を使用している場合は、luceneがこのステップで役立つことがあります。EnglishAnalyzer

標準的な方法を使用して正確な比較table1を行い、候補リスト内の各エントリを検索します。正規化された形式が通常の形式と一致する共通のフィールドがある場合、エントリはエントリの候補になりますe2。これは、迅速な文字列検索を可能にするデータ構造を使用して効率的に行うことができます - これらはたくさんあります。table2e1table1

の各エントリについてe1、選択した正確なメトリックを使用して、リスト内の「最適な」候補を見つけます (たとえば、提案されたレネシュタイン距離)

table1で 2 つの要素が同じ要素にマップされていないことを確認するために、後処理を行うことがtable2問題になる場合があります。

于 2012-12-05T18:29:16.657 に答える
0

スペルミスの可能性に応じて、Soundex または Metaphone を検索に使用できる場合があります。

于 2012-12-06T01:04:03.540 に答える