(57)【要約】  【課題】  小サイズのＮ−ｇｒａｍインデックスでひらがな、カタカナのキーワードの文書検索を行なう。  【解決手段】  文字列抽出部１１は、文書中のひらがな文字列、カタカナ文字列を抽出する。文字列連結部１２は、抽出した文字列をその区切りを判別可能に連結して擬似文書として構成する。ビットベクター生成部１３は、ひらがな語、タカナ語を実現可能な各Ｎ−ｇａｒｍについて各擬似文書におけるその出現位置をフラグビットで示すビットベクターを生成する。インデックス登録部１４はビットベクターを文書検索用のインデックスとしてインデックス記憶部１５に登録する。キーワード入力部１６は、ひらがな文字列、カタカナ文字列のキーワードを入力する。検索部１７は、キーワードをＮ−ｇａｒａｍに分解して、当該Ｎ−ｇａｒａｍの擬似文書中の位置情報から当該擬似文書中にキーワードが含まれるかどうかを判別し、検索結果出力部１８が検索結果を出力する。【選択図】  図１
2006209399.tif 000002
【特許請求の範囲】
【請求項１】
形態素解析結果から生成された検索辞書を用いて文書検索を行なう第１検索手段と、
Ｎ−ｇｒａｍ辞書を用いて文書検索を行なう第２検索手段とを有し、
上記第２検索手段は、
検索対象の文書の各々から、ひらがな文字列、カタカナ文字列、アルファベット文字列、ならびに、ひらがな、カタカナおよびアルファベットの混合文字列のうちの予め選定された少なくとも１種類の文字列を、抽出して連結し、擬似文書を生成する擬似文書生成手段と、
上記検索対象の文書の各々に対して、Ｎ−ｇｒａｍの各エントリについて当該Ｎ−ｇｒａｍの上記擬似文書中における出現位置を表す出現位置情報を記憶する出現位置記憶手段と、
ひらがな文字列、カタカナ文字列、アルファベット文字列、ならびに、ひらがな、カタカナおよびアルファベットの混合文字列のうちの上記予め選定された少なくとも１種類の文字列により構成される検索キーワードを上記出現位置情報に照合して上記検索キーワードを含む文書を特定する文書特定手段とを有することを特徴とする文書検索装置。
【請求項２】
検索対象の文書の各々から、ひらがな文字列、カタカナ文字列、アルファベット文字列、ならびに、ひらがな、カタカナおよびアルファベットの混合文字列のうちの予め選定された少なくとも１種類の文字列を、抽出して連結し、擬似文書を生成する擬似文書生成手段と、
上記検索対象の文書の各々に対して、Ｎ−ｇｒａｍの各エントリについて当該Ｎ−ｇｒａｍの上記擬似文書中における出現位置を表す出現位置情報を記憶する出現位置記憶手段と、
ひらがな文字列、カタカナ文字列、アルファベット文字列、ならびに、ひらがな、カタカナおよびアルファベットの混合文字列のうちの上記予め選定された少なくとも１種類の文字列により構成される検索キーワードを上記出現位置情報に照合して上記検索キーワードを含む文書を特定する文書特定手段とを有することを特徴とする文書検索装置。
【請求項３】
上記検索対象の文書の各々に対して、Ｎ−ｇｒａｍの各エントリについて当該Ｎ−ｇｒａｍの出現位置を表す出現位置情報を、当該位置に対応するビット位置にフラグビットを立てるビットベクターとして記憶する出現位置記憶手段と、
検索キーワードを上記出現位置情報に照合して上記検索キーワードを含む文書を特定する文書特定手段とを有し、
上記検索キーワードが２つ以上のＮ−ｇｒａｍから構成される場合に、当該Ｎ−ｇｒａｍの各々のビットベクターのフラグビット位置が対応する隣接関係にあることを判別して上記検索キーワードを含む文書を特定することを特徴とする文書検索装置。
【請求項４】
擬似文書生成手段が、検索対象の文書の各々から、ひらがな文字列、カタカナ文字列、アルファベット文字列、ならびに、ひらがな、カタカナおよびアルファベットの混合文字列のうちの予め選定された少なくとも１種類の文字列を、抽出して連結し、擬似文書を生成する擬似文書生成ステップと、
出現位置記憶手段が、上記検索対象の文書の各々に対して、Ｎ−ｇｒａｍの各エントリについて当該Ｎ−ｇｒａｍの上記擬似文書中における出現位置を表す出現位置情報を記憶する出現位置記憶ステップと、
文書特定手段が、ひらがな文字列、カタカナ文字列、アルファベット文字列、ならびに、ひらがな、カタカナおよびアルファベットの混合文字列のうちの上記予め選定された少なくとも１種類の文字列により構成される検索キーワードを上記出現位置情報に照合して上記検索キーワードを含む文書を特定する文書特定ステップとを有することを特徴とする文書検索方法。
【請求項５】
出現位置記憶手段が、上記検索対象の文書の各々に対して、Ｎ−ｇｒａｍの各エントリについて当該Ｎ−ｇｒａｍの出現位置を表す出現位置情報を、当該位置に対応するビット位置にフラグビットを立てるビットベクターとして記憶する出現位置記憶ステップと、
文書特定手段が、検索キーワードを上記出現位置情報に照合して上記検索キーワードを含む文書を特定する文書特定ステップとを有し、
上記検索キーワードが２以上のＮ−ｇｒａｍから構成される場合に、当該Ｎ−ｇｒａｍの各々のビットベクターのフラグビット位置が対応する隣接関係にあることを判別して上記検索キーワードを含む文書を特定することを特徴とする文書検索方法。
【請求項６】
検索対象の文書の各々から、ひらがな文字列、カタカナ文字列、アルファベット文字列、ならびに、ひらがな、カタカナおよびアルファベットの混合文字列のうちの予め選定された少なくとも１種類の文字列を、抽出して連結し、擬似文書を生成する擬似文書生成手段と、
上記検索対象の文書の各々に対して、Ｎ−ｇｒａｍの各エントリについて当該Ｎ−ｇｒａｍの上記擬似文書中における出現位置を表す出現位置情報を記憶する出現位置記憶手段と、
ひらがな文字列、カタカナ文字列、アルファベット文字列、ならびに、ひらがな、カタカナおよびアルファベットの混合文字列のうちの上記予め選定された少なくとも１種類の文字列により構成される検索キーワードを上記出現位置情報に照合して上記検索キーワードを含む文書を特定する文書特定手段とを実現するために用いられることを特徴とする文書検索用コンピュータプログラム。
【請求項７】
上記出現位置記憶手段は、上記Ｎ−ｇｒａｍの上記擬似文書中における出現位置を表す出現位置情報を、当該位置に対応するビット位置にフラグビットを立てるビットベクターで表す請求項６記載の文書検索用コンピュータプログラム。
【請求項８】
上記擬似文書は、同一文書内の複数の同一の文字列については１つに縮退して生成される請求項６または７記載の文書検索用コンピュータプログラム。
【請求項９】
上記擬似文書において隣接する文字列の間の区切りを表すために空白文字を用いる請求項６、７または８記載の文書検索用コンピュータプログラム。
【請求項１０】
上記予め選定された少なくとも１種類の文字列は、ひらがな文字列およびカタカナ文字列である請求項６〜９のいずれかに記載の文書検索用コンピュータプログラム。
【請求項１１】
上記ビットベクターのビット長が所定長を超える場合には、上記ビットベクターを上記所定長位置で折り返して上記フラグビットのＯＲ論理をとる請求項７記載の文書検索用コンピュータプログラム。
【請求項１２】
上記ビットベクターのビット長が所定長を超える場合には、上記ビットベクターを上記所定長のシーケンスに分割し、さらにフラグビットを含まないシーケンスは省略して補完する請求項７記載の文書検索用コンピュータプログラム。
【請求項１３】
上記検索対象の文書の各々に対して、Ｎ−ｇｒａｍの各エントリについて当該Ｎ−ｇｒａｍの出現位置を表す出現位置情報を、当該位置に対応するビット位置にフラグビットを立てるビットベクターとして記憶する出現位置記憶手段と、
検索キーワードを上記出現位置情報に照合して上記検索キーワードを含む文書を特定する文書特定手段とを実現するために用いられ、さらに、
上記検索キーワードが２つ以上のＮ−ｇｒａｍから構成される場合に、当該Ｎ−ｇｒａｍの各々のビットベクターのフラグビット位置が対応する隣接関係にあることを判別して上記検索キーワードを含む文書を特定することを特徴とする文書検索用コンピュータプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、Ｎ−ｇｒａｍ手法を用いた文書検索技術に関し、特に形態書解析手法の文書検索と組み合わせて最適なものである。
【背景技術】
【０００２】
文書検索手法としては形態素解析手法やＮ−ｇｒａｍ手法が知られている。形態素解析手法では、形態素解析により文書を形態素に分解してインデックスに登録する。形態素語のエントリごとに、当該形態素語を含む文書の識別子、または文書の識別子と当該形態素語の出現位置をインデックスに登録しておく。入力されたキーワードを元にインデックスを検索することにより当該キーワードを含む文書を高速に選択することができる。この形態素解析手法では、未知語などによる形態素区切りの誤判定によって、本来選択すべき文書を選べない場合があるという問題がある。
【０００３】
他方、Ｎ−ｇｒａｍ手法では、文書中の各Ｎ−ｇｒａｍをインデックスに登録する。Ｎ−ｇｒａｍとは言語モデルでの表現で、文書中から隣接する２文字（ｂｉ−ｇｒａｍ）や３文字（ｔｒｉ−ｇｒａｍ）を機械的に切り出したもののことである。通常、文書中での出現位置と文書の識別子も合わせてインデックスに登録され、出現位置から隣接判定を行うことで、任意の長さの文字列検索が可能である。たとえばＮ＝２のＮ−ｇｒａｍでは、「文字列の検索処理」という単語を２文字ごとに分解して、その出現位置を記憶しておく。この場合は、「（１）文字」、「（２）字列」、「（３）列の」、「（４）の検」、「（５）検索」、「（６）索処」、「（７）処理」、と分解して、インデックスに登録しておく（カッコ内の数字は出現位置）。ここで「検索」という単語を検索する場合は、インデックスから、「検索」というＮ−ｇｒａｍが含まれている文書を探せばよい。また「検索処理」ならば、「検索」と「処理」の両方が含まれている文書を探し、かつ「処理」の出現位置が「検索」の出現位置より２多いもの（この場合は、（５）と（７）で見つかる）を探せばよい。
【０００４】
しかしながら、Ｎ−ｇｒａｍ手法を用いた検索では、単語の境界を無視し、単に文字列の一致で文書を検索するため、本来ヒットすべきでない文書を検索してしまい、本来の文書が、検索に適合しない文書に埋もれてしまう場合がある。また、出現位置などによりインデックスサイズが肥大化しやすい。
【０００５】
なお、この発明と関連する先行文献としては、つぎのようなものがある。
【０００６】
特許文献１は、形態素解析手法のインデックスを小さくするために形態素語集合としてもっともコンパクトなものとし（他の形態素語を含む形態素語（延長語）は辞書に含めない）、その上で、コンパクトな形態素語集合に含まれる形態素語をエントリとして当該形態素語を一部として含む形態素語を関連づける辞書（延長語辞書）を用い、入力キーワードがコンパクトな形態素語集合に含まれない場合には、キーワードの構成語と延長語辞書を用いて漏れのない検索が行なわれるようにし、さらに、検索態様を、コンパクトな形態素語集合のみに限定したり、延長語辞書を用いた漏れのない検索を行なったり、切換を行なえるようにしている。
【０００７】
特許文献２は、文字種に基づいて文字列の切り出しを行い、ひらがな、カタカナはそのまま特徴語とし、漢字についてはＮ−ｇｒａｍを抽出して特徴語とし、特徴語の頻度情報を元に類似文書検索を行なうことを開示している。
【０００８】
特許文献３は、形態素解析結果から得た単語先頭位置、単語末尾位置の情報をＮ−ｇｒａｍのインデックスに付加して、単語の境界を意図して前方一致、後方一致等の検索を行なえるようにすることを開示している。
【特許文献１】特開平１１−７３４２９号公報
【特許文献２】特開平１１−１４３９０２号公報
【特許文献３】特開２０００−２３１５６公報
【発明の開示】
【発明が解決しようとする課題】
【０００９】
この発明は、以上の事情を考慮してなされたものであり、インデックスサイズを抑制しつつＮ−ｇｒａｍの検索を簡易に行なえるようにすることを目的としている。また、具体的な側面では、形態素解析手法の検索と組み合わせて最適なＮ−ｇｒａｍ手法による解析技術を提供することを目的としている。
【課題を解決するための手段】
【００１０】
この発明の具体的な構成例では、形態素解析方式のインデックスを検索の基本として用いながらも、典型的には、ひらがな、カタカナに限定してＮ−ｇｒａｍ方式でインデックスを構築することによって、形態素解析手法の検索漏れという課題を補う。
【００１１】
また、異なり語（同一でない語）を空白文字で区切った擬似文書中の出現位置をビットベクター化することでインデックスサイズを縮小し、隣接計算を高速化する。
【００１２】
この構成例では、形態素解析手法を用いながらも、典型的には、ひらがな、カタカナに限定してＮ−ｇｒａｍ方式で部分一致検索ができる。
【００１３】
また、異なり語のみからなる擬似文書を作成し、その文書中の出現位置をビットベクターで保持するのでＮ−ｇｒａｍのインデックスを小さくできる。
【００１４】
また、ビットベクターを固定長で折り返して当該固定長に縮退させることが可能である。
【００１５】
さらに、ビットベクターを複数のシーケンスに分けて出現位置を示すフラグビットが立っていないシーケンスを省略してビットベクターサイズを縮小できる。
【００１６】
さらにこの発明を説明する。なお、以下では、理解を容易にするために、実施例の各部の符号を付して説明することもあるが、これは、この発明を実施例に限定する意図ではない。
【００１７】
この発明の一側面によれば、上述の目的を達成するために、文書検索装置（１００）に：検索対象の文書の各々から、ひらがな文字列、カタカナ文字列、アルファベット文字列、ならびに、ひらがな、カタカナおよびアルファベットの混合文字列のうちの予め選定された少なくとも１種類の文字列を、抽出して連結し、擬似文書を生成する擬似文書生成手段（１１、１２）と；上記検索対象の文書の各々に対して、Ｎ−ｇｒａｍの各エントリについて当該Ｎ−ｇｒａｍの上記擬似文書中における出現位置を表す出現位置情報を記憶する出現位置記憶手段（１３、１４、１５）と；ひらがな文字列、カタカナ文字列、アルファベット文字列、ならびに、ひらがな、カタカナおよびアルファベットの混合文字列のうちの上記予め選定された少なくとも１種類の文字列により構成される検索キーワードを上記出現位置情報に照合して上記検索キーワードを含む文書を特定する文書特定手段（１７）とを設けている。
【００１８】
この構成によれば、Ｎ−ｇｒａｍのインデックスを小さくして少ない計算機資源で高速に検索処理を行なえる。
【００１９】
この構成において、上記出現位置記憶手段は、上記Ｎ−ｇｒａｍの上記擬似文書中における出現位置を表す出現位置情報を、当該位置に対応するビット位置にフラグビットを立てるビットベクターで表すことが好ましい。
【００２０】
ビットベクターを用いることによりシフト演算およびＡＮＤ演算により隣接関係の判別を簡易に行い、その結果、簡易に検索処理を行なえる。
【００２１】
また、上記擬似文書は、同一文書内の複数の同一の文字列についてはそのうち１つを残し、他を削除して生成されるようにすることが好ましい。このようにすれば一層インデックスサイズを小さくできる。もちろん、重複したものを残したままにしてもよい。
【００２２】
上記擬似文書において隣接する文字列の間の区切りを表すために空白文字を用いることができるが、これに限定されない。
【００２３】
また、上記予め選定された少なくとも１種類の文字列は、典型的には、ひらがな文字列およびカタカナ文字列である。
【００２４】
また、上記ビットベクターのビット長が所定長を超える場合には、上記ビットベクターを上記所定長位置で折り返して上記フラグビットのＯＲ論理をとり、ビットベクターを所定長に縮退させるようにしても良い。
【００２５】
また、上記ビットベクターのビット長が所定長を超える場合には、上記ビットベクターを上記所定長のシーケンスに分割し、さらにフラグビットを含まないシーケンスは省略して登録し、検索時に補完するようにしてもよい。このようなフォーマットのビットベクターは例えばハードディスクに記憶し、必要となったときにＮ−ｇｒａｍ単位で取りだして通常のフォーマットにメモリ上に展開するようにしても良い。
【００２６】
また、この発明の他の側面によれば、文書検索装置（１００）に：上記検索対象の文書の各々に対して、Ｎ−ｇｒａｍの各エントリについて当該Ｎ−ｇｒａｍの出現位置を表す出現位置情報を、当該位置に対応するビット位置にフラグビットを立てるビットベクターとして記憶する出現位置記憶手段（１５）と；検索キーワードを上記出現位置情報に照合して上記検索キーワードを含む文書を特定する文書特定手段（１７）とを設け；さらに、上記検索キーワードが２つ以上のＮ−ｇｒａｍから構成される場合に、当該Ｎ−ｇｒａｍの各々のビットベクターのフラグビット位置が対応する隣接関係にあることを判別して上記検索キーワードを含む文書を特定するようにしている。
【００２７】
この構成においては、Ｎ−ｇｒａｍの出現位置をビットベクターで表現しているのでＮ−ｇｒａｍの隣接関係をシフト演算およびＡＮＤ演算で処理することができる。
【００２８】
また、この発明の他の側面によれば、文書検索装置（２００）に：形態素解析結果から生成された検索辞書を用いて文書検索を行なう第１検索手段と；Ｎ−ｇｒａｍ辞書を用いて文書検索を行なう第２検索手段とを設け；さらに上記第２検索手段に：検索対象の文書の各々から、ひらがな文字列、カタカナ文字列、アルファベット文字列、ならびに、ひらがな、カタカナおよびアルファベットの混合文字列のうちの予め選定された少なくとも１種類の文字列を、抽出して連結し、擬似文書を生成する擬似文書生成手段と；上記検索対象の文書の各々に対して、Ｎ−ｇｒａｍの各エントリについて当該Ｎ−ｇｒａｍの上記擬似文書中における出現位置を表す出現位置情報を記憶する出現位置記憶手段と；ひらがな文字列、カタカナ文字列、アルファベット文字列、ならびに、ひらがな、カタカナおよびアルファベットの混合文字列のうちの上記予め選定された少なくとも１種類の文字列により構成される検索キーワードを上記出現位置情報に照合して上記検索キーワードを含む文書を特定する文書特定手段とを設けるようにしている。
【００２９】
この構成によれば、形態素手法の検索とＮ−ｇｒａｍ手法の検索とを複合的に利用することにより、Ｎ−ｇｒａｍ手法の検索を、各々から、ひらがな文字列、カタカナ文字列、アルファベット文字列、ならびに、ひらがな、カタカナおよびアルファベットの混合文字列のうちの予め選定された少なくとも１種類の文字列に限定することができ、この結果、Ｎ−ｇｒａｍのインデックスを小さくすることができる。しかも、形態素語にない文字列の検索も確実に行なうことができる。
【００３０】
なお、この発明は装置またはシステムとして実現できるのみでなく、方法としても実現可能である。また、そのような発明の一部をソフトウェアとして構成することができることはもちろんである。またそのようなソフトウェアをコンピュータに実行させるために用いるソフトウェア製品もこの発明の技術的な範囲に含まれることも当然である。
【００３１】
この発明の上述の側面および他の側面は特許請求の範囲に記載され以下実施例を用いて詳述される。
【発明の効果】
【００３２】
この発明によれば、インデックスサイズを抑制しつつＮ−ｇｒａｍの検索を簡易に行なえる。
【発明を実施するための最良の形態】
【００３３】
以下、この発明の実施例について説明する。
【実施例１】
【００３４】
まず、この発明の基本構成を実装した実施例１の文書検索装置１００について説明する。この実施例は、ひらがな語およびカタカナ語をキーワードとして受け取りＮ−ｇｒａｍの手法で文書を検索するものである。文書検索装置１００は計算機例えばパーソナルコンピュータ１０００にソフトウェアを例えば記録媒体１００１を用いてインストールすることにより実現される。パーソナルコンピュータ１０００は周知のとおりＣＰＵ、主メモリ、外部メモリ、バス、種々のＩ／Ｏ装置を具備して構成され、パーソナルコンピュータ１０００のハードウェア資源とソフトウェア資源とを協同させて文書検索装置１００の各部すなわち各機能ブロックが構成される。
【００３５】
図１は、実施例１の文書検索装置１００を示しており、この図において、文書検索装置１００は、文書入力部１０、文字列抽出部１１、文字列連結部１２、ビットベクター生成部１３、インデックス登録部１４、インデックス記憶部１５、キーワード入力部１６、検索部１７、検索結果出力部１８等を含んで構成される。文書入力部１０は、検索対象の文書（電子データ）を入力するものである。文書の入力は種々の態様で行なうことができる。ファイル管理システム上の１つ、または１群の文書ファイルを指定して入力していも良いし、ファイル転送やメッセージ転送で入力しても良い。入力文書をその属性や単語ベクトル等により選択しても良い。文字列抽出部１１は、文書中のひらがな文字列およびカタカナ文字列を抽出する。形態素情報を用いて漢字等とともに１の形態素語を構成するものは除くようにしても良い。この例では、ひらがな文字列およびカタカナ文字列のみを対象にするが、そのほかに、適宜に、ひらがな・カタカナ混合文字列、アルファベット文字列、ひらがな・アルファベット混合文字列、カタカナ・アルファベット混合文字列、ひらがな・カタカナ・アルファベット混合文字列を抽出するようにしても良い。文字列連結部１２は、抽出した文字列をその区切りを判別可能に連結して擬似文書として構成するものである。抽出した文字列はその種類ごとに複数の擬似文書に分けて構成されるようにしても良い。元の文書に含まれていても、抽出対象でない語は擬似文書から省かれそのサイズをコンパクトにすることができる。ビットベクター生成部１３は、ひらがな文字列（ひらがな語）およびカタカナ文字列（カタカナ語）を実現可能な各Ｎ−ｇａｒｍについて各擬似文書におけるその出現位置をフラグビットで示すビットベクターを生成するものである。ビットベクターについては後に例を挙げて説明する。インデックス登録部１４は、ビットベクターを文書検索用のインデックスとしてインデックス記憶部１５に登録する。キーワード入力部１６は、ひらがな文字列またはカタカナ文字列からなるキーワードを入力するものである。このキーワードは検索ユーザが直接に入力するものでも良いし、ユーザが入力した検索条件を所定のフロントエンドで処理してひらがな語およびカタカナ語に該当する部分をキーワード入力部１６から入力しても良い。検索部１７は、入力されたキーワードをＮ−ｇａｒａｍに分解して、当該Ｎ−ｇａｒａｍの擬似文書中の位置情報から当該擬似文書中にキーワードが含まれるかどうかを判別する。この点についても後に例を挙げて説明する。検索結果出力部１８は、擬似文書中に、すなわち入力文書中に、キーワードが含まれるかどうかを出力する。なお、該当文書のリストを出力するようにしても良い。
【００３６】
図２は、入力文書のインデックス登録処理のフローを示しており、図６は検索処理のフローを示している。
【００３７】
まず、入力文書のインデックス登録処理について図２を参照して説明する。ここでは、図３に示す文書を例に挙げて説明する。図３の文書は、文１〜文５により構成され、文１は「あいうえお」のひらがな文字列を有し、文２は「あいう」のひらがな文字列を有し、文３は「えおかきくけこ」のひらがな文字列を有し、文４は「あいう」の文字列を有し、文５は「えおかき」のひらがな文字列を有する。この例では、ひらがな文字列の例を示したが、カタカナ文字列を含む場合があることはもちろんである。
【００３８】
図２のインデックス登録処理の例は以下のとおりである。
【００３９】
［ステップＳ１０］：検索対象の文書を文書入力部１０により入力する。文書は図３に示すようなものとする。
【００４０】
［ステップＳ１１］：文書からひらがな文字列およびカタカナ文字列を文字列抽出部１１により抽出する。この文字列の抽出は文字種を用いて行なうことができる。
【００４１】
［ステップＳ１２］：抽出した文字列を文字列連結部１２により図４に示すように順次に連結して擬似文書を生成する。文字列の間に区切りコードを挿入する。この例では空白文字を用いた。さらに、同じ文字列が出現した場合（例えば、文２の「あいう」と文４の「あいう」）には、連結を省略する。同一の文字列については１つだけ登録しておけばその出現を検索可能であるからである。もちろん、擬似文書のサイズが大きくなるが、同一文字列を繰り返し登録するようにしても良い。逆に、ある文字列が他の文字列の部分文字列になる場合、連結を省略して擬似文書のサイズをさらに小さくしても良い。
【００４２】
［ステップＳ１３］：擬似文書の各文字位置をビットで表し、各Ｎ−ｇｒａｍについてその先頭位置にフラグビット（例えば「１」）を立てる。ここでは、Ｎを３とした。図４の例では、「あいう」のＮ−ｇｒａｍは、第０ビット、第６ビットにあるので、第０ビット、第６ビットにフラグビット（黒で示す）を立てたビットベクターが生成される。同様に「いうえ」のＮ−ｇｒａｍについては第２ビットにフラグビットを立てたビットベクターが生成される。同様にして実現可能なＮ−ｇｒａｍについてビットベクターが生成される。
【００４３】
［ステップＳ１４］：インデックス登録部１４が入力文書のビットベクターをインデックスとしてインデックス記憶部１５に登録する。このようにして、各Ｎ−ｇｒａｍのエントリに対して、それを含む文書ＩＤおよびそのビットベクターが生成され、インデックスレコードとして登録される。
【００４４】
図６の検索処理の例は以下のとおりである。
【００４５】
［ステップＳ２０］：キーワード入力部１６によりひらがな文字列またはカタカナ文字列のキーワードを入力する。
【００４６】
［ステップＳ２１］：検索部１７により、入力キーワードの文字列をＮ−ｇｒａｍに分解する。この例ではＮは３である。例えば、入力キーワードが「おかきくけこ」であれば、「おかき」と「くけこ」に分解する。
【００４７】
［ステップＳ２２］：検索部１７により、インデックス記憶部１５からＮ−ｇｒａｍに対応する文書ＩＤとビットベクターを取り出す。この例では図７で示すように「おかき」のビットベクターと「くけこ」のビットベクターが取り出される。
【００４８】
［ステップＳ２３］：検索部１７により、ビットベクターの隣接間隔を判別して該当する文字列「おかきくけこ」があるかどうかを判別する。この例では、図７に示すように、ビット位置の差は「３」であり、「おかきくけこ」が存在することが判別される。なお、この判別処理の詳細については後に詳述する。他方、「うえおかきく」をキーワードとして「うえお」のＮ−ｇｒａｍと「かきく」のＮ−ｇｒａｍを用いたときには、図８に示すように隣接関係がないことが判明し、該当するキーワードがないことがわかる。
【００４９】
この検索結果は検索結果出力部１８により出力される。
【００５０】
ここで、ビットベクターを用いたＮ−ｇｒａｍの隣接関係判別処理の詳細な例について説明する。
【００５１】
図９は隣接関係判別処理（キーワード検索処理）の詳細な処理例のフローを示しており、その処理は以下のとおりである。
【００５２】
［ステップＳ３０］：キーワードを構成するすべてのＮ−ｇｒａｍ（検索語ともいう）についてインデックスを検索して同じ文書ＩＤであれば、それぞれのビットベクターを取りだしてくる。ここでは、「おかきくけこさしす」のキーワードに対して「おかき」、「くけこ」、「さしす」のＮ−ｇｒａｍについてインデックスを検索して所定の文書ＩＤについて図１０に示すようなビットベクターが取り出された場合を例を挙げて説明する。
【００５３】
［ステップＳ３１］：ｉ番目のビットベクターを右に３ビットシフトし、ｉ＋１番目のビットベクターとのＡＮＤを取ってその結果をｉ＋１番目のビットベクターとする。（ｉの初期値は０）  さらにｉに１足す。
【００５４】
［ステップＳ３２］：つぎのビットベクターがあるかどうか判別する。あればステップＳ３１に戻り処理を繰り返す。つぎのビットベクターがなければステップＳ３３へ進む。
【００５５】
［ステップＳ３３］：ビットベクター中に「１」が立ってるかかどうか判別する。「１」が立っていれば当該文書中のＮ−ｇｒａｍの間に対応する隣接関係があり、検索キーワードが存在すること（ヒット）を示し、なければ当該文書中のＮ−ｇｒａｍの間に対応する隣接関係がなく検索キーワードが存在しないことを示す。
【００５６】
この例をさらに図１１に示す。この図から明らかなように、ビットベクターのシフト演算およびＡＮＤ演算により簡易に処理することができる。
【００５７】
つぎに実施例１の変形例について説明する。
【００５８】
図１２は、ビットベクターのサイズを抑制するものである。図１２の例では、１０００ビットごとに折り返して１０００ビットを超えるビットベクターを１０００ビットのビットベクターに縮退させるようにしている。重なるビットについてはＯＲ演算しておく。この場合、ＯＲ演算することにより、本来、対応する隣接関係にないＮ−ｇｒａｍの間でも、誤って対応する隣接関係があると判別する場合もあるが、検索漏れは生じない。もちろん、ビットベクターを１０００ビット長でなく任意のサイズに設定することが可能である。
【００５９】
図１３は、ビットベクターを複数のシーケンスに分けて、フラグビットの内シーケンスについては省略するようにしたものである。図１３の例では、ビットベクター（図１３（Ａ））を所定長例えば１バイトのシーケンスに分け（図１３（Ｂ））、シーケンス番号を用いてシーケンス単位で管理できるようにし、シーケンス中にフラグビットがないときは当該シーケンス自体も省略する。すなわち、図１３（Ｃ）に示すようにＮ−ｇｒａｍを示す識別子（ＫＥＹ）のほかにシーケンス番号を用い、フラグビットを含まないシーケンスのシーケンス番号は省略するようにする。
【００６０】
実際には、図１３（Ｃ）のフォーマットのインデックスデータは図１４に示すように圧縮インデックス記憶部１５ｂ（例えばハードディスク）に記憶されており、キーワードを分解してＮ−ｇｒａｍを決定した段階で、該当するＮ−ｇｒａｍのインデックスデータ（図１３（Ｃ）のフォーマット）を圧縮インデックス記憶部１５ｂから取りだしてメインメモリ１５ａに展開して上述のシフト処理やＡＮＤ演算を行い隣接関係を判別する。
【実施例２】
【００６１】
つぎにこの発明を形態素解析手法のインデックスおよびＮ−ｇｒａｍ手法のインデックスの双方を利用した文書検索装置に適用した実施例２について説明する。
【００６２】
図１５は実施例２の文書検索装置２００を示しており、この図において、文書検索装置２００は、検索条件入力部２０、検索フロントエンド２１、Ｎ−ｇｒａｍ文書検索部２２、Ｎ−ｇｒａｍインデックス記憶部２３、形態素語文書検索部２４、形態素語インデックス記憶部２５、検索結果合成部２６、合成検索結果出力部２７等を含んで構成されている。この例も実施例１と同様に計算機にソフトウェアをインストールして実現できる。
【００６３】
検索条件入力部２０は、検索条件を入力するものである。検索条件は、自然文を入力するものでもよい。検索フロントエンド２１は、検索条件に従ってＮ−ｇｒａｍ文書検索部２２にひらがな文字列のキーワードやカタカナ文字列のキーワードを出力し、形態素語文書検索部２４に形態素語をキーワードとして出力する。Ｎ−ｇｒａｍ文書検索部２２およびＮ−ｇｒａｍインデックス記憶部２３は、図１のＮ−ｇｒａｍ文書検索装置１００に対応するものである。Ｎ−ｇｒａｍインデックス記憶部２３はインデックス記憶部１５に対応する。形態素語文書検索部２４は形態素語インデックス記憶部２５に記憶された形態素語単位のインデックスを参照して文書検索を行なうものである。形態素単位のインデックスは形態素語をエントリとしてその形態素語が出現する文書のＩＤを含むインデックスレコードからなるものである。文書中の出現位置情報を保持していても良い。
【００６４】
検索結果合成部２６はＮ−ｇｒａｍ文書検索部２２および形態素語文書検索部２４の各検索結果を合成するものである。同一のキーワードをＮ−ｇｒａｍ文書検索部２２および形態素語文書検索部２４に供給して検索結果のＯＲをとって漏れのない検索を行なうようにしてもよいし、検索条件中の、形態素語に含まれないひらがな文字列や同様のカタカナ文字列のキーワードをＮ−ｇｒａｍ文書検索部２２に供給し、検索条件中の形態素語に対応するキーワードを形態素語文書検索部２４に供給して、検索条件のＡＮＤまたはＯＲ条件にしたがって対応する処理を検索結果合成部２６で行なっても良い。合成検索結果出力部２７は合成検索結果を例えば文書リストとして出力する。
【００６５】
なお、この発明は上述の実施例に限定されるものではなくその趣旨を逸脱しない範囲で種々変更が可能である。例えば、上述の例ではスタンドアローンの装置として説明したが複数のコンピュータシステムを用いてこの発明の検索手法を実現しても良い。例えば文書検索サーバ装置と任意のクライアント装置（パーソナルコンピュータ、携帯情報端末等を含む）を用いて実現しても良い。
【図面の簡単な説明】
【００６６】
【図１】この発明の実施例１の文書検索装置の構成を説明するブロック図である。
【図２】上述実施例１のインデックス登録処理の例を説明するフローチャートである。
【図３】インデックス登録処理の動作を説明するためのものであり、文書例を説明する図である。
【図４】インデックス登録処理の動作を説明するためのものであり、擬似文書の例を説明する図である。
【図５】インデックス登録処理の動作を説明するためのものであり、ビットベクターの例を説明する図である。
【図６】上述実施例１の検索処理の例を説明するフローチャートである。
【図７】検索キーワードに対応するＮ−ｇｒａｍの近隣関係がある例を説明する図である。
【図８】検索キーワードに対応するＮ−ｇｒａｍの近隣関係がない例を説明する図である。
【図９】検索キーワードに対応するＮ−ｇｒａｍの近隣関係があるかどうかをビットベクターから判別する処理の例を説明するフローチャートである。
【図１０】図９のフローチャートにおいてＮ−ｇｒａｍの例を説明する図である。
【図１１】図９のフローチャートの動作例を説明する図である。
【図１２】上述実施例の変形例を説明する図である。
【図１３】上述実施例の他の変形例を説明する図である。
【図１４】上述他の変形例を説明する図である。
【図１５】この発明の実施例２の文書検索装置の構成を説明するブロック図である。
【符号の説明】
【００６７】
１０      文書入力部
１１      文字列抽出部
１２      文字列連結部
１３      ビットベクター生成部
１４      インデックス登録部
１５      インデックス記憶部
１５      インデックス記憶部
１５ａ      メインメモリ
１５ｂ      圧縮インデックス記憶部
１６      キーワード入力部
１７      検索部
１８      検索結果出力部
２０      検索条件入力部
２１      検索フロントエンド
２２      Ｎ−ｇｒａｍ文書検索部
２３      Ｎ−ｇｒａｍインデックス記憶部
２４      形態素語文書検索部
２５      形態素語インデックス記憶部
２６      検索結果合成部
２７      合成検索結果出力部
１００      文書検索装置
２００      文書検索装置
１０００      パーソナルコンピュータ
１００１      記録媒体
【図１】
2006209399.tif 000003
【図２】
2006209399.tif 000004
【図３】
2006209399.tif 000005
【図４】
2006209399.tif 000006
【図５】
2006209399.tif 000007
【図６】
2006209399.tif 000008
【図７】
2006209399.tif 000009
【図８】
2006209399.tif 000010
【図９】
2006209399.tif 000011
【図１０】
2006209399.tif 000012
【図１１】
2006209399.tif 000013
【図１２】
2006209399.tif 000014
【図１３】
2006209399.tif 000015
【図１４】
2006209399.tif 000016
【図１５】
2006209399.tif 000017