アドレス一致キーアルゴリズム

https://stackoverflow.com/questions/824588

05-07-2019
|

質問

2つの別々のテーブルにアドレスのリストがありますが、それらは一致する必要があるため少しずれています。たとえば、同じ住所を複数の方法で入力できます。

110 Test St
110 Test St。
110テストストリート

単純ではありますが、より複雑なシーンの状況を想像できます。上記のアドレスをキーとして照合できる単純なアルゴリズムを開発しようとしています。

たとえば。キーは「11TEST」です。 -110の最初の2つ、Testの最初の2つ、Street Variantの最初の2つ。完全一致キーには郵便番号の最初の5つも含まれるため、上記の例では、完全キーは「11TEST44680」のようになります。

これを開発する際の考慮事項として検討できる、効果的なアルゴリズムまたはリソースのアイデアを探しています。アイデアは、擬似コードまたは選択した言語で作成できます。

私たちは、米国の住所のみに関心があります。実際、オハイオ州とミシガン州の250の郵便番号の住所のみを調べています。また、費用対効果の高いソリューションのアイデアを受け入れますが、郵便ソフトウェアにはアクセスできません（基本的には1回限りの使用になります）。これは政府のソースからのデータの最初のダンプであるため、アプリケーションを構築する際にユーザーがそれをきれいにする方法の提案は役立ちますが、可能な限り最高。

解決

私たちが話しているのと同様のアルゴリズムに取り組んでいます。カナダ、アメリカ、メキシコ、イギリスの住所を処理するまでに処理するはずです。私が直面している問題は、3フィールドのプレーンテキスト形式でデータベースにあることです（は良いアイデアだと思った人は誰でも私見するべきです）。、大容量の受信者、複数の国、州と州と郡、郵便番号と郵便番号、つづりの間違いは簡単な作業ではありません。

つづりの間違いだけで、特にフランス語の名前を使用している国に行く場合、Saint、Saint、St、Ste、Saints、Saintes、Sts、Stes、Grand、Grande、Grands、Grandes、ピリオドの有無にかかわらず、小さな偉業でしたまたは名前の大部分へのハイフネーションは、パフォーマンスの問題の終わりを引き起こしません-特にStが聖または通りを意味する可能性があり、正しいコンテキストで入力されている場合とされていない場合（つまり、女性対男性）。住所の大部分は正しく入力されているが、州または郵便番号が間違っている場合はどうなりますか？

検索を開始する場所の1つは、 Levenstein Distance Algorithm スペルミスの大部分を排除するのに本当に役立つことがわかった。その後、ほとんどの場合、キーワードを検索し、郵便データベースと比較します。

これを行うためのツールを現在開発している人との共同作業に本当に興味があります。おそらく、共通の解決策を互いに助け合うことができます。私はすでにその方法の一部であり、これまでに言及したすべての問題を克服しました。同じ問題に取り組んでいる他の人がいると、アイデアを跳ね返すのに本当に役立ちます。

乾杯- [afsinc dot caのベン]

他のヒント

開発するのではなく、ここで説明した多くの技術を使用する市販の製品を使用する場合は、 http://www.melissadata.com/dqt/matchup-api.htm

免責事項：私は会社の発展と仕事に役割を果たしました。

英国では次を使用します：

家の名前または番号（名前にはアパートブロックのフラット番号が含まれます）
郵便番号

確かに郵便番号を使用する必要がありますが、米国では、郵便番号が英国の郵便番号に比べて非常に広い範囲をカバーしていると思います。したがって、通りと都市を使用する必要があります。

この例では、11番地のテストストリート、110番地から119番地のテストストリートなどを区別しません。

あなたの会社が住所検索システムにアクセスできる場合は、それを介してすべてのデータを実行し、一貫性のある形式でデータを取得します。おそらく、照合に使用できる住所キーを使用します。

これをクラックする場合、事前に定義された操作の順序を使用して、各アドレス文字列をツリーに変換します。

たとえば110 Test Street Apt 3.どこでもカリフォルニア90210 =＆gt;

住所のタイプを取得します。たとえば、ストリートの住所には、田舎のルートの住所とは異なる形式があり、これは国によって異なります。
これが通りの住所であることを前提に、通りのタイプを表す文字列を取得し、それを列挙型（eBoulevard、eRoadなど）に変換します
これが番地であることを前提に、番地を引き出します（小文字で保存）
これが番地である場合、番地を引き出します

   eStreet  //1.an enum of possible address types eg. eStreet, eRuralRoute,...
      |
   eStreet        //2.an enum of street types eg. eStreet, eBlvd, eWay,...
   /   |   \

名前番号Apt | | | テスト110 3

たとえばRR＃3どこでもカリフォルニア90210 =＆gt;

住所のタイプを取得：田舎のルート
これが地方のルートアドレスである場合、ルート番号を取得します
```
   eRuralRoute 
      |
      3
```

国の州および郵便番号の情報についても同様の操作を行う必要があります。

次に、結果のツリーを比較します。

これにより、比較が非常に簡単になりますが、ツリーを生成するコードは非常に注意が必要です。数千、数千のアドレスで、そのくだらないものをテストしたいと思うでしょう。関心のある米国の住所のみである場合、問題はより単純です。すでに述べた英国の住所はかなり異なっており、カナダの住所にはフランス語が含まれている場合があります（例：Place D'Arms、Rue Laurentなど）

あなたの会社が独自のアドレス正規化ツールを作成するのが費用効果が高い場合は、 USPSアドレス標準。または、アドレスを正規化、修正、および検証するためのサーバー側ツールとWebサービスを提供するベンダーが多数あります。

私の会社では、この目的のために AccuMail Gold を使用しています。単に標準化するだけではありません。住所を修正してください。社内でツールを開発するための1週間分の給与のコストを考慮した場合、市販の製品を購入する選択は明らかでした。

既存のシステムを使用することを選択しなかった場合、1つのアイデアは以下を実行することです：

住所行から数字を抽出する
一般的な通りの単語を空白に置き換えます
一致文字列を作成

ie：＆quot; 555 Canal Street＆quot;：

抽出番号は「555」を返します。 +＆quot;キャナルストリート＆quot;
ストリートの単語を置換すると「555」が得られます。 +＆quot;運河＆quot;
一致文字列を作成すると、「555Canal」が得られます

＆quot; Canal st 555＆quot;同じ一致文字列が返されます。

ストリートワードとは、「ストリート」の単語と略語を意味します。たとえば、「st」、「st。」、「blv」、「ave」、「avenue」などはすべて文字列から削除されます。

数字を抽出して文字列から分離することにより、数字が最初か最後かは関係ありません。

プライマリキーのIDを使用、これは常に一意であり、後で重複を簡単にマージできます。

ユーザーインターフェイスで適切なデータ入力を強制します。各コンポーネントを独自のテキストボックスに入力させます。家番号は独自のボックスに、通りの名前は独自のボックスに、都市は独自のボックスに、選択リストの州などに入力されます。これにより、一致を簡単に検索できます

2つのプロセスを「保存」する

最初の保存後、検索を実行して一致を検索し、可能な一致のリストと新しい一致を提示します。
新しいIDを選択した後、既存のIDを選択してそのIDを使用する場合は保存します

データを消去します。＆quot; street＆quot;、＆quot; st＆quot;、＆quot; drive＆quot;などを削除して、FKを使用して適切な略語を含むテーブルにStreetType char（1）として保存し、ストリートを構築できるようにします。

SOUNDEXとDIFFERENCEを調べる

私はmailinigリストを管理する大企業で働いていましたが、自動的にそれをしようとはしませんでした。重複が発生したときに手動で重複をマージし、PKを介して値をリップルできるように、マージ機能を計画します。

GoogleマップAPIを調べて、アドレスを渡して一致を取得できるかどうかを確認します。私はそれをよく知らない、これは単なる推測である。

ライセンス： CC-BY-SA と帰属

所属していません StackOverflow