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