「ファジー正規表現」でアドレスを解析します

概要：自然言語表現の特定の辞書、特に都市の住所と比較するために書いたライブラリについて。

おじいちゃんの村へ

地理的な意味で、住所を記述する方法はいくつありますか？



タスクを単純化し、家番号、建物、土地、アパートなどのあらゆる種類の小さなものを破棄しても -そして同じ都市内で働く-通りの名前、広場、私道、路地などを書くためにいくつのオプションを思いつくことができますか？



簡単な例を挙げます。

ツヴェトチナヤ通り -「st。 「花」および「花通り」-さらに、「通り」はスキップできます（市内に花の広場がない場合）。「花」は、「花」または「花」と同様にエラーで記述できます-すべてそれは親指に見えます！



例はもっと複雑です：

第2馬軍通り -ここでは、詩人の魂に歩き回る場所があります。 数字は「2nd」または単に「2」と表現することも、「Second」という言葉で、または「Second」という略語で書くこともできます。回答者の約50％で「horse」と「army」の間にハイフンが発生します。 ヒープには、「馬軍」が長い間誰かに見え、「2 Konnoarm」に縮小されたことがわかります。 st。」



他の興味深い例は、「st。 セーラージェレズニャック」（または単に「ジェレズニャック」？）、「Pr。 モリサ・トレザ」（または「マリサ・テレサ」？）と同様に完全に叙事詩的な事件」 後半の3行目 "、" Rybatskoe村への道 "、" st。 イゾラ川の左岸」-私自身がメモリからそれらを正しく書き込めなかった場合はご容赦ください。

まあこれはビジネスの幸せです

想像してみてください。 アプリケーションを開発していること、これはとりわけ、すべての地理を「くし」にする（つまり、統一された外観に導く）必要があります。 2011年にこの問題に遭遇しました。住所を含む広告を印刷する前にプログラムで処理する必要がありました。



ビジネスの観点から、「コーミング」の必要性は、いくつかの理由で関連していました-同じ（ただし異なる表記）アドレスで複数の広告を発行しないか、罰金を得ることができるブラックリストに登録されたアドレスで広告を発行しない（オブジェクトなど）司法調査などが行われている不動産）



さらに、たとえば、フラワーストリートでは、サンクトペテルブルクのさまざまな地域で6人を数えました。 そのため、指定されたエリアにあるかどうかを確認し、そうでない場合は近くの道路を検索するために、通りを整理する必要がありました。



このタスクが私の手に渡る前に、同じ目的のための古いアプリケーションは、特別な人-オペレーター-のサービスを使用しました。オペレーターは数時間にわたって約30,000行を通過し、彼の裁量で修正しました。 いくつかの理由であまり便利ではありませんでした。 オペレーターがおかしな癖を持っていることを含めて-知らなかった通りの90％をKolpinoに送信します。 その結果、保存された辞書ファイルを確認したところ、他のすべてのエリアを合わせたよりもコルピノ地区に多くの道路が見つかりました。

...そしてプログラマーも幸せです

以前のバージョンのアプリケーションがオペレーターのサービスを使用したのはなぜですか？



ソフトウェアがアドレスを処理するには、いくつかの明白なトリックが必要であると推測するのは簡単です。 上司や同僚から聞いた興味深い提案の中には次のものがあります。

• ANTLRが必要です-機械語用であり、過度の自由、面白いタイプミスなどを許可しないことを説明する必要がありました。
• yuzay regexps-略語「Tsvetochnaya Street」のすべての種類のタイプミスの正規表現を作成する提案は、このベンチャーの作者にすべての失敗を示しました。
• ニューラルネットワーク-このような明るいアイデアの著者は、残念ながら、ニューラルネットワークの使用がどのように提案されているかを正確に説明できませんでした。 私の推定では、出力を持つ都市のすべての可能な地名と入力を持つ入力行のすべての文字（またはすべてのビット）を作成すると、アイデアはおそらく成功します-訓練のためだけに想像できない数のオプション（まあ、時間）がかかります。

実験とアプローチ

適切なアドバイスを見つけるために必死、私は実験し始めました。 ファジィ文字列比較アルゴリズムについてウィキペディアで読みました。 やってみた 確かに、単語と単語を比較するために、これは悪くありません。



しかし、「st。 宮殿「と」pl。 宮殿-ここでは、「y」を「p」に置き換えるのはタイプミスではありませんが、アルゴリズムの観点からは、「Palace」を「Door」に置き換えるのと同じ重さです。



さて、行を単語に分割し（スペースなど）、それらのタイプミスを個別に計算してから、平均値のようなものを定義します。または、各単語の最大誤差を誤差の推定値とします。



このアイデアはすでに興味深いものになりました。 しかし、略語の問題、単語の並べ替え、オプションの単語の省略（「Aleksandr Matrosov Street」-「Aleksandra」は何かを見逃す可能性が高い）-彼女はまだ解決しませんでした。



考え直すことなく、これらのルールを記述するための「メタ言語」を作成することにしました。 何が起こったのか、「Java用のファジー正規表現解析ライブラリ」と呼びました。



特定の式との「調整」機能に加えて、式の一部を直接置換するためのルールを正確に記述できると便利であることがわかりました。

簡単な説明

言語の構文は、括弧に対する私の大きな愛情を示しています。 式と部分式は角かっこで囲まれ、式のタイプは左角かっこに続く文字によって決まります。 読みやすくするために、丸括弧、角括弧、および中括弧を使用できます。主なことは、開き括弧と閉じ括弧がペアで一致することです。



（=通り、花）



記号「=」は、単語が指定された順序で、または逆に存在する必要があることを意味します。 この表現は、「Flower Street」または「Flower Street」のいずれかに対応します。



そして、はい、許容されるタイプミスの数は、比較のためにオブジェクトを作成するときのしきい値によって設定されます。デフォルトでは75％で、「Tsvyatochnaya」や「Ulitsa Tsvitoshnaya」までスキップできます。



（バラク、（？フセイン）、オバマ、（？2番目））



特殊文字を含まない括弧内のコンマで区切られた単語は、単語チェーンがこの順序で期待されることを意味します。 しかし、記号「？」で括弧で囲まれた式 オプションの部分、つまり 存在しない場合はスキップされ、エラーの計算には影響しません。 この場合、バラク・フセイン・オバマ、バラク・オバマII、さらにはバラック・アバマも完全に認められます。



（^（ウラジミール、レーニン）、（ニキータ、フルシチョフ）、（カール、マルクス））



記号「^」は、リストされた部分式の1つを選択することを意味します。この場合、式はリストされた3つの数字のいずれかと比較できますが、「ウラジミールマルクス」と「ニキータレーニン」は機能しません。



他の表現があります-数値の範囲との和解（あいまい比較を適用するのは不便です）、明確な正規表現との和解（予期しないことですが、役に立つかもしれません）-略語と和解する可能性もあります（「*」記号を使用）名前付きグループをキャプチャしてさらに確認するか、置換として使用します。これはすべてドキュメントで説明しました。



置換機能は大きな式に関連するようになります。簡潔で関連する例を挙げるのは困難ですが、試してください：



[^（（^ Vlad *、Vladimir、B）| Vova）〜A | Dear_ $ A、（（^ Al *、Alexander、Sasha）| Sasha）〜B | Nasty_ $ B]〜C | Hello_ $ C



見た目はかさばっていますが、本質はシンプルです-さまざまなスタイルの「Vladimir」という名前は「Hello Dear Vova」に置き換えられ、Alexanderのさまざまなバージョンが異なって歓迎されます。 置換が指定されていないフラグメントは、パターン自体で置換する必要があります（したがって、たとえば、「Vova」の置換ではない場合、「Vlodimer」は「Vladimir」に置換されます）。

おわりに

市内の18地区の街路用にコンパイルした式（合計18の式）は130キロバイトのファイルに収まります（ただし、インデントやその他のフォーマット要素を含む）。辞書を作成するのに約2週間かかりました。 後に、この地域の集落のリストに同様の何かを作成する必要がありました。 このスパムをここに投稿しようとしていないことをご容赦いただければ幸いです。代わりに、国名の解析に使用される表現の下に追加します。



ライブラリは不安定なロールを行っています。 問題をかなり狭い範囲で解決します（自然言語処理の分野のその他の多くのタスクでは適合しません）。 数年の間、私は約1000のダウンロードを見ています。 5人が手紙と質問に答えました。 英語の場合、ロシア語と同じ形式のあいまいな比較はあまり効果的ではないことに注意してください（誤字に対しては効果的ですが、英語では単語の発音が発音とは異なるため、発音エラーには効果的ではありません）



プリミティブアルゴリズムを書き換えることが計画されていました-ターミナルのオプション要素には不愉快な欠点があり、プログラムで式を接着することは不可能になりました-しかし、私は新しい仕事の場所に行き、このタスク（バージョン2.0リリース）は深い「todo」になりました。プロジェクトをリファクタリングできます（このプロジェクトは、私のJavaキャリアの最初に生まれました）。 自分の好みに合わせてこのビジネスを続けたいと思っている人がいるなら、私は嬉しいだけです！

参照資料

Java用のファジー正規表現は、実際には私のライブラリです。



Javadocs-「ファジー正規表現」の言語のドキュメントと詳細な説明



TREはファジー比較の可能性がある別の正規表現ライブラリ（C）です。使用方法については考えていませんでした。Javaバージョンがなく、置換が必要でした。 その中の比較エラーも異なる方法で評価されますが、他のタスクでは役立ちます。



Damero-Levenshteinは、式内の単一の単語を比較するために内部で使用した、人気のある単純なファジー比較アルゴリズムです。

約束された例

国を「とかす」表現の例-ロシア国外の不動産広告に使用されました。 私はそれを選んだのは、それが都市の地名の表現よりも幾分単純であり、同時に同様の目的で「そのまま」使用できるからです。 （嫌に見えないように短縮されていますが、完全版はこちらから入手できます ）。

 （^
    アブハジア、オーストラリア、オーストリア、アゼルバイジャン、アルバニア、アルジェリア、アンギラ、
    アンゴラ、アンドラ、アルゼンチン、アルメニア、アルバ、アフガニスタン、バハマ、
    バングラデシュ、バルバドス、バーレーン、ベリーズ、ベルギー、ベナン、バミューダ、
 // ...
    フィジー、フィリピン、フィンランド、フランス、クロアチア、チャド、モンテネグロ、
    チェコ共和国、チリ、スイス、スウェーデン、スバールバル諸島、エクアドル、エリトリア、エストニア、
    エチオピア、ジャマイカ、日本、
     [^（Connected *、State *、（？Amer *））、America、USA、USA] |アメリカ合衆国、
 // ...
     [^コモロ、（コモロ*、（@ ISLAND））] |コモロ、
     [^コンゴ、ブラザビル、（（@ REPUB）、コンゴ）] |コンゴ共和国、
     [^ Zaire、DRC、（{^ DR、（Democre *、（@ REPUB））}、Congo）] | DR_Congo、
 // ...
     [^ビルマ、ミャンマー] |ミャンマー、
     [（@ISLAND）、メイン] |マン島、
     [ナゴルノ*、（？-）、カラ*、（？@ REPUB）] |ナゴルノ・カラバフ共和国、
     [^オランダ、オランダ] |オランダ、
 // ...
     [ゆう*、オセチア] | South_Ossetia、
     [^南アフリカ、{（^南アフリカ*、{南*、（？-）、Afr *}）、（@ REPUB）}] |南アフリカ共和国、
     [ユー*、スーダン] | South_Sudan
 ）

 ::島（^島*、{o、-、in *}）
 :: REPUB（^ p、rep、rep * *）