(57)【要約】【課題】  本文テキスト自体を走査することなく、モノグラム索引を使用して、多数の検索キーワードを含む全文検索を効率よく行うことを可能にする。【解決手段】  登録文書の文字の文書中における出現位置を文字ごとに表わすモノグラム索引と、文字列と当該文字列から想定し得る表記展開された展開後文字列の展開規則と、入力検索キーワードに基づいて展開規則から得た展開後文字列を接続し、同意的キーワードとして想定し得る複数の検索対象文字列を展開する展開手段と、複数の検索対象文字列から１文字ずつモノグラム索引を照合する際に照合履歴を識別する複数の状態と文字の組ごとの状態の遷移先および検出した検索キーワードを表わす状態遷移表を生成する状態遷移表生成手段と、状態遷移表の状態とモノグラム索引の文字と位置番号とに基づいて出現位置を照合し、複数の検索対象文字列のいずれかと一致する文字列を有する文書を一意に識別する情報の集合を生成するモノグラム索引照合手段を備えた。【選択図】        図１
2006134161.tif 000002
【特許請求の範囲】
【請求項１】
登録された文書または当該文書の書誌的情報を構成する文字の当該文書中または書誌的情報中における出現位置を、文字ごとに表わすモノグラム索引を予め生成して格納しておく格納手段と、
文字列と当該文字列から想定し得る表記展開を行って生成された展開後文字列とからなる展開規則を予め記憶する記憶手段と、
入力された検索キーワードに基づいて前記展開規則から展開後文字列を抽出し、抽出した展開後文字列を接続して同意的キーワードとして想定し得る異表記を含む複数の検索対象文字列に展開した検索対象文字列群を生成するキーワード展開手段と、
前記複数の検索対象文字列から１文字ずつモノグラム索引を照合する際に照合の履歴を識別するための複数の状態と文字の組ごとによる状態の遷移先および検出した検索キーワードとを表わす状態遷移表を生成する状態遷移表生成手段と、
前記状態遷移表の状態と前記モノグラム索引に含まれる文字と位置番号とに基づいて出現位置を照合し、前記複数の検索対象文字列のいずれかと一致する文字列を有する文書を一意に識別する情報の集合を生成するモノグラム索引照合手段と、
登録された文書が予め格納された文書格納装置から前記一意に識別する情報の集合に基づいた文書を抽出する文書取得部とを備えたことを特徴とする文書検索装置。
【請求項２】
状態遷移表生成手段は、状態と文字の組み合わせごとに遷移先の状態を表わすｇｏｔｏ表、このｇｏｔｏ表に遷移先の状態が存在しないときの遷移先を表わすｆａｉｌｕｒｅ表、各状態に対して検出した検索キーワードを表わすｏｕｔｐｕｔ表および各状態に対して他の状態に遷移可能な文字の集合を表わすｓｕｃｃｅｓｓ表からなる状態遷移表を生成し、
モノグラム索引照合手段は、前記ｇｏｔｏ表に基づいて状態と文字の組み合わせにより状態の遷移を行い、前記ｇｏｔｏ表に遷移先の状態が存在しない場合に前記ｆａｉｌｕｒｅ表が示す遷移先に状態の遷移を行い、前記ｏｕｔｐｕｔ表に基づいて各状態に対して検出した検索キーワードを決定し、前記ｓｕｃｃｅｓｓ表に基づいて選択した遷移可能な文字を対象にモノグラム索引の照合を行うことを特徴とする請求項１記載の文書検索装置。
【請求項３】
登録された文書または当該文書の書誌的情報を構成する複数の文字および複数の隣り合う所定数の文字による組の当該文書中または書誌的情報中における出現位置を、当該複数の文字および文字の組ごとに表わすモノグラム索引を含んだＮグラム索引を予め生成して格納しておく格納手段と、
文字列と当該文字列から想定し得る表記展開を行って生成された展開後文字列とからなる展開規則を予め記憶する記憶手段と、
入力された検索キーワードに基づいて前記展開規則から展開後文字列を抽出し、抽出した展開後文字列を接続して同意的キーワードとして想定し得る異表記を含む複数の検索対象文字列に展開した検索対象文字列群を生成するキーワード展開手段と、
展開された複数の検索対象文字列から文字の組を単位としてＮグラム索引を照合する際に照合の履歴識別をするための複数の状態と、文字の組み合わせの組ごとによる状態の遷移先および検出した検索キーワードとを表わす状態遷移表を生成する状態遷移表生成手段と、
前記Ｎグラム状態遷移表の状態と前記Ｎグラム索引に含まれる文字の組と位置番号とに基づいて出現位置を照合し、前記複数の検索対象文字列のいずれかと一致する文字列を有する文書を一意に識別する情報の集合を生成するＮグラム索引照合手段と、
登録された文書が予め格納された文書格納装置から前記一意に識別する情報の集合に基づいた文書を抽出する文書取得部とを備えたことを特徴とする文書検索装置。
【請求項４】
Ｎグラム状態遷移表生成手段は、状態と複数の文字による組の組み合わせごとに遷移先の状態を表わすＮグラムｇｏｔｏ表、このｇｏｔｏ表に遷移先の状態が存在しないときの遷移先を表わすｆａｉｌｕｒｅ表、各状態に対して検出した検索キーワードを表わすｏｕｔｐｕｔ表、各状態とＮグラムの組み合わせに対して検出した検索キーワードを表わすＮグラムｏｕｔｐｕｔ表および各状態に対して他の状態に遷移可能な文字の組の集合を表わすＮグラムｓｕｃｃｅｓｓ表からなるＮグラム状態遷移表を生成し、
Ｎグラム索引照合手段は、前記Ｎグラムｇｏｔｏ表に基づいて状態と文字の組み合わせにより状態の遷移を行い、前記Ｎグラムｇｏｔｏ表に遷移先の状態が存在しない場合に前記ｆａｉｌｕｒｅ表が示す遷移先に状態の遷移を行い、前記ｏｕｔｐｕｔ表と前記Ｎグラムｏｕｔｐｕｔ表に基づいて各状態に対して検出した検索キーワードを決定し、前記Ｎグラムｓｕｃｃｅｓｓ表に基づいて選択した遷移可能な文字の組を対象にＮグラム索引の照合を行うことを特徴とする請求項３記載の文書検索装置。
【請求項５】
登録された文書または当該文書の書誌的情報を構成する文字の当該文書中または書誌的情報中における出現位置を文字ごとに表わすモノグラム索引と、文字列と当該文字列から想定し得る表記展開を行って生成された展開後文字列とからなる展開規則とを用いるコンピュータの文書検索プログラムであって、
入力された検索キーワードに基づいて前記展開規則から展開後文字列を抽出し、抽出した展開後文字列を接続して同意的キーワードとして想定し得る異表記を含む複数の検索対象文字列を展開し、展開された複数の検索対象文字列から１文字ずつ前記モノグラム索引を照合する際に照合の履歴を識別するための複数の状態と、文字の組ごとの状態の遷移先および検出した検索キーワードとを表わす状態遷移表を生成し、前記状態遷移表の状態と前記モノグラム索引に含まれる文字と位置番号とに基づいて出現位置を照合し、前記複数の検索対象文字列のいずれかと一致する文字列を有する文書を一意に識別する情報の集合を生成するモノグラム索引の照合を行い、登録された文書が予め格納された文書格納装置から前記一意に識別する情報の集合に基づいた文書を抽出することを特徴とする文書検索プログラム。
【請求項６】
状態遷移表として、状態と文字の組み合わせごとに遷移先の状態を表わすｇｏｔｏ表と、このｇｏｔｏ表に遷移先の状態が存在しないときの遷移先を表わすｆａｉｌｕｒｅ表と、各状態に対して検出した検索キーワードを表わすｏｕｔｐｕｔ表と、各状態に対して他の状態に遷移可能な文字の集合を表わすｓｕｃｃｅｓｓ表とを順次生成し、前記ｇｏｔｏ表に基づいて状態と文字の組み合わせにより状態の遷移を行い、前記ｇｏｔｏ表に遷移先の状態が存在しない場合に前記ｆａｉｌｕｒｅ表が示す遷移先に状態の遷移を行い、前記ｏｕｔｐｕｔ表に基づいて各状態に対して検出した検索キーワードを決定し、前記ｓｕｃｃｅｓｓ表に基づいて選択した遷移可能な文字を対象にモノグラム索引の照合を行うことを特徴とする請求項５記載の文書検索プログラム。
【請求項７】
登録された文書または当該文書の書誌的情報を構成する複数の文字および複数の隣り合う所定数の文字による組の当該文書中または書誌的情報中における出現位置を、当該複数の文字および文字の組ごとに表わすモノグラム索引を含んだＮグラム索引と、文字列と当該文字列から想定し得る表記展開を行って生成された展開後文字列とからなる展開規則とを用いるコンピュータの文書検索プログラムであって、
入力された検索キーワードに基づいて前記展開規則から展開後文字列を抽出し、抽出した展開後文字列を接続して同意的キーワードとして想定し得る異表記を含む複数の検索対象文字列を展開し、展開された複数の検索対象文字列から文字の組を単位として前記Ｎグラム索引を照合する際に照合の履歴識別をするための複数の状態と、文字の組み合わせの組ごとの状態の遷移先および検出した検索キーワードとを表わす状態遷移表を生成し、前記Ｎグラム状態遷移表の状態と前記Ｎグラム索引に含まれる文字の組と位置番号とに基づいて出現位置を照合し、前記複数の検索対象文字列のいずれかと一致する文字列を有する文書を一意に識別する情報の集合を生成するＮグラム索引の照合を行い、登録された文書が予め格納された文書格納装置から前記一意に識別する情報の集合に基づいた文書を抽出することを特徴とする文書検索プログラム。
【請求項８】
Ｎグラム状態遷移表として、状態と複数の文字の組の組み合わせごとに遷移先の状態を表わすＮグラムｇｏｔｏ表と、このｇｏｔｏ表に遷移先の状態が存在しないときの遷移先を表わすｆａｉｌｕｒｅ表と、各状態に対して検出した検索キーワードを表わすｏｕｔｐｕｔ表と、各状態とＮグラムの組み合わせに対して検出した検索キーワードを表わすＮグラムｏｕｔｐｕｔ表と、各状態に対して他の状態に遷移可能な文字の組の集合を表わすＮグラムｓｕｃｃｅｓｓ表とを順次生成し、
前記Ｎグラムｇｏｔｏ表に基づいて状態と文字の組み合わせにより状態の遷移を行い、前記Ｎグラムｇｏｔｏ表に遷移先の状態が存在しない場合に前記ｆａｉｌｕｒｅ表が示す遷移先に状態の遷移を行い、前記ｏｕｔｐｕｔ表と前記Ｎグラムｏｕｔｐｕｔ表に基づいて各状態に対して検出した検索キーワードを決定し、前記Ｎグラムｓｕｃｃｅｓｓ表に基づいて選択した遷移可能な文字の組を対象にＮグラム索引の照合を行うことを特徴とする請求項７記載の文書検索プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、情報検索処理の分野において、文書中に出現した文字列の全文検索を行い、複数の検索対象キーワードの検索、異表記検索、同義語・類義語検索、異体字検索などを高速に行う文書検索装置および文書検索プログラムに関するものである。
【背景技術】
【０００２】
近年、大量の電子文書の蓄積が進み、文書データベースからの効率の良い文書の検索方法が求められている。全文検索は、指定した文字列を文書の全体から探し出す方法として近年広く利用されている。この全文検索には、検索時に文書に含まれるテキストを直接照合する方法と、予め索引を生成しその索引を検索する方法がある。このうち、予め索引を生成する方法は、与えられた検索キーワードに関連して限られた情報だけを索引から読み出せばよいため、テキストをすべて照合する方式と比較して検索速度において優れている。索引の方式としてはＮグラム索引（ｎ−ｇｒａｍ索引）と呼ばれる方式が広く用いられている。ＮグラムとはＮ個の文字の並びであり、Ｎグラム索引とは、Ｎ個の文字の並びごとにその出現する位置を位置情報としてリスト化し、転置索引によって検索可能にしたものである。Ｎグラム索引は、検索漏れがなく、検索速度が速い検索方法として広く用いられている。Ｎの値は可変であるが、日本語の場合、Ｎ＝１（１グラム、あるいはモノグラム、ユニグラムとも呼ばれる）、Ｎ＝２（２グラム、あるいはバイグラムとも呼ばれる）が使われることが多い（例えば、非特許文献１参照）。
【０００３】
一般に、自然言語では同一の概念に対して異なる表現が存在する。このような表現の例には、「コンピュータ」、「計算機」のような同義語や、「障害」、「故障」のような類義語、「バ」と「ヴァ」のような異表記、「辺」、「邊」、「邉」のような異体字、英語などに見られる語尾変化（ステム）など、様々な種類が存在する。文書の作成者には一つの概念に対して多数の表現方法を用いることが許されているため、検索時に単純に一つの表現だけを検索キーワードとして指定したのでは、表現の差異により、意図した文書が見つからないことがある。このような場合、ユーザは、考え付く表記を列挙し、そのいずれかが含まれる文書を検索することになるが、この場合、表記の組み合わせが非常に多くなることがある。
【０００４】
多数の文字列の照合を同時に効率的に行う方法としてＡｈｏ−Ｃｏｒａｓｉｃｋ法と呼ばれる方法が知られている。Ａｈｏ−Ｃｏｒａｓｉｃｋ法については、例えば非特許文献１にも記載されている。この方法は、文書に含まれるテキストを直接走査することによって文字列照合を行う方式であり、検索キーワードに関わらず、すべての文書の内容を読み出すことが必要となる。このため、索引を使用する検索方法と比較して検索速度が低下するという問題がある。
【０００５】
一方、ユーザの指定した検索キーワードから自動的に同義語・類義語や異表記の展開を行う方法も知られている（例えば、特許文献１参照）。この方法では、「文字成分表」と呼ぶ、文字とその文字を含む文書との対応付けを示す表を用いて、検索対象とする文書を限定した後、予めテキスト本文の中から助詞や接続詞などの付属語を削除すると共に、繰り返し現れる単語を排除した「凝縮本文」と呼ばれるデータファイルをスキャンし、指定されたキーワードが記述されている文書だけを抽出した後に、抽出された本文のテキストファイルをストリングサーチエンジンによって走査する。ストリングサーチエンジンによる走査時には、検索条件式に対して同義語や異表記の展開を行った後、展開されたキーワードを受理する有限オートマトンを生成し、その状態遷移表に従って指定されたキーワード群を入力凝縮本文から探し出す。このような方法によって、抽出された本文のテキストデータを一回走査するだけで探索することを可能にしている。
【０００６】
しかし、特許文献１に示されるような検索方法は、走査の対象とするテキストファイルの数を事前に絞ることにより、本文サーチの回数を削減しているものの、本文サーチには依然として対応する文書のテキスト全体の読み出しを必要としており、索引を使用する検索方法と比較すると検索速度が低下する。また、専用のハードウェアによって文書の照合を高速化する方法も示されているが、このような特殊なハードウェアによる方法では、文書検索装置のコストの増加を招くことになる。
【０００７】
【特許文献１】特許第２９８６８６５号公報
【非特許文献１】北  研二・津田和彦・獅々堀正幹著「情報検索アルゴリズム」共立出版
【発明の開示】
【発明が解決しようとする課題】
【０００８】
従来の文書検索装置は、以上のように構成されているため、複数の検索対象キーワードの検索を行う際に、検索時間が長くなるという問題があった。
【０００９】
この発明は、上記問題点を解決するためになされたもので、本文テキスト自体を走査することなく、モノグラム索引またはＮグラム索引を使用して、多数の検索キーワードを含む全文検索を効率よく行うことを可能にする文書検索装置および文書検索プログラムを得ることを目的とする。
【課題を解決するための手段】
【００１０】
この発明に係る文書検索装置は、登録された文書または当該文書の書誌的情報を構成する文字の当該文書中または書誌的情報中における出現位置を、文字ごとに表わすモノグラム索引を予め生成して格納しておく格納手段と、文字列と当該文字列から想定し得る表記展開を行って生成された展開後文字列とからなる展開規則を予め記憶する記憶手段と、入力された検索キーワードに基づいて展開規則から展開後文字列を抽出し、抽出した展開後文字列を接続して同意的キーワードとして想定し得る異表記を含む複数の検索対象文字列に展開した検索対象文字列群を生成するキーワード展開手段と、複数の検索対象文字列から１文字づつモノグラム索引を照合する際に照合の履歴を識別するための複数の状態と、文字の組ごとの状態の遷移先および検出した検索キーワードとを表わす状態遷移表を生成する状態遷移表生成手段と、この状態遷移表の状態とモノグラム索引に含まれる文字と位置番号とに基づいて出現位置を照合し、複数の検索対象文字列のいずれかと一致する文字列を有する文書を一意に識別する情報の集合を生成するモノグラム索引照合手段と、登録された文書が予め格納された文書格納装置から一意に識別する情報の集合に基づいた文書を抽出する文書取得部とを備えたものである。
【発明の効果】
【００１１】
この発明によれば、１回の索引の走査だけで一つの検索キーワードに対して想定しえる異表記の複数の検索キーワードを生成し、その異表記の複数の検索キーワードで同時に索引照合を行うことができるようにしたため、複数の検索キーワードを別々に入力して繰り返し索引照合を行う方法と比較して、効率的な検索を可能にする効果がある。また、検索の際には、文書中のテキストをすべて走査する必要はなく、モノグラム索引に含まれている位置情報だけを参照すればよいため、テキストをすべて走査する方法と比較して、より効率的な検索を可能にする効果がある。
【発明を実施するための最良の形態】
【００１２】
実施の形態１．
図１はこの発明の実施の形態１による文書検索装置の構成を示すブロック図である。図において、文書検索装置１は、モノグラム索引生成部２、キーワード展開部３、状態遷移表生成部４、モノグラム索引照合部５、展開規則７の記憶手段、文書格納部１７、文書取得部１８、さらに内部もしくは外部に設けられるモノグラム索引６の格納手段、文書格納装置１６を備えている。
展開規則７は、文字列と当該文字列から想定し得る表記展開を行って生成される展開後文字列とからなるデータで、予め記憶手段に記憶されているものである。文書１１は、文書検索装置１に登録されるデータである。モノグラム索引６は、登録された文書または当該文書から作成された書誌的情報を構成する文字の文書中または書誌的情報中における出現位置を文字ごとに表わし、文書の登録時にモノグラム索引生成部２で予め生成され格納手段に格納されるデータである。検索キーワード１２は、ユーザによって文書の検索時に入力されるデータで、検索対象となる文書に使用されていると想定される語句である。検索対象文字列群１３は、入力された検索キーワード１２に基づいて展開規則７にある展開後文字列を接続して展開したデータで、キーワードとして想定し得る異表記を含む複数の検索対象文字列である。状態遷移表１４は、状態遷移表生成部４によって生成されるデータ表で、複数の検索対象文字列から１文字ずつモノグラム索引を照合する際に、照合の履歴を識別するために保持する複数の状態と、文字の組ごとの状態の遷移先および検出した検索キーワードとを表わしている。検索結果１５は、モノグラム索引照合部５によって生成される文書を一意に識別する情報、例えば検索結果識別子などの集合である。文書格納装置１６は、登録された文書を格納しておく記憶装置である。文書格納部１７は、文書１１を文書格納装置１６に格納する手段である。文書取得部１８は、検索結果１５に対応した文書、すなわち検索結果文書１９を文書格納装置１６から取り出す手段である。検索結果文書１９は、検索結果１５によって識別される文書であり、ユーザに対して表示するために出力されるデータである。なお、この文書検索装置１の構成は、コンピュータ、記憶装置およびコンピュータにインストールされる処理プログラムによって実現できるものである。
【００１３】
検索装置１において登録され検索対象とされる文書１１についての一例を図２示す。図２の文書１１がモノグラム索引生成部２により生成されたモノグラム索引６のデータ構成を図３に例示する。
図３において、２２は文書１１、すなわち「本日のイヴェントは・・・」内に出現する文字の集合を表わす。２３は各文字に対応する位置情報であり、文字が文書１１中で出現する位置を表わす位置番号２４の集合である。以下、文字を「ｃ」とした場合、その位置情報を、
ｐｏｓｉｔｉｏｎ（ｃ）＝｛ｐ０，ｐ１，ｐ２，…｝
と表記することにする。ここで、ｐ０，ｐ１，ｐ２，…は位置番号を表わす。これを、図３の例に当てはめると、
ｐｏｓｉｔｉｏｎ（「本」）＝｛１，…｝
ｐｏｓｉｔｉｏｎ（「ヴ」）＝｛５，…｝
のように表わされる。
【００１４】
次に、展開規則７の例を図４に示す。図において、３１は展開の対象となる文字列であり、３２は文字列３１に対応して展開された文字列（これを展開後文字列とする）である。例えば、文字列「べ」は「ヴェ」と展開でき、文字列「ェ」は「エ」と展開でき、文字列「エ」は「ヱ」と展開できることを表わしている。
キーワード展開部３により生成される検索対象文字列群１３の一例を図５に示す。入力された検索キーワードを「イベント」としたとき、図４に示される展開規則７の展開後文字列を接続して生成された検索対象文字列は「イベント」、「イヴェント」、「イヴエント」および「イヴヱント」となることを表わしている。これらの検索対象文字列は、入力された検索キーワードに対して同意的キーワードとして想定し得る異表記の同意的文字列を形成している。
【００１５】
状態遷移表１４は、モノグラム索引照合部５で複数の検索対象文字列から１文字づつモノグラム索引を照合する際に用いられるが、状態遷移表生成部４により生成される。この状態遷移表１４は、照合の履歴を識別するために保持する複数の状態と文字の組ごとに状態の遷移先および検出した検索キーワードとを表わしたもので、図６に示される全体構成からなる。すなわち、ｇｏｔｏ表４１、ｆａｉｌｕｒｅ表４２、ｏｕｔｐｕｔ表４３およびｓｕｃｃｅｓｓ表４４を構成要素としている。以下、これらの各表について説明する。
モノグラム索引照合部５は複数の状態を持つ。ここで、モノグラム索引照合部５のとり得る複数の状態をｓ０，ｓ１，…，ｓＮとし、その集合を状態集合Ｓとする。また、状態集合Ｓには、状態の遷移に失敗したことを示す特殊な状態ｆａｉｌが含まれる。したがって、状態集合Ｓは、
Ｓ＝｛ｓ０，ｓ１，…，ｓＮ，ｆａｉｌ｝
と表記できる。
図５に例示した検索対象文字列１３に対応して生成されるｇｏｔｏ表４１を図７に示す。Ｃを文字集合２２（図３）とするとき、ｇｏｔｏ関数は、
ｓ１＝ｇｏｔｏ（ｓ０，ｃ）        ｓ０，ｓ１∈Ｓ、  ｃ∈Ｃ
と表わされ、状態ｓ０において文字ｃが入力されたときに状態ｓ１に遷移することを示す。したがって、ｇｏｔｏ表４１はすべての状態∈Ｓと文字ｃ∈Ｃの組に対するｇｏｔｏ関数ｇｏｔｏ（ｓ，ｃ）の値、すなわち遷移先の状態を表わす。図７のｇｏｔｏ表４１を状態遷移図で表記すると図８のようになる。ただし、図８ではｆａｉｌ状態は省略している。また、各状態ｓｉは単にｉ（すなわち、数字）を用いて記述している。
【００１６】
図５の検索対象文字列１３に対応して生成されるｆａｉｌｕｒｅ表４２を図９に示す。Ｓを状態集合とするとき、ｆａｉｌｕｒｅ関数は、
ｓ２＝ｆａｉｌｕｒｅ（ｓ１）        ｓ１，ｓ２∈Ｓ
のようになり、状態ｓ１においてｇｏｔｏ（ｓ１，ｃ）＝ｆａｉｌのとき、状態ｓ２に遷移することを示す。すなわち、ｆａｉｌｕｒｅ表４２は、ｇｏｔｏ表に遷移先の状態が存在しないときの遷移先を表わしており、そのため、すべての状態ｓに対してｆａｉｌｕｒｅ（ｓ）の値を保持する表である。この例では、すべての状態ｓに対してｆａｉｌｕｒｅ関数は状態ｓ０に遷移する。
【００１７】
図５の検索対象文字列１３に対応して生成されるｏｕｔｐｕｔ表４３を図１０に示す。Ｓを状態集合、Ｋを検索対象文字列群に含まれる文字列の集合とするとき、ｏｕｔｐｕｔ関数は、
ｋ＝ｏｕｔｐｕｔ（ｓ）        ｓ∈Ｓ、  ｋ∈Ｋ
のようになる。この関数は、状態ｓにおいて文字列ｋを検出したことを表わしている。ｏｕｔｐｕｔ表は、すべての状態ｓに対して検出したｏｕｔｐｕｔ（ｓ）の値、すなわち検索キーワードを保持する表である。なお、φは空集合を意味する。
図５の検索対象文字列１３のそれぞれに対応して生成されるｓｕｃｃｅｓｓ表４４を図１１に示す。Ｓを状態集合、Ｃを文字集合２２とするとき、ｓｕｃｃｅｓｓ関数は、
ｄ＝ｓｕｃｃｅｓｓ（ｓ）        ｓ∈Ｓ、  ｄ∈｛Ｃ｝
のようになり、状態ｓにおいてｓ０以外の状態に遷移可能な文字２１の集合（ｓ＝ｓ０の時）、および状態ｓにおいてｆａｉｌ以外の状態に遷移可能な文字２１の集合（ｓ≠ｓ０の時）を示す。したがって、ｓｕｃｃｅｓｓ表４４は、すべての状態ｓに対してｓｕｃｃｅｓｓ（ｓ）の値、すなわち他の状態に遷移可能な文字の集合を保持する表である。
【００１８】
次に文書の登録の動作について説明する。
文書１１が登録されたとき、モノグラム索引生成部２により、その文書を構成する文字の文書中における出現位置を、文字ごとに表わすモノグラム索引６が生成され、記憶手段に格納される。文書中に、例えば図２に示す「本日のイヴェントは…」という文字列が存在する場合、図３に示されるモノグラム索引６が生成される。索引のエントリは各文字の文書中の出現位置を示しており、例えば「イ」の出現位置情報に位置番号「４」が含まれるのは、「イ」が４文字目に出現するということを示している。このモノグラム索引６は、例えば非特許文献１に示される周知の方法で生成できるので、ここでは詳細な記述は省略する。以下では、図２に示す文書１１以外にも多数の登録された文書について、同様な方法でモノグラム索引６が生成され記憶手段に格納されているものとする。一方、登録された文書は文書格納部１７によって文書格納装置１６に格納される。
【００１９】
次に、検索キーワード１２として「イベント」が入力された例について、文書検索の手順を図１２のフローチャートに従って説明する。
ユーザにより文字列「イベント」が検索キーワード１２として入力されると、キーワード展開部３において、検索キーワード１２は展開規則７の展開後文字列を接続して同意的キーワードとして想定し得る異表記を含む複数の展開文字列に展開され、検索対象文字列群１３を構成する（ステップＳＴ２０１）。検索キーワードの文字列「イベント」に対し、図４に示す展開規則７の展開後文字列を接続して、同意的キーワードとして想定し得る異表記の文字列、すなわち図５に示す検索対象文字列群１３の「イベント」、「イヴェント」、「イヴエント」および「イヴヱント」という４種類の展開文字列が生成される。このような異表記展開の方法については、例えば特許文献１に示される方法などによって行えばよい。
【００２０】
次に、状態遷移表生成部４において、検索対象文字列群１３から状態遷移表１４が生成される（ステップＳＴ２０２）。この状態遷移表生成の詳細については後述する。次に、すべての文書について処理を行うため変数ｋを１に初期化し（ステップＳＴ２０３）、すべての文書について以下の処理を繰り返す（ステップＳＴ２０４）。
モノグラム索引照合部５は、ｋ番目の文書について、モノグラム索引照合を行う（ステップＳＴ２０５）。このモノグラム索引照合の詳細については後述する。次の文書について検索を行うため、変数ｋに１を加える（ステップＳＴ２０６）。ステップＳＴ２０４〜ＳＴ２０６を繰り返し、すべての文書について処理を行ったら終了する（ステップＳＴ２０４）。
【００２１】
状態遷移表生成部４は、キーワード展開部３で展開された複数の検索対象文字列から１文字づつモノグラム索引６を照合する際に照合の履歴を識別するための複数の状態と、文字の組ごとの状態の遷移先および検出した検索キーワードを表わす状態遷移表を生成する。図１３に状態遷移表１４の生成（ステップＳＴ２０２）の手順を示す。
状態遷移表１４は、ｇｏｔｏ表４１の生成（ステップＳＴ３０１）、ｆａｉｌｕｒｅ表４２の生成（ステップＳＴ３０２）、ｏｕｔｐｕｔ表４３の生成（ステップＳＴ３０３）、ｓｕｃｃｅｓｓ表４４の生成（ステップＳＴ３０４）を順次実行することによって生成される。このうち、ステップＳＴ３０１〜ＳＴ３０３については、非特許文献１に示されている方法により生成することができるので、これらの詳細についてはここでは省略する。残りのｓｕｃｃｅｓｓ表４４の生成（ステップＳＴ３０４）の手順を図１４のフローチャートにより以下で説明する。
【００２２】
まず、状態ｓ＝ｓ０に対応するｓｕｃｃｅｓｓ（ｓ０）を生成するため、集合ｓｕｃｃｅｓｓ（ｓ０）を空にし（ステップＳＴ４０１）、変数ｊを１に初期化する（ステップＳＴ４０２）。ここで、変数ｊは文字集合Ｃ＝｛ｃ１，ｃ２，…，ｃｊ，…｝の中の処理中の要素の番号を表わす。
文字集合Ｃ＝｛ｃ１，ｃ２，…，ｃｊ，…｝に含まれるすべての文字ｃｊについて以下の処理を行う（ステップＳＴ４０３）。状態ｓ＝ｓ０と文字ｃｊに対するｇｏｔｏ関数ｇｏｔｏ（ｓ０，ｃｊ）の値がｓ０であるかどうかを判定する（ステップＳＴ４０４）。ｇｏｔｏ（ｓ０，ｃｊ）の値がｓ０であればステップＳＴ４０６に進む。一方、ｇｏｔｏ（ｓ０，ｃｊ）の値がｓ０でなければ、文字ｃｊによってｆａｉｌでない状態への遷移を行うことができるのでｓｕｃｃｅｓｓ（ｓ０）にｃｊを加える（ステップＳＴ４０５）。ステップＳＴ４０６では、次の文字を調べるためｊに１を加え、ステップＳＴ４０３に進む。以下、文字集合Ｃ＝｛ｃ１，ｃ２，…，ｃｊ，…｝に含まれるすべての文字ｃｊについて処理を終えるまでステップＳＴ４０３〜ＳＴ４０６を繰り返す。すべての文字ｃｊについて処理を終えたらステップＳＴ４０７に進む。
【００２３】
ステップＳＴ４０７では、状態ｓｉ（ｉ＝１，２，…）に関するｓｕｃｃｅｓｓ（ｓｉ）を生成するため、変数ｉを１に初期化する。次に、状態ｓｉ（ｉ＝１，２，…）について以下を繰り返す（ステップＳＴ４０８）。
集合ｓｕｃｃｅｓｓ（ｓｉ）を空にし（ステップＳＴ４０９）、変数ｊを１に初期化する（ステップＳＴ４１０）。ここで、変数ｊは文字集合Ｃ＝｛ｃ１，ｃ２，…，ｃｊ，…｝における処理中の要素の番号を表す。文字集合Ｃ＝｛ｃ１，ｃ２，…，ｃｊ，…｝に含まれるすべての文字ｃｊについて以下の処理を行う（ステップＳＴ４１１）
【００２４】
状態ｓ＝ｓｉと文字ｃｊに対するｇｏｔｏ関数ｇｏｔｏ（ｓｉ，ｃｊ）の値がｆａｉｌであるかどうかを判定する（ステップＳＴ４１２）。ｆａｉｌであればステップＳＴ４１４に進む。一方、ｆａｉｌでなければ、文字ｃｊによってｆａｉｌでない状態への遷移を行うことができるのでｓｕｃｃｅｓｓ（ｓｉ）にｃｊを加える（ステップＳＴ４１３）。次に、次の文字を調べるためｊに１を加え、ステップＳＴ４１１に進む（ステップＳＴ４１４）。以下、文字集合Ｃ＝｛ｃ１，ｃ２，…，ｃｊ，…｝に含まれるすべての文字ｃｊについて処理を終えるまでステップＳＴ４１１〜ＳＴ４１４を繰り返し、すべての文字ｃｊについて処理を終えたらステップＳＴ４１５に進む。ステップＳＴ４１５では、次の状態を調べるためｉに１を加え、ステップＳＴ４０８に進む。以下、状態ｓｉ（ｉ＝１，２，…）について処理を終えるまでステップＳＴ４０８〜ＳＴ４１５を繰り返す。ステップＳＴ４０８で、すべての状態ｓｉ（ｉ＝１，２，…）について処理を終えると、最後にｓｕｃｃｅｓｓ（ｆａｉｌ）を空とする（ステップＳＴ４１６）。
【００２５】
モノグラム索引照合部５では、状態遷移表１４に示される状態とモノグラム索引６に含まれる文字と位置番号とに基づいて出現位置を照合し、複数の検索対象文字列のいずれかと一致する文字列を有する文書を一意に識別する情報の集合を、検索結果として生成する。この場合、ｇｏｔｏ表に基づいて状態と文字の組み合わせにより状態の遷移を行い、ｇｏｔｏ表に遷移先の状態が存在しない場合にはｆａｉｌｕｒｅ表が示す遷移先に状態の遷移を行い、ｏｕｔｐｕｔ表に基づいて各状態に対して検出した検索キーワードを決定し、ｓｕｃｃｅｓｓ表に基づいて選択した遷移可能な文字を対象にモノグラム索引の照合を行う。文書１１のモノグラム索引照合（ステップＳＴ２０５）の詳細手順を図１５により説明する。
まず状態ｓをｓ０に初期化し（ステップＳＴ５０１）、文字位置ｉを１に初期化する（ステップＳＴ５０２）。次に、文字位置ｉが文書中の全文字数ｍを超えたか否かを判定する（ステップＳＴ５０３）。この場合、ｉ＝１であり、条件は成立しないため、ステップＳＴ５０４に進む。
ｓｕｃｃｅｓｓ（ｓ）に含まれるすべての文字ｃｊを調べ、ｐｏｓｉｔｉｏｎ（ｃｊ）に含まれる位置番号の中から、ｉを超えない最小の位置番号ｐ∈ｐｏｓｉｔｉｏｎ（ｃｊ）を持つ文字ｃｊを選ぶ（ステップＳＴ５０４）。この例の場合は、ｓｕｃｃｅｓｓ（ｓ０）＝｛イ｝であり、ｐｏｓｉｔｉｏｎ（イ）＝｛４，…｝であるから、最小の位置番号ｐ＝４であり、このときｃｊ＝イである。
【００２６】
状態ｓのｇｏｔｏ関数により、次の状態を決める（ステップＳＴ５０５）。この場合、ｇｏｔｏ（ｓ０，イ）＝ｓ１なので、ｓ＝ｓ１となる。状態ｓのｏｕｔｐｕｔ関数により、出力を決める（ステップＳＴ５０６）。この場合、ｏｕｔｐｕｔ（ｓ１）＝φなので出力は行わず、ステップＳＴ５０８に進み、文字位置ｉを１だけ進めて、ｉ＝５とする。ｓｕｃｃｅｓｓ（ｓ）に含まれるすべての文字ｃｊを調べ、ｉ∈ｐｏｓｉｔｉｏｎ（ｃｊ）となるｃｊが存在するかどうかを調べる（ステップＳＴ５０９）。その判定（ステップＳＴ５１０）で、文字ｃｊが存在するならばステップＳＴ５０５へ進む。存在しないならばステップＳＴ５１１へ進む。この場合は、ｓｕｃｃｅｓｓ（ｓ１）＝｛べ、ヴ｝であり、ｐｏｓｉｔｉｏｎ（ヴ）＝｛５，…｝であるから、文字ｃｊ＝ヴ  が存在し、ステップＳＴ５０５に進むことになる。
【００２７】
以下同様に、ｓ１→ｓ５→ｓ６→ｓ７の順に状態遷移を繰り返しながら、ステップＳＴ５０５〜ＳＴ５１０を繰り返し、ステップＳＴ５０５に進む。
ステップＳＴ５０５では、状態ｓのｇｏｔｏ関数により、次の状態を決める。この場合、ｇｏｔｏ（ｓ７，イ）＝ｓ８なので、ｓ＝ｓ８となる。状態ｓのｏｕｔｐｕｔ関数により、出力を決める（ステップＳＴ５０６）。この場合、ｏｕｔｐｕｔ（ｓ８）＝「イヴェント」となるのでステップＳＴ５０７に進む。ステップＳＴ５０７では、文字列「イヴェント」を検出したことを出力する。次に、文字位置ｉを１だけ進めて、ｉ＝９とする（ステップＳＴ５０８）。ｓｕｃｃｅｓｓ（ｓ）に含まれるすべての文字ｃｊを調べ、ｉ∈ｐｏｓｉｔｉｏｎ（ｃｊ）となる文字ｃｊが存在するかどうかを調べる（ステップＳＴ５０９）。この場合は、ｓｕｃｃｅｓｓ（ｓ８）＝φなので文字ｃｊは存在しないので、判定（ステップＳＴ５１０）で、ステップＳＴ５１１へ進むことになる。ステップＳＴ５１１では、状態ｓのｆａｉｌｕｒｅ関数により、次の状態を決める。この場合、ｆａｉｌｕｒｅ（ｓ８）＝ｓ０なので、ｓ＝ｓ０となる。以下、同様に繰り返し、文字位置ｉが全文字数ｍを超えるまでステップＳＴ５０３〜ＳＴ５１１を繰り返す。文字位置ｉが全文字数ｍを超えると終了する（ステップＳＴ５０３）。
次に、文書取得部１８により、検索結果１５によって検索結果文書１９が文書格納装置１６から取り出され、ユーザに対して表示される。
【００２８】
以上のように、この実施の形態１の文書検索装置は構成されているので、１回の索引の走査だけで一つの検索キーワードに対して想定しえる異表記の複数の検索キーワードを生成し、その異表記の複数の検索キーワードで同時に索引照合を行うことができるようにしたため、複数の検索キーワードを別々に入力して繰り返し索引照合を行う方法と比較して、効率的な検索を可能にする効果が得られる。また、検索の際には、文書中のテキストをすべて走査する必要はなく、モノグラム索引に含まれている位置情報だけを参照すればよいため、テキストをすべて走査する方法と比較して、より効率的な検索を可能にする効果が得られる。
【００２９】
実施の形態２．
実施の形態１では、Ｎグラム索引のＮ＝１の場合、すなわちモノグラム索引の場合を対象としていたため、検索キーワードとの照合を１文字ごとに行っている。Ｎ＞１の索引を利用することにより、検索キーワードとの照合を一度にＮ文字づつ行うことが可能になり、さらに検索効率を上げることができる。この実施の形態２ではＮ＝２の場合、すなわちバイグラム索引を用いた検索の方法について示す。
【００３０】
図１６は実施の形態２による文書検索装置の構成を示すブロック図である。図において、実施の形態１の図１と同一または相当する部分には同一符号を付して示す。図１と異なる構成部分は、Ｎグラム索引生成部１０２、Ｎグラム状態遷移表生成部１０４、Ｎグラム索引照合部１０５、Ｎグラム索引１０６、Ｎグラム状態遷移表１１４である。
実施の形態２に係るＮグラム索引１０６のデータ構成を図１７に例示する。図において、１２１はＮグラムであり、この例ではＮ＝１の場合（モノグラム）に加え、Ｎ＝２の場合（バイグラム）を格納する。１２２はモノグラムの集合であり、１２３はバイグラムの集合である。１２４はＮグラムの集合で、１２１と１２２の和集合である。位置情報２３は、Ｎグラムが文書１１中の何番目に出現するかを示している。
【００３１】
以下、文字ｃ１，ｃ２，…，ｃｎの並びから成るＮグラムを、
ｇｒａｍ（ｃ１，ｃ２，…，ｃｎ）
と表記することにする。すなわち文字ｃからなるモノグラムはｇｒａｍ（ｃ）と表記され、文字ｃ１，ｃ２から成るバイグラムはｇｒａｍ（ｃ１，ｃ２）と表記される。
以下、Ｎグラムｇに対する位置情報を、
ｐｏｓｉｔｉｏｎＮ（ｇ）＝｛ｐ０，ｐ１，ｐ２…｝        （ｐ０，ｐ１，ｐ２…は位置番号を表わす。）
と表記することにする。これを図１７の例に当てはめると、
ｐｏｓｉｔｉｏｎＮ（「本日」）＝｛１，…｝
ｐｏｓｉｔｉｏｎＮ（「ヴェ」）＝｛５，…｝
である。また、以下、Ｎグラムｇを構成する文字数をｌｅｎｇｔｈ（ｇ）と表記することにする。
実施の形態２における展開規則７、検索対象文字列群１３、状態遷移表１４の構成は実施の形態１と同様である。
【００３２】
Ｎグラム状態遷移表１１４は、Ｎグラム索引照合部１０５で複数の検索対象文字列から文字の組を単位としてＮグラム索引を照合する際に用いられるが、Ｎグラム状態遷移表生成部１０４により生成される。このＮグラム状態遷移表１１４は、照合の履歴識別をするための複数の状態と文字の組み合わせの組ごとに状態の遷移先および検出した検索キーワードとを表わしたもので、図１８に示される全体構成からなる。すなわち、Ｎグラムｇｏｔｏ表１４１、ｆａｉｌｕｒｅ表４２、ｏｕｔｐｕｔ表４３、Ｎグラムｏｕｔｐｕｔ表１４３およびＮグラムｓｕｃｃｅｓｓ表１４４を構成要素としている。以下、これらの各表について説明する。
図５の検索対象文字列１３に対応して生成されるＮグラムｇｏｔｏ表１４１を図１９に示す。Ｓを状態集合、ＧをＮグラムの集合１２３（図１７）とするとき、Ｎグラムｇｏｔｏ関数は、
ｓ１＝ｇｏｔｏＮ（ｓ０，ｇ）        ｓ０，ｓ１∈Ｓ、  ｇ∈Ｇ
と表わされ、状態ｓ０においてＮグラムｇが入力されたときに状態ｓ１に遷移することを示す。したがって、Ｎグラムｇｏｔｏ表はすべての状態∈ＳとＮグラムｇ∈Ｇの組に対するＮグラムｇｏｔｏ関数ｇｏｔｏＮ（ｓ，ｇ）の値、すなわち遷移先の状態を表わす。図１９のＮグラムｇｏｔｏ表１４１を状態遷移図で表記すると図２０のようになる。ただし、図２０ではｆａｉｌ状態は省略している。
【００３３】
図５の検索対象文字列１３に対応して生成されるＮグラムｏｕｔｐｕｔ表１４３を図２１に示す。
ここで、Ｓを状態集合、ＧＮをバイグラムの集合、Ｋを検索対象文字列群に含まれる文字列の集合とするとき、Ｎグラムｏｕｔｐｕｔ関数は、
ｋ＝ｏｕｔｐｕｔＮ（ｓ，ｇ）        ｓ∈Ｓ、  ｇ∈Ｇ２、  ｋ∈Ｋ
のようになる。この関数は、状態ｓにバイグラムｇが出現したことにより文字列ｋを検出したことを表わしている。Ｎグラムｏｕｔｐｕｔ表１４３は、すべての状態ｓとＮグラムｇ（Ｎ＞１）の組み合わせに対して検出したｏｕｔｐｕｔＮ（ｓ，ｇ）の値、すなわち検索キーワードを保持する表である。
【００３４】
図５の検索対象文字列１３に対応して生成されるＮグラムｓｕｃｃｅｓｓ表１４４を図２２に示す。Ｓを状態集合、ＧをＮグラムの集合１２３とするとき、Ｎグラムｓｕｃｃｅｓｓ関数は、
ｄ＝ｓｕｃｃｅｓｓＮ（ｓ）        ｓ∈Ｓ、  ｄ∈｛Ｇ｝
のようになり、状態ｓにおいてｓ０以外の状態に遷移可能なＮグラムの集合（ｓ＝ｓ０の時）および状態ｓにおいてｆａｉｌ以外の状態に遷移可能なＮグラムの集合（ｓ≠ｓ０の時）を示す。したがって、Ｎグラムｓｕｃｃｅｓｓ表は、すべての状態ｓに対してｓｕｃｃｅｓｓＮ（ｓ）の値、他の状態に遷移可能な文字の組の集合を保持する表である。
【００３５】
次に、実施の形態２における文書の登録時の動作について説明する。
文書１１が登録されると、Ｎグラム索引生成部１０２により、その文書を構成する複数の文字および複数の隣り合う所定数の文字の組の文書中における出現位置を、その複数の文字および文字の組ごとに表わすＮグラム索引１０６が生成される。ここでは、Ｎ＝１、すなわち１−ｇｒａｍ（モノグラム）と、Ｎ＝２、すなわち２−ｇｒａｍ（バイクラム）から成る索引を対象としているので、例えば文書中に「本日のイヴェントは…」という文字列が存在する場合、図１７に示すＮグラム索引が生成される。索引のエントリは各Ｎグラムの出現位置を示している。Ｎグラム索引１０６は、例えば非特許文献１に示されている周知の方法で生成できるので、ここでは詳細な記述は省略する。
図２３は文書の検索手順を示すフローチャートであるが、上記実施の形態１の図１２の手順と比較すると、状態遷移表生成（ステップＳＴ２０２）の後にＮグラム状態遷移表生成（ステップＳＴ６１０）が加わり、モノグラム索引照合（ステップＳＴ２０５）の代わりにＮグラム索引照合（ステップＳＴ６０５）が置き換えられている。したがって、同じ内容のステップについての説明は省略する。
【００３６】
Ｎグラム状態遷移表１１４の生成（ステップＳＴ６０５）の詳細な手順について図２４のフローチャートにより説明する。
まず、Ｎグラム状態遷移表生成部１０４において、Ｎグラムｇｏｔｏ表１４１を初期化し、すべての値をｆａｉｌにする（ステップＳＴ７０１）。次に、すべての文字ｃに対してＮグラムｇｏｔｏ表１４１のモノグラムの列に、状態遷移表生成部４で先に生成された図７に示すｇｏｔｏ表４１の状態を設定する。さらに、Ｎグラムｓｕｃｃｅｓｓ表１４４のモノグラムの部分に、先に生成された図１０に示すｓｕｃｃｅｓｓ表４４の状態を設定する（ステップＳＴ７０２）。次に、変数ｉを０に初期化する（ステップＳＴ７０３）。ここで、変数ｉは状態集合Ｓ＝｛ｓ０，ｓ１，…｝の番号を示す。状態集合Ｓ＝｛ｓ０，ｓ１，…｝に含まれるすべての状態ｓｉについて以下の処理を行う（ステップＳＴ７０４）。
【００３７】
変数ｊを１に初期化する（ステップＳＴ７０５）。変数ｊは文字集合Ｃ＝｛ｃ１，ｃ２，…，ｃｊ，…｝の中の処理中の要素の番号を示す。文字集合Ｃ＝｛ｃ１，ｃ２，…，ｃｊ，…｝に含まれるすべての文字ｃｊについて以下の処理を行う（ステップＳＴ７０６）。
状態ｓｉと文字ｃｊに対するｇｏｔｏ関数ｇｏｔｏ（ｓｉ，ｃｊ）の値がｆａｉｌであるかどうかを判定する（ステップＳＴ７０７）。ｆａｉｌであればステップＳＴ７１６に進む。一方、ｆａｉｌでなければ、変数ｋを１に初期化する（ステップＳＴ７０８）。ここで、ｋは文字集合Ｃ＝｛ｃ１，ｃ２，…，ｃｋ，…｝の中の処理中の要素の番号を示す。次に、文字集合Ｃ＝｛ｃ１，ｃ２，…，ｃｋ，…｝に含まれるすべての文字ｃｋについて以下の処理を行う（ステップＳＴ７０９）。
【００３８】
状態ｓｉと文字ｃｊ，ｃｋに対するｇｏｔｏ関数ｇｏｔｏ（ｇｏｔｏ（ｓｉ，ｃｊ），ｃｋ）の値がｆａｉｌであるかどうかを判定する（ステップＳＴ７１０）。ｆａｉｌあればステップＳＴ７１７に進む。一方、ｆａｉｌでなければ、ステップＳＴ７１１に進む。
状態ｓｉと文字ｃｊ，ｃｋに対するｇｏｔｏ関数ｇｏｔｏ（ｇｏｔｏ（ｓｉ，ｃｊ），ｃｋ）の値は、状態ｓｉから、文字ｃｊ，ｃｋが出現したときに到達する状態が存在することを意味する。したがって、Ｎグラムｇｏｔｏ表ｇｏｔｏＮ（ｓｉ，ｇｒａｍ（ｃｊ，ｃｋ））に状態ｇｏｔｏ（ｇｏｔｏ（ｓｉ，ｃｊ），ｃｋ）を設定する（ステップＳＴ７１１）。
例えば、ｓ＝ｓ０、ｃｊ＝イ  、ｃｋ＝べ  の時、ｇｏｔｏ（ｓ０，イ）＝ｓ１であり、ｇｏｔｏ（ｓ１，べ）＝ｓ２であるから、
ｇｏｔｏ（ｇｏｔｏ（ｓｉ，イ），べ）＝ｓ２≠ｆａｉｌにより、
ｇｏｔｏＮ（ｓ０，イベ）＝ｓ２と設定される。
【００３９】
さらに、ｓｕｃｃｅｓｓＮ（ｓｉ，２）にｇｒａｍ（ｃｊ，ｃｋ）を追加する（ステップＳＴ７１２）。ここで、ｇｒａｍ（ｃｊ，ｃｋ）は、文字ｃｊ，ｃｋから成るバイグラムである。例えばｓｕｃｃｅｓｓＮ（ｓ０，２）に「イベ」が追加される。
次に、ｏｕｔｐｕｔ（ｇｏｔｏ（ｓｉ，ｃｊ））が空かどうかを判定する（ステップＳＴ７１３）。空の場合はステップＳＴ７１５に進む。一方、空でない場合は、状態ｇｏｔｏ（ｓｉ，ｃｊ）に到達した時点で文字列が検出されることを意味するので、ｏｕｔｐｕｔＮ（ｓｉ，ｇｒａｍ（ｃｊ，ｃｋ））にｏｕｔｐｕｔ（ｇｏｔｏ（ｓｉ，ｃｊ））を設定し、検出されるべき文字列を記録する（ステップＳＴ７１４）。
【００４０】
次の文字ｃｋを調べるため、変数ｋに１を加える（ステップＳＴ７１５）。文字集合Ｃ＝｛ｃ１，ｃ２，…，ｃｊ，…｝に含まれるすべての文字ｃｋについてステップＳＴ７１０〜ＳＴ７１５を繰り返す。すべてのｃｋについて処理が終わったら、ステップＳＴ７１６に進む（ステップＳＴ７０９）。
ステップＳＴ７１６では、次の文字ｃｊを調べるため、変数ｊに１を加える。以下、文字集合Ｃ＝｛ｃ１，ｃ２，…，ｃｊ，…｝に含まれるすべての文字ｃｊについてステップＳＴ７０７〜ＳＴ７１６を繰り返す。繰り返しの中でステップＳＴ７１０においてｇｏｔｏ（ｇｏｔｏ（ｓｉ，ｃｊ），ｃｋ）の値がｆａｉｌであればステップＳＴ７１７に進む。
【００４１】
ステップＳＴ７１７では、状態ｓｆをｆａｉｌｕｒｅ（ｇｏｔｏ（ｓｉ，ｃｊ））とする。状態ｓｆは、ｃｋで状態遷移できなかったときに移動する状態を示している。したがって、状態ｓｆにおいてｃｋによる状態遷移が可能であれば、状態ｓｉからＮグラム（ｓｉ，ｇｒａｍ（ｃｊ，ｃｋ））による遷移が可能であることを意味する。次に、以下をｓｆがｓ０になるまで繰り返す（ステップＳＴ７１８）
【００４２】
ｇｏｔｏ（ｓｆ，ｃｋ）＝ｆａｉｌであるかどうかを調べる（ステップＳＴ７１９）。もし、ｇｏｔｏ（ｓｆ，ｃｋ）＝ｆａｉｌであれば、さらにｆａｉｌｕｒｅ関数による遷移が可能かどうかを調べるため、状態ｓｆをｆａｉｌｕｒｅ（ｇｏｔｏ（ｓｆ，ｃｊ））とし、ステップ７１８に戻る（ステップＳＴ７２０）。一方、ステップＳＴ７１９にてｇｏｔｏ（ｓｆ，ｃｋ）≠ｆａｉｌであれば、状態ｓｆにおいてｃｋによる状態遷移が可能なので、ｇｏｔｏＮ（ｓｉ，ｇｒａｍ（ｃｊ，ｃｋ））にｇｏｔｏ（ｓｆ，ｃｋ）を設定し（ステップＳＴ７２１）、ステップＳＴ７１２に進み、対応するＮグラムｓｕｃｃｅｓｓ表、Ｎグラムｏｕｔｐｕｔ表の設定を行う。
【００４３】
上記ステップＳＴ７１８において、ｓｆ＝ｓ０になった場合には、ｃｋによる状態遷移が不可能なので、ステップＳＴ７１５に進み、次のｃｋの処理を行う。
ステップＳＴ７０６〜ＳＴ７２１を繰り返し、すべてのｃｊについて処理が終わったら（ステップＳＴ７０６）、変数ｉに１を加え（ステップＳＴ７２２）、次の状態ｓｉを調べる（ステップＳＴ７０４）。状態集合Ｓ＝｛ｓ０，ｓ１，…｝に含まれるすべての状態ｓｉについてステップＳＴ７０５〜Ｓ７２１を繰り返し、すべてのｓｉについて処理が終わったら、終了する。
【００４４】
Ｎグラム索引照合部１０５では、Ｎグラム状態遷移表１１４に示される状態とＮグラム索引１０６に含まれる文字の組と位置番号とに基づいて出現位置を照合し、複数の検索対象文字列のいずれかと一致する文字列を有する文書を一意に識別する情報の集合を、検索結果として生成する。この場合、Ｎグラム索引照合部１０５は、Ｎグラムｇｏｔｏ表に基づいて状態と文字の組み合わせにより状態の遷移を行い、Ｎグラムｇｏｔｏ表に遷移先の状態が存在しない場合にはｆａｉｌｕｒｅ表が示す遷移先に状態の遷移を行い、ｏｕｔｐｕｔ表とＮグラムｏｕｔｐｕｔ表に基づいて各状態に対して検出した検索キーワードを決定し、Ｎグラムｓｕｃｃｅｓｓ表に基づいて選択した遷移可能な文字の組を対象にＮグラム索引１０６の照合を行う。この文書１１のＮグラム索引照合（ステップＳＴ６０５）の詳細手順を図２５により説明する。
まず、状態ｓをｓ０に初期化し（ステップＳＴ８０１）、文字位置ｉを１に初期化する（ステップＳＴ８０２）。次に、文字位置ｉが文書中の全文字数ｍを超えたか否かを判定する（ステップＳＴ８０３）。この場合、ｉ＝１であり条件は成立しないため、ステップＳＴ８０４に進む。
ステップＳＴ８０４では、ｓｕｃｃｅｓｓＮ（ｓ）に含まれるすべてのｇｊを調べ、ｐｏｓｉｔｉｏｎＮ（ｇｊ）に含まれる位置番号の中から、ｉを超えない最小の位置番号ｐ∈ｐｏｓｉｔｉｏｎＮ（ｇｊ）を持つＮグラムｇｊを選ぶ。ただし、複数のＮグラムｇｊが存在する場合はｌｅｎｇｔｈ（ｇｊ）の最大になるものを選択する。この場合は、ｓｕｃｃｅｓｓＮ（ｓ０）＝｛イ、イヴ｝であり、ｐｏｓｉｔｉｏｎ（イ）＝｛４，…｝、ｐｏｓｉｔｉｏｎ（イヴ）＝｛４，…｝であるから、最小の位置番号ｐ＝４であり、ｌｅｎｇｔｈ（イ）＝１、ｌｅｎｇｔｈ（イヴ）＝２であることからＮグラムｇｊ＝イヴ  を選択する。
【００４５】
状態ｓのＮグラムｏｕｔｐｕｔ関数により、出力を決める（ステップＳＴ８０５）。この場合、ｏｕｔｐｕｔＮ（ｓ１）＝φなので出力は行わず、ステップＳＴ８０７に進む。ステップＳＴ８０７において、状態ｓのＮグラムｇｏｔｏ関数により、次の状態を決める。この場合、ｇｏｔｏＮ（ｓ０，イヴ）＝ｓ５なので、ｓ＝ｓ５となる。次に、状態ｓのｏｕｔｐｕｔ関数により、出力を決める（ステップＳＴ８０８）。この場合、ｏｕｔｐｕｔ（ｓ５）＝φなので出力は行わず、ステップＳＴ８１０に進む。ステップＳＴ８１０において、文字位置ｉをｌｅｎｇｔｈ（ｇｊ）だけ進める。今の場合ｌｅｎｇｔｈ（ｇｊ）＝ｌｅｎｇｔｈ（イヴ）＝２なのでｉ＝６とする。次に、ｓｕｃｃｅｓｓＮ（ｓ）に含まれるすべてのｇｊを調べ、ｉ∈ｐｏｓｉｔｉｏｎＮ（ｇｊ）となるｇｊが存在するかどうかを調べる。複数のｇｊが存在する場合はｌｅｎｇｔｈ（ｇｊ）の最大になるものを選択する（ステップＳＴ８１１）。この場合は、ｓｕｃｃｅｓｓ（ｓ５）＝｛ェ，エ，ヱ，ェン，エン，ヱン｝であり、ｐｏｓｉｔｉｏｎ（ェン）＝｛６，…｝であるから、Ｎグラムｇｊ＝ェン  が存在する。Ｎグラムｇｊが存在するどうかの判定（ステップＳＴ８１２）において、存在するならばステップＳＴ８０５へ進み、存在しないならばステップＳＴ８１３へ進む。この場合は、Ｎグラムｇｊ＝ェン  が存在するのでステップＳＴ８０５に進む。
【００４６】
ステップＳＴ８０５において、状態ｓのＮグラムｏｕｔｐｕｔ関数により、出力を決める。この場合、ｏｕｔｐｕｔＮ（ｓ５）＝φなので出力は行わず、ステップＳＴ８０７に進む。次にステップＳＴ８０７において、状態ｓのＮグラムｇｏｔｏ関数により、次の状態を決める。この場合、ｇｏｔｏＮ（ｓ５，ェン）＝ｓ７なので、ｓ＝ｓ７となる。次に、状態ｓのｏｕｔｐｕｔ関数により、出力を決める（ステップＳＴ８０８）。この場合、ｏｕｔｐｕｔ（ｓ７）＝φなので出力は行わず、ステップＳＴ８１０に進む。ステップＳＴ８１０において、文字位置ｉをｌｅｎｇｔｈ（ｇｊ）だけ進める。今の場合ｌｅｎｇｔｈ（ｇｊ）＝ｌｅｎｇｔｈ（ェン）＝２なのでｉ＝８とする。次に、ｓｕｃｃｅｓｓＮ（ｓ）に含まれるすべてのＮグラムｇｊを調べ、ｉ∈ｐｏｓｉｔｉｏｎＮ（ｇｊ）となるｇｊが存在するかどうかを調べる。複数のｇｊが存在する場合はｌｅｎｇｔｈ（ｇｊ）の最大になるものを選択する（ステップＳＴ８１１）。この場合は、ｓｕｃｃｅｓｓ（ｓ７）＝｛ト｝であり、ｐｏｓｉｔｉｏｎ（ト）＝｛８，…｝であるから、Ｎグラムｇｊ＝ト  が存在する。Ｎグラムｇｊが存在するならばステップＳＴ８０５へ進む。存在しないならばステップＳＴ８１３へ進む（ステップＳＴ８１２）。この場合は、Ｎグラムｇｊ＝ト  が存在するのでステップＳＴ８０５に進む。
【００４７】
再び、状態ｓのＮグラムｏｕｔｐｕｔ関数により、出力を決める（ステップＳＴ８０５）。この場合、ｏｕｔｐｕｔＮ（ｓ７）＝φなので出力は行わず、ステップＳＴ８０７に進む。ステップＳＴ８０７において、状態ｓのＮグラムｇｏｔｏ関数により、次の状態を決める。この場合、ｇｏｔｏＮ（ｓ７，ト）＝ｓ８なので、ｓ＝ｓ８となる。次に、状態ｓのｏｕｔｐｕｔ関数により、出力を決める（ステップＳＴ８０８）。この場合、ｏｕｔｐｕｔ（ｓ８）＝「イヴェント」なので、ステップＳＴ８０９に進む。ステップＳＴ８０９では、ｏｕｔｐｕｔ（ｓ８）＝「イヴェント」を検出し出力する。次に、文字位置ｉをｌｅｎｇｔｈ（ｇｊ）だけ進める（ステップＳＴ８１０）。今の場合ｌｅｎｇｔｈ（ｇｊ）＝ｌｅｎｇｔｈ（ト）＝１なのでｉ＝９とする。ｓｕｃｃｅｓｓＮ（ｓ）に含まれるすべてのｇｊを調べ、ｉ∈ｐｏｓｉｔｉｏｎＮ（ｇｊ）となるＮグラムｇｊが存在するかどうかを調べる。複数のＮグラムｇｊが存在する場合はｌｅｎｇｔｈ（ｇｊ）の最大になるものを選択する（ステップＳＴ８１１）。この場合は、ｓｕｃｃｅｓｓ（ｓ７）＝｛φ｝であるから、Ｎグラムｇｊは存在しない。Ｎグラムｇｊ＝ト  が存在しないのでステップＳＴ８１３に進む（ステップＳＴ８１２）。次に、状態ｓのｆａｉｌｕｒｅ関数により、次の状態を決める（ステップＳＴ８１３）。この場合、ｆａｉｌｕｒｅ（ｓ８）＝ｓ０なので、ｓ＝ｓ０となる。
以下、同様に繰り返し、文字位置ｉが全文字数ｍを超えるまでステップＳＴ８０３〜ＳＴ８１３を繰り返す。文字位置ｉが全文字数ｍを超えと終了する（ステップＳＴ８０３）。
【００４８】
以上のように、この実施の形態２の構成によれば、１回の索引の走査だけで一つの検索キーワードに対して想定しえる異表記の複数の検索キーワードを生成し、その異表記の複数の検索キーワードに対して同時に索引照合を行うことができるようにしたため、複数の検索キーワードを別々に入力して繰り返し索引照合を行う方法と比較して、効率的な検索が可能になるという利点がある。また、検索の際には、文書中のテキストをすべて走査する必要はなく、Ｎグラム索引に含まれている位置情報だけを参照すればよいため、テキストをすべて走査する方法と比較して、より効率的な検索が可能になるという効果が得られる。また、Ｎグラム索引を使用することにより、検索キーワードとの照合を一度にＮ字ずつ行うことが可能になり、上記実施の形態１よりもさらに検索効率を上げることができるという効果が得られる。
【００４９】
なお、上記実施の形態ではＮ＝１、Ｎ＝２の場合について示したが、同様の手順を取ることにより、Ｎ＝３以上の場合についても拡張が可能である。
また、言語は日本語であることを仮定して説明してきたが、英語その他の言語であっても、文字コードが割り当てられていればこの発明の文書検索装置を適用し検索可能である。
さらに、検索は、索引に格納された全文書を対象とすることを仮定して説明してきたが、その文書から生成した書誌的な情報やその他の条件式によって予め検索対象を限定した後に、この発明の文書検索を適用するようにしてもよい。また、特許文献１に示されているように、文字成分表などの別の情報によって検索対象の文書を抽出した後にこの発明の文書検索を適用してもよい。
【００５０】
さらに、キーワードとなりえる文字列とその同義語または異義語の関連辞書を予め準備格納しておき、抽出手段を設けて、キーワード展開部において展開した検索対象文字列に対応する同義語または異義語の文字列を抽出し、それら文字列についても状態遷移表やＮグラム状態遷移表を生成し同様に処理するようにしてもよい。また、検索対象文字列に関して異字体の展開や語尾変化の展開を行う処理を加えるようにしてもよい。このことによって、異表記検索、同義語・類義語検索、異体字検索等を効率よく行うことができる
【図面の簡単な説明】
【００５１】
【図１】この発明の実施の形態１による文書検索装置の構成を示すブロック図である。
【図２】この発明の実施の形態１に係る検索対象の文書例を示す説明図である。
【図３】この発明の実施の形態１に係るモノグラム索引のデータ構成を例示する説明図である。
【図４】この発明の実施の形態１に係る文字列の展開規則を例示する説明図である。
【図５】この発明の実施の形態１に係る検索対象文字列群を例示する説明図である。
【図６】この発明の実施の形態１に係る状態遷移表の全体構成を示す説明図である。
【図７】この発明の実施の形態１に係るｇｏｔｏ表を示す説明図である。
【図８】この発明の実施の形態１に係るｇｏｔｏ表を状態遷移図に表記した説明図である。
【図９】この発明の実施の形態１に係るｆａｉｌｕｒｅ表を示す説明図である。
【図１０】この発明の実施の形態１に係るｏｕｔｐｕｔ表を示す説明図である。
【図１１】この発明の実施の形態１に係るｓｕｃｃｅｓｓ表を示す説明図である。
【図１２】この発明の実施の形態１に係る文書検索の手順を示すフローチャートである。
【図１３】この発明の実施の形態１に係る状態遷移表の生成手順を示すフローチャートである。
【図１４】この発明の実施の形態１に係るｓｕｃｃｅｓｓ表の生成手順を示すフローチャートである。
【図１５】この発明の実施の形態１に係るモノグラム索引照合の手順を示すフローチャートである。
【図１６】この発明の実施の形態２による文書検索装置の構成を示すブロック図である。
【図１７】この発明の実施の形態２に係るＮグラム索引のデータ構成を例示する説明図である。
【図１８】この発明の実施の形態２に係るＮグラム状態遷移表の全体構成を示す説明図である。
【図１９】この発明の実施の形態２に係るＮグラムｇｏｔｏ表を示す説明図である。
【図２０】この発明の実施の形態２に係るＮグラムｇｏｔｏ表を状態遷移図で表記する説明図である。
【図２１】この発明の実施の形態２に係るＮグラムｏｕｔｐｕｔ表を示す説明図である。
【図２２】この発明の実施の形態２に係るＮグラムｓｕｃｃｅｓｓ表を示す説明図である。
【図２３】この発明の実施の形態２に係る文書検索の手順を示すフローチャートである。
【図２４】この発明の実施の形態２に係るＮグラム状態遷移表の生成手順を示すフローチャートである。
【図２５】この発明の実施の形態２に係るＮグラム索引照合の手順を示すフローチャートである。
【符号の説明】
【００５２】
１  文書検索装置、２  モノグラム索引生成部、３  キーワード展開部、４  状態遷移表生成部、５  モノグラム索引照合部、６  モノグラム索引、７  展開規則、１１  文書、１２  検索キーワード、１３  検索対象文字列群、１４  状態遷移表、１５  検索結果、１６  文書格納装置、１７  文書格納部、１８  文書取得部、１９  検索結果文書、１０２  Ｎグラム索引生成部、１０４  Ｎグラム状態遷移表生成部、１０５  Ｎグラム索引照合部、１０６  Ｎグラム索引、１１４  Ｎグラム状態遷移表。
【図１】
2006134161.tif 000003
【図２】
2006134161.tif 000004
【図３】
2006134161.tif 000005
【図４】
2006134161.tif 000006
【図５】
2006134161.tif 000007
【図６】
2006134161.tif 000008
【図７】
2006134161.tif 000009
【図８】
2006134161.tif 000010
【図９】
2006134161.tif 000011
【図１０】
2006134161.tif 000012
【図１１】
2006134161.tif 000013
【図１２】
2006134161.tif 000014
【図１３】
2006134161.tif 000015
【図１４】
2006134161.tif 000016
【図１５】
2006134161.tif 000017
【図１６】
2006134161.tif 000018
【図１７】
2006134161.tif 000019
【図１８】
2006134161.tif 000020
【図１９】
2006134161.tif 000021
【図２０】
2006134161.tif 000022
【図２１】
2006134161.tif 000023
【図２２】
2006134161.tif 000024
【図２３】
2006134161.tif 000025
【図２４】
2006134161.tif 000026
【図２５】
2006134161.tif 000027