Ｎグラム検索のための転置インデックスの生成方法および生成装置、当該転置インデックスを用いた検索方法および検索装置、ならびに、コンピュータプログラム
【課題】データ容量が効率的に抑えられた転置インデックスの生成方法等を提供する。
【解決手段】文書入換ステップと、生成ステップと、合成ステップと、を備えた転置インデックスの生成方法であって、文書入換ステップでは、それぞれが、見出し語と対応する複数の説明文とから構成される複数の文書データ１８のうち、少なくとも１つの文書データ１８の複数の説明文の順序を入れ換えて、入換文書データを作成し、生成ステップでは、文書データ１８もしくは作成された入換文書データから、「Ｎ文字の文字列であるＮグラム（Ｎは自然数）」を抽出し、抽出されたＮグラムのそれぞれについて、当該文書データ１８もしくは当該入換文書データ中の出現位置を対応付けて、部分転置インデックスを生成し、複数の文書データ１８について生成された複数の部分転置インデックスから、転置インデックスを合成する。
【解決手段】文書入換ステップと、生成ステップと、合成ステップと、を備えた転置インデックスの生成方法であって、文書入換ステップでは、それぞれが、見出し語と対応する複数の説明文とから構成される複数の文書データ１８のうち、少なくとも１つの文書データ１８の複数の説明文の順序を入れ換えて、入換文書データを作成し、生成ステップでは、文書データ１８もしくは作成された入換文書データから、「Ｎ文字の文字列であるＮグラム（Ｎは自然数）」を抽出し、抽出されたＮグラムのそれぞれについて、当該文書データ１８もしくは当該入換文書データ中の出現位置を対応付けて、部分転置インデックスを生成し、複数の文書データ１８について生成された複数の部分転置インデックスから、転置インデックスを合成する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、Ｎグラム検索に関し、とくにＮグラム検索のための転置インデックスの生成方法および生成装置、当該転置インデックスを用いた検索方法および検索装置、ならびにコンピュータプログラムに関する。
【背景技術】
【０００２】
文書の電子化の増大に伴い、これまでに蓄積されてきた大量の文書群から所望の文書を見つけ出す検索技術の重要性が高まっている。
【０００３】
英語などの多くの言語においては、単語を索引単位として索引ファイルを作成して、これを用いて高速な検索処理を実現することが一般的である。しかし、日本語の場合、スペース等によって単語の切れ目が明示的に示されないため、しばしば、Ｎグラムを索引単位とする方法が用いられている。
【０００４】
Ｎグラムとは、連続するＮ文字からなる部分文字列のことである。Ｎグラムによる索引ファイル（以下、転置インデックスと呼称する）の作成には、文字列にのみ基づくため、単語を認識する必要がない。しかし、Ｎグラムによる転置インデックスは、単語を索引単位とするものに比べて、文書から抽出される索引単位の数が多くなるため、データ容量が大きくなりやすい。
【０００５】
このようなＮグラムによる転置インデックスのデータ容量を圧縮するための手法として、例えば非特許文献１には、以下のような方法が紹介されている。すなわち、Ｎグラムが文書中に出現する位置や回数などの値を転置インデックスに記録する際に、前の値との差分を取得し、その差分をゴロム符号やガンマ符号などの方式で可変長符号化することによって、転置インデックスを圧縮する。
【先行技術文献】
【非特許文献】
【０００６】
【非特許文献１】小川泰嗣，松田透，”ｎ−ｇｒａｍ索引を用いた効率的な文書検索法”，電子情報通信学会論文誌(D-I)，Vol.J82-D-I，No.1，pp.121-129，1999年1月
【発明の概要】
【発明が解決しようとする課題】
【０００７】
上記のような転置インデックスの圧縮方法は、取得された差分が小さな値であったときは圧縮率が大きくなるが、大きな値のときは圧縮率が小さくなる。すなわち、文書中におけるＮグラムの出現の仕方によって、あまり圧縮率されない場合もありうる。そこで、文書中におけるＮグラムの出現の仕方による影響を極力減らして、転置インデックスの圧縮効率を高めたい、との要望がある。
【０００８】
本発明は、以上のような課題を解決するためのものであり、データ容量が効率的に抑えられた転置インデックスの生成方法および生成装置、当該転置インデックスを用いた検索方法および検索装置、ならびに、コンピュータプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００９】
上記目的を達成するため、本発明の第１の観点にかかる転置インデックスの生成方法は、
それぞれが、見出し語と対応する複数の説明文とから構成される複数の文書データのうち、少なくとも１つの文書データの前記複数の説明文の順序を入れ換えて、入換文書データを作成する文書入換ステップと、
前記文書データもしくは前記作成された入換文書データから、「Ｎ文字の文字列であるＮグラム（Ｎは自然数）」を抽出し、抽出されたＮグラムのそれぞれについて、当該文書データもしくは当該入換文書データ中の出現位置を対応付けて、部分転置インデックスを生成する生成ステップと、
前記複数の文書データについて生成された複数の前記部分転置インデックスから、転置インデックスを合成する合成ステップと、
を備えることを特徴とする。
【００１０】
上記生成方法において、
前記生成ステップでは、前記文書データおよび当該文書データから作成された入換文書データから、それぞれ前記部分転置インデックスを生成し、当該それぞれ生成された部分転置インデックスのうち、容量が小さい部分転置インデックスを選定し、
前記合成ステップでは、前記複数の文書データについて選定された複数の前記部分転置インデックスから、転置インデックスを合成する、
ことが望ましい。
【００１１】
上記生成方法において、
前記文書入換ステップでは、前記文書データから、前記順序の入れ換え可能な組合せで前記順序を入れ換えて、当該組合せの数の入換文書データを作成し、
前記生成ステップでは、前記文書データおよび当該文書データから作成された前記組合せの数の入換文書データから、それぞれ前記部分転置インデックスを生成し、当該それぞれ生成された部分転置インデックスのうち、容量が最小の部分転置インデックスを選定する、
ことが望ましい。
【００１２】
上記生成方法において、
前記生成ステップでは、複数の文書データのうち、見出し語と対応する単一の説明文とから構成される文書データからも、前記部分転置インデックスを生成する、
ことが望ましい。
【００１３】
上記生成方法において、
前記生成ステップでは、前記抽出されたＮグラムのそれぞれについて、当該Ｎグラムに対応付けられた出現位置と隣接する出現位置との差分を対応付けて、部分転置インデックスを生成する、
ことが望ましい。
【００１４】
上記目的を達成するため、本発明の第２の観点にかかる検索方法は、
検索文字列からＮグラムを抽出する抽出ステップと、
上記の生成方法によって生成された転置インデックスから、前記検索文字列から抽出されたＮグラムに対応付けられた出現位置を取得する位置取得ステップと、
前記取得された出現位置に基づいて、前記複数の文書データのうちから、前記検索文字列を含む文書データを特定する文書特定ステップと、
を備えることを特徴とする。
【００１５】
上記目的を達成するため、本発明の第３の観点にかかる転置インデックスの生成装置は、
それぞれが、見出し語と対応する複数の説明文とから構成される複数の文書データのうち、少なくとも１つの文書データの前記複数の説明文の順序を入れ換えて、入換文書データを作成する文書入換手段と、
前記文書データもしくは前記作成された入換文書データから、「Ｎ文字の文字列であるＮグラム（Ｎは自然数）」を抽出し、抽出されたＮグラムのそれぞれについて、当該文書データもしくは当該入換文書データ中の出現位置を対応付けて、部分転置インデックスを生成する生成手段と、
前記複数の文書データについて生成された複数の前記部分転置インデックスから、転置インデックスを合成する合成手段と、
を備えることを特徴とする。
【００１６】
上記目的を達成するため、本発明の第４の観点にかかる検索装置は、
検索文字列からＮグラムを抽出する抽出手段と、
上記の生成方法によって生成された転置インデックスから、前記検索文字列から抽出されたＮグラムに対応付けられた出現位置を取得する位置取得手段と、
前記取得された出現位置に基づいて、前記複数の文書データのうちから、前記検索文字列を含む文書データを特定する文書特定手段と、
を備えることを特徴とする。
【００１７】
上記目的を達成するため、本発明の第５の観点にかかるコンピュータプログラムは、
コンピュータを、
それぞれが、見出し語と対応する複数の説明文とから構成される複数の文書データのうち、少なくとも１つの文書データの前記複数の説明文の順序を入れ換えて、入換文書データを作成する文書入換手段、
前記文書データもしくは前記作成された入換文書データから、「Ｎ文字の文字列であるＮグラム（Ｎは自然数）」を抽出し、抽出されたＮグラムのそれぞれについて、当該文書データもしくは当該入換文書データ中の出現位置を対応付けて、部分転置インデックスを生成する生成手段、
前記複数の文書データについて生成された複数の前記部分転置インデックスから、転置インデックスを合成する合成手段、
として機能させる。
【００１８】
上記目的を達成するため、本発明の第６の観点にかかるコンピュータプログラムは、
コンピュータを、
検索文字列からＮグラムを抽出する抽出手段、
上記の生成方法によって生成された転置インデックスから、前記検索文字列から抽出されたＮグラムに対応付けられた出現位置を取得する位置取得手段、
前記取得された出現位置に基づいて、前記複数の文書データのうちから、前記検索文字列を含む文書データを特定する文書特定手段、
として機能させる。
【発明の効果】
【００１９】
本発明によれば、データ容量が効率的に抑えられた転置インデックスの生成方法および生成装置、当該転置インデックスを用いた検索方法および検索装置、ならびに、コンピュータプログラムを提供することができる。
【図面の簡単な説明】
【００２０】
【図１】本発明に係る転置インデックスを生成する生成装置の概要構成の例を示す図である。
【図２】本発明に係る転置インデックスを搭載した検索装置の概要構成の例を示す図である。
【図３】本発明に係る複数の文書データの構成を示す図である。
【図４】本発明に係る生成装置の生成処理の流れを示すフローチャートである。
【図５】本発明に係る生成装置において、個々の文書データから部分転置インデックスを生成する処理の流れを示すフローチャートである。
【図６】（ａ）出現位置について隣接する出現位置との差分をとる前の部分転置インデックスの構成を示す図である。（ｂ）出現位置について隣接する出現位置との差分をとった後の部分転置インデックスの構成を示す図である。
【図７】文書データから作成可能な入換文書データの構成を示す図である。
【図８】複数の文書データ全体の転置インデックスの構成を示す図である。
【図９】本発明に係る検索装置の検索処理の流れを示すフローチャートである。
【図１０】本発明に係る転置インデックスを生成する生成装置の概要構成の別の例を示す図である。
【図１１】本発明に係る転置インデックスを搭載した検索装置の概要構成の別の例を示す図である。
【発明を実施するための形態】
【００２１】
以下、本発明の実施形態に係る転置インデックスの生成方法および生成装置、当該転置インデックスを用いた検索方法および検索装置、ならびに、これらをコンピュータ上にて実現するためのコンピュータプログラムについて説明する。以下に説明する実施形態は説明のためのものであり、本発明の範囲を制限するものではない。
【００２２】
本実施形態では、コンピュータ装置を、図１に示されるような転置インデックスの生成装置として構成する。また、図１に示される生成装置１０によって、本実施形態に係る転置インデックスの生成方法が実現される。
【００２３】
生成装置１０は、ＣＰＵ（Central Processing Unit）１１、ＲＯＭ（Read Only Memory）１２、ＲＡＭ（Random Access Memory）１３、ＨＤＤ（Hard Disk Drive）１４、入力装置１５、出力装置１６、通信制御装置１７により構成される。各構成要素は、命令やデータを転送するための伝送経路であるシステムバスにより、相互に接続されている。
【００２４】
ＣＰＵ１１は、生成装置１０全体の動作を制御し、各構成要素と接続され制御信号やデータをやりとりする。
ＲＯＭ１２は、生成装置１０全体の動作制御に必要なコンピュータプログラムや各種データを記憶する。ＣＰＵ１１は、ＲＯＭ１２に記憶されたコンピュータプログラムによって動作し、各種制御を実行する。
ＲＡＭ１３は、データやコンピュータプログラムを一時的に記憶するためのもので、ＲＯＭ１２から読み出したコンピュータプログラムやデータ、その他処理の進行に必要なデータが保持される。
ＨＤＤ１４は、転置インデックスの生成処理の動作のために必要なデータ等を記憶する。このＨＤＤ１４には、複数の文書データ１８が記憶される。生成装置１０は、この複数の文書データ１８をもとにして、転置インデックスを生成する。
入力装置１５は、例えばキーボードやタッチパネル等によって構成され、ユーザからの各種入力を受け付ける。
出力装置１６は、例えばディスプレイ等によって構成され、生成装置１０の種々の処理結果を出力する。
通信制御装置１７は、生成装置１０をインターネット等のコンピュータ通信網に接続するためのものであり、コンピュータ通信網に接続してデータをやり取りする場合に必要となる。
【００２５】
本実施形態では、生成装置１０は、文書入換手段と、生成手段と、合成手段と、を備える。これらは、上述したＣＰＵ１１が、ＲＯＭ１２やＲＡＭ１３と協働し、ＨＤＤ１４に記憶されたデータにアクセスしながら、入力装置１５や出力装置１６、通信制御装置１７を用いて外部とやり取りすることで、実現される。
【００２６】
具体的に、生成装置１０の文書入換手段は、それぞれが、見出し語と対応する複数の説明文とから構成される複数の文書データ１８のうち、少なくとも１つの文書データ１８の複数の説明文の順序を入れ換えて、入換文書データを作成する。このような文書入換手段として、例えばＣＰＵ１１が、ＲＯＭ１２やＲＡＭ１３と協働しながら、ＨＤＤ１４に記憶された文書データ１８にアクセスし、入換文書データをＲＡＭ１３に一時的に保持することにより、実現される。
【００２７】
そして、生成装置１０の生成手段は、文書データ１８もしくは作成された入換文書データから、「Ｎ文字の文字列であるＮグラム（Ｎは自然数）」を抽出し、抽出されたＮグラムのそれぞれについて、当該文書データ１８もしくは当該入換文書データ中の出現位置を対応付けて、部分転置インデックスを生成する。このような生成手段として、例えばＣＰＵ１１が、ＲＯＭ１２やＲＡＭ１３と協働しながら、保持された入換文書データから部分転置インデックスを生成して、生成された部分転置インデックスを再びＲＡＭ１３に保持することにより、実現される。
【００２８】
さらに、生成装置１０の合成手段は、複数の文書データ１８について生成された複数の部分転置インデックスから、転置インデックスを合成する。このような合成手段として、例えばＣＰＵ１１が、ＲＯＭ１２やＲＡＭ１３と協働しながら、出力装置１６やＨＤＤ１４、あるいは通信制御装置１７を介して、合成された転置インデックスを出力することで機能する。
【００２９】
このような生成装置１０によって生成された転置インデックスは、検索装置に搭載され、検索処理に用いられる。本実施形態では、コンピュータ装置を、図２に示されるような検索装置として構成する。また、図２に示される検索装置２０によって、本実施形態に係る転置インデックスの検索方法が実現される。
【００３０】
検索装置２０は、ＣＰＵ２１、ＲＯＭ２２、ＲＡＭ２３、ＨＤＤ２４、入力装置２５、出力装置２６、通信制御装置２７により構成される。各構成要素は、命令やデータを転送するための伝送経路であるシステムバスにより、相互に接続されている。
【００３１】
これらの構成要素は、基本的には図１に示された生成装置１０の構成要素と同等なものである。すなわち、図１では、文書データ１８から転置インデックスを生成するために機能した各構成要素が、ここでは生成された転置インデックスを用いて検索処理を行うために機能する。
【００３２】
すなわち、ＣＰＵ２１は、検索装置２０全体の動作を制御し、各構成要素と接続され制御信号やデータをやりとりする。
ＲＯＭ２２は、検索装置２０全体の動作制御に必要なコンピュータプログラムや各種データを記憶する。ＣＰＵ２１は、ＲＯＭ２２に記憶されたコンピュータプログラムによって動作し、各種制御を実行する。
ＲＡＭ２３は、データやコンピュータプログラムを一時的に記憶するためのもので、ＲＯＭ２２から読み出したコンピュータプログラムやデータ、その他処理の進行に必要なデータが保持される。
ＨＤＤ２４は、検索処理の動作のために必要なデータ等を記憶する。このＨＤＤ２４には、複数の文書データ１８と、生成装置１０によって生成された転置インデックス１９とが、記憶される。検索装置２０は、転置インデックス１９をもとに、ユーザによって指定された検索文字列が複数の文書データ１８の中のどの文書データ１８中に出現するかを特定する。
入力装置２５は、例えばキーボードやタッチパネル等によって構成され、ユーザからの各種入力を受け付ける。
出力装置２６は、例えばディスプレイ等によって構成され、検索装置２０の種々の処理結果を出力する。
通信制御装置２７は、検索装置２０をインターネット等のコンピュータ通信網に接続するためのものであり、コンピュータ通信網に接続してデータをやり取りする場合に必要となる。
【００３３】
本実施形態では、検索装置２０は、抽出手段と、位置取得手段と、文書特定手段と、を備える。これらは、上述したＣＰＵ２１が、ＲＯＭ２２やＲＡＭ２３と協働し、ＨＤＤ２４に記憶されたデータにアクセスしながら、入力装置２５や出力装置２６、通信制御装置２７を用いて外部とやり取りすることで、実現される。
【００３４】
具体的に、検索装置２０の抽出手段は、検索文字列からＮグラムを抽出する。このような抽出手段として、例えばＣＰＵ２１が、ＲＯＭ２２やＲＡＭ２３と協働しながら、入力装置２５を介してユーザから検索文字列を受け付け、抽出されたＮグラムをＲＡＭ２３に保持することにより、実現される。
【００３５】
そして、検索装置２０の位置取得手段は、生成装置１０によって生成された転置インデックス１９から、検索文字列から抽出されたＮグラムに対応付けられた出現位置を取得する。このような位置取得手段として、例えばＣＰＵ２１が、ＲＯＭ２２やＲＡＭ２３と協働しながら、ＨＤＤ２４に記憶された転置インデックス１９にアクセスし、取得された出現位置をＲＡＭ２３に保持することにより、実現される。
【００３６】
さらに、検索装置２０の文書特定手段は、取得された出現位置に基づいて、複数の文書データ１８のうちから、検索文字列を含む文書データ１８を特定する。このような文書特定手段として、例えばＣＰＵ２１が、ＲＯＭ２２やＲＡＭ２３と協働しながら、出力装置２６や通信制御装置２７を介して、特定された文書データ１８をユーザへ出力することにより、実現される。
【００３７】
文書データ１８は、図３に示されるように構成される。本実施形態では、図３に示されるような複数の文書データ１８ａ〜１８ｚの中から、所望の検索文字列を含む文書データ１８を見つけ出すための検索方法等が提供される。１つの文書データ１８は、１つの見出し語と複数の説明文から構成される。
【００３８】
具体的に、最初の文書データ１８ａにおいて、見出し語Ａには、３つの説明文Ａ１、Ａ２、Ａ３が対応付けられている。また、次の文書データ１８ｂでは、見出し語Ｂに、２つの説明文Ｂ１、Ｂ２が対応付けられ、文書エータ１８ｃでは、見出し語Ｃに、３つの説明文Ｃ１、Ｃ２、Ｃ３が対応付けられている。ここで、説明文の数は、必ずしも複数に限られず、文書データ１８ｄでの見出し語Ｄと説明文Ｄ１のように、説明文が１つであってもよい。また、図３のように１〜３個に限られず、４個以上であってもよい。
【００３９】
ここで、見出し語とは、その文書データ１８を表現する代表的な言葉を意味する。そして、説明文とは、対応する見出し語を説明する言葉を意味する。このような見出し語と対応する説明文とで構成される文書データ１８を複数有するものとして、例えば辞書のような文書が挙げられる。
【００４０】
そして、見出し語と説明文との間はスペースで区切られ、２つの説明文の間は読点で区切られる。以降、これらのスペースや読点を、「セパレータ」と称する。ここで、セパレータは、検索の対象にはならない。すなわち、本実施形態の検索装置２０は、例えば、見出し語Ａと説明文Ａ１にまたがるような、あるいは説明文Ａ１と説明文Ａ２にまたがるような、セパレータを含む検索文字列を検索の対象としない。
【００４１】
ここから、このような複数の文書データ１８から、転置インデックス１９を生成するための生成装置１０と、当該転置インデックス１９を用いて検索するための検索装置２０における、処理の流れの詳細を説明する。ここではまず、図４を参照して、転置インデックス１９の生成処理について、フローチャートを用いて説明していく。
【００４２】
生成装置１０は、例えば入力装置１５を介してユーザからの生成処理の開始の指示を受け付けることで、転置インデックス１９の生成処理を開始する。転置インデックス１９の生成処理が開始されると、まず生成装置１０の文書入換手段は、ＣＰＵ１１とＲＡＭ１３等の機能により、複数の文書データ１８のうちから、最初の文書データ１８を選択する（ステップＳ１０１）。すなわち、ＨＤＤ１４に記憶されている図３に示されたような複数の文書データ１８から、最初の文書データ１８を選択する。ここでは例えば、先頭の見出し語Ａの文書データ１８が選択される。
【００４３】
次に、生成装置１０の生成手段は、ＣＰＵ１１がＲＡＭ１３等と協働することで、選択された文書データ１８から、部分転置インデックスを生成し保持する（ステップＳ１０２）。ここで、部分転置インデックスとは、複数の文書データ１８全体から生成される転置インデックス１９と区別するため、複数の文書データ１８のうち個々の文書データ１８から生成された転置インデックス１９のことを指すものとする。このステップＳ１０２の処理については、詳細を図５のフローチャートを参照して説明する。
【００４４】
選択された文書データ１８から部分転置インデックスを生成するために、まず、文書データ１８から「Ｎ文字の文字列であるＮグラム（Ｎは自然数）」を抽出する（ステップＳ２０１）。すなわち、文書データ１８を構成する見出し語と説明文との文字列から、抽出可能なＮ文字列（Ｎグラム）をすべて抽出する。このとき、スペースや読点などのセパレータからはＮグラムを抽出しない。また、セパレータをまたぐようにＮグラムを抽出することもしない。
【００４５】
例えば、文書データ１８が、Ｎａ文字の見出し語と、Ｎｂ文字とＮｃ文字の２つの説明文から構成されるとする。Ｎの値が、Ｎａ、Ｎｂ、Ｎｃのいずれよりも大きな値でないとき、見出し語からはＮａ−Ｎ＋１個のＮグラムが、２つの説明文からはそれぞれＮｂ−Ｎ＋１個とＮｃ−Ｎ＋１個のＮグラムが、抽出される。すなわち、文書データ１８からは、これらの和であるＮａ＋Ｎｂ＋Ｎｃ−３Ｎ＋３個のＮグラムが抽出されることになる。
【００４６】
次に、生成装置１０の生成手段は、ＣＰＵ１１がＲＡＭ１３等と協働することで、抽出されたＮグラムのそれぞれについて、選択された文書データ１８中の出現位置を対応付ける（ステップＳ２０２）。すなわち、抽出されたＮグラムが、選択された文書データ１８中のどの位置にあったのかの情報を、抽出されたＮグラムそれぞれについて対応付ける。
【００４７】
そして、生成装置１０の生成手段は、ＣＰＵ１１がＲＡＭ１３等と協働することで、対応付けられた出現位置を昇順に並べて、隣接する出現位置との差分をとり（ステップＳ２０３）、部分転置インデックスを生成する（ステップＳ２０４）。昇順に並べられた出現位置と、モノグラム（Ｎ＝１のＮグラム）とを対応付けた部分転置インデックスは、例えば図６（ａ）のようになる。
【００４８】
この図６（ａ）では、選択された１つの文書データ１８から、「Ａ」〜「Ｚ」のモノグラムが抽出され、その文書データ１８中での出現位置が数字で対応付けられている。具体的に、例えばモノグラム「Ａ」には、「５」、「２２」、「３３」、「３５」、「８７」、「１２０」という６個の出現位置が対応付けられている。これはすなわち、選択された文書データ１８中に「Ａ」というモノグラムが、文書の先頭からそれぞれの文字列目の位置に６回出現するということを意味するものである。
【００４９】
ステップＳ２０３では、このようなＮグラム（図６（ａ）ではモノグラム）と出現位置とが対応付けられたものから、出現位置について隣接する出現位置との差分をとって、当該差分をＮグラムに対応付ける。図６（ｂ）は、図６（ａ）の出現位置について、隣接する出現位置との差分をとった後の様子を示している。
【００５０】
具体的に、例えばモノグラム「Ａ」では、図６（ａ）で２番目の出現位置であった「２２」は、１番目の出現位置「５」との差分をとられることで、「１７」となっている。また、３番目の出現位置であった「３３」は、２番目の出現位置であった「２２」との差分をとられることで、「１１」となっている。同様に図６（ｂ）では、４番目には「２（＝３５−３３）」が、５番目には「５２（＝８７−３５）」が、６番目には「３３（＝１２０−８７）」が、それぞれ前の出現位置との差分をとられて表示されている。なお、１番目の出現位置である「５」については、差分をとるべき前の出現位置がないため、図６（ａ）と図６（ｂ）で変化しない。
【００５１】
このように、選択された文書データ１８から抽出されたＮグラムのそれぞれについて、出現位置の差分を対応付けられたものを、生成装置１０は、部分転置インデックス２９としてＲＡＭ１３等に一時的に保持する。そして、図５におけるステップＳ１０２の処理を終える。
【００５２】
本実施形態では以上のように、部分転置インデックス２９を生成する際に出現位置についての差分をとる。これによって、部分転置インデックス２９に保存される出現位置の値は、差分をとる前に比べて小さな値に抑えられることができる。このような小さな値に抑えられた出現位置の情報に対して、例えばゴロム符号やガンマ符号などの方式で可変長符号化を用いて、小さな値ほど割り当てられる符号の長さを抑えることにより、差分をとる前の大きな値で出現位置を対応付けて生成した部分転置インデックス２９よりも、データ容量が抑えられた部分転置インデックス２９、さらにはそれらをあわせた全体の転置インデックス１９を生成することが可能となる。
【００５３】
本実施形態では、ここから、さらに部分転置インデックス２９のデータ容量を抑えるために、文書データ１８に含まれる説明文の順序を入れ換えて改めて部分転置インデックス２９を生成し、データ容量のより小さい方を採用する処理を行う。すなわち、後述する検索装置２０の処理では、上記図３に示されたような複数の文書データ１８のうちから、所望の検索文字列を含む文書データ１８（見出し語）を特定する。このとき、見出し語と説明文あるいは説明文同士を区切るセパレータを含んだ、あるいはまたいだ検索は行わないため、セパレータで区切られた複数の説明文の順番が入れ替わっていたとしても、検索結果には影響を与えない。そのため、本実施形態では、複数の説明文の順序を入れ換えて部分転置インデックス２９を生成して、データ容量のより小さい方を採用する処理を行う。
【００５４】
そのために、図４に戻って、生成装置１０の文書入換手段は、ＣＰＵ１１がＲＡＭ１３等と協働することで、選択された文書データ１８の説明文について、入れ換え可能な組合せを算出する（ステップＳ１０３）。例えば、上記図３の文書データ１８ａのように、３個の説明文Ａ１、Ａ２、Ａ３を有する場合、入れ換え可能な組合せは、「Ａ１、Ａ２、Ａ３」、「Ａ１、Ａ３、Ａ２」、「Ａ２、Ａ１、Ａ３」、「Ａ２、Ａ３、Ａ１」、「Ａ３、Ａ１、Ａ２」、「Ａ３、Ａ２、Ａ１」の６通り（入れ換え前を除けば５通り）がある。また、文書データ１８ｂのように、２個の説明文Ｂ１、Ｂ２を有する場合、入れ換え可能な組合せは、「Ｂ１、Ｂ２」、「Ｂ２、Ｂ１」の２通り（入れ換え前を除けば１通り）がある。一般的に、文書データ１８がＸ個の説明文を有する場合、Ｘ！（！は階乗）個の組合せがある。ここで、算出された組合せは、例えばＲＡＭ１３に一時的に保持される。
【００５５】
そして、生成装置１０の文書入換手段は、ＣＰＵ１１がＲＡＭ１３等と協働することで、すべての組合せを選択し終えたか、を判定する（ステップＳ１０４）。選択し終えてない場合（ステップＳ１０４；ＮＯ）、組合せを１つ選択し、その組合せで説明文を入れ換えて、入換文書データを作成する（ステップＳ１０５）。例えば、上記図３の文書データ１８ａのように、６個の入れ換え可能な組合せのうち、「Ａ１、Ａ３、Ａ２」を選択したとする。このとき、作成される入換文書データは、図７に示されるような入換文書データ２８ａのようになる。すなわち、入換文書データ２８ａでは、「見出し語Ａ」の後に、スペースを挟んで「説明文Ａ１、説明文Ａ３、説明文Ａ２」、というように、入れ換えられる前の文書データ１８ａから比べて、説明文Ａ２と説明文Ａ３の順序が、間の読点を挟んで入れ換えられている。作成された入換文書データ２８は、例えばＲＡＭ１３に一時的に保持される。
【００５６】
図４に戻って、この後、生成装置１０の生成手段は、ＣＰＵ１１がＲＡＭ１３等と協働することで、このような入換文書データ２８から、部分転置インデックス２９を生成する（ステップＳ１０６）。ここでの部分転置インデックス２９の生成処理は、上述したステップＳ１０２における処理と同じく、図５のフローチャートに示される。すなわち、ステップＳ１０２では、選択された（入換前の）文書データ１８から部分転置インデックス２９を生成したが、このステップＳ１０６では、ステップＳ１０２で用いられた文書データ１８から複数の説明文の順序が入れ換えられた入換文書データ２８から、部分転置インデックス２９を生成する。
【００５７】
そして、生成装置１０の生成手段は、ＣＰＵ１１がＲＡＭ１３等と協働することで、ステップＳ１０６で生成された部分転置インデックス２９を、ステップＳ１０２で生成された部分転置インデックス２９と比較して、容量が小さくなったかを判定する（ステップＳ１０７）。すなわち、入換文書データ２８から生成された部分転置インデックス２９では、入れ換え前の文書データ１８から生成された部分転置インデックス２９に比べて、説明文の順序が入れ換えられて生成されているので、抽出されるＮグラムに変化はないが、それぞれのＮグラムに対応付けられる出現位置（の差分）の値が変化する。そのため、値の大小によって割り当てられる符号が変化する可変長符号化を用いて生成された部分転置インデックス２９のデータ容量は、入れ換え前後で変化しうる。ステップＳ１０７では、生成装置１０の生成手段が、新たに生成された部分転置インデックス２９のデータ容量が、元の部分転置インデックス２９に比べて小さくなったかを判定する。
【００５８】
部分転置インデックス２９のデータ容量が小さくなっていれば（ステップＳ１０７；ＹＥＳ）、今回の部分転置インデックス２９を採用して保持し（ステップＳ１０８）、ステップＳ１０４へと戻る。一方で、小さくなっていなければ（ステップＳ１０７；ＮＯ）、何もせずにステップＳ１０４へと戻る。すなわち、比較された２個の部分転置インデックス２９のうち、容量の小さい方が、ＲＡＭ１３に保持される。
【００５９】
その後、生成装置１０は、処理をステップＳ１０４へと戻し、すべての組合せを選択し終えたか、を判定する。すなわち、選択された文書データ１８が有する複数の説明文の順序についての入れ換え可能な組合せのうち、すべての組合せが選択され終わるまで、ステップＳ１０５〜Ｓ１０８の処理を繰り返す。例えば、図７のように文書データ１８ａが選択されている場合、入換文書データ２８ａ〜２８ｅまでの５個の組合せについて、順にステップＳ１０５〜Ｓ１０８の処理を繰り返す。その中で、それぞれの入換文書データ２８ａ〜２８ｅごとに部分転置インデックス２９を生成して、それまでに保持された部分転置インデックス２９よりも容量が小さくなると、新たに生成された部分転置インデックス２９を保持し直す。このような処理によって、選択された文書データ１８について、入れ換え可能な組合せのうちの最も容量の小さい部分転置インデックス２９が、保持されることになる。
【００６０】
そして、すべての組合せを選択し終えると（ステップＳ１０４；ＹＥＳ）、次に生成装置１０の文書入換手段は、すべての文書データ１８を選択し終えたか、を判定する（ステップＳ１０９）。選択し終えていないと（ステップＳ１０９；ＮＯ）、次の文書データ１８を選択し（ステップＳ１１０）、処理はステップＳ１０２へと戻る。すなわち、複数の文書データ１８のうち、すべての文書データ１８が選択され終わるまで、ステップＳ１０２〜Ｓ１０８の処理を繰り返す。例えば、図３のように複数の文書データ１８ａ〜１８ｚのうち、それまで文書データ１８ａが選択されていた場合、ステップＳ１１０では次の文書データ１８ｂが選択される。このように、生成装置１０は、最後の文書データ１８ｚについての処理が終わるまで、ステップＳ１０２〜Ｓ１０８の処理を繰り返す。
【００６１】
その結果として、各文書データ１８について、含まれる複数の説明文の順序についての入れ換え可能な組合せのうち、生成される部分転置インデックス２９のデータ容量が最小となる組合せから生成された部分転置インデックス２９が、それぞれＲＡＭ１３に保持されることになる。
【００６２】
最終的に、すべての文書データ１８を選択し終えたら（ステップＳ１０９；ＹＥＳ）、生成装置１０の合成手段は、ＣＰＵ１１がＲＡＭ１３に保持されたすべての部分転置インデックス２９から、全体の転置インデックス１９を合成する（ステップＳ１１１）。そして、生成装置１０は処理を終える。すなわち、ここまで生成されてきた各文書データ１８についての部分転置インデックス２９には、抽出されたＮグラムが個別の文書データ１８（または対応する入換文書データ２８）においてどこに出現するかの情報が記載されていたが、ここでは最後に、複数の文書データ１８の全体においてのＮグラムの出現位置の情報を記載した転置インデックス１９を生成する。
【００６３】
それぞれの文書データ１８ごとの部分転置インデックス２９では、上記図６（ｂ）で示したように、文書データ１８から抽出されたＮグラム（図６（ｂ）ではモノグラム）と、その出現位置の差分とが対応付けられている。ステップＳ１０９では、このような部分転置インデックス２９をあわせて、全体として１つの転置インデックス１９とする。すなわち、異なる部分転置インデックス２９が共通のＮグラムを有し、それぞれに出現位置（の差分）が対応付けられていた場合、これらの出現位置（の差分）をまとめて、同じ１種類のＮグラムに対応付けられるようにする。その結果、図８に示されるような転置インデックス１９となる。
【００６４】
転置インデックス１９は、モノグラムの出現位置に関するファイルと、文書データ１８の文字数に関するファイルと、から構成される。モノグラムの出現位置に関するファイルの構成は、上記図６（ｂ）にて示された部分転置インデックス２９の構成と同様であり、抽出されたモノグラムについて、隣接する出現位置との差分をとられた出現位置が対応付けられている。ここで、図６（ｂ）の部分転置インデックス２９は個別の文書データ１８から生成されたものであったのに対して、図８の転置インデックス１９は複数の文書データ１８全体に対応するものであるため、各モノグラムに対してより多くの出現位置（の差分）が対応付けられている。
【００６５】
また、文書データ１８の文字数に関するファイルでは、それぞれの文書データ１８ａ〜１８ｚ中の見出し語と説明文が、何文字の文字列から構成されるかの情報が記載されている。この情報は、述する検索装置２０での検索処理において、検索文字列を構成するＮグラムの出現位置が、複数の文書データ１８のうちどの文書データ１８における位置であるのかを特定するために使用される。
【００６６】
なお、上記図６（ｂ）における個別の文書データ１８から生成された部分転置インデックス２９の各Ｎグラムに対応付けられた最初の出現位置は、その文書データ１８における先頭文字から何文字目に位置しているかの値であった。しかし、部分転置インデックス２９から全体の転置インデックス１９を合成する際、複数の文書データ１８全体における出現位置を示すようにするために、前の文書データ１８から抽出された同じＮグラムに対応付けられた最後の出現位置からの差分を算出して、値を付け直す処理を行う。
【００６７】
このような生成装置１０における転置インデックス１９の生成処理によって、それぞれの文書データ１８においてデータ容量が最小となる部分転置インデックス２９を用いて、複数の文書データ１８全体の転置インデックス１９を生成する。そのため、例えば携帯電話や電子辞書などのような小型の電子機器のような、使用できるデータ容量が限られた環境においても、データ容量が最小限に抑えられた転置インデックス１９を用いて、検索処理を実現することができる。
【００６８】
次に、生成装置１０によって生成された転置インデックス１９を用いて、所望の検索文字列が、複数の文書データ１８のうちどの文書データ１８に含まれているのかを特定するための検索装置２０の検索処理について、図９のフローチャートを参照して説明する。
【００６９】
検索処理が開始されると、まず検索装置２０は、ユーザから入力された検索文字列を受け付ける（ステップＳ３０１）。すなわち、検索装置２０の入力装置２５に対して、ユーザが検索文字列を入力することで、検索処理が開始される。
【００７０】
次に、検索装置２０の抽出手段は、ＣＰＵ２１がＲＡＭ２３等と協働することにより、受け付けられた検索文字列からＮグラムを抽出する（ステップＳ３０２）。このとき、検索文字列がＮｓ文字の文字列であるとすると、ＮｓがＮよりも大きい場合は、最大でＮｓ−Ｎ＋１個のＮグラムが抽出される。抽出されたＮグラムは、ＲＡＭ２３に一時的に保持される。
【００７１】
検索文字列からＮグラムが抽出されると、検索装置２０の位置取得手段は、ＣＰＵ２１の機能により、ＨＤＤ２４に記憶された転置インデックス１９を用いて、抽出されたＮグラムに対応付けられた出現位置を取得する（ステップＳ３０３）。例えば、検索文字列から「Ａ」、「Ｘ」というモノグラムが抽出された場合は、転置インデックス１９のモノグラム「Ａ」およびモノグラム「Ｘ」に対応付けられた出現位置を取得する。
【００７２】
このとき、転置インデックス１９から直接取得される出現位置の値は、差分をとられた値であるので、複数の文書データ１８の先頭文字から何文字目にあるかを示す値に変換する。具体的には、あるＮグラムに対応付けられたｉ番目の出現位置については、１番目からｉ番目までの値の和をとることで、先頭文字から何文字目にあるかを示す値に変換することができる。このように取得され、変換された出現位置は、ＲＡＭ２３に一時的に保持される。
【００７３】
そして、検索装置２０の文書特定手段は、ＣＰＵ２１がＲＡＭ２３等と協働することにより、取得された出現位置の連続性から、検索文字列を含む文書データ１８を特定する（ステップＳ３０４）。すなわち、ここではまず、ステップＳ３０３において取得されたＮグラムの出現位置が、１つの文書データ１８の中で、検索文字列を構成するような連続した出現位置になっているかを判定する。
【００７４】
例えば、検索文字列が「ＡＢＣ」であったとして、そこからは「Ａ」、「Ｂ」、「Ｃ」というモノグラムが順に抽出される。転置インデックス１９から取得されるこれらのモノグラムの（上記変換された）出現位置の中にが、１文字ずつずれた値を示す出現位置があれば、その位置に所望の検索文字列「ＡＢＣ」が存在することになる。
【００７５】
そして、ステップＳ３０４では、そのような検索文字列を構成するような連続した出現位置が、複数の文書データ１８のうちどの文書データ１８の中に存在するのかを特定する。具体的には、検索文字列「ＡＢＣ」を構成するような連続した位置にあるモノグラム「Ａ」の（上記変換された）出現位置の値が、例えば「１８０」であるとする。このとき、転置インデックス１９に記載された文書データ１８の文字数に関するファイルから、個別の文書データ１８の文字数を先頭から足していって、その和が「１８０」をはじめて超えたときの文書データ１８の中に、所望の検索文字列が存在すると分かる。
【００７６】
図８の例では、文書データ１８ａの文字数「１２０」と、文書データ１８ｂの文字数「２３」との和は「１４３」であり、「１８０」を超えない。一方で、次の文書データ１８ｃの文字数を足すと「２００」となり、「１８０」を超える。そのため、所望の検索文字列「ＡＢＣ」は、文書データ１８ｃの中にあることが分かる。ステップＳ３０４では、検索装置２０の文書特定手段が、このように特定された文書データ１８が複数あれば、それらをすべてＲＡＭ１３に一時的に保持する。
【００７７】
最後に、検索装置２０は、出力装置２６を用いることにより、特定された文書データ１８をユーザへ出力する（ステップＳ３０５）。すなわち、例えばディスプレイ等に検索結果を表示する。そして、検索装置２０は、検索処理を終了する。
【００７８】
このとき、文書データ１８の見出し語を表示するようにしてもよいし、ＨＤＤ２４に記憶されている（説明文の順序が入れ換えられる前の）文書データ１８にアクセスして、特定された文書データ１８を表示するようにしてもよい。また、検索結果は、出力装置２６を用いて表示することに限られず、ＨＤＤ２４に記憶されるようにしてもよいし、通信制御装置２７を介して出力されるようにしてもよい。
【００７９】
このように、個別の文書データ１８の中で説明文の順序が入れ換えられていても、そこから生成された転置インデックス１９を用いて、複数の文書データ１８のうちから所望の検索文字列を含む文書データ１８を特定するという検索処理には影響を与えない。そのため、データ容量が小さくなるように、文書データ１８を構成する説明文の順序を入れ換えて転置インデックス１９を生成し、それを用いて検索をすることができる。このようなデータ容量が抑えられた転置インデックス１９を用いることで、例えば携帯電話や電子辞書などのような小型の電子機器のような、使用できるデータ容量が限られた環境においても、使用するデータ容量を効率的に抑えながら、検索処理を実現することができる。
【００８０】
なお、本発明は上記の実施形態に限定されず、種々の変形及び応用が可能である。
【００８１】
例えば、本実施形態では、図３に示したように、文書データ１８は見出し語と複数の説明文とから構成された。しかしこれに限られず、文書データ１８の構成要素として、当該見出し語が説明された図面など、別の構成要素があってもよい。また、セパレータは、図３のようにスペースと読点とに限られない。句点、カンマ、ピリオド、ハイフン、コロン、セミコロン、括弧など、通常ユーザが検索文字列に含めないと考えられるものであれば、何でもセパレータになりうる。
【００８２】
そして、転置インデックス１９の構成要素は、図８に示したような構成要素に限られない。例えば、転置インデックス１９は、文書データ１８の文字数に関するファイルのかわりに、文書データ１８の先頭文字位置に関するファイルを有していてもよい。すなわち、文書データ１８の先頭文字が、複数の文書データ１８全体の先頭文字から何文字目に位置するかの情報を、転置インデックス１９が有していてもよい。
【００８３】
文書データ１８の先頭文字位置の情報は、先頭からその文書データ１８までの文字数の和の情報に相当するので、文書データ１８の文字数の情報に比べて、大きな値になりやすい。そのため、可変長符号化によって転置インデックス１９を生成する場合、転置インデックス１９のデータ容量が大きくなりやすい。しかし、その転置インデックス１９を用いた検索時には、上記図９のステップＳ３０４にて、検索文字列を含む文書データ１８を特定する処理の際に、文書データ１８の文字数の和をとる必要がないため、検索処理を効率的なものにすることができる。
【００８４】
また、本実施形態における生成装置１０では、文書データ１８は、例えば図１のようにＨＤＤ１４内に記憶されるなどして生成装置１０内に存在することに限られない。すなわち、例えば図１０のように、文書データ１８は、生成装置１０内ではなくインターネット上に存在し、通信制御装置１７を介して取得されうるものであってもよい。
【００８５】
また、本実施形態における検索装置２０では、上記の生成装置１０と同様に、文書データ１８は、例えば図２のようにＨＤＤ２４内に記憶されるなどして検索装置２０内に存在することに限られない。すなわち、例えば図１１のように、文書データ１８は、検索装置２０内ではなくインターネット上に存在し、通信制御装置２７を介して取得されうるものであってもよい。
【００８６】
このような構成をとることで、図１１の実施形態では図２でのものに比べ、検索装置２０内に文書データ１８を記憶する必要がなく、インターネットに適切に接続可能な環境であれば、小型の電子辞書のような限られた容量の装置においても実現しやすくなる。
【００８７】
また、本発明での実施形態は、上述した実施形態に加え、上記生成装置１０としてコンピュータ装置を機能させるためのコンピュータプログラムであってもよい。また、上記検索装置２０としてコンピュータ装置を機能させるためのコンピュータプログラムであってもよい。
【００８８】
上記コンピュータプログラムは、コンパクトディスク、フレキシブルディスク、ハードディスク、光磁気ディスク、ディジタルビデオディスク、磁気テープ、半導体メモリ等のコンピュータ読取可能な情報記憶媒体に記憶することができる。
【００８９】
また、上記コンピュータプログラムは、コンピュータプログラムが実行されるコンピュータ装置とは独立して、コンピュータ通信網を介して配付・販売することができる。また、上記情報記憶媒体は、コンピュータ装置とは独立して配付・販売することができる。
【符号の説明】
【００９０】
１０…生成装置、１１…ＣＰＵ、１２…ＲＯＭ、１３…ＲＡＭ、１４…ＨＤＤ、１５…入力装置、１６…出力装置、１７…通信制御装置、１８…文書データ、１９…転置インデックス、２０…検索装置、２１…ＣＰＵ、２２…ＲＯＭ、２３…ＲＡＭ、２４…ＨＤＤ、２５…入力装置、２６…出力装置、２７…通信制御装置、２８…入換文書データ、２９…部分転置インデックス
【技術分野】
【０００１】
本発明は、Ｎグラム検索に関し、とくにＮグラム検索のための転置インデックスの生成方法および生成装置、当該転置インデックスを用いた検索方法および検索装置、ならびにコンピュータプログラムに関する。
【背景技術】
【０００２】
文書の電子化の増大に伴い、これまでに蓄積されてきた大量の文書群から所望の文書を見つけ出す検索技術の重要性が高まっている。
【０００３】
英語などの多くの言語においては、単語を索引単位として索引ファイルを作成して、これを用いて高速な検索処理を実現することが一般的である。しかし、日本語の場合、スペース等によって単語の切れ目が明示的に示されないため、しばしば、Ｎグラムを索引単位とする方法が用いられている。
【０００４】
Ｎグラムとは、連続するＮ文字からなる部分文字列のことである。Ｎグラムによる索引ファイル（以下、転置インデックスと呼称する）の作成には、文字列にのみ基づくため、単語を認識する必要がない。しかし、Ｎグラムによる転置インデックスは、単語を索引単位とするものに比べて、文書から抽出される索引単位の数が多くなるため、データ容量が大きくなりやすい。
【０００５】
このようなＮグラムによる転置インデックスのデータ容量を圧縮するための手法として、例えば非特許文献１には、以下のような方法が紹介されている。すなわち、Ｎグラムが文書中に出現する位置や回数などの値を転置インデックスに記録する際に、前の値との差分を取得し、その差分をゴロム符号やガンマ符号などの方式で可変長符号化することによって、転置インデックスを圧縮する。
【先行技術文献】
【非特許文献】
【０００６】
【非特許文献１】小川泰嗣，松田透，”ｎ−ｇｒａｍ索引を用いた効率的な文書検索法”，電子情報通信学会論文誌(D-I)，Vol.J82-D-I，No.1，pp.121-129，1999年1月
【発明の概要】
【発明が解決しようとする課題】
【０００７】
上記のような転置インデックスの圧縮方法は、取得された差分が小さな値であったときは圧縮率が大きくなるが、大きな値のときは圧縮率が小さくなる。すなわち、文書中におけるＮグラムの出現の仕方によって、あまり圧縮率されない場合もありうる。そこで、文書中におけるＮグラムの出現の仕方による影響を極力減らして、転置インデックスの圧縮効率を高めたい、との要望がある。
【０００８】
本発明は、以上のような課題を解決するためのものであり、データ容量が効率的に抑えられた転置インデックスの生成方法および生成装置、当該転置インデックスを用いた検索方法および検索装置、ならびに、コンピュータプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００９】
上記目的を達成するため、本発明の第１の観点にかかる転置インデックスの生成方法は、
それぞれが、見出し語と対応する複数の説明文とから構成される複数の文書データのうち、少なくとも１つの文書データの前記複数の説明文の順序を入れ換えて、入換文書データを作成する文書入換ステップと、
前記文書データもしくは前記作成された入換文書データから、「Ｎ文字の文字列であるＮグラム（Ｎは自然数）」を抽出し、抽出されたＮグラムのそれぞれについて、当該文書データもしくは当該入換文書データ中の出現位置を対応付けて、部分転置インデックスを生成する生成ステップと、
前記複数の文書データについて生成された複数の前記部分転置インデックスから、転置インデックスを合成する合成ステップと、
を備えることを特徴とする。
【００１０】
上記生成方法において、
前記生成ステップでは、前記文書データおよび当該文書データから作成された入換文書データから、それぞれ前記部分転置インデックスを生成し、当該それぞれ生成された部分転置インデックスのうち、容量が小さい部分転置インデックスを選定し、
前記合成ステップでは、前記複数の文書データについて選定された複数の前記部分転置インデックスから、転置インデックスを合成する、
ことが望ましい。
【００１１】
上記生成方法において、
前記文書入換ステップでは、前記文書データから、前記順序の入れ換え可能な組合せで前記順序を入れ換えて、当該組合せの数の入換文書データを作成し、
前記生成ステップでは、前記文書データおよび当該文書データから作成された前記組合せの数の入換文書データから、それぞれ前記部分転置インデックスを生成し、当該それぞれ生成された部分転置インデックスのうち、容量が最小の部分転置インデックスを選定する、
ことが望ましい。
【００１２】
上記生成方法において、
前記生成ステップでは、複数の文書データのうち、見出し語と対応する単一の説明文とから構成される文書データからも、前記部分転置インデックスを生成する、
ことが望ましい。
【００１３】
上記生成方法において、
前記生成ステップでは、前記抽出されたＮグラムのそれぞれについて、当該Ｎグラムに対応付けられた出現位置と隣接する出現位置との差分を対応付けて、部分転置インデックスを生成する、
ことが望ましい。
【００１４】
上記目的を達成するため、本発明の第２の観点にかかる検索方法は、
検索文字列からＮグラムを抽出する抽出ステップと、
上記の生成方法によって生成された転置インデックスから、前記検索文字列から抽出されたＮグラムに対応付けられた出現位置を取得する位置取得ステップと、
前記取得された出現位置に基づいて、前記複数の文書データのうちから、前記検索文字列を含む文書データを特定する文書特定ステップと、
を備えることを特徴とする。
【００１５】
上記目的を達成するため、本発明の第３の観点にかかる転置インデックスの生成装置は、
それぞれが、見出し語と対応する複数の説明文とから構成される複数の文書データのうち、少なくとも１つの文書データの前記複数の説明文の順序を入れ換えて、入換文書データを作成する文書入換手段と、
前記文書データもしくは前記作成された入換文書データから、「Ｎ文字の文字列であるＮグラム（Ｎは自然数）」を抽出し、抽出されたＮグラムのそれぞれについて、当該文書データもしくは当該入換文書データ中の出現位置を対応付けて、部分転置インデックスを生成する生成手段と、
前記複数の文書データについて生成された複数の前記部分転置インデックスから、転置インデックスを合成する合成手段と、
を備えることを特徴とする。
【００１６】
上記目的を達成するため、本発明の第４の観点にかかる検索装置は、
検索文字列からＮグラムを抽出する抽出手段と、
上記の生成方法によって生成された転置インデックスから、前記検索文字列から抽出されたＮグラムに対応付けられた出現位置を取得する位置取得手段と、
前記取得された出現位置に基づいて、前記複数の文書データのうちから、前記検索文字列を含む文書データを特定する文書特定手段と、
を備えることを特徴とする。
【００１７】
上記目的を達成するため、本発明の第５の観点にかかるコンピュータプログラムは、
コンピュータを、
それぞれが、見出し語と対応する複数の説明文とから構成される複数の文書データのうち、少なくとも１つの文書データの前記複数の説明文の順序を入れ換えて、入換文書データを作成する文書入換手段、
前記文書データもしくは前記作成された入換文書データから、「Ｎ文字の文字列であるＮグラム（Ｎは自然数）」を抽出し、抽出されたＮグラムのそれぞれについて、当該文書データもしくは当該入換文書データ中の出現位置を対応付けて、部分転置インデックスを生成する生成手段、
前記複数の文書データについて生成された複数の前記部分転置インデックスから、転置インデックスを合成する合成手段、
として機能させる。
【００１８】
上記目的を達成するため、本発明の第６の観点にかかるコンピュータプログラムは、
コンピュータを、
検索文字列からＮグラムを抽出する抽出手段、
上記の生成方法によって生成された転置インデックスから、前記検索文字列から抽出されたＮグラムに対応付けられた出現位置を取得する位置取得手段、
前記取得された出現位置に基づいて、前記複数の文書データのうちから、前記検索文字列を含む文書データを特定する文書特定手段、
として機能させる。
【発明の効果】
【００１９】
本発明によれば、データ容量が効率的に抑えられた転置インデックスの生成方法および生成装置、当該転置インデックスを用いた検索方法および検索装置、ならびに、コンピュータプログラムを提供することができる。
【図面の簡単な説明】
【００２０】
【図１】本発明に係る転置インデックスを生成する生成装置の概要構成の例を示す図である。
【図２】本発明に係る転置インデックスを搭載した検索装置の概要構成の例を示す図である。
【図３】本発明に係る複数の文書データの構成を示す図である。
【図４】本発明に係る生成装置の生成処理の流れを示すフローチャートである。
【図５】本発明に係る生成装置において、個々の文書データから部分転置インデックスを生成する処理の流れを示すフローチャートである。
【図６】（ａ）出現位置について隣接する出現位置との差分をとる前の部分転置インデックスの構成を示す図である。（ｂ）出現位置について隣接する出現位置との差分をとった後の部分転置インデックスの構成を示す図である。
【図７】文書データから作成可能な入換文書データの構成を示す図である。
【図８】複数の文書データ全体の転置インデックスの構成を示す図である。
【図９】本発明に係る検索装置の検索処理の流れを示すフローチャートである。
【図１０】本発明に係る転置インデックスを生成する生成装置の概要構成の別の例を示す図である。
【図１１】本発明に係る転置インデックスを搭載した検索装置の概要構成の別の例を示す図である。
【発明を実施するための形態】
【００２１】
以下、本発明の実施形態に係る転置インデックスの生成方法および生成装置、当該転置インデックスを用いた検索方法および検索装置、ならびに、これらをコンピュータ上にて実現するためのコンピュータプログラムについて説明する。以下に説明する実施形態は説明のためのものであり、本発明の範囲を制限するものではない。
【００２２】
本実施形態では、コンピュータ装置を、図１に示されるような転置インデックスの生成装置として構成する。また、図１に示される生成装置１０によって、本実施形態に係る転置インデックスの生成方法が実現される。
【００２３】
生成装置１０は、ＣＰＵ（Central Processing Unit）１１、ＲＯＭ（Read Only Memory）１２、ＲＡＭ（Random Access Memory）１３、ＨＤＤ（Hard Disk Drive）１４、入力装置１５、出力装置１６、通信制御装置１７により構成される。各構成要素は、命令やデータを転送するための伝送経路であるシステムバスにより、相互に接続されている。
【００２４】
ＣＰＵ１１は、生成装置１０全体の動作を制御し、各構成要素と接続され制御信号やデータをやりとりする。
ＲＯＭ１２は、生成装置１０全体の動作制御に必要なコンピュータプログラムや各種データを記憶する。ＣＰＵ１１は、ＲＯＭ１２に記憶されたコンピュータプログラムによって動作し、各種制御を実行する。
ＲＡＭ１３は、データやコンピュータプログラムを一時的に記憶するためのもので、ＲＯＭ１２から読み出したコンピュータプログラムやデータ、その他処理の進行に必要なデータが保持される。
ＨＤＤ１４は、転置インデックスの生成処理の動作のために必要なデータ等を記憶する。このＨＤＤ１４には、複数の文書データ１８が記憶される。生成装置１０は、この複数の文書データ１８をもとにして、転置インデックスを生成する。
入力装置１５は、例えばキーボードやタッチパネル等によって構成され、ユーザからの各種入力を受け付ける。
出力装置１６は、例えばディスプレイ等によって構成され、生成装置１０の種々の処理結果を出力する。
通信制御装置１７は、生成装置１０をインターネット等のコンピュータ通信網に接続するためのものであり、コンピュータ通信網に接続してデータをやり取りする場合に必要となる。
【００２５】
本実施形態では、生成装置１０は、文書入換手段と、生成手段と、合成手段と、を備える。これらは、上述したＣＰＵ１１が、ＲＯＭ１２やＲＡＭ１３と協働し、ＨＤＤ１４に記憶されたデータにアクセスしながら、入力装置１５や出力装置１６、通信制御装置１７を用いて外部とやり取りすることで、実現される。
【００２６】
具体的に、生成装置１０の文書入換手段は、それぞれが、見出し語と対応する複数の説明文とから構成される複数の文書データ１８のうち、少なくとも１つの文書データ１８の複数の説明文の順序を入れ換えて、入換文書データを作成する。このような文書入換手段として、例えばＣＰＵ１１が、ＲＯＭ１２やＲＡＭ１３と協働しながら、ＨＤＤ１４に記憶された文書データ１８にアクセスし、入換文書データをＲＡＭ１３に一時的に保持することにより、実現される。
【００２７】
そして、生成装置１０の生成手段は、文書データ１８もしくは作成された入換文書データから、「Ｎ文字の文字列であるＮグラム（Ｎは自然数）」を抽出し、抽出されたＮグラムのそれぞれについて、当該文書データ１８もしくは当該入換文書データ中の出現位置を対応付けて、部分転置インデックスを生成する。このような生成手段として、例えばＣＰＵ１１が、ＲＯＭ１２やＲＡＭ１３と協働しながら、保持された入換文書データから部分転置インデックスを生成して、生成された部分転置インデックスを再びＲＡＭ１３に保持することにより、実現される。
【００２８】
さらに、生成装置１０の合成手段は、複数の文書データ１８について生成された複数の部分転置インデックスから、転置インデックスを合成する。このような合成手段として、例えばＣＰＵ１１が、ＲＯＭ１２やＲＡＭ１３と協働しながら、出力装置１６やＨＤＤ１４、あるいは通信制御装置１７を介して、合成された転置インデックスを出力することで機能する。
【００２９】
このような生成装置１０によって生成された転置インデックスは、検索装置に搭載され、検索処理に用いられる。本実施形態では、コンピュータ装置を、図２に示されるような検索装置として構成する。また、図２に示される検索装置２０によって、本実施形態に係る転置インデックスの検索方法が実現される。
【００３０】
検索装置２０は、ＣＰＵ２１、ＲＯＭ２２、ＲＡＭ２３、ＨＤＤ２４、入力装置２５、出力装置２６、通信制御装置２７により構成される。各構成要素は、命令やデータを転送するための伝送経路であるシステムバスにより、相互に接続されている。
【００３１】
これらの構成要素は、基本的には図１に示された生成装置１０の構成要素と同等なものである。すなわち、図１では、文書データ１８から転置インデックスを生成するために機能した各構成要素が、ここでは生成された転置インデックスを用いて検索処理を行うために機能する。
【００３２】
すなわち、ＣＰＵ２１は、検索装置２０全体の動作を制御し、各構成要素と接続され制御信号やデータをやりとりする。
ＲＯＭ２２は、検索装置２０全体の動作制御に必要なコンピュータプログラムや各種データを記憶する。ＣＰＵ２１は、ＲＯＭ２２に記憶されたコンピュータプログラムによって動作し、各種制御を実行する。
ＲＡＭ２３は、データやコンピュータプログラムを一時的に記憶するためのもので、ＲＯＭ２２から読み出したコンピュータプログラムやデータ、その他処理の進行に必要なデータが保持される。
ＨＤＤ２４は、検索処理の動作のために必要なデータ等を記憶する。このＨＤＤ２４には、複数の文書データ１８と、生成装置１０によって生成された転置インデックス１９とが、記憶される。検索装置２０は、転置インデックス１９をもとに、ユーザによって指定された検索文字列が複数の文書データ１８の中のどの文書データ１８中に出現するかを特定する。
入力装置２５は、例えばキーボードやタッチパネル等によって構成され、ユーザからの各種入力を受け付ける。
出力装置２６は、例えばディスプレイ等によって構成され、検索装置２０の種々の処理結果を出力する。
通信制御装置２７は、検索装置２０をインターネット等のコンピュータ通信網に接続するためのものであり、コンピュータ通信網に接続してデータをやり取りする場合に必要となる。
【００３３】
本実施形態では、検索装置２０は、抽出手段と、位置取得手段と、文書特定手段と、を備える。これらは、上述したＣＰＵ２１が、ＲＯＭ２２やＲＡＭ２３と協働し、ＨＤＤ２４に記憶されたデータにアクセスしながら、入力装置２５や出力装置２６、通信制御装置２７を用いて外部とやり取りすることで、実現される。
【００３４】
具体的に、検索装置２０の抽出手段は、検索文字列からＮグラムを抽出する。このような抽出手段として、例えばＣＰＵ２１が、ＲＯＭ２２やＲＡＭ２３と協働しながら、入力装置２５を介してユーザから検索文字列を受け付け、抽出されたＮグラムをＲＡＭ２３に保持することにより、実現される。
【００３５】
そして、検索装置２０の位置取得手段は、生成装置１０によって生成された転置インデックス１９から、検索文字列から抽出されたＮグラムに対応付けられた出現位置を取得する。このような位置取得手段として、例えばＣＰＵ２１が、ＲＯＭ２２やＲＡＭ２３と協働しながら、ＨＤＤ２４に記憶された転置インデックス１９にアクセスし、取得された出現位置をＲＡＭ２３に保持することにより、実現される。
【００３６】
さらに、検索装置２０の文書特定手段は、取得された出現位置に基づいて、複数の文書データ１８のうちから、検索文字列を含む文書データ１８を特定する。このような文書特定手段として、例えばＣＰＵ２１が、ＲＯＭ２２やＲＡＭ２３と協働しながら、出力装置２６や通信制御装置２７を介して、特定された文書データ１８をユーザへ出力することにより、実現される。
【００３７】
文書データ１８は、図３に示されるように構成される。本実施形態では、図３に示されるような複数の文書データ１８ａ〜１８ｚの中から、所望の検索文字列を含む文書データ１８を見つけ出すための検索方法等が提供される。１つの文書データ１８は、１つの見出し語と複数の説明文から構成される。
【００３８】
具体的に、最初の文書データ１８ａにおいて、見出し語Ａには、３つの説明文Ａ１、Ａ２、Ａ３が対応付けられている。また、次の文書データ１８ｂでは、見出し語Ｂに、２つの説明文Ｂ１、Ｂ２が対応付けられ、文書エータ１８ｃでは、見出し語Ｃに、３つの説明文Ｃ１、Ｃ２、Ｃ３が対応付けられている。ここで、説明文の数は、必ずしも複数に限られず、文書データ１８ｄでの見出し語Ｄと説明文Ｄ１のように、説明文が１つであってもよい。また、図３のように１〜３個に限られず、４個以上であってもよい。
【００３９】
ここで、見出し語とは、その文書データ１８を表現する代表的な言葉を意味する。そして、説明文とは、対応する見出し語を説明する言葉を意味する。このような見出し語と対応する説明文とで構成される文書データ１８を複数有するものとして、例えば辞書のような文書が挙げられる。
【００４０】
そして、見出し語と説明文との間はスペースで区切られ、２つの説明文の間は読点で区切られる。以降、これらのスペースや読点を、「セパレータ」と称する。ここで、セパレータは、検索の対象にはならない。すなわち、本実施形態の検索装置２０は、例えば、見出し語Ａと説明文Ａ１にまたがるような、あるいは説明文Ａ１と説明文Ａ２にまたがるような、セパレータを含む検索文字列を検索の対象としない。
【００４１】
ここから、このような複数の文書データ１８から、転置インデックス１９を生成するための生成装置１０と、当該転置インデックス１９を用いて検索するための検索装置２０における、処理の流れの詳細を説明する。ここではまず、図４を参照して、転置インデックス１９の生成処理について、フローチャートを用いて説明していく。
【００４２】
生成装置１０は、例えば入力装置１５を介してユーザからの生成処理の開始の指示を受け付けることで、転置インデックス１９の生成処理を開始する。転置インデックス１９の生成処理が開始されると、まず生成装置１０の文書入換手段は、ＣＰＵ１１とＲＡＭ１３等の機能により、複数の文書データ１８のうちから、最初の文書データ１８を選択する（ステップＳ１０１）。すなわち、ＨＤＤ１４に記憶されている図３に示されたような複数の文書データ１８から、最初の文書データ１８を選択する。ここでは例えば、先頭の見出し語Ａの文書データ１８が選択される。
【００４３】
次に、生成装置１０の生成手段は、ＣＰＵ１１がＲＡＭ１３等と協働することで、選択された文書データ１８から、部分転置インデックスを生成し保持する（ステップＳ１０２）。ここで、部分転置インデックスとは、複数の文書データ１８全体から生成される転置インデックス１９と区別するため、複数の文書データ１８のうち個々の文書データ１８から生成された転置インデックス１９のことを指すものとする。このステップＳ１０２の処理については、詳細を図５のフローチャートを参照して説明する。
【００４４】
選択された文書データ１８から部分転置インデックスを生成するために、まず、文書データ１８から「Ｎ文字の文字列であるＮグラム（Ｎは自然数）」を抽出する（ステップＳ２０１）。すなわち、文書データ１８を構成する見出し語と説明文との文字列から、抽出可能なＮ文字列（Ｎグラム）をすべて抽出する。このとき、スペースや読点などのセパレータからはＮグラムを抽出しない。また、セパレータをまたぐようにＮグラムを抽出することもしない。
【００４５】
例えば、文書データ１８が、Ｎａ文字の見出し語と、Ｎｂ文字とＮｃ文字の２つの説明文から構成されるとする。Ｎの値が、Ｎａ、Ｎｂ、Ｎｃのいずれよりも大きな値でないとき、見出し語からはＮａ−Ｎ＋１個のＮグラムが、２つの説明文からはそれぞれＮｂ−Ｎ＋１個とＮｃ−Ｎ＋１個のＮグラムが、抽出される。すなわち、文書データ１８からは、これらの和であるＮａ＋Ｎｂ＋Ｎｃ−３Ｎ＋３個のＮグラムが抽出されることになる。
【００４６】
次に、生成装置１０の生成手段は、ＣＰＵ１１がＲＡＭ１３等と協働することで、抽出されたＮグラムのそれぞれについて、選択された文書データ１８中の出現位置を対応付ける（ステップＳ２０２）。すなわち、抽出されたＮグラムが、選択された文書データ１８中のどの位置にあったのかの情報を、抽出されたＮグラムそれぞれについて対応付ける。
【００４７】
そして、生成装置１０の生成手段は、ＣＰＵ１１がＲＡＭ１３等と協働することで、対応付けられた出現位置を昇順に並べて、隣接する出現位置との差分をとり（ステップＳ２０３）、部分転置インデックスを生成する（ステップＳ２０４）。昇順に並べられた出現位置と、モノグラム（Ｎ＝１のＮグラム）とを対応付けた部分転置インデックスは、例えば図６（ａ）のようになる。
【００４８】
この図６（ａ）では、選択された１つの文書データ１８から、「Ａ」〜「Ｚ」のモノグラムが抽出され、その文書データ１８中での出現位置が数字で対応付けられている。具体的に、例えばモノグラム「Ａ」には、「５」、「２２」、「３３」、「３５」、「８７」、「１２０」という６個の出現位置が対応付けられている。これはすなわち、選択された文書データ１８中に「Ａ」というモノグラムが、文書の先頭からそれぞれの文字列目の位置に６回出現するということを意味するものである。
【００４９】
ステップＳ２０３では、このようなＮグラム（図６（ａ）ではモノグラム）と出現位置とが対応付けられたものから、出現位置について隣接する出現位置との差分をとって、当該差分をＮグラムに対応付ける。図６（ｂ）は、図６（ａ）の出現位置について、隣接する出現位置との差分をとった後の様子を示している。
【００５０】
具体的に、例えばモノグラム「Ａ」では、図６（ａ）で２番目の出現位置であった「２２」は、１番目の出現位置「５」との差分をとられることで、「１７」となっている。また、３番目の出現位置であった「３３」は、２番目の出現位置であった「２２」との差分をとられることで、「１１」となっている。同様に図６（ｂ）では、４番目には「２（＝３５−３３）」が、５番目には「５２（＝８７−３５）」が、６番目には「３３（＝１２０−８７）」が、それぞれ前の出現位置との差分をとられて表示されている。なお、１番目の出現位置である「５」については、差分をとるべき前の出現位置がないため、図６（ａ）と図６（ｂ）で変化しない。
【００５１】
このように、選択された文書データ１８から抽出されたＮグラムのそれぞれについて、出現位置の差分を対応付けられたものを、生成装置１０は、部分転置インデックス２９としてＲＡＭ１３等に一時的に保持する。そして、図５におけるステップＳ１０２の処理を終える。
【００５２】
本実施形態では以上のように、部分転置インデックス２９を生成する際に出現位置についての差分をとる。これによって、部分転置インデックス２９に保存される出現位置の値は、差分をとる前に比べて小さな値に抑えられることができる。このような小さな値に抑えられた出現位置の情報に対して、例えばゴロム符号やガンマ符号などの方式で可変長符号化を用いて、小さな値ほど割り当てられる符号の長さを抑えることにより、差分をとる前の大きな値で出現位置を対応付けて生成した部分転置インデックス２９よりも、データ容量が抑えられた部分転置インデックス２９、さらにはそれらをあわせた全体の転置インデックス１９を生成することが可能となる。
【００５３】
本実施形態では、ここから、さらに部分転置インデックス２９のデータ容量を抑えるために、文書データ１８に含まれる説明文の順序を入れ換えて改めて部分転置インデックス２９を生成し、データ容量のより小さい方を採用する処理を行う。すなわち、後述する検索装置２０の処理では、上記図３に示されたような複数の文書データ１８のうちから、所望の検索文字列を含む文書データ１８（見出し語）を特定する。このとき、見出し語と説明文あるいは説明文同士を区切るセパレータを含んだ、あるいはまたいだ検索は行わないため、セパレータで区切られた複数の説明文の順番が入れ替わっていたとしても、検索結果には影響を与えない。そのため、本実施形態では、複数の説明文の順序を入れ換えて部分転置インデックス２９を生成して、データ容量のより小さい方を採用する処理を行う。
【００５４】
そのために、図４に戻って、生成装置１０の文書入換手段は、ＣＰＵ１１がＲＡＭ１３等と協働することで、選択された文書データ１８の説明文について、入れ換え可能な組合せを算出する（ステップＳ１０３）。例えば、上記図３の文書データ１８ａのように、３個の説明文Ａ１、Ａ２、Ａ３を有する場合、入れ換え可能な組合せは、「Ａ１、Ａ２、Ａ３」、「Ａ１、Ａ３、Ａ２」、「Ａ２、Ａ１、Ａ３」、「Ａ２、Ａ３、Ａ１」、「Ａ３、Ａ１、Ａ２」、「Ａ３、Ａ２、Ａ１」の６通り（入れ換え前を除けば５通り）がある。また、文書データ１８ｂのように、２個の説明文Ｂ１、Ｂ２を有する場合、入れ換え可能な組合せは、「Ｂ１、Ｂ２」、「Ｂ２、Ｂ１」の２通り（入れ換え前を除けば１通り）がある。一般的に、文書データ１８がＸ個の説明文を有する場合、Ｘ！（！は階乗）個の組合せがある。ここで、算出された組合せは、例えばＲＡＭ１３に一時的に保持される。
【００５５】
そして、生成装置１０の文書入換手段は、ＣＰＵ１１がＲＡＭ１３等と協働することで、すべての組合せを選択し終えたか、を判定する（ステップＳ１０４）。選択し終えてない場合（ステップＳ１０４；ＮＯ）、組合せを１つ選択し、その組合せで説明文を入れ換えて、入換文書データを作成する（ステップＳ１０５）。例えば、上記図３の文書データ１８ａのように、６個の入れ換え可能な組合せのうち、「Ａ１、Ａ３、Ａ２」を選択したとする。このとき、作成される入換文書データは、図７に示されるような入換文書データ２８ａのようになる。すなわち、入換文書データ２８ａでは、「見出し語Ａ」の後に、スペースを挟んで「説明文Ａ１、説明文Ａ３、説明文Ａ２」、というように、入れ換えられる前の文書データ１８ａから比べて、説明文Ａ２と説明文Ａ３の順序が、間の読点を挟んで入れ換えられている。作成された入換文書データ２８は、例えばＲＡＭ１３に一時的に保持される。
【００５６】
図４に戻って、この後、生成装置１０の生成手段は、ＣＰＵ１１がＲＡＭ１３等と協働することで、このような入換文書データ２８から、部分転置インデックス２９を生成する（ステップＳ１０６）。ここでの部分転置インデックス２９の生成処理は、上述したステップＳ１０２における処理と同じく、図５のフローチャートに示される。すなわち、ステップＳ１０２では、選択された（入換前の）文書データ１８から部分転置インデックス２９を生成したが、このステップＳ１０６では、ステップＳ１０２で用いられた文書データ１８から複数の説明文の順序が入れ換えられた入換文書データ２８から、部分転置インデックス２９を生成する。
【００５７】
そして、生成装置１０の生成手段は、ＣＰＵ１１がＲＡＭ１３等と協働することで、ステップＳ１０６で生成された部分転置インデックス２９を、ステップＳ１０２で生成された部分転置インデックス２９と比較して、容量が小さくなったかを判定する（ステップＳ１０７）。すなわち、入換文書データ２８から生成された部分転置インデックス２９では、入れ換え前の文書データ１８から生成された部分転置インデックス２９に比べて、説明文の順序が入れ換えられて生成されているので、抽出されるＮグラムに変化はないが、それぞれのＮグラムに対応付けられる出現位置（の差分）の値が変化する。そのため、値の大小によって割り当てられる符号が変化する可変長符号化を用いて生成された部分転置インデックス２９のデータ容量は、入れ換え前後で変化しうる。ステップＳ１０７では、生成装置１０の生成手段が、新たに生成された部分転置インデックス２９のデータ容量が、元の部分転置インデックス２９に比べて小さくなったかを判定する。
【００５８】
部分転置インデックス２９のデータ容量が小さくなっていれば（ステップＳ１０７；ＹＥＳ）、今回の部分転置インデックス２９を採用して保持し（ステップＳ１０８）、ステップＳ１０４へと戻る。一方で、小さくなっていなければ（ステップＳ１０７；ＮＯ）、何もせずにステップＳ１０４へと戻る。すなわち、比較された２個の部分転置インデックス２９のうち、容量の小さい方が、ＲＡＭ１３に保持される。
【００５９】
その後、生成装置１０は、処理をステップＳ１０４へと戻し、すべての組合せを選択し終えたか、を判定する。すなわち、選択された文書データ１８が有する複数の説明文の順序についての入れ換え可能な組合せのうち、すべての組合せが選択され終わるまで、ステップＳ１０５〜Ｓ１０８の処理を繰り返す。例えば、図７のように文書データ１８ａが選択されている場合、入換文書データ２８ａ〜２８ｅまでの５個の組合せについて、順にステップＳ１０５〜Ｓ１０８の処理を繰り返す。その中で、それぞれの入換文書データ２８ａ〜２８ｅごとに部分転置インデックス２９を生成して、それまでに保持された部分転置インデックス２９よりも容量が小さくなると、新たに生成された部分転置インデックス２９を保持し直す。このような処理によって、選択された文書データ１８について、入れ換え可能な組合せのうちの最も容量の小さい部分転置インデックス２９が、保持されることになる。
【００６０】
そして、すべての組合せを選択し終えると（ステップＳ１０４；ＹＥＳ）、次に生成装置１０の文書入換手段は、すべての文書データ１８を選択し終えたか、を判定する（ステップＳ１０９）。選択し終えていないと（ステップＳ１０９；ＮＯ）、次の文書データ１８を選択し（ステップＳ１１０）、処理はステップＳ１０２へと戻る。すなわち、複数の文書データ１８のうち、すべての文書データ１８が選択され終わるまで、ステップＳ１０２〜Ｓ１０８の処理を繰り返す。例えば、図３のように複数の文書データ１８ａ〜１８ｚのうち、それまで文書データ１８ａが選択されていた場合、ステップＳ１１０では次の文書データ１８ｂが選択される。このように、生成装置１０は、最後の文書データ１８ｚについての処理が終わるまで、ステップＳ１０２〜Ｓ１０８の処理を繰り返す。
【００６１】
その結果として、各文書データ１８について、含まれる複数の説明文の順序についての入れ換え可能な組合せのうち、生成される部分転置インデックス２９のデータ容量が最小となる組合せから生成された部分転置インデックス２９が、それぞれＲＡＭ１３に保持されることになる。
【００６２】
最終的に、すべての文書データ１８を選択し終えたら（ステップＳ１０９；ＹＥＳ）、生成装置１０の合成手段は、ＣＰＵ１１がＲＡＭ１３に保持されたすべての部分転置インデックス２９から、全体の転置インデックス１９を合成する（ステップＳ１１１）。そして、生成装置１０は処理を終える。すなわち、ここまで生成されてきた各文書データ１８についての部分転置インデックス２９には、抽出されたＮグラムが個別の文書データ１８（または対応する入換文書データ２８）においてどこに出現するかの情報が記載されていたが、ここでは最後に、複数の文書データ１８の全体においてのＮグラムの出現位置の情報を記載した転置インデックス１９を生成する。
【００６３】
それぞれの文書データ１８ごとの部分転置インデックス２９では、上記図６（ｂ）で示したように、文書データ１８から抽出されたＮグラム（図６（ｂ）ではモノグラム）と、その出現位置の差分とが対応付けられている。ステップＳ１０９では、このような部分転置インデックス２９をあわせて、全体として１つの転置インデックス１９とする。すなわち、異なる部分転置インデックス２９が共通のＮグラムを有し、それぞれに出現位置（の差分）が対応付けられていた場合、これらの出現位置（の差分）をまとめて、同じ１種類のＮグラムに対応付けられるようにする。その結果、図８に示されるような転置インデックス１９となる。
【００６４】
転置インデックス１９は、モノグラムの出現位置に関するファイルと、文書データ１８の文字数に関するファイルと、から構成される。モノグラムの出現位置に関するファイルの構成は、上記図６（ｂ）にて示された部分転置インデックス２９の構成と同様であり、抽出されたモノグラムについて、隣接する出現位置との差分をとられた出現位置が対応付けられている。ここで、図６（ｂ）の部分転置インデックス２９は個別の文書データ１８から生成されたものであったのに対して、図８の転置インデックス１９は複数の文書データ１８全体に対応するものであるため、各モノグラムに対してより多くの出現位置（の差分）が対応付けられている。
【００６５】
また、文書データ１８の文字数に関するファイルでは、それぞれの文書データ１８ａ〜１８ｚ中の見出し語と説明文が、何文字の文字列から構成されるかの情報が記載されている。この情報は、述する検索装置２０での検索処理において、検索文字列を構成するＮグラムの出現位置が、複数の文書データ１８のうちどの文書データ１８における位置であるのかを特定するために使用される。
【００６６】
なお、上記図６（ｂ）における個別の文書データ１８から生成された部分転置インデックス２９の各Ｎグラムに対応付けられた最初の出現位置は、その文書データ１８における先頭文字から何文字目に位置しているかの値であった。しかし、部分転置インデックス２９から全体の転置インデックス１９を合成する際、複数の文書データ１８全体における出現位置を示すようにするために、前の文書データ１８から抽出された同じＮグラムに対応付けられた最後の出現位置からの差分を算出して、値を付け直す処理を行う。
【００６７】
このような生成装置１０における転置インデックス１９の生成処理によって、それぞれの文書データ１８においてデータ容量が最小となる部分転置インデックス２９を用いて、複数の文書データ１８全体の転置インデックス１９を生成する。そのため、例えば携帯電話や電子辞書などのような小型の電子機器のような、使用できるデータ容量が限られた環境においても、データ容量が最小限に抑えられた転置インデックス１９を用いて、検索処理を実現することができる。
【００６８】
次に、生成装置１０によって生成された転置インデックス１９を用いて、所望の検索文字列が、複数の文書データ１８のうちどの文書データ１８に含まれているのかを特定するための検索装置２０の検索処理について、図９のフローチャートを参照して説明する。
【００６９】
検索処理が開始されると、まず検索装置２０は、ユーザから入力された検索文字列を受け付ける（ステップＳ３０１）。すなわち、検索装置２０の入力装置２５に対して、ユーザが検索文字列を入力することで、検索処理が開始される。
【００７０】
次に、検索装置２０の抽出手段は、ＣＰＵ２１がＲＡＭ２３等と協働することにより、受け付けられた検索文字列からＮグラムを抽出する（ステップＳ３０２）。このとき、検索文字列がＮｓ文字の文字列であるとすると、ＮｓがＮよりも大きい場合は、最大でＮｓ−Ｎ＋１個のＮグラムが抽出される。抽出されたＮグラムは、ＲＡＭ２３に一時的に保持される。
【００７１】
検索文字列からＮグラムが抽出されると、検索装置２０の位置取得手段は、ＣＰＵ２１の機能により、ＨＤＤ２４に記憶された転置インデックス１９を用いて、抽出されたＮグラムに対応付けられた出現位置を取得する（ステップＳ３０３）。例えば、検索文字列から「Ａ」、「Ｘ」というモノグラムが抽出された場合は、転置インデックス１９のモノグラム「Ａ」およびモノグラム「Ｘ」に対応付けられた出現位置を取得する。
【００７２】
このとき、転置インデックス１９から直接取得される出現位置の値は、差分をとられた値であるので、複数の文書データ１８の先頭文字から何文字目にあるかを示す値に変換する。具体的には、あるＮグラムに対応付けられたｉ番目の出現位置については、１番目からｉ番目までの値の和をとることで、先頭文字から何文字目にあるかを示す値に変換することができる。このように取得され、変換された出現位置は、ＲＡＭ２３に一時的に保持される。
【００７３】
そして、検索装置２０の文書特定手段は、ＣＰＵ２１がＲＡＭ２３等と協働することにより、取得された出現位置の連続性から、検索文字列を含む文書データ１８を特定する（ステップＳ３０４）。すなわち、ここではまず、ステップＳ３０３において取得されたＮグラムの出現位置が、１つの文書データ１８の中で、検索文字列を構成するような連続した出現位置になっているかを判定する。
【００７４】
例えば、検索文字列が「ＡＢＣ」であったとして、そこからは「Ａ」、「Ｂ」、「Ｃ」というモノグラムが順に抽出される。転置インデックス１９から取得されるこれらのモノグラムの（上記変換された）出現位置の中にが、１文字ずつずれた値を示す出現位置があれば、その位置に所望の検索文字列「ＡＢＣ」が存在することになる。
【００７５】
そして、ステップＳ３０４では、そのような検索文字列を構成するような連続した出現位置が、複数の文書データ１８のうちどの文書データ１８の中に存在するのかを特定する。具体的には、検索文字列「ＡＢＣ」を構成するような連続した位置にあるモノグラム「Ａ」の（上記変換された）出現位置の値が、例えば「１８０」であるとする。このとき、転置インデックス１９に記載された文書データ１８の文字数に関するファイルから、個別の文書データ１８の文字数を先頭から足していって、その和が「１８０」をはじめて超えたときの文書データ１８の中に、所望の検索文字列が存在すると分かる。
【００７６】
図８の例では、文書データ１８ａの文字数「１２０」と、文書データ１８ｂの文字数「２３」との和は「１４３」であり、「１８０」を超えない。一方で、次の文書データ１８ｃの文字数を足すと「２００」となり、「１８０」を超える。そのため、所望の検索文字列「ＡＢＣ」は、文書データ１８ｃの中にあることが分かる。ステップＳ３０４では、検索装置２０の文書特定手段が、このように特定された文書データ１８が複数あれば、それらをすべてＲＡＭ１３に一時的に保持する。
【００７７】
最後に、検索装置２０は、出力装置２６を用いることにより、特定された文書データ１８をユーザへ出力する（ステップＳ３０５）。すなわち、例えばディスプレイ等に検索結果を表示する。そして、検索装置２０は、検索処理を終了する。
【００７８】
このとき、文書データ１８の見出し語を表示するようにしてもよいし、ＨＤＤ２４に記憶されている（説明文の順序が入れ換えられる前の）文書データ１８にアクセスして、特定された文書データ１８を表示するようにしてもよい。また、検索結果は、出力装置２６を用いて表示することに限られず、ＨＤＤ２４に記憶されるようにしてもよいし、通信制御装置２７を介して出力されるようにしてもよい。
【００７９】
このように、個別の文書データ１８の中で説明文の順序が入れ換えられていても、そこから生成された転置インデックス１９を用いて、複数の文書データ１８のうちから所望の検索文字列を含む文書データ１８を特定するという検索処理には影響を与えない。そのため、データ容量が小さくなるように、文書データ１８を構成する説明文の順序を入れ換えて転置インデックス１９を生成し、それを用いて検索をすることができる。このようなデータ容量が抑えられた転置インデックス１９を用いることで、例えば携帯電話や電子辞書などのような小型の電子機器のような、使用できるデータ容量が限られた環境においても、使用するデータ容量を効率的に抑えながら、検索処理を実現することができる。
【００８０】
なお、本発明は上記の実施形態に限定されず、種々の変形及び応用が可能である。
【００８１】
例えば、本実施形態では、図３に示したように、文書データ１８は見出し語と複数の説明文とから構成された。しかしこれに限られず、文書データ１８の構成要素として、当該見出し語が説明された図面など、別の構成要素があってもよい。また、セパレータは、図３のようにスペースと読点とに限られない。句点、カンマ、ピリオド、ハイフン、コロン、セミコロン、括弧など、通常ユーザが検索文字列に含めないと考えられるものであれば、何でもセパレータになりうる。
【００８２】
そして、転置インデックス１９の構成要素は、図８に示したような構成要素に限られない。例えば、転置インデックス１９は、文書データ１８の文字数に関するファイルのかわりに、文書データ１８の先頭文字位置に関するファイルを有していてもよい。すなわち、文書データ１８の先頭文字が、複数の文書データ１８全体の先頭文字から何文字目に位置するかの情報を、転置インデックス１９が有していてもよい。
【００８３】
文書データ１８の先頭文字位置の情報は、先頭からその文書データ１８までの文字数の和の情報に相当するので、文書データ１８の文字数の情報に比べて、大きな値になりやすい。そのため、可変長符号化によって転置インデックス１９を生成する場合、転置インデックス１９のデータ容量が大きくなりやすい。しかし、その転置インデックス１９を用いた検索時には、上記図９のステップＳ３０４にて、検索文字列を含む文書データ１８を特定する処理の際に、文書データ１８の文字数の和をとる必要がないため、検索処理を効率的なものにすることができる。
【００８４】
また、本実施形態における生成装置１０では、文書データ１８は、例えば図１のようにＨＤＤ１４内に記憶されるなどして生成装置１０内に存在することに限られない。すなわち、例えば図１０のように、文書データ１８は、生成装置１０内ではなくインターネット上に存在し、通信制御装置１７を介して取得されうるものであってもよい。
【００８５】
また、本実施形態における検索装置２０では、上記の生成装置１０と同様に、文書データ１８は、例えば図２のようにＨＤＤ２４内に記憶されるなどして検索装置２０内に存在することに限られない。すなわち、例えば図１１のように、文書データ１８は、検索装置２０内ではなくインターネット上に存在し、通信制御装置２７を介して取得されうるものであってもよい。
【００８６】
このような構成をとることで、図１１の実施形態では図２でのものに比べ、検索装置２０内に文書データ１８を記憶する必要がなく、インターネットに適切に接続可能な環境であれば、小型の電子辞書のような限られた容量の装置においても実現しやすくなる。
【００８７】
また、本発明での実施形態は、上述した実施形態に加え、上記生成装置１０としてコンピュータ装置を機能させるためのコンピュータプログラムであってもよい。また、上記検索装置２０としてコンピュータ装置を機能させるためのコンピュータプログラムであってもよい。
【００８８】
上記コンピュータプログラムは、コンパクトディスク、フレキシブルディスク、ハードディスク、光磁気ディスク、ディジタルビデオディスク、磁気テープ、半導体メモリ等のコンピュータ読取可能な情報記憶媒体に記憶することができる。
【００８９】
また、上記コンピュータプログラムは、コンピュータプログラムが実行されるコンピュータ装置とは独立して、コンピュータ通信網を介して配付・販売することができる。また、上記情報記憶媒体は、コンピュータ装置とは独立して配付・販売することができる。
【符号の説明】
【００９０】
１０…生成装置、１１…ＣＰＵ、１２…ＲＯＭ、１３…ＲＡＭ、１４…ＨＤＤ、１５…入力装置、１６…出力装置、１７…通信制御装置、１８…文書データ、１９…転置インデックス、２０…検索装置、２１…ＣＰＵ、２２…ＲＯＭ、２３…ＲＡＭ、２４…ＨＤＤ、２５…入力装置、２６…出力装置、２７…通信制御装置、２８…入換文書データ、２９…部分転置インデックス
【特許請求の範囲】
【請求項１】
それぞれが、見出し語と対応する複数の説明文とから構成される複数の文書データのうち、少なくとも１つの文書データの前記複数の説明文の順序を入れ換えて、入換文書データを作成する文書入換ステップと、
前記文書データもしくは前記作成された入換文書データから、「Ｎ文字の文字列であるＮグラム（Ｎは自然数）」を抽出し、抽出されたＮグラムのそれぞれについて、当該文書データもしくは当該入換文書データ中の出現位置を対応付けて、部分転置インデックスを生成する生成ステップと、
前記複数の文書データについて生成された複数の前記部分転置インデックスから、転置インデックスを合成する合成ステップと、
を備えることを特徴とする転置インデックスの生成方法。
【請求項２】
前記生成ステップでは、前記文書データおよび当該文書データから作成された入換文書データから、それぞれ前記部分転置インデックスを生成し、当該それぞれ生成された部分転置インデックスのうち、容量が小さい部分転置インデックスを選定し、
前記合成ステップでは、前記複数の文書データについて選定された複数の前記部分転置インデックスから、転置インデックスを合成する、
ことを特徴とする請求項１に記載の転置インデックスの生成方法。
【請求項３】
前記文書入換ステップでは、前記文書データから、前記順序の入れ換え可能な組合せで前記順序を入れ換えて、当該組合せの数の入換文書データを作成し、
前記生成ステップでは、前記文書データおよび当該文書データから作成された前記組合せの数の入換文書データから、それぞれ前記部分転置インデックスを生成し、当該それぞれ生成された部分転置インデックスのうち、容量が最小の部分転置インデックスを選定する、
ことを特徴とする請求項２に記載の転置インデックスの生成方法。
【請求項４】
前記生成ステップでは、複数の文書データのうち、見出し語と対応する単一の説明文とから構成される文書データからも、前記部分転置インデックスを生成する、
ことを特徴とする請求項１から３のいずれか１項に記載の転置インデックスの生成方法。
【請求項５】
前記生成ステップでは、前記抽出されたＮグラムのそれぞれについて、当該Ｎグラムに対応付けられた出現位置と隣接する出現位置との差分を対応付けて、部分転置インデックスを生成する、
ことを特徴とする請求項１から４のいずれか１項に記載の転置インデックスの生成方法。
【請求項６】
検索文字列からＮグラムを抽出する抽出ステップと、
請求項１から５のいずれか１項に記載の生成方法によって生成された転置インデックスから、前記検索文字列から抽出されたＮグラムに対応付けられた出現位置を取得する位置取得ステップと、
前記取得された出現位置に基づいて、前記複数の文書データのうちから、前記検索文字列を含む文書データを特定する文書特定ステップと、
を備えることを特徴とする検索方法。
【請求項７】
それぞれが、見出し語と対応する複数の説明文とから構成される複数の文書データのうち、少なくとも１つの文書データの前記複数の説明文の順序を入れ換えて、入換文書データを作成する文書入換手段と、
前記文書データもしくは前記作成された入換文書データから、「Ｎ文字の文字列であるＮグラム（Ｎは自然数）」を抽出し、抽出されたＮグラムのそれぞれについて、当該文書データもしくは当該入換文書データ中の出現位置を対応付けて、部分転置インデックスを生成する生成手段と、
前記複数の文書データについて生成された複数の前記部分転置インデックスから、転置インデックスを合成する合成手段と、
を備えることを特徴とする転置インデックスの生成装置。
【請求項８】
検索文字列からＮグラムを抽出する抽出手段と、
請求項１から５のいずれか１項に記載の生成方法によって生成された転置インデックスから、前記検索文字列から抽出されたＮグラムに対応付けられた出現位置を取得する位置取得手段と、
前記取得された出現位置に基づいて、前記複数の文書データのうちから、前記検索文字列を含む文書データを特定する文書特定手段と、
を備えることを特徴とする検索装置。
【請求項９】
コンピュータを、
それぞれが、見出し語と対応する複数の説明文とから構成される複数の文書データのうち、少なくとも１つの文書データの前記複数の説明文の順序を入れ換えて、入換文書データを作成する文書入換手段、
前記文書データもしくは前記作成された入換文書データから、「Ｎ文字の文字列であるＮグラム（Ｎは自然数）」を抽出し、抽出されたＮグラムのそれぞれについて、当該文書データもしくは当該入換文書データ中の出現位置を対応付けて、部分転置インデックスを生成する生成手段、
前記複数の文書データについて生成された複数の前記部分転置インデックスから、転置インデックスを合成する合成手段、
として機能させるためのコンピュータプログラム。
【請求項１０】
コンピュータを、
検索文字列からＮグラムを抽出する抽出手段、
請求項１から５のいずれか１項に記載の生成方法によって生成された転置インデックスから、前記検索文字列から抽出されたＮグラムに対応付けられた出現位置を取得する位置取得手段、
前記取得された出現位置に基づいて、前記複数の文書データのうちから、前記検索文字列を含む文書データを特定する文書特定手段、
として機能させるためのコンピュータプログラム。
【請求項１】
それぞれが、見出し語と対応する複数の説明文とから構成される複数の文書データのうち、少なくとも１つの文書データの前記複数の説明文の順序を入れ換えて、入換文書データを作成する文書入換ステップと、
前記文書データもしくは前記作成された入換文書データから、「Ｎ文字の文字列であるＮグラム（Ｎは自然数）」を抽出し、抽出されたＮグラムのそれぞれについて、当該文書データもしくは当該入換文書データ中の出現位置を対応付けて、部分転置インデックスを生成する生成ステップと、
前記複数の文書データについて生成された複数の前記部分転置インデックスから、転置インデックスを合成する合成ステップと、
を備えることを特徴とする転置インデックスの生成方法。
【請求項２】
前記生成ステップでは、前記文書データおよび当該文書データから作成された入換文書データから、それぞれ前記部分転置インデックスを生成し、当該それぞれ生成された部分転置インデックスのうち、容量が小さい部分転置インデックスを選定し、
前記合成ステップでは、前記複数の文書データについて選定された複数の前記部分転置インデックスから、転置インデックスを合成する、
ことを特徴とする請求項１に記載の転置インデックスの生成方法。
【請求項３】
前記文書入換ステップでは、前記文書データから、前記順序の入れ換え可能な組合せで前記順序を入れ換えて、当該組合せの数の入換文書データを作成し、
前記生成ステップでは、前記文書データおよび当該文書データから作成された前記組合せの数の入換文書データから、それぞれ前記部分転置インデックスを生成し、当該それぞれ生成された部分転置インデックスのうち、容量が最小の部分転置インデックスを選定する、
ことを特徴とする請求項２に記載の転置インデックスの生成方法。
【請求項４】
前記生成ステップでは、複数の文書データのうち、見出し語と対応する単一の説明文とから構成される文書データからも、前記部分転置インデックスを生成する、
ことを特徴とする請求項１から３のいずれか１項に記載の転置インデックスの生成方法。
【請求項５】
前記生成ステップでは、前記抽出されたＮグラムのそれぞれについて、当該Ｎグラムに対応付けられた出現位置と隣接する出現位置との差分を対応付けて、部分転置インデックスを生成する、
ことを特徴とする請求項１から４のいずれか１項に記載の転置インデックスの生成方法。
【請求項６】
検索文字列からＮグラムを抽出する抽出ステップと、
請求項１から５のいずれか１項に記載の生成方法によって生成された転置インデックスから、前記検索文字列から抽出されたＮグラムに対応付けられた出現位置を取得する位置取得ステップと、
前記取得された出現位置に基づいて、前記複数の文書データのうちから、前記検索文字列を含む文書データを特定する文書特定ステップと、
を備えることを特徴とする検索方法。
【請求項７】
それぞれが、見出し語と対応する複数の説明文とから構成される複数の文書データのうち、少なくとも１つの文書データの前記複数の説明文の順序を入れ換えて、入換文書データを作成する文書入換手段と、
前記文書データもしくは前記作成された入換文書データから、「Ｎ文字の文字列であるＮグラム（Ｎは自然数）」を抽出し、抽出されたＮグラムのそれぞれについて、当該文書データもしくは当該入換文書データ中の出現位置を対応付けて、部分転置インデックスを生成する生成手段と、
前記複数の文書データについて生成された複数の前記部分転置インデックスから、転置インデックスを合成する合成手段と、
を備えることを特徴とする転置インデックスの生成装置。
【請求項８】
検索文字列からＮグラムを抽出する抽出手段と、
請求項１から５のいずれか１項に記載の生成方法によって生成された転置インデックスから、前記検索文字列から抽出されたＮグラムに対応付けられた出現位置を取得する位置取得手段と、
前記取得された出現位置に基づいて、前記複数の文書データのうちから、前記検索文字列を含む文書データを特定する文書特定手段と、
を備えることを特徴とする検索装置。
【請求項９】
コンピュータを、
それぞれが、見出し語と対応する複数の説明文とから構成される複数の文書データのうち、少なくとも１つの文書データの前記複数の説明文の順序を入れ換えて、入換文書データを作成する文書入換手段、
前記文書データもしくは前記作成された入換文書データから、「Ｎ文字の文字列であるＮグラム（Ｎは自然数）」を抽出し、抽出されたＮグラムのそれぞれについて、当該文書データもしくは当該入換文書データ中の出現位置を対応付けて、部分転置インデックスを生成する生成手段、
前記複数の文書データについて生成された複数の前記部分転置インデックスから、転置インデックスを合成する合成手段、
として機能させるためのコンピュータプログラム。
【請求項１０】
コンピュータを、
検索文字列からＮグラムを抽出する抽出手段、
請求項１から５のいずれか１項に記載の生成方法によって生成された転置インデックスから、前記検索文字列から抽出されたＮグラムに対応付けられた出現位置を取得する位置取得手段、
前記取得された出現位置に基づいて、前記複数の文書データのうちから、前記検索文字列を含む文書データを特定する文書特定手段、
として機能させるためのコンピュータプログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【公開番号】特開２０１２−６９０７０（Ｐ２０１２−６９０７０Ａ）
【公開日】平成２４年４月５日（２０１２．４．５）
【国際特許分類】
【出願番号】特願２０１０−２１５６１０（Ｐ２０１０−２１５６１０）
【出願日】平成２２年９月２７日（２０１０．９．２７）
【出願人】（０００００１４４３）カシオ計算機株式会社 (8,748)
【Ｆターム（参考）】
【公開日】平成２４年４月５日（２０１２．４．５）
【国際特許分類】
【出願日】平成２２年９月２７日（２０１０．９．２７）
【出願人】（０００００１４４３）カシオ計算機株式会社 (8,748)
【Ｆターム（参考）】
[ Back to top ]