(57)【特許請求の範囲】
【請求項１】
入力文字列と文書データベースに含まれる文書中の文字列との間の類似度を算出する文字列類似度算出装置であって、
前記文書データベースは、少なくとも１つの文書を含み、
前記入力文字列から所定長さの部分文字列を順次切り出す切り出し手段と、
順次切り出された前記部分文字列の各々について、前記文書データベースにおける出現頻度を算出する出現頻度算出手段と、
前記部分文字列の各々についての前記出現頻度に基づいて、順次切り出された前記部分文字列の前記出現頻度が相対的に小さいもののうち所定数の部分文字列を選別文字列群として選別する選別手段と、
前記選別文字列群に含まれる部分文字列の各々について、前記文書データベースに含まれる前記文書中の出現場所を探索し、前記選別文字列群に含まれる各部分文字列の各文書における出現頻度を出力する探索手段と、
前記選別文字列群に含まれる部分文字列の各々について、文書における出現頻度の値に対応付けて予め規定された複数の関数のうち各部分文字列の各文書における出現頻度に対応する１つの関数を用いて当該文書における重みを算出する重み算出手段と、
前記文書データベースに含まれる前記文書について、当該文書に出現する前記選別文字列群に含まれる部分文字列の各々に対応付けられた前記重みを加算することで類似度を算出する類似度算出手段とを備える、文字列類似度算出装置。
【請求項２】
前記重み算出手段は、前記選別文字列群に含まれる部分文字列の各々について、各部分文字列を少なくとも１つ含む文書の数に対する、当該部分文字列を２つ以上含む文書の数の比が、所定しきい値を超えるか否かを判断し、この比が所定しきい値以下である場合に当該部分文字列の重みをゼロに設定する、請求項１に記載の文字列類似度算出装置。
【請求項３】
前記重み算出手段は、前記選別文字列群に含まれる部分文字列の各々について、各部分文字列を少なくとも１つ含む文書の数に対する、当該部分文字列の前記文書データベースにおける出現頻度の比が、所定しきい値を超えるか否かを判断し、この比が所定しきい値以下である場合に当該部分文字列の重みをゼロに設定する、請求項１に記載の文字列類似度算出装置。
【請求項４】
前記所定しきい値は、対応の部分文字列を少なくとも１つ含む文書の数と前記文書データベースに含まれる文書の総数とに基づいて算出される、請求項３に記載の文字列類似度算出装置。
【請求項５】
前記予め規定された複数の関数の各々は、情報量を背景とする値ｉｄｆを含む関数であり、
情報量を背景とする値ｉｄｆは、以下の式で表され、
ｉｄｆ＝ｌｏｇ２（Ｎ／ｄｆ）
但し、Ｎは前記文書データベースに含まれる文書数であり、ｄｆは前記文書データベースに含まれる文書のうち対応の部分文字列を含む文書数である、請求項１〜４のいずれか１項に記載の文字列類似度算出装置。
【請求項６】
前記文書データベースに含まれる文書のうち、算出された前記類似度が相対的に高い文書を選択して出力する結果出力部をさらに備える、請求項１〜５のいずれか１項に記載の文字列類似度算出装置。
【請求項７】
コンピュータを、入力文字列と文書データベースに含まれる文書中の文字列との間の類似度を算出する文字列類似度算出装置として機能させる文字列類似度算出プログラムであって、
前記文書データベースは、少なくとも１つの文書を含み、
前記プログラムは、コンピュータを、
前記入力文字列から所定長さの部分文字列を順次切り出す切り出し手段と、
順次切り出された前記部分文字列の各々について、前記文書データベースにおける出現頻度を算出する出現頻度算出手段と、
前記部分文字列の各々についての前記出現頻度に基づいて、順次切り出された前記部分文字列の前記出現頻度が相対的に小さいもののうち所定数の部分文字列を選別文字列群として選別する選別手段と、
前記選別文字列群に含まれる部分文字列の各々について、前記文書データベースに含まれる前記文書中の出現場所を探索し、前記選別文字列群に含まれる各部分文字列の各文書における出現頻度を出力する探索手段と、
前記選別文字列群に含まれる部分文字列の各々について、文書における出現頻度の値に対応付けて予め規定された複数の関数のうち各部分文字列の各文書における出現頻度に対応する１つの関数を用いて当該文書における重みを算出する重み算出手段と、
前記文書データベースに含まれる前記文書について、当該文書に出現する前記選別文字列群に含まれる部分文字列の各々に対応付けられた前記重みを加算することで類似度を算出する類似度算出手段として機能させる、文字列類似度算出プログラム。
【請求項８】
請求項７に記載の文字列類似度算出プログラムを記録したコンピュータ読み取り可能な記録媒体。
【請求項９】
処理装置を含むコンピュータを用いて、入力文字列と文書データベースに含まれる文書中の文字列との間の類似度を算出する文字列類似度算出方法であって、
前記文書データベースは、少なくとも１つの文書を含み、
前記文字列類似度算出方法は、
前記処理装置が、前記入力文字列から所定長さの部分文字列を順次切り出すステップと、
前記処理装置が、順次切り出された前記部分文字列の各々について、前記文書データベースにおける出現頻度を算出するステップと、
前記処理装置が、前記部分文字列の各々についての前記出現頻度に基づいて、順次切り出された前記部分文字列の前記出現頻度が相対的に小さいもののうち所定数の部分文字列を選別文字列群として選別するステップと、
前記処理装置が、前記選別文字列群に含まれる部分文字列の各々について、前記文書データベースに含まれる前記文書中の出現場所を探索し、前記選別文字列群に含まれる各部分文字列の各文書における出現頻度を出力するステップと、
前記処理装置が、前記選別文字列群に含まれる部分文字列の各々について、文書における出現頻度の値に対応付けて予め規定された複数の関数のうち各部分文字列の各文書における出現頻度に対応する１つの関数を用いて当該文書における重みを算出するステップと、
前記文書データベースに含まれる前記文書について、当該文書に出現する前記選別文字列群に含まれる部分文字列の各々に対応付けられた前記重みを加算することで類似度を算出するステップとを備える、文字列類似度算出方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、二つの文字列の類似度判定に関するものであり、特に情報検索において、入力された文字列とデータベースに登録された文書との類似度判定に用いると好適である。
【０００２】
【従来の技術】
文書のデータベースから、所望の文書を取り出す情報検索がよく行なわれている。このような情報検索において、文書は、複数の文字からなる単語を組み合わせた文字列の集合として扱う。そして、検索文字列と検索対象文書中の文字列同士を比較し、類似度の高いものを一つあるいは複数選び出すことで情報検索を行っている。この文字列同士の類似度は、大きく分けて、形態素解析を用いる方法と、長さｎの部分文字列（以下、ｎグラムと称する）の一致を求める方法の２通りがある。
【０００３】
形態素解析を用いる方法は、例えば、Gerard Salton and Christopher Buckley, Term-Weighting Approaches in Automatic Text Retrieval, Information Proceeding and Management, 24, pp.513-523, 1988.に開示されている。この方法で二つの文字列同士の類似度を求める基本的手順は以下のようになる。まず、両方の文字列を、辞書と文法知識を用いた形態素解析により単語の列に分解する。次に、両方の単語列を比較して、一致する単語を求める。そして、一致する単語に対して重みを設定する。その上で、この重みを、すべての一致する単語に関して加算する。この加算の結果得られた総和が、形態素解析による類似度となる。
【０００４】
形態素解析を用いる方法は、形態素解析自体の精度が低いと情報検索が不調に終わるという本質的な問題を有している。形態素解析の精度を上げるには、単語辞書や文法規則などが大規模にならざるを得ず、簡単に情報検索を利用することが難しくなる。さらに、流行語、造語、限られた分野でのみ用いられる専門用語が出現する文書では、単語辞書の整備の手間が大きな負担となる。
【０００５】
次に、ｎグラムによる方法は、例えば、Yasushi Ogawa and Toru Matsuda, Overlapping statistical word indexing: A new indexing method for Japanese text, In proceeding of SIGIR'97, Philadelphia PA, USA, pp.226-234, 1997.に開示されている。この方法で文字列同士の類似度を求める基本的手順は以下のようになる。まず、両方の文字列に共通して含まれるｎ文字の部分文字列を求める。次に、この共通する部分文字列に対して、重みを設定する。そして、この重みを、すべての一致する部分に関して加算する。この加算の結果得られた総和が、ｎグラムによる類似度となる。
【０００６】
共通する部分文字列の重みの設定に関しては、特定の文書に集中的に出現して、他の文書には出現しない文字列には大きな値が与えられる。逆に多くの文書に出現する文字列には小さな値しか与えられない。これは多くの文書に出現する文字列は文書を特徴づける要素になっておらず、検索に際し、有効に利用できないことを反映したものである。
【０００７】
ｎグラムによる方法は、形態素解析を要しないため、新しい技術用語などの未知語にも対応することができ、簡単に利用できる。
【０００８】
ｎグラムによる方法の中でも、特に、長さ２の文字列（以下、bigramと称する）による類似度の算出においては、切り出されるすべてのbigramを対象にするのではなく、ひらがなを含まないbigramに限定して、文字列同士に関する一致情報を求め、類似度を算出する方法がある。これは、ひらがなを含むbigramは、文書データベース内の多くの文書で出現する可能性が高く、各文書を特徴づける文字列となる確率が極めて小さいことを考慮したものである。ひらがなを含むbigramを文字列の比較の対象に含めると計算量が大きくなるばかりで、検索の精度は大きな向上が期待できないと認識されている。
【０００９】
【発明が解決しようとする課題】
上記のように、ｎグラムによる方法は形態素解析による方法と比較して有利な面が多く、情報検索の分野で利用される場面が多い。ｎグラム法における問題は、文書データベースが大きくなるに従って計算量が増し、検索結果を得るまでの時間がかかることである。
【００１０】
ところで、文字列から切り出される部分文字列の中には、必ずしも類似度の算出において有効でない部分文字列、すなわち文書データベース内の多くの文書に含まれるため重みが小さく、類似度に与える影響の小さい部分文字列が多く含まれていると考えられている。そのため、文字列から切り出されるすべてのｎグラムについて一致するかどうかを調べる方法は、計算時間の点からみて効率がよくない。
【００１１】
また、切り出されたbigramに対し、ひらがなを含む文字列を一致情報として扱わないという方法は、計算時間の点については効率化されているが、本来は検索に有効な文字列までも一律に切り捨てられてしまう。その結果、検索精度が低下してしまうという問題があった。
【００１２】
本発明は上記したｎグラム法における問題を解決し、計算時間短縮と検索精度向上を両立する方法を提供するものである。
【００１３】
【課題を解決するための手段】
請求項１に記載の発明は、二つの文字列の類似度を算出する方法において、第１の文字列から切り出した部分文字列のうち、類似度算出に対する効果に基づいて選別した部分文字列について、第２の文字列との一致情報を収集し、前記一致情報から一致した部分文字列の重みを算出し、前記重みに基づいて類似度を算出することを特徴とする。このように文字列同士の一致情報を求める際に、切り出されるすべてのｎグラムを扱うのではなく、類似度の算出に対する効果を推定することで、類似度の算出に有効なｎグラムを選別している。
【００１４】
かかるように構成されているので、選別しない方法による検索精度とほぼ同等の検索精度を保ちつつ、計算時間の短縮を図ることが可能となる。
【００１５】
請求項２に記載の発明は、二つの文字列の類似度を算出する方法において、第１の文字列から切り出した部分文字列のうち、類似度算出に対する効果に基づいて選別した部分文字列について、第２の文字列との一致情報を収集し、前記一致情報に含まれる部分文字列の中から、第１および第２の文字列に出現する順序が適合する部分文字列の重みに基づいて類似度を算出することを特徴とする。このように、文字列同士の類似度の算出において、一致情報に記録された部分文字列の中から、さらにそれぞれの文字列に出現する順序が適合する部分文字列を選び、その重みを類似度の算出に用いている。
【００１６】
かかるように構成されているので、重みを算出する部分文字列が限定され、検索精度を保ったまま、一層の計算の高速化が達成できる。
【００１７】
請求項３に記載の発明は、請求項１または２に記載の発明において、部分文字列の選別を、第１の文字列から切り出した部分文字列が第２の文字列に出現する回数を加味して行うことを特徴とする。
【００１８】
かかるように構成されているので、類似度の算出に効果のある部分文字列が効率的に選別でき、検索精度を保ちつつ、一層の計算時間の短縮を図ることが可能となる。
【００１９】
請求項４に記載の発明は、請求項１から３のいずれかに記載の発明において、文字列同士の一致情報として、部分文字列の長さ、第１の文字列における部分文字列の出現場所、第２の文字列における部分文字列の出現場所、第２の文字列内で何番目の一致かを表すシーケンス番号、を含むことを特徴とする。
【００２０】
かかるように構成されているので、一致したｎグラムの重みを加算して類似度を算出する方法だけでなく、多くの類似度算出方法を併用することが可能となる。
【００２１】
請求項５に記載の発明は、二つの文字列の類似度を算出する文字列類似度算出装置において、第１の文字列から切り出した部分文字列のうち、類似度算出に対する効果に基づいて選別する部分文字列選別部と、第２の文字列との一致情報を収集する一致情報収集部と、前記一致情報に基づき一致した部分文字列の重みを算出し、前記重みを総和することで類似度を算出する類似度算出部と、を有することを特徴とする文字列類似度算出装置である。
【００２２】
かかるように構成されているので、選別しない方法による検索精度とほぼ同等の検索精度を保ちつつ、計算時間の短縮を図る装置を実現できる。
【００２３】
請求項６に記載の発明は、二つの文字列の類似度を算出する文字列類似度算出装置において、第１の文字列から切り出した部分文字列について、類似度算出に対する効果に基づいて選別する部分文字列選別部と、前記選別部分文字列について、第２の文字列との一致情報を収集する一致情報収集部と、前記一致情報に含まれる部分文字列の中から、それぞれの文字列に出現する順序が適合する部分文字列を選択する適合部分文字列選択手段と、前記適合部分文字列に付けられた重みを総和する類似度算出部と、を有することを特徴とする文字列類似度算出装置である。
【００２４】
かかるように構成されているので、重みを算出する部分文字列が限定され、検索精度を保ったまま、一層の計算の高速化が達成できる装置を実現できる。
【００２５】
請求項７に記載の発明は、二つの文字列の類似度を算出する文字列類似度算出プログラムであって、コンピュータを、第１の文字列から切り出した部分文字列が第２の文字列に出現する回数に基づいて選別する選別手段と、前記選別部分文字列について、第２の文字列との一致情報を収集する一致情報収集手段と、前記一致情報に基づき一致した部分文字列の重みを算出し、前記重みを総和することで類似度を算出する類似度算出手段、として機能させることを特徴とする文字列類似度算出プログラムである。
【００２６】
かかるように構成されているので、コンピュータを、選別しない方法による検索精度とほぼ同等の検索精度を保ちつつ、計算時間の短縮を図る手段として機能させることができる。
【００２７】
請求項８に記載の発明は、二つの文字列の類似度を算出する文字列類似度算出プログラムであって、コンピュータを、第１の文字列から切り出した部分文字列について、類似度算出に対する効果に基づいて選別する選別手段と、前記選別部分文字列について、第２の文字列との一致情報として、部分文字列の長さ、第１の文字列における部分文字列の出現場所、第２の文字列における部分文字列の出現場所、第２の文字列内で何番目の一致かを表すシーケンス番号、を収集する一致情報収集手段と、前記一致情報に含まれる部分文字列の中から、それぞれの文字列に出現する順序が適合する部分文字列に付けられた重みに基づいて類似度を算出する類似度算出手段、として機能させることを特徴とする文字列類似度算出プログラムである。
【００２８】
かかるように構成されているので、コンピュータを、重みを算出する部分文字列を限定し検索精度を保ったまま、一層の計算の高速化を図る手段として機能させることができる。
【００２９】
請求項９に記載の発明は、請求項７または８に記載のプログラムを記録したコンピュータ読取可能な記録媒体である。
【００３０】
かかるように構成されているので、記録された機能を必要な場所で実現することができる。
【００３１】
【発明の実施の形態】
本発明は、ｎグラムによる文字列同士の類似度の算出方法およびそれを実現する装置、プログラム、記録媒体に関する。入力された文字列とデータベースに登録された複数の文書との類似度を算出することを想定しているが、それ以外の応用も可能である。文字列同士の一致部分を求める際に、データベース中のすべての文書それぞれに対して、入力文字列と文書に共通するｎグラムを求めるという方法ではなく、入力文字列からｎグラムを切り出し、それぞれのｎグラムを含む文書をサフィックスファイルの利用によって効率的にデータベース内から検索するという方法を用いる。
【００３２】
入力文字列から切り出されるｎグラムの中には、類似度の算出に与える影響の少ないｎグラムが多く含まれていると考えられる。入力文字列から切り出される部分文字列の数は、例えば、入力文字列の長さをｍとし、部分文字列を２文字であるbigramに限定するとｍ−１となる。従って、部分文字列の選別を行わずに、切り出されたbigramすべてに対し一致情報を求めると、入力文字列長ｍが大きくなるほど、計算時間も大きくなる。そこで、本発明では、切り出されたｎグラムの中から、類似度の算出に対する効果を推定することでｎグラムを選別し、定数個のｎグラムのみを一致情報の収集に適用する。
【００３３】
部分文字列の選別については、類似度に加算される重みの大きな部分文字列を選別するのが検索精度向上のために必要である。重みは、その部分文字列を含むデータベース中の文書の数（以下、ｄｆと記す）によって決まるので、ｄｆの値を元に選別するのが自然である。しかし、本発明の一つの局面では、ｄｆの代わりに、ｎグラムがデータベース内の文書に出現する数（以下、出現度数、もしくは、ｔｆと記す）に基づき部分文字列の選別を行うことが推奨される。
【００３４】
ｔｆは直接的に算出でき、その値が増えても計算時間はほとんど変わらないのに対し、ｄｆを算出するには、ｔｆを算出した後に文書内の重複を再計算しなければならず、ｔｆの値が大きな場合は計算時間が大きくなる。一方、ｔｆとｄｆには大きな相関があり、ｄｆの代わりにｔｆを用いても、検索の精度に影響しないことが期待できる。
【００３５】
一致情報の収集は選別された各ｎグラムに対し、次のような方法で行う。
まず、ｎグラムの重みを計算する。次に、文書データベース全体からそのｎグラムを含む文書を求め、その文書内におけるｎグラムの出現場所、入力文字列におけるｎグラムの出現場所、ｎグラムの長さ、文書内において何番目の一致かを表すシーケンス番号、ｎグラムの重みを一致情報として記録する。
【００３６】
通常、得られた一致情報は、記録・管理することなく、そのまま重みの加算がされ類似度が算出されるが、本発明では、これを記録・管理することにより、一致したｎグラムの重みを加算して類似度を算出する方法だけでなく、高速性を保ったまま、多くの類似度算出方法に適用することも可能にしている。
【００３７】
入力文字列とデータベース内の文書との類似度は、一致したｎグラムに付けられた重みを加算することによって算出される。ただし、一致するｎグラムが同じ文書内に２回以上出現する場合でも、その重みは１度しか加算されない。つまり、一致するｎグラムが２回現れるからといって、加算される重みが２倍になるわけではない。そうではなく、ｎグラムが文書内に出現する回数（以下、ｄｔｆ）に応じて、一致情報として記憶されているｎグラムの重みは各文書によって異なり、ｄｔｆの値が大きいほど、与えられる重みは大きくなっている。また、この重みは、各ｎグラムに対して、ｄｔｆ＝０の場合にも定義されており、そのｎグラムを含まない文書すべてに対して、０以下の重みが加算される。これは、ｎグラムを含まないということは類似していないということを示すものである、という考え方に基づくもので、加算される重みは、類似していない度合いを数値化したものと言える。従って、類似度を示す値は負の値を含む実数値を取り、その数直線上での値が大きいほど入力文字列との類似度は高くなる。
【００３８】
類似度を算出する方法は、一致したｎグラムに付けられた重みを加算するという前記の方法に限定されるものではなく、これ以外の類似度算出方法を適用することも可能である。その一例が、一致したｎグラムの中からそれぞれの文字列に出現する順序が適合するｎグラムだけを選び、それらのｎグラムに付けられた重みを総和した値を類似度とする方法である。
【００３９】
文字列の出現順序を考慮して類似度を算出する方法は、これまでも提案されている。しかしそれらは一致する全ての長さの部分文字列について重みを計算するため、一致したｎグラムの重みを加算する方法に比べて計算量が増え、扱う文字列の長さが大きくなるほど計算時間が大きくなる。
【００４０】
本発明では、選別されたｎグラムに重みを与え、それらのｎグラムが一致した時にのみ類似度に重みが加算される。従って、選別された部分文字列に対してのみ、一致および出現順序を考慮すればよいので、これまでの方法に比べて高速に計算でき、扱う文字列の長さが大きくなっても計算時間に与える影響は小さい。この方法では、適合するｎグラムの組み合わせの中で最も類似度が高くなる組み合わせを効率的に見つけるため、動的計画法（Dynamic Programming、以下ＤＰと称する）を用いて類似度を計算する。以下では、ＤＰを使って、ｎグラムＤＰ類似度を求める方法を説明する。
【００４１】
α、β、γ、δを長さ０以上の文字列、ξ、ζ、ηを長さ１以上の文字列、""を空文字列とする。複数の文字列（例えば、ξとγ）を繋げた文字列（例えば、α）は、要素となる文字列の記号を続けて書くことで表す。（例えば、α=ξγ）。
【００４２】
ｎグラムＤＰ類似度SimDPは、引数の文字列の部分に関する一致パターンに応じて、以下の式を再帰的に当てはめることで求める。まず、両方とも空文字列の時は、
SimDP("", "") = 0                                        （１）
とする。それ以外のときは、
SimDP(α, β) = MAX( SimDPs(α, β), SimDPg(α, β) )    （２）
とする。
ここで、SimDPs(α, β)は、ξを、一致情報管理テーブルのαとβに関するリストに記録されている文字列とし、α=ξγ、β=ξδとすると、
SimDPs(α, β) = MAX( Score(ξ) + SimDP(γ, δ) )      （３）
を、全てのξに関して計算することによって求められる。そのような文字列ξが存在しないときは、
SimDPs(α, β) = 0.0                                    （４）
とする。Score(ξ)は、一致情報管理テーブルに記録されたξの重みを返す関数である。
【００４３】
また、ζとηをα＝ζγ、β＝ηδを満たし、かつ、一致情報管理テーブルのαとβに関するリストに記録された文字列と共通部分を持たない最大の文字列とすると、SimDPg(α, β)は、
SimDPg(α,β)=MAX(SimDP(α,δ), SimDP(γ,β), SimDP(γ,δ) )  （５）
によって求められる。この式は、二つの文字列（ζγとηδ）から、ζかηの一方、もしくはζとηの両方を取り除いた残りに相当する文字列同士（αとδ、γとβ、γとδ）の類似度のうち、最も高い類似度を採用することを意味する。
【００４４】
以上の式を再帰的に適用することで、一致情報管理テーブルに記録された部分文字列の中から、二つの文字列それぞれの順序に適合する部分文字列が求められ、かつ、類似度が最大となる。
【００４５】
上記で示したｎグラムＤＰ類似度は、式（３）のように、文字（長さ１の文字列）ではなく、ｎグラム（長さｎの文字列）に対する一致を考慮し、重みを与えることによって、文字の連続性を加味した類似度算出法になっている。また、全ての部分文字列について文字列同士の一致を考慮するのではなく、一致情報管理テーブルに記録されたｎグラムに限定することで、式（５）のように、一致情報管理テーブルに記録された部分文字列に関係のない部分については、一致の有無を判定する必要がなく、取り除くことができる。これによって、類似度の算出対象とする文字列の長さがどんなに大きくても、一致情報管理テーブルに記録された部分文字列に関係する部分だけを考慮すればよいので、全ての部分文字列について文字列同士の一致を考慮する従来の方法に比べ、高速に類似度を算出することができる。
【００４６】
（第１実施例）
まず、ｎグラムを用いて文字列同士の類似度を算出する方法の実施例を示す。図１は選別された部分文字列に基づき、入力された文字列と最も類似度の高い文書を検索する文書検索装置の例である。この文書検索装置は、文書データベース１０、文字列入力部１１、部分文字列選別部１３、一致情報収集部１４、類似度算出部１５、類似度算出制御部１６、及び、検索結果出力部１２から構成されている。
【００４７】
文書データベース１０には、検索対象となる複数の文書１０ａ、１０ｂ、…、１０ｃが登録されている。検索のためには、キーワード、語、語句、文、文章などを入力する（以下、代表して検索文章と呼ぶ）。文字列入力部１１は、検索文章を文字列Ｘとして部分文字列選別部１３に与える。
【００４８】
部分文字列選別部１３は、文字列入力部１１から与えられた文字列Ｘから部分文字列を切り出し、出現頻度ｔｆを算出した後、算出したｔｆの小さいものから定数個を取り出し、部分文字列管理テーブルＴ１に登録する。部分文字列選別部１３は、部分文字列切り出し制御部３１、部分文字列切り出し部３２、文字列出現頻度算出部３３、部分文字列登録部３４から成る。部分文字列切り出し制御部３１は、部分文字列切り出し部３２がどの部分文字列を切り出すかを制御する。部分文字列切り出し部３２は文字列Ｘより部分文字列ｘを切り出す。文字列出現頻度算出部３３は部分文字列ｘの文書データベース１０内における出現頻度ｔｆを算出する。部分文字列登録部３４は切り出された部分文字列をｔｆの値の小さい順に定数個選び、部分文字列管理テーブルＴ１に登録する。
【００４９】
一致情報収集部１４は部分文字列管理テーブルＴ１に登録された各部分文字列に対し、文字列に与える重みを算出し、文書データベース内における各部分文字列の出現場所を検出し、一致情報として、文書内における出現場所、入力文字列における出現場所、部分文字列の文字列の長さ、文書内において何番目の一致かを表すシーケンス番号、文字列の重みを一致情報管理テーブルＴ２に記録する。一致情報収集部１４は、一致情報収集制御部４１、文字列出現場所検索部４２、文字列重み算出部４３、一致情報登録制御部４４、一致情報登録部４５から成る。一致情報収集制御部４１は部分文字列管理テーブルＴ１に登録された部分文字列ａを１つずつ取り出し、文字列出現場所検索部４２と文字列重み算出部４３に与える。文字列出現場所検索部４２は与えられた部分文字列ａの文書データベース内における出現場所の全てについて、出現場所、部分文字列ａの長さ、文書内において何番目の一致かを表すシーケンス番号を求める。文字列重み算出部４３は与えられた文字列ａに与える重みを計算する。一致情報登録制御部４４は部分文字列ａの出現場所を１つずつ選び、文書内における出現場所、入力文字列における出現場所、部分文字列ａの長さ、文書内におけるシーケンス番号、部分文字列ａの重みと組にして、一致情報登録部４５に与える。一致情報登録部４５は受け取った各組を、一致情報管理テーブルＴ２の該当する文書番号のリストに一致情報として登録する。
【００５０】
類似度算出制御部１６は一致情報管理テーブルＴ２から、ある１つの文書Ｙに関するリストを取り出し、類似度算出部１５に与える。
【００５１】
類似度算出部１５は、与えられた一致情報のリストより、ＸとＹの類似度を算出する。類似度算出部１５は、文字列重み加算制御部５１、文字列重み加算部５２から成る。文字列重み加算制御部５１は一致情報のリストより１つの一致情報を選び、その一致情報の持つシーケンス番号が１であれば、その文字列の重みscoreを文字列重み加算部５２に与える。文字列重み加算部５２は与えられた重みをＸとＹの類似度Sim(X,Y)に加算する。
【００５２】
検索結果出力部１２は類似度が最も高い文書を選択し出力する。この時、類似度が一定値以上の文書や、上位から一定の順位までの文書を合わせて出力しても良い。
【００５３】
（第２実施例）
本発明による文章検索をソフトウエアにより実施する実施例を以下に説明する。
【００５４】
図２に、文章検索の実行に用いる計算機システムの一例を示す。この計算機システムは、ディスプレイ１０１、プリンタ１０２、キーボード１０３、フロッピー（Ｒ）ディスク装置１０４、ＣＤ−ＲＯＭ（Compact Disk− Read Only Memory）装置１０５、読み出し専用メモリ（Read Only Memory。以下、ＲＯＭ）１０６、読み書き可能なランダムアクセスメモリ（Random Access Memory。以下、ＲＡＭ）１０７、磁気ディスク装置１０８、中央処理装置（Central Processing Unit。以下、ＣＰＵ）１０９、通信インターフェイス１１０、及び、これらを接続するバス１１１から構成されている。フロッピー（Ｒ）ディスク装置１０４はフロッピー（Ｒ）ディスク１１２の読み書きを行い、ＣＤ−ＲＯＭ装置１０４はＣＤ−ＲＯＭ１１３の読み出しを行う。また、通信インターフェイス１１０により、本計算機システムは通信ネットワーク１１４に接続されている。
【００５５】
本発明を実施する文章検索プログラムは、ＲＯＭ１０６に記憶しておく。あるいは、フロッピー（Ｒ）ディスク１１２、ＣＤ−ＲＯＭ１１３、又は、磁気ディスク装置１０８に文章検索プログラムを記憶しておき、ＲＡＭ１０７に転送した後、ＣＰＵ１０９が実行するのでも良い。ＣＰＵ１０９は、ＲＡＭ１０７を作業領域に使って文章検索プログラムを実行する。必要に応じて、磁気ディスク装置１０８を作業領域に使っても良い。文章検索プログラムの実行の指示はキーボード１０３から行い、実行結果は、ディスプレイ１０１、又は、プリンタ１０２に出力する。文章検索プログラムの実行を、フロッピー（Ｒ）ディスク１１２から指示することや、実行結果をフロッピー（Ｒ）ディスク１１２に書き込んでも良いのは言うまでもない。
【００５６】
文書データベースは、フロッピー（Ｒ）ディスク１１２、ＣＤ−ＲＯＭ１１３、又は、磁気ディスク１０８に蓄えておく。高速なアクセスのためにＲＡＭ１０７に転送しておくのでも良い。ＲＡＭ１０７に転送する際に、容易に処理できる形式に変換するのも良い。また、文章検索プログラム、文書データベース、又は、実行の指示を、ネットワーク１１４経由で本計算機システムに入力したり、実行の結果をネットワーク１１４経由で本計算機システムから出力したりしても良いことは、もちろんである。
【００５７】
また、図に示されたものに限らず、各種の記録媒体、入力手段、出力手段を用いて、本計算機システムへの入力と出力を行うなど各種の実施態様への変形が可能なことは言うまでもない。これらの、記録媒体、入力手段、出力手段は本計算機システムが直接アクセスするものの他、通信ネットワークを経由してアクセスするものであっても良いのはもちろんである。
【００５８】
図３から図７に示すのは、計算対象とするｎグラムを選別して算出する文字列類似度による文書検索プログラムの処理フローである。
【００５９】
図３は、検索文章に基づいて文書データベースを検索し、類似度の高い文書を選び出して出力する処理フローを示す。
【００６０】
まず、ステップＳ１１（以下、Ｓ１１と略記）で、ある文字列の出現回数を効率よく計算する準備のために、文書データベースに含まれる全文書を統合してサフィックスファイル（Suffix File）を作成する。サフィックスファイルの作成法と利用法は、M. Yamamoto and K. W. Church, Using Suffix Arrays to Compute Term Frequency and Document Frequency for All Substrings in a Corpus, In proceeding of 6th Workshop on Very Large Corpora, Ed. Eugene Charniak, Motreal, pp28-37, 1998に開示されている。
【００６１】
サフィックスファイルを使うと、ある文字列が文書データベース内に出現する回数を高速に求めることができる。サフィックスファイルは、すべての文書において生じうる部分の文字列を、文字コード順に並び替えて、通し番号(サフィックス)を付けておくことで実施する。文字列が文書データベースに出現する回数は、その文字列と一致する文字列がサフィックスファイルの中にいくつあるかを算出することで求められる。
【００６２】
具体的には、まず、一致する文字列のサフィックスの最小値minと最大値maxをそれぞれ二分探索法により求める。一致する文字列がなければ、文書データベースに出現する回数は０である。minとmaxが求まれば、文字列が出現する回数ｔｆは、ｔｆ=max‐min+1で求められる。
【００６３】
文書データベースの文書は、文書番号によって互いに区別されるものとし、サフィックスファイルに登録する部分文字列にはこの文書番号を付けておく。これによって、ある部分文字列を含む文書を効率的に検索することができる。また、ｄｆは、重複する文書番号の数を数え上げ、その数をｔｆから引くことによって計算することができる。
【００６４】
次にＳ１２で、検索文章を文字列Ｘに読み込む。
【００６５】
Ｓ１３では、文字列Ｘから切り出される部分文字列を、文書データベース内における出現頻度ｔｆに基づいて選別し、ｔｆと組にして部分文字列管理テーブルに記録する。Ｓ１３で行う処理については、図４を用いて後述する。
【００６６】
Ｓ１４では、部分文字列管理テーブルに記録された各部分文字列に対し、一致情報を収集し、一致情報管理テーブルへの記録を行う。一致情報管理テーブルには、文書番号毎に、一致情報のリストとして記録される。Ｓ１４で行う処理については、図５を用いて後述する。
【００６７】
Ｓ１５では、一致情報管理テーブルから、ある一つの文書Ｙのリストを取り出す。
【００６８】
次にＳ１６で、取り出したリストよりＸとＹの類似度を計算する。Ｓ１６で行う処理については、図６を用いて後述する。
【００６９】
Ｓ１７では、求めた類似度と文書番号を組にして文書管理テーブルに登録する。
【００７０】
Ｓ１８では、一致情報管理テーブルに記録された全てのリストについて類似度を計算したかどうかを判定する。もし、まだ全てのリストについて類似度を計算していなければ、まだ類似度の計算を行っていないリストをＳ１５で選んで取り出し、Ｓ１７までの処理を繰り返す。もし、全てのリストについて計算していれば、Ｓ１９で、登録したテーブルを類似度の高い順に並び替える。
【００７１】
Ｓ２０では、類似度の高い文書の出力する処理を行う。出力する文書は、一つだけにする、あるいは、所定の複数にする、所定の類似度以上である全ての文書にする、など種々の態様が可能である。
【００７２】
図４は、検索文章を読み込んだ文字列Ｘから部分文字列を切り出し、一致情報の収集に利用する部分文字列を出現頻度に基づき選別し、部分文字列管理テーブルに記録する処理のフローを示す。
【００７３】
まず、Ｓ３１で、部分文字列管理テーブルに記録された部分文字列の数を表す変数num_substringと切り出す部分文字列の長さを表す変数ｊを初期化している。MinNgramLengthは、切り出す部分文字列の長さの最小値を決めるパラメータである。
【００７４】
次にＳ３２で、文字列Ｘから長さｊの部分文字列を一つ切り出し、文書データベース内における出現頻度ｔｆを計算する。
【００７５】
Ｓ３３では、切り出された部分文字列のｔｆの値が０かどうかを判定する。もし、ｔｆ＝０ならば、文書データベース内にその部分文字列は存在しないため、一致情報の収集に利用するのは不適当である。したがって、Ｓ３４の処理を飛ばして、Ｓ３５に進む。ｔｆ≠０ならば、Ｓ３４に進む。
【００７６】
Ｓ３４では、切り出された部分文字列をｔｆと共に部分文字列管理テーブルに記録し、num_substringの値に１を加える。
【００７７】
Ｓ３５では、Ｘから切り出される長さｊの全ての部分文字列についてｔｆを計算したかどうかを判定する。もし、まだ長さｊの全ての部分文字列について計算していなければ、まだ計算していない長さｊの部分文字列をＳ３２で選んでｔｆを計算し、Ｓ３４までの処理を繰り返す。もし、長さｊの全ての部分文字列について計算していれば、Ｓ３６で、ｊに１を加える。
【００７８】
Ｓ３７では、Ｘから切り出す部分文字列の長さｊの値が、切り出す部分文字列の長さの最大値を決めるパラメータMaxNgramLengthより大きいかどうかを判定する。もし、ｊの値がMaxNgramLength以下なら、Ｓ３２に戻り、長さｊの部分文字列に対し、Ｓ３６までの処理を繰り返す。もし、ｊの値がMaxNgramLengthより大きければ、長さがMinNgramLength以上、MaxNgramLength以下のすべての部分文字列に対しｔｆの計算を終えているので、Ｓ３８に進み、部分文字列管理テーブルに記録された部分文字列をｔｆの小さい順に並び替える。
【００７９】
Ｓ３９では、部分文字列管理テーブルに登録された部分文字列の数num_substringが、一致情報の収集に用いる部分文字列の数の上限値を決めるパラメータSubStringLimitより大きいかどうかを判定する。もし、num_substringがSubStringLimitより大きければ、Ｓ４０に進み、ｔｆの小さい順にSubStringLimit個の部分文字列を取り出し、これらの部分文字列を改めて部分文字列管理テーブルに記録する。もし、num_substringがSubStringLimit以下ならば、Ｓ４０をスキップしてＳ４１に進む。
【００８０】
Ｓ４１は、記録された部分文字列管理テーブルを返す処理である。
【００８１】
図５は、部分文字列管理テーブルに記録された各部分文字列と、文書データベース内の各文書との一致情報を収集し、その情報を一致情報管理テーブルに記録する処理のフローを表す。
【００８２】
まず、Ｓ５１では、変数p0fit_sumを０に初期化する。変数p0fit_sumは、類似度を一致したｎグラムの重みの加算で算出する際に、計算手間を高速化するために用いる変数で、文書データベース内の文書全体に関する類似度のオフセットである。
【００８３】
Ｓ５２では、部分文字列管理テーブルからある一つの部分文字列を選びａに読み込む。
【００８４】
Ｓ５３では、p0fit、p1fit、p2fit、p3fit、p4fitを計算し、p0fit_sumにp0fitを加算する。p0fit、p1fit、p2fit、p3fit、p4fitは、それぞれ、ａがある文書内に、出現しなかった、１回出現した、２回出現した、３回出現した、４回以上出現したときの、その文書におけるａの重みである。p0fit、p1fit、p2fit、p3fit、p4fitの計算方法については、図７を用いて後述する。
【００８５】
Ｓ５４では、文書データベース内でａが出現する場所を全て求め、これを出現する場所の順に並び替える。
【００８６】
Ｓ５５では、ａの各出現場所に対し、ａを含む文書の文書番号を求める。このとき、ａは出現場所順に並んでいるので、得られる文書番号も小さい順に並んでいる。
【００８７】
Ｓ５６では、出現場所の順にａの出現場所を一つ選ぶ。
【００８８】
Ｓ５７では、選んだａの出現場所が、それを含む文書内において、最も前方にある出現場所かどうかを判定する。つまり、選んだ出現場所の文書と、一つ前の出現場所の文書が異なっていれば、それは最初の出現場所であり、同じであれば、２番目以降の出現場所である。最初の出現場所であれば、Ｓ５８に進み、その文書内におけるａの出現回数ｄｔｆを計算し、ａの文書内における重みを決める。また、sequence_num=1とする。sequence_numは、選らんだ出現場所が文書内において何番目のａの出現場所かを表すシーケンス番号である。
【００８９】
Ｓ５９では、文書内のシーケンス番号sequence_num、入力文字列Ｘにおけるａの出現場所（以下、startX）、文書内におけるａの出現場所（以下、startdoc）、ａの長さ（以下、termlength）、ａの重み（以下、score）を組にして一致情報管理テーブルに記録し、sequence_numに１を加える。ただし、scoreに記録される値はａのそのままの重みではなく、ａの重みからp0fitを引いた値を記録する。これは、類似度を一致したｎグラムの重みの加算で計算する場合、選別された各部分文字列について、それを含まない文書の類似度にそれぞれの部分文字列のp0fitを加算する代わりに、一致したｎグラムの重みからp0fitを引いた値を加算しておき、最後に全ての類似度に対して重みのオフセットp0fit_sumを加えることによって、計算の手間を減らすための工夫である。
【００９０】
Ｓ６０では、sequence_numとｔｆの値を比較して、ａの全ての出現場所について一致情報の記録を行ったかどうかを判定する。もし、記録していない一致情報があれば、Ｓ５６で次のａの出現場所を選び、Ｓ５９までの処理を繰り返す。もし、ａの全ての出現場所について一致情報の記録をしていればＳ６１に進む。
【００９１】
Ｓ６１では、部分文字列管理テーブル内の全ての部分文字列について、一致情報の収集を行ったかどうかを判定する。もし、一致情報の収集をしていない部分文字列があれば、Ｓ５２で、まだ選んでいない部分文字列をａに読み込み、Ｓ６０までの処理を繰り返す。もし、すべての部分文字列について一致情報の収集を終えていれば、Ｓ６２で、得られた一致情報管理テーブルを返す。
【００９２】
図６は、入力文章Ｘと文書Ｙの類似度を、一致情報管理テーブルから取り出したリストを用いて、一致した文字列の重みの加算によって求める処理フローである。
【００９３】
まず、Ｓ７１で、ＸとＹの類似度（以下、sim）を０に初期化する。
【００９４】
Ｓ７２では、一致情報管理テーブルに記録されているＹに関するリストからある一つを選び、Ｉに読み込む。
【００９５】
Ｓ７３では、読み込んだＩのsequence_numが１かどうかを判定する。これは、同一の部分文字列のscoreをsimに重複して加算しないための処理である。もし、sequence_numが１でなければ、Ｓ７４をスキップし、Ｓ７５に進む。sequence_num=1であれば、Ｓ７４で、simにＩのscoreを加算する。
【００９６】
Ｓ７５では、Ｙに関する一致情報のリストに記録された全ての一致情報について調べたかどうかを判定する。もし、全ての一致情報について調べていれば、Ｓ７６で、simに文書全体の重みのオフセットp0fit_sumを加算する。まだ、調べていない一致情報があれば、Ｓ７２で、まだ調べていない一致情報を選んでＩに読み込み、Ｓ７４までの処理を繰り返す。
【００９７】
Ｓ７７は、得られたsimをＸとＹの類似度として返す処理である。
【００９８】
図７は、図５のＳ５３における、p0fit、p1fit、p2fit、p3fit、p4fitの計算処理フローを示す。
【００９９】
まず、Ｓ８１で、p0fit、p1fit、p2fit、p3fit、p4fitをすべて０に初期化する。
【０１００】
Ｓ８２では、部分文字列ａのｄｆを計算し、Ｓ８３で、ｄｆと文書データベース内の文書の総数Ｎからｉｄｆを計算する。このｉｄｆは、情報理論の分野における情報量を背景とする値で、この値を部分文字列の重みとする方法も良く知られている。
【０１０１】
Ｓ８４では、部分文字列ａが検索に有効な部分文字列であるかどうかを判定するための閾値tf_thresholdを計算する。
【０１０２】
Ｓ８５では、ｔｆとｄｆの値から部分文字列ａが検索に有効かどうかを判定する。ｔｆ /ｄｆ > tf_thresholdであれば、検索に有効な部分文字列であると判断し、Ｓ８６に進む。そうでなければ、検索には有効でないと判断して、Ｓ８６、Ｓ８７をスキップし、Ｓ８８でp0fit、p1fit、p2fit、p3fit、p4fitを返す。つまり、p0fit、p1fit、p2fit、p3fit、p4fitの値は全て０が返される。
【０１０３】
Ｓ８６では、p0fit、p1fit、p2fit、p3fit、p4fitを計算する。
【０１０４】
Ｓ８７の関数MAXとMINは、それぞれ、引数に与えられた数値の最大値もしくは最小値を返す関数で、この関数により、p0fit、p1fit、p2fit、p3fit、p4fitの値をLB以上UB以下の範囲に制限している。LBとUBは共にp0fit、p1fit、p2fit、p3fit、p4fitの分布を制限するパラメータである。Ｓ８８は、p0fit、p1fit、p2fit、p3fit、p4fitを返す処理である。
【０１０５】
以上の説明からも分かる通り、重みp0fit、p1fit、p2fit、p3fit、p4fitは、ｔｆ、ｄｆ、ｉｄｆの関数として求められる。Ｓ８４とＳ８６に用いている係数は、Christopher D. Manning and Hinrich Schutze, Foundations of Statistical Natural Language Processing, The MIT Press, Cambridge, Massachusetts, pp.529-574, 1999.に開示されている理論に基づき、ドキュメントデータの観測値を求めることによって定めた。なおこれらの係数は示された数値に限定されるものではなく、目的に応じて適切な値にすることが許容される。
【０１０６】
図５のＳ５３における、p0fit、p1fit、p2fit、p3fit、p4fitの計算処理フローとしては、図７で示したフローの代わりに、図１５に示すフローを適用することもできる。図１５における計算処理フローを以下に述べる。
【０１０７】
まず、Ｓ１８１で、p0fit、p1fit、p2fit、p3fit、p4fitをすべて０に初期化する。
【０１０８】
Ｓ１８２では、部分文字列ａのｄｆと、部分文字列ａが２回以上出現する文書データベース中の文書の数（以下、ｄｆ２と記す）を計算する。Ｓ１８３で、ｄｆと文書データベース内の文書の総数Ｎからｉｄｆを計算する。
【０１０９】
Ｓ１８４では、部分文字列ａが検索に有効な部分文字列であるかどうかを判定するための閾値df2_thresholdを０．２２に設定する。
【０１１０】
Ｓ１８５では、ｄｆとｄｆ２の値から部分文字列ａが検索に有効かどうかを判定する。ｄｆ２ /ｄｆ > df2_thresholdであれば、検索に有効な部分文字列であると判断し、Ｓ１８６に進む。そうでなければ、検索には有効でないと判断して、Ｓ１８６、Ｓ１８７をスキップし、Ｓ１８８でp0fit、p1fit、p2fit、p3fit、p4fitを返す。つまり、p0fit、p1fit、p2fit、p3fit、p4fitの値は全て０が返される。
【０１１１】
Ｓ１８６では、p0fit、p1fit、p2fit、p3fit、p4fitを計算する。
【０１１２】
Ｓ１８７は図７のＳ８７と同様に、p0fit、p1fit、p2fit、p3fit、p4fitの値をLB以上UB以下の範囲に制限するものである。LBとUBは共にp0fit、p1fit、p2fit、p3fit、p4fitの分布を制限するパラメータである。Ｓ１８８は、p0fit、p1fit、p2fit、p3fit、p4fitを返す処理である。
【０１１３】
以上の説明からも分かる通り、図１５の計算処理フローでは、部分文字列ａが検索に有効かどうかを判定する基準として、先に述べた図７の計算処理フローにおけるｔｆの代わりにｄｆ２を用いている。ｄｆ２／ｄｆは、部分文字列の出現集中度、つまり、ある部分文字列が特定の文書にのみ集中して出現する度合を表しており、この情報を用いて部分文字列の選別を行うことにより、検索精度の向上を図っている。
【０１１４】
Ｓ１８３における閾値df2_thresholdおよびＳ１８６に用いている係数は、示された数値に限定されるものではなく、目的に応じて適切な値にすることが許容される。
【０１１５】
図８に、一致情報管理テーブルの構成図を示す。一致情報管理テーブルは、文書番号毎の一致情報のリストによって構成される。図８では、文書番号０００２に一致情報１と一致情報５が、文書番号０１００に一致情報２、一致情報３と一致情報６が、文書番号０１１１に一致情報４と一致情報７がリストとして記録されている。それぞれの一致情報には、部分文字列の文書内におけるシーケンス番号sequence_num、入力文字列Ｘにおける部分文字列の出現場所（startX）、文書内における部分文字列の出現場所（startdoc）、部分文字列の長さ（termlength）、部分文字列に付けられた重み（score）が格納されている。
【０１１６】
新たに、文書番号０００２に関する一致情報８が得られた場合、図８のように、これまで一致情報５を指していたリストの先頭を指すポインタは一致情報８を指し、一致情報８から一致情報５へのポインタが張られ、文書番号０００２のリストの先頭に一致情報８は記録される。
【０１１７】
（第３実施例）
次に、ｎグラムＤＰ類似度に基づき、入力された文字列と最も類似度の高い文書を検索する文書検索装置の実施例を図９に示す。この文書検索装置は、文書データベース１０、文字列入力部１１、部分文字列選別部１３（内部の図示は省略）、一致情報収集部１４（内部の図示は省略）、類似度算出部１７、類似度算出制御部１８、再帰実行制御部１９、及び、検索結果出力部１２から構成されている。
【０１１８】
文書データベース１０、文字列入力部１１、部分文字列選別部１３、一致情報収集部１４、及び、検索結果出力部１２は実施例１の同符号を付した部分と同じ機能・構成であり説明を省略する。
【０１１９】
類似度算出制御部１８は一致情報管理テーブルＴ２より、ある１つの文書Ｙに関するリストを取り出し、文字列ＸとＹとともに類似度算出部１７に与える。
【０１２０】
類似度算出部１７は、与えられた一致情報のリストより、式（１）または式（２）に基づいてＸとＹの類似度を算出する。この類似度を算出する途中で、一部分の文字列について同様に類似度を求める必要がある。これは、再帰実行制御部１９により、類似度算出部１７を繰り返し用いることで実施する。類似度算出部１７は一致文字列類似度算出部６１、任意文字列類似度算出部６２、最大値選択部６３から成る。一致文字列類似度算出部６１は式（３）のSimDPs(α, β)を計算する。任意文字列類似度算出部６２は式（５）のSimDPg(α, β)を計算する。最大値選択部６３は、これらに対して関数MAXを実施することで、式（２）のSimDP(α, β)を算出する。なお、類似度算出部１７の受け取った文字列α、βの両方が空文字のときは、再帰実行制御部１９によりSimDP(α,β) ＝0.0とする。この際、一致文字列類似度算出部６１、任意文字列類似度算出部６２、最大値選択部６３は動作させない。言うまでもなく、このSimDP(α,β) ＝0.0という値は、式（１）を実施するものである。
【０１２１】
一致文字列類似度算出部６１は、文字列分離制御部７１、文字列分離部７２、類似度算出部７３、加算部７４、最大値選択部７５により実施されており、式（３）のSimDPｓ(α,β)を算出する。αとβの一致する先頭の文字列が一致情報管理テーブルＴ２に記録された文字列である場合のみSimDPｓ(α,β)を算出する。
【０１２２】
まず、文字列分離制御部７１は、一致文字列類似度算出部６１が受け取った文字列α(=ξγ)、β(=ξδ)において、一致する文字列ξがない場合、すなわち、一致する文字列ξが空文字列の場合は、式（１）に従い、SimDPｓ(α,β)＝0.0とする。
【０１２３】
次に、文字列分離制御部７１は、一致文字列類似度算出部６１が受け取った文字列α(=ξγ)、β(=ξδ)において、一致する文字列ξがある場合は、全てのξに関して、文字列分離部７２、類似度算出部７３、加算部７４を動作させて、式（３）に含まれるScore(ξ)＋SimDP(γ, δ)を計算させる。そして、最も大きな値を最大値選択部７５により選択する。このことにより、式（３）に示すSimDPs(α,β)が求まる。
【０１２４】
文字列分離部７２は、文字列αをξとγに、文字列βをξとδに分離した後に一致情報管理テーブルＴ２を参照してξの重みScore(ξ)を加算部７４に与え、γとδを類似度算出部７３に与える。類似度算出部７３は、式（３）のSimDP(γ, δ)を算出する。類似度算出部７３は、実際には、再帰実行制御部１７により、類似度算出部１６をγとδに対して適用することで、実施する。加算部７４は、式（３）の加算を行う。
【０１２５】
任意文字列類似度算出部６２は、類似度算出部８１〜８３、最大値選択部８４により実施されており、式（２）のSimDPg(α,β)を算出する。先頭の文字列が異なる場合か、先頭の文字列は一致するが一致情報管理テーブルに登録されていない文字列の場合に任意文字列類似度算出部６２は実行される。受け取った文字列α(=ζγ)、β(=ηδ)の先頭の１文字ζ、ηの有無に関する各場合に対応して、類似度算出部８１、８２、８３は、それぞれ式（５）のSimDP(α,δ), SimDP(γ,β), SimDP(γ,δ)を求める。類似度算出部８１〜８３は、実際には、再帰実行制御部１９により、類似度算出部１７を、αとδ、γとβ、γとδのそれぞれに対して適用することで、実施する。最大値選択部８４は、式（５）の関数MAXを実施する。
【０１２６】
（第４実施例）
ソフトウエアにより文字列Ｘと文字列ＹのｎグラムＤＰ類似度を求める処理フローを図１０と図１１に示す。この処理は、図３のＳ１６の内部処理として、図６で説明した処理の代わりに用いることが可能である。また、実行にあたっては第２実施例で示したコンピュータシステムを用いている。
【０１２７】
まず、Ｓ９１では、ＸとＹそれぞれにおいて、リストに記録された部分文字列の先頭文字と最終文字の中で、最も前にある先頭文字の場所minX、minYと、最も後ろにある最終文字の場所maxX、maxYを求め、長さmaxX-minX+1の配列X_indexと、長さmaxY-minY+1の配列Y_indexを用意し、全ての要素を−１に初期化する。これらの配列は、それぞれ、ＸのminXからmaxXまでの各文字、ＹのminYからmaxYまでの各文字と対応している。
【０１２８】
Ｓ９２からＳ９４の処理では、ＸにおけるminXからmaxXまでの各文字、ＹにおけるminYからmaxYまでの各文字で、リストに記録された各部分文字列の先頭文字もしくは最終文字にあたる文字と対応する配列X_index、Y_indexの要素に０を代入する。
【０１２９】
Ｓ９５からＳ９９の処理では、X_index[ｉ]=0であるｉに対し、前から順に、０,１,２,…, X_index_num-1と通し番号を振り、その番号をX_index[ｉ]に代入する。従って、X_index_numは、X_index[ｉ]≠−１であるｉの数である。
【０１３０】
Ｓ１００からＳ１０４では、Y_indexに対して同様の処理を行う。Y_index[ｊ]=0であるｊに対し、前から順に、０,１,２,…, Y_index_num-1と通し番号を振り、その番号をY_index[ｊ]に代入する。従って、Y_index_numは、Y_index[ｊ]≠−１であるｊの数である。
【０１３１】
Ｓ１０５では、リストに記録されたＸとＹの一致情報を、まずＸにおける部分文字列の出現する順に並び替える。次にＸにおける部分文字列の出現する順が同じものについて、Ｙにおける部分文字列の出現する順に並び替え、一致情報の数をｍに読み込む。
【０１３２】
次に、類似度をＤＰによって効率的に求めるための準備として、(X_index_num+2)行(Y_index_num+2)列のスコア表scoretableを作り、表の全ての要素を０に初期化する。この表は、縦方向が、文字列Ｘの中で、リストに記録された部分文字列の先頭文字もしくは最終文字にあたる文字、横方向が、文字列Ｙの中で、リストに記録された部分文字列の先頭文字もしくは最終文字にあたる文字に対応している。
【０１３３】
Ｓ１０６では、ｋとｉを、k=1、i=0に初期化する。
【０１３４】
Ｓ１０７では、ｊをj=0に初期化する。変数ｋは、現在、先頭からｋ番目の一致情報について注目していることを表し、ｉとｊは、それぞれ、ＸとＹにおけるリストに記録された部分文字列の先頭文字もしくは最終文字の中で、どの文字に注目しているかを表す変数である。Ｓ１０８では、現在のスコアとして、currentscoreにscoretable[ｉ] [ｊ]を代入する。
【０１３５】
ここで、説明の便宜上、リストの先頭からｋ番目の一致情報を、それぞれ、startX(k)、startdoc(k)、termlength(k)、score(k)と表すことにする。
【０１３６】
Ｓ１０９では、ｉとｊが指す場所が、前からｋ番目の一致情報の部分文字列が出現する場所と一致しているかどうかを判定する。一致していれば、Ｓ１１０に進み、一致していなければ、Ｓ１１４に進む。
【０１３７】
Ｓ１１０では、スコア表において、一致した部分文字列の最終文字と対応する行番号と列番号を求め、それぞれ、target_iとtarget_jに代入する。
【０１３８】
Ｓ１１１では、scoretable[target_i][target_j]において、現段階で得られているスコアと、currentscoreに一致する部分文字列の重みscore(k)を加算して得られるスコアを比較し、もし、scoretable[target_i][target_j]よりcurrentscore+score(k)の方が大きければ、Ｓ１１２で、scoretable[target_i][target_j]にcurrentscore+score(k)を代入する。そうでなければ、Ｓ１１２をスキップし、Ｓ１１３に進む。
【０１３９】
Ｓ１１３では、ｋの値に１を加え、リスト内の次の一致情報に注目し、Ｓ１０９に戻る。Ｓ１０９では、次の一致情報もｉとｊを出現場所とするならＳ１１３までの処理を繰り返し、そうでなければ、Ｓ１１４に進む。
【０１４０】
Ｓ１１４からＳ１１９までの処理では、現在のスコアcurrentscoreとスコア表の右、下、右下のスコアを比較し、currentscoreの方が大きければcurrentscoreを代入する。
【０１４１】
Ｓ１２０では、ｊがスコア表の右端まで来たかどうかを判定する。もし、右端まで来ていなければ、Ｓ１２１でｊに１を加え、Ｓ１０８に戻り、Ｓ１１９までの処理を繰り返す。右端まで来ていれば、Ｓ１２２に進む。
【０１４２】
Ｓ１２２では、ｉがスコア表の下端までに来たかどうかを判定する。もし、下端まで来ていなければ、Ｓ１２３でｉに１を加え、Ｓ１０７に戻り、Ｓ１２０までの処理を繰り返す。下端までていれば、Ｓ１２４に進み、scoretable[X_index_num+1][Y_index_num+1]をＸとＹの類似度として返す。
【０１４３】
【発明の効果】
請求項１に記載の発明によれば、入力された文字列から切り出した部分文字列のうち、文書データベース内の文書との類似度算出に関して効果のある文字列を選別して、類似度を求めることができる。すなわち検索に効果の高い文字列に限定して類似度を求めることができる。
【０１４４】
請求項２に記載の発明によれば、二つの文字列それぞれにおける順序に適合し、かつ、共通する部分文字列に着目して類似度を求めることができる。すなわち文字列の出現順序を考慮した類似度が求められる。
【０１４５】
請求項３に記載の発明によれば、類似度算出に関する効果の大きな順に文字列を選別して、類似度を求めることができる。これにより決まった類似度はより適切な値となる。
【０１４６】
請求項４に記載の発明によれば、一致した部分文字列の重みを加算する方法だけでなく、その他の類似度算出方法を組み合わせることができる。これにより検索精度が更に向上する。
【０１４７】
請求項５に記載の発明によれば、入力された文字列から切り出した部分文字列のうち、文書データベース内の文書との類似度算出に関して効果のある文字列を選別して、検索に効果の高い文字列に限定して類似度を求める装置を実現できる。
【０１４８】
請求項６に記載の発明によれば、二つの文字列それぞれにおける順序に適合し、かつ、共通する部分文字列に着目して文字列の出現順序を考慮した類似度を求める装置を実現できる。
【０１４９】
請求項７の発明によれば、入力された文字列から切り出した部分文字列のうち、文書データベース内の文書との類似度算出に関して効果のある文字列を選別して、検索に効果の高い文字列に限定して類似度を求めるプログラムを提供できる。
【０１５０】
請求項８に記載の発明によれば、二つの文字列それぞれにおける順序に適合し、かつ、共通する部分文字列に着目して文字列の出現順序を考慮した類似度を求めるプログラムを提供できる。
【０１５１】
請求項９に記載の発明によれば、以上述べたような効果を種々のコンピュータ上で実現できる。
【０１５２】
次に、第１および第２の実施例に関する検索性能を説明する。入力文字列から切り出される部分文字列を選別する効果と、部分文字列の選別基準にｄｆの代わりにｔｆを用いることの効果を確認するための評価実験を行った。
【０１５３】
選別の基準にｔｆ、ｄｆを用いた時の、選択した部分文字列の数と検索精度の関係を図１２に、選別した部分文字列の数と検索時間の関係を図１３に示す。検索精度には、１１ｐｔ平均精度と呼ばれる値を用いた。１１ｐｔ平均精度とは、再現率（０〜１）に対し、０．１刻みで１〜１１点を割り当て、それぞれの値を平均した評価指数で、詳細については、G Salton and M. J MacGill, Introduction to Modern Information Retrieval, p174-181, MacGraw-Hill Book Co., New York, 1983.に開示されている。
【０１５４】
入力文字列から切り出す部分文字列の長さは２に、つまりbigramのみとした。また、図７のＳ８７で用いるパラメータLBとUBは、それぞれ、LB=０、UB=ｉｄｆとした。用いた文書データは、NTCIR1テストコレクションと呼ばれる代表的な類似情報検索用テストデータで、約３００，０００件の文書と５３件の検索文章を含んでいる。
【０１５５】
図１２、図１３共に、横軸には選択した部分文字列の数、つまりSubStringLimitの値を、図１２の縦軸には検索精度を、図１３の縦軸には５３件の検索文章を検索するのに要した時間を示している。
【０１５６】
図１２を見ると、ｔｆ、ｄｆ共に、SubStringLimitの値が小さい時には、SubStringLimitを増加させることによって検索精度が向上することが確認できるが、ある程度大きくなると、SubStringLimitの値を増加させても検索精度があまり変化しないことが確認できる。このことから、SubStringLimitを適当な値に設定してやれば、部分文字列の選別を行っても、検索精度の低下を抑えることができる。また、ｔｆとｄｆを比較すると、ｄｆを基準とした選別による検索精度の方が上回っていることが確認できるが、SubStringLimitの値がある程度大きくなると、ｔｆを基準として選別した場合でも、ｄｆの時とほぼ同等の検索精度を持つことが確認できる。
【０１５７】
図１３を見ると、ｔｆ、ｄｆ共に、SubStringLimitの値が減少するにつれ検索時間が短くなっており、部分文字列を選別することによる高速化の効果が確認できる。また、ｔｆとｄｆの比較をすると、ｔｆを用いた方の検索時間が小さく、SubStringLimitの値が小さいほどその差は大きくなることが確認できる。仮に、SubStringLimitの値を、ｔｆ、ｄｆ共に高い検索精度を示している値、SubStringLimit=22に設定したとすると、その時の検索時間は、ｔｆが２６４．６秒、ｄｆが３６７．１秒で、１．４倍ほどｔｆの方が高速である。このように、本発明によって検索時間を向上させることができる。
【０１５８】
次に、図３のＳ１６における類似度の算出に、第３および第４実施例による方法を適用した時の検索性能を説明する。類似度の算出法に、図６の加算による方法を用いた場合と、図１０、１１のＤＰによる方法を用いた場合の検索精度の比較を行い、その結果を図１４に示す。検索精度には、１１ｐｔ平均精度を用いた。入力文字列から切り出す部分文字列の長さは２に、つまりbigramのみとし、図７のＳ８７で用いるパラメータLBとUBは、それぞれ、LB=0、UB=ｉｄｆとした。用いた文書データは、NTCIR1テストコレクションである。
【０１５９】
図１４の横軸には選択した部分文字列の数、つまりSubStringLimitの値を、縦軸には検索精度を示している。図１４を見ると、SubStringLimitが１５以下の時には、検索精度に大きな差はないが、１５を超えた場合には、ＤＰを用いた方法が加算による方法に比べ、検索精度が上回っていることが確認できる。また、検索時間を測定した所、ＤＰによる方法は、加算による方法に比べ約２倍の検索時間を要すること、既存のＤＰによる方法と比較すると数十倍高速であることが確認された。
【０１６０】
このように、本発明によって、収集した一致情報に対しＤＰを適用することで、加算による方法よりも検索精度を向上することができ、既存のＤＰによる方法と比べ高速に類似度を算出できることができる。
【図面の簡単な説明】
【図１】本発明による文書検索装置の実施例を示す図である。
【図２】本発明により文章検索を行う計算機システムの実施例を示す図である。
【図３】本発明の実施例の文章検索を行う処理のフローチャートである。
【図４】文字列から切り出される部分文字列の選別を行う処理のフローチャートである。
【図５】一致情報を収集し、記録する処理のフローチャートである。
【図６】一致情報から加算による類似度を求める処理のフローチャートである。
【図７】部分文字列の重みを求める処理のフローチャートである。
【図８】一致情報管理テーブルの構成図である。
【図９】本発明による文書検索装置の別の実施例を示す図である。
【図１０】一致情報からｎグラムＤＰ類似度を求める処理の前半部分のフローチャートである。
【図１１】一致情報からｎグラムＤＰ類似度を求める処理の後半部分のフローチャートである。
【図１２】選別の基準にｔｆ、ｄｆを用いた時の、選択した部分文字列の数と検索精度の関係を示す図である。
【図１３】選別の基準にｔｆ、ｄｆを用いた時の、選別した部分文字列の数と検索時間の関係を示す図である。
【図１４】本発明におけるＤＰを用いた類似度算出法と加算による類似度算出法の、検索精度の対比を示す図である。
【図１５】部分文字列の重みを求める別の処理のフローチャートである。
【符号の説明】
１０：文書データベース
１０ａ、１０ｂ、１０ｃ：文書
１１：文字列入力部
１２：検索結果出力部
１３：部分文字列選別部
１４：一致情報収集部
１５、１７、７３、８１、８２、８３：類似度算出部
１６、１８：類似度算出制御部
１９：再帰実行制御部
３１：部分文字列切り出し制御部
３２：部分文字列切り出し部
３３：文字列出現頻度算出部
３４：部分文字列登録部
４１：一致情報収集制御部
４２：文字列出現場所検索部
４３：文字列重み算出部
４４：一致情報登録制御部
４５：一致情報登録部
５１：文字列重み加算制御部
５２：文字列重み加算部
６１：一致文字列類似度算出部
６２：任意文字列類似度算出部
６３、７５、８４：最大値選択部
７１：文字列分離制御部
７２：文字列分離部
７４：加算部
１０１：ディスプレイ
１０２：プリンタ
１０３：キーボード
１０４：フロッピー（Ｒ）ディスク装置
１０５：ＣＤ−ＲＯＭ装置
１０６：読み出し専用メモリ（ＲＯＭ）
１０７：ランダムアクセスメモリ（ＲＡＭ）
１０８：磁気ディスク装置
１０９：中央処理装置（ＣＰＵ）
１１０：通信インターフェイス
１１１：バス
１１２：フロッピー（Ｒ）ディスク
１１３：ＣＤ−ＲＯＭ
１１４：通信ネットワーク
【図１】
0004065695.tif 000002
【図２】
0004065695.tif 000003
【図３】
0004065695.tif 000004
【図４】
0004065695.tif 000005
【図５】
0004065695.tif 000006
【図６】
0004065695.tif 000007
【図７】
0004065695.tif 000008
【図８】
0004065695.tif 000009
【図９】
0004065695.tif 000010
【図１０】
0004065695.tif 000011
【図１１】
0004065695.tif 000012
【図１２】
0004065695.tif 000013
【図１３】
0004065695.tif 000014
【図１４】
0004065695.tif 000015
【図１５】
0004065695.tif 000016