JP7601220B2 - 名称データ対応付け装置、名称データ対応付け方法及び名称データ対応付けプログラム - Google Patents

Description

この発明の実施形態は、名称データ対応付け装置、名称データ対応付け方法及び名称データ対応付けプログラムに関する。

データベースを用いた業務には、異なる管理下にあるデータベースを統合し、格納されていた名称データを横並びで使用することで、より多角的・包括的な分析を行うことがある。そのためには、統合するデータベースの間で同一の事柄を表している名称データに対し、同一の識別情報を付与するなどして、名称データを統合する、所謂「名寄せ」という作業が必要になる。

しかしながら、名称データの入力方法は、データベースの管理元に依る。そのため、統合するデータベースの間で同一の事柄を表しているにもかかわらず、その表記が異なるという状況（表記ゆれ）はしばしば存在する。表記ゆれを含むデータベースを統合してしまうと、前述のような分析を行う際に、一つの事柄に関連する情報が表記ゆれを起こした部分だけ不足してしまう事態が発生してしまう。

このような表記ゆれに対処する技術として、非特許文献１及び非特許文献２は、検索対象の文字列同士の類似度を定量的に計算することで、最も似ている文字列を検索する手法を提案している。また、非特許文献３は、検索用の辞書を作成することで正確且つ効率良く同一の事柄を表す文字列を探し出す方法を提案している。また、特許文献１は、名寄せをしたいデータの周辺情報を用いた紐づけ方法を開示している。

中川 裕志, 他, 「出現頻度と連接頻度に基づく専門用語抽出」, 自然言語処理, 2003, 10巻, 1号, p.27-45 田淵裕章, 他, 「N-gram に基づく用例対訳検索手法」, 信学技報, 人工知能と知識処理研究会, Vol.108, No.441, pp.43-48, 2009. Surajit Chaudhuri, Venkatesh Ganti, and Dong Xin. 2009. "Mining document collections to facilitate accurate approximate entity matching". Proc. VLDB Endow. 2, 1 (August 2009), 395-406. DOI: https://doi.org/10.14778/1687627.1687673

日本国特開２０２０－１２３２１０号公報

表記のゆれ方には、登録データ名を省略した表記と、使用者同士でのローカルルールに基づく呼び名（通称）による表記と、が存在する。

非特許文献１及び２に開示されているような手法は、前者の省略表記のみが表記ゆれとして存在する場合には、ポピュラー且つ有効な手段である。しかしながら、後者の通称表記が混在している状況下では、各通称に対してその通称と文字列的に類似した名称が紐付けられるため、誤った結果を提示する可能性が高い。なぜならば、通称表記は、本来紐付けられるべき名称と著しくかけ離れているケースが多いためである。

また、前者の省略表記のみを扱う場合であっても、非特許文献１及び２に開示の手法は、日本語に対して使用されることを想定して作られているので、技術の適用範囲が限定的である。日本語における省略表記の特徴と他言語における特徴は全てが一致するわけではないので、非特許文献１及び２に開示の手法が、他言語で入力された名称データに対して問題なく適用可能とは限らないためである。

よって、通称表記に対しては、非特許文献３に開示されているような、辞書を作成することが最適な手法だと考えられている。しかしながら、統合するデータベースの個数が増加すると、それに伴い辞書を拡張する必要が発生するため、表記ゆれに対処可能になるまでに時間が掛かるという欠点がある。

そこで、特許文献１では、辞書に頼らず、名寄せの対象データ周辺の情報（同データベースのデータＡとデータＢは繋がりがある、など）を用いて、通称を名寄せ可能とする技術を提案している。しかしながら、この特許文献１に開示されているような技術は、それぞれのデータベースの名称データから構築できるグラフが、一種の包含関係（一方のグラフの辺に対応する辺が、他方のグラフに必ず存在する）を満たしている必要がある。そのため、包含関係が保たれていない構造のグラフが得られてしまう名称データを名寄せすることは困難か、できたとしても候補となる名称が大量に出てきてしまう、という問題があった。

この発明は、統合するデータベース間で表記ゆれが存在する同義の名称データを、人的稼働を掛けず正確に対応付けることができる技術を提供しようとするものである。

上記課題を解決するために、この発明の一態様に係る名称データ対応付け装置は、複数の名称データ及びそれら名称データの論理的または物理的な隣接関係を示す隣接情報を保持する第１のデータベースと、複数の名称データ、それら名称データの隣接情報及びそれら名称データが属するパスを表すパス識別情報を保持する第２のデータベースとの間で異なる表記を有する同義の名称データを対応付ける名称データ対応付け装置であって、共通データ抽出部と、パス作成部と、対応付け部と、を備える。共通データ抽出部は、第１のデータベースと第２のデータベースとの間で同じ表記である名称データを共通データとして抽出する。パス作成部は、第２のデータベースが保持するパス識別情報で表されるパスから、共通データ抽出部が抽出した共通データを端点とし且つ非共通データを端点間の頂点とする部分パスを抽出し、第１のデータベースが保持する情報に基づいて、部分パスそれぞれについて、部分パスの端点と同じ共通データの端点を持ち且つ部分パスの長さ以上の長さを持つパスを作成する。対応付け部は、パス作成部が抽出した部分パスそれぞれについて、部分パス上の各頂点とパス作成部が作成したパス上の頂点との組み合わせを探索することで、第１のデータベースが保持する名称データと第２のデータベースが保持する名称データとを対応付ける。

この発明の一態様によれば、統合するデータベース間で表記ゆれが存在する同義の名称データを人的稼働を掛けず正確に対応付けることができる技術を提供することができる。

図１は、この発明の一実施形態に係る名称データ対応付け装置の構成の一例を示すブロック図である。 図２は、名称データ対応付け装置のハードウェア構成の一例を示す図である。 図３は、基礎データベース記憶部に記憶される基礎データベースが保持する情報の一例を示す図である。 図４は、派生データベース記憶部に記憶される派生データベースが保持する情報の一例を示す図である。 図５は、名称データ対応付け装置における名称データの対応付けに係わる処理動作の一例を示すフローチャートである。 図６は、名称の対応付け方法を説明するための模式図である。 図７は、動作例において基礎データベースが保持する情報の一例を示す図である。 図８は、動作例において派生データベースが保持する情報の一例を示す図である。 図９は、動作例においてグラフ作成部によって基礎データベースが保持する情報から作成された閉路グラフの一例を示す模式図である。 図１０は、動作例においてグラフ作成部によって派生データベースが保持する情報から作成された閉路グラフから生成されたパスの一例を示す模式図である。 図１１は、動作例において出力情報記憶部に記憶される出力情報の一例を示す図である。

以下、図面を参照して、この発明に係わる実施形態を説明する。

本実施形態において、複数のデータベースは、異なる表記を有する同義の名称データを保持しており、これらデータベースで名称データを対応付けしたいデータカラムは、既知であるとする。各データカラムは、名称データと、例えば測定値や測定日時、売上日時や売上金額、などといった、名称データに対応する文字列別データを含むことができる。また、各データベースは、名称データの隣接関係を示す論理的あるいは物理的な隣接情報を保持していることを想定する。ここで、名称データの隣接関係を示す隣接情報とは、例えば、人脈（人物Ａと人物Ｂが知り合いである）や、ネットワーク上の接続関係（ビルＡとビルＢがケーブルによって接続されている）といった、データ同士の繋がり方の情報を指す。この発明は、名称データを対応付けするデータベースの個数に制限は特にないが、本一実施形態では、説明の簡単化のため、対象とするデータベースは２つであるとする。また、各データベース内の名称データ間には、ネットワーク上の接続関係があるとする。具体的には、各データベースに「上位ビル」「下位ビル」という名前のカラムがあり、「上位ビル」に格納された名称データと「下位ビル」に格納された名称データは、あるネットワーク上で隣接していることを表す。加えて、複数のデータベースのうち少なくとも１つには、隣接情報に加えて、名称データが属するパスを表すパス識別情報が追加されていると想定する。

（構成例）
図１は、この発明の一実施形態に係る名称データ対応付け装置の構成の一例を示すブロック図である。名称データ対応付け装置は、基礎データベース（図では、データベースをＤＢと略記する。）１、派生データベース２、グラフ作成部３、共通データ抽出部４、パス情報抽出部５、パス作成部６、対応付け部７及びデータ出力部８を有する。

基礎データベース１は、複数の名称データと、それら名称データの隣接関係を示す隣接情報と、を保持する第１のデータベースである。また、派生データベース２は、複数の名称データと、それら名称データの隣接情報と、それら名称データが属するパスを表すパス識別情報と、を保持する第２のデータベースである。

グラフ作成部３は、基礎データベース１及び派生データベース２が保持する情報に基づいて、名称データを頂点とする無向グラフを作成する。

共通データ抽出部４は、基礎データベース１と派生データベース２との間で同じ表記である名称データを、共通データとして抽出する。

パス情報抽出部５は、派生データベース２が保持するパス識別情報に基づいて、共通データ抽出部４が抽出した共通データのうち１つを始点とし、派生データベース２が保持する名称データを頂点とする、全てのパスを生成する。パスの終点は、始点と同じ共通データとなる場合もあるし、始点と異なる共通データとなる場合もある。そして、パス情報抽出部５は、それらのパスそれぞれについて、頂点数、含まれる頂点の名称データ及びそのパス上の位置を含むパス情報を抽出する。例えば、パス情報抽出部５は、グラフ作成部３が作成した無向グラフと派生データベース２が保持するパス識別情報とに基づいて、パス情報を抽出することができる。

パス作成部６は、パス情報抽出部５が抽出したパス情報で示される各パスについて、各共通データを端点とする、すなわち始点及び終点とする、部分パスを抽出する。そして、パス作成部６は、基礎データベース１が保持する情報に基づいて、各部分パスと一致する共通データを端点とし且つ規定の長さである全てのパスを数え上げる。例えば、パス作成部６は、グラフ作成部３が基礎データベース１から作成した無向グラフに基づいて、パスを列挙することができる。

対応付け部７は、例えば、編集距離等の文字列類似度に基づいて、パス作成部６が抽出した部分パスと数え上げたパスとから、頂点の名称データの組み合わせを探索する。そして、対応付け部７は、探索した組み合わせに基づいて、基礎データベース１が保持する名称データと派生データベース２が保持する名称データとを対応付ける。

データ出力部８は、対応付け部７での対応付けの結果に基づいて、出力情報を生成し、それを出力する。例えば、データ出力部８は、対応付け部７での対応付けの結果に基づいて、名称データの対応関係を表す対応表を、出力情報として生成することができる。また、データ出力部８は、対応付け部７での対応付けの結果に基づいて基礎データベース１が保持している情報について名称データを変換して、新たなデータベースを作成し、これを出力情報とするようにしても良い。あるいは、データ出力部８は、対応付け部７での対応付けの結果に基づいて基礎データベース１及び派生データベース２が保持している情報を統合して、新たなデータベースを作成し、これを出力情報とするようにしても良い。

図２は、名称データ対応付け装置のハードウェア構成の一例を示す図である。

名称データ対応付け装置は、図２に示すように、例えばサーバコンピュータ（Server computer）やパーソナルコンピュータ（Personal computer）などのコンピュータにより構成され、ＣＰＵ（Central Processing Unit）等のハードウェアプロセッサ１０１を有する。そして、名称データ対応付け装置では、このプロセッサ１０１に対し、プログラムメモリ１０２と、データメモリ１０３と、通信インタフェース１０４と、入出力インタフェース（図２では入出力ＩＦと記す）１０５とが、バス１０６を介して接続される。

通信インタフェース１０４は、例えば一つ以上の有線または無線の通信モジュールを含むことができる。通信インタフェース１０４は、基礎データベース１及び／または派生データベース２が、ＬＡＮ（Local Area Network）やインターネットなどのネットワークを介して接続されるデータサーバなどに構成される場合には、そのデータサーバなどとの間で通信を行い、それらデータサーバからデータを取得することができる。また、通信インタフェース１０４は、外部のデータ処理装置などと通信して、そのデータ処理装置からの要求を受信したり、その要求に応じたデータ処理結果をデータ処理装置に返信したりすることもできる。

入出力インタフェース１０５には、入力部１０７及び表示部１０８が接続されている。入力部１０７及び表示部１０８は、例えば液晶または有機ＥＬ（Electro Luminescence）を使用した表示デバイスの表示画面上に、静電方式または圧力方式を採用した入力検知シートを配置した、いわゆるタブレット型の入力・表示デバイスを用いたものが用いられることができる。なお、入力部１０７及び表示部１０８は独立するデバイスにより構成されても良い。入出力インタフェース１０５は、上記入力部１０７において入力された操作情報をプロセッサ１０１に入力すると共に、プロセッサ１０１で生成された表示情報を表示部１０８に表示させる。

なお、入力部１０７及び表示部１０８は、入出力インタフェース１０５に接続されていなくても良い。入力部１０７及び表示部１０８は、通信インタフェース１０４と直接またはネットワークを介して接続するための通信ユニットを備えることで、プロセッサ１０１との間で情報の授受を行い得る。

また、入出力インタフェース１０５は、フラッシュメモリなどの半導体メモリといった記録媒体のリード／ライト機能を有しても良いし、あるいは、そのような記録媒体のリード／ライト機能を持ったリーダライタとの接続機能を有しても良い。これにより、名称データ対応付け装置に対して着脱自在な記録媒体を、名称データを保持するデータベースとすることができる。入出力インタフェース１０５は、さらに、他の機器との接続機能を有して良い。

プログラムメモリ１０２は、非一時的な有形のコンピュータ可読記憶媒体として、例えば、ＨＤＤ（Hard Disk Drive）またはＳＳＤ（Solid State Drive）等の随時書込み及び読出しが可能な不揮発性メモリと、ＲＯＭ等の不揮発性メモリとが組合せて使用されたものである。このプログラムメモリ１０２には、プロセッサ１０１が一実施形態に係る各種制御処理を実行するために必要なプログラムが格納されている。すなわち、上記のグラフ作成部３、共通データ抽出部４、パス情報抽出部５、パス作成部６、対応付け部７及びデータ出力部８の各部における処理機能部は、いずれも、プログラムメモリ１０２に格納されたプログラムを上記プロセッサ１０１により読み出させて実行させることにより実現され得る。なお、これらの処理機能部の一部または全部は、特定用途向け集積回路（ＡＳＩＣ：Application Specific Integrated Circuit）またはＦＰＧＡ（field-programmable gate array）などの集積回路を含む、他の多様な形式によって実現されても良い。

データメモリ１０３は、有形のコンピュータ可読記憶媒体として、例えば、上記の不揮発性メモリと、ＲＡＭ（Random Access Memory）等の揮発性メモリとが組合せて使用されたものである。このデータメモリ１０３は、各種処理が行われる過程で取得及び作成された各種データが記憶されるために用いられる。すなわち、データメモリ１０３には、各種処理が行われる過程で、適宜、各種データを記憶するための領域が確保される。そのような領域として、データメモリ１０３には、例えば、基礎データベース記憶部１０３１、派生データベース記憶部１０３２、一時記憶部１０３３及び出力情報記憶部１０３４を設けることができる。

基礎データベース記憶部１０３１は、基礎データベース１の情報を記憶し、派生データベース記憶部１０３２は、派生データベース２の情報を記憶する。すなわち、基礎データベース１及び派生データベース２が、この基礎データベース記憶部１０３１及び派生データベース記憶部１０３２に構成されることができる。

図３は、基礎データベース記憶部１０３１に記憶される基礎データベース１が保持する情報の一例を示す図であり、図４は、派生データベース記憶部１０３２に記憶される派生データベース２が保持する情報の一例を示す図である。ここでは、名称データがビルの名称である例を示す。基礎データベース記憶部１０３１に記憶される基礎データベース１では、上位ビルと下位ビルは、隣接関係にある。派生データベース記憶部１０３２に記憶される派生データベース２では、同一のパス識別子（図では、識別子をＩＤと略記する）を持つビルの組み合わせが、１つのパス（新宿ビル→南新宿ビル→外苑ビル→四ツ谷ビル→新宿ビル）を構成している。以降、派生データベース２にあるビル名をｃ_i（ｉ∈｛１，２，…，ｎ｝）で表し、基礎データベース１にあるビル名をｄ_j（ｊ∈｛１，２，…，ｍ｝）で表す。ここで、ｎ及びｍは、それぞれのデータベースにおけるビル名数である。

これら基礎データベース記憶部１０３１及び派生データベース記憶部１０３２に記憶される情報は、例えば、プロセッサ１０１が入出力インタフェース１０５を介して受け取った、入力部１０７から入力された基礎データベース１及び派生データベース２の情報とすることができる。すなわち、基礎データベース１及び派生データベース２が、データメモリ１０３に構築されることができる。また、外部のデータサーバに構築された基礎データベース１及び派生データベース２が保持する情報の全部または一部を、基礎データベース記憶部１０３１及び派生データベース記憶部１０３２に記憶させるようにしても良い。この場合は、例えば、プロセッサ１０１は、入力部１０７からのユーザ操作による指示に応じて、データベースサーバに蓄積された情報を通信インタフェース１０４を介して取得して、それらを記憶部１０３１、１０３２に記憶させる。あるいは、プロセッサ１０１は、記録媒体に記録された情報を、入出力インタフェース１０５を介して取得しても良い。また、プロセッサ１０１は、外部のデータ処理装置などから基礎データベース１及び派生データベース２の情報と名称データの対応付け要求とを通信インタフェース１０４を介して受信して、それら受信したデータベースの情報を、処理対象の情報として記憶部１０３１、１０３２に記憶させるようにしても良い。

一時記憶部１０３３は、プロセッサ１０１が、上記グラフ作成部３としての動作を実施した際に作成する無向グラフ、上記共通データ抽出部４としての動作を実施した際に抽出した共通データ、上記パス情報抽出部５としての動作を実施した際に抽出した全てのパスについてのパス情報、上記パス作成部６としての動作を実施した際に抽出した部分パス及び数え上げたパス、上記対応付け部７としての動作を実施した際に得られる名称データの対応付け結果、などを記憶する。

出力情報記憶部１０３４は、プロセッサ１０１が上記データ出力部８としての動作を実施した際に得られる出力情報を記憶する。

（動作）
次に、名称データ対応付け装置の動作を説明する。

図５は、名称データ対応付け装置における名称データの対応付けに係わる処理動作の一例を示すフローチャートである。ここでは、既に、基礎データベース記憶部１０３１には基礎データベース１の情報が記憶され、派生データベース記憶部１０３２には派生データベース２の情報が記憶されているものとする。入出力インタフェース１０５を介して入力部１０７から、あるいは、通信インタフェース１０４を介して外部のデータ処理装置から、名称データの対応付けの実施を指示されると、名称データ対応付け装置のプロセッサ１０１は、このフローチャートに示す動作を開始する。

まず、プロセッサ１０１は、グラフ作成部３としての動作を実行する。すなわち、プロセッサ１０１は、派生データベース記憶部１０３２に記憶された派生データベース２の情報と基礎データベース記憶部１０３１に記憶された基礎データベース１の情報とのそれぞれについて、隣接情報を使用して、名称データを頂点とする閉路グラフＧ_c及びＧ_dを生成する（ステップＳ１）。生成された閉路グラフＧ_c及びＧ_dは、データメモリ１０３の一時記憶部１０３３に記憶される。

派生データベース２にあるビル名ｃ_i及び基礎データベース１にあるビル名ｄ_jをそれぞれ頂点とし、隣接関係にある頂点同士は辺で結ばれていると解釈すると、以下のように、無向グラフである閉路グラフＧ_c及びＧ_dが構築できる。ここで、閉路とは、閉路グラフＧ_cの部分グラフであり、始点と終点が同一頂点であるようなパスを指す。

Ｅ_d： 基礎データベース１の隣接情報から得られる辺の集合
ｇ_d： Ｅ_d→Ｐ（Ｖ_d） Ｅ_dの元に頂点集合Ｖ_dの部分集合を対応させる写像。ただし、Ｐ（Ｖ_d）は頂点集合Ｖ_dの冪集合である
Ｇ_d :＝（ｇ_d，Ｖ_d，Ｅ_d）

Ｅ_c： 派生データベース２の隣接情報から得られる辺の集合
ｇ_c： Ｅ_c→Ｐ（Ｖ_c） Ｅ_cの元に頂点集合Ｖ_cの部分集合を対応させる写像。ただし、Ｐ（Ｖ_c）は頂点集合Ｖ_cの冪集合である
Ｇ_c :＝（ｇ_c，Ｖ_c，Ｅ_c）

また、名称データ対応付け装置のプロセッサ１０１は、共通データ抽出部４としての動作を実行する。すなわち、プロセッサ１０１は、基礎データベース記憶部１０３１に記憶された基礎データベース１の情報と派生データベース記憶部１０３２に記憶された派生データベース２の情報とで、共通する名称データを抽出する（ステップＳ２）。抽出され共通する名称データは、データメモリ１０３の一時記憶部１０３３に記憶される。

次に、プロセッサ１０１は、パス情報抽出部５としての動作を実行する。すなわち、プロセッサ１０１は、共通する名称データと派生データベース２が格納するパス識別情報とに基づいて、派生データベース２の閉路グラフＧ_cからパスΓ_k（ｋ∈｛１，２，…，Ｋ｝、Ｋは閉路グラフＧ_c内のパスの総数）を抽出する（ステップＳ３）。抽出されたパスΓ_kを示すパス情報は、データメモリ１０３の一時記憶部１０３３に記憶される。パス情報は、抽出されたパスΓ_kの頂点数、含まれる頂点の名称データ及びそのパス上の位置を含むことができる。

ここで、パスΓ_kとは、派生データベース２の閉路グラフＧ_cにおける頂点ｓ_k∈Ｖ_cを始点とするｋ番目のパスである。
Γ_k[l]： Γ_kを構成する頂点のうちｌ番目の頂点 （第ｌ要素）
｜Γ_k｜： パスΓ_kの長さ （パスΓ_kを構成する頂点の個数）
Γ_k＝（ｓ_k，…，ｔ_k），
（Γ_k[l]，Γ_k[l+1]）∈Ｅ_c，
ｌ∈｛１，２，…，｜Γ_k｜｝

閉路グラフＧ_cに対しパスはいくつあっても良いとするが、いずれのパスも、以下の３条件を満たすとする。
１．全てのｓ_kに対してｓ_k＝ｄ_j，ｔ_k＝ｄ_lを満たすｄ_j∈Ｖ_d，ｄ_lが存在する。
２．パスΓ_kを構成する全ての辺は、Ｅ_cに存在する。
３．∀ｃ_i∈Ｖ_cは、いずれかのパスΓ_kに所属している。

ここで、ステップＳ２で抽出された、Ｖ_cとＶ_dで同一表記であるようなビル名の集合をＳ :＝｛ｃ_i∈Ｖ_c｜∃ｄ_j∈Ｖ_d s.t. ｃ_i＝ｄ_j｝とする。名称データ対応付け装置は、この集合Ｓの要素ではない各ｃ_i，ｄ_jに対し、以下のようにして、閉路グラフＧ_c及びＧ_dを用いた対応付けを行う。

ここで、閉路グラフＧ_cを構成するパスの一つをΓ_kと表記し、パスΓ_kを構成する頂点のうち、集合Ｓに含まれる頂点の配列をＩ_kとし、以下で定義する。
Ｉ_k :＝（Γ_k[i]｜Γ_k[i]∈Ｓ，Γ_k[i]≠ｓ_k，i＝１，２，…，｜Γ_k｜）

次に、プロセッサ１０１は、パス作成部６としての動作を実行する。
すなわち、プロセッサ１０１は、まず、上記ステップＳ３で抽出されたパス情報に基づいて、一つのパスΓ_kに対して、閉路グラフＧ_cから集合Ｓの各要素を端点とする部分パス

を抽出する（ステップＳ４）。すなわち、Ｌ_k ⁱとは、パスΓ_kにおいて、頂点ｌ_k[i]から頂点ｌ_k[i+1]までの部分パスのことである。また、ｌ_k[i]は、配列ｌ_kのｉ番目の要素である。

次に、プロセッサ１０１は、抽出された部分パスに基づいて、基礎データベース１の閉路グラフＧ_dにおいて始点がｌ_k[i]、終点がｌ_k[i+1]であるようなパスのうち、長さが、｜Ｌ_k ⁱ｜以上（i＝１，２，…，｜Γ_k｝）且つ｜Ｌ_k ⁱ｜＋ｘ以下であるものを全て数え上げる（ステップＳ５）。ここで、ｘはユーザが指定した０以上の正整数である。なお、このパスを列挙する際に、同じ頂点及び辺を２回通ることはない。列挙された部分パスの集合を

と表記する。

次に、プロセッサ１０１は、対応付け部７としての動作を実行する。
すなわち、プロセッサ１０１は、まず、上記ステップＳ５で数え上げられた、パスの集合Ａ_k ⁱの中で、長さが｜Ｌ_k ⁱ｜のものがある場合、そのパスをαとする。この下で、以下のように名称の組み合わせを選出する（ステップＳ６）。
（Ｌ_k ⁱ[j]，α[j]），j＝１，２，…，｜Ｌ_k ⁱ｜
ただし、Ｌ_k ⁱ[j]，α[j]は、各パスのｊ番目の頂点である。

さらに、プロセッサ１０１は、それら選出した組み合わせの中で、長さが｜Ｌ_k ⁱ｜より長く且つ｜Ｌ_k ⁱ｜＋ｘ以下のものがある場合、図６のように文字列類似度（例えば、編集距離）に基づく名称検索技術を用いて、名称データの組み合わせを探索して対応付け、その結果をデータメモリ１０３の一時記憶部１０３３に記憶する（ステップＳ７）。編集距離は、例えば、D. Gusfield. "Algorithms on strings, trees and sequences: computer science and computational biology." Cambridge university press, 1997.に開示されている。

図６は、名称の対応付け方法を説明するための模式図である。基礎データベース１に格納されたビルＢＬ_dの名称データ（Ａビル、Ｂビル、…ｎビル）と派生データベース２に格納されたビルＢＬ_cの名称（αビル、βビル、…νビル）があり、同図に一点鎖線で示すように、同一名称または別のパスにより、Ａビルとαビル、ｎビルとνビルが既に対応付けがされているとする。このような場合、プロセッサ１０１は、以下の手順で、名称データの組み合わせを探索することができる。

１．ｘ＝０と初期化する。
２．長さ｜Ｌ_k ⁱ｜＋ｘのパスを数え上げる。
３．数え上げた１パスの頂点の中から、既に対応付けできている名称を除く。
４．得られたパスの長さが｜Ｌ_k ⁱ｜より大きい場合、派生データベース２のビルＢＬ_cの内、未だ対応付けできていないビル（γビル）から、基礎データベース１のビルＢＬ_dへ、編集距離が最短であるビルを求める。例えば、γビルから編集距離が最短のビルとして、実線矢印で示すように、Ｃビルが探索され、対応付けされることができる。
５．ｘ＝ｘ＋１として、予めユーザが指定したｘの上限値になるまで、上記２～４を繰り返す。
なお、編集距離が最短のビルＢＬ_dを探索する際には、破線矢印で示すように、既に対応付けされたビルＢＬ_dの次のビルから探索が開始される。

以上のようにして、組み合わせが１通りしかないものについてはそのまま出力結果とし、それ以外のものについては、既に出力結果が得られている名称データを候補から除外する。除外して残った候補のうち、整合性のとれるものを残して対応付け結果とする。ここでの整合性とは、ある名称Ａについて複数の候補名がある下で、候補名の中で前述の操作で除外された名称Ｂがあるときには、除外された名称Ｂと、名称Ａの組み合わせ（Ａ，Ｂ）を出力する根拠となったパスＰが必ず存在する。このパスＰからは、名称Ａとは別の名称Ｃに対しても、名称の組み合わせ（Ｃ，Ｄ）を与えている。名称組み合わせ（Ａ，Ｂ）が除外されたことで、組み合わせ（Ｃ，Ｄ）もまた除外する。より具体的な例は、動作例として、後述する。

こうして、一つのパスΓ_kについての処理が終了したならば、プロセッサ１０１は、上記ステップＳ３で抽出されたパス情報に基づくパスΓ_kの全てを処理したか否か判断する（ステップＳ８）。すなわち、全てのパスΓ_kの全ての頂点について処理を終了したか判断する。未だ処理していないパスΓ_kが存在すると判断した場合には、プロセッサ１０１は、ｋを更新して、上記ステップＳ４の処理に移行して、上記ステップＳ４乃至ステップＳ７の処理を繰り返す。

そして、上記ステップＳ８においてパスΓ_kの全てを処理したと判断した場合、プロセッサ１０１は、データ出力部８としての動作を実行することで、名称データの対応付け情報を出力する（ステップＳ９）。すなわち、プロセッサ１０１は、入力部１０７からまたは外部のデータ処理装置から指示された形態の出力情報をデータメモリ１０３の一時記憶部１０３３に記憶された対応付け結果から生成し、その生成した出力情報をデータメモリ１０３の出力情報記憶部１０３４に記憶させる。そして、プロセッサ１０１は、この出力情報を、入出力インタフェース１０５を介して表示部１０８により表示したり、通信インタフェース１０４を介して外部のデータ処理装置に送信したりすることができる。

以上に説明した一実施形態に係る名称データ対応付け装置は、パス作成部６により、共通データを端点とし且つ非共通データを端点間の頂点とする部分パスを抽出し、部分パスそれぞれについて、端点と同じ共通データの端点を持ち且つ部分パスの長さ以上の長さを持つパスを作成し、対応付け部７により、この部分パスそれぞれについて、部分パス上の各頂点とパス上の頂点との組み合わせを探索することで、基礎データベース１が保持する名称データと派生データベース２が保持する名称データとを対応付ける。これにより、統合するデータベース間で表記ゆれが存在する同義の名称データを、名称データに対応する文字列別データがデータベース間で対応関係を有していなくとも、人的稼働を掛けず正確に対応付けることができる。よって、異なるデータベース間で、ある事柄に対して漏れのない情報収集を行うことが可能となる。また、人的稼働の削減により、業務効率を上げる効果が期待できる。

なお、一実施形態に係る名称データ対応付け装置は、グラフ作成部３により、名称データを頂点とする基礎データベース１及び派生データベース２の無向グラフである閉路グラフＧ_d及びＧ_cを作成し、パス情報抽出部５によって、共通データを端点とし且つ派生データベース２が保持する名称データを頂点とする全てのパスΓ_kを生成し、それらのパスΓ_kそれぞれについて、頂点数、含まれる頂点の名称データ及びそのパス上の位置を含むパス情報を抽出する。そして、パス作成部６は、このパスΓ_kの１つに対して、前記パス情報に基づいて、閉路グラフＧ_cから部分パスを抽出し、この部分パスそれぞれについて、閉路グラフＧ_dから、部分パスの端点と同じ共通データの端点を持ち且つ部分パスが有する頂点の頂点数以上の頂点を含むパスを作成する。よって、基礎データベース１が保持している名称データのうち、派生データベース２が保持している名称データと対応付けできる可能性がある頂点を含む、換言すれば、派生データベース２が保持している名称データと対応付けできる可能性の無い頂点を除外した、パスを作成することができる。

さらにここで、パス作成部６は、作成するパスとして、パスΓ_kの頂点数以上であり且つ頂点数に対してユーザが指定した個数以下の頂点数を含むパスを作成する。よって、パスが含む頂点数を制限することで、処理時間の短縮化を図れる。

また、一実施形態に係る名称データ対応付け装置においては、対応付け部７は、パス作成部６によって作成したパス上の頂点それぞれについて、パス上の位置が部分パス上の頂点に対応する場合には、基礎データベース１が保持する名称データのうちのパス上の頂点に対応する名称データを、派生データベース２が保持する名称データのうちの部分パス上の頂点の名称データに対応付ける。また、パス上の位置が部分パス上の頂点に対応しない場合には、対応付け部７は、名称データ同士の文字列類似度に基づいて、基礎データベース１が保持する名称データのうちのパス上の頂点に対応する名称データと、派生データベース２が保持する名称データのうちの部分パス上の頂点の名称データとを対応付ける。よって、基礎データベース１が保持する名称データを、派生データベース２が保持する名称データに容易に対応付けすることができる。

また、一実施形態に係る名称データ対応付け装置は、パス情報抽出部５が生成したパスΓ_kの全てに対する処理が終了するまで、パス作成部６及び対応付け部７の処理を繰り返す。よって、派生データベース２が保持する名称データが基礎データベース１が保持する名称データと対応付けし損なう確率を減少させることができる。

また、一実施形態に係る名称データ対応付け装置は、データ出力部８により、名称データの対応付けの結果に基づいて、名称データの対応表を含む出力情報を生成する。よって、この出力情報を利用して、データベースの統合処理を実施することが可能となる。また、一実施形態に係る名称データ対応付け装置は、出力情報として、統合したデータベースの情報を生成しても良い。

［動作例］
本実施形態の動作例として、適用した名称データの概要と結果を説明する。

図７は、動作例において基礎データベース記憶部１０３１に記憶される基礎データベース１が保持する情報の一例を示す図である。この基礎データベースから得られる隣接情報は、以下の通りである。ここで、（Ａ，Ｂ）という表記は、データ名Ａとデータ名Ｂとは繋がりがあることを示すものとする。
・（福岡花園ビル、立子山ビル）
・（立子山ビル、福山伊達ビル）
・（福山伊達ビル、桑原ビル）
・（桑原ビル、福井藤田ビル）
・（福井藤田ビル、福地梁川ビル）
・（福地梁川ビル、保科ビル）
・（保科ビル、恐山ビル）
・（保科ビル、福岡花園ビル）
・（恐山ビル、福岡花園ビル）
・（恐山ビル、月舘ビル）
・（月舘ビル、福島川俣ビル）
・（福島川俣ビル、福岡花園ビル）

図８は、動作例において派生データベース記憶部１０３２に記憶される派生データベース２が保持する情報の一例を示す図である。この派生データベースから得られる隣接情報は、以下の通りである。この隣接情報のパスがΓ_kであり、本動作例で扱うパスは一本なのでｋ＝１とする。ここで、（Ａ→Ｂ）という表記は、データ名Ａからデータ名Ｂへパスがあることを示すものとする。
・（花園ビル→伊達ビル）
・（伊達ビル→桑原ビル）
・（桑原ビル→藤田ビル）
・（藤田ビル→梁川ビル）
・（梁川ビル→保科ビル）
・（保科ビル→恐山ビル）
・（恐山ビル→月館ビル）
・（月館ビル→川俣ビル）
・（川俣ビル→花園ビル）

この動作例では、パスＩＤ＝２の名称データに関して、頂点集合Ｖ_c及びＶ_dは、以下の通りである。
Ｖ_c＝｛福岡花園ビル、立子山ビル、福山伊達ビル、桑原ビル、福井藤田ビル、福地梁川ビル、保科ビル、恐山ビル、月舘ビル、福島川俣ビル｝
Ｖ_d＝｛花園ビル、伊達ビル、桑原ビル、藤田ビル、梁川ビル、保科ビル、恐山ビル、月館ビル、川俣ビル｝

そして、名称データの正確な表記の組み合わせ、すなわち名称データの対応付けは、この動作例では、次の通りである。
｛（月舘ビル、月館ビル），（福島川俣ビル、川俣ビル），（福岡花園ビル、花園ビル），（福山伊達ビル、伊達ビル），（福井藤田ビル、藤田ビル），（福地梁川ビル、梁川ビル）｝

実施形態に係る名称データ対応付け装置がこの対応付けを正しく行うことができるか確認した。

名称データ対応付け装置のプロセッサ１０１は、ステップＳ１において、グラフ作成部３としての動作を実施し、閉路グラフを作成する。図９は、動作例において基礎データベース１が保持する情報から作成された閉路グラフＧ_dの一例を示す模式図である。

また、プロセッサ１０１は、ステップＳ２において、共通データ抽出部４としての動作を実施し、閉路グラフＧ_cと閉路グラフＧ_dとで共通する名称データを抽出する。ここで、同一表記であるような名称データつまりビル名集合Ｓは、以下の通りである。
Ｓ :＝｛桑原ビル、保科ビル、恐山ビル｝

そこで、プロセッサ１０１は、ステップＳ３において、パス情報抽出部５としての動作を実施して派生データベース２からパス情報を抽出し、ステップＳ４において、パス作成部６としての動作を実施して部分パスを抽出する。図１０は、動作例において派生データベース２が保持する情報から作成された閉路グラフＧ_cから生成されたパスΓ1の一例を示す模式図である。プロセッサ１０１は、閉路グラフＧ_cからビル名集合Ｓの各要素を端点とする部分パス

を抽出する。
Ｌ₁ ¹ :＝（桑原ビル、藤田ビル、梁川ビル、保科ビル）
Ｌ₁ ² :＝（保科ビル、恐山ビル）
Ｌ₁ ³ :＝（恐山ビル、月館ビル、川俣ビル、花園ビル、伊達ビル、桑原ビル）

そして、プロセッサ１０１は、ステップＳ５において、部分パスＬ₁ ¹について、閉路グラフＧ_d上で、「桑原ビル」と「保科ビル」を端点に持つ、長さ３以上、３＋ｘ以下のパスを数え上げる。

今回は動作例のため、パラメータｘ＝１とする。すると、
長さ３： （桑原ビル、福井藤田ビル、福地梁川ビル、保科ビル）
長さ４： （桑原ビル、福山伊達ビル、立子山ビル、福岡花園ビル、保科ビル）
となる。

長さ３の場合について、数え上げたパスと部分パスＬ₁ ¹との対応する頂点名を組合せると、
（福井藤田ビル、藤田ビル）、（福地梁川ビル、梁川ビル）
の候補を得る。

長さ４の場合は、どの組み合わせも編集距離が１であるので、
「藤田ビル」に対し、候補：「福山伊達ビル」、「立子山ビル」、「福井藤田ビル」
「梁川ビル」に対し、候補：「福岡花園ビル」、「立子山ビル」、「福地梁川ビル」
が考えられる。

部分パスＬ₁ ²については、長さ１なので、省略する。

部分パスＬ₁ ³について、プロセッサ１０１は、閉路グラフＧ_d上で、「恐山ビル」と「桑原ビル」を端点に持つ、長さ５以上、５＋ｘ＝６以下のパスを数え上げる。すると、
長さ５：該当なし
長さ６：（恐山ビル、月舘ビル、福島川俣ビル、福岡花園ビル、立子山ビル、福山伊達ビル、桑原ビル）
を得る。

長さ６のパスから、部分パスＬ₁ ³の各頂点と編集距離が最短である点を選択すると、
（月舘ビル、月館ビル）、（福島川俣ビル、川俣ビル）、（福岡花園ビル、花園ビル）、（福山伊達ビル、伊達ビル）
の候補を得る。

以上より、候補数が１つである組み合わせ＝回答、とするので、
（月舘ビル、月館ビル）、（福島川俣ビル、川俣ビル）、（福岡花園ビル、花園ビル）、（福山伊達ビル、伊達ビル）
は回答となる。

そして、この「花園ビル」と「伊達ビル」の回答から、「藤田ビル」及び「梁川ビル」の候補は、
「藤田ビル」に対し、候補：「立子山ビル」、「福井藤田ビル」
「梁川ビル」に対し、候補：「立子山ビル」、「福地梁川ビル」
になる。ここで、「福岡花園ビル」と「福山伊達ビル」の候補がなくなったことから、
パス：（桑原ビル、福山伊達ビル、立子山ビル、福岡花園ビル、保科ビル）
は、部分パスＬ₁ ¹の閉路グラフＧ_dにおける対応パスにはなりえない。よって、「藤田ビル」及び「梁川ビル」の候補から「立子山ビル」も除外されるので、
（福井藤田ビル、藤田ビル）、（福地梁川ビル、梁川ビル）
を回答として得る。

その後、プロセッサ１０１は、データメモリ１０３の一時記憶部１０３３に記憶された上記対応付けの結果に基づいて出力情報を生成し、データメモリ１０３の出力情報記憶部１０３４に記憶させる。図１１は、この出力情報記憶部１０３４に記憶される出力情報の一例を示す図である。なお、ここでは、出力情報を名称データの対応関係を表す対応表として示しているが、これに限定されないことは勿論である。

以上より、名称データ対応付け装置により、部分パスを使用することで、正確な名称データの対応付けが可能であることが検証できた。

［他の実施形態］
前記一実施形態では、対象とするデータベースも２つの場合を例に説明したが、３つ以上であっても良い。すなわち、３つ以上のデータベースのうち、少なくとも１つのデータベースがパス識別情報を保持していれば、残りの２つ以上のデータベースとの間で名称データの対応付けを行うことが可能となる。

また、前記一実施形態では、パスを例に説明したが、パスではなく閉路である場合（始点と終点が同一の頂点）であっても対応可能なことは勿論である。

また、前記一実施形態では、データメモリ１０３の基礎データベース記憶部１０３１及び派生データベース記憶部１０３２に基礎データベース１及び派生データベース２が保持する情報の全部または一部を記憶して処理を進める例を説明したが、それに限定するものではない。プロセッサ１０１は、通信インタフェース１０４により外部のデータサーバに適宜アクセスして、そこに構築された基礎データベース１及び派生データベース２に蓄積されている情報を使用して処理を進め、各ステップの処理結果のみを一時記憶部１０３３に記憶するようにしても良い。これにより、名称データ対応付け装置が備えるデータメモリ１０３の容量を抑えることができ、安価に名称データ対応付け装置を構成することが可能となる。

また、前記一実施形態では、出力情報を生成して、表示部１０８または外部のデータ処理装置に出力する例を説明したが、出力情報を生成することなく、一時記憶部１０３３に記憶した対応付け結果を出力するようにしても良い。これにより、名称データ対応付け装置が備えるデータメモリ１０３の容量を抑えることができ、安価に名称データ対応付け装置を構成することが可能となる。また、データベースの統合処理を行うデータ処理装置に対して、名称データの対応付けのみを行うサービスを提供することが可能となる。

また、各実施形態に記載した手法は、計算機（コンピュータ）に実行させることができるプログラム（ソフトウェア手段）として、例えば磁気ディスク（フロッピー（登録商標）ディスク、ハードディスク等）、光ディスク（ＣＤ－ＲＯＭ、ＤＶＤ、ＭＯ等）、半導体メモリ（ＲＯＭ、ＲＡＭ、フラッシュメモリ等）等の記録媒体に格納し、また通信媒体により伝送して頒布することもできる。なお、媒体側に格納されるプログラムには、計算機に実行させるソフトウェア手段（実行プログラムのみならずテーブル、データ構造も含む）を計算機内に構成させる設定プログラムをも含む。本装置を実現する計算機は、記録媒体に記録されたプログラムを読み込み、また場合により設定プログラムによりソフトウェア手段を構築し、このソフトウェア手段によって動作が制御されることにより上述した処理を実行する。なお、本明細書でいう記録媒体は、頒布用に限らず、計算機内部あるいはネットワークを介して接続される機器に設けられた磁気ディスク、半導体メモリ等の記憶媒体を含むものである。

要するに、この発明は上記実施形態に限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で種々に変形することが可能である。また、各実施形態は可能な限り適宜組合せて実施しても良く、その場合組合せた効果が得られる。さらに、上記実施形態には種々の段階の発明が含まれており、開示される複数の構成要件における適当な組み合わせにより種々の発明が抽出され得る。

１…基礎データベース
２…派生データベース
３…グラフ作成部
４…共通データ抽出部
５…パス情報抽出部
６…パス作成部
７…対応付け部
８…データ出力部
１０１…プロセッサ
１０２…プログラムメモリ
１０３…データメモリ
１０４…通信インタフェース
１０５…入出力インタフェース
１０６…バス
１０７…入力部
１０８…表示部
１０３１…基礎データベース記憶部
１０３２…派生データベース記憶部
１０３３…一時記憶部
１０３４…出力情報記憶部

Claims (8)

1. 複数の名称データ及びそれら名称データの論理的または物理的な隣接関係を示す隣接情報を保持する第１のデータベースと、複数の名称データ、それら名称データの隣接情報及びそれら名称データが属するパスを表すパス識別情報を保持する第２のデータベースとの間で異なる表記を有する同義の名称データを対応付ける名称データ対応付け装置であって、
   前記第１のデータベースと前記第２のデータベースとの間で同じ表記である名称データを共通データとして抽出する共通データ抽出部と、
   前記第２のデータベースが保持する前記パス識別情報で表される前記パスから、前記共通データ抽出部が抽出した前記共通データを端点とし且つ非共通データを前記端点間の頂点とする部分パスを抽出し、前記第１のデータベースが保持する情報に基づいて、前記部分パスそれぞれについて、前記部分パスの前記端点と同じ共通データの端点を持ち且つ前記部分パスの長さ以上の長さを持つパスを作成するパス作成部と、
   前記パス作成部が抽出した前記部分パスそれぞれについて、前記部分パス上の各頂点と前記パス作成部が作成した前記パス上の頂点との組み合わせを探索することで、前記第１のデータベースが保持する前記名称データと前記第２のデータベースが保持する前記名称データとを対応付ける対応付け部と、
   を具備する、名称データ対応付け装置。
2. 前記第１のデータベース及び前記第２のデータベースが保持する情報に基づいて、前記名称データを頂点とする前記第１のデータベース及び前記第２のデータベースの無向グラフを作成するグラフ作成部と、
   前記グラフ作成部が作成した前記第２のデータベースの前記無向グラフと前記第２のデータベースが保持する前記パス識別情報とに基づいて、前記共通データ抽出部が抽出した前記共通データを端点とし且つ前記第２のデータベースが保持する前記名称データを頂点とする全てのパスを生成し、それらのパスそれぞれについて、頂点数、含まれる頂点の名称データ及びそのパス上の位置を含むパス情報を抽出するパス情報抽出部と、
   をさらに具備し、
   前記パス作成部は、前記パス情報抽出部が生成したパスの１つに対し、前記パス情報に基づいて、前記グラフ作成部が作成した前記第２のデータベースの前記無向グラフから前記部分パスを抽出し、前記部分パスそれぞれについて、前記第１のデータベースの前記無向グラフから、前記部分パスの前記端点と同じ共通データの端点を持ち且つ前記部分パスが有する頂点の頂点数以上の頂点を含むパスを作成する、請求項１に記載の名称データ対応付け装置。
3. 前記パス作成部は、前記パスとして、前記頂点数以上であり且つ前記頂点数に対してユーザが指定した個数以下の頂点数を含むパスを作成する、請求項２に記載の名称データ対応付け装置。
4. 前記対応付け部は、前記パス作成部が作成した前記パス上の前記頂点それぞれについて、
   前記パス上の位置が前記部分パス上の前記頂点に対応する場合には、前記第１のデータベースが保持する前記名称データのうちの前記パス上の前記頂点に対応する名称データを、前記第２のデータベースが保持する前記名称データのうちの前記部分パス上の前記頂点の前記名称データに対応付け、
   前記パス上の位置が前記部分パス上の前記頂点に対応しない場合には、名称データ同士の文字列類似度に基づいて、前記第１のデータベースが保持する前記名称データのうちの前記パス上の前記頂点に対応する名称データと、前記第２のデータベースが保持する前記名称データのうちの前記部分パス上の前記頂点の前記名称データとを対応付ける、
   請求項１乃至３のいずれかに記載の名称データ対応付け装置。
5. 前記パス作成部及び前記対応付け部は、前記パス情報抽出部が生成したパスの全てに対する処理が終了するまで、処理を繰り返す、請求項２または３に記載の名称データ対応付け装置。
6. 前記対応付け部による対応付けの結果に基づいて、名称データの対応表を含む出力情報を生成する出力部をさらに具備する、請求項１乃至５のいずれかに記載の名称データ対応付け装置。
7. プロセッサと、複数の名称データ及びそれら名称データの論理的または物理的な隣接関係を示す隣接情報を保持する第１のデータベースと、複数の名称データ、それら名称データの隣接情報及びそれら名称データが属するパスを表すパス識別情報を保持する第２のデータベースとを記憶したメモリと、を備え、前記第１のデータベースと前記第２のデータベースとの間で異なる表記を有する同義の名称データを対応付ける名称データ対応付け装置における名称データ対応付け方法であって、
   前記プロセッサにより、前記メモリに記憶されている前記第１のデータベースと前記第２のデータベースとの間で同じ表記である名称データを共通データとして抽出し、
   前記プロセッサにより、前記メモリに記憶されている前記第２のデータベースが保持する前記パス識別情報で表される前記パスから、前記抽出した前記共通データを端点とし且つ非共通データを前記端点間の頂点とする部分パスを抽出し、
   前記プロセッサにより、前記メモリに記憶されている前記第１のデータベースが保持する情報に基づいて、前記抽出した前記部分パスそれぞれについて、前記部分パスの前記端点と同じ共通データの端点を持ち且つ前記部分パスの長さ以上の長さを持つパスを作成し、
   前記プロセッサにより、前記抽出した前記部分パスそれぞれについて、前記部分パス上の各頂点と前記作成した前記パス上の頂点との組み合わせを探索することで、前記メモリに記憶されている前記第１のデータベースが保持する前記名称データと前記メモリに記憶されている前記第２のデータベースが保持する前記名称データとを対応付ける、
   名称データ対応付け方法。
8. 請求項１乃至６のいずれかに記載の名称データ対応付け装置の前記各部としてプロセッサを機能させる名称データ対応付けプログラム。
   
   

Images