Ｎグラム検索のための転置インデックスの生成方法および生成装置、当該転置インデックスを用いた検索方法および検索装置、ならびに、コンピュータプログラム
【課題】データサイズを抑えつつ高速な検索処理を実現するのに好適な転置インデックスの生成方法等を提供する。
【解決手段】生成装置１において、抽出部１０１は、文書データ３００のうちから「３文字の文字列であるトライグラム」を、当該文書データ３００中での出現位置と対応付けて、抽出する。分類部１０２は、抽出されたトライグラムのうち中央の文字が共通なトライグラムを、先頭および末尾の文字に基づいて、トライグラム群に分類する。生成部１０３は、分類されたトライグラム群のそれぞれに、当該トライグラム群に分類されたトライグラムに対応付けられた出現位置を対応付けて、転置インデックス９００を生成する。
【解決手段】生成装置１において、抽出部１０１は、文書データ３００のうちから「３文字の文字列であるトライグラム」を、当該文書データ３００中での出現位置と対応付けて、抽出する。分類部１０２は、抽出されたトライグラムのうち中央の文字が共通なトライグラムを、先頭および末尾の文字に基づいて、トライグラム群に分類する。生成部１０３は、分類されたトライグラム群のそれぞれに、当該トライグラム群に分類されたトライグラムに対応付けられた出現位置を対応付けて、転置インデックス９００を生成する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、Ｎグラム検索に関し、とくにデータサイズを抑えつつ高速な検索処理を実現するのに好適な転置インデックスの生成方法および生成装置、当該転置インデックスを用いた検索方法および検索装置、ならびにコンピュータプログラムに関する。
【背景技術】
【０００２】
文書の電子化の増大に伴い、これまでに蓄積されてきた大量の文書群から所望の文書を見つけ出す検索技術の重要性が高まっている。
【０００３】
大量の文書群を対象とした検索では、検索処理の高速化のため、検索対象となる文書群に含まれる単語等を索引単位として、索引ファイルを作成することが一般的である。あらかじめ作成された索引ファイル（以下、転置インデックスと呼称する）を検索時に用いることで、検索のたびに大量の文書群にアクセスする必要がなくなり、高速な検索処理が実現されるからである。
【０００４】
英語などの多くの言語においては、単語を索引単位として転置インデックスを作成することが一般的である。しかし、日本語の場合、スペース等によって単語の切れ目が明示的に示されないため、しばしば、Ｎグラムを索引単位とする方法が用いられる。Ｎグラムとは、連続するＮ文字からなる部分文字列のことである。Ｎグラムによる転置インデックスの作成は、単語を認識する必要がなく、文字列にのみ基づくため、日本語の文書を検索対象とした検索に適している。
【０００５】
このようなＮグラムを用いた検索では、検索処理の速度や転置インデックスのデータサイズは、索引単位として採用するＮグラムのＮの値によって変化する。例えば、非特許文献１には、異なるＮの値における検索処理の高速化の比較が記載されている。
【先行技術文献】
【非特許文献】
【０００６】
【非特許文献１】小川泰嗣，松田透，”ｎ−ｇｒａｍ索引を用いた効率的な文書検索法”，電子情報通信学会論文誌(D-I)，Vol.J82-D-I，No.1，pp.121-129，1999年1月
【発明の概要】
【発明が解決しようとする課題】
【０００７】
Ｎグラムを用いた検索では、転置インデックスの単位として採用するＮの値を大きくすると、原則として検索処理の速度は上がる。一方で、Ｎの値を大きくすると、文書から抽出されるＮグラムの種類が多くなるため、転置インデックスのデータサイズは増大する。そのため、検索処理の高速化と転置インデックスのデータサイズの抑制とは両立しにくかった。しかし、転置インデックスのデータサイズをなるべく抑えつつ、検索処理の高速化も実現したい、との要望がある。
【０００８】
本発明は、以上のような課題を解決するためのものであり、データサイズを抑えつつ高速な検索処理を実現するのに好適な転置インデックスの生成方法および生成装置、当該転置インデックスを用いた検索方法および検索装置、ならびに、コンピュータプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００９】
上記目的を達成するため、本発明にかかる転置インデックスの生成方法は、
文書データのうちから「３文字の文字列であるトライグラム」を、当該文書データ中での出現位置と対応付けて、抽出する抽出ステップと、
前記抽出されたトライグラムのうち中央の文字が共通なトライグラムを、先頭および末尾の文字に基づいて、トライグラム群に分類する分類ステップと、
前記分類されたトライグラム群のそれぞれに、当該トライグラム群に分類されたトライグラムに対応付けられた出現位置を対応付けて、転置インデックスを生成する生成ステップと、
を備えることを特徴とする。
【発明の効果】
【００１０】
本発明によれば、データサイズを抑えつつ高速な検索処理を実現するのに好適な転置インデックスの生成方法および生成装置、当該転置インデックスを用いた検索方法および検索装置、ならびに、コンピュータプログラムを提供することができる。
【図面の簡単な説明】
【００１１】
【図１】本発明の実施形態に係る転置インデックスの生成装置の概要構成を示す図である。
【図２】本発明の実施形態に係る転置インデックスの生成装置の物理構成を示す図である。
【図３】本発明の実施形態に係る文書データ構成を示す図である。
【図４】本発明の実施形態に係る生成装置の処理の流れを示すフローチャートである。
【図５】本発明の実施形態において、文書データから抽出されたトライグラムとその出現位置の例を示す図である。
【図６】本発明の実施形態において、トライグラムが統合トライグラム群に分類された様子を示す図である。
【図７】本発明の実施形態において、統合トライグラム群のトライグラムが中間トライグラム群に分類される様子を示す図である。
【図８】本発明の実施形態において、中間トライグラム群のトライグラムがトライグラム群に分類される様子を示す図である。
【図９】本発明の実施形態において、転置インデックスの構成をトライグラムの中央の文字ごとに２次元状に表した図である。
【図１０】本発明の実施形態に係る検索装置の概要構成を示す図である。
【図１１】本発明の実施形態に係る検索装置の物理構成を示す図である。
【図１２Ａ】本発明の実施形態に係る検索装置の処理の流れを示す第１のフローチャートである。
【図１２Ｂ】本発明の実施形態に係る検索装置の処理の流れを示す第２のフローチャートである。
【図１２Ｃ】本発明の実施形態に係る検索装置の処理の流れを示す第３のフローチャートである。
【図１３Ａ】本発明の実施形態に係る検索処理において、転置インデックスから出現位置が取得される様子を示す第１の図である。
【図１３Ｂ】本発明の実施形態に係る検索処理において、転置インデックスから出現位置が取得される様子を示す第２の図である。
【図１３Ｃ】本発明の実施形態に係る検索処理において、転置インデックスから出現位置が取得される様子を示す第３の図である。
【図１３Ｄ】本発明の実施形態に係る検索処理において、転置インデックスから出現位置が取得される様子を示す第４の図である。
【図１４】本発明に係る検索装置の構成概要について、別の例を示す図である。
【図１５】本発明に係る転置インデックスの構成について、別の例を示す図である。
【発明を実施するための形態】
【００１２】
以下、本発明の実施形態について、図面を参照して説明する。なお、以下に説明する実施形態は説明のためのものであり、本発明の範囲を制限するものではない。したがって、当業者であれば下記の各構成要素を均等なものに置換した実施形態を採用することが可能であるが、これらの実施形態も本発明の範囲に含まれる。また、以下の説明では、本発明の理解を容易にするため、重要でない公知の技術的事項の説明を適宜省略する。
【００１３】
まず、本実施形態に係る転置インデックスの生成装置１が実現される情報処理装置は、図１に示されるような構成をとる。すなわち、生成装置１は、制御部１００と、記憶部１１０と、入力部１２０と、出力部１３０と、通信部１４０と、を備える。一方、当該生成装置１は、物理的には図２に示されるように構成され、ＣＰＵ（Central Processing Unit）１５１と、ＲＯＭ（Read Only Memory）１５２と、ＲＡＭ（Random Access Memory）１５３と、ハードディスク１５４と、キーボード１５５と、モニタ１５６と、ＤＶＤ−ＲＯＭドライブ１５７と、通信装置１５８と、を備える。以下、図１および図２を参照して、生成装置１の構成要素の説明をする。
【００１４】
制御部１００は、生成装置１全体の動作を制御し、各構成要素と接続され、制御信号やデータをやりとりする。すなわち、制御部１００は、記憶部１１０、入力部１２０、出力部１３０、通信部１４０と接続され、これら各部の機能を活用しながら、転置インデックスの生成処理を実行する。
【００１５】
ここで制御部１００は、抽出部１０１と、分類部１０２と、生成部１０３と、を備える。これらの各部は、詳細には後述するように、記憶部１１０に記憶されている文書データ３００をもとにして、転置インデックス９００を生成する処理を実行する。
【００１６】
このような制御部１００（抽出部１０１、分類部１０２、生成部１０３）は、例えばＣＰＵ１５１によって構成される。ここでＣＰＵ１５１は、命令やデータを転送するための伝送経路であるシステムバスにより各構成要素と相互に接続され、ＲＯＭ１５２に記録されている生成装置１全体の動作制御に必要なコンピュータプログラムや各種データに従って動作する。そしてＣＰＵ１５１は、ＲＯＭ１５２から読み出したコンピュータプログラムやデータ、その他処理の進行に必要なデータを、ＲＡＭ１５３に一時的に記憶しながら、各種動作を制御する。このようにＣＰＵ１５１がＲＯＭ１５２やＲＡＭ１５３と協働することで、制御部１００は、生成装置１全体の動作を制御する。
【００１７】
記憶部１１０は、例えばハードディスク１５４のような大容量外部記憶装置によって構成され、制御部１００が転置インデックス９００を生成する処理のために必要な各種データ、具体的には後述する検索装置によって検索対象とされる文書データ３００等が、記憶される。また、記憶部１１０は、生成装置１の処理によって生成された転置インデックス９００も記憶する。
【００１８】
ここで、記憶部１１０にあらかじめ記憶される文書データ３００は、図３に示されるように、個々の文書データ３００ａ〜３００ｃ等から構成され、さらに文書データ３００ａ〜３００ｃ等はそれぞれ、「見出し語」と「説明文」とから構成される。すなわち、文書データ３００ａ〜３００ｃ等は、辞書を構成する構成単位であり、「見出し語」とは、当該辞書の見出しとなる１つの語句であり、１つの文書データ３００に対して１つの見出し語が対応付けられる。そして、「見出し語」には当該見出し語を説明する「説明文」が対応付けられ、これらを合わせて１つの文書データ３００を構成する。
【００１９】
図１および図２に戻って、記憶部１１０が記憶するこれらのデータは、例えば生成装置１のＤＶＤ−ＲＯＭドライブ１５７を介して、あるいは通信部１４０によって接続されるネットワーク１５０を介して、外部とやり取りされる。
【００２０】
入力部１２０は、例えばキーボード１５５のような入力装置によって構成され、ユーザからの入力を受け付ける。受け付けられた入力情報は、制御部１００へと供給される。本実施形態では、転置インデックス９００を生成するためのユーザからの命令を受け付ける。
【００２１】
出力部１３０は、例えばモニタ１５６のような表示装置によって構成され、制御部１００が処理を行った結果をユーザへ出力する。本実施形態では、抽出部１０１、分類部１０２、生成部１０３のそれぞれが行う転置インデックス９００の生成処理の経過や結果がモニタ１５６に表示される。これにより、ユーザは当該生成処理の経過や結果についての情報を得ることができる。
【００２２】
通信部１４０は、生成装置１をインターネット等のネットワーク１５０に接続し、制御部１００の制御のもと、ネットワーク１５０を介してデータをやり取りする。このような通信部１４０は、例えばモデム等の適宜の通信装置１５８によって構成される。
【００２３】
以上のように構成される生成装置１は、制御部１００の制御のもと、転置インデックス９００の生成処理を行う。具体的には、図４のフローチャートに示される手順で処理を実行する。
【００２４】
本処理は、ユーザからの転置インデックス９００を生成する旨の指示を、生成装置１の入力部１２０が受け付けることを契機として、開始される。すなわち、キーボード１５５を用いて、ユーザが転置インデックス９００を生成する旨を指示することで、本処理が開始する。
【００２５】
処理が開始されると、まず抽出部１０１が、記憶部１１０に記憶された文書データ３００からトライグラム（Ｎ＝３のＮグラム）を、その出現位置を対応付けて抽出する（ステップＳ４０１）。ここでＮグラムとは、Ｎ文字の文字列（Ｎは自然数）を意味し、Ｎ＝３のＮグラム（トライグラム）とは、３文字の文字列をいう。すなわち、抽出部１０１は、文書データ３００に含まれる見出し語や説明文を構成する文字列から、３文字の文字列（トライグラム）を抽出可能な数だけ抽出する。
【００２６】
一般的に、文字数がＸ文字の文字列からは、Ｘ−Ｎ＋１個のＮグラムが抽出されるため、Ｎ＝３の場合は、Ｘ−２個（Ｘ−３＋１個）のバイグラムが抽出される。例えば、「携帯電話」という４文字の文字列からは、「携帯電」「帯電話」という２個（４−２個）のトライグラムが抽出され、「ボールペン」という５文字の文字列からは、「ボール」「ールペ」「ルペン」という３個（５−２個）のトライグラムが抽出される。
【００２７】
このとき抽出部１０１は、それぞれに文書データ３００中での出現位置を対応付けつつ、トライグラムを抽出する。すなわち、抽出されたトライグラムが、抽出元の文書データ３００中の先頭文字から数えて何文字目に位置していたかの情報を、当該トライグラムに対応付けながら抽出する。
【００２８】
例えば、文書データ３００を構成する文字列が、「ボールペン」という５文字の文字列から始まっていたとした場合は、抽出されたトライグラムのうち、トライグラム「ボール」には１（文字目）、トライグラム「ールペ」には２（文字目）、トライグラム「ルペン」には３（文字目）、という出現位置を表す値が対応付けられる。ここで、文書データ３００中に同一のトライグラムが複数出現する場合には、当該トライグラムに複数の出現位置が対応付けられることになる。
【００２９】
出現位置の対応付け処理が行われると、具体的には図５に示されるように、文書データ３００から抽出された各トライグラムとその出現位置との対応関係が形成される。本図の対応関係からは、例えば「ボール」というトライグラムは、文書データ３００の先頭から１文字目、２２文字目、３３文字目、８７文字目、１２０文字目に出現し、また「リンゴ」というトライグラムは１９９文字目と２１９文字目に出現するということが分かる。
【００３０】
これらの抽出されたトライグラムやそれらの出現位置は、ＲＡＭ１５３等に一時的に保持される。
【００３１】
トライグラムが抽出されると、次に分類部１０２が、抽出されたトライグラムのうち、中央の文字が共通なトライグラムを統合トライグラム群としてまとめる（ステップＳ４０２）。すなわち、分類部１０２は、トライグラムの３文字の文字列のうち、中央の（２番目の）文字に着目し、同じ文字を中央の文字として有するトライグラムを１つの統合トライグラム群としてまとめる。
【００３２】
まとめられた統合トライグラム群は、例えば図６に示されるようになる。すなわち、「あ」を中央の文字として有するトライグラムが分類された統合トライグラム群、「の」を中央の文字として有するトライグラムが分類された統合トライグラム群、「ン」を中央の文字として有するトライグラムが分類された統合トライグラム群、「山」を中央の文字として有するトライグラムが分類された統合トライグラム群・・・というように、文書データ３００から抽出されたトライグラムの中央の文字の種類の数だけ、統合トライグラム群を作成する。
【００３３】
統合トライグラム群にトライグラムがまとめられると、次に分類部１０２は、統合トライグラム群ごとにトライグラムを先頭の文字順に並べる（ステップＳ４０３）。ここで文字順とは、いわゆる辞書順であり、五十音順やアルファベット順等のような文字列の並び順をいう。日本語のように複数の文字種がある場合にはひらがな、カタカナ、漢字、アルファベット・・・といったように文字種に順序を定めてもよい。すなわち、中央の文字が共通なトライグラムについて、先頭の文字に着目し、このような辞書順に並べる。
【００３４】
具体的には図７に示すように、分類部１０２は、例えば文字「の」を共通な中央の文字とする統合トライグラム群にまとめられたトライグラムについて、それぞれの先頭の文字に着目し、先頭の文字が「あ」「い」・・・「お」・・・「ん」・・・「意」・・・といった順になるように並べる。このようなトライグラムを先頭の文字について辞書順に並べる処理を、すべての統合トライグラム群に対して実行する。
【００３５】
図４のフローチャートに戻って、次に分類部１０２は、並べられたトライグラムを、出現位置が所定の個数を超えないように、並び順に中間トライグラム群に分類する（ステップＳ４０４）。すなわち分類部１０２は、先頭の文字順に並べられたトライグラムについて、最初のトライグラムから並び順に１つ以上のトライグラムをひとまとめにし、中間トライグラム群としてまとめていく。
【００３６】
具体的に、図７のように「の」を共通な中央の文字とする統合トライグラム群の例では、先頭の文字順に並べられたトライグラムについて、最初に並べられたトライグラム「あのあ」から順に、「あのい」、「あのう」・・・「おの輪」までを１つの中間トライグラム群Ａとしてまとめる。そして、次のトライグラム「かのあ」から、並べられた順に「けの和」まで、中間トライグラム群Ｂとしてまとめる。このような処理を繰り返して、中間トライグラム群Ｘ、中間トライグラム群Ｙ・・・というように、並べられた最後のトライグラムまで、中間トライグラム群としてまとめていく。
【００３７】
なおこのとき、分類が複雑になることを防ぐため、分類部１０２は、先頭の文字が同一のトライグラムは同一の中間トライグラム群にまとめられるようにする。例えば、「かのあ」と「かのわ」という２つのトライグラムは、同一の先頭の文字「か」を有するため、異なる中間トライグラム群に分けて分類されるのではなく、トライグラム「かのあ」が分類された中間トライグラム群には必ずトライグラム「かのわ」も分類されるようにする。
【００３８】
さらにこのとき、１つの中間トライグラム群にまとめられるトライグラムの個数が、まとめられたトライグラムに対応付けられた出現位置の個数の和が所定の個数を超えないように、分類部１０２はトライグラムを分類する。具体的に説明すると、分類部１０２は、各トライグラムに対応付けられた出現位置の個数に着目し、最初のトライグラムから順に中間トライグラム群に分類していく際、分類対象となっているトライグラムの出現位置の個数と、分類候補となっている中間トライグラム群にすでに分類されたトライグラムの出現位置の個数との和を算出し、あらかじめ用意された所定の個数と比較する。所定の個数を超えていなければ、当該分類候補となっている中間トライグラム群に分類対象のトライグラムを分類する。一方で、所定の個数を超えていれば、異なる中間トライグラム群に分類対象のトライグラムを分類する。
【００３９】
このように、分類部１０２が各中間トライグラム群に分類されるトライグラムの出現位置の個数の和が所定の個数を超えないように分類することで、各中間トライグラム群の出現位置の個数をなるべく均一にすることができる。その結果、出現位置が効率的に格納された転置インデックス９００を生成することへとつながる。
【００４０】
再び図４のフローチャートに戻って、さらに分類部１０２は、作成された中間トライグラム群ごとに、トライグラムを末尾の文字順に並べる（ステップＳ４０５）。すなわち分類部１０２は、トライグラムの先頭の文字に基づいて分類された中間トライグラム群のそれぞれにおいて、今度はトライグラムの末尾の文字に着目し、末尾の文字の辞書順に並べる。
【００４１】
具体的には図８に示すように、分類部１０２は、例えば文字「の」を共通な中央の文字とし、先頭の文字が「あ」〜「お」のトライグラムが分類された中間トライグラム群Ａにおいて、トライグラムの末尾の文字に着目し、末尾の文字が「あ」「い」「う」・・・「り」・・・「輪」・・・といった順になるように並べる。このようなトライグラムを末尾の文字について辞書順に並べる処理を、すべての中間トライグラム群に対して実行する。
【００４２】
図４のフローチャートに戻って、次に分類部１０２は、末尾の文字順に並べられたトライグラムを、出現位置が所定の個数を超えないように、並び順にトライグラム群に分類する（ステップＳ４０６）。すなわち分類部１０２は、末尾の文字順に並べられたトライグラムについて、最初のトライグラムから並び順に１つ以上のトライグラムをひとまとめにし、トライグラム群としてまとめていく。
【００４３】
具体的に、図８のような中間トライグラム群Ａの例では、末尾の文字順に並べられたトライグラムについて、最初に並べられたトライグラム「あのあ」から順に、「いのあ」・・・「おのあ」「あのい」・・・「おのう」までを１つのトライグラム群ＡＡとしてまとめる。そして、次のトライグラム「あのえ」から、並べられた順に「おのく」まで、トライグラム群ＡＢとしてまとめる。このような処理を繰り返して、トライグラム群ＡＰ、トライグラム群ＡＱ・・・というように、並べられた最後のトライグラムまで、トライグラム群としてまとめていく。
【００４４】
なおこのとき、上記中間トライグラム群への分類と同様に、分類が複雑になることを防ぐため、分類部１０２は、末尾の文字が同一のトライグラムは同一のトライグラム群にまとめられるようにする。例えば、「かのさ」と「このさ」という２つのトライグラムは、同一の末尾の文字「さ」を有するため、異なるトライグラム群に分けて分類されるのではなく、トライグラム「かのさ」が分類されたトライグラム群には必ずトライグラム「このさ」も分類されるようにする。
【００４５】
さらにこのとき、上記中間トライグラム群への分類と同様に、トライグラム群の出現位置の個数をなるべく均一にするため、１つのトライグラム群にまとめられるトライグラムの個数が、まとめられたトライグラムに対応付けられた出現位置の個数の和が所定の個数を超えないように、分類部１０２はトライグラムを分類する。具体的に説明すると、分類部１０２は、各トライグラムに対応付けられた出現位置の個数に着目し、各中間トライグラム群において最初のトライグラムから順にトライグラム群に分類していく際、分類対象となっているトライグラムの出現位置の個数と、分類候補となっているトライグラム群にすでに分類されたトライグラムの出現位置の個数との和を算出し、あらかじめ用意された所定の個数と比較する。所定の個数を超えていなければ、当該分類候補となっているトライグラム群に分類対象のトライグラムを分類する。一方で、所定の個数を超えていれば、異なるトライグラム群に分類対象のトライグラムを分類する。
【００４６】
図４のフローチャートに戻って、最後に生成装置１の生成部１０３が、各トライグラム群に、そこに分類されたトライグラムの出現位置を対応付けて、転置インデックス９００を生成する（ステップＳ４０７）。すなわち、生成部１０３は、トライグラム群と、そこに分類された全てのトライグラムに上記ステップＳ４０１にて対応付けられた文書データ３００中での出現位置と、を構成要素として、転置インデックス９００を生成する。その後、生成された転置インデックス９００は、ハードディスク１５４のような記憶部１１０に記憶され、本フローチャートの処理は終了する。
【００４７】
ここで生成される転置インデックス９００は、図９に示されるような２次元の表状に表すことができる。すなわち、生成される転置インデックス９００の構成は、トライグラムの中央の文字ごとに、先頭の２文字を縦軸に、末尾の２文字を横軸にとり、出現位置を要素とする２次元状の表として表される。１つの表全体は、中央の文字を共通とするトライグラム全体、すなわち統合トライグラム群１つに相当するものである。
【００４８】
ここで本図における縦軸の構成単位は、中央の文字が共通のトライグラムを先頭の文字に基づいて中間トライグラム群に分類した際の分類の単位であり、横軸の構成単位は、中間トライグラム群に分類されたトライグラムを末尾の文字に基づいてトライグラム群に分類した際の分類の単位である。そのため、１つのセルは１つのトライグラム群に相当し、１つのセルには、対応するトライグラム群に分類されたトライグラムに対応付けられた全ての出現位置が格納される。
【００４９】
具体的に説明すると、表上で最も左上に配置されたセルは、先頭の２文字が「あの」〜「おの」であり、末尾の２文字が「のあ」〜「のう」であるトライグラムが分類されたトライグラム群に相当する。例えば「いのう」や「おのあ」というトライグラムがここに分類される。そして、当該トライグラム群に分類されたいずれかのトライグラムは、本図の当該セルに示されるように、文書データ３００中の先頭から１２文字目、４９文字目、９２３文字目、１１１０４文字目、１１２９３文字目・・・という位置に出現する。一方で別の例を挙げると、例えば「しのひ」や「たのへ」といったトライグラムは、先頭の２文字が「さの」〜「ちの」で末尾の２文字が「のひ」〜「のほ」に相当するトライグラムである。本図によれば、これらのうちいずれかのトライグラムが、文書データ３００中の先頭から６５８６文字目、５９８９９文字目、７２４９５文字目・・・の位置に出現する。
【００５０】
生成装置１が生成する転置インデックス９００は、このようなトライグラム群とその出現位置との２次元状の対応関係を、トライグラムの中央の文字のそれぞれについて備え、後述する検索処理において用いられる。
【００５１】
以上のような構成により、本実施形態の生成装置１は、文書データ３００から抽出されたトライグラムについて、中央の文字が共通なトライグラムをまとめ、まとめられたトライグラムをさらに先頭および末尾の文字に基づいてトライグラム群に分類する。そして、トライグラム群とそれぞれに分類されたトライグラムの出現位置とを対応付けて、転置インデックス９００を生成する。その結果、トライグラムを単独で単位としたものに比べてデータサイズが抑えられ、かつ後述する検索装置２において高速な検索処理を実現することができる転置インデックス９００を生成することができる。
【００５２】
その際、生成装置１は、トライグラム群に分類されるトライグラムの出現位置の個数の和が所定の上限値を超えないようにトライグラムを分類していく。これにより、各トライグラム群に対応付けられる出現位置の個数がなるべく同じ個数に均一化することができ、出現位置が効率的に格納された転置インデックス９００を生成することができる。
【００５３】
本発明では、上記のような転置インデックス９００の生成装置１、およびそれを用いた転置インデックス９００の生成方法に加え、当該生成された転置インデックス９００を用いて、文書データ３００を検索対象とした検索を行う検索装置２、およびそれを用いた検索方法を提供する。
【００５４】
ここで検索装置は、通常は上記転置インデックスの生成装置１とは異なる情報処理装置によって実現される。具体的に本実施形態では、検索装置として、電子辞書等の機能を備える小型の情報処理装置を想定して説明する。すなわち、検索対象である文書データ３００についての転置インデックス９００の生成については、あらかじめ上記図１および図２に示されたような一般的な情報処理装置において行われ、一方で当該生成された転置インデックス９００を用いた文書データ３００の検索については、生成装置１とは異なる情報処理装置、すなわち電子辞書等の小型の情報処理装置において実現される。
【００５５】
このような検索装置２として、その構成は図１０に示されるようなものになる。すなわち検索装置２は、制御部２００と、記憶部２１０と、入力部２２０と、出力部２３０と、を備える。一方、当該検索装置２は、物理的には図１１に示されるように構成され、ＣＰＵ２５１と、ＲＯＭ２５２と、ＲＡＭ２５３と、キーボード２５５と、モニタ２５６と、を備える。以下、図１０および図１１を参照して、検索装置２の構成要素の説明をする。
【００５６】
制御部２００は、検索装置２全体の動作を制御し、各構成要素と接続され、制御信号やデータをやりとりする。すなわち、制御部２００は、記憶部２１０、入力部２２０、出力部２３０と接続され、これら各部の機能を活用しながら、検索処理を実行する。
【００５７】
ここで制御部２００は、取得部２０１と、特定部２０２と、を備える。これらの各部は、詳細には後述するように、記憶部２１０に記憶されている転置インデックス９００を用いて、文書データ３００のうちから検索文字列が出現する位置を特定する処理を実行する。
【００５８】
このような制御部２００（取得部２０１、特定部２０２）は、例えばＣＰＵ２５１によって構成される。ここでＣＰＵ２５１は、基本的には生成装置１におけるＣＰＵ１５１と同様、命令やデータを転送するための伝送経路であるシステムバスにより各構成要素と相互に接続され、ＲＯＭ２５２に記録されている検索装置２全体の動作制御に必要なコンピュータプログラムや各種データに従って動作し、さらにＲＯＭ２５２から読み出したコンピュータプログラムやデータ、その他処理の進行に必要なデータを、ＲＡＭ２５３に一時的に記憶しながら、各種動作を制御する。このようにＣＰＵ２５１がＲＯＭ２５２やＲＡＭ２５３と協働することで、制御部２００は、検索装置２全体の動作を制御する。
【００５９】
記憶部２１０は、例えば検索装置２内に備えられたＲＯＭ２５２のような読出し専用の記憶媒体によって構成され、制御部２００が検索処理に必要な各種データを記憶する。具体的にここでは、検索対象とされる文書データ３００、および転置インデックス９００が記憶される。
【００６０】
これら文書データ３００は、上記生成装置１の記憶部１１０に記憶された文書データ３００と同一のものであり、また転置インデックス９００は、上記生成装置１が、これら文書データ３００をもとにして生成した転置インデックス９００と同一のものである。
【００６１】
入力部２２０は、例えばキーボード２５５のような入力装置によって構成され、ユーザからの入力を受け付ける。具体的にここでは、ユーザからの検索語を受け付ける。受け付けられた検索語は、制御部２００の取得部２０１へと供給され、当該検索語の文字列の文書データ３００における出現位置を検索する処理に用いられる。
【００６２】
出力部２３０は、例えばモニタ２５６のような表示装置によって構成され、制御部２００が処理を行った結果をユーザへ出力する。具体的にここでは、ユーザが入力した検索語の文書データ３００における出現位置を、検索結果としてモニタ２５６に表示することで、当該ユーザへと出力する。これにより、ユーザは、自身が入力した検索語の出現位置を出力結果として取得し、種々に利用することができるようになる。
【００６３】
なお、入力部２２０と出力部２３０は、タッチパネル等のような入力装置と出力装置が組み合わされた装置によって構成されてもよい。この場合には、タッチパネルに内蔵されたタッチセンサ等からなる位置入力装置が入力部２２０を、液晶ディスプレイ等からなる表示装置が出力部２３０を、それぞれ構成する。
【００６４】
以上のように構成される検索装置２は、制御部２００の制御のもと、検索処理を行う。具体的には、図１２Ａ〜図１２Ｃのフローチャートに示される手順で処理を実行する。
【００６５】
本処理は、ユーザから入力された検索語を、検索装置２の入力部２２０が受け付けることを契機として、開始される。すなわち、キーボード２５５を用いて、ユーザが所望の検索語を入力し、検索する旨を指示することで、本処理が開始する。
【００６６】
まず図１２Ａのフローチャートにおいて、検索処理が開始されると、まず取得部２０１が、入力された検索語の文字列（検索文字列）の先頭の文字に注目する（ステップＳ１２０１）。例えば、ユーザが「しすてむ」という検索語を入力した場合、取得部２０１は、先頭の文字「し」に注目する。あるいは、ユーザが「山」という１文字の検索語を入力した場合には、取得部２０１は、当該１文字「山」を先頭の文字として注目する。
【００６７】
先頭の文字が注目されると、次に取得部２０１は、その文字を中央の文字とするトライグラムが分類された全てのトライグラム群に注目する（ステップＳ１２０２）。すなわち取得部２０１は、記憶部２１０に記憶されている転置インデックス９００にアクセスし、その中に格納されているトライグラム群のうち、注目した文字を中央の文字とするトライグラムが分類された全てのトライグラム群（上記図９における１つの表全体に対応する全てのトライグラム群に相当）に注目する。上記の例では、注目した先頭の文字「し」や「山」を中央の文字とするトライグラムが分類された全てのトライグラム群に注目する。
【００６８】
ここで取得部２０１は、検索文字列が１文字か否かを判定する（ステップＳ１２０３）。例えばユーザが「山」という検索語を入力したとき等のように、検索文字列が１文字の場合は（ステップＳ１２０３；ＹＥＳ）、検索語が２文字以上の場合とは異なるフローへ移行し、まず検索装置２の特定部２０２が、注目したトライグラム群があるか否かを判定する（ステップＳ１２０４）。すなわち、上記ステップＳ１２０２にて注目した、１文字の検索語（例えば「山」）を中央の文字とするトライグラムが分類されたトライグラム群が１つでも存在するか否かを判定する。
【００６９】
１文字の検索語を中央の文字とするトライグラム群がない場合（ステップＳ１２０４；ＮＯ）、特定部２０２は、「該当箇所無し」を出力し（ステップＳ１２０５）、検索処理を終了する。文書データ３００のいずれかの位置に当該１文字の検索語があるならば、その１文字を中央の文字とするトライグラムが分類されたトライグラム群があるはずであり、トライグラム群がないということは、文書データ３００中に入力された１文字の検索語がないということになるからである。そのため、特定部２０２は、出力部２３０を介してモニタ２５６に「該当箇所無し」という文字を表示する等により、ユーザへその旨を出力する。
【００７０】
一方、１文字の検索語を中央の文字とするトライグラム群がある場合（ステップＳ１２０４；ＹＥＳ）、特定部２０２は、該当するトライグラム群の全ての出現位置に１を加算して出力し（ステップＳ１２０６）、検索処理を終了する。後述する２文字以上の検索語の場合と異なり、検索語が１文字の場合には、注目したトライグラム群のトライグラムは当該１文字の検索語をその中央の文字として必ず含んでいるため、トライグラム群の出現位置に１を加算した位置（すなわち対応するトライグラムの２文字目）には必ず当該１文字の検索語が出現するからである。そのため、特定部２０２は、出力部２３０を介してモニタ２５６に表示する等により、該当するトライグラム群の全ての出現位置に１を加算した位置を、ユーザへ出力する。
【００７１】
また一方で、入力された検索語の文字列が１文字でない場合（ステップＳ１２０３；ＮＯ）は、検索装置２の処理はステップＳ１２０７へと移行し、取得部２０１が、注目したトライグラム群のうち後の文字を末尾の文字とするトライグラムが分類されたトライグラム群の出現位置を全て取得する（ステップＳ１２０７）。すなわちここでは、取得部２０１は、上記ステップＳ１２０２にて注目した検索文字列の先頭の文字を中心の文字とするトライグラムが分類された全てのトライグラム群について、さらに検索文字列の後の文字（先頭から２文字目）を末尾の文字とするトライグラムが分類されたトライグラム群にまで絞り込みを行う。そして、取得部２０１は、絞り込んだトライグラム群について、転置インデックス９００に格納されている全ての出現位置を取得する。
【００７２】
具体的な例として、ユーザが「しすてむ」という検索語を入力した場合について説明する。この場合、上記ステップＳ１２０２にて注目したトライグラム群は、当該４文字の検索語の先頭の文字「し」を中心の文字とするトライグラムが分類された全てのトライグラム群であって、図１３Ａに表された文字「し」についての２次元状の表に配置されたトライグラム群全体に相当する。ここで本図における２次元状の表は、上記図９と同様に、転置インデックス９００の構成をトライグラムの中央の文字ごとに２次元状に表したものである。
【００７３】
そして、上記ステップＳ１２０７にて絞り込んだトライグラム群は、当該検索語「しすてむ」の２番目の文字「す」を末尾の文字とするトライグラムが分類されたトライグラム群であって、図１３Ａにおける太線で囲われた部分のトライグラム群に相当する。すなわち、絞り込むべきトライグラム群は、「しす」という２文字を末尾の２文字とするトライグラム「＊しす」（＊はどの文字種でもよい）が分類されたトライグラム群であるので、図１３Ａにおける「しさ」〜「しせ」の欄の縦一列の全てのセルのトライグラム群に相当することになる。ステップＳ１２０７では、取得部２０１が、これら縦一列の全てのセル内の出現位置（１９１文字目、４４９文字目、６５４５文字目、１１０９５文字目・・・、３２１文字目、１０８８文字目・・・等）を取得する。
【００７４】
図１２Ａのフローチャートに戻って、取得部２０１が転置インデックス９００から出現位置を取得すると、次に取得部２０１が、出現位置があるか否かを判定する（ステップＳ１２０８）。すなわち、取得した出現位置がそもそも１つでも存在するか否かを判定する。出現位置がない場合は（ステップＳ１２０８；ＮＯ）、検索対象の文書データ３００中に入力された検索文字列が存在しないということを意味するため、特定部２０２が、「該当箇所無し」を出力し（ステップＳ１２０５）、検索処理を終了する。すなわち特定部２０２は、出力部２３０を介してモニタ２５６に「該当箇所無し」という文字を表示する等により、ユーザへその旨を出力する。
【００７５】
一方、出現位置が１つでも存在する場合は（ステップＳ１２０８；ＹＥＳ）、特定部２０２が、その出現位置を保持する（ステップＳ１２０９）。すなわち、転置インデックス９００から取得した全ての出現位置を、ＲＡＭ２５３等に一時的に保持する。その後、検索処理は図１２Ｂのフローチャートへ移行する。
【００７６】
検索処理が図１２Ｂのフローチャートへ移行すると、次に取得部２０１は、検索文字列の次の文字に注目し（ステップＳ１２１０）、その文字を中央の文字とするトライグラムが分類された全てのトライグラム群に注目する（ステップＳ１２１１）。具体的にユーザが「しすてむ」という４文字の検索語を入力した場合では、取得部２０１は、先頭の文字の次の文字、すなわち２文字目の文字「す」に注目する。そして、転置インデックス９００内に格納された当該文字「す」を中心の文字とするトライグラムが分類された全てのトライグラム群に注目する。ここで注目するトライグラム群は、図１３Ｂに表された文字「す」についての２次元状の表に配置されたトライグラム群全体に相当する。
【００７７】
図１２Ｂのフローチャートにおいて、さらに取得部２０１は、検索文字列の注目した文字に対して、後の文字があるか否かを判定する（ステップＳ１２１２）。上記検索語「しすてむ」での例では、注目した文字「す」の後にさらに「て」と「む」の文字が存在しているため、取得部２０１は後の文字があると判定する。
【００７８】
後の文字があると判定すると（ステップＳ１２１２；ＹＥＳ）、取得部２０１は、注目したトライグラム群のうち、前の文字を先頭の文字とし、後の文字を末尾の文字とするトライグラムが分類されたトライグラム群の出現位置を全て取得する（ステップＳ１２１３）。すなわち、上記検索語「しすてむ」での例では、注目した２文字目の文字「す」を中央の文字、前の文字「し」を先頭の文字、後の文字「て」を末尾の文字とするトライグラム「しすて」が分類されたトライグラム群の出現位置を全て、取得部２０１が取得する。
【００７９】
図１３Ｂに表された文字「す」についての２次元状の表では、当該「しすて」というトライグラムは、先頭の２文字（縦軸）が「しす」〜「つす」、末尾の２文字（横軸）が「すそ」〜「すと」の範囲に該当するものであるため、当該トライグラムが分類されたトライグラム群は、太線で囲われた１つのセルに相当するものとなる。従って、取得部２０１は、当該セル内の出現位置（５２３文字目、８７６文字目・・・等）を全て取得する。
【００８０】
図１２Ｂのフローチャートに戻って、出現位置を取得すると、次に特定部２０２が、保持された出現位置と連続する出現位置があるか否かを判定する（ステップＳ１２１４）。すなわち特定部２０２は、上記ステップＳ１２０９にて保持した検索語の先頭の文字についてのトライグラム群の出現位置と、取得した検索語の２番目の文字についてのトライグラム群の出現位置とを比較して、保持した出現位置の値に１だけ加算した値の出現位置があるか否かを判定する。保持した出現位置と取得した出現位置の中に、検索語の文字列を構成するトライグラムの出現位置が含まれているならば、それらは検索語の文字列を構成するように連続しているはずだからである。
【００８１】
そのため、連続する出現位置がなければ（ステップＳ１２１４；ＮＯ）、検索対象の文書データ３００には検索語が含まれていないということになり、特定部２０２は、「該当箇所無し」を出力し（ステップＳ１２１５）、検索処理を終了する。すなわち特定部２０２は、出力部２３０を介してモニタ２５６に「該当箇所無し」という文字を表示する等により、ユーザへその旨を出力する。
【００８２】
一方、連続する出現位置があれば（ステップＳ１２１４；ＹＥＳ）、特定部２０２は、保持する出現位置を連続する出現位置と入れ替える（ステップＳ１２１６）。すなわち、特定部２０２は、検索文字列の２番目の文字についてのトライグラム群の出現位置のうち、連続すると判定した出現位置を、それまで保持していた先頭の文字についてのトライグラム群の出現位置と入れ替えて、ＲＡＭ２５３等に保持する。
【００８３】
その後、検索処理は再びステップＳ１２１０へと戻る。すなわち、検索装置２は、検索文字列の次の文字に注目し、当該注目した文字について、ステップＳ１２１１以降の処理を繰り返す。上記検索語「しすてむ」での例では、取得部２０１は、３文字目の文字「て」に注目し、その前後の文字とともに構成するトライグラム「すてむ」が分類されたトライグラム群の出現位置を、転置インデックス９００から取得する。
【００８４】
具体的に図１３Ｃに表された文字「て」についての２次元状の表では、当該「すてむ」というトライグラムは、先頭の２文字（縦軸）が「さて」〜「ちて」、末尾の２文字（横軸）が「てま」〜「てめ」の範囲に該当するものであるため、当該トライグラムが分類されたトライグラム群は、太線で囲われたセルに相当するものとなる。従って、取得部２０１は、当該セル内の出現位置（３１文字目、５１９文字目・・・等）を全て取得する。
【００８５】
その後同様に、特定部２０２が出現位置の連続性を判定し（ステップＳ１２１４）、連続する出現位置を保持して（ステップＳ１２１６）、再び検索処理はステップＳ１２１０へと戻る。そして、検索文字列の次の文字、すなわち検索語「しすてむ」の最後の文字「む」に注目し（ステップＳ１２１０）、当該文字「む」についてのトライグラム群に注目する（ステップＳ１２１１）。注目した文字が検索語の最後の文字の場合には、その後の文字はないため（ステップＳ１２１２；ＮＯ）、検索処理は図１２Ｃのフローチャートへと移行する。
【００８６】
検索処理が図１２Ｃのフローチャートへ移行すると、次に取得部２０１は、注目したトライグラム群のうち、前の文字を先頭の文字とするトライグラムが分類されたトライグラム群の出現位置を全て取得する（ステップＳ１２１７）。すなわち、上記検索語「しすてむ」での例では、注目した最後の文字「む」を中央の文字、前の文字「て」を先頭の文字とするトライグラム「てむ＊」（＊はどの文字種でもよい）が分類されたトライグラム群の出現位置を全て、取得部２０１が取得する。
【００８７】
図１３Ｄに表された文字「む」についての２次元状の表では、当該「てむ＊」というトライグラムは、先頭の２文字（縦軸）が「たむ」〜「とむ」の範囲に該当するものであるため、当該トライグラムが分類されたトライグラム群は、太線で囲われた横一列のセルに相当するものとなる。従って、取得部２０１は、当該セル内の出現位置（２６１文字目、６９０文字目、１５６５文字目、３２８２文字目・・・、６７文字目、２９８文字目・・・等）を全て取得する。
【００８８】
図１２Ｃのフローチャートに戻って、最後の文字についての出現位置を取得すると、上記ステップＳ１２１４と同様に、特定部２０２が、保持された出現位置と連続する出現位置があるか否かを判定する（ステップＳ１２１８）。取得された出現位置が入力された検索語の文字列を構成するものであるか否かを判定するためである。
【００８９】
連続する出現位置がなければ（ステップＳ１２１８；ＮＯ）、検索対象の文書データ３００には検索語が含まれていないということになるため、特定部２０２は、「該当箇所無し」を出力し（ステップＳ１２１９）、検索処理を終了する。すなわち特定部２０２は、出力部２３０を介してモニタ２５６に「該当箇所無し」という文字を表示する等により、ユーザへその旨を出力する。
【００９０】
一方、連続する出現位置があれば（ステップＳ１２１８；ＹＥＳ）、入力された検索語が文書データ３００中に含まれているということになる。そのため、特定部２０２は、その出現位置から検索文字列の先頭文字位置を計算し、出力する（ステップＳ１２２０）。すなわち特定部２０２は、連続すると判定した出現位置に対応する検索文字列の先頭文字位置を計算し、それを検索結果としてユーザへ出力する。連続する出現位置が複数存在した場合は、特定部２０２は、原則的には全てについて検索文字列の先頭文字位置を計算し、出力する。その後、本フローチャートにて示した検索装置２の処理は終了する。
【００９１】
このとき出力結果は、出力部２３０を介しモニタ２５６に表示される等によって、ユーザへと出力される。ユーザは、当該出力結果により、記憶部２１０に記憶された文書データ３００中において、自身が入力した検索語が出現する位置を取得することができ、種々に利用することができるようになる。
【００９２】
以上のような構成により、本実施形態の検索装置２は、所望の検索文字列に対して、それを構成する文字ごとに前後の文字とあわせて転置インデックス９００から出現位置を取得し、出現位置の連続性を判定することで、当該検索文字列が文書データ３００中のどこに出現するのかを特定する。ここで用いられる転置インデックス９００は、トライグラムがその文字列に基づいて分類されたトライグラム群を単位として構成されている。そのため、検索装置２は、トライグラムを単独で単位としたものに比べ、搭載される転置インデックス９００のデータサイズを抑え、検索処理の速度をなるべく低下することなく検索を実行できる。
【００９３】
これは、例えば電子辞書や携帯電話等のような小型の電子機器のような使用できるデータ容量が限られた環境においてはとくに、転置インデックス９００のデータサイズを抑制しつつ高速な検索処理を実現する上で効果的である。
【００９４】
なお、上記実施形態は一例であり、本発明の適用範囲はこれに限られない。すなわち、種々の応用が可能であり、あらゆる実施の形態が本発明の範囲に含まれる。
【００９５】
例えば、上記実施形態では、検索装置２は、ＲＯＭ２５２のような記憶部２１０内に文書データ３００等を記憶した。しかしこれに限られず、検索装置２は、ハードディスク等の大容量記憶装置やＤＶＤ−ＲＯＭドライブを備え、文書データ３００等がハードディスクやＤＶＤ−ＲＯＭ等に記憶されるようにしてもよい。あるいは、検索装置２は、ネットワークに接続され、文書データ３００等がネットワーク上に存在するようにしてもよい。
【００９６】
また、上記実施形態では、検索装置２は、ユーザが検索語を入力する入力部２２０や検索結果を出力する出力部２３０は、制御部２００や記憶部２１０と同一の装置内に存在した。しかしこれに限られず、入力部２２０と出力部２３０は、検索装置２の外部にあってもよい。すなわち、例えば図１４に示すように、検索装置２は入力部２２０と出力部２３０を備えず、これらを備える端末装置３とネットワーク１５０を介して接続されるようにし、オンライン型の電子辞書のような情報機器として構成するようにしてもよい。
【００９７】
このとき、検索装置２と端末装置３は、それぞれが備える通信部２４０ａ，２４０ｂにより、ネットワーク１５０を介して互いにデータを通信しあう。すなわち、端末装置３のユーザが入力した検索語は、検索装置２へと送信され、制御部２００により検索処理が実行される。その後、検索結果の情報が再び端末装置３へと送信され、端末装置３のユーザへと出力される。このような構成をとることで、検索装置２内の文書データ３００等を一括して管理して複数のユーザに利用できるようになり、またユーザ側の端末装置３は、文書データ３００等を保持する必要がないため、データサイズを抑えることができるといった利点がある。
【００９８】
また、上記実施形態では、検索装置２として電子辞書のような小型の情報処理装置を想定して説明した。しかしこれに限られず、検索装置２は、ビジネス用・家庭用の一般的なコンピュータ装置や、携帯電話等の他の情報機器であってもよい。また、電子辞書における検索に限られず、種々の電子データを検索するものであってもよい。例えば、一般的なコンピュータ装置において、ハードディスク等の大容量記憶装置やＤＶＤ−ＲＯＭ等に記憶された電子ファイルのうちから、所望の検索語を含む電子ファイルを検索するものであってもよい。あるいは、ネットワークと接続され、ネットワーク上に存在するウェブページを検索するものであってもよい。
【００９９】
また、生成装置１について、上記実施形態での生成装置１は、ハードディスク１５４のような記憶部１１０に記憶されている文書データ３００をもとにして転置インデックス９００を生成し、当該生成された転置インデックス９００を記憶部１１０に記憶した。しかし、これら文書データ３００は、生成装置１内に備えられた記憶部１１０に記憶されることに限られず、通信部１４０を介して接続されるネットワーク１５０上に存在していてもよいし、あるいはＤＶＤ−ＲＯＭドライブ１５７に搭載されるＤＶＤ−ＲＯＭ内に記憶されていてもよい。
【０１００】
また、上記実施形態では、文書データ３００は、「見出し語」と「説明文」とから構成された。しかしこれらに限られず、様々な要素から構成されてもよい。例えば、「見出し語」を説明するための図や表を有するものであってもよい。あるいは、辞書における検索以外の一般的な電子ファイル等の検索では、このような「見出し語」と「説明文」といった構成要素に限らず、文書データ３００は様々な形式で文字列データを有していてもよい。
【０１０１】
また、上記実施形態では、分類部１０２がトライグラムを中間トライグラム群およびトライグラム群に分類する際、１つの中間トライグラム群およびトライグラム群に分類されるトライグラムに対応付けられた出現位置の個数の和が所定の個数を超えないように分類した。しかし出現位置の個数ではなく、文字種の個数に着目して分類してもよい。すなわち、分類部１０２は、
（ａ）共通な中央の文字を有するトライグラムがまとめられた統合トライグラム群ごとに、トライグラムを先頭の文字順に並べ、１つの中間トライグラム群に分類されるトライグラムの先頭の文字種の個数が所定の個数を超えないように、トライグラムを並び順に中間トライグラム群に分類し、
（ｂ）さらに中間トライグラム群ごとに、トライグラムを末尾の文字順に並べ、１つのトライグラム群に分類されるトライグラムの末尾の文字種の個数が所定の個数を超えないように、トライグラムを並び順にトライグラム群に分類してもよい。
【０１０２】
具体的に、１つの中間トライグラム群およびトライグラム群に分類されるトライグラムの先頭および末尾の文字種の個数を５種類とした場合について説明する。このとき、例えば文字「の」を中央の文字とするトライグラムについて、分類部１０２は、５種類の先頭の文字「あ」〜「お」を有するトライグラムを最初の中間トライグラム群としてまとめ、その後「か」〜「こ」、「さ」〜「そ」・・・というように、先頭の文字について５種類ずつ中間トライグラム群にまとめていく。さらに分類部１０２は、中間トライグラム群ごとに、５種類の末尾の文字「あ」〜「お」を有するトライグラムを最初のトライグラム群としてまとめ、その後「か」〜「こ」、「さ」〜「そ」・・・というように、末尾の文字について５種類ずつトライグラム群にまとめていく。
【０１０３】
その結果、生成される転置インデックス９００について、例えば文字「の」についてのトライグラム群と出現位置との対応関係を２次元状に表すと、図１５のようになる。すなわち、当該２次元状の表の縦軸と横軸の構成単位は、「あの」〜「おの」・・・「さの」〜「その」・・・等のように、先頭および末尾についての５個の文字種ごとに区切られたものとなる。
【０１０４】
このように、先頭および末尾の文字種の個数に基づいてトライグラム群を作成していくことで、各トライグラム群に分類されるトライグラムの種類の個数をなるべく同じ個数にすることができる。これにより、トライグラム群の出現位置の個数がなるべく同じ個数になるように分類された場合に比べ、出現位置の個数にはばらつきがでるが、各トライグラム群のトライグラムの個数が均一化されるため、一般的に扱いやすい転置インデックス９００を生成することができる。
【０１０５】
なお、本発明に係る機能を実現するための構成を予め備えた転置インデックスの生成装置および当該転置インデックスを用いた検索装置として提供できることはもとより、プログラムの適用により、既存のパーソナルコンピュータや情報端末機器等を、本発明に係る生成装置および検索装置として機能させることもできる。すなわち、上記実施形態で例示した生成装置１および検索装置２による各機能構成を実現させるための生成プログラムまたは検索プログラムを、既存のパーソナルコンピュータや情報端末機器等を制御するＣＰＵ等が実行できるように適用することで、それぞれ本発明に係る生成装置１および検索装置２として機能させることができる。また、本発明に係る転置インデックスの生成方法および当該転置インデックスを用いた検索方法は、それぞれ生成装置１および検索装置２を用いて実施できる。
【０１０６】
また、このようなプログラムの適用方法は任意であり、例えば、ＣＤ−ＲＯＭやＤＶＤ−ＲＯＭ、メモリカードなどのコンピュータ読み取り可能な記憶媒体に格納して適用できる他、例えば、インターネットなどの通信媒体を介して適用することもできる。
【０１０７】
以上、本発明の好ましい実施形態について説明したが、本発明は係る特定の実施形態に限定されるものではなく、本発明には、特許請求の範囲に記載された発明とその均等の範囲が含まれる。以下に、本願出願の当初の特許請求の範囲に記載された発明を付記する。
【０１０８】
（付記１）
文書データのうちから「３文字の文字列であるトライグラム」を、当該文書データ中での出現位置と対応付けて、抽出する抽出ステップと、
前記抽出されたトライグラムのうち中央の文字が共通なトライグラムを、先頭および末尾の文字に基づいて、トライグラム群に分類する分類ステップと、
前記分類されたトライグラム群のそれぞれに、当該トライグラム群に分類されたトライグラムに対応付けられた出現位置を対応付けて、転置インデックスを生成する生成ステップと、
を備えることを特徴とする転置インデックスの生成方法。
【０１０９】
（付記２）
前記分類ステップでは、
（ａ）前記抽出されたトライグラムのうち中央の文字が共通なトライグラムを、先頭の文字に基づいて、中間トライグラム群に分類し、
（ｂ）前記中間トライグラム群に分類されたトライグラムを、末尾の文字に基づいて、トライグラム群に分類する、
ことを特徴とする付記１に記載の転置インデックスの生成方法。
【０１１０】
（付記３）
前記分類ステップでは、
（ａ）前記抽出されたトライグラムのうち中央の文字が共通なトライグラムを、前記中間トライグラム群に分類されるトライグラムに対応付けられた出現位置の個数の和が所定の第１の個数を超えないように分類し、
（ｂ）前記中間トライグラム群に分類されたトライグラムを、前記トライグラム群に分類されるトライグラムに対応付けられた出現位置の個数が所定の第２の個数の和を超えないように分類する、
ことを特徴とする付記２に記載の転置インデックスの生成方法。
【０１１１】
（付記４）
前記分類ステップでは、
（ａ）前記抽出されたトライグラムのうち中央の文字が共通なトライグラムを、前記中間トライグラム群に分類されるトライグラムの先頭の文字種の個数が所定の第３の個数を超えないように分類し、
（ｂ）前記中間トライグラム群に分類されたトライグラムを、前記トライグラム群に分類されるトライグラムの末尾の文字種の個数が所定の第４の個数を超えないように分類する、
ことを特徴とする付記２に記載の転置インデックスの生成方法。
【０１１２】
（付記５）
付記１から４のいずれか１つに記載の生成方法によって生成された転置インデックスを用いる検索方法であって、
所望の検索文字列を構成するトライグラムのそれぞれについて、前記転置インデックスから、当該トライグラムが分類されたトライグラム群に対応付けられた出現位置を取得する取得ステップと、
前記取得された出現位置に基づいて、前記検索文字列の前記文書データにおける出現位置を特定する特定ステップと、
を備えることを特徴とする検索方法。
【０１１３】
（付記６）
前記取得ステップでは、
（ｐ）前記検索文字列の先頭の文字を中央の文字とし、先頭から２番目の文字を末尾の文字とするトライグラムが分類されたトライグラム群に対応付けられた出現位置を取得し、
（ｑ）前記検索文字列の末尾の文字を中央の文字とし、末尾から２番目の文字を先頭の文字とするトライグラムが分類されたトライグラム群に対応付けられた出現位置を取得する、
ことを特徴とする付記５に記載の検索方法。
【０１１４】
（付記７）
文書データのうちから「３文字の文字列であるトライグラム」を、当該文書データ中での出現位置と対応付けて、抽出する抽出手段と、
前記抽出されたトライグラムのうち中央の文字が共通なトライグラムを、先頭および末尾の文字に基づいて、トライグラム群に分類する分類手段と、
前記分類されたトライグラム群のそれぞれに、当該トライグラム群に分類されたトライグラムに対応付けられた出現位置を対応付けて、転置インデックスを生成する生成手段と、
を備えることを特徴とする生成装置。
【０１１５】
（付記８）
付記１から４のいずれか１つに記載の生成方法によって生成された転置インデックスを用いる検索装置であって、
所望の検索文字列を構成するトライグラムのそれぞれについて、前記転置インデックスから、当該トライグラムが分類されたトライグラム群に対応付けられた出現位置を取得する取得手段と、
前記取得された出現位置に基づいて、前記検索文字列の前記文書データにおける出現位置を特定する特定手段と、
を備えることを特徴とする検索装置。
【０１１６】
（付記９）
コンピュータを、
文書データのうちから「３文字の文字列であるトライグラム」を、当該文書データ中での出現位置と対応付けて、抽出する抽出手段、
前記抽出されたトライグラムのうち中央の文字が共通なトライグラムを、先頭および末尾の文字に基づいて、トライグラム群に分類する分類手段、
前記分類されたトライグラム群のそれぞれに、当該トライグラム群に分類されたトライグラムに対応付けられた出現位置を対応付けて、転置インデックスを生成する生成手段、
として機能させることを特徴とするコンピュータプログラム。
【０１１７】
（付記１０）
コンピュータを、
付記１から４のいずれか１つに記載の生成方法によって生成された転置インデックスを用いる検索装置として機能させるコンピュータプログラムであって、
前記コンピュータを、
所望の検索文字列を構成するトライグラムのそれぞれについて、前記転置インデックスから、当該トライグラムが分類されたトライグラム群に対応付けられた出現位置を取得する取得手段、
前記取得された出現位置に基づいて、前記検索文字列の前記文書データにおける出現位置を特定する特定手段、
として機能させることを特徴とするコンピュータプログラム。
【符号の説明】
【０１１８】
１…生成装置、２…検索装置、３…端末装置、１００…制御部、１０１…抽出部、１０２…分類部、１０３…生成部、１１０…記憶部、１２０…入力部、１３０…出力部、１４０…通信部、１５０…ネットワーク、１５１…ＣＰＵ、１５２…ＲＯＭ、１５３…ＲＡＭ、１５４…ハードディスク、１５５…キーボード、１５６…モニタ、１５７…ＤＶＤ−ＲＯＭドライブ、１５８…通信装置、２００…制御部、２０１…取得部、２０２…特定部、２１０…記憶部、２２０…入力部、２３０…出力部、２４０ａ，２４０ｂ…通信部、２５１…ＣＰＵ、２５２…ＲＯＭ、２５３…ＲＡＭ、２５５…キーボード、２５６…モニタ、３００…文書データ、９００…転置インデックス
【技術分野】
【０００１】
本発明は、Ｎグラム検索に関し、とくにデータサイズを抑えつつ高速な検索処理を実現するのに好適な転置インデックスの生成方法および生成装置、当該転置インデックスを用いた検索方法および検索装置、ならびにコンピュータプログラムに関する。
【背景技術】
【０００２】
文書の電子化の増大に伴い、これまでに蓄積されてきた大量の文書群から所望の文書を見つけ出す検索技術の重要性が高まっている。
【０００３】
大量の文書群を対象とした検索では、検索処理の高速化のため、検索対象となる文書群に含まれる単語等を索引単位として、索引ファイルを作成することが一般的である。あらかじめ作成された索引ファイル（以下、転置インデックスと呼称する）を検索時に用いることで、検索のたびに大量の文書群にアクセスする必要がなくなり、高速な検索処理が実現されるからである。
【０００４】
英語などの多くの言語においては、単語を索引単位として転置インデックスを作成することが一般的である。しかし、日本語の場合、スペース等によって単語の切れ目が明示的に示されないため、しばしば、Ｎグラムを索引単位とする方法が用いられる。Ｎグラムとは、連続するＮ文字からなる部分文字列のことである。Ｎグラムによる転置インデックスの作成は、単語を認識する必要がなく、文字列にのみ基づくため、日本語の文書を検索対象とした検索に適している。
【０００５】
このようなＮグラムを用いた検索では、検索処理の速度や転置インデックスのデータサイズは、索引単位として採用するＮグラムのＮの値によって変化する。例えば、非特許文献１には、異なるＮの値における検索処理の高速化の比較が記載されている。
【先行技術文献】
【非特許文献】
【０００６】
【非特許文献１】小川泰嗣，松田透，”ｎ−ｇｒａｍ索引を用いた効率的な文書検索法”，電子情報通信学会論文誌(D-I)，Vol.J82-D-I，No.1，pp.121-129，1999年1月
【発明の概要】
【発明が解決しようとする課題】
【０００７】
Ｎグラムを用いた検索では、転置インデックスの単位として採用するＮの値を大きくすると、原則として検索処理の速度は上がる。一方で、Ｎの値を大きくすると、文書から抽出されるＮグラムの種類が多くなるため、転置インデックスのデータサイズは増大する。そのため、検索処理の高速化と転置インデックスのデータサイズの抑制とは両立しにくかった。しかし、転置インデックスのデータサイズをなるべく抑えつつ、検索処理の高速化も実現したい、との要望がある。
【０００８】
本発明は、以上のような課題を解決するためのものであり、データサイズを抑えつつ高速な検索処理を実現するのに好適な転置インデックスの生成方法および生成装置、当該転置インデックスを用いた検索方法および検索装置、ならびに、コンピュータプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００９】
上記目的を達成するため、本発明にかかる転置インデックスの生成方法は、
文書データのうちから「３文字の文字列であるトライグラム」を、当該文書データ中での出現位置と対応付けて、抽出する抽出ステップと、
前記抽出されたトライグラムのうち中央の文字が共通なトライグラムを、先頭および末尾の文字に基づいて、トライグラム群に分類する分類ステップと、
前記分類されたトライグラム群のそれぞれに、当該トライグラム群に分類されたトライグラムに対応付けられた出現位置を対応付けて、転置インデックスを生成する生成ステップと、
を備えることを特徴とする。
【発明の効果】
【００１０】
本発明によれば、データサイズを抑えつつ高速な検索処理を実現するのに好適な転置インデックスの生成方法および生成装置、当該転置インデックスを用いた検索方法および検索装置、ならびに、コンピュータプログラムを提供することができる。
【図面の簡単な説明】
【００１１】
【図１】本発明の実施形態に係る転置インデックスの生成装置の概要構成を示す図である。
【図２】本発明の実施形態に係る転置インデックスの生成装置の物理構成を示す図である。
【図３】本発明の実施形態に係る文書データ構成を示す図である。
【図４】本発明の実施形態に係る生成装置の処理の流れを示すフローチャートである。
【図５】本発明の実施形態において、文書データから抽出されたトライグラムとその出現位置の例を示す図である。
【図６】本発明の実施形態において、トライグラムが統合トライグラム群に分類された様子を示す図である。
【図７】本発明の実施形態において、統合トライグラム群のトライグラムが中間トライグラム群に分類される様子を示す図である。
【図８】本発明の実施形態において、中間トライグラム群のトライグラムがトライグラム群に分類される様子を示す図である。
【図９】本発明の実施形態において、転置インデックスの構成をトライグラムの中央の文字ごとに２次元状に表した図である。
【図１０】本発明の実施形態に係る検索装置の概要構成を示す図である。
【図１１】本発明の実施形態に係る検索装置の物理構成を示す図である。
【図１２Ａ】本発明の実施形態に係る検索装置の処理の流れを示す第１のフローチャートである。
【図１２Ｂ】本発明の実施形態に係る検索装置の処理の流れを示す第２のフローチャートである。
【図１２Ｃ】本発明の実施形態に係る検索装置の処理の流れを示す第３のフローチャートである。
【図１３Ａ】本発明の実施形態に係る検索処理において、転置インデックスから出現位置が取得される様子を示す第１の図である。
【図１３Ｂ】本発明の実施形態に係る検索処理において、転置インデックスから出現位置が取得される様子を示す第２の図である。
【図１３Ｃ】本発明の実施形態に係る検索処理において、転置インデックスから出現位置が取得される様子を示す第３の図である。
【図１３Ｄ】本発明の実施形態に係る検索処理において、転置インデックスから出現位置が取得される様子を示す第４の図である。
【図１４】本発明に係る検索装置の構成概要について、別の例を示す図である。
【図１５】本発明に係る転置インデックスの構成について、別の例を示す図である。
【発明を実施するための形態】
【００１２】
以下、本発明の実施形態について、図面を参照して説明する。なお、以下に説明する実施形態は説明のためのものであり、本発明の範囲を制限するものではない。したがって、当業者であれば下記の各構成要素を均等なものに置換した実施形態を採用することが可能であるが、これらの実施形態も本発明の範囲に含まれる。また、以下の説明では、本発明の理解を容易にするため、重要でない公知の技術的事項の説明を適宜省略する。
【００１３】
まず、本実施形態に係る転置インデックスの生成装置１が実現される情報処理装置は、図１に示されるような構成をとる。すなわち、生成装置１は、制御部１００と、記憶部１１０と、入力部１２０と、出力部１３０と、通信部１４０と、を備える。一方、当該生成装置１は、物理的には図２に示されるように構成され、ＣＰＵ（Central Processing Unit）１５１と、ＲＯＭ（Read Only Memory）１５２と、ＲＡＭ（Random Access Memory）１５３と、ハードディスク１５４と、キーボード１５５と、モニタ１５６と、ＤＶＤ−ＲＯＭドライブ１５７と、通信装置１５８と、を備える。以下、図１および図２を参照して、生成装置１の構成要素の説明をする。
【００１４】
制御部１００は、生成装置１全体の動作を制御し、各構成要素と接続され、制御信号やデータをやりとりする。すなわち、制御部１００は、記憶部１１０、入力部１２０、出力部１３０、通信部１４０と接続され、これら各部の機能を活用しながら、転置インデックスの生成処理を実行する。
【００１５】
ここで制御部１００は、抽出部１０１と、分類部１０２と、生成部１０３と、を備える。これらの各部は、詳細には後述するように、記憶部１１０に記憶されている文書データ３００をもとにして、転置インデックス９００を生成する処理を実行する。
【００１６】
このような制御部１００（抽出部１０１、分類部１０２、生成部１０３）は、例えばＣＰＵ１５１によって構成される。ここでＣＰＵ１５１は、命令やデータを転送するための伝送経路であるシステムバスにより各構成要素と相互に接続され、ＲＯＭ１５２に記録されている生成装置１全体の動作制御に必要なコンピュータプログラムや各種データに従って動作する。そしてＣＰＵ１５１は、ＲＯＭ１５２から読み出したコンピュータプログラムやデータ、その他処理の進行に必要なデータを、ＲＡＭ１５３に一時的に記憶しながら、各種動作を制御する。このようにＣＰＵ１５１がＲＯＭ１５２やＲＡＭ１５３と協働することで、制御部１００は、生成装置１全体の動作を制御する。
【００１７】
記憶部１１０は、例えばハードディスク１５４のような大容量外部記憶装置によって構成され、制御部１００が転置インデックス９００を生成する処理のために必要な各種データ、具体的には後述する検索装置によって検索対象とされる文書データ３００等が、記憶される。また、記憶部１１０は、生成装置１の処理によって生成された転置インデックス９００も記憶する。
【００１８】
ここで、記憶部１１０にあらかじめ記憶される文書データ３００は、図３に示されるように、個々の文書データ３００ａ〜３００ｃ等から構成され、さらに文書データ３００ａ〜３００ｃ等はそれぞれ、「見出し語」と「説明文」とから構成される。すなわち、文書データ３００ａ〜３００ｃ等は、辞書を構成する構成単位であり、「見出し語」とは、当該辞書の見出しとなる１つの語句であり、１つの文書データ３００に対して１つの見出し語が対応付けられる。そして、「見出し語」には当該見出し語を説明する「説明文」が対応付けられ、これらを合わせて１つの文書データ３００を構成する。
【００１９】
図１および図２に戻って、記憶部１１０が記憶するこれらのデータは、例えば生成装置１のＤＶＤ−ＲＯＭドライブ１５７を介して、あるいは通信部１４０によって接続されるネットワーク１５０を介して、外部とやり取りされる。
【００２０】
入力部１２０は、例えばキーボード１５５のような入力装置によって構成され、ユーザからの入力を受け付ける。受け付けられた入力情報は、制御部１００へと供給される。本実施形態では、転置インデックス９００を生成するためのユーザからの命令を受け付ける。
【００２１】
出力部１３０は、例えばモニタ１５６のような表示装置によって構成され、制御部１００が処理を行った結果をユーザへ出力する。本実施形態では、抽出部１０１、分類部１０２、生成部１０３のそれぞれが行う転置インデックス９００の生成処理の経過や結果がモニタ１５６に表示される。これにより、ユーザは当該生成処理の経過や結果についての情報を得ることができる。
【００２２】
通信部１４０は、生成装置１をインターネット等のネットワーク１５０に接続し、制御部１００の制御のもと、ネットワーク１５０を介してデータをやり取りする。このような通信部１４０は、例えばモデム等の適宜の通信装置１５８によって構成される。
【００２３】
以上のように構成される生成装置１は、制御部１００の制御のもと、転置インデックス９００の生成処理を行う。具体的には、図４のフローチャートに示される手順で処理を実行する。
【００２４】
本処理は、ユーザからの転置インデックス９００を生成する旨の指示を、生成装置１の入力部１２０が受け付けることを契機として、開始される。すなわち、キーボード１５５を用いて、ユーザが転置インデックス９００を生成する旨を指示することで、本処理が開始する。
【００２５】
処理が開始されると、まず抽出部１０１が、記憶部１１０に記憶された文書データ３００からトライグラム（Ｎ＝３のＮグラム）を、その出現位置を対応付けて抽出する（ステップＳ４０１）。ここでＮグラムとは、Ｎ文字の文字列（Ｎは自然数）を意味し、Ｎ＝３のＮグラム（トライグラム）とは、３文字の文字列をいう。すなわち、抽出部１０１は、文書データ３００に含まれる見出し語や説明文を構成する文字列から、３文字の文字列（トライグラム）を抽出可能な数だけ抽出する。
【００２６】
一般的に、文字数がＸ文字の文字列からは、Ｘ−Ｎ＋１個のＮグラムが抽出されるため、Ｎ＝３の場合は、Ｘ−２個（Ｘ−３＋１個）のバイグラムが抽出される。例えば、「携帯電話」という４文字の文字列からは、「携帯電」「帯電話」という２個（４−２個）のトライグラムが抽出され、「ボールペン」という５文字の文字列からは、「ボール」「ールペ」「ルペン」という３個（５−２個）のトライグラムが抽出される。
【００２７】
このとき抽出部１０１は、それぞれに文書データ３００中での出現位置を対応付けつつ、トライグラムを抽出する。すなわち、抽出されたトライグラムが、抽出元の文書データ３００中の先頭文字から数えて何文字目に位置していたかの情報を、当該トライグラムに対応付けながら抽出する。
【００２８】
例えば、文書データ３００を構成する文字列が、「ボールペン」という５文字の文字列から始まっていたとした場合は、抽出されたトライグラムのうち、トライグラム「ボール」には１（文字目）、トライグラム「ールペ」には２（文字目）、トライグラム「ルペン」には３（文字目）、という出現位置を表す値が対応付けられる。ここで、文書データ３００中に同一のトライグラムが複数出現する場合には、当該トライグラムに複数の出現位置が対応付けられることになる。
【００２９】
出現位置の対応付け処理が行われると、具体的には図５に示されるように、文書データ３００から抽出された各トライグラムとその出現位置との対応関係が形成される。本図の対応関係からは、例えば「ボール」というトライグラムは、文書データ３００の先頭から１文字目、２２文字目、３３文字目、８７文字目、１２０文字目に出現し、また「リンゴ」というトライグラムは１９９文字目と２１９文字目に出現するということが分かる。
【００３０】
これらの抽出されたトライグラムやそれらの出現位置は、ＲＡＭ１５３等に一時的に保持される。
【００３１】
トライグラムが抽出されると、次に分類部１０２が、抽出されたトライグラムのうち、中央の文字が共通なトライグラムを統合トライグラム群としてまとめる（ステップＳ４０２）。すなわち、分類部１０２は、トライグラムの３文字の文字列のうち、中央の（２番目の）文字に着目し、同じ文字を中央の文字として有するトライグラムを１つの統合トライグラム群としてまとめる。
【００３２】
まとめられた統合トライグラム群は、例えば図６に示されるようになる。すなわち、「あ」を中央の文字として有するトライグラムが分類された統合トライグラム群、「の」を中央の文字として有するトライグラムが分類された統合トライグラム群、「ン」を中央の文字として有するトライグラムが分類された統合トライグラム群、「山」を中央の文字として有するトライグラムが分類された統合トライグラム群・・・というように、文書データ３００から抽出されたトライグラムの中央の文字の種類の数だけ、統合トライグラム群を作成する。
【００３３】
統合トライグラム群にトライグラムがまとめられると、次に分類部１０２は、統合トライグラム群ごとにトライグラムを先頭の文字順に並べる（ステップＳ４０３）。ここで文字順とは、いわゆる辞書順であり、五十音順やアルファベット順等のような文字列の並び順をいう。日本語のように複数の文字種がある場合にはひらがな、カタカナ、漢字、アルファベット・・・といったように文字種に順序を定めてもよい。すなわち、中央の文字が共通なトライグラムについて、先頭の文字に着目し、このような辞書順に並べる。
【００３４】
具体的には図７に示すように、分類部１０２は、例えば文字「の」を共通な中央の文字とする統合トライグラム群にまとめられたトライグラムについて、それぞれの先頭の文字に着目し、先頭の文字が「あ」「い」・・・「お」・・・「ん」・・・「意」・・・といった順になるように並べる。このようなトライグラムを先頭の文字について辞書順に並べる処理を、すべての統合トライグラム群に対して実行する。
【００３５】
図４のフローチャートに戻って、次に分類部１０２は、並べられたトライグラムを、出現位置が所定の個数を超えないように、並び順に中間トライグラム群に分類する（ステップＳ４０４）。すなわち分類部１０２は、先頭の文字順に並べられたトライグラムについて、最初のトライグラムから並び順に１つ以上のトライグラムをひとまとめにし、中間トライグラム群としてまとめていく。
【００３６】
具体的に、図７のように「の」を共通な中央の文字とする統合トライグラム群の例では、先頭の文字順に並べられたトライグラムについて、最初に並べられたトライグラム「あのあ」から順に、「あのい」、「あのう」・・・「おの輪」までを１つの中間トライグラム群Ａとしてまとめる。そして、次のトライグラム「かのあ」から、並べられた順に「けの和」まで、中間トライグラム群Ｂとしてまとめる。このような処理を繰り返して、中間トライグラム群Ｘ、中間トライグラム群Ｙ・・・というように、並べられた最後のトライグラムまで、中間トライグラム群としてまとめていく。
【００３７】
なおこのとき、分類が複雑になることを防ぐため、分類部１０２は、先頭の文字が同一のトライグラムは同一の中間トライグラム群にまとめられるようにする。例えば、「かのあ」と「かのわ」という２つのトライグラムは、同一の先頭の文字「か」を有するため、異なる中間トライグラム群に分けて分類されるのではなく、トライグラム「かのあ」が分類された中間トライグラム群には必ずトライグラム「かのわ」も分類されるようにする。
【００３８】
さらにこのとき、１つの中間トライグラム群にまとめられるトライグラムの個数が、まとめられたトライグラムに対応付けられた出現位置の個数の和が所定の個数を超えないように、分類部１０２はトライグラムを分類する。具体的に説明すると、分類部１０２は、各トライグラムに対応付けられた出現位置の個数に着目し、最初のトライグラムから順に中間トライグラム群に分類していく際、分類対象となっているトライグラムの出現位置の個数と、分類候補となっている中間トライグラム群にすでに分類されたトライグラムの出現位置の個数との和を算出し、あらかじめ用意された所定の個数と比較する。所定の個数を超えていなければ、当該分類候補となっている中間トライグラム群に分類対象のトライグラムを分類する。一方で、所定の個数を超えていれば、異なる中間トライグラム群に分類対象のトライグラムを分類する。
【００３９】
このように、分類部１０２が各中間トライグラム群に分類されるトライグラムの出現位置の個数の和が所定の個数を超えないように分類することで、各中間トライグラム群の出現位置の個数をなるべく均一にすることができる。その結果、出現位置が効率的に格納された転置インデックス９００を生成することへとつながる。
【００４０】
再び図４のフローチャートに戻って、さらに分類部１０２は、作成された中間トライグラム群ごとに、トライグラムを末尾の文字順に並べる（ステップＳ４０５）。すなわち分類部１０２は、トライグラムの先頭の文字に基づいて分類された中間トライグラム群のそれぞれにおいて、今度はトライグラムの末尾の文字に着目し、末尾の文字の辞書順に並べる。
【００４１】
具体的には図８に示すように、分類部１０２は、例えば文字「の」を共通な中央の文字とし、先頭の文字が「あ」〜「お」のトライグラムが分類された中間トライグラム群Ａにおいて、トライグラムの末尾の文字に着目し、末尾の文字が「あ」「い」「う」・・・「り」・・・「輪」・・・といった順になるように並べる。このようなトライグラムを末尾の文字について辞書順に並べる処理を、すべての中間トライグラム群に対して実行する。
【００４２】
図４のフローチャートに戻って、次に分類部１０２は、末尾の文字順に並べられたトライグラムを、出現位置が所定の個数を超えないように、並び順にトライグラム群に分類する（ステップＳ４０６）。すなわち分類部１０２は、末尾の文字順に並べられたトライグラムについて、最初のトライグラムから並び順に１つ以上のトライグラムをひとまとめにし、トライグラム群としてまとめていく。
【００４３】
具体的に、図８のような中間トライグラム群Ａの例では、末尾の文字順に並べられたトライグラムについて、最初に並べられたトライグラム「あのあ」から順に、「いのあ」・・・「おのあ」「あのい」・・・「おのう」までを１つのトライグラム群ＡＡとしてまとめる。そして、次のトライグラム「あのえ」から、並べられた順に「おのく」まで、トライグラム群ＡＢとしてまとめる。このような処理を繰り返して、トライグラム群ＡＰ、トライグラム群ＡＱ・・・というように、並べられた最後のトライグラムまで、トライグラム群としてまとめていく。
【００４４】
なおこのとき、上記中間トライグラム群への分類と同様に、分類が複雑になることを防ぐため、分類部１０２は、末尾の文字が同一のトライグラムは同一のトライグラム群にまとめられるようにする。例えば、「かのさ」と「このさ」という２つのトライグラムは、同一の末尾の文字「さ」を有するため、異なるトライグラム群に分けて分類されるのではなく、トライグラム「かのさ」が分類されたトライグラム群には必ずトライグラム「このさ」も分類されるようにする。
【００４５】
さらにこのとき、上記中間トライグラム群への分類と同様に、トライグラム群の出現位置の個数をなるべく均一にするため、１つのトライグラム群にまとめられるトライグラムの個数が、まとめられたトライグラムに対応付けられた出現位置の個数の和が所定の個数を超えないように、分類部１０２はトライグラムを分類する。具体的に説明すると、分類部１０２は、各トライグラムに対応付けられた出現位置の個数に着目し、各中間トライグラム群において最初のトライグラムから順にトライグラム群に分類していく際、分類対象となっているトライグラムの出現位置の個数と、分類候補となっているトライグラム群にすでに分類されたトライグラムの出現位置の個数との和を算出し、あらかじめ用意された所定の個数と比較する。所定の個数を超えていなければ、当該分類候補となっているトライグラム群に分類対象のトライグラムを分類する。一方で、所定の個数を超えていれば、異なるトライグラム群に分類対象のトライグラムを分類する。
【００４６】
図４のフローチャートに戻って、最後に生成装置１の生成部１０３が、各トライグラム群に、そこに分類されたトライグラムの出現位置を対応付けて、転置インデックス９００を生成する（ステップＳ４０７）。すなわち、生成部１０３は、トライグラム群と、そこに分類された全てのトライグラムに上記ステップＳ４０１にて対応付けられた文書データ３００中での出現位置と、を構成要素として、転置インデックス９００を生成する。その後、生成された転置インデックス９００は、ハードディスク１５４のような記憶部１１０に記憶され、本フローチャートの処理は終了する。
【００４７】
ここで生成される転置インデックス９００は、図９に示されるような２次元の表状に表すことができる。すなわち、生成される転置インデックス９００の構成は、トライグラムの中央の文字ごとに、先頭の２文字を縦軸に、末尾の２文字を横軸にとり、出現位置を要素とする２次元状の表として表される。１つの表全体は、中央の文字を共通とするトライグラム全体、すなわち統合トライグラム群１つに相当するものである。
【００４８】
ここで本図における縦軸の構成単位は、中央の文字が共通のトライグラムを先頭の文字に基づいて中間トライグラム群に分類した際の分類の単位であり、横軸の構成単位は、中間トライグラム群に分類されたトライグラムを末尾の文字に基づいてトライグラム群に分類した際の分類の単位である。そのため、１つのセルは１つのトライグラム群に相当し、１つのセルには、対応するトライグラム群に分類されたトライグラムに対応付けられた全ての出現位置が格納される。
【００４９】
具体的に説明すると、表上で最も左上に配置されたセルは、先頭の２文字が「あの」〜「おの」であり、末尾の２文字が「のあ」〜「のう」であるトライグラムが分類されたトライグラム群に相当する。例えば「いのう」や「おのあ」というトライグラムがここに分類される。そして、当該トライグラム群に分類されたいずれかのトライグラムは、本図の当該セルに示されるように、文書データ３００中の先頭から１２文字目、４９文字目、９２３文字目、１１１０４文字目、１１２９３文字目・・・という位置に出現する。一方で別の例を挙げると、例えば「しのひ」や「たのへ」といったトライグラムは、先頭の２文字が「さの」〜「ちの」で末尾の２文字が「のひ」〜「のほ」に相当するトライグラムである。本図によれば、これらのうちいずれかのトライグラムが、文書データ３００中の先頭から６５８６文字目、５９８９９文字目、７２４９５文字目・・・の位置に出現する。
【００５０】
生成装置１が生成する転置インデックス９００は、このようなトライグラム群とその出現位置との２次元状の対応関係を、トライグラムの中央の文字のそれぞれについて備え、後述する検索処理において用いられる。
【００５１】
以上のような構成により、本実施形態の生成装置１は、文書データ３００から抽出されたトライグラムについて、中央の文字が共通なトライグラムをまとめ、まとめられたトライグラムをさらに先頭および末尾の文字に基づいてトライグラム群に分類する。そして、トライグラム群とそれぞれに分類されたトライグラムの出現位置とを対応付けて、転置インデックス９００を生成する。その結果、トライグラムを単独で単位としたものに比べてデータサイズが抑えられ、かつ後述する検索装置２において高速な検索処理を実現することができる転置インデックス９００を生成することができる。
【００５２】
その際、生成装置１は、トライグラム群に分類されるトライグラムの出現位置の個数の和が所定の上限値を超えないようにトライグラムを分類していく。これにより、各トライグラム群に対応付けられる出現位置の個数がなるべく同じ個数に均一化することができ、出現位置が効率的に格納された転置インデックス９００を生成することができる。
【００５３】
本発明では、上記のような転置インデックス９００の生成装置１、およびそれを用いた転置インデックス９００の生成方法に加え、当該生成された転置インデックス９００を用いて、文書データ３００を検索対象とした検索を行う検索装置２、およびそれを用いた検索方法を提供する。
【００５４】
ここで検索装置は、通常は上記転置インデックスの生成装置１とは異なる情報処理装置によって実現される。具体的に本実施形態では、検索装置として、電子辞書等の機能を備える小型の情報処理装置を想定して説明する。すなわち、検索対象である文書データ３００についての転置インデックス９００の生成については、あらかじめ上記図１および図２に示されたような一般的な情報処理装置において行われ、一方で当該生成された転置インデックス９００を用いた文書データ３００の検索については、生成装置１とは異なる情報処理装置、すなわち電子辞書等の小型の情報処理装置において実現される。
【００５５】
このような検索装置２として、その構成は図１０に示されるようなものになる。すなわち検索装置２は、制御部２００と、記憶部２１０と、入力部２２０と、出力部２３０と、を備える。一方、当該検索装置２は、物理的には図１１に示されるように構成され、ＣＰＵ２５１と、ＲＯＭ２５２と、ＲＡＭ２５３と、キーボード２５５と、モニタ２５６と、を備える。以下、図１０および図１１を参照して、検索装置２の構成要素の説明をする。
【００５６】
制御部２００は、検索装置２全体の動作を制御し、各構成要素と接続され、制御信号やデータをやりとりする。すなわち、制御部２００は、記憶部２１０、入力部２２０、出力部２３０と接続され、これら各部の機能を活用しながら、検索処理を実行する。
【００５７】
ここで制御部２００は、取得部２０１と、特定部２０２と、を備える。これらの各部は、詳細には後述するように、記憶部２１０に記憶されている転置インデックス９００を用いて、文書データ３００のうちから検索文字列が出現する位置を特定する処理を実行する。
【００５８】
このような制御部２００（取得部２０１、特定部２０２）は、例えばＣＰＵ２５１によって構成される。ここでＣＰＵ２５１は、基本的には生成装置１におけるＣＰＵ１５１と同様、命令やデータを転送するための伝送経路であるシステムバスにより各構成要素と相互に接続され、ＲＯＭ２５２に記録されている検索装置２全体の動作制御に必要なコンピュータプログラムや各種データに従って動作し、さらにＲＯＭ２５２から読み出したコンピュータプログラムやデータ、その他処理の進行に必要なデータを、ＲＡＭ２５３に一時的に記憶しながら、各種動作を制御する。このようにＣＰＵ２５１がＲＯＭ２５２やＲＡＭ２５３と協働することで、制御部２００は、検索装置２全体の動作を制御する。
【００５９】
記憶部２１０は、例えば検索装置２内に備えられたＲＯＭ２５２のような読出し専用の記憶媒体によって構成され、制御部２００が検索処理に必要な各種データを記憶する。具体的にここでは、検索対象とされる文書データ３００、および転置インデックス９００が記憶される。
【００６０】
これら文書データ３００は、上記生成装置１の記憶部１１０に記憶された文書データ３００と同一のものであり、また転置インデックス９００は、上記生成装置１が、これら文書データ３００をもとにして生成した転置インデックス９００と同一のものである。
【００６１】
入力部２２０は、例えばキーボード２５５のような入力装置によって構成され、ユーザからの入力を受け付ける。具体的にここでは、ユーザからの検索語を受け付ける。受け付けられた検索語は、制御部２００の取得部２０１へと供給され、当該検索語の文字列の文書データ３００における出現位置を検索する処理に用いられる。
【００６２】
出力部２３０は、例えばモニタ２５６のような表示装置によって構成され、制御部２００が処理を行った結果をユーザへ出力する。具体的にここでは、ユーザが入力した検索語の文書データ３００における出現位置を、検索結果としてモニタ２５６に表示することで、当該ユーザへと出力する。これにより、ユーザは、自身が入力した検索語の出現位置を出力結果として取得し、種々に利用することができるようになる。
【００６３】
なお、入力部２２０と出力部２３０は、タッチパネル等のような入力装置と出力装置が組み合わされた装置によって構成されてもよい。この場合には、タッチパネルに内蔵されたタッチセンサ等からなる位置入力装置が入力部２２０を、液晶ディスプレイ等からなる表示装置が出力部２３０を、それぞれ構成する。
【００６４】
以上のように構成される検索装置２は、制御部２００の制御のもと、検索処理を行う。具体的には、図１２Ａ〜図１２Ｃのフローチャートに示される手順で処理を実行する。
【００６５】
本処理は、ユーザから入力された検索語を、検索装置２の入力部２２０が受け付けることを契機として、開始される。すなわち、キーボード２５５を用いて、ユーザが所望の検索語を入力し、検索する旨を指示することで、本処理が開始する。
【００６６】
まず図１２Ａのフローチャートにおいて、検索処理が開始されると、まず取得部２０１が、入力された検索語の文字列（検索文字列）の先頭の文字に注目する（ステップＳ１２０１）。例えば、ユーザが「しすてむ」という検索語を入力した場合、取得部２０１は、先頭の文字「し」に注目する。あるいは、ユーザが「山」という１文字の検索語を入力した場合には、取得部２０１は、当該１文字「山」を先頭の文字として注目する。
【００６７】
先頭の文字が注目されると、次に取得部２０１は、その文字を中央の文字とするトライグラムが分類された全てのトライグラム群に注目する（ステップＳ１２０２）。すなわち取得部２０１は、記憶部２１０に記憶されている転置インデックス９００にアクセスし、その中に格納されているトライグラム群のうち、注目した文字を中央の文字とするトライグラムが分類された全てのトライグラム群（上記図９における１つの表全体に対応する全てのトライグラム群に相当）に注目する。上記の例では、注目した先頭の文字「し」や「山」を中央の文字とするトライグラムが分類された全てのトライグラム群に注目する。
【００６８】
ここで取得部２０１は、検索文字列が１文字か否かを判定する（ステップＳ１２０３）。例えばユーザが「山」という検索語を入力したとき等のように、検索文字列が１文字の場合は（ステップＳ１２０３；ＹＥＳ）、検索語が２文字以上の場合とは異なるフローへ移行し、まず検索装置２の特定部２０２が、注目したトライグラム群があるか否かを判定する（ステップＳ１２０４）。すなわち、上記ステップＳ１２０２にて注目した、１文字の検索語（例えば「山」）を中央の文字とするトライグラムが分類されたトライグラム群が１つでも存在するか否かを判定する。
【００６９】
１文字の検索語を中央の文字とするトライグラム群がない場合（ステップＳ１２０４；ＮＯ）、特定部２０２は、「該当箇所無し」を出力し（ステップＳ１２０５）、検索処理を終了する。文書データ３００のいずれかの位置に当該１文字の検索語があるならば、その１文字を中央の文字とするトライグラムが分類されたトライグラム群があるはずであり、トライグラム群がないということは、文書データ３００中に入力された１文字の検索語がないということになるからである。そのため、特定部２０２は、出力部２３０を介してモニタ２５６に「該当箇所無し」という文字を表示する等により、ユーザへその旨を出力する。
【００７０】
一方、１文字の検索語を中央の文字とするトライグラム群がある場合（ステップＳ１２０４；ＹＥＳ）、特定部２０２は、該当するトライグラム群の全ての出現位置に１を加算して出力し（ステップＳ１２０６）、検索処理を終了する。後述する２文字以上の検索語の場合と異なり、検索語が１文字の場合には、注目したトライグラム群のトライグラムは当該１文字の検索語をその中央の文字として必ず含んでいるため、トライグラム群の出現位置に１を加算した位置（すなわち対応するトライグラムの２文字目）には必ず当該１文字の検索語が出現するからである。そのため、特定部２０２は、出力部２３０を介してモニタ２５６に表示する等により、該当するトライグラム群の全ての出現位置に１を加算した位置を、ユーザへ出力する。
【００７１】
また一方で、入力された検索語の文字列が１文字でない場合（ステップＳ１２０３；ＮＯ）は、検索装置２の処理はステップＳ１２０７へと移行し、取得部２０１が、注目したトライグラム群のうち後の文字を末尾の文字とするトライグラムが分類されたトライグラム群の出現位置を全て取得する（ステップＳ１２０７）。すなわちここでは、取得部２０１は、上記ステップＳ１２０２にて注目した検索文字列の先頭の文字を中心の文字とするトライグラムが分類された全てのトライグラム群について、さらに検索文字列の後の文字（先頭から２文字目）を末尾の文字とするトライグラムが分類されたトライグラム群にまで絞り込みを行う。そして、取得部２０１は、絞り込んだトライグラム群について、転置インデックス９００に格納されている全ての出現位置を取得する。
【００７２】
具体的な例として、ユーザが「しすてむ」という検索語を入力した場合について説明する。この場合、上記ステップＳ１２０２にて注目したトライグラム群は、当該４文字の検索語の先頭の文字「し」を中心の文字とするトライグラムが分類された全てのトライグラム群であって、図１３Ａに表された文字「し」についての２次元状の表に配置されたトライグラム群全体に相当する。ここで本図における２次元状の表は、上記図９と同様に、転置インデックス９００の構成をトライグラムの中央の文字ごとに２次元状に表したものである。
【００７３】
そして、上記ステップＳ１２０７にて絞り込んだトライグラム群は、当該検索語「しすてむ」の２番目の文字「す」を末尾の文字とするトライグラムが分類されたトライグラム群であって、図１３Ａにおける太線で囲われた部分のトライグラム群に相当する。すなわち、絞り込むべきトライグラム群は、「しす」という２文字を末尾の２文字とするトライグラム「＊しす」（＊はどの文字種でもよい）が分類されたトライグラム群であるので、図１３Ａにおける「しさ」〜「しせ」の欄の縦一列の全てのセルのトライグラム群に相当することになる。ステップＳ１２０７では、取得部２０１が、これら縦一列の全てのセル内の出現位置（１９１文字目、４４９文字目、６５４５文字目、１１０９５文字目・・・、３２１文字目、１０８８文字目・・・等）を取得する。
【００７４】
図１２Ａのフローチャートに戻って、取得部２０１が転置インデックス９００から出現位置を取得すると、次に取得部２０１が、出現位置があるか否かを判定する（ステップＳ１２０８）。すなわち、取得した出現位置がそもそも１つでも存在するか否かを判定する。出現位置がない場合は（ステップＳ１２０８；ＮＯ）、検索対象の文書データ３００中に入力された検索文字列が存在しないということを意味するため、特定部２０２が、「該当箇所無し」を出力し（ステップＳ１２０５）、検索処理を終了する。すなわち特定部２０２は、出力部２３０を介してモニタ２５６に「該当箇所無し」という文字を表示する等により、ユーザへその旨を出力する。
【００７５】
一方、出現位置が１つでも存在する場合は（ステップＳ１２０８；ＹＥＳ）、特定部２０２が、その出現位置を保持する（ステップＳ１２０９）。すなわち、転置インデックス９００から取得した全ての出現位置を、ＲＡＭ２５３等に一時的に保持する。その後、検索処理は図１２Ｂのフローチャートへ移行する。
【００７６】
検索処理が図１２Ｂのフローチャートへ移行すると、次に取得部２０１は、検索文字列の次の文字に注目し（ステップＳ１２１０）、その文字を中央の文字とするトライグラムが分類された全てのトライグラム群に注目する（ステップＳ１２１１）。具体的にユーザが「しすてむ」という４文字の検索語を入力した場合では、取得部２０１は、先頭の文字の次の文字、すなわち２文字目の文字「す」に注目する。そして、転置インデックス９００内に格納された当該文字「す」を中心の文字とするトライグラムが分類された全てのトライグラム群に注目する。ここで注目するトライグラム群は、図１３Ｂに表された文字「す」についての２次元状の表に配置されたトライグラム群全体に相当する。
【００７７】
図１２Ｂのフローチャートにおいて、さらに取得部２０１は、検索文字列の注目した文字に対して、後の文字があるか否かを判定する（ステップＳ１２１２）。上記検索語「しすてむ」での例では、注目した文字「す」の後にさらに「て」と「む」の文字が存在しているため、取得部２０１は後の文字があると判定する。
【００７８】
後の文字があると判定すると（ステップＳ１２１２；ＹＥＳ）、取得部２０１は、注目したトライグラム群のうち、前の文字を先頭の文字とし、後の文字を末尾の文字とするトライグラムが分類されたトライグラム群の出現位置を全て取得する（ステップＳ１２１３）。すなわち、上記検索語「しすてむ」での例では、注目した２文字目の文字「す」を中央の文字、前の文字「し」を先頭の文字、後の文字「て」を末尾の文字とするトライグラム「しすて」が分類されたトライグラム群の出現位置を全て、取得部２０１が取得する。
【００７９】
図１３Ｂに表された文字「す」についての２次元状の表では、当該「しすて」というトライグラムは、先頭の２文字（縦軸）が「しす」〜「つす」、末尾の２文字（横軸）が「すそ」〜「すと」の範囲に該当するものであるため、当該トライグラムが分類されたトライグラム群は、太線で囲われた１つのセルに相当するものとなる。従って、取得部２０１は、当該セル内の出現位置（５２３文字目、８７６文字目・・・等）を全て取得する。
【００８０】
図１２Ｂのフローチャートに戻って、出現位置を取得すると、次に特定部２０２が、保持された出現位置と連続する出現位置があるか否かを判定する（ステップＳ１２１４）。すなわち特定部２０２は、上記ステップＳ１２０９にて保持した検索語の先頭の文字についてのトライグラム群の出現位置と、取得した検索語の２番目の文字についてのトライグラム群の出現位置とを比較して、保持した出現位置の値に１だけ加算した値の出現位置があるか否かを判定する。保持した出現位置と取得した出現位置の中に、検索語の文字列を構成するトライグラムの出現位置が含まれているならば、それらは検索語の文字列を構成するように連続しているはずだからである。
【００８１】
そのため、連続する出現位置がなければ（ステップＳ１２１４；ＮＯ）、検索対象の文書データ３００には検索語が含まれていないということになり、特定部２０２は、「該当箇所無し」を出力し（ステップＳ１２１５）、検索処理を終了する。すなわち特定部２０２は、出力部２３０を介してモニタ２５６に「該当箇所無し」という文字を表示する等により、ユーザへその旨を出力する。
【００８２】
一方、連続する出現位置があれば（ステップＳ１２１４；ＹＥＳ）、特定部２０２は、保持する出現位置を連続する出現位置と入れ替える（ステップＳ１２１６）。すなわち、特定部２０２は、検索文字列の２番目の文字についてのトライグラム群の出現位置のうち、連続すると判定した出現位置を、それまで保持していた先頭の文字についてのトライグラム群の出現位置と入れ替えて、ＲＡＭ２５３等に保持する。
【００８３】
その後、検索処理は再びステップＳ１２１０へと戻る。すなわち、検索装置２は、検索文字列の次の文字に注目し、当該注目した文字について、ステップＳ１２１１以降の処理を繰り返す。上記検索語「しすてむ」での例では、取得部２０１は、３文字目の文字「て」に注目し、その前後の文字とともに構成するトライグラム「すてむ」が分類されたトライグラム群の出現位置を、転置インデックス９００から取得する。
【００８４】
具体的に図１３Ｃに表された文字「て」についての２次元状の表では、当該「すてむ」というトライグラムは、先頭の２文字（縦軸）が「さて」〜「ちて」、末尾の２文字（横軸）が「てま」〜「てめ」の範囲に該当するものであるため、当該トライグラムが分類されたトライグラム群は、太線で囲われたセルに相当するものとなる。従って、取得部２０１は、当該セル内の出現位置（３１文字目、５１９文字目・・・等）を全て取得する。
【００８５】
その後同様に、特定部２０２が出現位置の連続性を判定し（ステップＳ１２１４）、連続する出現位置を保持して（ステップＳ１２１６）、再び検索処理はステップＳ１２１０へと戻る。そして、検索文字列の次の文字、すなわち検索語「しすてむ」の最後の文字「む」に注目し（ステップＳ１２１０）、当該文字「む」についてのトライグラム群に注目する（ステップＳ１２１１）。注目した文字が検索語の最後の文字の場合には、その後の文字はないため（ステップＳ１２１２；ＮＯ）、検索処理は図１２Ｃのフローチャートへと移行する。
【００８６】
検索処理が図１２Ｃのフローチャートへ移行すると、次に取得部２０１は、注目したトライグラム群のうち、前の文字を先頭の文字とするトライグラムが分類されたトライグラム群の出現位置を全て取得する（ステップＳ１２１７）。すなわち、上記検索語「しすてむ」での例では、注目した最後の文字「む」を中央の文字、前の文字「て」を先頭の文字とするトライグラム「てむ＊」（＊はどの文字種でもよい）が分類されたトライグラム群の出現位置を全て、取得部２０１が取得する。
【００８７】
図１３Ｄに表された文字「む」についての２次元状の表では、当該「てむ＊」というトライグラムは、先頭の２文字（縦軸）が「たむ」〜「とむ」の範囲に該当するものであるため、当該トライグラムが分類されたトライグラム群は、太線で囲われた横一列のセルに相当するものとなる。従って、取得部２０１は、当該セル内の出現位置（２６１文字目、６９０文字目、１５６５文字目、３２８２文字目・・・、６７文字目、２９８文字目・・・等）を全て取得する。
【００８８】
図１２Ｃのフローチャートに戻って、最後の文字についての出現位置を取得すると、上記ステップＳ１２１４と同様に、特定部２０２が、保持された出現位置と連続する出現位置があるか否かを判定する（ステップＳ１２１８）。取得された出現位置が入力された検索語の文字列を構成するものであるか否かを判定するためである。
【００８９】
連続する出現位置がなければ（ステップＳ１２１８；ＮＯ）、検索対象の文書データ３００には検索語が含まれていないということになるため、特定部２０２は、「該当箇所無し」を出力し（ステップＳ１２１９）、検索処理を終了する。すなわち特定部２０２は、出力部２３０を介してモニタ２５６に「該当箇所無し」という文字を表示する等により、ユーザへその旨を出力する。
【００９０】
一方、連続する出現位置があれば（ステップＳ１２１８；ＹＥＳ）、入力された検索語が文書データ３００中に含まれているということになる。そのため、特定部２０２は、その出現位置から検索文字列の先頭文字位置を計算し、出力する（ステップＳ１２２０）。すなわち特定部２０２は、連続すると判定した出現位置に対応する検索文字列の先頭文字位置を計算し、それを検索結果としてユーザへ出力する。連続する出現位置が複数存在した場合は、特定部２０２は、原則的には全てについて検索文字列の先頭文字位置を計算し、出力する。その後、本フローチャートにて示した検索装置２の処理は終了する。
【００９１】
このとき出力結果は、出力部２３０を介しモニタ２５６に表示される等によって、ユーザへと出力される。ユーザは、当該出力結果により、記憶部２１０に記憶された文書データ３００中において、自身が入力した検索語が出現する位置を取得することができ、種々に利用することができるようになる。
【００９２】
以上のような構成により、本実施形態の検索装置２は、所望の検索文字列に対して、それを構成する文字ごとに前後の文字とあわせて転置インデックス９００から出現位置を取得し、出現位置の連続性を判定することで、当該検索文字列が文書データ３００中のどこに出現するのかを特定する。ここで用いられる転置インデックス９００は、トライグラムがその文字列に基づいて分類されたトライグラム群を単位として構成されている。そのため、検索装置２は、トライグラムを単独で単位としたものに比べ、搭載される転置インデックス９００のデータサイズを抑え、検索処理の速度をなるべく低下することなく検索を実行できる。
【００９３】
これは、例えば電子辞書や携帯電話等のような小型の電子機器のような使用できるデータ容量が限られた環境においてはとくに、転置インデックス９００のデータサイズを抑制しつつ高速な検索処理を実現する上で効果的である。
【００９４】
なお、上記実施形態は一例であり、本発明の適用範囲はこれに限られない。すなわち、種々の応用が可能であり、あらゆる実施の形態が本発明の範囲に含まれる。
【００９５】
例えば、上記実施形態では、検索装置２は、ＲＯＭ２５２のような記憶部２１０内に文書データ３００等を記憶した。しかしこれに限られず、検索装置２は、ハードディスク等の大容量記憶装置やＤＶＤ−ＲＯＭドライブを備え、文書データ３００等がハードディスクやＤＶＤ−ＲＯＭ等に記憶されるようにしてもよい。あるいは、検索装置２は、ネットワークに接続され、文書データ３００等がネットワーク上に存在するようにしてもよい。
【００９６】
また、上記実施形態では、検索装置２は、ユーザが検索語を入力する入力部２２０や検索結果を出力する出力部２３０は、制御部２００や記憶部２１０と同一の装置内に存在した。しかしこれに限られず、入力部２２０と出力部２３０は、検索装置２の外部にあってもよい。すなわち、例えば図１４に示すように、検索装置２は入力部２２０と出力部２３０を備えず、これらを備える端末装置３とネットワーク１５０を介して接続されるようにし、オンライン型の電子辞書のような情報機器として構成するようにしてもよい。
【００９７】
このとき、検索装置２と端末装置３は、それぞれが備える通信部２４０ａ，２４０ｂにより、ネットワーク１５０を介して互いにデータを通信しあう。すなわち、端末装置３のユーザが入力した検索語は、検索装置２へと送信され、制御部２００により検索処理が実行される。その後、検索結果の情報が再び端末装置３へと送信され、端末装置３のユーザへと出力される。このような構成をとることで、検索装置２内の文書データ３００等を一括して管理して複数のユーザに利用できるようになり、またユーザ側の端末装置３は、文書データ３００等を保持する必要がないため、データサイズを抑えることができるといった利点がある。
【００９８】
また、上記実施形態では、検索装置２として電子辞書のような小型の情報処理装置を想定して説明した。しかしこれに限られず、検索装置２は、ビジネス用・家庭用の一般的なコンピュータ装置や、携帯電話等の他の情報機器であってもよい。また、電子辞書における検索に限られず、種々の電子データを検索するものであってもよい。例えば、一般的なコンピュータ装置において、ハードディスク等の大容量記憶装置やＤＶＤ−ＲＯＭ等に記憶された電子ファイルのうちから、所望の検索語を含む電子ファイルを検索するものであってもよい。あるいは、ネットワークと接続され、ネットワーク上に存在するウェブページを検索するものであってもよい。
【００９９】
また、生成装置１について、上記実施形態での生成装置１は、ハードディスク１５４のような記憶部１１０に記憶されている文書データ３００をもとにして転置インデックス９００を生成し、当該生成された転置インデックス９００を記憶部１１０に記憶した。しかし、これら文書データ３００は、生成装置１内に備えられた記憶部１１０に記憶されることに限られず、通信部１４０を介して接続されるネットワーク１５０上に存在していてもよいし、あるいはＤＶＤ−ＲＯＭドライブ１５７に搭載されるＤＶＤ−ＲＯＭ内に記憶されていてもよい。
【０１００】
また、上記実施形態では、文書データ３００は、「見出し語」と「説明文」とから構成された。しかしこれらに限られず、様々な要素から構成されてもよい。例えば、「見出し語」を説明するための図や表を有するものであってもよい。あるいは、辞書における検索以外の一般的な電子ファイル等の検索では、このような「見出し語」と「説明文」といった構成要素に限らず、文書データ３００は様々な形式で文字列データを有していてもよい。
【０１０１】
また、上記実施形態では、分類部１０２がトライグラムを中間トライグラム群およびトライグラム群に分類する際、１つの中間トライグラム群およびトライグラム群に分類されるトライグラムに対応付けられた出現位置の個数の和が所定の個数を超えないように分類した。しかし出現位置の個数ではなく、文字種の個数に着目して分類してもよい。すなわち、分類部１０２は、
（ａ）共通な中央の文字を有するトライグラムがまとめられた統合トライグラム群ごとに、トライグラムを先頭の文字順に並べ、１つの中間トライグラム群に分類されるトライグラムの先頭の文字種の個数が所定の個数を超えないように、トライグラムを並び順に中間トライグラム群に分類し、
（ｂ）さらに中間トライグラム群ごとに、トライグラムを末尾の文字順に並べ、１つのトライグラム群に分類されるトライグラムの末尾の文字種の個数が所定の個数を超えないように、トライグラムを並び順にトライグラム群に分類してもよい。
【０１０２】
具体的に、１つの中間トライグラム群およびトライグラム群に分類されるトライグラムの先頭および末尾の文字種の個数を５種類とした場合について説明する。このとき、例えば文字「の」を中央の文字とするトライグラムについて、分類部１０２は、５種類の先頭の文字「あ」〜「お」を有するトライグラムを最初の中間トライグラム群としてまとめ、その後「か」〜「こ」、「さ」〜「そ」・・・というように、先頭の文字について５種類ずつ中間トライグラム群にまとめていく。さらに分類部１０２は、中間トライグラム群ごとに、５種類の末尾の文字「あ」〜「お」を有するトライグラムを最初のトライグラム群としてまとめ、その後「か」〜「こ」、「さ」〜「そ」・・・というように、末尾の文字について５種類ずつトライグラム群にまとめていく。
【０１０３】
その結果、生成される転置インデックス９００について、例えば文字「の」についてのトライグラム群と出現位置との対応関係を２次元状に表すと、図１５のようになる。すなわち、当該２次元状の表の縦軸と横軸の構成単位は、「あの」〜「おの」・・・「さの」〜「その」・・・等のように、先頭および末尾についての５個の文字種ごとに区切られたものとなる。
【０１０４】
このように、先頭および末尾の文字種の個数に基づいてトライグラム群を作成していくことで、各トライグラム群に分類されるトライグラムの種類の個数をなるべく同じ個数にすることができる。これにより、トライグラム群の出現位置の個数がなるべく同じ個数になるように分類された場合に比べ、出現位置の個数にはばらつきがでるが、各トライグラム群のトライグラムの個数が均一化されるため、一般的に扱いやすい転置インデックス９００を生成することができる。
【０１０５】
なお、本発明に係る機能を実現するための構成を予め備えた転置インデックスの生成装置および当該転置インデックスを用いた検索装置として提供できることはもとより、プログラムの適用により、既存のパーソナルコンピュータや情報端末機器等を、本発明に係る生成装置および検索装置として機能させることもできる。すなわち、上記実施形態で例示した生成装置１および検索装置２による各機能構成を実現させるための生成プログラムまたは検索プログラムを、既存のパーソナルコンピュータや情報端末機器等を制御するＣＰＵ等が実行できるように適用することで、それぞれ本発明に係る生成装置１および検索装置２として機能させることができる。また、本発明に係る転置インデックスの生成方法および当該転置インデックスを用いた検索方法は、それぞれ生成装置１および検索装置２を用いて実施できる。
【０１０６】
また、このようなプログラムの適用方法は任意であり、例えば、ＣＤ−ＲＯＭやＤＶＤ−ＲＯＭ、メモリカードなどのコンピュータ読み取り可能な記憶媒体に格納して適用できる他、例えば、インターネットなどの通信媒体を介して適用することもできる。
【０１０７】
以上、本発明の好ましい実施形態について説明したが、本発明は係る特定の実施形態に限定されるものではなく、本発明には、特許請求の範囲に記載された発明とその均等の範囲が含まれる。以下に、本願出願の当初の特許請求の範囲に記載された発明を付記する。
【０１０８】
（付記１）
文書データのうちから「３文字の文字列であるトライグラム」を、当該文書データ中での出現位置と対応付けて、抽出する抽出ステップと、
前記抽出されたトライグラムのうち中央の文字が共通なトライグラムを、先頭および末尾の文字に基づいて、トライグラム群に分類する分類ステップと、
前記分類されたトライグラム群のそれぞれに、当該トライグラム群に分類されたトライグラムに対応付けられた出現位置を対応付けて、転置インデックスを生成する生成ステップと、
を備えることを特徴とする転置インデックスの生成方法。
【０１０９】
（付記２）
前記分類ステップでは、
（ａ）前記抽出されたトライグラムのうち中央の文字が共通なトライグラムを、先頭の文字に基づいて、中間トライグラム群に分類し、
（ｂ）前記中間トライグラム群に分類されたトライグラムを、末尾の文字に基づいて、トライグラム群に分類する、
ことを特徴とする付記１に記載の転置インデックスの生成方法。
【０１１０】
（付記３）
前記分類ステップでは、
（ａ）前記抽出されたトライグラムのうち中央の文字が共通なトライグラムを、前記中間トライグラム群に分類されるトライグラムに対応付けられた出現位置の個数の和が所定の第１の個数を超えないように分類し、
（ｂ）前記中間トライグラム群に分類されたトライグラムを、前記トライグラム群に分類されるトライグラムに対応付けられた出現位置の個数が所定の第２の個数の和を超えないように分類する、
ことを特徴とする付記２に記載の転置インデックスの生成方法。
【０１１１】
（付記４）
前記分類ステップでは、
（ａ）前記抽出されたトライグラムのうち中央の文字が共通なトライグラムを、前記中間トライグラム群に分類されるトライグラムの先頭の文字種の個数が所定の第３の個数を超えないように分類し、
（ｂ）前記中間トライグラム群に分類されたトライグラムを、前記トライグラム群に分類されるトライグラムの末尾の文字種の個数が所定の第４の個数を超えないように分類する、
ことを特徴とする付記２に記載の転置インデックスの生成方法。
【０１１２】
（付記５）
付記１から４のいずれか１つに記載の生成方法によって生成された転置インデックスを用いる検索方法であって、
所望の検索文字列を構成するトライグラムのそれぞれについて、前記転置インデックスから、当該トライグラムが分類されたトライグラム群に対応付けられた出現位置を取得する取得ステップと、
前記取得された出現位置に基づいて、前記検索文字列の前記文書データにおける出現位置を特定する特定ステップと、
を備えることを特徴とする検索方法。
【０１１３】
（付記６）
前記取得ステップでは、
（ｐ）前記検索文字列の先頭の文字を中央の文字とし、先頭から２番目の文字を末尾の文字とするトライグラムが分類されたトライグラム群に対応付けられた出現位置を取得し、
（ｑ）前記検索文字列の末尾の文字を中央の文字とし、末尾から２番目の文字を先頭の文字とするトライグラムが分類されたトライグラム群に対応付けられた出現位置を取得する、
ことを特徴とする付記５に記載の検索方法。
【０１１４】
（付記７）
文書データのうちから「３文字の文字列であるトライグラム」を、当該文書データ中での出現位置と対応付けて、抽出する抽出手段と、
前記抽出されたトライグラムのうち中央の文字が共通なトライグラムを、先頭および末尾の文字に基づいて、トライグラム群に分類する分類手段と、
前記分類されたトライグラム群のそれぞれに、当該トライグラム群に分類されたトライグラムに対応付けられた出現位置を対応付けて、転置インデックスを生成する生成手段と、
を備えることを特徴とする生成装置。
【０１１５】
（付記８）
付記１から４のいずれか１つに記載の生成方法によって生成された転置インデックスを用いる検索装置であって、
所望の検索文字列を構成するトライグラムのそれぞれについて、前記転置インデックスから、当該トライグラムが分類されたトライグラム群に対応付けられた出現位置を取得する取得手段と、
前記取得された出現位置に基づいて、前記検索文字列の前記文書データにおける出現位置を特定する特定手段と、
を備えることを特徴とする検索装置。
【０１１６】
（付記９）
コンピュータを、
文書データのうちから「３文字の文字列であるトライグラム」を、当該文書データ中での出現位置と対応付けて、抽出する抽出手段、
前記抽出されたトライグラムのうち中央の文字が共通なトライグラムを、先頭および末尾の文字に基づいて、トライグラム群に分類する分類手段、
前記分類されたトライグラム群のそれぞれに、当該トライグラム群に分類されたトライグラムに対応付けられた出現位置を対応付けて、転置インデックスを生成する生成手段、
として機能させることを特徴とするコンピュータプログラム。
【０１１７】
（付記１０）
コンピュータを、
付記１から４のいずれか１つに記載の生成方法によって生成された転置インデックスを用いる検索装置として機能させるコンピュータプログラムであって、
前記コンピュータを、
所望の検索文字列を構成するトライグラムのそれぞれについて、前記転置インデックスから、当該トライグラムが分類されたトライグラム群に対応付けられた出現位置を取得する取得手段、
前記取得された出現位置に基づいて、前記検索文字列の前記文書データにおける出現位置を特定する特定手段、
として機能させることを特徴とするコンピュータプログラム。
【符号の説明】
【０１１８】
１…生成装置、２…検索装置、３…端末装置、１００…制御部、１０１…抽出部、１０２…分類部、１０３…生成部、１１０…記憶部、１２０…入力部、１３０…出力部、１４０…通信部、１５０…ネットワーク、１５１…ＣＰＵ、１５２…ＲＯＭ、１５３…ＲＡＭ、１５４…ハードディスク、１５５…キーボード、１５６…モニタ、１５７…ＤＶＤ−ＲＯＭドライブ、１５８…通信装置、２００…制御部、２０１…取得部、２０２…特定部、２１０…記憶部、２２０…入力部、２３０…出力部、２４０ａ，２４０ｂ…通信部、２５１…ＣＰＵ、２５２…ＲＯＭ、２５３…ＲＡＭ、２５５…キーボード、２５６…モニタ、３００…文書データ、９００…転置インデックス
【特許請求の範囲】
【請求項１】
文書データのうちから「３文字の文字列であるトライグラム」を、当該文書データ中での出現位置と対応付けて、抽出する抽出ステップと、
前記抽出されたトライグラムのうち中央の文字が共通なトライグラムを、先頭および末尾の文字に基づいて、トライグラム群に分類する分類ステップと、
前記分類されたトライグラム群のそれぞれに、当該トライグラム群に分類されたトライグラムに対応付けられた出現位置を対応付けて、転置インデックスを生成する生成ステップと、
を備えることを特徴とする転置インデックスの生成方法。
【請求項２】
前記分類ステップでは、
（ａ）前記抽出されたトライグラムのうち中央の文字が共通なトライグラムを、先頭の文字に基づいて、中間トライグラム群に分類し、
（ｂ）前記中間トライグラム群に分類されたトライグラムを、末尾の文字に基づいて、トライグラム群に分類する、
ことを特徴とする請求項１に記載の転置インデックスの生成方法。
【請求項３】
前記分類ステップでは、
（ａ）前記抽出されたトライグラムのうち中央の文字が共通なトライグラムを、前記中間トライグラム群に分類されるトライグラムに対応付けられた出現位置の個数の和が所定の第１の個数を超えないように分類し、
（ｂ）前記中間トライグラム群に分類されたトライグラムを、前記トライグラム群に分類されるトライグラムに対応付けられた出現位置の個数が所定の第２の個数の和を超えないように分類する、
ことを特徴とする請求項２に記載の転置インデックスの生成方法。
【請求項４】
前記分類ステップでは、
（ａ）前記抽出されたトライグラムのうち中央の文字が共通なトライグラムを、前記中間トライグラム群に分類されるトライグラムの先頭の文字種の個数が所定の第３の個数を超えないように分類し、
（ｂ）前記中間トライグラム群に分類されたトライグラムを、前記トライグラム群に分類されるトライグラムの末尾の文字種の個数が所定の第４の個数を超えないように分類する、
ことを特徴とする請求項２に記載の転置インデックスの生成方法。
【請求項５】
請求項１から４のいずれか１項に記載の生成方法によって生成された転置インデックスを用いる検索方法であって、
所望の検索文字列を構成するトライグラムのそれぞれについて、前記転置インデックスから、当該トライグラムが分類されたトライグラム群に対応付けられた出現位置を取得する取得ステップと、
前記取得された出現位置に基づいて、前記検索文字列の前記文書データにおける出現位置を特定する特定ステップと、
を備えることを特徴とする検索方法。
【請求項６】
前記取得ステップでは、
（ｐ）前記検索文字列の先頭の文字を中央の文字とし、先頭から２番目の文字を末尾の文字とするトライグラムが分類されたトライグラム群に対応付けられた出現位置を取得し、
（ｑ）前記検索文字列の末尾の文字を中央の文字とし、末尾から２番目の文字を先頭の文字とするトライグラムが分類されたトライグラム群に対応付けられた出現位置を取得する、
ことを特徴とする請求項５に記載の検索方法。
【請求項７】
文書データのうちから「３文字の文字列であるトライグラム」を、当該文書データ中での出現位置と対応付けて、抽出する抽出手段と、
前記抽出されたトライグラムのうち中央の文字が共通なトライグラムを、先頭および末尾の文字に基づいて、トライグラム群に分類する分類手段と、
前記分類されたトライグラム群のそれぞれに、当該トライグラム群に分類されたトライグラムに対応付けられた出現位置を対応付けて、転置インデックスを生成する生成手段と、
を備えることを特徴とする生成装置。
【請求項８】
請求項１から４のいずれか１項に記載の生成方法によって生成された転置インデックスを用いる検索装置であって、
所望の検索文字列を構成するトライグラムのそれぞれについて、前記転置インデックスから、当該トライグラムが分類されたトライグラム群に対応付けられた出現位置を取得する取得手段と、
前記取得された出現位置に基づいて、前記検索文字列の前記文書データにおける出現位置を特定する特定手段と、
を備えることを特徴とする検索装置。
【請求項９】
コンピュータを、
文書データのうちから「３文字の文字列であるトライグラム」を、当該文書データ中での出現位置と対応付けて、抽出する抽出手段、
前記抽出されたトライグラムのうち中央の文字が共通なトライグラムを、先頭および末尾の文字に基づいて、トライグラム群に分類する分類手段、
前記分類されたトライグラム群のそれぞれに、当該トライグラム群に分類されたトライグラムに対応付けられた出現位置を対応付けて、転置インデックスを生成する生成手段、
として機能させることを特徴とするコンピュータプログラム。
【請求項１０】
コンピュータを、
請求項１から４のいずれか１項に記載の生成方法によって生成された転置インデックスを用いる検索装置として機能させるコンピュータプログラムであって、
前記コンピュータを、
所望の検索文字列を構成するトライグラムのそれぞれについて、前記転置インデックスから、当該トライグラムが分類されたトライグラム群に対応付けられた出現位置を取得する取得手段、
前記取得された出現位置に基づいて、前記検索文字列の前記文書データにおける出現位置を特定する特定手段、
として機能させることを特徴とするコンピュータプログラム。
【請求項１】
文書データのうちから「３文字の文字列であるトライグラム」を、当該文書データ中での出現位置と対応付けて、抽出する抽出ステップと、
前記抽出されたトライグラムのうち中央の文字が共通なトライグラムを、先頭および末尾の文字に基づいて、トライグラム群に分類する分類ステップと、
前記分類されたトライグラム群のそれぞれに、当該トライグラム群に分類されたトライグラムに対応付けられた出現位置を対応付けて、転置インデックスを生成する生成ステップと、
を備えることを特徴とする転置インデックスの生成方法。
【請求項２】
前記分類ステップでは、
（ａ）前記抽出されたトライグラムのうち中央の文字が共通なトライグラムを、先頭の文字に基づいて、中間トライグラム群に分類し、
（ｂ）前記中間トライグラム群に分類されたトライグラムを、末尾の文字に基づいて、トライグラム群に分類する、
ことを特徴とする請求項１に記載の転置インデックスの生成方法。
【請求項３】
前記分類ステップでは、
（ａ）前記抽出されたトライグラムのうち中央の文字が共通なトライグラムを、前記中間トライグラム群に分類されるトライグラムに対応付けられた出現位置の個数の和が所定の第１の個数を超えないように分類し、
（ｂ）前記中間トライグラム群に分類されたトライグラムを、前記トライグラム群に分類されるトライグラムに対応付けられた出現位置の個数が所定の第２の個数の和を超えないように分類する、
ことを特徴とする請求項２に記載の転置インデックスの生成方法。
【請求項４】
前記分類ステップでは、
（ａ）前記抽出されたトライグラムのうち中央の文字が共通なトライグラムを、前記中間トライグラム群に分類されるトライグラムの先頭の文字種の個数が所定の第３の個数を超えないように分類し、
（ｂ）前記中間トライグラム群に分類されたトライグラムを、前記トライグラム群に分類されるトライグラムの末尾の文字種の個数が所定の第４の個数を超えないように分類する、
ことを特徴とする請求項２に記載の転置インデックスの生成方法。
【請求項５】
請求項１から４のいずれか１項に記載の生成方法によって生成された転置インデックスを用いる検索方法であって、
所望の検索文字列を構成するトライグラムのそれぞれについて、前記転置インデックスから、当該トライグラムが分類されたトライグラム群に対応付けられた出現位置を取得する取得ステップと、
前記取得された出現位置に基づいて、前記検索文字列の前記文書データにおける出現位置を特定する特定ステップと、
を備えることを特徴とする検索方法。
【請求項６】
前記取得ステップでは、
（ｐ）前記検索文字列の先頭の文字を中央の文字とし、先頭から２番目の文字を末尾の文字とするトライグラムが分類されたトライグラム群に対応付けられた出現位置を取得し、
（ｑ）前記検索文字列の末尾の文字を中央の文字とし、末尾から２番目の文字を先頭の文字とするトライグラムが分類されたトライグラム群に対応付けられた出現位置を取得する、
ことを特徴とする請求項５に記載の検索方法。
【請求項７】
文書データのうちから「３文字の文字列であるトライグラム」を、当該文書データ中での出現位置と対応付けて、抽出する抽出手段と、
前記抽出されたトライグラムのうち中央の文字が共通なトライグラムを、先頭および末尾の文字に基づいて、トライグラム群に分類する分類手段と、
前記分類されたトライグラム群のそれぞれに、当該トライグラム群に分類されたトライグラムに対応付けられた出現位置を対応付けて、転置インデックスを生成する生成手段と、
を備えることを特徴とする生成装置。
【請求項８】
請求項１から４のいずれか１項に記載の生成方法によって生成された転置インデックスを用いる検索装置であって、
所望の検索文字列を構成するトライグラムのそれぞれについて、前記転置インデックスから、当該トライグラムが分類されたトライグラム群に対応付けられた出現位置を取得する取得手段と、
前記取得された出現位置に基づいて、前記検索文字列の前記文書データにおける出現位置を特定する特定手段と、
を備えることを特徴とする検索装置。
【請求項９】
コンピュータを、
文書データのうちから「３文字の文字列であるトライグラム」を、当該文書データ中での出現位置と対応付けて、抽出する抽出手段、
前記抽出されたトライグラムのうち中央の文字が共通なトライグラムを、先頭および末尾の文字に基づいて、トライグラム群に分類する分類手段、
前記分類されたトライグラム群のそれぞれに、当該トライグラム群に分類されたトライグラムに対応付けられた出現位置を対応付けて、転置インデックスを生成する生成手段、
として機能させることを特徴とするコンピュータプログラム。
【請求項１０】
コンピュータを、
請求項１から４のいずれか１項に記載の生成方法によって生成された転置インデックスを用いる検索装置として機能させるコンピュータプログラムであって、
前記コンピュータを、
所望の検索文字列を構成するトライグラムのそれぞれについて、前記転置インデックスから、当該トライグラムが分類されたトライグラム群に対応付けられた出現位置を取得する取得手段、
前記取得された出現位置に基づいて、前記検索文字列の前記文書データにおける出現位置を特定する特定手段、
として機能させることを特徴とするコンピュータプログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２Ａ】
【図１２Ｂ】
【図１２Ｃ】
【図１３Ａ】
【図１３Ｂ】
【図１３Ｃ】
【図１３Ｄ】
【図１４】
【図１５】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２Ａ】
【図１２Ｂ】
【図１２Ｃ】
【図１３Ａ】
【図１３Ｂ】
【図１３Ｃ】
【図１３Ｄ】
【図１４】
【図１５】
【公開番号】特開２０１２−２０３５７９（Ｐ２０１２−２０３５７９Ａ）
【公開日】平成２４年１０月２２日（２０１２．１０．２２）
【国際特許分類】
【出願番号】特願２０１１−６６６１１（Ｐ２０１１−６６６１１）
【出願日】平成２３年３月２４日（２０１１．３．２４）
【出願人】（０００００１４４３）カシオ計算機株式会社 (8,748)
【Ｆターム（参考）】
【公開日】平成２４年１０月２２日（２０１２．１０．２２）
【国際特許分類】
【出願日】平成２３年３月２４日（２０１１．３．２４）
【出願人】（０００００１４４３）カシオ計算機株式会社 (8,748)
【Ｆターム（参考）】
[ Back to top ]