JP5601121B2 - Ｎグラム検索のための転置インデックスの生成方法および生成装置、当該転置インデックスを用いた検索方法および検索装置、ならびに、コンピュータプログラム - Google Patents

Description

本発明は、Ｎグラム検索に関し、とくにＮグラム検索のための転置インデックスの生成方法および生成装置、当該転置インデックスを用いた検索方法および検索装置、ならびにコンピュータプログラムに関する。

文書の電子化の増大に伴い、これまでに蓄積されてきた大量の文書群から所望の文書を見つけ出す検索技術の重要性が高まっている。

英語などの多くの言語においては、単語を索引単位として索引ファイルを作成して、これを用いて高速な検索処理を実現することが一般的である。しかし、日本語の場合、スペース等によって単語の切れ目が明示的に示されないため、しばしば、Ｎグラムを索引単位とする方法が用いられている。

Ｎグラムとは、連続するＮ文字からなる部分文字列のことである。Ｎグラムによる索引ファイル（以下、転置インデックスと呼称する）の作成には、文字列にのみ基づくため、単語を認識する必要がない。しかし、検索処理される検索語が複数のＮグラムに分割されて処理されるので、長い検索語で検索処理を行う場合、検索時間が増大するという問題がある。

このような問題に対し、非特許文献１において、検索処理の高速化の技術が開示されている。具体的に、非特許文献１では、Ｎグラムの文書頻度の和を処理の高速化の推定値として計算し、実際に文書の検索処理に用いるＮグラムの選定に利用することで、検索処理の高速化を行う。

小川泰嗣，松田透，"ｎ−ｇｒａｍ索引を用いた効率的な文書検索法"，電子情報通信学会論文誌(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）１４、入力装置１５、出力装置１６、通信制御装置１７により構成される。各構成要素は、命令やデータを転送するための伝送経路であるシステムバスにより、相互に接続されている。

ＣＰＵ１１は、生成装置１０全体の動作を制御し、各構成要素と接続され制御信号やデータをやりとりする。
ＲＯＭ１２は、生成装置１０全体の動作制御に必要なコンピュータプログラムや各種データを記憶する。ＣＰＵ１１は、ＲＯＭ１２に記憶されたコンピュータプログラムによって動作し、各種制御を実行する。
ＲＡＭ１３は、データやコンピュータプログラムを一時的に記憶するためのもので、ＲＯＭ１２から読み出したコンピュータプログラムやデータ、その他処理の進行に必要なデータが保持される。
ＨＤＤ１４は、転置インデックスの生成処理の動作のために必要なデータ等を記憶する。このＨＤＤ１４には、複数の文書データ１８が記憶される。生成装置１０は、この複数の文書データ１８をもとにして、転置インデックスを生成する。
入力装置１５は、例えばキーボードやタッチパネル等によって構成され、ユーザからの各種入力を受け付ける。
出力装置１６は、例えばディスプレイ等によって構成され、生成装置１０の種々の処理結果を出力する。
通信制御装置１７は、生成装置１０をインターネット等のコンピュータ通信網に接続するためのものであり、コンピュータ通信網に接続してデータをやり取りする場合に必要となる。

本実施形態では、生成装置１０は、順序入換手段と、対応付け手段と、生成手段と、を備える。これらは、上述したＣＰＵ１１が、ＲＯＭ１２やＲＡＭ１３と協働し、ＨＤＤ１４に記憶されたデータにアクセスしながら、入力装置１５や出力装置１６、通信制御装置１７を用いて外部とやり取りすることで、実現される。

具体的に、生成装置１０の順序入換手段は、見出し語と対応する説明文とからそれぞれ構成される複数の文書データ１８のそれぞれについて、当該見出し語と当該説明文との文字数を計数し、文字数が少ない順に、当該複数の文書データ１８の順序を入れ換える。

ここで、見出し語とは、検索対象となる単語や文書をいう。また、説明文とは、見出し語の意味が説明された文書をいう。例えば、見出し語が「記憶」という単語の場合、説明文は、例えば、「（１）物事を忘れずに覚えている、または覚えておくこと。（２）生物体に過去の影響が残ること。（３）過去の経験の内容を保持し、それを後で思い出すこと。」となり、見出し語と説明文とが対応付けられて、１つの文書データ１８として、例えばＨＤＤ１４に記憶される。

順序入換手段は、ＣＰＵ１１等の機能により、このような見出し語と説明文とから構成される文書データ１８毎に文字列の文字数を計数する。さらに、順序入換手段は、ＣＰＵ１１等の機能により、ＨＤＤ１４に記憶された複数の文書データ１８のうち、文書データ１８の文字数が少ない順に、文書データ１８の順序を入れ換えて、当該順序を入れ換えた複数の入換文書データ１９を、例えばＲＡＭ１２等に記憶させて保持する。

また、生成装置１０の対応付け手段は、順序が入れ換えられた複数の入換文書データ１９のそれぞれの見出し語と説明文との文字列を包含する入換文書データ１９を抽出し、当該抽出された入換文書データ１９と、当該抽出された入換文書データ１９に文字列が包含される入換文書データ１９と、の包含関係を対応付ける。

対応付け手段は、ＣＰＵ１１等の機能により、入換文書データ１９が表す所定の見出し語や所定の説明文の文字列を包含する、複数の入換文書データ１９を抽出する。ここでは、具体例として、複数の入換文書データ１９として、３つの見出し語と、当該３つの見出し語に対応する３つの説明文がある場合を考える。文書データＡ（見出し語：「ダイヤ」、当該見出し語に対応する説明文：「ダイヤ」）、文書データＢ（見出し語：「ダイヤグラム」、当該見出し語に対応する説明文：「列車運行表、また、バスや航空機などの運行予定、ダイヤ、列車ダイヤ」）、文書データＣ（見出し語「記憶」、当該見出し語に対応する説明文：「物事を忘れずに覚えている、または覚えておくこと」）とする。この場合、入換文書データＡには「ダイヤ」という文字列があり、入換文書データＢにも「ダイヤグラム」、「ダイヤ」、「列車ダイヤ」という文字列があるため、入換文書データＢは、入換文書データＡを包含する関係にある。一方、入換文書データＣには「ダイヤ」という文字列がないため、入換文書データＣは、入換文書データＡや入換文書データＢを包含する関係にはない。

すなわち、対応付け手段は、見出し語や説明文の文字列と一致する、他の見出し語や他の説明文の文字列があるか否かを判別することにより、文字列を包含する入換文書データ１９を特定する。そして、文字列を包含する入換文書データ１９がある場合、対応付け手段は、入換文書データ１９同士を対応付けて、当該対応付けられた包含関係を、例えばＲＡＭ１２等に記憶させて保持する。

また、生成装置１０の生成手段は、「Ｎ文字の文字列であるＮグラム（Ｎは自然数）」のそれぞれについて、複数の入換文書データ１９中の出現位置を対応付けて、そして対応付け手段により対応付けられた包含関係をさらに記憶させて、転置インデックスを生成する。生成された転置インデックスは、ＨＤＤ１４に、あるいは出力装置１６や通信制御装置１７を介して、出力される。

具体的には、生成手段は、１個の文書データがＮ_ｄｏｃ文字の文字列から構成されていた場合、Ｎ_ｄｏｃ−Ｎ＋１個のＮグラム（Ｎ文字列）を抽出し、さらに、複数の文書データについて同様にＮグラムを抽出し、同一パターンのＮグラムに関して、それぞれの出現位置を記載した転置インデックスを、生成する。また、生成手段は、対応付け手段により対応付けられた文書データについても同様にＮグラムを抽出し、同一パターンのＮグラムに関して、それぞれの出現位置を記載した転置インデックスを、生成する。生成された転置インデックスは、例えばＨＤＤ１４に記憶されて保存されることになる。

このような生成装置１０によって生成された転置インデックスは、検索装置に搭載され、検索処理に用いられる。本実施形態では、コンピュータ装置を、図２に示されるような検索装置として構成する。また、図２に示される検索装置２０によって、本実施形態に係る転置インデックスの検索方法が実現される。

検索装置２０は、ＣＰＵ２１、ＲＯＭ２２、ＲＡＭ２３、ＨＤＤ２４、入力装置２５、出力装置２６、通信制御装置２７により構成される。各構成要素は、命令やデータを転送するための伝送経路であるシステムバスにより、相互に接続されている。

これらの構成要素は、基本的には図１に示された生成装置１０の構成要素と同等なものである。すなわち、図１では、文書データ１８から転置インデックスを生成するために機能した各構成要素が、ここでは生成された転置インデックスを用いて検索処理を行うために機能する。

すなわち、ＣＰＵ２１は、検索装置２０全体の動作を制御し、各構成要素と接続され制御信号やデータをやりとりする。
ＲＯＭ２２は、検索装置２０全体の動作制御に必要なコンピュータプログラムや各種データを記憶する。ＣＰＵ１１は、ＲＯＭ１２に記憶されたコンピュータプログラムによって動作し、各種制御を実行する。
ＲＡＭ２３は、データやコンピュータプログラムを一時的に記憶するためのもので、ＲＯＭ２２から読み出したコンピュータプログラムやデータ、その他処理の進行に必要なデータが保持される。
ＨＤＤ２４は、検索処理の動作のために必要なデータ等を記憶する。このＨＤＤ２４には、生成装置１０によって生成された転置インデックス３０と、その際に複数の文書データ１８から順序が入れ換えられた複数の入換文書データ１９と、が記憶される。検索装置２０は、この転置インデックス３０をもとに、ユーザによって指定された検索文字列が複数の入換文書データ１９の中のどの入換文書データ１９中に出現するかを特定する。
入力装置２５は、例えばキーボードやタッチパネル等によって構成され、ユーザからの各種入力を受け付ける。
出力装置２６は、例えばディスプレイ等によって構成され、検索装置２０の種々の処理結果を出力する。
通信制御装置２７は、検索装置２０をインターネット等のコンピュータ通信網に接続するためのものであり、コンピュータ通信網に接続してデータをやり取りする場合に必要となる。

本実施形態では、検索装置２０は、Ｎグラム抽出手段と、文書特定手段と、を備える。これらは、上述したＣＰＵ１１が、ＲＯＭ１２やＲＡＭ１３と協働し、ＨＤＤ１４に記憶されたデータにアクセスしながら、入力装置１５や出力装置１６、通信制御装置１７を用いて外部とやり取りすることで、実現される。

具体的に、検索装置２０のＮグラム抽出手段は、検索文字列からＮグラムを抽出する。すなわち、例えば検索装置２０の入力装置２５が、ユーザが入力した検索文字列を受付ける。そして、Ｎグラム抽出手段は、検索装置２０のＣＰＵ２１などによって、検索文字列を構成するＮグラムのうち、抽出可能なものを抽出する。具体的には、ユーザがＭ文字の検索文字列を入力したとき、Ｎグラム抽出部１３は、検索文字列から抽出可能なすべてのＮグラム（Ｎ文字列）を抽出する。すなわち、ＭがＮより大きい場合は、Ｍ−Ｎ＋１個のＮグラムが抽出されることになる。

そして、検索装置２０の文書特定手段は、転置インデックス３０から、Ｎグラム抽出手段において抽出されたＮグラムに対応付けられた出現位置を取得し、当該出現位置に基づいて、複数の入換文書データ１９のうちから検索文字列を含む入換文書データ１９を特定する。さらに、文書特定手段は、特定した入換文書データ１９に対応付けられた入換文書データ１９を特定する。特定された入換文書データ１９は、出力装置２６や通信制御装置２７を介して出力される。

すなわち、生成装置１０によって生成された転置インデックス３０は、文字列を包含する文書データが対応付けられているので、文書特定手段は、複数の入換文書データ１９のうち、１つの入換文書データ１９を特定すると、当該入換文書データ１９に対応付けられた入換文書データ１９をさらに特定することとなる。

このような構成によって実現される生成装置１０と検索装置２０における、処理の流れの詳細を説明する。ここではまず、図３を参照して、転置インデックス３０の生成処理について、フローチャートを用いて説明する。

生成装置１０が、例えば入力装置１５を介してユーザからの生成処理の開始の指示を受け付けることで、転置インデックス３０の生成処理を開始する。転置インデックス３０の生成処理が開始されると、生成装置１０の順序入換手段は、ＣＰＵ１１の機能により、例えばＨＤＤ１４に記憶された複数の文書データ１８のそれぞれについて、文字列の文字数を計数する（ステップＳ１０１）。ここで、文書データ１８は、見出し語と当該見出し語の説明文とから構成される。順序入換手段は、文書データ１８の文字数によって、複数の文書データ１８の順序を入れ換えるために、見出し語の文字列及び説明文の文字列の文字数を計数する。例えば、順序入換手段は、見出し語の文字数が５であり、説明文の文字数が１５である場合、文書データ１８の文字数を２０（＝５＋１５）と計数する。順序入換手段により、複数の文書データ１８のそれぞれについて文字数が計数されるため、文書データ１８毎の文字数が導出される。

次に、生成装置１０の順序入換手段は、ＣＰＵ１１の機能により、順序入換手段により計数された文字数の少ない順に、複数の文書データ１８の順序を入れ換える（ステップＳ１０２）。具体的に説明すると、複数の文書データ１８は、図４に示されるように、例えば、当初は、見出し語１、見出し語２、見出し語３、というように、見出し語の順番で文書データ１８が並べられて、文書データ１８の文字数とは無関係に並べられていた。例えば、文字数の少ない見出し語２（１５文字）の文書データ１８よりも、文字数の多い見出し語１（３０文字）の文書データ１８の方が前に位置している。

本実施形態では、順序入換手段が、この状態から、複数の文書データ１８を文字数の少ない順に並べ替えて、複数の入換文書データ１９とする。具体的に説明すると、複数の文書データ１８のうち、最も文字数の少ない見出し語Ｚの文書データ１８を先頭にし、最も文字数の多い見出し語３の文書データ１８を末尾にする。また、当初は先頭にあった見出し語１の文書データ１８は、複数の文書データ１８の中では５番目に文字数が少ないものであるため、複数の入換文書データ１９では５番目に並べる。

このように、順序入換手段は、文書データ１８毎に文字数が計数された複数の文書データ１８のうち、文字数が少ない順に、文書データ１８の順序を入れ換えることにより、入換文書データ１９を生成する。そして、順序入換手段は、入換文書データ１９を、ＲＡＭ１３やＨＤＤ１４に記憶する。

次に、生成装置１０の対応付け手段は、ＣＰＵ２１の機能により、最初の入換文書データ１９に着目する（ステップＳ１０３）。そして、対応付け手段は、複数の入換文書データ１９の中に、着目された入れ過分書データ１９の構成する見出し語と説明文との文字列を包含する入換文書データ１９が、他にあるか否かを判定する（ステップＳ１０４）。例えば、着目された入換文書データ１９の見出し語の文字列が「ＡＢ」であり、対応する説明文の文字列が「ＣＤＥ」の場合、対応付け手段は、当該「ＡＢ」という文字列と当該「ＣＤＥ」という文字列とを、いずれも含む入換文書データ１９が他にあるか否かを判定する。このような文字列を包含する入換文書データ１９としては、例えば、見出し語あるいは説明文に「ＡＢＣＤＥ」、「ＡＢＸＹＺＣＤＥ」、「ＣＤＥＡＢ」という文字列を含む入換文書データ１９などが相当する。

そして、複数の入換文書データ１９の中に、着目された入換文書データ１９の文字列を包含するものがあると判定された場合（ステップＳ１０４；ＹＥＳ）、対応付け手段は、着目した入換文書データ１９に、その文字列を包含する入換文書データ１９を対応付けて、当該対応付けられた包含関係を保持する（ステップＳ１０５）。具体的に説明すると、図５に示されるように、例えば、見出し語２０を有する入換文書データ１９ａに、４つの入換文書データ１９ｃ〜１９ｆを対応付け、見出し語５７を有する入換文書データ１９ｂに、２つの入換文書データ１９ｇ〜１９ｈを対応付ける。対応付け手段は、このように対応付けられた包含関係を、ＲＡＭ１３等に保持する。

一方で、複数の入換文書データ１９の中に、着目された入換文書データ１９の文字列を包含するものがあると判定されなかった場合（ステップＳ１０４；ＮＯ）、検索装置２０の処理は上述したステップＳ１０５を通らない。すなわち、上述した包含関係を保持しない。

そして、検索装置２０の対応付け手段は、次の入換文書データ１９があるかを判定する（ステップＳ１０６）。すなわち、対応付け手段は、現在着目している入換文書データ１９が、最後の入換文書データ１９かを判定する。次の入換文書データ１９があれば（ステップＳ１０６；ＹＥＳ）、対応付け手段は、当該次の入換文書データ１９に着目して（ステップＳ１０７）、その後、処理は再びステップＳ１０４へと戻る。

このようなステップＳ１０４〜Ｓ１０７の処理を、入換文書データ１９ごとに行う。そして、次の入換文書データ１９がなくなるまで、ステップＳ１０３において着目された入換文書データ１９の文字列を包含する、入換文書データ１９を判定して、含まれていれば包含関係を保持する。

ここで、複数の入換文書データ１９は、文字数の少ない順に入れ換えられているので、ステップＳ１０３において着目された入換文書データ１９の文字数より文字数が多い入換文書データ１９が、ステップＳ１０４〜Ｓ１０７の処理において、次々と着目されることとなる。このため、複数の入換文書データ１９を先頭から順次着目するだけで、ステップＳ１０３において着目された入換文書データ１９の文字列を包含する、他の入換文書データ１９を特定することができる。

次に、生成装置１０の生成手段は、ＣＰＵ１１の機能により、文字数が少ない順に入れ換えられて記憶された入換文書データ１９から抽出されるＮグラムのそれぞれについて、入換文書データ１９中の出現位置と、を構成要素とし、さらにステップＳ１０５において保持された包含関係を記憶させて、転置インデックス３０を生成する（ステップＳ１０８）。生成された転置インデックス３０は、ＨＤＤ１４に記憶される、あるいは出力装置１６、通信制御装置１７を介して出力される。そして、その後、検索処理を終了する。

以下、図６を用いて、本実施形態に係る転置インデックス３０の具体的な構成を説明する。本図に示すように、転置インデックス３０は、Ｎグラム文字列パターンと出現位置情報格納アドレスが記載されたファイル（pattern.idx）、各Ｎグラム文字列パターンについての出現位置が記載されたファイル（position.idx）、文書番号と各文書の先頭文字位置が記載されたファイル（number.idx）、および包含関係に関するファイル（relation.idx）から構成される。

ここで、出現位置は、検索対象の文書群を文書番号順に並べたテキストの先頭文字位置を基準とした位置である。同様に、本図中の各文書番号の先頭文字位置も、検索対象の文書群を文書番号順に並べたテキストの先頭文字位置を基準とした位置である。

包含関係に関するファイル（relation.idx）は、上述した生成処理のステップＳ１０５において保持された包含関係が記載される。具体的には、上記図５において、見出し語２０の入換文書データ１９ａには、見出し語４５、８５、４５６、７７５の入換文書データ１９ｃ〜１９ｆが対応付けられていたため、図６では、文書番号２０（見出し語２０）に対して、４つの包含文書番号４５、８５、４５６、７７５が対応付けられている。同様に、文書番号５７（見出し語５７）に対して、２つの包含文書番号２０３、３６０が対応付けられている。

ステップＳ１０８において作成された転置インデックス３０は、後述する検索装置２０にて行われる検索処理に利用される。

以上の処理により、本実施形態における転置インデックス３０の生成装置１０は、文書データ１８毎の文字数が少ない順に、複数の文書データ１８の順序を入れ換えた入換文書データ１９を作成し、入換文書データ１９中のＮグラムについて、入換文書データ１９中における出現位置を対応付けて、転置インデックス３０を生成する。また、文字列を包含する関係にある入換文書データ１９を対応付けて、その包含関係をさらに記憶させて転置インデックス３０を生成する。文字列を包含する関係にある入換文書データ１９が対応付け（紐付け）されているため、検索文字列を含む入換文書データ１９が特定されると、当該入換文書データ１９に紐付けられた入換文書データ１９も特定されることとなる。これは、後述する検索処理を効率的なものにすることにつながる。

次に、本実施形態に係る検索装置２０にて行われる、検索処理について説明する。図７は、検索処理の流れを示すフローチャートである。

まず、検索装置２０の処理が開始されると、例えば検索装置２０の入力装置２５が、ユーザから検索文字列を受け付ける（ステップＳ２０１）。

次に、Ｎグラム抽出手段は、ＣＰＵ２１の機能により、ステップＳ２０１において受け付けられた検索文字列から、Ｎグラムを抽出する（ステップＳ２０２）。ここでＮの値は、検索装置２０において予め定められている値であり、Ｎ＝２、Ｎ＝３、あるいはそれ以外の自然数の値をとる、以下では説明のために、その都度Ｎ＝２やＮ＝３などの場合を用いて説明をする。

具体的に、ユーザが「高速化全文検索処理」という９文字の検索文字列を入力したとする。このとき、Ｎ＝２による検索処理の場合、抽出されるＮグラム（バイグラム）は、前から順に「高速」、「速化」、「化全」、「全文」、「文検」、「検索」、「索処」、「処理」、の８個（９−２＋１個）である。また、例えば、Ｎ＝３による検索処理の場合、抽出されるＮグラム（トリグラム）は、前から順に「高速化」、「速化全」、「化全文」、「全文検」、「文検索」、「検索処」、「索処理」の７個（９−３＋１個）である。

次に、文書特定手段は、ＣＰＵ２１の機能により、最初の入換文書データ１９に着目する（ステップＳ２０３）。そして、文書特定手段は、着目された入換文書データ１９に、検索文字列が含まれるか否かを判定する（ステップＳ２０４）。ここで、入換文書データ１９に検索文字列が含まれるかどうかを判定するために、転置インデックス３０を用いる。具体的には、ステップＳ２０２において、検索文字列から抽出されたＮグラムを用いて、それぞれのＮグラムに対応付けられた出現位置を、転置インデックス３０から取得する。

ステップＳ２０４では、文書特定手段は、取得されたＮグラムの出現位置のうち、検索文字列を構成するような連続した出現位置があるかを判定して、その検索文字列が着目された入換文書データ１９中に含まれているかを判断する。そして、着目された入換文書データ１９に検索文字列が含まれる場合（ステップＳ２０４；ＹＥＳ）、文書特定手段は、その入換文書データ１９をＲＡＭ１３等に一時的に保持して（ステップＳ２０５）、後の処理においてユーザへ出力する。

一方、着目された入換文書データ１９に検索文字列が含まれない場合（ステップＳ２０４；ＮＯ）、文書特定手段は、着目された入換文書データ１９の次に、入換文書データ１９があるか否かを判定する（ステップＳ２０８）。複数の入換文書データ１９は、文字数が少ない順に入れ換えられているので、文書特定手段は、文字数が徐々に多くなる順に、入換文書データ１９を着目していくこととなる。そして、文書特定手段は、現在着目している入換文書データ１９が、最後の入換文書データ１９かを判定する。

次に、文書特定手段は、ＣＰＵ２１の機能により、検索文字列が含まれると判定された入換文書データ１９に対応付けられる入換文書データ１９があるか否かを判定する（ステップＳ２０６）。

転置インデックス３０の包含関係に関するファイル（relation.idx）では、文字列が対応する（文字列を包含する）文書番号がそれぞれ対応付けられている。このため、文書特定手段は、検索文字列が含まれると判定された入換文書データ１９の文書番号に対応付けられた包含文書番号があるか否かを判定する。そして、対応付けられた包含文書番号がある場合、文書特定手段は、当該包含文書番号が付された入換文書データ１９が、検索文字列が含まれると判定された入換文書データ１９に対応付けられている文書データであると特定する。

対応付けられる入換文書データ１９がある場合（ステップＳ２０６；ＹＥＳ）、文書特定手段は、ステップＳ２０４において、検索文字列が含まれると判定された入換文書データ１９に対応付けられた、すべての入換文書データ１９をＲＡＭ１３等に一時的に保持する（ステップＳ２０７）。

一方、対応付けられる入換文書データ１９がない場合（ステップＳ２０６；ＮＯ）、文書特定手段は、着目された入換文書データ１９の次に、入換文書データ１９があるか否かを判定する（ステップＳ２０８）。そして、次の入換文書データ１９があれば（ステップＳ２０８；ＹＥＳ）、文書特定手段は、当該次の入換文書データ１９が、ステップＳ２０４において対応付けられていると判定された入換文書データ１９であるか否かを判定する（ステップＳ２０９）。

次の入換文書データ１９が、対応付けられていると判定された入換文書データ１９である場合（ステップＳ２０９；ＹＥＳ）、文書特定手段は、当該次の入換文書データ１９を着目せずに（ステップＳ２１０）、当該次の入換文書データ１９のその次の入換文書データ１９があるか否かを判定する（ステップＳ２０８）。これは、ステップＳ２０４において対応付けられていると判定された入換文書データ１９は、検索文字列が含まれると判定された入換文書データの文字列を包含しているため、検索文字列が含まれるか否かを再度判定する必要がないからである。このため、ステップＳ２０８〜Ｓ２１０の処理を行うことにより、入換文書データ１９に検索文字列が含まれるか否かを判定する処理回数を減らすことができる。

次の入換文書データ１９が、対応付けられていると判定された入換文書データ１９でない場合（ステップＳ２０９；ＮＯ）、文書特定手段は、当該次の入換文書データ１９に着目して（ステップＳ２１１）、その後、処理は再びステップＳ２０４へと戻る。

次の入換文書データ１９がない場合（ステップＳ２０８；ＮＯ）、文書特定手段は、すべての入換文書データ１９について、検索文字列が含まれるか否かを判定したとして、上記のステップＳ２０４〜Ｓ２１１の繰り返し処理を抜ける。そして、文書特定手段は、ステップＳ２０５及びＳ２０７によって保持された検索文字列を含む入換文書データ１９を、ユーザへ出力する（ステップＳ２１２）。すなわち、ステップＳ２０４の処理において、検索文字列を含むと特定された入換文書データ１９と、ステップＳ２０６の処理において、当該入換文書データ１９に対応付けられていると判定されたすべての入換文書データ１９と、が出力されることになる。その後、検索処理を終了する。

このようなステップＳ２０４〜Ｓ２１１の処理を、入換文書データ１９ごとに行う。検索文字列が含まれると判定された入換文書データ１９に対応付けられた入換文書データ１９がある場合、検索文字列が含まれる入換文書データ１９がまず１つ特定され、当該入換文書データ１９に対応付けられた入換文書データ１９についてもさらに特定される。このため、検索文字列が含まれる入換文書データ１９を一度に特定することができる。

ステップＳ２１２において、もし検索文字列を含むと特定された入換文書データ１９が１つもなければ、文書特定手段は、いずれの入換文書データ１９も出力せず、典型的には「検索文字列が見つかりませんでした。」等をユーザへ出力して、処理を終了する。

このように、本実施形態における検索装置２０は、複数の入換文書データ１９のうち、検索文字列が含まれる入換文書データ１９が１つ特定されると、当該入換文書データ１９に対応付けられた、文字列が一致する（文字列を包含する）入換文書データ１９も同時に特定することができる。これによって、複数の入換文書データ１９中から、検索文字列が含まれるか否かを判定する処理回数を減らすことができ、効率的に検索処理を行うことができる。そのため、例えば携帯電話や電子辞書などのような小型の電子機器では、使用できる資源が限られている環境において、とくに本実施形態は有用である。

なお、本発明は上記の実施形態に限定されず、種々の変形及び応用が可能である。

例えば、本実施形態では、順序入換手段が入換文書データ１９を作成する際に、入れ換えられる前の状態との対応関係が認識できるように、番号を付してもよい。図８では、順序入れ換え前の複数の文書データ１８のそれぞれに昇順に見出し番号を付し、その状態で、文字数が多い順に文書データ１８が入れ換えられて入換文書データ１９が作成される様子を示している。ここで、最初は昇順に並んでいた見出し番号は、入換文書データ１９では、ばらばらになって並べ替えられている。それに対して、図８では、改めて入換後の見出し番号が、昇順に付されている。

このように付された入換後の見出し番号と入換前の見出し番号とを対応付けて、生成手段が、例えば転置インデックス３０に記憶することで、それぞれの入換文書データ１９が、入れ換えられる前はどの順番で並んでいたかの対応を付けることができるようになる。

これにより、検索装置２０の文書特定手段が、複数の入換文書データ１９から生成された転置インデックス３０に基づいて、検索文字列が含まれる入換文書データ１９を特定した場合でも、複数の入換文書データ１９の中においてどの入換文書データ１９が特定されたかだけでなく、入れ換えられる前の順序で並んでいた複数の文書データ１８の中においてもどの文書データ１８が特定されたのかを判別することが可能になる。

また、対応付け手段は、入換文書データ同士の対応構造が多層構造となるように、入換文書データ１９同士を対応付けることもできる。図９では、入換文書データ１９ａ（見出し語２０）に対して、入換文書データ１９ｃ（見出し語４５）が対応付けられ、さらに、当該入換文書データ１９ｃ（見出し語４５）に対して、３つの入換文書データ１９ｉ〜１９ｋが対応付けられた様子を示している。また、入換文書データ１９ｆ（見出し語７７５）に対しては、２つの入換文書データ１９ｌ〜１９ｍが対応付けられ、さらに入換文書データ１９ｌに対して、入換文書データ１９ｎが対応付けられている。このように、対応付け手段は、文字列が一致する入換文書データ１９を多層的に対応付けることもできる。これにより、１つの入換文書データ１９が特定されると、当該入換文書データ１９に対応付けられた複数の入換文書データ１９を特定することができるため、効率的に検索処理を行うことができる。

また、ステップＳ１０８において、「＆」、「＊」、「＋」等の記号や特殊文字を取り除いた、転置インデックス３０を生成することもできる。当該記号等は、検索文字列としてユーザから入力されることが少ないため、記号等を取り除いた転置インデックス３０を生成し、当該転置インデックスに基づいて、検索処理を行うことにより、検索対象となる単語等を効率的に絞り込むことができる。さらに、記号等を取り除いた転置インデックス３０では、文字列を包含する関係にある入換文書データ１９同士を対応付けた対応関係を示す構成要素の割合が相対的に大きくなるため、効率的な検索を行うことができる。

また、ユーザから受け付けられる検索文字列は、１語であってもよいし、一方で、複数の検索文字列であってもよい。複数の検索文字列を受け付けた場合、複数の検索文字列の論理積、論理和、否定論理積など、演算方法に種類があり、いずれの演算方法による検索を行ってもよい。

また、文書データ１８の構成要素は、見出し語と説明文とに限られない。例えば、文書データ１８は、見出し語、説明文、当該見出し語が説明された図面、当該見出し語が意味する反対の意味を有する見出し語など、から構成されてもよい。

そして、転置インデックス３０の構成要素は、上記図５に示したような構成要素に限られない。例えば、抽出されたＮグラムについて、検索対象の複数の文書データ１８中における出現頻度を、さらに構成要素としてもよい。この場合、文書特定手段は、出現頻度の情報を利用することで、検索文字列を含む文書データ１８を、さらに効率的に特定することができる。

さらに、順序入換手段は、文書データ１８の順序を入れ換える際に、文字数を計数することに限られず、見出し語と説明文とから構成される文書データ１８のデータ量を計測することもできる。そして、順序入換手段は、計測されたデータ量が少ない順に、複数の文書データ１８の順序を入れ換えることにより、入換文書データ１９を作成することもできる。

なお、本実施形態における生成装置１０では、文書データ１８は、例えば図１のようにＨＤＤ１４内に記憶されるなどして生成装置１０内に存在することに限られない。すなわち、例えば図１１のように、文書データ１８は、生成装置１０内ではなくインターネット上に存在し、通信制御装置１７を介して取得されうるものであってもよい。

また、本実施形態における検索装置２０では、上記の生成装置１０と同様に、文書データ１８は、例えば図２のようにＨＤＤ１４内に記憶されるなどして検索装置２０内に存在することに限られない。すなわち、例えば図１１のように、文書データ１８は、検索装置２０内ではなくインターネット上に存在し、通信制御装置１７を介して取得されうるものであってもよい。

このような構成をとることで、図１１の実施形態では図２でのものに比べ、検索装置２０内に文書データ１８を記憶する必要がなく、インターネットに適切に接続可能な環境であれば、小型の電子辞書のような限られた容量の装置においても実現しやすくなる。

また、本発明での実施形態は、上述した実施形態に加え、上記生成装置１０としてコンピュータ装置を機能させるためのコンピュータプログラムであってもよい。また、上記検索装置２０としてコンピュータ装置を機能させるためのコンピュータプログラムであってもよい。

上記コンピュータプログラムは、コンパクトディスク、フレキシブルディスク、ハードディスク、光磁気ディスク、ディジタルビデオディスク、磁気テープ、半導体メモリ等のコンピュータ読取可能な情報記憶媒体に記憶することができる。

また、上記コンピュータプログラムは、コンピュータプログラムが実行されるコンピュータ装置とは独立して、コンピュータ通信網を介して配付・販売することができる。また、上記情報記憶媒体は、コンピュータ装置とは独立して配付・販売することができる。

１０…生成装置、１１…ＣＰＵ、１２…ＲＯＭ、１３…ＲＡＭ、１４…ＨＤＤ、１５…入力装置、１６…出力装置、１７…通信制御装置、１８…文書データ、１９…入換文書データ、２０…検索装置、２１…ＣＰＵ、２２…ＲＯＭ、２３…ＲＡＭ、２４…ＨＤＤ、２５…入力装置、２６…出力装置、２７…通信制御装置、３０…転置インデックス

Claims (10)

1. 情報処理装置における転置インデックスの生成方法であって、
   前記情報処理装置は、見出し語と対応する説明文とからそれぞれ構成される複数の文書データを記憶している記憶手段と、前記記憶手段に記憶されている前記複数の文書データに対する転置インデックスを生成する制御手段とを有し、
   前記制御手段が、
   前記記憶手段に記憶されている前記見出し語と対応する説明文とからそれぞれ構成される複数の文書データのそれぞれについて、当該見出し語と当該説明文との文字数を計数し、文字数が少ない順に、当該複数の文書データの順序を入れ換える順序入換ステップと、
   「Ｎ文字の文字列であるＮグラム（Ｎは自然数）」のそれぞれについて、前記順序が入れ換えられた複数の文書データ中の出現位置を対応付けて、転置インデックスを生成する生成ステップと、
   を実行することを特徴とする転置インデックスの生成方法。
2. 前記制御手段は、
   前記順序が入れ換えられた複数の文書データのそれぞれの見出し語と説明文との文字列を包含する文書データを抽出し、当該抽出された文書データと、当該抽出された文書データに文字列が包含される文書データと、の包含関係を対応付ける対応付けステップをさらに実行し、
   前記制御手段が実行する前記生成ステップでは、当該包含関係をさらに記憶させて、前記転置インデックスを生成する、
   ことを特徴とする請求項１に記載の転置インデックスの生成方法。
3. 前記制御手段が実行する前記生成ステップでは、前記順序が入れ換えられた複数の文書データと、前記順序が入れ換えられる前の複数の文書データと、の対応関係をさらに記憶させて、前記転置インデックスを生成する、
   ことを特徴とする請求項１または２に記載の転置インデックスの生成方法。
4. 請求項１に記載された転置インデックスの生成方法の順序入換ステップで順序が入れ換えられた複数の文書データを記憶する入換文書データ記憶手段と、
   請求項１に記載された転置インデックスの生成方法の生成ステップで生成された転置インデックスを記憶する転置インデックス記憶手段と、
   前記転置インデックスを用いて前記文書データを検索する制御手段とを有する情報処理装置における検索方法であって、
   前記制御手段は、
   検索文字列からＮグラムを抽出するＮグラム抽出ステップと、
   前記転置インデックスから、前記Ｎグラム抽出ステップにおいて抽出されたＮグラムに対応付けられた出現位置を取得し、当該出現位置に基づいて、前記順序が入れ換えられた複数の文書データのうちから前記検索文字列を含む文書データを特定する文書特定ステップと、
   を実行することを特徴とする検索方法。
5. 請求項２に記載された転置インデックスの生成方法の順序入換ステップで順序が入れ換えられた複数の文書データを記憶する入換文書データ記憶手段と、
   請求項２に記載された転置インデックスの生成方法の生成ステップで生成された転置インデックスを記憶する転置インデックス記憶手段と、
   前記転置インデックスを用いて前記文書データを検索する制御手段とを有する情報処理装置における検索方法であって、
   前記制御手段は、
   検索文字列からＮグラムを抽出するＮグラム抽出ステップと、
   前記転置インデックスから、前記Ｎグラム抽出ステップにおいて抽出されたＮグラムに対応付けられた出現位置を取得し、当該出現位置に基づいて、前記順序が入れ換えられた複数の文書データのうちから前記検索文字列を含む文書データを特定し、前記記憶された包含関係に基づいて、当該特定した文書データに対応付けられた文書データをさらに特定する文書特定ステップと、
   を実行することを特徴とする検索方法。
6. 請求項３に記載された転置インデックスの生成方法の順序入換ステップで順序が入れ換えられた複数の文書データを記憶する入換文書データ記憶手段と、
   請求項３に記載された転置インデックスの生成方法の生成ステップで生成された転置インデックスを記憶する転置インデックス記憶手段と、
   前記転置インデックスを用いて前記文書データを検索する制御手段とを有する情報処理装置における検索方法であって、
   前記制御手段は、
   検索文字列からＮグラムを抽出するＮグラム抽出ステップと、
   前記転置インデックスから、前記Ｎグラム抽出ステップにおいて抽出されたＮグラムに対応付けられた出現位置を取得し、当該出現位置と、前記順序が入れ換えられた複数の文書データと前記順序が入れ換えられる前の複数の文書データとの対応関係と、に基づいて、前記順序が入れ換えられる前の複数の文書データのうちから前記検索文字列を含む文書データを特定し、前記記憶された包含関係に基づいて、当該特定した文書データに対応付けられた文書データをさらに特定する文書特定ステップと、
   を実行することを特徴とする検索方法。
7. 見出し語と対応する説明文とからそれぞれ構成される複数の文書データのそれぞれについて、当該見出し語と当該説明文との文字数を計数し、文字数が少ない順に、当該複数の文書データの順序を入れ換える順序入換手段と、
   「Ｎ文字の文字列であるＮグラム（Ｎは自然数）」のそれぞれについて、前記順序が入れ換えられた複数の文書データ中の出現位置を対応付けて、転置インデックスを生成する生成手段と、
   を備えることを特徴とする転置インデックスの生成装置。
8. 検索文字列からＮグラムを抽出するＮグラム抽出手段と、
   請求項１に記載の生成方法によって生成された転置インデックスから、前記Ｎグラム抽出ステップにおいて抽出されたＮグラムに対応付けられた出現位置を取得し、当該出現位置に基づいて、前記順序が入れ換えられた複数の文書データのうちから前記検索文字列を含む文書データを特定する文書特定手段と、
   を備えることを特徴とする検索装置。
9. コンピュータを、
   見出し語と対応する説明文とからそれぞれ構成される複数の文書データのそれぞれについて、当該見出し語と当該説明文との文字数を計数し、文字数が少ない順に、当該複数の文書データの順序を入れ換える順序入換手段、
   「Ｎ文字の文字列であるＮグラム（Ｎは自然数）」のそれぞれについて、前記順序が入れ換えられた複数の文書データ中の出現位置を対応付けて、転置インデックスを生成する生成手段、
   として機能させるためのコンピュータプログラム。
10. コンピュータを、
    検索文字列からＮグラムを抽出するＮグラム抽出手段、
    請求項１に記載の生成方法によって生成された転置インデックスから、前記Ｎグラム抽出ステップにおいて抽出されたＮグラムに対応付けられた出現位置を取得し、当該出現位置に基づいて、前記順序が入れ換えられた複数の文書データのうちから前記検索文字列を含む文書データを特定する文書特定手段、
    として機能させるためのコンピュータプログラム。

Images