(57)【要約】【課題】  重要度を考慮して、複数文書から文字列を検索する。【解決手段】  入力された検索文字列を構成する部分文字列が含まれる文書数が多いほど当該部分文字列の重要度を小さくし、部分文字列が出現する頻度が多いほど当該部分文字列の重要度を大きくする重要度の計算を行ない、前記前記検索文字列を構成する前記各部分文字列の重要度に基づいて、被検索文字列中の部分文字列によって構成される各文字列のスコアを計算することを特徴とする。【選択図】  図１
2006216085.tif 000002
【特許請求の範囲】
【請求項１】
複数文書から文字列を検索する情報処理装置であって、
入力された検索文字列を構成する各部分文字列の重要度を計算する文字列重要度計算手段と、
前記前記検索文字列を構成する前記各部分文字列の重要度に基づいて、被検索文字列中の部分文字列によって構成される各文字列のスコアを計算するスコア計算手段と、
前記スコア計算手段の結果に基づいて得られた検索結果を保持する検索結果保持手段と、を有し、
前記重要度計算手段は、部分文字列が含まれる文書数が多いほど当該部分文字列の重要度を小さくし、部分文字列が出現する頻度が多いほど当該部分文字列の重要度を大きくする計算を行なうことを特徴とする情報処理装置。
【請求項２】
処理ユニットとメモリとを有し、複数文書から文字列を検索する情報処理装置の情報処理方法であって、
前記処理ユニットが、入力された検索文字列を構成する各部分文字列の重要度を計算する文字列重要度計算工程と、
前記処理ユニットが、前記前記検索文字列を構成する前記各部分文字列の重要度に基づいて、被検索文字列中の部分文字列によって構成される各文字列のスコアを計算するスコア計算工程と、
前記メモリが、前記スコア計算手段の結果に基づいて得られた検索結果を保持する検索結果保持工程と、を有し、
前記重要度計算工程において、前記処理ユニットが、部分文字列が含まれる文書数が多いほど当該部分文字列の重要度を小さくし、部分文字列が出現する頻度が多いほど当該部分文字列の重要度を大きくする計算を行なうことを特徴とする情報処理装置の情報処理方法。
【請求項３】
処理ユニットとメモリとを有し、複数文書から文字列を検索する情報処理方法をコンピュータに実行させるためのプログラムを記憶した記憶媒体であって、
前記処理ユニットが、入力された検索文字列を構成する各部分文字列の重要度を計算する文字列重要度計算工程と、
前記処理ユニットが、前記前記検索文字列を構成する前記各部分文字列の重要度に基づいて、被検索文字列中の部分文字列によって構成される各文字列のスコアを計算するスコア計算工程と、
前記メモリが、前記スコア計算手段の結果に基づいて得られた検索結果を保持する検索結果保持工程と、を有し、
前記重要度計算工程においては、前記処理ユニットが、部分文字列が含まれる文書数が多いほど当該部分文字列の重要度を小さくし、部分文字列が出現する頻度が多いほど当該部分文字列の重要度を大きくする計算を行なうことを特徴とする情報処理方法をコンピュータに実行させるためのプログラムを記憶したコンピュータ読み出し可能な記憶媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、文書情報から文字列を検索する情報処理装置に関し、特に、指定する文字列に表層的に類似する文字列を検索するあいまい検索を行なう情報処理装置に関するものである。
【背景技術】
【０００２】
従来の、文書中の全ての文字列を検索対象とするテキスト検索装置では、検索文字列として語が与えられた場合に、その検索文字列に似た文字列をも検索するあいまい検索技術がある。
【０００３】
あいまい検索技術の一例として、北陸先端科学技術大学院大学情報科学研究科  Ｒｅｓｅａｒｃｈ  ＲｅｐｏｒｔＩＳ−ＲＲ−９３６Ｉ、「用例検索による日英翻訳支援システムＣＴＭ２  −−−部分文字列インデックスを用いた最適照合検索」において示されているあいまい検索技術がある。このあいまい検索技術では、検索文字列を長さｋの部分文字列に分解する。次に、各部分文字列が被検索テキスト内の特定のブロックに存在する場合に、そのブロックのスコアに１点加点をすることで、スコアが高いブロックを検索するものである。ｋは任意であるが、上記の文献では、ｋが２と３の２種類で行ない、その合計値をスコアとするのが適当であると示されている。
【０００４】
たとえば、図３に示す文書に対して、「全文検索」という語をあいまい検索するさいに、長さ２の部分文字列に分解した場合には、「全文」、「文検」、「検索」の３つの部分文字列に分解して、各ブロックにこの部分文字列が存在する個数を計算して、図４に示すスコアを得る。つまり、この文書においては、「文検索」と「全文検出」の語は、あいまい性の一致度のスコアとして同じスコア２を持つ結果となる。
【０００５】
また、別のあいまい検索技術の一例として、特開平０８−２３５１２号公報の第１の実施例において、検索文字列の構成文字が閾値以内の位置のずれで存在するテキスト検索の方法が示され、第２の実施例では、第１の実施例にさらに、部分文字列の一致の度合いを考慮したあいまい検索の方法が示されている。
【０００６】
また、別のあいまい検索技術の一例として、情報処理学会研究報告  情処研報Ｖｏｌ．９２  Ｎｏ．３２  ｐｐ．２７−３２（１９９２）に掲載されている「高速全文不完全一致検索システムの実現」において示されているあいまい検索技術がある。この技術内容についての詳細は示されていない。
【０００７】
しかし、いずれの技術も、検索文字列に表層的に近い被検索文字列をその文字列単独のスコア付けによって検索する技術であって、検索文字列の部分文字列の対象文書の中で生じる頻度を考慮に入れた検索をすることはできない。
【発明の開示】
【発明が解決しようとする課題】
【０００８】
上記従来例の技術によるテキスト検索装置では、表層的に近い文字列を検索するあいまい検索を行なうときに、検索文字列と被検索文字列単独の表層上の一致度を計算するだけであって、対象となる被検索文字列を構成する部分文字列が対象文書の中で持つ重要度を、あいまい性の計算に含めることができなかった。
【課題を解決するための手段】
【０００９】
上記課題を解決するために、本発明は、複数文書から文字列を検索する情報処理装置であって、入力された検索文字列を構成する各部分文字列の重要度を計算する文字列重要度計算手段と、前記前記検索文字列を構成する前記各部分文字列の重要度に基づいて、被検索文字列中の部分文字列によって構成される各文字列のスコアを計算するスコア計算手段と、前記スコア計算手段の結果に基づいて得られた検索結果を保持する検索結果保持手段と、を有し、前記重要度計算手段は、部分文字列が含まれる文書数が多いほど当該部分文字列の重要度を小さくし、部分文字列が出現する頻度が多いほど当該部分文字列の重要度を大きくする計算を行なうことを特徴とする情報処理装置を提供する。
【００１０】
また、上記課題を解決するために、本発明は、処理ユニットとメモリとを有し、複数文書から文字列を検索する情報処理装置の情報処理方法であって、前記処理ユニットが、入力された検索文字列を構成する各部分文字列の重要度を計算する文字列重要度計算工程と、前記処理ユニットが、前記前記検索文字列を構成する前記各部分文字列の重要度に基づいて、被検索文字列中の部分文字列によって構成される各文字列のスコアを計算するスコア計算工程と、前記メモリが、前記スコア計算手段の結果に基づいて得られた検索結果を保持する検索結果保持工程と、を有し、  前記重要度計算工程において、前記処理ユニットが、部分文字列が含まれる文書数が多いほど当該部分文字列の重要度を小さくし、部分文字列が出現する頻度が多いほど当該部分文字列の重要度を大きくする計算を行なうことを特徴とする情報処理装置の情報処理方法を提供する。
【００１１】
また、処理ユニットとメモリとを有し、複数文書から文字列を検索する情報処理方法をコンピュータに実行させるためのプログラムを記憶した記憶媒体であって、前記処理ユニットが、入力された検索文字列を構成する各部分文字列の重要度を計算する文字列重要度計算工程と、前記処理ユニットが、前記前記検索文字列を構成する前記各部分文字列の重要度に基づいて、被検索文字列中の部分文字列によって構成される各文字列のスコアを計算するスコア計算工程と、前記メモリが、前記スコア計算手段の結果に基づいて得られた検索結果を保持する検索結果保持工程と、を有し、前記重要度計算工程においては、前記処理ユニットが、部分文字列が含まれる文書数が多いほど当該部分文字列の重要度を小さくし、部分文字列が出現する頻度が多いほど当該部分文字列の重要度を大きくする計算を行なうことを特徴とする情報処理方法をコンピュータに実行させるためのプログラムを記憶したコンピュータ読み出し可能な記憶媒体を提供する。
【発明の効果】
【００１２】
以上説明したように、本発明によれば、検索文字列の文書中における重要度を考慮した検索ができる。
【発明を実施するための最良の形態】
【００１３】
以下、図面を参照して本発明の実施例を詳細に説明する。
【００１４】
図１は、本発明の一実施形態に係る装置の基本構成を示すブロック図である。
【００１５】
同図において、１０１は、検索を行なう文字列を保持する検索文字列保持部である。１０２は、検索文字列保持部１０１に保持された検索文字列を、スコア計算部１０３に渡し、その計算結果をもとに、類似度閾値を越える被検索文字列の文字位置を、検索結果として抽出するあいまい検索部である。１０３は、文字列重要度計算部１０４の計算結果と検索文字列と被検索文字列との表層的な類似度をもとに検索文字列と被検索文字列とのあいまい性を計算するスコア計算部である。１０４は、スコア計算において、検索文字列を構成する部分文字列の重要度を計算する文字列重要度計算部である。１０５は、あいまい検索部１０２による検索結果を保持する検索結果保持部である。
【００１６】
図５は実施形態１のテキスト検索装置の制御構成を表わすブロック図である。
【００１７】
同図において、１はＣＰＵであり、ＲＯＭ２に格納された制御プログラムを実行することにより各種の制御を実現する。２はＲＯＭであり、ＣＰＵ１によって実行される各種の制御プログラムを格納する。ＣＰＵ１とＲＯＭ２は、特に、後述するフローチャートで示される制御を実行することにより、図１で示した各部の機能を実現する。３はＲＡＭであり、各種データを一時的に保存する。ＲＡＭ３は、検索文字列保持部１０１、あいまい検索部１０２、スコア計算部１０３、文字列重要度計算部１０４、検索結果保持部１０５のための格納領域を提供する。４は入力部であり、検索文字列の入力や、類似度閾値設定のためのデータ入力等を行う。５はディスプレイであり、文書の表示や、検索結果の表示を行う。６は外部記憶装置であり、検索対象となる文書データ等を格納する。７はバスであり、図５に示された上記の各構成を接続する。
【００１８】
スコア計算部１０３と文字列重要度計算部１０４におけるスコアの計算方法には、様々なものが考えられるが、以下にその一例を示す。
【００１９】
検索文字列の長さをｍ、被検索文字列の仮想位置ｐを設定したときに、検索文字列を分解した各文字の被検索文字列中での出現位置
ｐｉ（１＜ｉ＜ｍ）で、ｐｊ，ｐｊ＋１（１＜ｊ＜ｍ−１）があって、
ｐｊ＝ｐｊ＋１−１
を満足する組を見つけた時に、その文字列の、被検索文字列の中での重要度を
１／（１＋ｌｏｇ２（ｋ））
とし、その値の和をあいまい性のスコアとする。ただし、ｋは、ｐｊ，ｐｊ＋１の文字列が被検索文字列の中で出現する回数とする。この重要度を計算するのが文字列重要度計算部１０４であり、その値の和を計算するのがスコア計算部である。このスコアの高い順にその仮想位置にある文字列を、あいまい性が少ない検索結果とする。
【００２０】
以下、図２のフローチャートを参照して、上記の類似度計算例に従った本装置の処理を説明する。
【００２１】
ステップＳ２０１では、検索文字列保持部１０１に保持されている検索文字列の長さをｍに代入する。また、ｎに１を代入する。例えば、検索文字列が「全文検索」である場合は、ｍ＝４、ｎ＝１となる。そしてステップＳ２０２に移る。
【００２２】
ステップＳ２０２では、検索文字列保持部１０１に保持されている検索文字列の１番目と２番目の文字がその順番で被検索文字列に現れる位置を第１配列に格納する。ステップＳ２０３では、その１、２文字目からなる文字列の当該被検索文字列における重要度を文字列重要度計算部１０４から得て、第１配列のスコアに格納する。
【００２３】
図６は、図２の被検索文字列を対象としたときに、検索文字列「全文検索」を検索しているときのステップＳ２０３を終了したときの状態を示している。第１配列の列６０１に「全文」の文字列が現れる位置を示し、列６０２には、「全文」の文字列の重要度を示している。この例では、「全文」が出現する回数ｋは２であるので、
１／（１＋ｌｏｇ２（２））＝０．５
が格納される。
【００２４】
ステップＳ２０４では、変数ｍとｎを比較し、ｎ＜ｍ−１である場合は、ステップＳ２０５に移る。ｎ＞ｍ−１である場合は、ステップＳ２０９に移る。ステップＳ２０５では、ｎの値を１増やす。そしてステップＳ２０６に移る。
【００２５】
ステップＳ２０６では、検索文字列保持部１０１に保持されている検索文字列のｎ番目とｎ＋１番目の文字がその順番で被検索文字列に現れる位置の値からｎ−１減じた値を第２配列に格納する。そしてステップＳ２０７に移る。
【００２６】
ステップＳ２０７では、そのｎ，ｎ＋１文字目からなる文字列の当該被検索文字列における重要度を文字列重要度計算部１０４から得て、第２配列のスコアに格納する。そしてステップＳ２０８に移る。
【００２７】
ステップＳ２０８では、第２配列中の各値ｐｉについて、次の処理を行なう。第１配列の列６０１にｐｉと同じ値が存在する場合は、第１配列の当該値と同じ行の列６０２の値に第２配列の値ｐｉに対応するスコアの値を加算する。
【００２８】
そうでない場合は、第１配列に新たに行を加え、当該行の列６０１の値をｐｉに、列６０２の値を第２配列の値ｐｉに対応するスコアの値にする。そしてステップＳ２０４に戻る。
【００２９】
図７は、先に示した例において、ｎ＝４のときの第１配列の状態を示している。
【００３０】
ステップＳ２０９では、第１配列の列６０２のスコアの値の大きい順に第１配列の行をソートする。そしてステップＳ２１０に移る。ステップＳ２１０では、第１配列の各行の値を、あいまい検索の結果として、列６０１の値を、被検索テキスト中の検索文字列の先頭文字の位置として、検索結果保持部１０５に保持する。そして全ての処理を終了する。
【００３１】
（他の実施形態）
上記実施形態では、文字列重要度計算部の重要度として、
１／（１＋ｌｏｇ２（ｋ））
（ただし、ｋは、ｐｊ、ｐｊ＋１の文字列が被検索文字列の中で出現する回数とする）を用いたが、これに限定されるものでなく、任意の重要度計算方法を用いてよい。
【００３２】
他の類似度計算の例として、複数文書からなる被検索文字列を対象としたあいまい検索の場合に、文書頻度逆数（ｄｏｃｕｍｅｎｔ  ｆｒｅｑｕｅｎｃｙ  ｉｎｖｅｒｓｅ：ｉｄｆと呼ぶ）を用いて、部分文字列が含まれる文書数が多い場合にはそのスコアを小さくする計算方法がある。
【００３３】
ｉｄｆは一般的に次の様に定義される。ある単語（ここでは部分文字列とする）が総文書Ｎ個の中で、ｄｆｊ個の文書に存在したときに、
ｉｄｆ＝ｌｏｇ（Ｎ／ｄｆｊ）
で計算される。この値に、検索対象の部分文字列の頻度（ｔｅｒｍ  ｆｒｅｑｕｅｎｃｙ：ｔｆと呼ぶ）を乗じて、部分文字列の重要度を計算する。
【００３４】
つまり、この場合の文字列重要度計算部では、
ｔｆ＊ｉｄｆ＝ｔｆ＊ｌｏｇ（Ｎ／ｄｆｊ）
を計算して、スコア計算部１０３に値を渡す。
【００３５】
（他の実施形態）
上記の実施形態では、あいまい検索部１０２には、スコア計算部１０３で求められたすべてのあいまい文字列として検索結果保持部１０５に渡していたが、これに限定されるものではなく、閾値を用いて検索結果の類似度を判定してもよい。この場合の一実施例の基本構成を示すブロック図を図８に示す。同図において、１０６は閾値を保持する類似度閾値保持部である。
【００３６】
この場合、図２のステップＳ２０９において、ソートされた第１配列のスコアの値と、類似度閾値保持部１０６に保存された閾値を比較して閾値を越えたスコアをもつものを検索結果とする。
【００３７】
（他の実施形態）
上記の実施形態では、スコア計算部１０３では、文字列重要度計算部１０４から渡される値の和をとってスコア計算を行なっていたが、これに限定されるものではなく、その他の計算式を用いても構わない。例えば、部分文字列の生起する個数で割り算を行ない平均値を用いるなどである。
【００３８】
（他の実施形態）
上記の実施形態では、類似度の閾値として類似度閾値に保持されている値を用いる場合について説明したが、これに限定されるものでなく、予め規定された閾値を用いてもよい。
【００３９】
上記の実施形態では、部分文字列として２文字を用いる場合について説明したが、これに限定されるものでなく、３文字以上の文字列を部分文字列として検索を行なってもよい。
【００４０】
上記の実施形態では、検索処理において、検索語の先頭文字から順次処理を行なう場合について説明したが、これに限定されるものでなく、検索語中の任意の文字から検索を行なってもよい。
【００４１】
上記の実施形態では、検索文字列中での部分文字列の生じる位置の違いを第２配列に格納する時に補正する場合について説明したが、これに限定されるものでなく、マージの計算時に位置の違いを考慮するなど、任意の箇所で違いを考慮してもよい。
【００４２】
上記の実施形態では、検索結果として文字位置を保持する場合について説明したが、これに限定されるものでなく、検索箇所を含むブロックを保持するなど、検索された文字列に関する任意の情報を保持してよい。
【００４３】
また、検索結果の表示方法については特に述べていないが、公知の技術により文書中でハイライト表示することができる。また、その場合、スコア別に色を変える等の識別表示をすることも可能である。
【００４４】
なお、本発明は、複数の機器から構成されるシステムに適用しても、１つの機器からなる装置に適用してもよい。前述した実施形態の機能を実現するソフトウエアのプログラムコードを記録した記録媒体を、システム或いは装置に供給し、そのシステム或いは装置のコンピュータ（またはＣＰＵやＭＰＵ）が記録媒体に格納されたプログラムコードを読み出し実行することによっても、達成されることは言うまでもない。この場合、記録媒体から読み出されたプログラムコード自体が前述した実施形態の機能を実現することになり、そのプログラムコードを記録した記録媒体は本発明を構成することになる。
【００４５】
プログラムコードを供給するための記録媒体としては、例えば、フロッピー（登録商標）ディスク、ハードディスク、光ディスク、光磁気ディスク、ＣＤーＲＯＭ、ＣＤーＲ、磁気テープ、不揮発性のメモリカード、ＲＯＭなどを用いることができる。
【００４６】
また、コンピュータが読み出したプログラムコードを実行することにより、前述した実施形態の機能が実現されるだけでなく、そのプログラムコードの指示に基づき、コンピュータ上で稼働しているＯＳなどが実際の処理の一部または全部を行ない、その処理によって前述した実施形態の機能が実現される場合も含まれることは言うまでもない。
【００４７】
更に、記録媒体から読み出されたプログラムコードが、コンピュータに挿入された機能拡張ボードやコンピュータに接続された機能拡張ユニットに備わるメモリに書き込まれた後、そのプログラムコードの指示に基づき、その機能拡張ボードや機能拡張ユニットに備わるＣＰＵなどが実際の処理の一部または全部を行ない、その処理によって前述した実施形態の機能が実現される場合も含まれることは言うまでもない。
【図面の簡単な説明】
【００４８】
【図１】本発明に係るテキスト検索装置の実施例の基本構成を示すブロック図である。
【図２】本発明に係るテキスト検索装置の実施例における処理の概要を示すフローチャートである。
【図３】被検索テキストの一例を示す図である。
【図４】従来のテキスト検索装置の例で用いるスコア計算を示す図である。
【図５】実施例１のテキスト検索装置の制御構成を表わすブロック図である。
【図６】本発明に係るテキスト検索装置の実施例で用いる配列の状態を示す図である。
【図７】本発明に係るテキスト検索装置の実施例で用いる配列の別の状態を示す図である。
【図８】本発明に係るテキスト検索装置の別の実施例の基本構成を示すブロック図である。
【図１】
2006216085.tif 000003
【図２】
2006216085.tif 000004
【図３】
2006216085.tif 000005
【図４】
2006216085.tif 000006
【図５】
2006216085.tif 000007
【図６】
2006216085.tif 000008
【図７】
2006216085.tif 000009
【図８】
2006216085.tif 000010