(57)【特許請求の範囲】
【請求項１】
情報処理装置における転置インデックスの生成方法であって、
前記情報処理装置は、見出し語と対応する説明文とからそれぞれ構成される複数の文書データを記憶している記憶手段と、前記記憶手段に記憶されている前記複数の文書データに対する転置インデックスを生成する制御手段とを有し、
前記制御手段が、
前記記憶手段に記憶されている前記見出し語と対応する説明文とからそれぞれ構成される複数の文書データのそれぞれについて、当該見出し語と当該説明文との文字数を計数する文字数計数ステップと、
前記計数された文字数が多い順に、前記複数の文書データの順序を入れ換える順序入換ステップと、
前記順序が入れ換えられた複数の文書データから、「Ｎ文字の文字列であるＮグラム（Ｎは自然数）」を抽出し、抽出されたＮグラムのそれぞれについて、前記順序が入れ換えられた複数の文書データ中の出現位置を対応付けて、転置インデックスを生成する生成ステップと、
を実行することを特徴とする転置インデックスの生成方法。
【請求項２】
前記制御手段が実行する前記生成ステップでは、前記順序が入れ換えられた複数の文書データと、前記順序が入れ換えられる前の複数の文書データと、の対応関係をさらに記憶させて、前記転置インデックスを生成する、
ことを特徴とする請求項１に記載の転置インデックスの生成方法。
【請求項３】
請求項１に記載された転置インデックスの生成方法の順序入換ステップで順序が入れ換えられた複数の文書データを記憶する入換文書データ記憶手段と、
前記請求項１に記載された転置インデックスの生成方法の生成ステップで生成された転置インデックスを記憶する転置インデックス記憶手段と、
前記転置インデックスを用いて前記文書データを検索する制御手段とを有する情報処理装置における検索方法であって、
前記制御手段は、
検索文字列からＮグラムを抽出するＮグラム抽出ステップと、
前記転置インデックスから、前記Ｎグラム抽出ステップにおいて抽出されたＮグラムに対応付けられた出現位置を取得し、当該出現位置に基づいて、前記順序が入れ換えられた複数の文書データのうちから前記検索文字列を含む文書データを特定する文書特定ステップと、
を実行することを特徴とする検索方法。
【請求項４】
見出し語と対応する説明文とからそれぞれ構成される複数の文書データを記憶している記憶手段と、
前記請求項２に記載された転置インデックスの生成方法の生成ステップで生成された転置インデックスを記憶する転置インデックス記憶手段と、
前記転置インデックスを用いて前記文書データを検索する制御手段とを有する情報処理装置における検索方法であって、
前記制御手段は、
検索文字列からＮグラムを抽出するＮグラム抽出ステップと、
前記転置インデックスから、前記Ｎグラム抽出ステップにおいて抽出されたＮグラムに対応付けられた出現位置を取得し、当該出現位置と前記記憶された対応関係とに基づいて、前記順序が入れ換えられる前の複数の文書データのうちから前記検索文字列を含む文書データを特定する文書特定ステップと、
を実行することを特徴とする検索方法。
【請求項５】
前記制御手段が実行する前記文書特定ステップでは、前記複数の文書データのうちから、見出し語と説明文との文字数が前記検索文字列の文字数より少ない文書データを除いて、当該検索文字列を含む文書データを特定する、
ことを特徴とする請求項３または４に記載の検索方法。
【請求項６】
前記制御手段が実行する前記文書特定ステップでは、特定された文書データの数が所定の閾値に達した場合、前記複数の文書データのうちから前記検索文字列を含む文書データの特定処理を終了する、
ことを特徴とする請求項３から５のいずれか１項に記載の検索方法。
【請求項７】
前記検索文字列は、２以上の検索文字列であって、
前記制御手段が実行する前記Ｎグラム抽出ステップでは、前記２以上の検索文字列のそれぞれからＮグラムを抽出し、
前記文書特定ステップでは、前記転置インデックスから、前記２以上の検索文字列のそれぞれから抽出されたＮグラムに対応付けられた出現位置を取得し、当該出現位置に基づいて、前記２以上の検索文字列を含む文書データを特定する、
ことを特徴とする請求項３から６のいずれか１項に記載の検索方法。
【請求項８】
見出し語と対応する説明文とからそれぞれ構成される複数の文書データのそれぞれについて、当該見出し語と当該説明文との文字数を計数する文字数計数手段と、
前記計数された文字数が多い順に、前記複数の文書データの順序を入れ換える順序入換手段と、
前記順序が入れ換えられた複数の文書データから、「Ｎ文字の文字列であるＮグラム（Ｎは自然数）」を抽出し、抽出されたＮグラムのそれぞれについて、前記順序が入れ換えられた複数の文書データ中の出現位置を対応付けて、転置インデックスを生成する生成手段と、
を備えることを特徴とする転置インデックスの生成装置。
【請求項９】
検索文字列からＮグラムを抽出するＮグラム抽出手段と、
請求項１に記載の生成方法によって生成された転置インデックスから、前記Ｎグラム抽出ステップにおいて抽出されたＮグラムに対応付けられた出現位置を取得し、当該出現位置に基づいて、前記順序が入れ換えられた複数の文書データのうちから前記検索文字列を含む文書データを特定する文書特定手段と、
を備えることを特徴とする検索装置。
【請求項１０】
コンピュータを、
見出し語と対応する説明文とからそれぞれ構成される複数の文書データのそれぞれについて、当該見出し語と当該説明文との文字数を計数する文字数計数手段、
前記計数された文字数が多い順に、前記複数の文書データの順序を入れ換える順序入換手段、
前記順序が入れ換えられた複数の文書データから、「Ｎ文字の文字列であるＮグラム（Ｎは自然数）」を抽出し、抽出されたＮグラムのそれぞれについて、前記順序が入れ換えられた複数の文書データ中の出現位置を対応付けて、転置インデックスを生成する生成手段、
として機能させるためのコンピュータプログラム。
【請求項１１】
コンピュータを、
検索文字列からＮグラムを抽出するＮグラム抽出手段、
請求項１に記載の生成方法によって生成された転置インデックスから、前記Ｎグラム抽出ステップにおいて抽出されたＮグラムに対応付けられた出現位置を取得し、当該出現位置に基づいて、前記順序が入れ換えられた複数の文書データのうちから前記検索文字列を含む文書データを特定する文書特定手段、
として機能させるためのコンピュータプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、Ｎグラム検索に関し、とくにＮグラム検索のための転置インデックスの生成方法および生成装置、当該転置インデックスを用いた検索方法および検索装置、ならびにコンピュータプログラムに関する。
【背景技術】
【０００２】
文書の電子化の増大に伴い、これまでに蓄積されてきた大量の文書群から所望の文書を見つけ出す検索技術の重要性が高まっている。
【０００３】
英語などの多くの言語においては、単語を索引単位として索引ファイルを作成して、これを用いて高速な検索処理を実現することが一般的である。しかし、日本語の場合、スペース等によって単語の切れ目が明示的に示されないため、しばしば、Ｎグラムを索引単位とする方法が用いられている。
【０００４】
Ｎグラムとは、連続するＮ文字からなる部分文字列のことである。Ｎグラムによる索引ファイル（以下、転置インデックスと呼称する）の作成には、文字列にのみ基づくため、単語を認識する必要がない。しかし、検索処理される検索語が複数のＮグラムに分割されて処理されるので、長い検索語で検索処理を行う場合、検索時間が増大するという問題がある。
【０００５】
このような問題に対し、非特許文献１において、検索処理の高速化の技術が開示されている。具体的に、非特許文献１では、Ｎグラムの文書頻度の和を処理の高速化の推定値として計算し、実際に文書の検索処理に用いるＮグラムの選定に利用することで、検索処理の高速化を行う。
【先行技術文献】
【非特許文献】
【０００６】
【非特許文献１】小川泰嗣，松田透，”ｎ−ｇｒａｍ索引を用いた効率的な文書検索法”，電子情報通信学会論文誌(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）の３つのファイルから構成される。
【００４８】
ここで、出現位置は、検索対象の文書群を文書番号順に並べたテキストの先頭文字位置を基準とした位置である。同様に、本図中の各文書番号の先頭文字位置も、検索対象の文書群を文書番号順に並べたテキストの先頭文字位置を基準とした位置である。
【００４９】
ステップＳ１０３において作成された転置インデックス３０は、後述する検索装置２０にて行われる検索処理に利用される。
【００５０】
以上の処理により、本実施形態における転置インデックス３０の生成装置１０は、文書データ１８毎の文字数が多い順に、複数の文書データ１８の順序を入れ換えた複数の入換文書データ１９を作成し、複数の入換文書データ１９中のＮグラムについて、複数の入換文書データ１９中における出現位置を対応付けて、転置インデックス３０を生成する。文字数が多い順に順序が入れ換えられるので、複数の入換文書データ１９のうち、文字数が多い入換文書データ１９から順に、検索文字列を含む文書データが特定されることとなる。これは、後述する検索処理を効率的なものにすることにつながる。
【００５１】
次に、本実施形態に係る検索装置２０にて行われる、検索処理について説明する。図６は、検索処理の流れを示すフローチャートである。
【００５２】
まず、検索装置２０の処理が開始されると、例えば検索装置２０の入力装置２５が、ユーザから検索文字列を受け付ける（ステップＳ２０１）。
【００５３】
次に、Ｎグラム抽出手段は、ＣＰＵ２１の機能により、ステップＳ２０１において受け付けられた検索文字列から、Ｎグラムを抽出する（ステップＳ２０２）。ここでＮの値は、検索装置２０において予め定められている値であり、Ｎ＝２、Ｎ＝３、あるいはそれ以外の自然数の値をとる、以下では説明のために、その都度Ｎ＝２やＮ＝３などの場合を用いて説明をする。
【００５４】
具体的に、ユーザが「高速化全文検索処理」という９文字の検索文字列を入力したとする。このとき、Ｎ＝２による検索処理の場合、抽出されるＮグラム（バイグラム）は、前から順に「高速」、「速化」、「化全」、「全文」、「文検」、「検索」、「索処」、「処理」、の８個（９−２＋１個）である。また、例えば、Ｎ＝３による検索処理の場合、抽出されるＮグラム（トリグラム）は、前から順に「高速化」、「速化全」、「化全文」、「全文検」、「文検索」、「検索処」、「索処理」の７個（９−３＋１個）である。
【００５５】
次に、文書特定手段は、ＣＰＵ２１の機能により、最初の入換文書データ１９に着目する（ステップＳ２０３）。そして、検索文字列の文字数と、見出し語と説明文とから構成される着目された入換文書データ１９の文字数と、を比較して、検索文字列の文字数が、入換文書データ１９の文字数より多いか否かを判定する（ステップＳ２０４）。
【００５６】
ここで、入換文書データ１９の文字数を取得するため、上記の生成装置１０によって生成された転置インデックス３０を用いる。例えば、転置インデックス３０が上記の図５のような形式で生成されている場合、文書番号に関するファイル（number.idx）から、連続した２つの文書番号についての先頭文字位置を取得し、両者の差を取ることで、所望の入換文書データ１９の文字数が得られる。例えば、文書番号１の先頭文字位置と、文書番号２の先頭文字位置とを、転置インデックス３０から取得して、両者の差をとると、最初の入換文書データ１９（文書番号１）の文字数が得られる。
【００５７】
ここで、転置インデックス３０は、生成装置１０によって、複数の文書データ１８を文字数の多い順に入れ換えられた複数の入換文書データ１９をもとに生成されているので、最初の入換文書データ１９から得られた文字数は、他の入換文書データ１９に比べて最も多い文字数ということになる。
【００５８】
検索文字列の文字数が、取得された入換文書データ１９の文字数より少ない場合（ステップＳ２０４；ＮＯ）、文書特定手段は、文字数が取得された入換文書データ１９に、検索文字列が含まれるかを判定して、含まれる場合に、その入換文書データ１９を保持する（ステップＳ２０５）。
【００５９】
ここで、入換文書データ１９に検索文字列が含まれるかどうかを判定するために、転置インデックス３０を用いる。具体的には、ステップＳ２０２において、検索文字列から抽出されたＮグラムを用いて、それぞれのＮグラムに対応付けられた出現位置を、転置インデックス３０から取得する。このとき、Ｎグラムに対応付けられた出現位置のすべてを取得する必要はなく、現在着目されている（文字数が取得された）入換文書データ１９内での出現位置を取得すればよい。例えば、先頭の入換文書データ１９（文書番号１）が着目されていた場合は、検索文字列から抽出されたＮグラムに対応付けられた出現位置のうち、その入換文書データ１９内に位置するもの、すなわち、２番目の入換文書データ１９（文書番号２）の先頭文字位置より小さい値の出現位置を、取得すればよい。
【００６０】
そして、ステップＳ２０５では、このように取得されたＮグラムの出現位置のうち、検索文字列を構成するような順番になっているかを判定して、その検索文字列が着目された入換文書データ１９中に含まれているかを判断する。含まれていれば、その入換文書データ１９をＲＡＭ１３等に一時的に保持して、後の処理においてユーザへ出力する。
【００６１】
そして、その後、検索装置２０は、次の入換文書データ１９があるかを判定する（ステップＳ２０６）。すなわち、現在着目している入換文書データ１９が、最後の入換文書データ１９かを判定する。次の入換文書データ１９があれば（ステップＳ２０６）、当該次の入換文書データ１９に着目して（ステップＳ２０７）、その後、処理は再びステップＳ２０４へと戻る。
【００６２】
ここで、複数の入換文書データ１９は、文字数の多い順に入れ換えられているので、例えば最初に着目していた入換文書データ１９が最も文字数の多い入換文書データ１９であった場合は、２番目に文字数の多い入換文書データ１９が着目されることになる。その上で、ステップＳ２０４において、転置インデックス３０のファイル（number.idx）から、文書番号２の先頭文字位置と、文書番号３の先頭文字位置と、の差をとることで、２番目に文字数の多い入換文書データ１９の文字数を取得することができる。
【００６３】
そして、ステップＳ２０４において、このようにして得られた次に着目された入換文書データ１９の文字数が、検索文字列の文字数より多ければ、処理は再びステップＳ２０５へ移行する。すなわち、その着目された入換文書データ１９内に検索文字列が含まれるかを判定して、含まれている場合に、その入換文書データ１９をＲＡＭ１３等に保持する。
【００６４】
このようなステップＳ２０４〜Ｓ２０７の処理を、入換文書データ１９ごとに行う。入換文書データ１９は、文字数の多い順に入れ換えられているので、処理が進めば進むほど、ステップＳ２０４で判定に用いられる入換文書データ１９の文字数は少なくなるが、入換文書データ１９の文字数が、検索文字列の文字数以上である限り、もしくは、ステップＳ２０６において判定されるように次の入換文書データ１９がなくなるまで、その入換文書データ１９に検索文字列が含まれるかを判定して、含まれていれば保持する。
【００６５】
そして、検索文字列の文字数が、入換文書データ１９の文字数より多いと判定された場合（ステップＳ２０４；ＹＥＳ）、もしくは、次の入換文書データ１９がないと判定された場合（ステップＳ２０６；ＮＯ）、上記のステップＳ２０４〜Ｓ２０７の繰り返し処理を抜ける。そして、ステップＳ２０５によって保持された検索文字列を含む入換文書データ１９を、ユーザへ出力する（ステップＳ２０８）。すなわち、ステップＳ２０５の処理において、検索文字列を含むと特定された入換文書データ１９の数だけ、入換文書データ１９が出力されることになる。その後、検索処理を終了する。
【００６６】
ここで、もし検索文字列を含むと特定された入換文書データ１９が１つもなければ、ステップＳ２０８においては、いずれの入換文書データ１９も出力せず、典型的には「検索文字列が見つかりませんでした。」等をユーザへ出力して、処理を終了する。
【００６７】
このように、本実施形態における検索装置２０は、複数の入換文書データ１９のうち、文字数が多い入換文書データ１９から順に、検索文字列が含まれているかを検索していく。そして、入換文書データ１９の文字数が検索文字列の文字数より少ないものについては、検索を行わない。なぜなら、検索文字列よりも文字数の少ない入換文書データ１９は、検索文字列を含まないことが自明なため、検索を行う必要のないからである。これによって、検索処理を行う入換文書データ１９の数を減らすことができ、効率的に検索処理を行うことができる。そのため、例えば携帯電話や電子辞書などのような小型の電子機器では、使用できる資源が限られている環境において、とくに本実施形態は有用である。
【００６８】
なお、本発明は上記の実施形態に限定されず、種々の変形及び応用が可能である。
【００６９】
例えば、上記図６のフローチャートのステップＳ２０５において、特定され、保持された検索文字列を含む入換文書データ１９の数が、所定の閾値を超えた場合、文書特定手段は、処理を終了することもできる。例えば、ユーザが検索をする際に、検索文字列を含む入換文書データ１９をすべて特定せず、いくつか特定された時点で、検索を終了したい場合がある。とくに、入換文書データ１９の数が多い場合など、すべての入換文書データ１９に検索処理を行って、その結果が出力されるのを待っていると、時間がかかりすぎる場合がある。このような状況を考慮して、文書特定手段は、一定数以上、例えば、１００以上の入換文書データ１９を特定した時点で、特定処理を終了することで、効率的な検索を行うことができる。
【００７０】
とくに、本実施形態では、文字数の多い入換文書データ１９から順に検索処理を行うので、この場合における検索処理の効率化がより一層高まることになる。なぜなら、文字数の多い入換文書データ１９の方が、文字数の少ない入換文書データ１９よりも、検索文字列を含む確率が高いため、所定の閾値の数の入換文書データ１９が特定されるまでに検索された入換文書データ１９の数（ステップＳ２０４〜Ｓ２０７までの繰り返し処理の回数）を、少なく抑えることができるからである。なお、所定の閾値は、任意であり、ユーザが設定することもできる。
【００７１】
また、本実施形態では、順序入換手段が入換文書データ１９を作成する際に、入れ換えられる前の状態との対応関係が認識できるように、番号を付してもよい。図７では、順序入れ換え前の複数の文書データ１８のそれぞれに昇順に見出し番号を付し、その状態で、文字数が多い順に文書データ１８が入れ換えられた様子を示している。ここで、最初は昇順に並んでいた見出し番号は、入換文書データ１９では、ばらばらになって並べ替えられている。それに対して、図７では、改めて入換後の見出し番号が、昇順に付されている。
【００７２】
このように付された入換後の見出し番号と入換前の見出し番号とを対応付けて、生成手段が、例えば転置インデックス３０に記憶することで、複数の入換文書データ１９のそれぞれが、入れ換えられる前はどの順番で並んでいたかの対応を付けることができるようになる。
【００７３】
これにより、検索装置２０の文書特定手段が、入換文書データ１９から生成された転置インデックス３０に基づいて、検索文字列が含まれる文書データ１８を特定した場合でも、複数の入換文書データ１９の中においてどの文書データが特定されたかだけでなく、入れ換えられる前の順序で並んでいた複数の文書データ１８の中においてもどの文書データが特定されたのかを判別することが可能になる。
【００７４】
なお、この場合の検索装置２０は、そのＨＤＤ２４に、上記図２のように複数の入換文書データ１９を記憶するかわりに、順序が入れ換えられる前の複数の文書データ１８を記憶する。そして、上記図６のステップＳ２０８では、入換後の見出し番号と入換前の見出し番号との対応付けに基づいて、特定された入れ換え前の文書データ１８を、出力装置２６に表示する等により、ユーザに出力する。
【００７５】
また、ユーザから受け付けられる検索文字列は、上述したように１語であってもよいし、一方で、複数の検索文字列であってもよい。複数の検索文字列を受け付けた場合、複数の検索文字列の論理積、論理和、否定論理積など、演算方法に種類があり、いずれの演算方法による検索を行ってもよい。
【００７６】
このうち、２個の検索文字列の論理積をとって検索を行う場合を例として、以下に説明する。このとき、上述した図６のフローチャートのステップＳ２０４の判定処理において、２個の検索文字列の文字数の和をとって、入換文書データ１９の文字数と比較を行うことになる。すなわち、３文字の検索文字列と５文字の検索文字列の論理積で検索を行う場合、基本的には、和をとった８文字（３＋５文字）と、入換文書データ１９の文字数とを比較する。
【００７７】
ここで、文字列の和をとる際に、一方の検索文字列のうち先頭の文字を含む文字列と、他方の検索文字列のうち末尾の文字を含む文字列と、が一致する場合は、当該一致する文字列の文字数を除いた上で、和をとる。例えば、一方の検索文字列が「あいうえお」であり、他方の検索文字列が「えおかきく」である場合、文字列「えお」が一致しているため、この一致している２文字を除いた８文字（５＋５−２文字）と、入換文書データ１９の文字数と、が比較されることになる。
【００７８】
このように、ステップＳ２０４において、検索文字列の文字数の和と入換文書データ１９の文字数との比較を行う。そして、検索文字列の文字数の和よりも少ない文字数の入換文書データ１９については、ステップＳ２０５の入換文書データ１９の特定処理を行わない。なぜなら、複数の検索文字列の論理積で検索を行う場合、検索装置２０は、複数の検索文字列がすべて入換文書データ１９に含まれているものを特定するため、複数の検索文字列の文字数の和よりも文字数が少ない入換文書データ１９には、すべての検索文字列が含まれることはないからである。
【００７９】
このように、複数の検索文字列の論理積をとった検索では、複数の検索文字列の和をとるため、単一の検索文字列での検索に比べて、入換文書データ１９の文字数と比較する文字数が大きな値になる場合が多い。これによって、多数の入換文書データ１９について、ステップＳ２０５の入換文書データ１９の特定処理を行う必要がなくなる場合が多い。そのため、本実施形態は、複数の検索文字列の論理積をとって行う検索において、とくに検索処理の効率化を高めることができる。
【００８０】
また、文書データ１８（入換文書データ１９）の構成要素は、見出し語と説明文とに限られない。例えば、文書データ１８（入換文書データ１９）は、見出し語、説明文、当該見出し語が説明された図面、当該見出し語が意味する反対の意味を有する見出し語など、から構成されてもよい。
【００８１】
そして、転置インデックス３０の構成要素は、上記図５に示したような構成要素に限られない。例えば、抽出されたＮグラムについて、検索対象の複数の文書データ１８（入換文書データ１９）中における出現頻度を、さらに構成要素としてもよい。この場合、文書特定手段は、出現頻度の情報を利用することで、検索文字列を含む文書データ１８（入換文書データ１９）を、さらに効率的に特定することができる。
【００８２】
さらに、文字列計数手段は、文字数を計数することに限られず、見出し語と説明文とから構成される文書データ１８のデータ量を計測することもできる。そして、順序入換手段は、文字列計数手段により計測されたデータ量が多い順に、複数の文書データ１８の順序を入れ換えることにより、複数の入換文書データ１９を作成することもできる。
【００８３】
なお、本実施形態における生成装置１０では、複数の文書データ１８は、例えば図１のようにＨＤＤ１４内に記憶されるなどして生成装置１０内に存在することに限られない。すなわち、例えば図８のように、複数の文書データ１８は、生成装置１０内ではなくインターネット上に存在し、通信制御装置１７を介して取得されうるものであってもよい。
【００８４】
また、本実施形態における検索装置２０では、上記の生成装置１０と同様に、複数の文書データ１８（入換文書データ１９）は、例えば図２のようにＨＤＤ１４内に記憶されるなどして検索装置２０内に存在することに限られない。すなわち、例えば図９のように、複数の文書データ１８（入換文書データ１９）は、検索装置２０内ではなくインターネット上に存在し、通信制御装置１７を介して取得されうるものであってもよい。
【００８５】
このような構成をとることで、図９の実施形態では図２でのものに比べ、検索装置２０内に複数の文書データ１８（入換文書データ１９）を記憶する必要がなく、インターネットに適切に接続可能な環境であれば、小型の電子辞書のような限られた容量の装置においても実現しやすくなる。
【００８６】
また、本発明での実施形態は、上述した実施形態に加え、上記生成装置１０としてコンピュータ装置を機能させるためのコンピュータプログラムであってもよい。また、上記検索装置２０としてコンピュータ装置を機能させるためのコンピュータプログラムであってもよい。
【００８７】
上記コンピュータプログラムは、コンパクトディスク、フレキシブルディスク、ハードディスク、光磁気ディスク、ディジタルビデオディスク、磁気テープ、半導体メモリ等のコンピュータ読取可能な情報記憶媒体に記憶することができる。
【００８８】
また、上記コンピュータプログラムは、コンピュータプログラムが実行されるコンピュータ装置とは独立して、コンピュータ通信網を介して配付・販売することができる。また、上記情報記憶媒体は、コンピュータ装置とは独立して配付・販売することができる。
【符号の説明】
【００８９】
１０…生成装置、１１…ＣＰＵ、１２…ＲＯＭ、１３…ＲＡＭ、１４…ＨＤＤ、１５…入力装置、１６…出力装置、１７…通信制御装置、１８…文書データ、１９…入換文書データ、２０…検索装置、２１…ＣＰＵ、２２…ＲＯＭ、２３…ＲＡＭ、２４…ＨＤＤ、２５…入力装置、２６…出力装置、２７…通信制御装置、３０…転置インデックス
【図１】
0005601123.tif 000002
【図２】
0005601123.tif 000003
【図３】
0005601123.tif 000004
【図４】
0005601123.tif 000005
【図５】
0005601123.tif 000006
【図６】
0005601123.tif 000007
【図７】
0005601123.tif 000008
【図８】
0005601123.tif 000009
【図９】
0005601123.tif 000010