(57)【要約】【課題】代表度の閾値の設定／調整を必要とせずに、実質的に同一とみなされる情報群から、その内容を要約するに適切な数の代表情報を選択することができる代表情報選択技術を提供すること。【解決手段】代表情報を除く各情報が少なくとも一つ以上の代表情報と所定類似度以上の関係となるように代表情報を選択する。文書D3、文書D5、文書D10の３つの文書を代表文書として選択すれば、文書D1と文書D2とは代表文書D3と類似度閾値以上の関係にあり、文書D4は代表文書D3、D5と類似度閾値以上の関係にあり、文書D6と文書D7と文書8と文書D9とは代表文書D5と類似度閾値以上の関係にあり、文書D11と文書D12と文書13と文書D14とは代表文書D10と類似度閾値以上の関係にあり、代表文書を除く各文書が少なくとも一つ以上の代表文書と類似度閾値以上の関係となる。【選択図】図３
2008071136.tif 000002
【特許請求の範囲】
【請求項１】
少なくとも一つ以上の情報と所定の類似度以上となり、前記所定の類似度以上の情報を介して他の情報とも類似とみなされる情報の集合である同一情報グループから、前記同一情報グループを代表する代表情報を選択する代表情報選択方法であって、
代表情報を除く各情報が少なくとも一つ以上の代表情報と所定類似度以上の関係となるように代表情報を選択することを特徴とする代表情報選択方法。
【請求項２】
代表情報を除く各情報が少なくとも一つ以上の代表情報と所定類似度以上の関係となるまで、所定類似度以上の関係となる情報が多い順に代表情報を選択することを特徴とする請求項１に記載の代表情報選択方法。
【請求項３】
代表情報を除く各情報が少なくとも一つ以上の代表情報と所定類似度以上の関係となるまで、所定類似度以上の関係となる情報との重みの総和が大きい順に代表情報を選択することを特徴とする請求項１に記載の代表情報選択方法。
【請求項４】
前記情報が文書であることを特徴とする請求項１から請求項３のいずれかに記載の代表情報選択方法。
【請求項５】
類似度の計算対象となる情報群で共通して適用される、情報を構成する情報要素の優先順位を決定し、
情報の対である情報対が少なくとも所定の類似度以上となるために、情報間で前記情報要素が共通する割合を求め、
前記割合に基づく、各情報の情報要素の選択数を決定し、
前記優先順位に従って、前記各情報から前記選択数の情報要素を選択し、
選択した情報要素が情報間で全て共通しない情報対以外の情報対に対して、類似度の計算を行い、
計算の結果、所定の類似度以上となる情報対を同一情報グループとする
ことを特徴とする請求項１から請求項４のいずれかに記載の代表情報選択方法。
【請求項６】
前記情報が文書であり、前記情報要素が前記文書に含まれる単語または文字であることを特徴とする請求項５に記載の代表情報選択方法。
【請求項７】
少なくとも一つ以上の情報と所定の類似度以上となり、前記所定の類似度以上の情報を介して他の情報とも類似とみなされる情報の集合である同一情報グループから、前記同一情報グループを代表する代表情報を選択する代表情報選択システムであって、
代表情報を除く各情報が少なくとも一つ以上の代表情報と所定類似度以上の関係となるように代表情報を選択する代表情報選択手段を有することを特徴とする代表情報選択システム。
【請求項８】
前記代表情報選択手段は、代表情報を除く各情報が少なくとも一つ以上の代表情報と所定類似度以上の関係となるまで、所定類似度以上の関係となる情報が多い順に代表情報を選択することを特徴とする請求項７に記載の代表情報選択システム。
【請求項９】
前記代表情報選択手段は、代表情報を除く各情報が少なくとも一つ以上の代表情報と所定類似度以上の関係となるまで、所定類似度以上の関係となる情報との重みの総和が大きい順に代表情報を選択することを特徴とする請求項７に記載の代表情報選択システム。
【請求項１０】
前記情報が文書であることを特徴とする請求項７から請求項９のいずれかに記載の代表情報選択システム。
【請求項１１】
類似度の計算対象となる情報群で共通して適用され、情報を構成する情報要素の優先順位が格納された優先順位記憶部と、
前記情報の対である情報対が少なくとも所定の類似度以上となるために、情報間で前記情報要素が共通する割合を求め、この割合に基づいた各情報の情報要素の選択数を決定し、前記優先順位に従って、前記各情報から前記選択数の情報要素を選択する情報要素選択手段と、
選択した情報要素が情報間で全て共通しない情報対以外の情報対に対して、類似度の計算を行い、決算の結果、所定の類似度以上となる情報対を同一情報グループとする同一情報グループ生成手段と
を有することを特徴とする請求項７から請求項１０のいずれかに記載の代表情報選択システム。
【請求項１２】
前記情報が文書であり、前記情報要素が前記文書に含まれる単語または文字であることを特徴とする請求項１１に記載の代表情報選択システム。
【請求項１３】
同一文書照合システムであって、
所定の類似度以上となる文書の対の関係を示す文書対が格納された同一文書グループ記憶手段と、
前記同一文書グループ記憶手段に格納された文書対に従って、代表文書を除く各文書が少なくとも一つ以上の代表文書と対の関係にあるように、代表文書を選択する代表文書選択手段と
を有することを特徴とする同一文書照合システム。
【請求項１４】
前記代表文書選択手段は、代表文書を除く各文書が少なくとも一つ以上の代表文書と対の関係となるまで、対の関係となる文書が多い順に代表文書を選択することを特徴とする請求項１３に記載の同一文書照合システム。
【請求項１５】
前記代表情報選択手段は、代表文書を除く各文書が少なくとも一つ以上の代表文書と対の関係となるまで、対の関係となる文書との重みの総和が大きい順に代表文書を選択することを特徴とする請求項１３に記載の同一文書照合システム。
【請求項１６】
単語または文字で識別され、実質的に同一の候補である文書のグループである同一文書候補グループと、そのグループに属する文書との対応関係が記憶される同一文書候補グループ記憶部と、
文書間で少なくとも所定の類似度閾値以上となるために、文書間で単語または文字が共通する割合を求め、この割合に基づいて、文書照合の対象となるすべての文書間で共通する優先順位で単語または文字を選択し、選択したそれぞれの単語または文字で識別される同一文書候補グループにその文書を対応付けて前記同一文書候補グループ記憶部に記憶する同一文書候補グループ作成手段と、
前記同一文書候補グループ記憶部に記憶されている同一の同一文書候補グループに対応付けられた２つの異なる文書の対である文書対に対して類似度を計算し、この類似度が前記類似度閾値以上の文書対を前記同一文書グループ記憶部に登録する同一文書グループ作成手段と
を有することを特徴とする請求項１３から請求項１５のいずれかに記載の同一文書照合システム。
【請求項１７】
少なくとも一つ以上の情報と所定の類似度以上となり、前記所定の類似度以上の情報を介して他の情報とも類似とみなされる情報の集合である同一情報グループから、前記同一情報グループを代表する代表情報を選択する代表情報選択プログラムであって、
代表情報を除く各情報が少なくとも一つ以上の代表情報と所定類似度以上の関係となるように代表情報を選択する処理を情報処理装置に実行させることを特徴とする代表情報選択プログラム。
【請求項１８】
同一文書照合のプログラムであって、
所定の類似度以上となる文書の対の関係を示す文書対に従って、代表文書を除く各文書が少なくとも一つ以上の代表文書と対の関係にあるように、代表文書を選択する処理を情報処理装置に実行させることを特徴とする同一文書照合のプログラム。
【請求項１９】
与えられた情報間で実質的に同一の情報群がグルーピングされた同一情報グループから代表情報群を選択する代表情報群選択方法であって、
代表情報群と前記代表情報群との類似度が所定の類似度閾値以上になる情報群とを合わせた情報群が、同一情報グループの情報群と一致するように同一情報グループから代表情報群を選択することを特徴とする代表情報群選択方法。
【請求項２０】
既に選択された代表情報群と前記代表情報群との類似度が所定の類似度閾値以上となる情報群とを、同一情報グループの情報群から除いた残りの情報群の最も多くと類似度が前記所定の類似度閾値以上になる情報を、代表情報として選択し、
残りの情報群がなくなるまで繰り返し、代表情報を選択する
ことを特徴とした請求項１９に記載の代表情報群選択方法。
【請求項２１】
既に選択された代表情報群と前記代表情報群との類似度が所定の類似度閾値以上となる情報群とを、同一情報グループの情報群から除いた残りの情報群との重みの総和が最も大きい情報を、代表情報として選択し、
残りの情報群がなくなるまで繰り返し、代表情報を選択する
ことを特徴とした請求項１９に記載の代表情報群選択方法。
【請求項２２】
前記情報が文書であることを特徴とする請求項１９から請求項２１のいずれかに記載の代表情報選択方法。
【請求項２３】
与えられた情報間で実質的に同一の情報群がグルーピングされた同一情報グループから代表情報群を選択する代表情報群選択システムであって、
代表情報群と前記代表情報群との類似度が所定の類似度閾値以上になる情報群とを合わせた情報群が、同一情報グループの情報群と一致するように同一情報グループから代表情報群を選択する代表情報群選択手段を備えることを特徴とする代表情報群選択システム。
【請求項２４】
前記代表情報群選択手段は、
既に選択された代表情報群と前記代表情報群との類似度が所定の類似度閾値以上となる情報群とを、同一情報グループの情報群から除いた残りの情報群の最も多くと類似度が前記所定の類似度閾値以上になる情報を、代表情報として選択し、
残りの情報群がなくなるまで繰り返し、代表情報を選択する
ように構成されていることを特徴とした請求項２３に記載の代表情報群選択システム。
【請求項２５】
前記代表情報群選択手段は、
既に選択された代表情報群と前記代表情報群との類似度が所定の類似度閾値以上となる情報群とを、同一情報グループの情報群から除いた残りの情報群との重みの総和が最も大きい情報を、代表情報として選択し、
残りの情報群がなくなるまで繰り返し、代表情報を選択する
ように構成されていることを特徴とした請求項２３に記載の代表情報群選択システム。
【請求項２６】
前記情報が文書であることを特徴とする請求項２３から請求項２５のいずれかに記載の代表情報選択システム。
【請求項２７】
与えられた情報間で実質的に同一の情報群がグルーピングされた同一情報グループから代表情報群を選択するプログラムであって、
代表情報群と前記代表情報群との類似度が所定の類似度閾値以上になる情報群とを合わせた情報群が、同一情報グループの情報群と一致するように同一情報グループから代表情報群を選択する処理を情報処理装置に実行させることを特徴とするプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、与えられた情報間で実質的に同一の情報群から、それを代表する代表情報を選択する技術に関し、特に、代表度の閾値の設定／調整を必要とせずに、情報群の内容全体を要約する適切な数の代表情報を選択できる代表情報選択方法、代表情報選択システム及びプログラムに関する。
【背景技術】
【０００２】
文書、画像等の情報の同一性又は類似度を判断する技術は数多く提案されており、その中でも、文書の同一性を判断する同一文書照合の技術が有名である。同一文書照合とは、文書間で実質的に同一の文書群をグルーピングすることを言う。実質的に同一であるとは、表記上は異なるが人が見れば同一と判断できることをいう。
（１）  データベース（以下、DBと称する）の重複レコード照合
DBの重複レコード照合は、DB内の実質的に同じレコードをグルーピングすることをいい、例えば、異なる人／場所／方法によって管理された表記のゆれを含む顧客DBを統合する際のデータクリーニングやコンタクトセンターの問い合わせ事例の重複削除に必要となる。１レコードを１文書とみなすことで同一文書照合の問題とみなすことができる。
（２）  トピック分析
トピック分析は、Blogなどの書き込みデータをグルーピングすることをいい、Blogで同じトピックが、いつ／どのあたりで話題になっているかを把握するために必要となる。
【０００３】
同一文書照合システムは、対象となる文書集合と、実質的に同一とみなす条件である類似度閾値を入力として、同一文書グループを出力する。例えば、図１の（ａ）のような５つの文書と、類似度閾値として９０％が入力された場合で説明する。ここでは、全ての文書はそれぞれ１０個のアルファベットの文字から構成されており、また、文書xと文書yの類似度が９０％であるとは、xとyの１０個の文字のうち９個が共通することを意味する。この時システムは、図１の（ｂ）のように、まず類似度が９０％以上となる２つの異なる文書の対を求め、その後、共通する文書を含む文書対を統合した図１の（ｃ）を同一文書グループとする。
【０００４】
同一文書照合では、ぞれぞれの同一文書グループの代表文書を選択する。代表文書とは、その同一文書グループの全体の内容を最も適切に要約する文書を意味する。代表文書は、（１）のDBの重複レコード照合では、重複レコードの中で代表として残すレコードの候補として活用できる。また、（２）のトピック分析では、各トピック（同一文書グループ）の概要把握のために活用できる。
【０００５】
同一文書照合の際に各同一文書グループから代表文書を選択する方法として、従来は同一文書グループに所属する個々の文書の代表度を計算し、代表度が最大の文書を代表文書としていた。例えば、特許文献１の代表度算出部２５８では、各同一文書グループ（クラスタ）の個々の文書について、文書に含まれる単語の重みの総和を代表度として求め、その代表度が最大の文書を代表文書として選択する。特許文献２の代表文選択部１６では、各同一文書グループに所属する最も類似度が高い文書対の内で、文書に含まれる単語の重みの総和が大きい一方を代表文書として選択する。単語の重みは、その単語が出現する文書数で定義されている。
【特許文献１】特開２００３−３０２２４号公報
【特許文献２】特開２００３−２６３４４３号公報
【発明の開示】
【発明が解決しようとする課題】
【０００６】
このような従来の技術の課題は、選択された代表文書が同一文書グループの内容の全体を必ずしも要約しないことである。図２は同一文書グループの一例を示す。それぞれの円（D1からD14）は、同一文書グループに所属する文書を表し、類似度が閾値以上の文書対には実線を引いている。特許文献１や特許文献２の方法は、各文書に含まれる単語の種類によってD1からD14のいずれも代表文書として選択される可能性がある。しかし、仮にD1が選択された場合、D1と類似度が閾値以上の文書はD3のみなので、その他の文書はD1とは内容が異なり、D1がグループの内容全体を要約しないことになる。
【０００７】
また、従来の技術の他の課題は、各同一文書グループから複数の代表文書を選択するためには、代表度の閾値を設定／調整する必要があることである。図２の例から分かるように、同一文書グループは全ての文書間の類似度が閾値以上になるとは限らないので、複数の代表文書によってグループの内容全体を要約することがある。しかし、特許文献１や特許文献２の方法を用いて代表文書を複数選択するためには、代表度の閾値を設定／調整する必要がある。全てのグループで適切な数の代表文書を選択するような閾値を設定するのは困難である。
【０００８】
そこで、本発明は上記課題に鑑みて発明されたものであって、その目的は、代表度の閾値の設定／調整を必要とせずに、実質的に同一とみなされる情報群から、その内容を要約するに適切な数の代表情報を選択することができる代表情報選択方法、代表情報選択システム及びプログラムを提供することにある。
【課題を解決するための手段】
【０００９】
また、本発明の目的は、代表度の閾値の設定／調整を必要とせずに、実質的に同一とみなされる同一文書グループの内容全体を要約するに適切な数の代表文書を選択することができる同一文書照合システム及びプログラムを提供することにある。
【００１０】
上記課題を解決する本発明は、少なくとも一つ以上の情報と所定の類似度以上となり、前記所定の類似度以上の情報を介して他の情報とも類似とみなされる情報の集合である同一情報グループから、前記同一情報グループを代表する代表情報を選択する代表情報選択方法であって、代表情報を除く各情報が少なくとも一つ以上の代表情報と所定類似度以上の関係となるように代表情報を選択することを特徴とする。
【００１１】
上記課題を解決する本発明は、少なくとも一つ以上の情報と所定の類似度以上となり、前記所定の類似度以上の情報を介して他の情報とも類似とみなされる情報の集合である同一情報グループから、前記同一情報グループを代表する代表情報を選択する代表情報選択システムであって、代表情報を除く各情報が少なくとも一つ以上の代表情報と所定類似度以上の関係となるように代表情報を選択する代表情報選択手段を有することを特徴とする。
【００１２】
上記課題を解決する本発明は、同一文書照合システムであって、所定の類似度以上となる文書の対の関係を示す文書対が格納された同一文書グループ記憶手段と、前記同一文書グループ記憶手段に格納された文書対に従って、代表文書を除く各文書が少なくとも一つ以上の代表文書と対の関係にあるように、代表文書を選択する代表文書選択手段とを有することを特徴とする。
【００１３】
上記課題を解決する本発明は、少なくとも一つ以上の情報と所定の類似度以上となり、前記所定の類似度以上の情報を介して他の情報とも類似とみなされる情報の集合である同一情報グループから、前記同一情報グループを代表する代表情報を選択する代表情報選択プログラムであって、代表情報を除く各情報が少なくとも一つ以上の代表情報と所定類似度以上の関係となるように代表情報を選択する処理を情報処理装置に実行させることを特徴とする。
【００１４】
上記課題を解決する本発明は、同一文書照合のプログラムであって、所定の類似度以上となる文書の対の関係を示す文書対に従って、代表文書を除く各文書が少なくとも一つ以上の代表文書と対の関係にあるように、代表文書を選択する処理を情報処理装置に実行させることを特徴とする。
【００１５】
上記課題を解決する本発明は、与えられた情報間で実質的に同一の情報群がグルーピングされた同一情報グループから代表情報群を選択する代表情報群選択方法であって、代表情報群と前記代表情報群との類似度が所定の類似度閾値以上になる情報群とを合わせた情報群が、同一情報グループの情報群と一致するように同一情報グループから代表情報群を選択することを特徴とする。
【００１６】
上記課題を解決する本発明は、与えられた情報間で実質的に同一の情報群がグルーピングされた同一情報グループから代表情報群を選択する代表情報群選択システムであって、代表情報群と前記代表情報群との類似度が所定の類似度閾値以上になる情報群とを合わせた情報群が、同一情報グループの情報群と一致するように同一情報グループから代表情報群を選択する代表情報群選択手段を備えることを特徴とする。
【００１７】
上記課題を解決する本発明は、与えられた情報間で実質的に同一の情報群がグルーピングされた同一情報グループから代表情報群を選択するプログラムであって、代表情報群と前記代表情報群との類似度が所定の類似度閾値以上になる情報群とを合わせた情報群が、同一情報グループの情報群と一致するように同一情報グループから代表情報群を選択する処理を情報処理装置に実行させることを特徴とする。
【発明の効果】
【００１８】
本発明の効果は、代表度の閾値の設定／調整を必要とせずに、各同一情報グループの内容全体を要約する適切な数の代表情報を選択することが可能なことである。選択された代表情報群が同一文書グループの内容全体を要約することができる理由は、同一情報グループの情報群は、代表情報群のいずれかとの類似度が必ず類似度閾値以上になるからである。また、代表度の閾値の設定／調整を必要とせずに同一文書グループの代表情報を選択することができる理由は、類似度が閾値以上となる情報対のみを与えれば自動的に代表文書が決定されるからである。
【発明を実施するための最良の形態】
【００１９】
まず、本発明の概要を説明する。尚、以下の説明にあたって、文書を情報の例として説明するが、これに限られない。例えば、情報の例としては画像、音等でも良い。
【００２０】
本発明では、少なくとも一つ以上の情報と所定の類似度以上となり、所定の類似度以上の情報を介して他の情報とも類似とみなされる情報の集合である同一情報グループから、同一情報グループを代表する代表情報を選択する際、代表情報を除く各情報が少なくとも一つ以上の代表情報と所定類似度以上の関係となるように代表情報を選択することを特徴とする。
【００２１】
例えば、図２では文書を情報の例として説明しており、文書D1から文書D14がひとつの同一文書グループを構成している。各文書D1−D14は、少なくとも一つ以上の文書と所定の類似度以上である。以下、所定の類似度以上にある文書の組を文書対と称する。また、ひとつの文書は、文書対となる文書を介して他の文書と類似の関係にあると推定される。但し、文書対となる文書を介して類似の関係にあると推定される文書は、かならずしも所定の類似度以上になるとは限らない。例えば、文書D1は文書D3と文書対の関係にあり、文書D1と文書D3との類似度は所定の類似度（以下、類似度閾値と称する）以上である。しかし、文書D3と文書対の関係にある文書D4と文書D1との類似度は類似度閾値以上であるとは限らない。
【００２２】
このような同一文書グループから、同一文書グループを代表する代表文書を選択する際、代表文書を除く各文書が少なくとも一つ以上の代表文書と類似度閾値以上の関係となるように、すなわち、文書対の関係となるように代表文書を選択する。
【００２３】
これは、代表文書群と、この代表文書群との類似度が類似度閾値以上になる文書群とを合わせた文書群が、同一文書グループの文書群と一致することも意味する。
【００２４】
具体的には、図３のように文書D3、文書D5、文書D10の３つの文書を代表文書として選択すれば、文書D1と文書D2とは代表文書D3と類似度閾値以上の関係にあり、文書D4は代表文書D3、D5と類似度閾値以上の関係にあり、文書D6と文書D7と文書8と文書D9とは代表文書D5と類似度閾値以上の関係にあり、文書D11と文書D12と文書13と文書D14とは代表文書D10と類似度閾値以上の関係にあり、代表文書を除く各文書が少なくとも一つ以上の代表文書と類似度閾値以上の関係となる。
【００２５】
また、代表文書群（文書D3、文書D5、文書D10）と、この代表文書群と類似度閾値以上の関係にある文書群（文書D1、文書D2、文書D4、文書D6、文書D7、文書8、文書D9、文書D11、文書D12、文書13、文書D14）とを合わせた文書群（文書D1から文書D14）が、同一文書グループの文書群（文書D1から文書D14）とも一致している。
【００２６】
このようにするとこにより、同一文書グループの文書群は、代表文書群のいずれかとの類似度が必ず類似度閾値以上になるので、選択された代表文書群は同一文書グループの内容全体を要約することができる。
【００２７】
また、類似度が閾値以上となる情報対のみを与えれば自動的に代表文書が決定されので、代表度の閾値の設定／調整を必要とせずに同一文書グループの代表文書を選択することができる。
【００２８】
ここで、代表文書の選択の順序であるが、類似度閾値以上の関係となる文書が多い順に、すなわち、多くの文書と文書対となっている文書から代表文書を選択し、選択された代表文書を除く各文書が少なくとも一つ以上の代表文書と文書対の関係となるまで代表文書の選択を行う方法が考えられる。すなわち、既に選択された代表文書群と前記代表文書群との類似度が所定の類似度閾値以上となる文書群とを、同一文書グループの文書群から除いた残りの文書群の最も多くと類似度が前記所定の類似度閾値以上になる情報を、代表文書として選択し、残りの文書群がなくなるまで繰り返し、代表文書を選択するのである。
【００２９】
図３の例では、文書D5は、文書D3、文書D4、文書D6、文書D7、文書D8、文書D9、文書D10の７個の文書と文書対の関係にあり、最も多くの文書と文書対の関係にあるので、文書D5を第１の代表文書として選択する。第１の代表文書として文書D5を選択した時点では、代表文書D5と文書対の関係となっていない文書D1、文書D2、文書D11、文書D12、文書D13、文書D14が存在する。すなわち、同一グループ文書の文書群から、代表文書群（文書D5）と、この代表文書群（文書D5）と所定の類似度閾値以上の文書群（文書D3、文書D4、文書D6、文書D7、文書D8、文書D9、文書D10）とを引いた残りの文書群（文書D1、文書D2、文書D11、文書D12、文書D13、文書D14）が存在する。そこで、代表文書の選択を続ける。
【００３０】
文書D10は、代表文書D5と文書対の関係となっていない文書D1、文書D2、文書D11、文書D12、文書D13、文書D14のうち、文書D11、文書D12、文書D13、文書D14の４個の文書と文書対の関係にあり、文書D5の次に多くの文書と文書対の関係にあるので、文書D10を第２の代表文書として選択する。第１、第２の代表文書として文書D5、文書D10を選択した時点では、代表文書D5と文書D10とのいずれかの代表文書とも文書対の関係となっていない文書D1、文書D2が存在する。すなわち、同一グループ文書の文書群から、代表文書群（文書D5、文書D10）と、この代表文書群（文書D5、文書D10）と所定の類似度閾値以上の文書群（文書D3、文書D4、文書D6、文書D7、文書D8、文書D9、文書D10、文書D11、文書D12、文書D13、文書D14）とを引いた残りの文書群（文書D1、文書D2）が存在する。そこで、代表文書の選択を続ける。そこで、代表文書の選択を続ける。
【００３１】
文書D3は、代表文書D5と文書D10とのいずれかの代表文書とも文書対の関係となっていない文書D1、文書D2と文書対の関係にあり、文書D5、D10の次に多くの文書と文書対の関係にあるので、文書D3を第３の代表文書として選択する。第１、第２、第３の代表文書として文書D5、文書D10、文書D3を選択した時点では、代表文書を除く各文書が、代表文書D5と代表文書D10と代表文書D3との少なくともいずれかの代表文書と文書対の関係となっている。すなわち、同一グループ文書の文書群から、代表文書群（文書D5、文書D10、文書D3）と、この代表文書群（文書D5、文書D10、文書D3）と所定の類似度閾値以上の文書群（文書D1、文書D2、文書D3、文書D4、文書D6、文書D7、文書D8、文書D9、文書D10、文書D11、文書D12、文書D13、文書D14）とを引くと、文書群は存在しない。そこで、代表文書の選択を終了し、この文書グループの代表文書として、文書D5、文書D10、文書D3を選択する。
【００３２】
このように、多くの文書と文書対にある文書を代表文書として選択していくので、同一文書グループの内容をより適切に表現できる代表文書を選択できる。
【００３３】
尚、代表文書を選択する方法として、文書対に重みがある場合、この重みを考慮するようにしても良い。例えば、ある文書対では重みが１０、他の文書対では重みが１のように各文書対に重みがある場合、文書対に重みの総和が最も大きい文書順に、代表文書を選択するようにしても良い。
【００３４】
以下、本発明の実施の形態を詳細に説明する。
【００３５】
本発明の第１の実施の形態を説明する。
【００３６】
図５を参照すると、本発明の第１の実施の形態は、プログラム制御により動作するデータ処理装置１と、同一文書グループ記憶部５と、代表文書記憶部６から構成されている。
【００３７】
同一文書グループ記憶部５は、同一文書グループと文書との対応関係と、類似度閾値以上となる文書対を格納している。代表文書記憶部６は、同一文書グループと代表文書と代表度の対応関係を格納している。データ処理装置１は、代表文書選択手段１３を含む。
【００３８】
代表文書選択手段１３は、同一文書グループから、代表文書を除く各文書が少なくとも一つ以上の代表文書と類似度閾値以上の関係となるように、すなわち、文書対の関係となるように代表文書を選択する。これは、代表文書群とそれらとの類似度が類似度閾値以上になる文書群を合わせた文書群が、同一文書グループの文書群と一致するように代表文書群を選択するともいえる。
【００３９】
次に、図６を参照して第１の実施の形態の動作について詳細に説明する。
【００４０】
代表文書選択手段１３は、代表文書を除く各文書が少なくとも一つ以上の代表文書と類似度閾値以上の関係となるように、すなわち、文書対の関係となるように代表文書を選択する（図６のステップS4）。
【００４１】
ここで、図７を参照して、代表文書選択手段１３の動作の詳細を説明する。
【００４２】
まず、同一文書グループ記憶部に格納された同一文書グループをグループi（1＜＝i＜＝n）として、グループi＝１を選択する（図７のステップS41）。図８に同一文書グループ記憶部の例を示す。図８の（ａ）には２つの同一文書グループ（ID1,ID2）とそれぞれに所属する文書IDの対応関係が格納されている。同一文書グループに所属する文書は、必ずその中のいずれかの文書（すべててある必要はない）との類似度が閾値以上になる。図８の（ｂ）には類似度が類似度閾値以上となる文書対が格納されている。
【００４３】
次に、代表文書を除く各文書が少なくとも一つ以上の代表文書と類似度閾値以上の関係となるようにグループiの代表文書群を選択する（図７のステップS42）。図９に代表文書記憶部の格納例を示す。例えば、同一文書グループ記憶部のグループID1の代表文書は、第１の代表文書がID3、第２の代表文書がID5、第３の代表文書がID10であることを示している。
【００４４】
次に、i＞＝nである場合かを判断し（図７のステップS43）し、i＞＝nである場合は処理を終了する。i＜nの場合は、グループi＝グループ｛i＋1｝（図７のステップS44）としてステップS42に戻る。
【００４５】
ここで、グループi＝1である場合を例として、ステップS42の動作の詳細を、図１０を用いて説明する。
【００４６】
まず、未選択代表文書バッファ、未選択文書バッファに同一文書グループ記憶部に格納されたグループiに所属する文書IDを格納し、代表文書番号＝1とする。（図10のステップS421）。図８の同一文書グループ記憶部からグループ１に関する文書ID1−ID14を未選択代表文書バッファ、未選択文書バッファに格納した例を図１１に示す。
【００４７】
次に、未選択代表文書バッファのそれぞれの文書の中で、未選択文書バッファの文書との類似度が閾値以上となる文書対の数が最大の文書を代表文書番号＝iとして選択し、代表文書記憶部６に格納する（図１０のステップS422）。図８の同一文書グループ記憶部のグループ１に関する文書群をグラフ表示したものを図１２に示す。円は文書、実線は類似度が閾値以上となる文書対を示す。この時、類似度閾値以上となる文書対の数が７個と最大の文書である大きな円で囲んだD5が代表文書番号＝１となる。
【００４８】
次に、ステップS422で選択した代表文書を未選択代表文書バッファから削除し、さらにステップS422で選択した代表文書とそれとの類似度が閾値以上の文書を未選択文書バッファから削除する（図１０のステップS423）。図１２の例では、代表文書番号＝１としてD5が選択されたので、D5を未選択代表文書バッファから削除し、さらに、D5および、D5と類似度が閾値以上となるD3,D4,D6,D7,D8,D9,D10を未選択文書バッファから削除する。その結果を図１３に示す。
【００４９】
次に、未選択文書バッファに文書が残っているかを判断し（図１０のステップS424）、残っていない場合は処理を修了する。残っている場合は、代表文書番号＝i＋1としてステップS422に戻る。図１３の未選択文書バッファは空ではないので、ステップS422に戻る。
【００５０】
次に、ステップS422で代表文書番号＝２の代表文書を再度選択し、代表文書記憶部6に格納する。図８の同一文書グループ記憶部のグループ１に関する文書群と図１３のバッファの状態をグラフ表示したものを図１４に示す。大きい円は選択済みの代表文書（未選択代表文書バッファから取り除かれた文書）、色つきの円は選択済みの文書（未選択文書バッファから取り除かれた文書）を示す。この時、代表文書番号＝２として選ばれるのは、図１５のように最も多くの未選択の文書D11,D13,D14,D12と類似度が閾値以上となるD10となる。
【００５１】
次に、ステップS423では、代表文書番号＝２としてD10が選ばれたので、未選択代表文書バッファからD10が削除され、さらに、D10(すでに削除されているが)および、D10と類似度が類似度閾値以上のD11,D13,D14,D12を未選択文書バッファから削除する。その結果を図１６に示す。
【００５２】
次に、未選択文書バッファは空ではないので、ステップS422で代表文書番号＝３の代表文書を再度選択し、代表文書記憶部６に格納する。図１６のバッファの状態をグラフ表示したものを図１７に示す。この時、代表文書番号＝３として選ばれるのは、図１８のように最も多くの未選択の文書D1,D2と類似度が類似度閾値以上となるD3となる。
【００５３】
ステップS423では、代表文書番号＝３としてD3が選ばれたので、未選択代表文書バッファからD3が削除し、さらに、D3(すでに削除されているが)および、D3と類似度が閾値以上となるD1,D2を未選択文書バッファから削除する。その結果を図１９に示す。
【００５４】
ステップS424では、未選択代表文書バッファは空なので処理を終了する。
【００５５】
最終的には、代表文書記憶部６は、図９のように格納される。
【００５６】
以上、代表文書選択手段１３の動作を説明したが、ステップS422において、未選択代表文書バッファのそれぞれの文書の中で、未選択文書バッファの文書との類似度が閾値以上となる文書対の「重みの総和」が最大の文書を代表文書番号＝iとして選択するようにしても良い。この場合、文書対の重みは、同一文書グループ記憶部にあらかじめ登録しておく。図４０にその例を示す。この場合、上述した例では、代表文書番号＝１の代表文書はD5であるが、図４１に示すように、その重みの総和は、２＋１＋１＋１＋１＋２＋２＝１０である。一方、D10の重みの総和は、１＋１＋３＋１＋５＝１１となり最大となるので、代表文書番号＝１の代表文書は、D10となる。
【００５７】
尚、文書対の重みを全て１に設定すると最初のステップS422の動作と同じになる。文書対の重みは、例えば、文書対の類似度が大きいほど大きな値を設定する。
【００５８】
本発明の効果は、代表度の閾値の設定/調整を必要とせずに、各同一文書グループの内容全体を要約する適切な数の代表文書を選択することが可能なことである。選択された代表文書群が同一文書グループの内容全体を要約することができる理由は、同一文書グループの文書群は、代表文書群のいずれかとの類似度が必ず閾値以上になるからである。
【００５９】
また、代表度の閾値の設定/調整を必要とせずに同一文書グループの代表文書を選択することができる理由は、類似度が閾値以上となる情報対のみを与えれば自動的に代表文書が決定されるからである。
【００６０】
第２の実施の形態を説明する。
【００６１】
第１の実施の形態では、同一文書グループ記憶部５に同一文書グループと文書との対応関係と、類似度閾値以上となる文書対とが既に格納されているものとして説明した。第２の実施の形態は、上述した第１の実施の形態の構成に加えて、同一文書グループ記憶部５に同一文書グループと文書との対応関係と、類似度閾値以上となる文書対とを格納するまでの構成を追加したことを特徴とする。
【００６２】
第２の実施の形態の構成の特徴は、類似度の計算対象となる文書群で共通して適用される、文書を構成する文書要素の優先順位を決定し、文書対が少なくとも所定の類似度以上となるために、文書間で文書要素が共通する割合を求め、この割合に基づく、各文書の文書要素の選択数を決定し、前記優先順位に従って、前記各文書から前記選択数の文書要素を選択し、選択した文書要素が文書間で全て共通しない文書対以外の文書対に対して、類似度の計算を行い、計算の結果、所定の類似度以上となる文書対を同一情報グループとすることを特徴とする。尚、文書要素とは、単語群や文字群である。
【００６３】
以下、図４を用いて、第２の実施の形態の特徴の概要を説明する。
【００６４】
尚、以下の説明にあたって、情報の例として文書を、情報要素の例として文字を例にして説明するが、これに限られない。例えば、情報の例としては画像、音等でも良く、それを構成する情報要素としては、画像中の特定の絵柄や、特定の音等が考えられる。
【００６５】
また、以下の説明にあたって、図４に示される文書１から文書５に対して、与えられた類似度閾値９０％であり、類似度が９０％以上にならない文書の組（以下、文書対と称する）を検索する場合を説明する。
【００６６】
まず、５つの文書で共通する文字の優先順位を決める。例えば、図４の（ｄ）のように文書群全体で出現文書数が少ない文字ほど、優先順位が高くなるように定める。尚、出現文書数が同じ場合はアルファベット順で若い文字を優先順位が高くなるように定められているものとする。
【００６７】
次に、文書対が少なくとも類似度９０％以上となるために、文書間で文字が共通する割合を求め、この割合に基づいて、１文書から選択する文字数を決定する。
【００６８】
類似度９０％以上となるためには文書対の文書間で文字が９０％以上共通すれば良い。これは、文書対の文書間で少なくとも９個の文字が共通しなければ、類似度９０％以上にはならないといことである。
【００６９】
別の言い方をすると、文書ｘから選んだ２つの文字のどちらも文書ｙに含まれなければ、文書ｘと文書ｙとは共通する単語が８個以下ということになり、類似度は９０％未満となるということになり、文書ｘと文書ｙとの類似度が９０％以上であるという前提と矛盾する。これは、文書ｙと文書ｘを置き換えた場合でも同様である。従って、１文書から選択する文字数は２個である。尚、本例では、文書１から文書５が１０文字で構成されているため、いずれの文書も選択する文字数が２個であるが、例えば、一文書が５文字で構成されている場合には、選択する文字数は１個である。
【００７０】
続いて、各文書から優先順位に基づいて２個の文字を選択する。図４（ａ）の例では、文書１で選択する文字はＡとＩであり、文書２で選択する文字はＫとＬであり、文書３で選択する文字はＩとＬであり、文書４で選択する文字はＫとＬであり、文書５で選択する文字はＡとＭである。
【００７１】
そして、選択した文字が文書間で全て共通しない文書対を検索する。図４（ａ）の例では、文書１と文書２との文書対では共通する文字がなく、文書１と文書３との文書対ではＩが共通し、文書１と文書４との文書対では共通する文字がなく、文書１と文書５との文書対ではＡが共通する。また、文書２と文書３との文書対ではＬが共通し、文書２と文書４との文書対ではＫとＬとが共通し、文書２と文書５との文書対では共通する文字がない。また、文書３と文書４との文書対ではＬが共通し、文書３と文書５との文書対では共通する文字がない。また、文書４と文書５との文書対では共通する文字がない。従って、共通する文字がない文書対は、文書１と文書２との文書対と、文書１と文書４との文書対と、文書２と文書５との文書対と、文書３と文書５との文書対と、文書４と文書５との文書対との５個である。これらの５個の文書対は、類似度が９０％以上にはならない文書対である。
【００７２】
このようになる理由は、文書ｘと文書ｙとの類似度が９０％以上であるならば、さらに、選ぶ文字の優先順位が全ての文書間で一意に定められているならば、文書ｘ（文書ｙ）から優先順位に従い選んだ２つの文字のいずれかは、文書ｙ（文書ｘ）から選んだ２つの文字のいずれかに含まれるからである。
【００７３】
文書ｘから選んだ２つの文字｛ｘ１，ｘ２｝のいずれかもしくは両方が文書ｙに含まれるが、それが文書ｙから選んだ２つの文字｛ｙ１，ｙ２｝には含まれないとすると、文書ｙにおける文字の優先度は｛ｙ１，ｙ２｝＞｛ｘ１，ｘ２｝となる。この時、｛ｘ１，ｘ２｝∩｛ｙ１，ｙ２｝＝φになるため、同時に、文書ｙから選んだ２つの文字｛ｙ１，ｙ２｝のいずれかもしくは両方が文書ｘに含まれるが、それが文書ｘから選んだ２つの文字｛ｘ１，ｘ２｝には含まれないことになる。この時、文書ｘにおける文字の優先度は｛ｘ１，ｘ２｝＞｛ｙ１，ｙ２｝となる。これは、文書ｘと文書ｙとで選択する文字の優先順位が異なることになり、選ぶ文字の優先順位が全ての文書間で一意に定められていることに矛盾する。文書ｙと文書ｘを置き換えた場合でも同様である。
【００７４】
このように、類似度閾値以上にはならない文書対を検索することができる。
【００７５】
更に、類似度閾値以上にはならない文書対を検索することにより、所定の類似度以上となる文書対の類似度を求めるシステムにおいても、類似度の計算回数を減らすことができる。例えば、図４の例のように、９０％以上の類似度となる文書対の類似度を求める場合、９０％以上の類似度とはならない文書対を類似度計算の対象から外すことにより、類似度の計算回数を減らすことができる。図４の（ａ）の例では、従来の類似度計算においては、類似度計算を（５×４）／（２×１）＝１０回行わなければならない。しかし、文書１と文書２との文書対と、文書１と文書４との文書対と、文書２と文書５との文書対と、文書３と文書５との文書対と、文書４と文書５との文書対との５個の文書対は、９０％以上の類似度とはならない文書対であるため、類似度計算の対象から外すと、類似度計算の回数は、１０−５＝５回となる。
【００７６】
次に、上記の説明をより一般化する。
１．文書を単語の集合と考える場合
記号の定義
データベースに含まれる文書集合: D = {di| 0<=i<=|D|}、
データベースに含まれる単語集合: T = {tl| 0<=l<=|T|}、
diに含まれる単語の異なり数: |di|、
diに含まれる単語集合: di = {tl| 0<=l<=|di|}、
tlの優先順位: Pr（tl）、
tlの重要度: w（tl） # Pr（tl）はw（tl）の大きさから求めても良い
diとdjの類似度: sim（di,dj）、
類似度閾値: ST
と定義する。
定理1-1:
sdiを
sdi⊆di { sdi∩∀dk[sim（di,dk） >= ST]≠φ ∧ Pr（∀tl∈sdi） > Pr（∀tl∈-sdi） }
（-sdiはsdiの補集合）
により定義する。
この時、PrがDで一意に定まり、sdi, sdjが定まれば、
sim（di, dj） >= STのとき、
sdi∩sdj≠φが成立する。
証明:
まず、sdi,sdjの定義により、
sim(di, dj) >= STのとき、
sdi∩dj≠φ
sdj∩di≠φ
が成立する。
ここで、
sdi∩dj≠φ ∧ sdi∩sdj=φ
と仮定すると、
djにおける単語の重要度は、
Pr（∀tl∈sdj） > Pr（∀tl∈sdi）となる。
この時、sdi∩sdj=φであるから
sdj∩di≠φ ∧ sdj∩sdi=φ
が同時に成立する。
そのため、
diにおける単語の重要度は、Pr（∀tl∈sdi） > Pr（∀tl∈sdj）になる。
これは、PrがDで一意に定まることと矛盾する。
iとjを置き換えた場合でも同様である。
【００７７】
したがって、定理1-1は成立する。
【００７８】
次に、
sim（∀di∈D, ∀dj∈D）を求める前にsdiを求めることができることを示す。
定理1-2:
sim（di, dj） = 
（Σtl∈di∩dj w（tl）^2） / （（√Σtl∈di w（tl）^2） * √（Σtl∈dj w（tl）^2））
で定義されるcosine類似度を用いる場合、
sdi∈di { （Σtl∈sdl w（tl）^2） / （Σtl∈di w（tl）^2） > 1- ST^2 ∧ Pr（∀tl∈sdi） > Pr（∀tl∈-sdi） }
で定義されるならば、
sdi∩∀dk[sim（di,dk） >= ST]≠φ ∧ Pr（∀tl∈sdi） > Pr（∀tl∈-sdi）
が成立する。
証明:
まず、
sim（di, dj） >= ST
ならば
（Σtl∈di∩dj w（ti）^2） / （Σtl∈di w（tl）^2） >= ST^2
が成立することを証明する。
（Σtl∈dj w（tl）^2） >= （Σtl∈di∩dj w（tl）^2）
であるから
ST
<= sim(di, dj) = (Σti∈di∩dj w(ti)^2) / ((√Σtl∈di w(tl)^2) * (√Σtl∈dj w(tl)^2))
<= (Σti∈dj w(ti)^2) /
((√Σtl∈di w(tl)^2) * (√Σtl∈dj w(tl)^2))
= (√Σtl∈di∩dj w(tl)^2) / (√Σtl∈di w(tl)^2)
したがって、
（Σtl∈di∩dj w（tl）^2） / （Σtl∈di w（tl）^2） >= ST^2
次に、
sdi∈di { （Σl=1..|sdi| w（tl）^2） / （Σtl∈di w（tl）^2） } > 1- ST^2
で定義されるならば、
sdi∩∃dk[sim（di, dk）>=ST]＝φ
であると仮定する。
このとき、
sim（di,dk） >= ST
であるから、上記より、
（Σti∈di∩dk w（tl）^2） / （Σtl∈di w（tl）^2） >= ST^2
が成立し、
また、
（Σtl∈sdi w（tl）^2） / （Σtl∈di w（tl）^2） > 1- ST^2
であるから、であるから、２つを足して
((Σti∈di∩dk w(tl)^2) + (Σtl∈sdi w(tl)^2)) / (Σtl∈di w(tl)^2) > 1 
((Σti∈di∩dk w(tl)^2) + (Σtl∈sdi w(tl)^2)) > (Σtl∈di w(tl)^2)
となる。
ここで、
sdi∩dk＝φ
であるから、
（Σti∈（di∩dk）∪sdi w（tl）^2） > （Σtl∈di w（tl）^2）
となるが、
（di∩dk）∪sdi ⊆ di
であるから成立せず矛盾する。
したがって、
sdi = sdi∈di { （Σtl∈sdi w（tl）^2） / （Σtl∈di w（tl）^2） } > 1- ST^2
で定義されるならば、
sdi∩∀dk[sim（di,dk） >= ST]≠φ
が成立する。
上記は、sdiにどの単語から選んでいったとしても成立するので定理1-2は成立する。
２．文書を文字の集合と考える場合
記号の定義:
データベースに含まれる文書集合: D = {di| 0<=i<=|D|}
データベースに含まれる文字集合: T = {tl| 0<=l<=|T|}
diに含まれる文字の異なり数:|di|
diに含まれる文字集合: di = {tl| 0<=l<=|di|}
diにおけるtlの出現回数: fq（di,tl）
diに含まれる文字数: fq（di）
tlの優先順位: Pr（tl）
tlの重要度: w（tl） # Pr（tl）はw（tl）の大きさから求めても良い
diとdjの類似度: sim（di,dj）
類似度閾値: ST
定理2-1:
sdiを
sdi⊆di { sdi∩∀dk[sim（di,dk） >= ST]≠φ ∧ Pr（∀tl∈sdi） > Pr（∀tl∈-sdi） }
により定義する。
この時、
PrがDで一意に定まり、
sdi, sdjが定まれば、
sim（di, dj） >= STのとき
sdi∩sdj≠φ
が成立する。
証明:
定理1-1と同一の証明となる。
定理2-2:
sim（di, dj） = 
（fq（di） + fq（dj） - edit_dis（di,dj）） / （fq（di） + fq（dj））
で定義される関数を用いる場合
sdi = sdi∈di { （Σl=1..|sdi|fq（di,tl）） / fq（di） > 1 - （ST / （2-ST）） ∧ Pr（∀tl∈sdi） > Pr（∀tl∈-sdi） }
で定義されるならば、
sdi∩∀dk[sim（di,dk） >= ST]≠φ ∧ Pr（∀tl∈sdi） > Pr（∀tl∈-sdi）
が成立する。
尚、edit_dis（di,dj）はdiとdjの編集距離を意味する。
【００７９】
diとdjの編集距離とは、diからdj又はdjからdiに変換するために必要となる最小の挿入又は削除の回数を意味し、距離が小さいほど2つの文書は似ていることを意味する。
証明:
まず、
sim（di, dj） >= ST
ならば
（Σtl∈di∩dj fq（di,tl）） / fq（di） >= ST / （2-ST）
が成立することを証明する。
edit_dis（di,dj） >= fq（di） + fq（dj） - 2 x （Σtl∈di∩dj min（fq（di,tl）, fq（dj,tl）））
であるから、
ST <= sim（di,dj）
= （fq（di） + fq（dj） - edit_dis（di,dj）） / （fq（di） + fq（dj））
<= 2 x （Σtl∈di∩dj min（fq（di,tl）, fq（dj,tl））） / （fq（di） + fq（dj））
また、
fq（dj） >= （Σtl∈di∩dj min（fq（di,tl）, fq（dj,tl）））
であるから
ST <= 2 x （Σtl∈di∩dj min（fq（di,tl）, fq（dj,tl））） / （fq（di） + （Σtl∈di∩dj min（fq（di,tl）, fq（dj,tl））））
したがって、
（Σtl∈di∩dj min（fq（di,tl）, fq（dj,tl））） / fq（di） >= ST / （2-ST）
ここで、
fq（di,tl） >= min（fq（di,tl）, fq（dj,tl）） 
であるから
（Σtl∈di∩dj fq（di,tl）） / fq（di） >= ST / （2-ST）
次に、
sdi∈di { （Σtl∈sdi fq（di,tl）） / fq（di） } > 1 - （ST / （2-ST）） }
で定義されるならば、
sdi∩∃dk[sim（di, dk）>=ST]＝φ
であると仮定する。
sim（di,dk） >= ST
であるから、上記より、
Σtl∈di∩dk fq（di,tl） / fq（di） >= ST / （2-ST）
が成立し、
また、
sdi∈di { （Σtl∈sdi fq（di,tl）） / fq（di） } > 1 - （ST / （2-ST）） }
であるから、
（Σtl∈di∩dk fq（di,tl）） / fq（di） + （Σtl∈sdi fq（di,tl）） / fq（di） > 1
（Σtl∈di∩dk fq（di,tl）） + （Σtl∈sdi fq（di,tl）） > fq（di）
となる。
ここで、
sdi∩dk＝φ
であるから、
（Σtl∈（di∩dk）∪sdi fq（di,tl）） > fq（di）
となるが、
（di∩dk）∪sdi ⊆ di
であるから成立せず矛盾する。
したがって、
sdi = sdi∈di { （Σtl∈sdi fq（di,tl）） / fq（di） } > 1- （ST / （2-ST）） }
で定義されるならば、
sdi∩∀dk[sim（di,dk） >= ST]≠φ
が成立する。
上記は、sdiにどの文字から選んでいったとしても成立するので定理2-2は成立する。
【００８０】
このように、第２の実施の形態では、類似度計算の回数を減らして高速に同一文書グループを作成し、そして、この同一文書グループの内容を代表する代表文書を選択することを特徴とする。
【００８１】
以下、図２０を用いてシステムの説明を行う。
【００８２】
図２０を参照すると、本発明の第２の実施の形態は、プログラム制御により動作するデータ処理装置１と、情報を記憶する記憶装置２と、対象データベース３と、キーボード等の入力装置４と、同一文書グループ記憶部５と、代表文書記憶部６とを含む。
【００８３】
対象データベース３は、いわゆるデータベースであり、複数の文書が記憶されている。単一のデータベースであっても、複数のデータベースを仮想的にマージしたデータベースであってもよい。
【００８４】
入力装置４からは、同一文書照合システムの利用者が類似度閾値を入力する。２つの文書対の類似度がこの類似度閾値以上であれば同一文書とみなす。
【００８５】
データ処理装置１は、文書解析手段１０と、同一文書候補グループ作成手段１１と、同一文書グループ作成手段１２と、代表文書選択手段１３とを含む。
【００８６】
文書解析手段１０は、対象データベース３に格納された各文書に含まれる単語群を抽出して単語群記憶部２０に格納し、さらに、対象データベース３に出現する全ての単語に関するすべての文書で共通する優先順位を判定して優先順位記憶部２１に格納する。
【００８７】
同一文書候補グループ作成手段１１は、単語群記憶部２０に格納された文書に含まれる単語群の中から、入力装置４から入力された類似度閾値以上の文書間で少なくとも一つが必ず共通するような種類の単語群を、優先順位記憶部２１に格納された同一文書照合の対象となるすべての文書で共通する優先順位で選択した後、同一文書候補グループ記憶部２２を参照して選択したそれぞれの単語をIDとした同一文書候補グループにその文書を追加する。
【００８８】
同一文書グループ作成手段１２は、同一文書候補グループ記憶部２２に格納された同一の同一文書候補グループに所属する文書対の類似度を単語群記憶部２０を参照して計算して、入力装置４から入力された類似度閾値以上の文書対を同一文書グループとする、または、共通する文書を含む類似度閾値以上の文書対を統合した文書グループを同一文書グループとして判定し、その結果を対象データベース３に格納する。
【００８９】
代表文書選択手段１３は、第１の実施の形態と同様である。
【００９０】
記憶装置２は、単語群記憶部２０と、優先順位記憶部２１と、同一文書候補グループ記憶部２２とを含む。記憶装置２は処理の高速化の都合上、メモリ内に格納することが望ましいが、ＨＤＤ等の磁器記憶媒体であっても良い
単語群記憶部２０は、文書とその文書に含まれる単語群の対応関係を格納する。
【００９１】
優先順位記憶部２１は、単語とその優先順位の対応関係を格納する。
【００９２】
同一文書候補グループ記憶部２２は、同一文書候補グループと文書の対応関係を格納する。
【００９３】
同一文書グループ記憶部５は、第１の実施の形態と同様である。
【００９４】
代表文書文書記憶部６は、第１の実施の形態と同様である。
【００９５】
次に、図２１を参照して第２の実施の形態の動作について詳細に説明する。なお、入力装置４から入力された類似度閾値は７５％として説明する。
【００９６】
文書解析手段１０は、対象データベース３に格納された各文書に含まれる単語群を抽出して単語群記憶部２０に格納し、さらに、対象データベース３に出現する全ての単語に関するすべての文書で共通する優先順位を判定して優先順位記憶部２１に格納する（図２１のステップS1）。
【００９７】
文書から抽出する単語群は、文書を形態素解析して切り出した単語群とする。切り出した単語群のうち、特定の品詞、例えば、名詞、形容動詞、形容詞、動詞、未知語を持つ単語群のみを使用するようにしても良い。例えば、ある文書「情報検索で検索」の場合は{情報,検索}が単語群となる。このように、単語の文書内の出現回数は後の処理では用いないので、１つの文書に同じ単語が複数出現する場合でもそのうち１つを単語群としてもよい。
【００９８】
形態素解析は、日本語や中国語のような文書に単語の区切りが存在しない言語に対して本発明を適用する際に必要となる。一方、英語や韓国語、ドイツ語、フランス語、スペイン語等、文書に単語の区切りが存在する言語に対しては必ずしも必要ではない。
【００９９】
図２２に単語群記憶部２０の格納例を示す。なお、動作を分かりやすくするために、ここではそれぞれの単語をアルファベットとして記号化した上で、アルファベット毎に列を揃えて表記している。
【０１００】
単語の優先順位は、優先順位が一意であれば、どのような基準で決定しても本発明の実施には影響しない。ただし、出現文書数が少ない単語に高い優先順位を与えれば、同一文書候補グループ作成手段１１において同一文書候補グループに登録される文書数を少なく抑えられるため、同一文書グループ作成手段１２において類似度計算の回数を少なくすることが可能である。
【０１０１】
図２３に優先順位記憶部２１の格納例を示す。ここでは、単語とその出現文書数、優先順位の対応関係を格納している。単語の優先順位は、単語の出現文書数が小さいほど高く、出現文書数が同じ場合は、文字コードの若い単語、すなわち、アルファベット順で若い単語ほど優先順位を高くしている。
【０１０２】
同一文書候補グループ作成手段１１は、単語群記憶部２０に格納された文書に含まれる単語群の中から、入力装置４から入力された類似度閾値以上の文書間で少なくとも一つが必ず共通するような種類の単語群を、優先順位記憶部２１に格納された同一文書照合の対象となるすべての文書で共通する優先順位で選択した後、同一文書候補グループ記憶部２２を参照して選択したそれぞれの単語をIDとした同一文書候補グループにその文書を追加する（図２１のステップS2）。
【０１０３】
ここで図２４を用いて、ステップS2の動作の詳細を説明する。
【０１０４】
まず、単語群記憶部２０に格納された先頭の文書IDを持つ文書を選択する（図２４のステップS20）。文書を選択する順番は本発明の実施とは無関係であり任意の順番でよい。ここでは、説明をわかりやすくするために、文書には文書1から文書nのIDが振られており、i番目の文書は文書iで現し、また、ステップS20では文書i = 文書1が選択されたとして説明する。
【０１０５】
次に、文書iに含まれる単語のうち、入力装置４から入力された類似度閾値以上の文書間で少なくとも一つが必ず共通するような種類の単語群を、優先順位記憶部２１に格納された同一文書照合の対象となるすべての文書で共通する優先順位で選択する（図２４のステップS21）。ここでは、類似度を定理1-2のcosine類似度で計算する場合で説明する。
【０１０６】
文書iに含まれる各単語の重みw（tl）はどのように決定しても本発明の実施には影響しない。例えば、w（tl）=1のように単語の重み全て同一にするか、w（tl）=log2（総文書数 / tlの出現文書数）のように出現文書数が少ないほど重要度が高くなるように設定することができる。ここでは、w（tl）=1として説明する。なお、w（tl）=log2（総文書数 / tlの出現文書数）で計算する場合は、tlの出現文書数は、優先順位記憶部２１から得ることが可能である。
【０１０７】
文書iから選択する単語群は、定義1-2に従う。例えば、入力装置４から入力された類似度閾値は７５％であるから、図２２の単語群記憶部２０の文書1から選択する単語は、定理1-2に従い、（選択する単語の異なり数） ／ 9 ＞ 1-0.75＾2を満たす最小の単語の異なり数である４個を選択すればよい。
【０１０８】
文書iから選択する単語の順序は、優先順位記憶部２１に格納された優先順位に従う。文書１から選択する４個の単語は、{A,I,B,C}となる。
【０１０９】
次に、ステップS21で選択した単語群の先頭の単語IDを持つ単語を選択する（図２４のステップS22）。単語を選択する順番は本発明の実施とは無関係であり任意の順番でよい。ここでは、説明をわかりするために、単語には単語1から単語mのIDが振られており、j番目の単語は単語jで表し、またステップS22では単語j = 単語1から選択されたとして説明する。
【０１１０】
次に、同一文書候補グループ記憶部２２に単語jをIDとした同一文書候補グループが存在するかを参照する（図２４のステップS23）。もし存在しない場合は、単語jをIDとした同一文書候補グループを新たに作成し、それに文書iを追加する（図２４のステップS24）。存在する場合は、単語jをIDとした同一文書候補グループに文書iを追加する（図２４のステップS25）。
【０１１１】
次に、ステップS22の単語IDがj >= mを満たすかを判断し（図２４のステップS26）、満たす場合はステップS29へ進む、満たさない場合は、単語j=単語{j+1}として（図２４のステップS27）、ステップS22へ戻る。
【０１１２】
次に、ステップS21の文書IDがi >= nを満たすかを判断し（図２４のステップS29）、満たす場合はステップS3に進み、満たさない場合は、文書i=文書{i+1}として（図２４のステップS28）、ステップS21へ戻る。
【０１１３】
以上、ステップS2の同一文書候補グループ作成手段１１を説明した。類似度閾値が７５％の場合、同一文書候補グループ作成手段１１は、図２２の単語群記憶部２０の文書１から{A,I,B,C}を、文書2から{G,L,E}を、文書3から{I,B,C,D}を、文書4から{G,K,L}を、文書5から{A,M,B,C}を、文書６から{K}選択し、それを同一文書候補グループ記憶部２２に図２５のように格納する。
【０１１４】
同一文書グループ作成手段１２は、同一文書候補グループ記憶部２２を参照して同一の同一文書候補グループに所属する文書対の類似度を単語群記憶部２０を参照して計算して、入力装置４から入力された類似度閾値以上の文書対を同一文書グループとする、または、共通する文書を含む類似度閾値以上の文書対を統合した文書グループを同一文書グループとして判定し、その結果を同一文書グループ記憶部５に格納する（図２１のステップS3）。
【０１１５】
ステップS3の動作の詳細を説明する。なおステップS3の動作は、２通りの方法があり、まず一つ目を図１０を用いて説明する。
【０１１６】
まず、同一文書候補グループ記憶部２２に格納された先頭の単語IDを持つ単語を選択する（図２６のステップS310）。単語を選択する順番は本発明の実施とは無関係であり任意の順番でよい。ここでは、説明をわかりやすくするために、単語には単語1から単語nのIDが振られており、i番目の単語は単語iで現し、また、ステップS310では単語i = 単語1が選択されたとして説明する。
【０１１７】
次に、単語iをIDとする同一文書候補グループのうち先頭の文書IDを持つ文書を選択する（図２６のステップS311）。文書を選択する順番は本発明の実施とは無関係であり任意の順番でよい。ここでは、説明をわかりやすくするために、単語iをIDとする同一文書候補グループの文書には文書1から文書mのIDが振られており、j番目の文書は文書jで現し、また、ステップS311では文書j = 文書1が選択されたとして説明する。
【０１１８】
単語iをIDとする同一文書候補グループのうち文書k=文書j+1の文書IDを持つ文書を選択する（図２６のステップS312）。
【０１１９】
次に、単語群記憶部２０を参照して文書jと文書kの類似度を求め、類似度が入力装置４から入力された類似度閾値以上の場合は、同一文書グループとして出力データベース５に登録する（図２６のステップS313）。類似度の計算式は、ステップS2の同一文書候補グループ作成手段１１と同一のものを用いる。例えば、図２５の同一文書候補グループ記憶部２２の単語AをIDとする同一文書グループに登録された文書1と文書5の類似度を単語の重みをw（tl）=1とした定義2のcosine類似度で計算すると、cosine（文書1,文書5）= 6 ／ √9 x √7 ＝ 0.76となり、類似度閾値は７５％であるから、同一文書グループとして同一文書グループ記憶部５に登録する。
【０１２０】
次に、ステップS312の文書IDがk >= mを満たすかを判断し（図２６のステップS314）、満たす場合はステップS316へ進む、満たさない場合は、文書k=文書{k+1}として（図２６のステップS315）、ステップS312へ戻る。
【０１２１】
次に、ステップS311の文書IDがj >= mを満たすかを判断し（図２６のステップS316）、満たす場合はステップS318へ進む、満たさない場合は、文書j=文書{j+1}（図２６のステップS317）として、ステップS311へ戻る。
【０１２２】
次に、ステップS310の単語IDがi >= nを満たすかを判断し（図２６のステップS318）、満たす場合はステップS4に進み、満たさない場合は、単語i=単語{i+1}（図２６のステップS319）として、ステップS310へ戻る。
【０１２３】
以上、一つ目のステップS3の同一文書グループ作成手段１２の動作を説明した。類似度敷居値が75%の場合、同一文書グループ作成手段１２は、図２５の同一文書候補グループ記憶部２２の単語AをIDとする同一文書候補グループの{文書1,文書5}、単語Bのグループの{文書1,文書3},{文書1,文書5},{文書3,文書5}、単語Cのグループの{文書1,文書3},{文書1,文書5},{文書3,文書5}、単語Gのグループの{文書2,文書4}、単語Iのグループの{文書1,文書3}、単語Kのグループの{文書4,文書6}、単語Lのグループの{文書2,文書4}と、類似度を計11回計算し（類似度の計算結果は図２７を参照のこと）、同一文書グループ記憶部５に同一文書グループを図２８のように出力する。
【０１２４】
このように、従来の総当りの方法では、図２２の単語群記憶部２０に対して類似度は６ｘ５／２＝１５回計算する必要があるが、本発明では１１回で同一の結果を出力できる。ステップS3の同一文書グループ作成手段１２の説明は、同一の文書対に対しても何度も類似度計算する単純な方法を採用しているが、既に類似度を求めた文書対を記憶装置２に保持することで、同一の文書対を１度だけ計算すれば良いようにできる。この時、ステップS3の同一文書グループ作成手段１２は図２５の同一文書候補グループ記憶部２２に対して類似度は５回計算するだけで良い。
【０１２５】
同一文書グループ記憶部５への同一文書グループの格納方法は、図２８の（ａ）（ｂ）（ｃ）が考えられる。
【０１２６】
（ａ）は、類似度閾値以上のそれぞれの文書対を同一文書グループとして格納している。各レコードが一つの同一文書グループを意味する。
【０１２７】
（ｂ）は、共通する文書を含む類似度閾値以上の文書対を統合した文書群を同一文書グループとして格納している。1列目のフィールドの値が一つの同一文書グループのIDを意味する。
【０１２８】
（ｃ）は、ある文書との類似度が閾値以上となる文書群を、その文書に対する同一文書グループとして格納している。第1列の文書IDが、その文書IDに対する同一文書グループを意味する。例えば、文書１に対する同一文書グループとして文書３と文書５が、文書２に対しては文書４が登録されている。
【０１２９】
第１の実施の形態では、このうち（ｂ）と（ｃ）が同一文書グループ記憶部に格納されていることを前提としている。
【０１３０】
ステップS3の2つ目の動作の詳細を図３０を用いて説明する。2つ目の動作を実現するためには、ステップS2の同一文書候補グループ作成手段１１において、各文書と選択した単語群との対応関係を選択単語記憶部へ出力することが必要である。選択単語記憶部の例を図２９に示す。
【０１３１】
まず、選択単語記憶部に格納された先頭の文書IDを持つ文書を選択する（図３０のステップS320）。文書を選択する順番は本発明の実施とは無関係であり任意の順番でよい。ここでは、説明をわかりやすくするために、文書には文書1から文書nのIDが振られており、i番目の文書は文書iで現し、また、ステップS320では文書i = 文書1が選択されたとして説明する。
【０１３２】
次に、同一文書候補グループ記憶部２２を参照して、文書iのそれぞれの選択単語をIDとする同一文書候補グループの論理和の文書群を求める（図３０のステップS321）。例えば、文書i=文書1の場合、文書1の選択単語は、図２９を参照すると{A,B,C,I}となっている。それぞれの選択単語をIDとした同一文書候補グループの文書群は、図２５を参照すると単語Aについては{文書1,文書5}、単語Bについては{文書1,文書3,文書5}、単語Cについては{文書1,文書3,文書5}、単語Iについては{文書1,文書3}となっている。これらの論理和の文書群は、{文書1,文書3,文書5}となる。
【０１３３】
次に、ステップS321で求めた文書群から文書jを取り出す（図３０のステップS322）。文書を取り出す順番は本発明の実施とは無関係であり任意の順番でよい。
【０１３４】
次に、ｊ>iならば、文書iと文書jの類似度を計算し、類似度閾値以上の場合は同一文書グループとして出力データベース５に登録する（図１４のステップS323） 。例えば、文書i=文書1のとき、ステップS322では、{文書1,文書3,文書5}が論理和の単語群となるが、文書j=文書3、文書j=文書5のときにのみ類似度を計算することとなる。類似度の計算式は、ステップS2の同一文書候補グループ作成手段１１と同一のものを用いるが、この点に関しては、一つ目の同一文書グループ作成手段１２の動作と同様なので省略する。
【０１３５】
次に、ステップS322で求めた論理和の単語群に残りがある場合はステップS322に戻り、残りがない場合はステップS325に進む（図３０のステップS324）。
【０１３６】
次に、ステップS320の文書IDがi >= nを満たすかを判断し（図３０のステップS325）、満たす場合はステップS4へ進み、満たさない場合は、文書i=文書{i+1}（図３０のステップS326）として、ステップS320へ戻る。
【０１３７】
以上、２つ目のステップS3の同一文書グループ作成手段１２の動作を説明した。類似度閾値が７５％の場合、文書1に対する論理和の単語群は{文書1,文書3,文書5}、文書2に対する論理和の単語群は{文書2,文書4}、文書3に対する論理和の単語群は{文書1,文書3,文書5}、文書4に対する論理和の単語群は{文書2,文書4,文書6}、文書5に対する論理和の単語群は{文書1,文書3,文書5}、文書6に対する論理和の単語群は{文書4,文書6}となり、類似度は、{文書1,文書3}、{文書1,文書5}、{文書2,文書4}、{文書3,文書5}、{文書4,文書6}の計5回計算し、同一文書グループ記憶部５に同一文書グループを図２８のように出力する。
【０１３８】
次に、代表文書選択手段１３は、同一文書グループから、代表文書を除く各文書が少なくとも一つ以上の代表文書と類似度閾値以上の関係となるように、すなわち、文書対の関係となるように代表文書を選択する。これは、代表文書群とそれらとの類似度が類似度閾値以上になる文書群を合わせた文書群が、同一文書グループの文書群と一致するように代表文書群を選択するともいえる。この動作は、第１の実施の形態と同様なのでここでは省略する。
【０１３９】
本発明の効果は、第１の実施の形態の効果に加え、グループ数の指定が事前に必要なく、照合漏れのない厳密解で、かつ、グループ数が多くなっても高速に同一文書の照合が可能なことである。高速である理由は、類似度計算の対象となる文書対を、同一の同一文書候補グループに所属する文書対に限定するためである。
【０１４０】
また、照合漏れのない厳密解である理由は、文書に含まれる単語群の中から類似度閾値以上の文書間で少なくとも一つが必ず共通するような種類の単語群を選択して文書グループ作成に用いるためである。さらに、同一文書グループ数を事前に指定しなくてもよく、同一文書グループ数が多くなっても高速な理由は、同一文書グループ数があらかじめ与えられていなくても同一文書グループを作成することが可能なためである。
【０１４１】
第３の実施の形態を説明する。
【０１４２】
第３の実施の形態は、文書の文字群に着目する場合を説明する。
【０１４３】
図３１を参照すると、本発明の第３の実施の形態は、プログラム制御により動作するデータ処理装置１と、情報を記憶する記憶装置２と、対象データベース３とキーボード等の入力装置４と同一文書グループ記憶部５と、代表文書記憶部６とを含む。
【０１４４】
対象データベース３については、第２の実施の形態と同様である。入力装置４については、第２の実施の形態と同様である。
【０１４５】
データ処理装置１は、文書解析手段１０と、同一文書候補グループ作成手段１１と、同一文書グループ作成手段１２と、代表文書選択手段１３を有する。
【０１４６】
文書解析手段１０は、対象データベース３に出現する全ての文字に関するすべての文書で共通する優先順位を判定して優先順位記憶部２１に格納する。
【０１４７】
同一文書候補グループ作成手段１１は、対象データベース３に格納された文書に含まれる文字群の中から、入力装置４から入力された類似度閾値以上の文書間で少なくとも一つが必ず共通するような数の文字群を、優先順位記憶部２１に格納された同一文書照合の対象となるすべての文書で共通する優先順位で選択した後、同一文書候補グループ記憶部２２を参照して選択したそれぞれの文字をIDとした同一文書候補グループにその文書を追加する。
【０１４８】
同一文書グループ作成手段１１は、同一文書候補グループ記憶部２２に格納された同一の同一文書候補グループに所属する文書対の類似度を対象データベース３を参照して計算して、入力装置４から入力された類似度閾値以上の文書対を同一文書グループとする、または、共通する文書を含む類似度閾値以上の文書対を統合した文書グループを同一文書グループとして判定し、その結果を同一文書グループ記憶部５に格納する。
【０１４９】
記憶装置２は、優先順位記憶部２１と、同一文書候補グループ記憶部２２とを含む。記憶装置２は処理の高速化の都合上、メモリ内に格納することが望ましいが、ＨＤＤ等の磁器記憶媒体であっても良い
優先順位記憶部２１は、第２の実施の形態と同様である。同一文書候補グループ記憶部２２は、第２の実施の形態と同様である。同一文書グループ５は、第１の実施の形態と同様である。代表文書記憶部６は、第１の実施の形態と同様である。
【０１５０】
次に、図３２を参照して本発明を実施するための最良の形態の動作について詳細に説明する。なお、入力装置４から入力された類似度閾値は７５％として説明する。
【０１５１】
文書解析手段１０は、対象データベース３に出現する全ての文字に関するすべての文書で共通する優先順位を判定して優先順位記憶部２１に格納する（図３２のステップS1）。
【０１５２】
文字の優先順位は、優先順位が一意であれば、どのような基準で決定しても本発明の実施には影響しない。ただし、出現文書数が少ない文字に高い優先順位を与えれば、同一文書候補グループ作成手段１１において同一文書候補グループに登録される文書数を少なく抑えられるため、同一文書グループ作成手段１２において類似度計算の回数を少なくすることが可能である。
【０１５３】
図２３に図２２の対象データベース３を参照して求めた優先順位記憶部２１の格納例を示す。ここでは、文字とその出現文書数、優先順位の対応関係を格納している。文字の優先順位は、文字の出現文書数が小さいほど高く、出現文書数が同じ場合は、文字コードの若い文字、すなわち、アルファベット順で若い文字ほど優先順位を高くしている。
【０１５４】
同一文書候補グループ作成手段１１は、対象データベース３に格納された文書に含まれる文字群の中から、入力装置４から入力された類似度閾値以上の文書間で少なくとも一つが必ず共通するような数の文字群を、優先順位記憶部２１に格納された同一文書照合の対象となるすべての文書で共通する優先順位で選択した後、同一文書候補グループ記憶部２２を参照して選択したそれぞれの文字をIDとした同一文書候補グループにその文書を追加する（図３２のステップS2）。
【０１５５】
ここで図３３を用いて、ステップS2の動作の詳細を説明する。
【０１５６】
まず、対象データベース３に格納された先頭の文書IDを持つ文書を選択する（図３３のステップS20）。文書を選択する順番は本発明の実施とは無関係であり任意の順番でよい。ここでは、説明をわかりやすくするために、文書には文書1から文書nのIDが振られており、i番目の文書は文書iで現し、また、ステップS20では文書i = 文書1が選択されたとして説明する。
【０１５７】
次に、文書iに含まれる文字のうち、入力装置４から入力された類似度閾値以上の文書間で少なくとも一つが必ず共通するような数の文字群を、対象データベース３に格納された同一文書照合の対象となるすべての文書で共通する優先順位で選択する（図３３のステップS21）。ここでは、類似度を定義2-2の類似度で計算する場合で説明する。
【０１５８】
文書iから選択する文字数は、定義2-2に従う。例えば、入力装置４から入力された類似度閾値は７５％であるから、図２２の対象データベース３の文書1から選択する文字は、定義2-2に従い、（選択する文字数） / 9 > 1-0.75/（2-0.75）を満たす最小の選択文字数である４個を選択すればよい。
【０１５９】
文書iから選択する文字の順序は、優先順位記憶部２１に格納された優先順位に従う。文書1から選択する4個の文字は、{A,I,B,C}となる。
【０１６０】
次に、ステップS21で選択した文字群の先頭の文字IDを持つ文字を選択する（図３３のステップS22）。文字を選択する順番は本発明の実施とは無関係であり任意の順番でよい。ここでは、説明をわかりやすくするために、文字には文字1から文字mのIDが振られており、j番目の文字は文字jで表し、またステップS22では文字j = 文字1から選択されたとして説明する。
【０１６１】
次に、同一文書候補グループ記憶部２２に文字jをIDとした同一文書候補グループが存在するかを参照する（図３３のステップS23）。もし存在しない場合は、文字jをIDとした同一文書候補グループを新たに作成し、それに文書iを追加する（図３３のステップS24）。存在する場合は、文字jをIDとした同一文書候補グループに文書iを追加する（図３３のステップS25）。
【０１６２】
次に、ステップS22の文字IDがj >= mを満たすかを判断し（図３３のステップS26）、満たす場合はステップS29へ進む、満たさない場合は、文字j=文字{j+1}（図３３のステップS27）として、ステップS22へ戻る。
【０１６３】
次に、ステップS22の文書IDがi >= nを満たすかを判断し（図３３のステップS29）、満たす場合はステップS3に進み、満たさない場合は、文書i=文書{i+1}（図３３のステップS28）として、ステップS21へ戻る。
【０１６４】
以上、ステップS2の同一文書候補グループ作成手段１１を説明した。類似度敷居値が７５％の場合、同一文書候補グループ作成手段１１は、図２２の対象データベース３の文書1から{A,I,B,C}を、文書2から{G,L,E}を、文書3から{I,B,C}を、文書4から{G,K,L}を、文書5から{A,M,B}を、文書6から{K}選択し、それを同一文書候補グループ記憶部２２に図３４のように格納する。
【０１６５】
同一文書グループ作成手段１２は、同一文書候補グループ記憶部２２を参照して同一の同一文書候補グループに所属する文書対の類似度を対象データベース３を参照して計算して、入力装置４から入力された類似度閾値以上の文書対を同一文書グループとする、または、共通する文書を含む類似度閾値以上の文書対を統合した文書グループを同一文書グループとして判定し、その結果を同一文書グループ記憶部５に格納する（図３２のステップS3）。
【０１６６】
ステップS3の動作の詳細を説明する。なおステップS3の動作は2通りの方法があり、まず一つ目を、図３５を用いて説明する。
【０１６７】
まず、同一文書候補グループ記憶部２２に格納された先頭の文字IDを持つ文字を選択する（図３５のステップS310）。文字を選択する順番は本発明の実施とは無関係であり任意の順番でよい。ここでは、説明をわかりやすくするために、文字には文字1から文字nのIDが振られており、i番目の文字は文字iで現し、また、ステップS310では文字i = 文字1が選択されたとして説明する。
【０１６８】
次に、文字iをIDとする同一文書候補グループのうち先頭の文書IDを持つ文書を選択する（図３５のステップS311）。文書を選択する順番は本発明の実施とは無関係であり任意の順番でよい。ここでは、説明をわかりやすくするために、文字iをIDとする同一文書候補グループの文書には文書1から文書mのIDが振られており、j番目の文書は文書jで現し、また、ステップS311では文書j = 文書1が選択されたとして説明する。
【０１６９】
次に、文字iをIDとする同一文書候補グループのうち文書k=文書j+1の文書IDを持つ文書を選択する（図３５のステップS312）。
【０１７０】
次に、対象データベース３を参照して文書jと文書kの類似度を求め、類似度が入力装置４から入力された類似度閾値以上の場合は、同一文書グループとして出力データベース５に登録する（図３５のステップS313）。類似度の計算式は、ステップS2の同一文書候補グループ作成手段１１と同一のものを用いる。例えば、図３４の同一文書候補グループ記憶部２２の文字AをIDとする同一文書グループに登録された文書1と文書5の類似度を定義2-2の類似度で計算すると、sim（文書1,文書5）= （9+7-4）/（9+7） = 0.75となり、類似度閾値は７５％であるから、同一文書グループとして同一文書グループ記憶部５に登録する。
【０１７１】
次に、ステップS312の文書IDがk >= mを満たすかを判断し（図３５のステップS314）、満たす場合はステップS316へ進む、満たさない場合は、文書k=文書{k+1}（図３５のステップS315）として、ステップS312へ戻る。
【０１７２】
次に、ステップS311の文書IDがj >= mを満たすかを判断し（図３５のステップS316）、満たす場合はステップS318へ進む、満たさない場合は、文書j=文書{j+1}（図３５のステップS317）として、ステップS311へ戻る。
【０１７３】
次に、ステップSの文字IDがi >= nを満たすかを判断し（図３５のステップS318）、満たす場合はステップS4へ進み、満たさない場合は、文字i=文字{i+1}（図３５のステップS319）として、ステップS310へ戻る。
【０１７４】
以上、一つ目のステップS3の同一文書グループ作成手段１２の動作を説明した。類似度敷居値が７５％の場合、同一文書グループ作成手段１２は、図１８の同一文書候補グループ記憶部２２の文字AをIDとする同一文書候補グループの{文書1,文書5}、文字Bのグループの{文書1,文書3},{文書1,文書5},{文書3,文書5}、文字Cのグループの{文書1,文書3}、文字Gのグループの{文書2,文書4}、文字Iのグループの{文書1,文書3}、文字Kのグループの{文書4,文書6}、文字Lのグループの{文書2,文書4}と、類似度を計9回計算し（類似度の計算結果は図３６を参照のこと）、出力データベース５に同一文書グループを図２８のように出力する。
【０１７５】
ステップS2の同一文書グループ作成手段１２の説明は、同一の文書対に対しても何度も類似度計算する単純な方法を採用しているが、既に類似度を求めた文書対を記憶装置２に保持することで、同一の文書対を1度だけ計算すれば良いようにできる。この時、ステップS3の同一文書グループ作成手段１２は図３４の同一文書候補グループ記憶部２２に対して類似度は５回計算するだけで良い。
【０１７６】
ステップS3の２つ目の動作の詳細を図３８を用いて説明する。2つ目の動作を実現するためには、ステップS2の同一文書候補グループ作成手段１１において、各文書と選択した文字群との対応関係を選択文字記憶部へ出力することが必要である。選択文字記憶部の例を図３７に示す。
【０１７７】
まず、選択文字記憶部に格納された先頭の文書IDを持つ文書を選択する（図３８のステップS320）。文書を選択する順番は本発明の実施とは無関係であり任意の順番でよい。ここでは、説明をわかりやすくするために、文書には文字1から文字nのIDが振られており、i番目の文字は文字iで現し、また、ステップS320では文字i = 文字1が選択されたとして説明する。
【０１７８】
次に、同一文書候補グループ記憶部２２を参照して、文書iのそれぞれの選択文字をIDとする同一文書候補グループの論理和の文書群を求める（図３８のステップS321）。例えば、文書i=文書1の場合、文書1の選択文字は、図３７を参照すると{A,B,C,I}となっている。それぞれの選択文字をIDとした同一文書候補グループの文書群は、図３４を参照すると文字Aについては{文書1,文書5}、文字Bについては{文書1,文書3,文書5}、文字Cについては{文書1,文書3}、文字Iについては{文書1,文書3}となっている。これらの論理和の文書群は、{文書1,文書3,文書5}となる。
【０１７９】
次に、ステップS321で求めた文書群から文書jを取り出す（図３８のステップS322）。文書を取り出す順番は本発明の実施とは無関係であり任意の順番でよい。
【０１８０】
次に、ｊ>iならば、文書iと文書jの類似度を計算し、類似度閾値以上の場合は同一文書グループとして出力データベース５に登録する（図３８のステップS323）。例えば、文書i=文書1のとき、ステップS321では、{文書1,文書3,文書5}が論理和の文字群となるが、文書j=文書3、文書j=文書5のときにのみ類似度を計算することとなる。類似度の計算式は、ステップS2の同一文書候補グループ作成手段１１と同一のものを用いるが、この点に関しては、一つ目の同一文書グループ作成手段１２の動作と同様なので省略する。
【０１８１】
次に、ステップS321で求めた論理和の文字群に残りがある場合はステップS322に戻り、残りがない場合はステップS325に進む（図３８のステップS324）。
【０１８２】
次に、ステップS320の文書IDがi >= nを満たすかを判断し（図３８のステップS325）、満たす場合はステップS4へと進み、満たさない場合は、文書i=文書{i+1}（図３８のステップS326）として、ステップS320へ戻る。
【０１８３】
以上、２つ目のステップS3の同一文書グループ作成手段１２の動作を説明した。類似度閾値が７５％の場合、文書1に対する論理和の文字群は{文書1,文書3,文書5}、文書2に対する論理和の文字群は{文書2,文書4}、文書3に対する論理和の文字群は{文書1,文書3,文書5}、文書4に対する論理和の文字群は{文書2,文書4,文書6}、文書5に対する論理和の文字群は{文書1,文書3,文書5}、文書6に対する論理和の文字群は{文書4,文書6}となり、類似度は、{文書1,文書3}、{文書1,文書5}、{文書2,文書4}、{文書3,文書5}、{文書4,文書6}の計5回計算し、同一文書グループ記憶部５に同一文書グループを図２８のように出力する。
【０１８４】
次に、代表文書選択手段１３は、代表文書を除く各文書が少なくとも一つ以上の代表文書と類似度閾値以上の関係となるように、すなわち、文書対の関係となるように代表文書を選択する（（図３２のステップS4）。この動作は、第１の実施の形態と同様なのでここでは省略する。
【０１８５】
本発明の効果は、第１の実施の形態の効果に加えて、グループ数の指定が事前に必要なく、照合漏れのない厳密解で、かつ、グループ数が多くなっても高速に同一文書の照合が可能なことである。高速である理由は、類似度計算の対象となる文書対を、同一の同一文書候補グループに所属する文書対に限定するためである。また、照合漏れのない厳密解である理由は、文書に含まれる文字群の中から類似度閾値以上の文書間で少なくとも一つが必ず共通するような数の文字群を選択して文書グループ作成に用いるためである。さらに、同一文書グループ数を事前に指定しなくてもよく、同一文書グループ数が多くなっても高速な理由は、同一文書グループ数があらかじめ与えられていなくても同一文書グループを作成することが可能なためである。
【０１８６】
以上説明した第１から第３の実施の形態の同一文書照合システム７によれば、図３９に示す如く、利用者から照合対象のデータベースを受け取り、同一文書グループの作成、および、代表文書の選択を行い、同一文書記憶部、代表文書記憶部を利用者に提供することができる。
【０１８７】
また、本発明は次のような場合に利用できる。
（１）DBの重複レコード照合
DBの重複レコード照合は、DB内の実質的に同じレコードをグルーピングすることをいい、例えば、例えば、異なる人/場所/方法によって管理された表記のゆれを含む顧客DBを統合する際のデータクリーニングやコンタクトセンターの問い合わせ事例の重複削除に利用できる。１レコードを１文書とみなすことで同一文書照合の問題とみなすことができる。
（２）トピック分析
トピック分析は、Blogなどの書き込みデータをグルーピングすることをいい、Blogで同じトピックが、いつ／どのあたりで話題になっているかを把握するために利用できる。
【図面の簡単な説明】
【０１８８】
【図１】背景技術において同一文書照合を説明する為の図である。
【図２】同一文書グループを説明する為の図である。
【図３】本発明を説明する為の図である。
【図４】第２の実施の形態の概要を説明する為の図である。
【図５】本発明の第１の実施の形態の構成を示すブロック図である。
【図６】本発明の第１の実施の形態の動作を示す流れ図である。
【図７】本発明の第１の実施の形態の代表文書選択手段の動作の詳細を示す流れ図である。
【図８】本発明の第１の実施の形態の同一文書グループ記憶部の格納例である。
【図９】本発明の第１の実施の形態の代表文書記憶部の格納例である。
【図１０】本発明の第１の実施の形態の代表文書選択手段のステップS42の動作の詳細を示す流れ図である。
【図１１】本発明の第１の実施の形態の未選択代表文書バッファ、未選択文書バッファの格納例である。
【図１２】本発明の第１の実施の形態の代表文書の選択状態を示す図である。
【図１３】本発明の第１の実施の形態の未選択代表文書バッファ、未選択文書バッファの格納例である。
【図１４】本発明の第１の実施の形態の代表文書の選択状態を示す図である。
【図１５】本発明の第１の実施の形態の代表文書の選択状態を示す図である。
【図１６】本発明の第１の実施の形態の未選択代表文書バッファ、未選択文書バッファの格納例である。
【図１７】本発明の第１の実施の形態の代表文書の選択状態を示す図である。
【図１８】本発明の第１の実施の形態の代表文書の選択状態を示す図である。
【図１９】本発明の第１の実施の形態の未選択代表文書バッファ、未選択文書バッファの格納例である。
【図２０】本発明の第２の実施の形態の構成を示すブロック図である。
【図２１】本発明の第２の実施の形態の動作を示す流れ図である。
【図２２】本発明の第２の実施の形態の単語記憶部２０、および、第２の実施の形態の対象データベース３の格納例である。
【図２３】本発明の第２の実施の形態と第２の実施の形態の優先順位記憶部２１の格納例である。
【図２４】本発明の第２の実施の形態の同一文書候補グループ作成手段１１の動作を示す流れ図である。
【図２５】本発明の第２の実施の形態の同一文書候補グループ記憶部２２の格納例である。
【図２６】本発明の第２の実施の形態の１つ目の同一文書グループ作成手段１２の動作を示す流れ図である。
【図２７】本発明の第２の実施の形態の類似度計算の例を示す図である。
【図２８】本発明の第２の実施の形態と第２の実施の形態の出力データベース５の格納例を示す図である。
【図２９】本発明の第２の実施の形態の選択単語記憶部の格納例である。
【図３０】本発明の第２の実施の形態の２つ目の同一文書候補グループ作成手段１２の動作を示す流れ図である。
【図３１】本発明の第３の実施の形態の構成を示すブロック図である。
【図３２】本発明の第３の実施の形態の動作を示す流れ図である。
【図３３】本発明の第３の実施の形態の同一文書候補グループ作成手段１１の動作を示す流れ図である。
【図３４】本発明の第３の実施の形態の同一文書候補グループ記憶部２２の格納例である。
【図３５】本発明の第３の実施の形態の1つ目の同一文書グループ作成手段１２の動作を示す流れ図である。
【図３６】本発明の第３の実施の形態の類似度計算の例を示す図である。
【図３７】本発明の第３の実施の形態の選択文字記憶部の格納例である。
【図３８】本発明の第３の実施の形態の2つ目の同一文書候補グループ作成手段１２の動作を示す流れ図である。
【図３９】本発明の利用例を示す図である。
【図４０】本発明の第１の実施の形態の変形例を説明する為の図である。
【図４１】本発明の第１の実施の形態の変形例を説明する為の図である。
【符号の説明】
【０１８９】
１  データ処理装置
２  記憶装置
３  対象データベース
４  入力装置
５  同一文書グループ記憶部
６  代表文書記憶部
１０  文書解析手段
１１  同一文書候補グループ作成手段
１２  同一文書グループ作成手段
１３  代表文書選択手段
２０  単語群記憶部
２１  優先順位記憶部
２２  同一文書候補グループ記憶部
【図１】
2008071136.tif 000003
【図２】
2008071136.tif 000004
【図３】
2008071136.tif 000005
【図４】
2008071136.tif 000006
【図５】
2008071136.tif 000007
【図６】
2008071136.tif 000008
【図７】
2008071136.tif 000009
【図８】
2008071136.tif 000010
【図９】
2008071136.tif 000011
【図１０】
2008071136.tif 000012
【図１１】
2008071136.tif 000013
【図１２】
2008071136.tif 000014
【図１３】
2008071136.tif 000015
【図１４】
2008071136.tif 000016
【図１５】
2008071136.tif 000017
【図１６】
2008071136.tif 000018
【図１７】
2008071136.tif 000019
【図１８】
2008071136.tif 000020
【図１９】
2008071136.tif 000021
【図２０】
2008071136.tif 000022
【図２１】
2008071136.tif 000023
【図２２】
2008071136.tif 000024
【図２３】
2008071136.tif 000025
【図２４】
2008071136.tif 000026
【図２５】
2008071136.tif 000027
【図２６】
2008071136.tif 000028
【図２７】
2008071136.tif 000029
【図２８】
2008071136.tif 000030
【図２９】
2008071136.tif 000031
【図３０】
2008071136.tif 000032
【図３１】
2008071136.tif 000033
【図３２】
2008071136.tif 000034
【図３３】
2008071136.tif 000035
【図３４】
2008071136.tif 000036
【図３５】
2008071136.tif 000037
【図３６】
2008071136.tif 000038
【図３７】
2008071136.tif 000039
【図３８】
2008071136.tif 000040
【図３９】
2008071136.tif 000041
【図４０】
2008071136.tif 000042
【図４１】
2008071136.tif 000043