(57)【要約】【課題】各単語の重要度を考慮した文書署名生成装置を提供する。【解決手段】文書集合データベース１００に保存された文書に含まれる各単語の重要度ｗtを求め、該重要度ｗtを単語重要度データベース３００に保存する単語統計情報計算手段２００と、文書集合データベース１００に保存された各文書に含まれる各単語の出現位置に応じた重要度ｗpを求めるとともに、該重要度ｗpと単語重要度データベース３００に保存された重要度ｗtに基づいて、文書集合に含まれる各文書について文書署名を計算する文書署名計算手段４００と、文書署名計算手段４００により求められた各文書に対する文書署名を保存する文書署名データベース５００とを備える。【選択図】図１
2010267108.tif 000002
【特許請求の範囲】
【請求項１】
類似文書を検出するための文書署名情報を生成する装置であって、
文書に含まれる各単語の重要度ｗt又は前記各単語の出現位置に応じた重要度ｗpのうち少なくともいずれか一方を計算して重要度ｗを求める重要度算出手段と、
前記重要度算出手段により求められた各単語の重要度ｗに応じて、各単語について{−ｗ，ｗ}を要素とするベクトルを生成し、前記生成されたベクトルからＦ要素の文書署名ベクトルを求め、該文書署名ベクトルを文書署名情報とする文書署名計算手段と、を備えたことを特徴とする類似文書を検出するための文書署名生成装置。
【請求項２】
前記文書署名計算手段は、
文書に含まれる各単語についてＦビットのハッシュ値を計算し、
前記重要度算出手段により求められた各単語の重要度ｗtおよび各単語の出現位置に応じた重要度ｗpに基づいて、前記計算されたハッシュ値をビット列として扱い、ビットが０となっている位置の要素を−ｗtｗp、ビットが１となっている位置の要素をｗtｗpとする第１のベクトルを求め、
前記第１のベクトルの同じ位置にある要素の和を計算して第２のベクトルを求め、
前記第２のベクトルの非負の要素を１、負の要素を０とするＦ要素の文書署名ベクトルを求めることを特徴とする請求項１に記載の類似文書を検出するための文書署名生成装置。
【請求項３】
類似文書を検出するための文書署名情報を生成する方法であって、
重要度算出手段が、文書に含まれる各単語の重要度ｗt又は前記各単語の出現位置に応じた重要度ｗpのうち少なくともいずれか一方を計算して重要度ｗを求める重要度算出ステップと、
文書署名計算手段が、前記重要度算出手段により求められた各単語の重要度ｗに応じて、各単語について{−ｗ，ｗ}を要素とするベクトルを生成し、前記生成されたベクトルからＦ要素の文書署名ベクトルを求め、該文書署名ベクトルを文書署名情報とする文書署名計算ステップと、を備えたことを特徴とする類似文書を検出するための文書署名生成方法。
【請求項４】
前記文書署名計算ステップは、
文書に含まれる各単語についてＦビットのハッシュ値を計算するステップと、
前記重要度算出手段により求められた各単語の重要度ｗtおよび各単語の出現位置に応じた重要度ｗpに基づいて、前記計算されたハッシュ値をビット列として扱い、ビットが０となっている位置の要素を−ｗtｗp、ビットが１となっている位置の要素をｗtｗpとする第１のベクトルを求めるステップと、
前記第１のベクトルの同じ位置にある要素の和を計算して第２のベクトルを求めるステップと、
前記第２のベクトルの非負の要素を１、負の要素を０とするＦ要素の文書署名ベクトルを求めるステップとを備えたことを特徴とする請求項３に記載の類似文書を検出するための文書署名生成方法。
【請求項５】
コンピュータを請求項１又は２に記載の各手段として機能させる類似文書を検出するための文書署名生成プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、Ｗｅｂ全文検索エンジンのインデックスを構成するような大規模文書集合に含まれる類似文書を検出するための文書署名生成技術に関する。
【背景技術】
【０００２】
大規模文書集合に含まれる文書から効率的に文書を検索する技術として、文書署名を用いる方法が古くから知られている。たとえば、非特許文献１では複数の文書署名作成法が紹介されている。文書署名は元文書集合と比較して小容量であり、また、文書署名を利用することで元文書集合を利用するよりも高速に文書を検索することができる。
【０００３】
文書署名法を類似文書検索に適用するため、非特許文献２では、非特許文献１で紹介されている“Ｓｕｐｅｒｉｍｐｏｓｅｄ  Ｃｏｄｉｎｇ”法を拡張し、単語の出現頻度を考慮した文書署名生成技術を紹介している。
【０００４】
ここで、非特許文献２で紹介されている技術を利用してＦビット長の文書署名を生成する方法を示す。まず、文書に含まれる各単語についてＦビットのハッシュ値を計算する。次に、各ハッシュ値をビット列として扱い、ビットが１となっている位置の要素を１、ビットが０となっている位置の要素を−１、とするような、各要素が｛−１，１｝であるＦ要素のベクトルに各ビット列を変換する。これで、各単語がＦ要素のベクトルで表現されたことになる。さらに、各ベクトルの同じ位置にある要素の和を計算し、その和が非負であれば１、負であれば０、を要素とするＦ要素のベクトルを求める。このベクトルの要素をビット列としたものが文書署名となる。
【先行技術文献】
【非特許文献】
【０００５】
【非特許文献１】Ｆａｌｏｕｔｓｏｓ，Ｃ．ａｎｄ  Ｃｈｒｉｓｔｏｄｏｕｌａｋｉｓ，Ｓ．“Ｄｅｓｃｒｉｐｔｉｏｎ  ａｎｄ  ｐｅｒｆｏｒｍａｎｃｅ  ａｎａｌｙｓｉｓ  ｏｆ  ｓｉｇｎａｔｕｒｅ  ｆｉｌｅ  ｍｅｔｈｏｄｓ  ｆｏｒ  ｏｆｆｉｃｅ  ｆｉｌｉｎｇ．”ＡＣＭ  Ｔｒａｎｓａｃｔｉｏｎｓ  ｏｎ  Ｏｆｆｉｃｅ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｓｙｓｔｅｍｓ．Ｖｏｌ．５，Ｎｏ．３，Ｊｕｌｙ  １９８７，ｐｐ．２３７−２５７．２００９年５月１日検索＜インターネットＵＲＬ；ｈｔｔｐ：／／ｄｏｉ．ａｃｍ．ｏｒｇ／１０．１１４５／２７６４１．２８０５７＞
【非特許文献２】Ｈｅｎｚｉｎｇｅｒ，Ｍ．“Ｆｉｎｄｉｎｇ  ｎｅａｒ−ｄｕｐｌｉｃａｔｅ  ｗｅｂ  ｐａｇｅｓ：ａ  ｌａｒｇｅ−ｓｃａｌｅ  ｅｖａｌｕａｔｉｏｎ  ｏｆ  ａｌｇｏｒｉｔｈｍｓ．”Ｉｎ  Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ｔｈｅ  ２９ｔｈ  Ａｎｎｕａｌ  ｉｎｔｅｒｎａｔｉｏｎａｌ  ＡＣＭ  ＳＩＧＩＲ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｒｅｓｅａｒｃｈ  ａｎｄ  Ｄｅｖｅｌｏｐｍｅｎｔ  ｉｎ  ｉｎｆｏｒｍａｔｉｏｎ  Ｒｅｔｒｉｅｖａｌ（Ｓｅａｔｔｌｅ，Ｗａｓｈｉｎｇｔｏｎ，ＵＳＡ，Ａｕｇｕｓｔ  ０６−１１，２００６．）ＳＩＧＩＲ  ’０６．ＡＣＭ，Ｎｅｗ  Ｙｏｒｋ，ＮＹ，ｐｐ．２８４−２９１．２００９年５月１日検索＜インターネットＵＲＬ；ｈｔｔｐ：／／ｄｏｉ．ａｃｍ．ｏｒｇ／１０．１１４５／１１４８１７０．１１４８２２２＞
【発明の概要】
【発明が解決しようとする課題】
【０００６】
本発明では、類似文書検索のための文書署名生成法としての背景技術がもつ２つの課題を解決する。以下、２つの課題を、それぞれ、課題１、課題２として述べる。
【０００７】
課題１は、背景技術が文書中の全ての単語を同等に扱うため、大きな違いも小さな違いも同等に扱うことである。その一例として、次の２組の文を挙げる。
【０００８】
（例１−ａ）  私は大阪に行きました。
【０００９】
（例１−ｂ）  私は大阪へ行きました。
【００１０】
（例２−ａ）  私は東京へ行きました。
【００１１】
（例２−ｂ）  私は大阪へ行きました。
【００１２】
例１−ａと例１−ｂは「に」と「へ」の１語のみの違いである。また、例２−ａと例２−ｂも同様に「東京」と「大阪」の１語のみの違いである。背景技術では各単語の扱いは同等のため、例１−ａと例１−ｂとの違い、あるいは、例２−ａと例２−ｂとの違いについて差をつけない。しかし、例１−ａと例１−ｂとが類似文書であるのに対して、例２−ａと例２−ｂとは類似文書ではない。
【００１３】
課題２は、背景技術が文書中の語順を考慮しないので、文の順番が入れ替わっているものに対しても同じ文書署名を生成することである。その一例として次の２文を挙げる。
【００１４】
（例３−ａ）  私は大阪に行きました。その後、東京に行きました。
【００１５】
（例３−ｂ）  私は東京に行きました。その後、大阪に行きました。
【００１６】
背景技術では語順を考慮しないため、例３−ａと例３−ｂに対して同じ文書署名を生成する。背景技術では、これらの文書を類似文書とせず文書署名で区別したいという要求に応えられない。
【課題を解決するための手段】
【００１７】
課題１に対しては、文書署名を計算する際に各単語の重要度を考慮する。具体的には、非特許技術２で各単語をビット列とし、さらに、ベクトルに変換する際に各要素を｛−１，１｝としているところを、単語の重要度に応じて｛−ｗt，ｗt｝とする。ただし、ｗtは各単語の重要度を数値化したもので、重要な単語ほど大きく、重要でない単語ほど小さくする。
【００１８】
課題２に対しては、出現位置に応じて各単語の文書署名への寄与度を決定する。具体的には、非特許技術２で各単語をビット列とし、さらに、ベクトルに変換する際に各要素を｛−１，１｝としているところを、単語の出現位置に応じて｛−ｗp，ｗp｝とする。ただし、ｗpは出現位置による寄与度を数値化したもの（出現位置に応じた重要度）である。一般に、文書の先頭に重要な情報が集中する傾向があるので、ｗpは出現位置が前の単語ほど大きく、後ろの単語ほど小さくする。
【００１９】
課題１と課題２とを同時に解決するには、非特許技術２で各単語をビット列とし、さらに、ベクトルに変換する際に各要素を｛−１，１｝としているところを、単語の重要度と出現位置に応じて｛−ｗtｗp，ｗtｗp｝とする。
【００２０】
本発明の請求項１に記載の類似文書を検出するための文書署名生成装置は、文書に含まれる各単語の重要度ｗt又は前記各単語の出現位置に応じた重要度ｗpのうち少なくともいずれか一方を計算して重要度ｗを求める重要度算出手段と、前記重要度算出手段により求められた各単語の重要度ｗに応じて、各単語について{−ｗ，ｗ}を要素とするベクトルを生成し、前記生成されたベクトルからＦ要素の文書署名ベクトルを求め、該文書署名ベクトルを文書署名情報とする文書署名計算手段と、を備えたことを特徴としている。
【発明の効果】
【００２１】
（１）本発明によれば、課題１を解決することができ、これにより、文書署名を生成する際に瑣末な単語の違いに影響されなくなる。背景技術では文書中の単語の違いにより異なる文書署名を生成していた場合でも、本発明により、類似文書に対して同じ文書署名を生成できるようになる場合が増える。本発明の文書署名を利用することで、背景技術より多くの類似文書を検出できる。
（２）また本発明によれば、課題２を解決することができ、これにより、文書署名を生成する際に、文書中の語順の違いを考慮することができる。背景技術では、語順が異なるだけの複数文書に対して同じ文書署名を生成していたが、本発明では、語順が異なる場合は異なる文書署名を生成する。背景技術は語順が異なるだけの文書を類似文書として誤検出することがあったが、本発明の文書署名を利用することで、そのような誤検出を回避できる。
【図面の簡単な説明】
【００２２】
【図１】本発明の文書署名生成装置の一実施形態例を示すブロック図。
【図２】本発明の文書署名生成方法の一実施形態例における文書署名計算方法を示すフローチャート。
【発明を実施するための形態】
【００２３】
以下、図面を参照しながら本発明の実施の形態を説明するが、本発明は下記の実施形態例に限定されるものではない。図１は本発明の文書署名生成装置の一実施形態例のブロック図であり、図中、破線矢印はデータの流れを、実線矢印は処理の流れを示す。
【００２４】
図１において、１００は文書集合データベースであり、類似文書検出対象の文書を保存した記憶装置である。
【００２５】
２００は文書集合データベース１００に保存された各文書に含まれる各単語の重要度ｗtを計算する単語統計情報計算手段である。
【００２６】
３００は単語重要度データベースであり、単語統計情報計算手段２００により計算された各単語に対する重要度ｗtを保存する記憶装置である。
【００２７】
４００は、文書集合データベース１００に保存された各文書に含まれる各単語の出現位置に応じた重要度ｗpを求めるとともに、該重要度ｗpと単語重要度データベース３００に保存された重要度ｗtに基づいて、文書集合に含まれる各文書について文書署名を計算する文書署名計算手段である。
【００２８】
５００は、文書署名データベースであり、各文書に対する文書署名を保存する記憶装置である。
【００２９】
前記単語統計情報計算手段２００および文書署名計算手段４００の後述する各機能は例えばコンピュータによって達成される。
【００３０】
また本発明の重要度算出手段は、単語統計情報計算手段２００が各単語の重要度ｗtを求め、文書署名計算手段４００が各単語の出現位置に応じた重要度ｗpを求めることで達成される。
【００３１】
次に上記のように構成された装置の動作を説明する。まず、単語統計情報計算手段２００が単語の重要度を計算する。単語統計情報計算手段２００は、文書集合データベース１００から文書を読み込み、形態素解析器により各文書に含まれる単語を抽出する。
【００３２】
次に、各単語のＩＤＦ（逆文頻度）を計算し、ＩＤＦを各単語ｔの重要度ｗt（下記式（１））として単語重要度データベース３００に記録する。
【００３３】
【数１】
2010267108.tif 000003
【００３４】
ここで、式（１）のｉｄｆは単語ｔのＩＤＦを、Ｎは集合文書に含まれる文書の総数を示し、ｄｆtは単語ｔを含む文書数を示す。
【００３５】
次に、文書署名計算手段４００が、図２に示すフローチャートに沿って、文書集合に含まれる各文書について文書署名を計算する。文書署名計算手段４００は、文書集合データベース１００から文書を読み込み、形態素解析器により各文書に含まれる単語を抽出する（ステップＳ１）。形態素解析器を利用できない場合は、例えばｎ−ｇｒａｍを単語として抽出してよい。
【００３６】
次いで、抽出した各単語についてハッシュ関数を用いてＦビットのハッシュ値を計算する（ステップＳ２）。ハッシュ関数には、似た単語から近いハッシュ値が生成されない、ハッシュ値の衝突が容易に起きない、という条件を満たす関数を利用する。ＭＤ５（Ｍｅｓｓａｇｅ  Ｄｉｇｅｓｔ  Ａｌｇｏｒｉｔｈｍ  ５）、ＳＨＡ（Ｓｅｃｕｒｅ  Ｈａｓｈ  Ａｌｇｏｒｉｔｈｍ）−１、ＳＨＡ−２５６といった標準化されたハッシュ関数は、これらの条件を満たす。つづいて、単語重要度データベース３００から各単語の単語重要度を取得する。
【００３７】
さらに、単語の出現位置ｐに応じた重要度ｗpを計算する。実施例では、文書の先頭に近いほど重要であるとして、文書長をＮ語である文書において単語がｐ番目に出現したとすると、
ｗp＝（Ｎ−ｐ）／Ｎ  …（２）
であるｗpを出現位置の重要度とする。
【００３８】
そして、各単語について、各単語のハッシュ値をビット列として扱い、ビットが０となっている位置の要素を−ｗtｗp、ビットが１となっている位置の要素をｗtｗp、とするようなＦ要素ベクトル（第１のベクトル）を求める（ステップＳ３）。ここで、単語の出現位置に応じた重要度ｗpを利用しない場合はｗp＝１、単語重要度ｗtを利用しない場合はｗt＝１とする。
【００３９】
さらに、各Ｆ要素ベクトルの同じ位置にある要素の和を計算して新たなベクトル（第２のベクトル）とし（ステップＳ４）、その和が非負であれば１、負であれば０、を要素とするＦ要素の文書署名ベクトルを求める（ステップＳ５）。最後にこの文書署名ベクトルをＦビットのビット列としたものを文書署名として文書署名データベース５００に格納する（ステップＳ６）。
【００４０】
尚、前記文書署名計算手段４００により計算されたハッシュ値は、例えば図示省略のメモリに格納して利用するように構成しても良い。
【００４１】
また、本実施形態の文書署名生成装置における各手段の一部もしくは全部の機能をコンピュータのプログラムで構成し、そのプログラムをコンピュータを用いて実行して本発明を実現することができること、本実施形態の文書署名生成方法における手順をコンピュータのプログラムで構成し、そのプログラムをコンピュータに実行させることができることは言うまでもなく、コンピュータでその機能を実現するためのプログラムを、そのコンピュータが読み取り可能な記録媒体、例えばＦＤ（Ｆｌｏｐｐｙ（登録商標）  Ｄｉｓｋ）や、ＭＯ（Ｍａｇｎｅｔｏ−Ｏｐｔｉｃａｌ  ｄｉｓｋ）、ＲＯＭ（Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）、メモリカード、ＣＤ（Ｃｏｍｐａｃｔ  Ｄｉｓｋ）−ＲＯＭ、ＤＶＤ（Ｄｉｇｉｔａｌ  Ｖｅｒｓａｔｉｌｅ  Ｄｉｓｋ）−ＲＯＭ、ＣＤ−Ｒ、ＣＤ−ＲＷ、ＨＤＤ、リムーバブルディスクなどに記録して、保存したり、配布したりすることが可能である。また、上記のプログラムをインターネットや電子メールなど、ネットワークを通して提供することも可能である。
【符号の説明】
【００４２】
１００…文書集合データベース
２００…単語統計情報計算手段
３００…単語重要度データベース
４００…文書署名計算手段
５００…文書署名データベース
【図１】
2010267108.tif 000004
【図２】
2010267108.tif 000005