高速類似文字検索：1億超レコード対応、検索漏れゼロ、類似度順複数リスト取得

類似文字検索アルゴリズム

32ビット版で2000万レコード、64ビット版で1億レコード超に対応。検索漏れはゼロ。一瞬で超高速検索。類似度の高い方から任意個数の結果を取得可能
岡崎直観氏の論文：集合間類似度に対する簡潔かつ高速な類似文字検索アルゴリズムに基づいている。 アルゴリズムは以下の野通り、
  1. 膨大な文字列データから3-gram統計を作成する
  2. 各文字列へユニークなidを割り振り3-gramからid(1つから数万件)への全リンクを高速検索できるデータ構造で保存する
  3. 検索文字列も3-gram化して、3-gramから、同じidへのリンクの多いものほど類似しているとして出力する
    4. この部分をまともに計算すると計算量が膨大となるため、高速化のための工夫が複数含まれている。詳細は上記の論文参照
実際に開発したものは岡崎直観氏の公開している高速類似文字検索プログラムとは２つの点で異なっている。
  1. １つは、元のテキストの3-gramを構築する際に、自社開発のn-gramデータベースライブラリを利用している点
    2. 文字認識ライブラリで、候補文字の選定に文字の連接頻度による予測を利用するためにに、すでに開発済みのn-gramライブラリがあった。そのライブラリを出発点に岡崎メソッドを組み込んでいる。
    そのため岡崎氏が公開している擬似コードとは、かなり異なったものになった。
  2. もう一つの違いは、各テキストに任意のデータレコードをリンクする機能がある点
    3. 具体的には、
上に戻る

類似文字検索用の辞書の作成

長尾真編「自然言語処理」岩波講座ソフトウェア科学15 1996の２章の記述に基づいたアルゴリズムでn-gramを求めている。書籍の入手が困難なので簡単に解説しておく。
以下のように処理を進める。
  1. テキストの正規化処理
    2. この際に、改行やタブコード等は、必要に応じて存在しない文字コードに変換するなり無視するなりしておく。
    1行ごとにつながらない別のテキストと考える場合（法人名、人名、住所のリスト）は、前後に適当な数の「存在しない文字コード」を補充しておくことも考えられる。
    これは、類似文字検索では3-gramデータを利用するので、1文字や2文字の法人名や人名にも対応できるための措置である。
    場合によっては、1バイト文字や3バイト文字を2バイト文字に正規化することもある。とりあえず各文字の先頭が分かれば良いので、この処理は必須ではない。
    最終的に対象テキスト全体がメモリ中に存在していれば良い。
  2. 全ての文字のアドレスを配列として取得
    3. 1億文字であれば1億個の配列となる。たとえば日本の法人名のテキスト全て(2023年時点)を対象とするのであれば7千万要素の配列となる。アドレスなので32ビット環境では280メガバイトの配列が必要となる。
    20億文字ある日本語ウィキペディアでも、64ビット環境ならば16ギガバイトの配列として処理対象とすることができる。
  3. 上記の配列をソートする
    4. 一瞬で処理する必要が無いならばクイックソートで十分。20億文字でも数分(並列クイックソートが使えるのであれば10秒程度)で処理することができる。
    リアルタイムで処理することが必要であれば、先頭文字のコードでグループに分割してからクイックソートすることで一瞬で処理することも可能である。
  4. n-gram統計をカウント
    5. 文字のアドレスは、テキストの末端まで達する半直線文字列の全文字のソート済みのアドレスとなっている。
    たとえば以下のようになっている。
    ...
コンピユーター.....
...
コンピューター.....
...
コンピューター.....
コンピュータアート....
...
コンピュータアイ....
コンピュータアカウント....
...
    全ての文字列は数百メガバイト長のテキスト末端まで至る半直線テキストとなっている。
    後続のテキストのn文字目まで調べれば同じかどうか、同じものがいくつあるかなどが全て調べられる。必要に応じてアルゴリズムを工夫することで高速化することが可能である。
  5. ファイルに保存
    6. 高速にランダムアクセスできるならば、どのような形式でも良い。
    n-gramの性質を調べるならばランダムアクセスに加えてシーケンシャルアクセスも可能なように考慮しておく。
    全てメモリ中にn-gram情報を読み込むのでは無いケースでも、(n-1)-gramまではメモリ中に読み込んでファイルアクセス数を減らすことができるようにした方が良い。
    頻度の大きいものだけメモリ中にキャッシュできるような工夫があればなお良い。
    もちろん、全データをメモリ中に読み込めるのであれば、そうした方が良い。
上に戻る

全法人マイナンバーを対象とした類似文字検索

法人マイナンバーデータは誰でもダウンロードができる。 以下のような法人名と郵便番号、住所のデータだけを使う。
...
釧路検察審査会 0850824 北海道釧路市柏木町４－７
...
一般社団法人日本色彩療法士協会 0030005 北海道札幌市白石区東札幌五条１丁目１番１号札幌市産業振興センター３階Ｃ７
...
有限会社アートロジック 2250002 神奈川県横浜市青葉区美しが丘２丁目１７番地２９
...
類似文字検索プログラムの利用目的に合致しないので、あらかじめ数百パターンの「独立行政法人」「株式会社」「（株）」等の法人種別名は取り除く。
「丁目」以降の番地、ビル名、部屋番号は分離する。「丁目」が付く町名があったりするため、ルールベースによる解析で「丁目」以降の番地部分を100%の精度で分離している。
...
釧路検察審査会 0850824 北海道釧路市柏木町 ４－７
...
日本色彩療法士協会 0030005 北海道札幌市白石区東札幌五条 １丁目１番１号 札幌市産業振興センター３階Ｃ７
...
アートロジック 2250002 神奈川県横浜市青葉区美しが丘 ２丁目１７番地２９
...
会社名が200文字以上あるような、ふざけて登録したとしか思えないようなレコードなど、明らかにおかしいレコードを取り除く必要もある。
いろいろなはずれデータ除去、正規化処理後に、前後に＄＄をつけた法人名から3-gramを作成している。
二文字の会社名はもちろん、「株式会社Ｘ」のように「株式会社」を除くと1文字になってしまうような会社も大量にあるので、上記の補完処理は必須となる。
最終的には、会社名から読みを取得、生成（別の会社名読みデータベースや mecab+neologd のような形態素解析ソフトを利用）して、
  1. 会社名を類似文字検索することで、郵便番号、住所、法人名読みを取得
  2. 会社住所を類似文字検索することで、郵便番号と法人名を取得
という検索処理が実行できるようにしている。
上に戻る

日本国内全住所を対象とした類似文字検索

全住所は、ＪＰ(日本郵便）が公開している郵便番号データベースを利用している。
上位システムでは、会社名ＤＢの住所から郵便番号を検索する機能も合わせて利用している。マイナンバー登録の際の住所には揺れが含まれているので検索の頑強性が高くなる。
郵便番号から住所の検索は、類似文字検索プログラムを使う必要は無い。通常の郵便番号による検索を行っている。
住所から郵便番号は、類似文字検索によって行っている。
構築は、会社名を対象とした類似文字検索と同じであるが、リンクレコードには郵便番号だけとなっている。
上に戻る