ユーザーが入力した名前と住所に基づいて、連絡先に最も近い一致を返すアルゴリズムを作成する必要があります。会社名と住所を入力する方法はたくさんあるので、これらは両方とも厄介です。たとえば、次のようになります。
Company A, 123 Any Street Suite 200, Anytown, AK 99012
Comp. A, 123 Any St., Suite 200, Anytown, AK 99012
CA, 123 Any Street Ste 200, Anytown, AK 99012
名前でレーベンシュタイン距離を実行することを検討しましたが、名前を省略できるため、これは優れたツールではないようです。可能な限り多くの情報に一致するものを探しています。
私の最初の試みは、最初に郵便番号の最初の5桁で結果を制限し、次に他の情報に基づいて1つにフィルターをかけることでしたが、これを行うにはより標準的なアプローチが必要です。私は.NETで作業していますが、これを実現する方法についてのアイデアを得るために提供できるコードを調べます。
これがどのように達成されるかは正確にはわかりませんが、すべての主要な配送会社（FedEx、USPS、UPS）は、入力した住所をデータベースと照合し、正規化された形式に変換する方法を持っているようです。これは複数のWebサイトで発生しているので（Amazonが思い浮かびます）、この機能にはAPIがあると思いますが、どこを探すべきか、目的に適しているかどうかはわかりません。
ただ考えてみてください。
編集：USPSAPIを見つけました
アドレスの正規化、Metaphone、およびレーベンシュタイン距離を組み合わせて、この問題を解決しました。名前と住所は特性が異なるため、名前と住所を分ける必要があります。必要な手順は次のとおりです。
1) 郵便番号 (の最初の 6 文字) を使用して、一致するリストを絞り込みます。基本的には、2 つの文字列のレーベンシュタイン距離を計算し、最大で 1 または 2 の距離を持つものを選択する必要があります。検索を本当に高速化する必要がある場合は、郵便番号とその「レーベンシュタインの隣人」の表を潜在的に事前計算できます。
http://en.wikipedia.org/wiki/Levenshtein_distance
2) USPS の正式な接頭辞と接尾辞の略語のリストを使用して、すべての住所の略語を標準形式に変換します。これにより、次のステップの結果がより均一になります。
https://www.usps.com/send/official-abbreviations.htm
3) Methaphone アルゴリズムを使用して、アドレスを短いコードに変換します。これにより、最も一般的なスペルミスが解消されます。実装が単語以外のすべての文字を削除し、数値をそのまま渡し、複数の単語を処理できることを確認してください (各単語が単一のスペースで区切られていることを確認してください)。
http://en.wikipedia.org/wiki/Metaphone
4) Methaphone の結果が得られたら、レーベンシュタイン距離を使用してアドレス文字列を比較します。結果を長い文字列の文字数で割って、変更スコアのパーセンテージを計算します。
5) 手順 3 と 4 を繰り返しますが、アドレスの代わりに名前を使用します。
6) 次の式を使用して、各エントリのスコアを計算します: (住所の重み * アドレスのスコア) + (名前の重み * 名前のスコア)。より重要なことに基づいて重みを選択します。住所は .9 から始め (住所の方が具体的であるため)、名前は .1 から始めますが、重みはアプリケーションによって異なる場合があります。スコアが最も低いエントリを選択します。スコアが高すぎる場合 (たとえば .15 を超えると、一致がないと宣言できます)。
郵便番号を見つけるのはかなり明確なので、最初に郵便番号に基づいてフィルタリングするのが最も簡単だと思います。そこから、おそらく街や通りを抽出できます。名前を見つける方法はわかりませんが、（名前、住所）のペアのデータベースがすでにある場合は、名前を住所と照合することは可能です。
最初に、私はおそらく単語インデックス検索を行います。それは2つの段階を意味します：
オフライン段階：キーワードによってすべてのアドレスのインデックスを生成します。たとえば、「Company」、「A」、「123」はすべて、上記で指定したアドレスのキーワードになります。ステミングを行うことができます。つまり、「street」のような単語の場合は、インデックスに「st」という単語も追加します。
オンラインステージ：ユーザーが検索クエリを提供します。検索クエリをすべてのキーワードに分割し、データベース内の各キーワードに一致する可能性のあるものをすべて見つけます。各アドレスで一致したキーワードの数を集計します。次に、一致したキーワードの数で結果を並べ替えます。一致するものが多すぎない場合、これは非常に迅速に実行できるはずです。これは、ソートされたリストがいくつかマージおよびインクリメントされ、最後にソートが続くためです。
問題のドメインがわかっている場合は、アルゴリズムを特殊化して、ドメインに関する知識を使用できます。たとえば、前述の郵便番号フィルタリングなどです。
また、より良い答えを提供できるようにするために、SQLデータベースを使用していますか？キーワードインデックスをSQLデータベースに保存すると、データベースがすべての作業を実行するため、キーワードで検索するSQLクエリが非常に簡単になります。
名前だけにレーベンシュタインを使用する代わりに、連絡先の文字列表現全体で使用すると便利な場合があります。たとえば、最初の例から2番目の例までの距離は7、3番目の例までの距離は9です。文字列の長さが54、50、45であることを考えると、これは比較的便利で非常に単純な類似度の尺度のようです。
各住所の一般的な構造を確実に把握できる場合 (おそらく他の回答の提案によって)、最善の策は、USPS 認定を介してデータを実行することです (つまり、結果は信頼性が高く、正確であり、連邦法に準拠しています)。規格）住所確認サービス。
@RyanDelucchi、それは楽しい問題ですが、一度だけ解決してください。したがって、@SteveBering さん、USPS のガイドラインに従って、住所に基づいて重複にフラグを立てるリスト処理サービスに連絡先のリストを送信することをお勧めします。
私は住所確認の分野で働いているので、SmartyStreets (私が働いている) をお勧めします。SmartyStreets は、特定のニーズに対して最大の価値を提供します。ただし、基本的に同様のことを行う CASS 認定ベンダーがいくつかあります。
これが私がすることです。私はアルゴリズムを認識していないので、意味のあるものを使用しています。
その人は、名前、住所、都市名、州名、および郵便番号を提供すると想定しています。
郵便番号が 9 つの数字で提供されている場合、またはハイフンが含まれている場合は、5 つの数字に減らします。データベースを検索して、その郵便番号を持つすべての住所を探します。[クエリ 1] 次に、州の手紙をデータベースの住所と比較します。一致しない場合は、それをユーザーに伝えます。都市名も同様です。
私の理解では、通りの名前は数字ではなく、通りの家だけに数字が入っていました。さらに、ハウス番号は、ハウス番号またはスイート番号でない限り、通常は先頭にあります。
したがって、数字とその隣の次のスペースまたはコンマを検索するために正規表現を実行します。次に、ピリオド (.) を持たない、またはコンマで終わる最初の単語の位置を見つけます。通りの名前の一部があるので、以前にフェッチした行と比較するか、通りの名前が LIKE %streetName% になるようにクエリを変更します。
データベースには、ブロック上の家の開始番号と終了番号があると思います。指定された通りの番号がその通りにあるかどうかを確認するために、その通りの行をチェックします。ここまでで、表示する正しいデータがわかったので、別のテーブルでその番地に関連付けられている名前を調べることができます。なぜ比較したいのかわからない。住所が提供されていない人を見つけたい場合は、名前の比較にのみ使用してください。文字列の方法を比較するには、ここを参照してください。同様の文字列アルゴリズム
Dun & Bradstreet はこれを行います。それは本当に難しいので、彼らはお金を請求します。「標準」ソリューションはありません。ほとんどの場合、D&B のようなサービスを選ぶか、独自のサービスを作成するかを選択するのは苦痛です。