(57)【特許請求の範囲】
【請求項１】
所定の文字列に含まれる１または複数の部分文字列であって、前記所定の文字列の文字数を所定の編集距離で除算した商よりも小さい文字数の、１または複数の部分文字列を抽出し、
抽出された前記１または複数の部分文字列のうち、前記所定の文字列の文字数及び１の和から、前記所定の編集距離及び１の和と前記商よりも小さい自然数との積を引いた差以下の部分文字列のいずれかを含む文字列を、文字列群から抽出する、
処理をコンピュータに実行させる抽出プログラム。
【請求項２】
前記文字列群から抽出された文字列について、前記所定の文字列との間の編集距離が前記所定の編集距離以下であるか否か判定する、
処理をさらに実行させる請求項１に記載の抽出プログラム。
【請求項３】
前記所定の文字列との間の編集距離が前記所定の編集距離以下の文字列は、
前記所定の文字列に対して前記所定の編集距離以下の編集回数の編集を行なうことにより得られる文字列である、
ことを特徴とする請求項２に記載の抽出プログラム。
【請求項４】
所定の文字列に含まれる１または複数の部分文字列であって、前記所定の文字列の文字数を所定の編集距離で除算した商よりも小さい文字数の、１または複数の部分文字列を抽出し、
抽出された前記１または複数の部分文字列のうち、前記所定の文字列の文字数及び１の和から、前記所定の編集距離及び１の和と前記商よりも小さい自然数との積を引いた差以下の部分文字列のいずれかを含む文字列を、文字列群から抽出する、
処理をコンピュータに実行させる抽出方法。
【請求項５】
所定の文字列に含まれる１または複数の部分文字列であって、前記所定の文字列の文字数を所定の編集距離で除算した商よりも小さい文字数の、１または複数の部分文字列を抽出する第１の抽出手段と、
抽出された前記１または複数の部分文字列のうち、前記所定の文字列の文字数及び１の和から、前記所定の編集距離及び１の和と前記商よりも小さい自然数との積を引いた差以下の部分文字列のいずれかを含む文字列を、文字列群から抽出する第２の抽出手段と、
を含むことを特徴とする抽出装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、所定の文字列を文字列群から抽出するための抽出プログラム、抽出方法及び抽出装置に関する。
【背景技術】
【０００２】
情報技術の進歩に伴い、情報の収集、加工、保管といった情報処理がコンピュータを用いて行われることが多くなっている。扱う情報量が増加しつつある一方で、効率的な情報処理の技術が求められている。
【０００３】
例えば、ユーザが指定した文書に記述されている内容の特徴を表す文字列を抽出し、当該文書に記述されている内容と類似する内容を含む文書を文書データベースの中から検索する技術が知られている。また、ユーザが指定した検索条件にしたがって所望の文書を文書データベースから検索する際に、各文書が検索条件に合致する度合に応じて検索結果を並べ替えて表示する技術も知られている。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開平１１−３３８８８３号公報
【特許文献２】特開２００１−１０９７６６号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
情報処理の１つとして、複数のデータが集まっている状況において、データ同士を照合してその関連性を導き出す「名寄せ」という処理がある。名寄せにおいては、ある文字列と類似する文字列を抽出する処理が行なわれる。類似する文字列を抽出する処理は、同一の文字列を抽出する処理よりも条件判断処理を多く含むため、処理負荷が大きい。名寄せを行う対象のデータ量が膨大である場合には、名寄せの処理量も膨大なものとなる。そこで、本願の開示内容の一側面として、類似文字列の抽出対象のデータの増大による抽出処理負荷の増大を抑制することを目的とする。
【課題を解決するための手段】
【０００６】
本願に開示する抽出技術においては、所定の文字列に含まれる１または複数の部分文字列であって、前記所定の文字列の文字数を所定の編集距離で除算した商よりも小さい文字数の、１または複数の部分文字列を抽出し、抽出された前記１または複数の部分文字列のうち、前記所定の文字列の文字数及び１の和から、前記所定の編集距離及び１の和と前記商よりも小さい自然数との積を引いた差以下の部分文字列のいずれかを含む文字列を、文字列群から抽出する。
【発明の効果】
【０００７】
本願の開示内容の一側面として、類似文字列の抽出対象のデータの増大による抽出処理負荷の増大を抑制することができる。
【図面の簡単な説明】
【０００８】
【図１】名寄せ機能の説明図である。
【図２】名寄せ機能の動作についての説明図である。
【図３】名寄せ定義のデータ構造の一例を示す説明図である。
【図４】粗絞りによる名寄せの説明図である。
【図５】粗絞りによる名寄せの処理手順を示すフローチャートである。
【図６】照合処理の手順を示すフローチャートである。
【図７】粗絞り定義のデータ構造の一例を示す説明図である。
【図８】粗絞り定義の作成の流れを示す説明図である。
【図９】名寄せ処理と粗絞り処理の詳細を示す説明図である。
【図１０】名寄せ処理の比較条件と粗絞り処理の検索条件との対応関係を示す説明図である。
【図１１】名寄せ先のレコードの集合から検索する必要のあるレコードを示す説明図である。
【図１２】名寄せ先のレコードの集合から検索する必要のあるレコードを示す説明図である。
【図１３】名寄せ先のレコードの集合から検索する必要のあるレコードを示す説明図である。
【図１４】名寄せの比較条件と粗絞りの検索条件との関係を示す説明図である。
【図１５】名寄せの比較条件と粗絞りの検索条件との関係式を示す説明図である。
【図１６】粗絞り定義のチューニングの詳細を示す説明図である。
【図１７】粗絞り定義のチューニングの詳細を示す説明図である。
【図１８】情報処理装置の機能構成例を示す説明図である。
【図１９】情報処理装置のハードウェア構成例を示す説明図である。
【図２０】情報処理装置により行われる粗絞り定義の作成の流れを示す説明図である。
【発明を実施するための形態】
【０００９】
［１．名寄せの概要］
値の集合を含んだレコードについて、レコード間を照合し、レコード間の同一性、類似性及び関連性を判定する機能として名寄せ機能がある。名寄せ機能では、例えば、名寄せするレコードの集合を名寄せ元、名寄せ相手となるレコードの集合を名寄せ先と称する。図１は、名寄せ機能を説明する図である。図示しているように、名寄せ機能を実現する名寄せ処理は、名寄せ元と同じレコード、名寄せ元と類似するレコードまたは名寄せ元と関連するレコードを名寄せ先から検出し、検出結果を名寄せ結果として出力する。
【００１０】
近年、データベースの大容量（大規模）化に伴い、名寄せを高速に行う手法が求められている。従来の名寄せ機能の動作について、図２を参照しながら説明する。図２は、名寄せ機能の動作を説明する図である。図示しているように、名寄せ元が取引先表であり、名寄せ先が顧客表である。そして、名寄せ元である取引先表に含まれる複数のレコードのうち、１つのレコードＪ１のみが図示されている。また、名寄せ先である顧客表については、全レコードＭ（Ｍ１〜Ｍｎ）が図示されている。名寄せ元のレコードＪ１は、ＩＤ、会社名、郵便番号、住所、電話番号という５つのカラムを含んでいる。他方、名寄せ先のレコードＭ（Ｍ１〜Ｍｎ）は、ＩＤ、顧客名、郵便番号、顧客住所、電話番号という５つのカラムを含んでいる。名寄せ機能を実現する名寄せ処理は、名寄せ元の１レコードＪ１について、名寄せ先のレコードＭ（Ｍ１〜Ｍｎ）との名寄せを実行する。
【００１１】
まず、名寄せ処理は、名寄せ元のレコードＪ１及び名寄せ先のレコードＭ１の各名寄せ対象の項目（「名寄せ対象項目」という。）の値について、予め名寄せ対象項目毎に定義した評価関数を適用して照合を行う。ここでは、名寄せ元の会社名と名寄せ先の顧客名とを第１の名寄せ対象項目とし、名寄せ元の郵便番号と名寄せ先の郵便番号とを第２の名寄せ対象項目とする。さらに、名寄せ元の住所と名寄せ先の顧客住所とを第３の名寄せ対象項目とし、名寄せ元の電話番号と名寄せ先の電話番号とを第４の名寄せ対象項目とする。名寄せ処理は、第１の名寄せ対象項目をｆａ（）、第２の名寄せ対象項目をｆｂ（）、第３の名寄せ対象項目をｆｃ（）、第４の名寄せ対象項目をｆｄ（）とする各評価関数を適
用して照合を行う。そして、名寄せ処理は、照合の結果として導出される各名寄せ対象項目の評価値に重みＡ〜Ｄを用いて名寄せ対象項目毎に重み付けを行い、得られた各値を加算することによって、総合評価値ｈを導出する。さらに、名寄せ処理は、名寄せ元のレコードＪ１に対する残り全ての名寄せ先のレコードＭ２〜Ｍｎについて、総合評価値をそれぞれ導出する。名寄せ処理は、これら名寄せ元のレコードＪ１及び名寄せ先のレコードＭ１〜Ｍｎの組についての総合評価値を含む名寄せ候補集合を作成する。
【００１２】
そして、名寄せ処理は、予め定義した閾値や判定ルールに基づいて、名寄せ候補集合に属するレコードの組について名寄せに関する判定を行う。例えば、名寄せ処理は、総合評価値ｈを閾値と比較して、一致していると判定されたレコードの組を「Ｗｈｉｔｅ」、一致していないと判定されたレコードの組を「Ｂｌａｃｋ」とし、名寄せ結果を出力する。名寄せ処理は、「Ｗｈｉｔｅ」、「Ｂｌａｃｋ」のいずれにも該当しない組を「Ｇｒａｙ」として候補リストに出力する。そして、候補リストに出力された組の関連性の判定が人により行われる。なお、人による設定が必要な名寄せ定義１０３ａとして、名寄せ対象項目の選定、評価関数の選定、重み及び閾値の設定がある。
【００１３】
名寄せ定義１０３ａの具体例を図３に示している。図３は、名寄せ定義のデータ構造の一例を示す図であり、図３（Ａ）が、名寄せ定義の内容を示し、図３（Ｂ）が、名寄せ定義の具体例を示す。
【００１４】
図３（Ａ）に示すように、名寄せ定義は、名寄せ方法ｄ１、名寄せ元指定ｄ２、名寄せ先指定ｄ３、名寄せ対象項目指定ｄ４および閾値ｄ５を対応付けて定義される。名寄せ方法ｄ１には、名寄せの方法が指定される。例えば、名寄せの方法には、１つのレコード集合を対象として集合内のレコード間の総当りで名寄せを行い、一致しているレコードを検出して重複するレコードを除去する「自己名寄せ」がある。自己名寄せは、名寄せ元と名寄せ先が同じレコード集合なので、その構造（レコードの項目）も同じであるという特徴を有する。また、名寄せの方法には、名寄せ及び名寄せ先として異なるレコード集合を対象として名寄せ元レコードと名寄せ先レコードの組み合わせによる名寄せを行い、一致しているレコードを検出して該当レコード間の関連付けを行う「他者名寄せ」がある。他者名寄せは、名寄せ元と名寄せ先が異なる集合なので、一般的にその構造（レコードの項目）が異なるという特徴を有する。名寄せ元指定ｄ２には、名寄せ元のデータベース名等のアクセス情報および名寄せ元のレコードの項目が指定される。名寄せ先指定ｄ３には、名寄せ先のデータベース名等のアクセス情報および名寄せ先のレコードの項目が指定される。名寄せ対象項目指定ｄ４には、名寄せ対象項目が名寄せ元の項目と名寄せ先の項目の組み合わせとして指定され、名寄せ対象項目毎に適用される評価関数および重みが指定される。閾値ｄ５には、Ｗｈｉｔｅ判定用の上位の閾値およびＢｌａｃｋ判定用の下位の閾値が指定される。
【００１５】
図３（Ｂ）に示すように、例えば、名寄せ方法ｄ１には、「他者名寄せ」が指定されている。名寄せ元指定ｄ２のアクセス情報には、「取引先表」が指定され、名寄せ元指定ｄ２のレコード情報には、ＩＤ（identification）、会社名、郵便番号、住所および電話番号の項目が指定されている。名寄せ先指定ｄ３のアクセス情報には、「顧客表」が指定され、名寄せ先指定ｄ３のレコード情報には、ＩＤ（identification）、顧客名、郵便番号、顧客住所および電話番号の項目が指定されている。
【００１６】
名寄せ対象項目指定ｄ４には、名寄せ対象項目を会社名：顧客名、郵便番号：郵便番号、住所：顧客住所および電話番号：電話番号として指定されている。これは、名寄せ元の項目：名寄せ先の項目の組として名寄せ対象項目を指定してするものである。この名寄せ対象項目に対して、適用する評価関数と重みを指定する。例えば名寄せ対象項目が会社名：顧客名の場合には、評価関数に「編集距離１字違い以内」、重みに０．２が指定されて
いる。名寄せ対象項目が郵便番号：郵便番号の場合には、評価関数に「完全一致」、重みに０．２が指定されている。閾値ｄ５には、上位の閾値に０．７２、下位の閾値に０．２６が指定されている。
【００１７】
なお、「編集距離」とは、名寄せ元と名寄せ先との名寄せ対象項目の値の照合において名寄せ先の値を名寄せ元の値に変形させる際の最小編集回数を距離として表す評価関数である。例えば、「編集距離１字違い以内」を評価関数としたときに、編集距離が１字違い以内の場合には当該評価関数は１．０を返し、その他の場合には当該評価関数は０を返す。
【００１８】
また、「完全一致」とは、名寄せ元と名寄せ先との名寄せ対象項目の値の照合において２つの値が完全に一致するか否かを表す評価関数である。２つの値が完全に一致する場合には１．０を返し、それ以外は０を返す。なお、図３（Ｂ）に示した「編集距離」及び「完全一致」はあくまで評価関数の一例である。
【００１９】
図１〜図３を参照して説明した名寄せ処理において、名寄せに係る照合処理の対象となるレコードの組み合わせの数は、名寄せ元のレコード数と名寄せ先のレコード数とを乗ずることにより求められる。例えば、図２において、名寄せ元である取引先表のレコード数が１０万件、名寄せ先である顧客表のレコード数が２００万件である場合には、２０００億組の照合処理が必要となる。このような大規模な名寄せは、膨大な時間を要することとなる。
【００２０】
［２．粗絞りによる名寄せの高速化］
名寄せ元のレコードおよび名寄せ先のレコードについて、レコード同士を照合する照合処理の前に、照合するレコードの組を減らし、大規模な名寄せを高速化する技術がある。ここでは、照合処理の前に、名寄せ元と一致する可能性のある名寄せ先のレコードを粗く絞り込む「粗絞り」の技術について説明する。以下、粗絞りを「事前検索」とも呼び、続いて行う照合処理を「本検索」とも呼ぶ。
【００２１】
図４は、「粗絞り」による名寄せを説明する図である。図示しているように、粗絞り処理１０２では、名寄せ元１００のレコード毎に生成される検索条件を用いて、名寄せ先１０１からレコードを検索し、検索した結果を検索結果１０２ｂとして出力する。この検索条件は、後述する粗絞り定義１０２ａに基づいて生成される。
【００２２】
ここで、名寄せ先候補となる検索結果１０２ｂの件数が名寄せ元１００の１レコードに対して平均１００件であると仮定すると、名寄せ処理１０３による照合では、名寄せ元１００の１０万件×名寄せ先候補の平均１００件＝１０００万組の照合となり、名寄せ先１０１のレコード全件を対象とする名寄せに係る照合の２０００億組に比べて大幅な削減となる。
【００２３】
次に、粗絞りによる名寄せの処理手順について、図５及び図６を参照しながら説明する。図５及び図６は、粗絞りによる名寄せの処理手順を示すフローチャートである。
【００２４】
まず、粗絞り処理１０２は、粗絞り定義１０２ａを読み込んで動作環境を設定し（ステップＳ１００）、名寄せ元１００から名寄せする対象となる名寄せ元のレコード（以降、「名寄せ元レコード」という。）を順に取り出す（ステップＳ１０１）。そして、粗絞り処理１０２は、粗絞り定義１０２ａに定義される粗絞り対象項目毎に名寄せ元レコードの該当する項目の値を条件にして、名寄せ先１０１を粗く検索する（ステップＳ１０２）。具体的には、粗絞り処理１０２は、粗絞り対象項目毎に名寄せ元レコードの該当する項目の値を条件とした各条件をＯＲした検索条件で名寄せ先１０１を曖昧検索する。ここで、
曖昧検索とは「ｎ−ｇｒａｍ」等による検索である。そして、粗絞り処理１０２は、検索したレコードを検索結果１０２ｂとして格納する。
【００２５】
次に、名寄せ処理１０３は、検索結果１０２ｂに格納された各レコードを名寄せ先として順に取り出し（ステップＳ１０３）、名寄せ元レコードと名寄せ先との照合処理を行う（ステップＳ１０４）。このステップＳ１０４の詳細は図６を参照して後述する。そして、名寄せ処理１０３は、照合結果を名寄せ候補集合に格納する（ステップＳ１０５）。なお、照合結果には、総合評価値が含まれる。
【００２６】
続いて、名寄せ処理１０３は、検索結果１０２ｂに残りの検索結果レコードが有るか否かを判定する（ステップＳ１０６）。検索結果１０２ｂに残りの検索結果レコードが有ると判定された場合には（ステップＳ１０６；Ｙｅｓ）、名寄せ処理１０３は、残りの検索結果レコードを取り出すべく、ステップＳ１０３に移行する。
【００２７】
一方、検索結果１０２ｂに残りの検索結果レコードが無いと判定された場合には（ステップＳ１０６；Ｎｏ）、名寄せ処理１０３は、名寄せ候補集合に格納された各総合評価値について閾値による判定を実行して判定結果を出力する（ステップＳ１０７）。例えば、名寄せ処理１０３は、総合評価値が上位閾値以上である場合には、照合した名寄せ元レコードと名寄せ先レコードの組について、一致しているレコードの組であると判断して「Ｗｈｉｔｅ」と判定する。また、名寄せ処理１０３は、総合評価値が上位閾値未満且つ下位閾値以上である場合には、照合した名寄せ元レコードと名寄せ先レコードの組について、一致しているとも一致していないとも判定できないと判断して「Ｇｒａｙ」と判定する。また、名寄せ処理１０３は、総合評価値が下位閾値未満である場合には、照合した名寄せ元レコードと名寄せ先レコードの組について、不一致であるレコードの組であると判断して「Ｂｌａｃｋ」と判定する。そして、「Ｗｈｉｔｅ」及び「Ｂｌａｃｋ」と判定されたレコードの組が名寄せ結果として出力され、「Ｇｒａｙ」と判定されたレコードの組は候補リストとして出力される。この候補リストにあるレコードの組についての一致または不一致の判断は人により行われる。
【００２８】
そして、粗絞り処理１０２は、名寄せ元１００に残りの名寄せ元レコードが有るか否かを判定する（ステップＳ１０８）。そして、名寄せ元１００に残りの名寄せ元レコードが有ると判定された場合には（ステップＳ１０８；Ｙｅｓ）、粗絞り処理１０２は、残りの名寄せ元レコードを取り出すべく、ステップＳ１０１に移行する。一方、名寄せ元１００に残りの名寄せ元レコードが無いと判定された場合には（ステップＳ１０８；Ｎｏ）、粗絞り処理１０２は、粗絞りによる名寄せ処理を終了する。
【００２９】
次に、図５に示すステップＳ１０４の処理手順について、図６を参照しながら説明する。図６は、照合処理の手順を示すフローチャートである。照合処理は、名寄せ元レコードと名寄せ先レコードの１組毎に、照合を行い総合評価値を導出する処理である。
【００３０】
まず、名寄せ処理１０３は、名寄せ定義１０３ａに定義された名寄せ対象項目を順に選択する（ステップＳ１１０）。なお、名寄せ対象項目は、名寄せ元の項目と名寄せ先の項目で構成される比較の対象とする項目の対として予め名寄せ定義１０３ａに定義されている。そして、名寄せ処理１０３は、名寄せ元レコードおよび名寄せ先レコードについて、それぞれ選択した名寄せ対象項目に対応した各値を指定し（ステップＳ１１１）、指定した２つの値に評価関数を適用し（ステップＳ１１２）、評価値を算出する。なお、評価関数は、名寄せ定義１０３ａにおいて名寄せ対象項目につき予め定義されている関数である。
【００３１】
続いて、名寄せ処理１０３は、残りの名寄せ対象項目が有るか否かを判定する（ステッ
プＳ１１３）。残りの名寄せ対象項目が有ると判定された場合には（ステップＳ１１３；Ｙｅｓ）、名寄せ処理１０３は、残りの名寄せ対象項目について評価関数を適用すべく、ステップＳ１１０に移行する。
【００３２】
一方、残りの名寄せ対象項目が無いと判定された場合には（ステップＳ１１３；Ｎｏ）、名寄せ処理１０３は、各名寄せ対象項目の評価値に名寄せ対象項目毎の重み付けを行い、重み付けを行った結果の各評価値を加算する（ステップＳ１１４）。そして、名寄せ処理１０３は、加算結果の値を対象のレコード組に対する総合評価値として出力し（ステップＳ１１５）、１組に対する照合処理を終える。
【００３３】
粗絞り定義のデータ構造の一例を図７に示している。図７（Ａ）が粗絞り定義の内容を示し、図７（Ｂ）が粗絞り定義の具体例を示している。この粗絞り定義の作成は、名寄せ定義の作成と同様に人により行われる。
【００３４】
図７（Ａ）に示すように、粗絞り定義は、対象項目と検索条件を対応付けて定義し、必要に応じて最大検出数も定義することができる。対象項目は、粗絞り処理において検索条件を適用する名寄せ元の項目と名寄せ先の項目とを対として複数指定することができ、対応する検索条件が指定される。最大検出数は、１つの名寄せ元レコードについて名寄せ先を検索した結果として残す名寄せ先レコードの最大件数である。
【００３５】
図７（Ｂ）に示すように、粗絞り定義１０２ａにおいては、粗絞り対象項目ｄ１１毎に対象とする名寄せ元の項目と名寄せ元の項目および適用する検索条件が定義され、前述の最大検出数ｄ１２も必要に応じて定義される。粗絞り対象項目ｄ１１には、「元先」および「検索条件」が対応付けられている。「元先」は、名寄せ元レコード及び名寄せ先レコードそれぞれの粗絞り対象項目となる項目の名称を「名寄せ元項目：名寄せ先項目」として示す。検索条件は、各対象項目について、名寄せ元の該当項目の値により名寄せ先の該当項目を検索する際の検索方法を指定する。例えば、検索条件には、名寄せ元レコードの対象項目について値の連続する何れかのＮ文字を対象項目に含む名寄せ先レコードを検索する「ｎ−ｇｒａｍ」や、名寄せ先レコードの対象項目の値が完全に一致している対象項目を有する名寄せ先レコードを検索する「完全一致」がある。「ｎ−ｇｒａｍ」を用いる場合には、インデックス一致数ｃを指定することもできる。ここで、ｎ−ｇｒａｍにおけるインデックスとは、名寄せ元レコードの対象項目においてｎ文字にわたって連続した文字列のことである。例えば、「Ｂｉ−ｇｒａｍ／インデックス一致数４」という検索条件である場合には、名寄せ元レコードの対象項目において２文字にわたって連続した文字列のうち、４個以上を対象項目に含むレコードを名寄せ先レコードから検索することになる。
【００３６】
図７（Ｂ）の例では、対象項目が「会社名：顧客名」の検索条件は、「Ｂｉ−Ｇｒａｍ／一致数２」であることを示している。また、「住所：顧客住所」の検索条件は、「Ｂｉ−Ｇｒａｍ／一致数４」であることを示している。対象項目が「郵便番号：郵便番号」及び「電話番号：電話番号」の検索条件は「完全一致」であることを示す。これら４つの検索条件により検索される各集合の和集合が、図４の検索結果１０２ｂに相当する。また、各名寄せ元レコードに対する名寄せ先レコードの最大検出数は、１０００件である。
【００３７】
［３．粗絞り定義の作成］
これまで、図４〜図７を参照して粗絞りを伴う名寄せについて説明した。名寄せ処理に用いる名寄せ定義、粗絞り処理に用いる粗絞り定義はいずれも人により作成されることは、上述したとおりである。通常、名寄せ定義がまず作成され、続いて粗絞り定義が作成される。このうちの粗絞り定義の作成の流れを図８に示している。
【００３８】
手順Ｔ１１では、ユーザが名寄せ元データと、名寄せ先データと、既に作成した名寄せ定義とを参照しながら、名寄せ先データのうち照合する必要がないとして除外できるレコードを考慮し、初期の粗絞り定義を作成する。
【００３９】
手順Ｔ１２では、名寄せ元のレコードをいくつかサンプリングし、サンプリングしたレコードを元に、手順Ｔ１１で作成した初期の粗絞り定義を用いて粗絞り処理を試行する。
【００４０】
手順Ｔ１３では、使用するコンピュータの処理速度を踏まえて、名寄せ先データの絞込みレコード件数を評価する。十分に絞込みができていると評価されれば、後述の手順Ｔ１４に進む。さもなければ、粗絞り定義を修正し、手順Ｔ１２に戻る。
【００４１】
手順Ｔ１４では、上記手順Ｔ１２でサンプリングしたレコードについて、名寄せ処理を試行する。
【００４２】
手順Ｔ１５では、上記手順Ｔ１４の名寄せ処理の試行結果を確認し、既に作成されている「名寄せ定義」に基づいて、名寄せ元レコードと照合すべき名寄せ先レコードが粗絞り処理により除外されていないかを調査する。除外されている場合には、上記手順Ｔ１２に戻る。
【００４３】
以上のように、試行錯誤しながら手順Ｔ１２〜Ｔ１５を繰り返すことにより、手順Ｔ１６にて粗絞り定義が完成する。
【００４４】
この粗絞り定義を作成するにあたり、使用するコンピュータの処理速度を考慮して名寄せ先のレコードを絞り込み過ぎると、後続の名寄せ処理に必要なデータが漏れてしまうため、名寄せの精度が低くなる。一方で、名寄せの精度を重視し過ぎると、十分な粗絞りができないため、名寄せ処理に膨大な時間を要することになる。そのため、粗絞り定義の作成には試行錯誤を伴う。粗絞り定義の作成を人により行う場合の工数は、数人月にも及ぶことが一般的である。
【００４５】
［４．粗絞り定義を効率的に作成する技術］
以下、粗絞り定義を効率的に作成する技術について述べる。本技術は、事前に作成されている名寄せ定義に基づいて粗絞り定義を効率的に作成するものである。まず、名寄せ処理と粗絞り処理とについて図９を参照してさらに詳しく説明する。
【００４６】
図９には、名寄せ元の１つのレコードＪ１と名寄せ先のレコードの集合Ｍを示している。これらは図２に示した名寄せ元のレコードＪ１及び名寄せ先のレコードの集合Ｍにそれぞれ相当する。そして、名寄せ先のレコードの集合Ｍに対して粗絞り処理を行うことにより、検索されたレコードの集合Ｍａが作成される。この粗絞り処理を行うにあたっては、図示しているように、検索用関数を用いて、集合Ｍから特定の文字列を含んだレコードを検索する。この粗絞り処理は、粗い精度で良い一方で高速に行う必要がある。検索用関数の例としては、既に述べたような完全一致、Ｕｎｉ−ｇｒａｍやＢｉ−ｇｒａｍといったｎ−ｇｒａｍ、前方一致、後方一致などがある。
【００４７】
検索されたレコードの集合Ｍａが作成されると、次に名寄せ元のレコードＪ１と集合Ｍａとの名寄せ処理を行う。このとき、レコードＪ１との関係で、名寄せ定義にて定義されている照合ルールの少なくとも１つを満たすレコードの集合ができる。この集合を名寄せ集合Ｍｂとして図示している。この名寄せ処理を行うにあたっては、図示しているように、比較用関数を用いて、レコードＪ１と集合Ｍａ内の各レコードとを比較する。この比較は、きめ細かく行う必要があるために処理に時間がかかるという点において、粗絞り処理とは対照的である。比較用関数の例としては、完全一致、編集距離がある。さらに、編集
距離の具体例として、比較する２つの文字列において異なる字数を見る関数がある。くわえて、比較する２つの文字列において異なる字数を、これら２つの文字列の一方の文字数で割ることにより得られる値を編集の比率として見る関数もある。
【００４８】
このような粗絞り処理を行うにあたっては以下の点に留意する必要がある。
・レコードＪ１との名寄せ結果がＷｈｉｔｅまたはＧｒａｙとなるレコードの集合Ｍｂが、検索されたレコードの集合Ｍａに含まれるようにする。
・その一方で、集合Ｍａを極力小さな集合とする。
・粗絞り処理自体のコスト（処理時間、使用する計算資源など）を抑える。
【００４９】
そして、図１０には、名寄せ処理の比較条件と粗絞り処理の検索条件との対応関係を示している。図示しているように、名寄せ処理における比較条件として「完全一致」を用いる場合は、粗絞り処理における検索条件も「完全一致」となる。「完全一致」は、明確な文字列比較関数であり、そのまま粗絞り用としても利用できるためである。
【００５０】
次に、名寄せ処理における比較条件として「あいまい一致」すなわち編集距離に基づく条件を用いる場合を説明する。編集距離は、あいまい比較用の評価関数であり、比較する２つの文字列の並び順が一部変更されている場合にも有効に評価できる特徴を持つ。この比較条件を包含する検索条件としては、ｎ−ｇｒａｍ及びインデックス一致数に基づく検索条件が妥当である。
【００５１】
続いて、名寄せ処理における編集距離に基づいた比較条件を、粗絞り用検索条件であるｎ−ｇｒａｍに変換する具体的な方法について説明する。なお、ｎ−ｇｒａｍの「ｎ」及び「インデックスの一致数」に基づいて評価するためには、比較元の文字列の最小字数を考慮する必要がある。
【００５２】
まず、比較条件が「編集距離で１文字違い以内」である場合を説明する。比較元が「ＡＢＣ」という３文字の文字列である場合に、名寄せ先のレコードの集合Ｍから検索する必要のあるレコードを図１１に示している。ただし、「？」は、「Ａ」、「Ｂ」、「Ｃ」のいずれでもない文字とする。つまり、図１１に示している文字列パターンは、比較元の文字列「ＡＢＣ」から抽出される文字列パターンである。
【００５３】
図１１に示しているように、名寄せ先から検索する必要のあるレコードは、比較元の値「ＡＢＣ」における文字数１のインデックス（つまり、「Ａ」、「Ｂ」、「Ｃ」）のうち、２個以上を含むレコードである。したがって、図示したようなレコードを名寄せ先から検索するための検索条件は、「１（ｕｎｉ）−ｇｒａｍ、インデックスの一致数２以上」である。
【００５４】
次に、比較条件が同じく「編集距離で１文字違い以内」であって、比較元が「ＡＢＣＤ」という４文字の文字列である場合に、名寄せ先のレコードの集合Ｍから検索する必要のあるレコードを図１２に示している。ただし、「？」は、「Ａ」、「Ｂ」、「Ｃ」、「Ｄ」のいずれでもない文字とする。つまり、図１２に示している文字列パターンは、比較元の文字列「ＡＢＣＤ」から抽出される文字列パターンである。
【００５５】
図１２に示しているように、名寄せ先から検索する必要のあるレコードは、比較元の値「ＡＢＣＤ」における文字数２のインデックス（つまり、「ＡＢ」、「ＢＣ」、「ＣＤ」）のうち、１個以上を含むレコードである。したがって、図示したようなレコードを名寄せ先から検索するための検索条件は、「２（ｂｉ）−ｇｒａｍ、インデックスの一致数１以上」である。あるいは、比較元の値「ＡＢＣＤ」における文字数１のインデックス（つまり、「Ａ」、「Ｂ」、「Ｃ」、「Ｄ」）のうち、３個以上を含むレコードを名寄せ先か
ら検索することとしてもよい。この場合の検索条件は「１（ｕｎｉ）−ｇｒａｍ、インデックスの一致数３以上」となる。
【００５６】
図１１及び図１２に示した例から、名寄せ時の比較条件「編集距離ｄ字違い以内」を、粗絞り時の検索条件「ｎ−ｇｒａｍ、インデックスの一致数ｃ」へと変換するための式は以下のようになる。
ｎ＝Ｆ１（ｄ，ｍ）
ｃ＝Ｆ２（ｄ，ｍ，ｎ）
ただし、ｍは比較元の文字列の最小字数であり、Ｆ１及びＦ２は互いに異なる関数である。
【００５７】
また、比較条件が「編集距離で２文字違い以内」であって、比較元が「ＡＢＣ」という３文字の文字列である場合に、名寄せ先のレコードの集合Ｍから検索する必要のあるレコードを図１３に示している。ただし、「？」は、「Ａ」、「Ｂ」、「Ｃ」のいずれでもない文字とする。つまり、図１３に示している文字列パターンは、比較元の文字列「ＡＢＣ」から抽出される文字列パターンである。
【００５８】
図１３に示しているように、名寄せ先から検索する必要のあるレコードは、比較元の値「ＡＢＣ」における文字数１のインデックス（つまり、「Ａ」、「Ｂ」、「Ｃ」）のうち、１個以上を含むレコードである。したがって、図示したようなレコードを名寄せ先から検索するための検索条件は、「１（ｕｎｉ）−ｇｒａｍ、インデックスの一致数１以上」である。
【００５９】
図１１〜図１３に示したような例は一例であるが、さらに範囲を広げた結果を図１４（Ａ）に示している。図１４（Ａ）は、名寄せの比較条件（ｄ及びｍ）と、粗絞りの検索条件（ｎ及びｃ）との関係を示している。既に述べたとおり、ｄは名寄せの比較条件「編集距離ｄ字違い以内」の「ｄ」に相当し、ｍは比較元の文字列の最小字数である。また、ｎ及びｃは、粗絞りの検索条件「ｎ−ｇｒａｍ、インデックスの一致数ｃ」の「ｎ」及び「ｃ」にそれぞれ相当する。そして、図１４（Ａ）には、ｄについてはｄ＝１，２，３の３パターン、ｍについてはｍ＝１，２，・・・，１０の１０パターンを組み合わせた計３０パターンについてｎとｃのとりうる値を示している。
【００６０】
例えば、ｄ＝１かつｍ＝３のときは、「ｎ＝１／ｃ＝２」となっている。これは、図１１に示した例に相当する。そして、ｄ＝１かつｍ＝４のときは、「ｎ＝１／ｃ＝３」または「ｎ＝２／ｃ＝１」となっている。これは、図１２に示した例に相当する。また、ｄ＝２かつｍ＝３のときは、「ｎ＝１／ｃ＝１」となっている。これは、図１３に示した例に相当する。なお、ｄ＝１かつｍ＝１のときは「Ｎｏｎｅ（ａｌｌ）」となっているが、これは、名寄せ先の全レコードが検索されてしまうために粗絞りの意義がなくなることを示している。
【００６１】
図１４（Ｂ）は、名寄せの比較条件（ｒ及びｍ）と、粗絞りの検索条件（ｎ及びｃ）との関係を示している。ここで、ｒは名寄せの比較条件「編集距離（比率ｒ以内）」の「ｒ」に相当する。その他は図１４（Ａ）と同様であるので、説明を省略する。なお、ｒ＝０．３３かつｍ＝１のときは「Ｎｏｎｅ（＝０％）」となっているが、これは、ｒ＝０を指定したことと同じになってしまうために粗絞りの意義がなくなることを示している。
【００６２】
図１４（Ａ）及び（Ｂ）から、ｄ（あるいはｒ）及びｍとｎ及びｃとの関係を図１５に示したような式で表すことができる。つまり、名寄せ定義で定義された比較条件に基づいて粗絞りの検索条件が作成できることになる。以下、ｍ、ｎ、ｃ、ｄをそれぞれ第１の数、第２の数、第３の数、第４の数とも呼ぶ。
【００６３】
図１５（Ａ）は、ｄ及びｍに基づいてｎ及びｃを求める式を示している。図１５（Ｂ）は、ｒ及びｍに基づいてｎ及びｃを求める式を示しているが、図１５（Ａ）に示した式と結果的に同じとなる。これは、ｄ＝ｒ×ｍ（小数点切捨て）という式に基づいて、ｒをｄに変換することができるためである。また、図１５（Ａ）及び（Ｂ）の両方に共通していえることとして、実際に粗絞りを行う際には、ｎを大きくすると検索用インデックスが巨大化するため、ｎの最大値を決めておく必要がある。
【００６４】
これまで図９〜図１５を参照して、名寄せの比較条件から粗絞りの検索条件を定める点について説明してきた。このようにして、従来では試行錯誤を繰り返しながら作成していた粗絞り定義を効率的に作成することができる。具体的には、従来行われている粗絞り定義の作成時に生じうる人為的ミスや本来定義すべき粗絞り条件の漏れを低減することができる。また、粗絞りの精度とコンピュータの処理速度とのバランスを考慮するための専門知識の習得や経験が不要となる。さらに、粗絞り定義の作成に必要な人的コストを大幅に削減することができる。その一方で、ユーザは、粗絞りの検索条件を考慮せずに、実際の名寄せ元データ及び名寄せ先データを見て直観的に「名寄せ定義」を作成することができる。
【００６５】
そして、図１５に示したような式を用いることにより、比較元の最小字数に該当するカラム内にどんな文字列が入っていても、（図９の集合Ｍｂに相当する）名寄せされた集合が、（同じく図９の集合Ｍａに相当する）粗絞りにより検索されたレコードの集合に含まれることになる。
【００６６】
しかし、実際に名寄せをする際に、名寄せ元及び名寄せ先のレコードに含まれる文字列によっては、粗絞り条件のｎあるいはｃを、図１５に示したような式により求められる値よりも大きくすることにより、さらに小さな集合へと絞り込める可能性がある。このようにｎ及びｃを大きくすることを粗絞り定義のチューニングと呼ぶ。
【００６７】
［５．粗絞り定義のチューニング］
以下、粗絞り定義のチューニングについて図１６及び図１７を参照して説明する。前提として、名寄せ定義と、図１５に示したような式に基づく粗絞り定義（初期の粗絞り定義とも呼ぶ）とが作成されているものとする。この粗絞り定義のｎ及びｃをチューニングするにあたり、まず名寄せ元のレコードをいくつかサンプリングする。このときのサンプリング率ｓは０．１であるとする。このサンプリングにおいては、名寄せ元のレコードを分析して、サンプリングされたレコードになるべく偏りがないようにする必要がある。例えば、統計学に基づいた手法を用いてサンプリングを行うことができる。また、図１６（Ａ）に示しているように、名寄せ先のレコードの集合Ｐは、レコードＲ１〜Ｒ１４という１４個のレコードを含んでいる。このことを図１６（Ａ）にてｖ＝１４と表現している。
【００６８】
次に、名寄せ定義に定義された比較条件に基づいて、名寄せ元からサンプリングしたレコードと名寄せ先との、粗絞りを伴わない名寄せを行う。これを名寄せ試行と呼ぶ。この名寄せ試行により、名寄せ元からサンプリングしたレコードとの関係で、名寄せ定義に定義された比較条件の少なくとも１つを満たす名寄せ先のレコードをその比較条件ごとに記録しておく。このようにして記録されるレコードの集合を名寄せ集合Ｐｃとして図１６（Ａ）に示している。集合ＰｃはレコードＲ１１〜Ｒ１４という４個のレコードを含んでいる。このことを図１６（Ａ）にてｘ＝４と表現している。
【００６９】
続いて、名寄せ元からサンプリングしたレコードと、名寄せ先の全レコードとに対して、事前に作成されている粗絞り定義を用いて粗絞りを行う。これを粗絞り試行と呼ぶ。この粗絞り試行により検索された名寄せ先のレコードはカラム毎に記録しておく。粗絞り試
行により作成された集合Ｐａを図１６（Ａ）に示している。集合ＰａはレコードＲ３〜Ｒ１４という１２個のレコードを含んでいる。つまり、粗絞り試行によりレコードＲ１及びＲ２が除外されたことになる。このことを図１６（Ａ）にてｗ＝１２と表現している。
【００７０】
次に、名寄せ試行によりＷｈｉｔｅまたはＧｒａｙと判定された名寄せ先のレコードの集合Ｐｃが、粗絞り試行により検索された名寄せ先のレコードの集合Ｐａに含まれているかどうかをチェックする。具体的には以下のように行う。
【００７１】
まず、集合Ｐａと集合Ｐｃとの積集合には、レコードＲ１１〜Ｒ１４という４個のレコードが含まれている。このことを図１６（Ａ）にてｙ＝４と表現している。また、集合Ｐｃが集合Ｐａに含まれる割合を粗絞り適合率と呼ぶ。粗絞り適合率はｙ／ｗ＝４／１２＝３３％と計算される。また、集合Ｐｃが集合Ｐａから漏れている割合を漏れ率と呼ぶ。漏れ率は１−ｙ／ｘ＝１−４／４＝０％と計算される。
【００７２】
なお、名寄せ元の全レコードに関して名寄せ先を粗絞りした場合の検索される予測レコード数を予測粗絞り数と呼ぶ。予測粗絞り数はｗ／ｓ＝１２／０．１＝１２０以内と予測される。また、名寄せ元の全レコードに関して名寄せした場合にＷｈｉｔｅまたはＧｒａｙと判定されるであろう名寄せ先のレコード数を予測名寄せ数と呼ぶ。予測名寄せ数は、ｘ／ｓ＝４／０．１＝４０以内と予測される。
【００７３】
つまり、前記チェックでは、漏れ率が０％かどうかが判断される。漏れ率が０％であれば、もう少し粗絞りの検索条件を狭くすることができると予想されるため、後述する検索条件変更に進む。なお、図１５に示したような式に基づいた粗絞り定義に基づく粗絞り試行を行った後の漏れ率は必ず０％となる。漏れ率が０％となるようにｎ及びｃの値が定められているからである。
【００７４】
検索条件変更においては、粗絞りにより検索されるレコードの集合をより小さなものにするために、粗絞りの検索条件すなわちｎ及びｃの値を変更する。例えば、ｃの値だけをｃ’＝ｃ＋１に変更する。あるいは、ｎをｎ’＝ｎ＋１へ変更し、ｃをｃ’へ変更する。このときのｎ’とｃ’との関係を図１７に示している。つまり、ｃ’＝ｃ−（ｎ’−ｎ）×（ｄ＋１）となる。この式により、ｎをｎ’＝ｎ＋１に変更した場合のｃ’を求めることができる。そして、ｎ’が図１５を参照して説明したｎ−ｇｒａｍのｎの最大値以下であり、かつｃ’が０より大きい値であれば、ｎ’及びｃ’による検索条件を用いて、前記粗絞り試行と前記チェックと前記検索条件変更とを繰り返す。そして、チェックの結果、例えば図１６（Ｂ）に示すように漏れ率が０％ではなかった場合には、ｎ’及びｃ’ではなく、ｎ及びｃの値を最終的な値として決定する。あるいは、検索条件変更の結果、ｃ’が０以下の値となった場合にも、ｎ’及びｃ’ではなく、ｎ及びｃの値を最終的な値として決定する。
【００７５】
このように、検索条件をｎ’及びｃ’に変更し、それらを用いて粗絞り試行を行い、この粗絞り試行の結果と前記名寄せ試行の結果をチェックするという一連の処理を繰り返す。これにより、初期の値ｎより一定量大きい最終的な値ｎが定まる。
【００７６】
一例として、初期の値ｎ＝１、初期の値ｃ＝３であったときの検索条件変更の流れを説明する。まずｎ’を求める。ｎ’がｎよりも１だけ大きい値とすれば、ｎ’＝ｎ＋１＝１＋１＝２である。次に、このｎ’を用いてｃ’を求める。つまり、ｃ’＝ｃ−（ｎ’−ｎ）×（ｄ＋１）＝３−（２−１）×（１＋１）＝１となる。これらｎ’＝２及びｃ’＝１による検索条件を用いて、粗絞り試行とチェックと検索条件変更とを繰り返す。
【００７７】
これまで図１６及び図１７を参照して粗絞り定義のチューニングについて説明してきた
。このチューニングにより、粗絞り定義にて定義される検索条件を、実際の名寄せ元データ及び名寄せ先データに応じてより範囲の狭い検索条件に変更し、粗絞りをさらに効率的に行うことができるようになる。
【００７８】
［６．実施例］
続いて、粗絞り定義の作成とチューニングの実施例について図１８〜図２０を参照して説明する。図１８は、名寄せを行う情報処理装置１の機能構成例を示している。情報処理装置１は、制御部１１と不揮発性記憶部１２と揮発性記憶部１３とを備えている。不揮発性記憶部１２は、名寄せ元データを格納した名寄せ元ＤＢ１２１と、名寄せ先データを格納した名寄せ先ＤＢ１２２とを有している。さらに、不揮発性記憶部１２には、事前にユーザによって作成された名寄せ定義１２３が保存されている。加えて、不揮発性記憶部１２には、後述する粗絞り定義生成部１１１によって作成される粗絞り定義１２４が保存される。
【００７９】
制御部１１は、粗絞り定義生成部１１１と、粗絞り処理部１１３と、名寄せ部１１４とを有している。粗絞り定義生成部１１１は、名寄せ定義１２３を元にチューニング済みの粗絞り定義１２４を作成して不揮発性記憶部１２に保存する。粗絞り処理部１１３は、名寄せ元ＤＢ１２１にあるレコードと粗絞り定義１２４とを参照し、名寄せ先ＤＢ１２２にあるレコードの粗絞りを行う。粗絞りの結果は粗絞り処理結果１３１として揮発性記憶部１３に保存される。名寄せ部１１４は、粗絞り処理結果１３１に基づいて、名寄せ元ＤＢ１２１の各レコードと、名寄せ先ＤＢ１２２のレコードのうちの絞り込まれたレコードとの名寄せを行う。名寄せの結果は、名寄せ処理結果１３２として揮発性記憶部１３に保存される。
【００８０】
図１９は、名寄せを行う情報処理装置１のハードウェア構成例を示している。情報処理装置１は、ＣＰＵ１０１０と、インタフェース装置１０２０と、表示装置１０３０と、入力装置１０４０と、ドライブ装置１０５０と、補助記憶装置１０６０と、メモリ装置１０７０とを備えており、これらがバス１０８０により相互に接続されている。
【００８１】
情報処理装置１の機能を実現するプログラムは、ＣＤ−ＲＯＭ等の記録媒体１０９０によって提供される。プログラムを記録した記録媒体１０９０がドライブ装置１０５０にセットされると、プログラムが記録媒体１０９０からドライブ装置１０５０を介して補助記憶装置１０６０にインストールされる。あるいは、プログラムのインストールは必ずしも記録媒体１０９０により行う必要はなく、ネットワークを介して他のコンピュータからダウンロードすることもできる。補助記憶装置１０６０は、インストールされたプログラムを格納すると共に、必要なファイルやデータ等を格納する。
【００８２】
メモリ装置１０７０は、プログラムの起動指示があった場合に、補助記憶装置１０６０からプログラムを読み出して格納する。ＣＰＵ１０１０は、メモリ装置１０７０に格納されたプログラムに従って情報処理装置１の機能を実現する。インタフェース装置１０２０は、ネットワークを通して他のコンピュータに接続するためのインタフェースとして用いられる。表示装置１０３０はプログラムによるＧＵＩ（Graphical User Interface）等を表示する。入力装置１０４０はキーボード及びマウス等であり、名寄せのユーザが様々な指示を入力するために用いるものである。
【００８３】
図２０は、情報処理装置１により行われる粗絞り定義１２４を作成する処理の流れを示している。まずステップＳ４００にて粗絞り定義生成部１１１は、不揮発性記憶部１２に事前に保存されている名寄せ定義１２３を読み込む。名寄せ定義１２３の具体例は図３に示したとおりである。続いて粗絞り定義生成部１１１は、読み込んだ名寄せ定義１２３を元に図示しない初期の粗絞り定義（現粗絞り定義とも呼ぶ）を生成し、不揮発性記憶部１
に保存する。このときの初期の粗絞り定義の生成の方法は、図１０〜図１５を参照して説明したとおりである。すなわち、名寄せ定義１２３に定義された１つ以上の比較条件のそれぞれについて、比較条件が「完全一致」であれば粗絞りの検索条件も「完全一致」とし、比較条件が「あいまい一致」であれば、ｎ−ｇｒａｍ及びインデックス一致数ｃを用いた粗絞りのあいまい検索条件を定義する。
【００８４】
ステップＳ４０１にて粗絞り定義生成部１１１は、生成した初期の粗絞り定義にあいまい条件が含まれているか否かを判断する。この判断結果が「ＮＯ」であれば処理を終了し、初期の粗絞り定義をそのまま最終的な粗絞り定義１２４とする。
【００８５】
ステップＳ４０１の判断結果が「ＹＥＳ」であった場合には、ステップＳ４０２にて名寄せ部１１４が名寄せ元ＤＢ１２１にあるレコードをいくつかサンプリングする。上述したようにサンプリングは、名寄せ元のレコードを分析して、サンプリングされたレコードになるべく偏りがないように行う。図示していないが、サンプリングされた名寄せ元のレコードは揮発性記憶部１３に保存される。
【００８６】
ステップＳ４０３にて名寄せ部１１４が、サンプリングしたいくつかのレコードについての粗絞りを伴わない名寄せ、つまり名寄せ試行を行う。名寄せ部１１４は、サンプリングしたレコードとの関係で、名寄せ定義に定義された比較条件の少なくとも１つを満たす名寄せ先のレコードをその比較条件ごとに名寄せ試行結果（図示せず）として揮発性記憶部１３に保存する。
【００８７】
ステップＳ４０４にて粗絞り処理部１１３は、名寄せ部１１４によりサンプリングされたレコードと、現粗絞り定義とを参照し、粗絞り試行を行う。粗絞り試行の結果は、図示しない粗絞り試行結果として揮発性記憶部１３に保存される。
【００８８】
ステップＳ４０５にて粗絞り定義生成部１１１は、揮発性記憶部１３に保存されている名寄せ試行結果と粗絞り試行結果とを参照する。そして、粗絞り定義生成部１１１は、図１６（Ａ）及び（Ｂ）に示したような粗絞り適合率及び漏れ率を算出する。
【００８９】
ステップＳ４０６にて粗絞り定義生成部１１１はステップＳ４０５にて算出した漏れ率が０％か否かをチェックする。チェック結果が「ＹＥＳ」であればステップＳ４０７に進む。チェック結果が「ＮＯ」であればステップＳ４０９に進み、現粗絞り定義の１つ前の粗絞り定義を現粗絞り定義として、ステップＳ４１０に進む。なお、初期の粗絞り定義に関しては漏れ率が必ず０％となるため、ステップＳ４０６のチェック結果は必ず「ＹＥＳ」となる。
【００９０】
ステップＳ４０７にて粗絞り定義生成部１１１は、ステップＳ４０５にて算出した粗絞り適合率が１００％か否かをチェックする。このチェック結果が「ＹＥＳ」であればステップＳ４１０に進み、さもなければステップＳ４０８に進む。
【００９１】
ステップＳ４０８にて粗絞り定義生成部１１１は、現粗絞り定義に定義されているあいまい検索条件の中でチューニング対象となっているものがあるか否かを判断する。この判断結果が「ＹＥＳ」であればステップＳ４１２に進み、さもなければステップＳ４１０に進む。
【００９２】
ステップＳ４１０にて粗絞り定義生成部１１１は、現粗絞り定義に定義されているあいまい検索条件の中でまだチューニングがなされていないものがあるか否かを判断する。この判断結果が「ＹＥＳ」であればステップＳ４１１に進む。
【００９３】
ステップＳ４１１にて粗絞り定義生成部１１１は、まだチューニングがなされていないあいまい検索条件のうちの１つをチューニング対象として選ぶ。
【００９４】
ステップＳ４１２にて粗絞り定義生成部１１１は、チューニング対象のあいまい検索条件を、より絞り込める条件に変更する。具体的には、図１７を参照して説明したように、チューニング対象のあいまい検索条件に含まれるｎ−ｇｒａｍのｎに１を加えてｎ’を算出する。続いて、このｎ’及びインデックス一致数ｃを元にしてｃ’を算出する。
【００９５】
ステップＳ４１３にて粗絞り定義生成部１１１は、あいまい検索条件を変更することができるか否かを判断する。具体的にはｎ’＝ｎ＋１が、図１５を参照して説明したｎ−ｇｒａｍのｎの最大値以下であり、かつｃ’が０より大きい場合に、変更可能と判断する。この場合は、ｎ’及びｃ’を新たなｎ及びｃとして新たなあいまい検索条件を作成する。もし変更が不可能な場合には、ｃ’＝ｃ＋１として新たなあいまい検索条件を作成する。そして、この新たなあいまい検索条件を含んだ新たな粗絞り定義を作成し、ステップＳ４０４以降を繰り返す。つまり、初期の粗絞り定義におけるｎやｃをどの程度大きくできるかは、ステップＳ４０３における名寄せ試行結果とステップＳ４０４における粗絞り試行結果とに基づいて定められる。そして、ステップＳ４１３の判断結果がいずれ「ＮＯ」となり、ステップＳ４１０に進む。
【００９６】
そして、ステップＳ４１０の判断結果がいずれ「ＮＯ」となり、処理を終了する。このときの粗絞り定義がそのまま最終的な粗絞り定義１２４となる。
【００９７】
［７．他の実施形態］
図３に示した名寄せ定義においては、比較する名寄せ元のカラムと名寄せ先のカラムの組み合わせ１つにつき、１つの比較条件を定義した。しかし、他の形態では、比較する名寄せ元のカラムと名寄せ先のカラムの組み合わせ１つにつき、複数の比較条件を定義することができる。
【００９８】
図２０のステップＳ４１２では、ｎを１だけ大きくすることに限られず、ｎを２だけ、３だけあるいはそれ以上の値だけ大きくしてもよい。
【００９９】
前述した情報処理装置の機能的構成及び物理的構成は、前述の態様に限られるものではなく、例えば、各機能や物理資源を統合して実装したり、逆に、さらに分散して実装したりすることも可能である。
【０１００】
以上の実施形態に関し、さらに以下の付記を開示する。
（付記１）
所定の文字列との間の編集距離が所定数以下の文字列を文字列群から抽出する抽出プログラムであって、
前記所定の文字列内の連続する文字列である１または複数の部分文字列であって、前記所定の文字列において連続する文字数が前記所定の文字列の文字数を前記所定数で除算した商よりも小さい、１または複数の部分文字列を抽出し、
抽出された前記１または複数の部分文字列のいずれかを含む文字列を前記文字列群から抽出し、
前記文字列群から抽出された文字列について、前記所定の文字列との間の編集距離が所定の距離以下であるか否か判定する、
処理をコンピュータに実行させる抽出プログラム。
（付記２）
前記所定の文字列との間の編集距離が前記所定数以下の文字列は、
前記所定の文字列に対して前記所定数以下の編集回数の編集を行なうことにより得られ
る文字列である、
ことを特徴とする付記１に記載の抽出プログラム。
（付記３）
前記コンピュータに、
前記１または複数の部分文字列のうち、前記所定の文字列の文字数及び１の和から、前記所定数及び１の和と前記商よりも小さい自然数との積を引いた差以下の部分文字列を含む文字列を、前記文字列群から抽出する、
ことを実行させることを特徴とする付記１に記載の抽出プログラム。
（付記４）
所定の文字列との間の編集距離が所定数以下の文字列を文字列群から抽出する抽出方法であって、
前記所定の文字列内の連続する文字列である１または複数の部分文字列であって、前記所定の文字列において連続する文字数が前記所定の文字列の文字数を前記所定数で除算した商よりも小さい、１または複数の部分文字列を抽出し、
抽出された前記１または複数の部分文字列のいずれかを含む文字列を前記文字列群から抽出し、
前記文字列群から抽出された文字列について、前記所定の文字列との間の編集距離が所定の距離以下であるか否か判定する、
処理をコンピュータに実行させる抽出方法。
（付記５）
前記所定の文字列との間の編集距離が前記所定数以下の文字列は、
前記所定の文字列に対して前記所定数以下の編集回数の編集を行なうことにより得られる文字列である、
ことを特徴とする付記４に記載の抽出方法。
（付記６）
前記コンピュータに、
前記１または複数の部分文字列のうち、前記所定の文字列の文字数及び１の和から、前記所定数及び１の和と前記商よりも小さい自然数との積を引いた差以下の部分文字列を含む文字列を、前記文字列群から抽出する、
ことを実行させることを特徴とする付記４に記載の抽出方法。
（付記７）
所定の文字列との間の編集距離が所定数以下の文字列を文字列群から抽出する抽出装置であって、
前記所定の文字列内の連続する文字列である１または複数の部分文字列であって、前記所定の文字列において連続する文字数が前記所定の文字列の文字数を前記所定数で除算した商よりも小さい、１または複数の部分文字列を抽出する第１の抽出手段と、
抽出された前記１または複数の部分文字列のいずれかを含む文字列を前記文字列群から抽出する第２の抽出手段と、
前記文字列群から抽出された文字列について、前記所定の文字列との間の編集距離が所定の距離以下であるか否か判定する判定手段と、
を含むことを特徴とする抽出装置。
（付記８）
前記所定の文字列との間の編集距離が前記所定数以下の文字列は、
前記所定の文字列に対して前記所定数以下の編集回数の編集を行なうことにより得られる文字列である、
ことを特徴とする付記７に記載の抽出装置。
（付記９）
前記第２の抽出手段が、
前記１または複数の部分文字列のうち、前記所定の文字列の文字数及び１の和から、前記所定数及び１の和と前記商よりも小さい自然数との積を引いた差以下の部分文字列を含
む文字列を、前記文字列群から抽出する、
ことを特徴とする付記７に記載の抽出装置。
【符号の説明】
【０１０１】
１  情報処理装置
１１  制御部
１２  不揮発性記憶部
１３  揮発性記憶部
１００  名寄せ元
１０１  名寄せ先
１０２  粗絞り処理
１０２ａ  粗絞り定義
１０２ｂ  検索結果
１０３  名寄せ処理
１０３ａ  名寄せ定義
１１１  粗絞り定義生成部
１１３  粗絞り処理部
１１４  名寄せ部
１２１  名寄せ元ＤＢ
１２２  名寄せ先ＤＢ
１２３  名寄せ定義
１２４  粗絞り定義
１３１  粗絞り処理結果
１３２  名寄せ処理結果
１０１０  ＣＰＵ
１０２０  インタフェース装置
１０３０  表示装置
１０４０  入力装置
１０５０  ドライブ装置
１０６０  補助記憶装置
１０７０  メモリ装置
１０８０  バス
１０９０  記録媒体
ｍ  比較元の文字列の最小字数（第１の数）
ｎ  「ｎ−ｇｒａｍ」のｎの値（第２の数）
ｃ  インデックス一致数（第３の数）
ｄ  「編集距離ｄ字違い以内」のｄ（第４の数）
ｒ  「編集距離比率ｒ以内」のｒ
【図１】
0005780036.tif 000002
【図２】
0005780036.tif 000003
【図３】
0005780036.tif 000004
【図４】
0005780036.tif 000005
【図５】
0005780036.tif 000006
【図６】
0005780036.tif 000007
【図７】
0005780036.tif 000008
【図８】
0005780036.tif 000009
【図９】
0005780036.tif 000010
【図１０】
0005780036.tif 000011
【図１１】
0005780036.tif 000012
【図１２】
0005780036.tif 000013
【図１３】
0005780036.tif 000014
【図１４】
0005780036.tif 000015
【図１５】
0005780036.tif 000016
【図１６】
0005780036.tif 000017
【図１７】
0005780036.tif 000018
【図１８】
0005780036.tif 000019
【図１９】
0005780036.tif 000020
【図２０】
0005780036.tif 000021