(57)【要約】      （修正有）【課題】N-gram（bi-gram）索引を用いた検索方式において、検索処理量や索引容量の増加を抑えながら、検索ノイズをさらに低減することが可能なテキスト検索装置、テキスト検索プログラム、及びテキスト検索方法を提供する。【解決手段】検索対象テキストを解析して検索語を抽出する検索対象テキスト部と、検索語を解析して語を切り出す検索解析部とを設け、それぞれ異なる解析ルールを用いて語の切り出しを行い、索引の生成、及びテキストの検索を行う。【選択図】  図１
2007219620.tif 000002
【特許請求の範囲】
【請求項１】
N-gram方式を用いてテキスト検索を行うテキスト検索装置において、
検索対象テキストをテキスト解析ルールに基づいて解析し、索引語を抽出する検索対象テキスト解析手段と、
前記索引語を用いて索引を生成する索引生成手段と、
検索条件に含まれる検索語を検索語解析ルールに基づいて解析し、該検索語から語を切り出す検索語解析手段と、
前記検索語から切り出した語に基づいて内部的な検索条件を生成する検索条件生成手段と、
前記内部的な検索条件に基づいて前記索引を検索する検索処理手段と
を具備することを特徴とするテキスト検索装置。
【請求項２】
前記テキスト解析ルールは、
前記検索対象テキスト内の処理単位文字列の最後の一文字を前記索引語として切り出すことが少なくとも規定され、
前記検索語解析ルールは、
前記検索語が２文字以上であって最後の一文字が非ASCII文字であると最後の一文字を語として切り出さないことが少なくとも規定されている
ことを特徴とする請求項１記載のテキスト検索装置。
【請求項３】
N-gram方式を用いたテキスト検索をコンピュータに実行させるテキスト検索プログラムにおいて、
検索対象テキストをテキスト解析ルールに基づいて解析し、索引語を抽出するステップと、
前記索引語を用いて索引を生成するステップと、
検索条件に含まれる検索語を検索語解析ルールに基づいて解析し、該検索語から語を切り出すステップと、
前記検索語から切り出した語に基づいて内部的な検索条件を生成するステップと、
前記内部的な検索条件に基づいて前記索引を検索するステップと
をコンピュータに実行させることを特徴とするテキスト検索プログラム。
【請求項４】
前記テキスト解析ルールは、
前記検索対象テキスト内の処理単位文字列の最後の一文字を前記索引語として切り出すことが少なくとも規定され、
前記検索語解析ルールは、
前記検索語が２文字以上であって最後の一文字が非ASCII文字であると最後の一文字を語として切り出さないことが少なくとも規定されている
ことを特徴とする請求項３記載のテキスト検索プログラム。
【請求項５】
N-gram方式を用いてテキスト検索を行うテキスト検索方法において、
検索対象テキストをテキスト解析ルールに基づいて検索対象テキスト解析手段で解析して索引語を抽出し、
前記索引語を用いて索引生成手段で索引を生成し、
検索条件に含まれる検索語を検索語解析ルールに基づいて検索語解析手段で解析して該検索語から語を切り出し、
前記検索語から切り出した語に基づいて検索条件生成手段で内部的な検索条件を生成し、
前記内部的な検索条件に基づいて検索処理手段で前記索引を検索する
ことを特徴とするテキスト検索方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、テキスト検索装置、テキスト検索プログラム、及びテキスト検索方法に関し、特に、単語や文章などをキーワードとして検索するテキスト検索装置、テキスト検索プログラム、及びテキスト検索方法に関するものである。
【背景技術】
【０００２】
複数のテキスト文章（検索対象テキスト）から目的となるテキストを検索する検索サービスへの要求項目として、検索性能、検索精度（ノイズや検索漏れ）、索引生成時間、索引容量などがあり、これらの項目は、検索漏れの低減を図ると検索ノイズが増えるといったように、トレードオフの関係にある。
【０００３】
例えば、検索漏れを低減する方法の一つとして、bi-gram索引を用いた検索方式があり、この検索方式では、（ａ）文書中の文字出現位置を保持した索引を利用する検索方式や、（ｂ）文書から抽出される索引語の並び順を保持した索引を利用する検索方式などを用いて検索ノイズの低減を図っている。
【０００４】
しかし、（ａ）の検索方式では、索引語の位置情報を示すため、文書の長さに比例したバイト長が必要となり、（ｂ）の検索方式に比べて索引容量が大きくなる。
【０００５】
また、（ａ）の検索方式では、文字の出現位置などを加味して検索を行うため、検索語の文字列長と索引語の位置情報を加味した計算量が増加し、（ｂ）の検索方式に比べて検索処理量も多くなる。
【０００６】
このため、重複パターンがある場合に既に処理した演算結果を再利用する方法（例えば、特許文献１参照）や、単語の境界への成り易さに基づいてテキストを分割する方法（例えば、特許文献２参照）、索引語間で重複のない極大単語を用いた索引を別途保持する方法（例えば、特許文献３参照）などが提案されている。
【特許文献１】特開平１０−３０７８４１号公報
【特許文献２】特開平１０−３２０４２１号公報
【特許文献３】特開平１１−０７３４２９号公報
【発明の開示】
【発明が解決しようとする課題】
【０００７】
一方、（ｂ）の検索方式では、索引語の並び順だけを利用するため、（ａ）の検索方式に比べて検索ノイズが増加する。
【０００８】
例えば、文書から索引語を抽出する際に、あらかじめ定義された区切り文字で区切られた文字列単位で処理をする場合、
（例１）テキスト「東京都，…」の索引は、「東京」「京都」…となり、
（例２）テキスト「東京，京都，…」の索引は、「東京」「京都」…となる。
なお、この場合、カンマが区切り文字の１つである。
【０００９】
このため、索引語の並びが同じとなり、検索語「東京都」で、テキスト「東京，京都…」が検索され、検索ノイズが発生するという問題があった。
【００１０】
また、上記の例において、検索語「東京都」の「都」で全ての索引語の最後の文字をチェックし、「京都」の「都」を検索することによって検索ノイズを軽減する方法もあるが、検索時間が索引語の種類に比例していた。
【００１１】
さらに、索引語の文字の並びの逆順（例えば、「都京」「京東」など）を別途検索して検索ノイズを抑える方法もあるが、全体の索引容量が増加してしまうという問題があった。
【００１２】
そこで、本発明では、N-gram（bi-gram）索引を用いた検索方式において、検索処理量や索引容量の増加を抑えながら、検索ノイズをさらに低減することが可能なテキスト検索装置、テキスト検索プログラム、及びテキスト検索方法を提供することを目的とする。
【課題を解決するための手段】
【００１３】
本発明は、N-gram方式を用いてテキスト検索を行うテキスト検索装置において、検索対象テキストをテキスト解析ルールに基づいて解析し、索引語を抽出する検索対象テキスト解析手段と、前記索引語を用いて索引を生成する索引生成手段と、検索条件に含まれる検索語を検索語解析ルールに基づいて解析し、該検索語から語を切り出す検索語解析手段と、前記検索語から切り出した語に基づいて内部的な検索条件を生成する検索条件生成手段と、前記内部的な検索条件に基づいて前記索引を検索する検索処理手段とを具備することを特徴とする。
【００１４】
当該構成では、N-gram方式において、検索対象テキストと検索条件を異なる解析ルールに基づいて解析するため、検索語専用の解析ルールに基づいて検索語から語を切り出すことが可能であり、N-gram方式における検索ノイズを低減し、さらにN-gram索引における１文字検索を効率的に処理することができる。
【００１５】
また、前記テキスト解析ルールは、前記検索対象テキスト内の処理単位文字列の最後の一文字を前記索引語として切り出すことが少なくとも規定され、前記検索語解析ルールは、前記検索語が２文字以上であって最後の一文字が非ASCII文字であると最後の一文字を語として切り出さないことが少なくとも規定されていることが望ましい。
【００１６】
次に、本発明は、N-gram方式を用いたテキスト検索を情報処理装置に実行させるテキスト検索プログラムにおいて、検索対象テキストをテキスト解析ルールに基づいて解析し、索引語を抽出するステップと、前記索引語を用いて索引を生成するステップと、検索条件に含まれる検索語を検索語解析ルールに基づいて解析し、該検索語から語を切り出すステップと、前記検索語から切り出した語に基づいて内部的な検索条件を生成するステップと、前記内部的な検索条件に基づいて前記索引を検索するステップとを情報処理装置に実行させることを特徴とする。
【００１７】
当該構成では、N-gram方式において、検索対象テキストと検索条件を異なる解析ルールに基づいて解析するため、検索語専用の解析ルールに基づいて検索語から語を切り出すことが可能であり、N-gram方式における検索ノイズを低減し、さらにN-gram索引における１文字検索を効率的に処理することができる。
【００１８】
また、前記テキスト解析ルールは、前記検索対象テキスト内の処理対象文字列の最後の一文字を前記索引語として切り出すことが少なくとも規定され、前記検索語解析ルールは、前記検索語が２文字以上であって最後の一文字が非ASCII文字であると最後の一文字を語として切り出さないことが少なくとも規定されていることが望ましい。
【００１９】
本発明では、N-gram方式を用いてテキスト検索を行うテキスト検索方法において、検索対象テキストをテキスト解析ルールに基づいて検索対象テキスト解析手段で解析して索引語を抽出し、前記索引語を用いて索引生成手段で索引を生成し、検索条件に含まれる検索語を検索語解析ルールに基づいて検索語解析手段で解析して該検索語から語を切り出し、前記検索語から切り出した語に基づいて検索条件生成手段で内部的な検索条件を生成し、前記内部的な検索条件に基づいて検索処理手段で前記索引を検索することを特徴とする。
【００２０】
当該構成では、N-gram方式において、検索対象テキストと検索条件を異なる解析ルールに基づいて解析するため、検索語専用の解析ルールに基づいて検索語から語を切り出すことが可能であり、N-gram方式における検索ノイズを低減し、さらにN-gram索引における１文字検索を効率的に処理することができる。
【００２１】
また、前記テキスト解析ルールは、前記検索対象テキストの文字列の最後の一文字を前記索引語として切り出すことが少なくとも規定され、前記検索語解析ルールは、前記検索語が２文字以上であって最後の一文字が非ASCII文字であると最後の一文字を語として切り出さないことが少なくとも規定されていることが望ましい。
【発明の効果】
【００２２】
本発明では、bi-gram索引を用いた検索方式において、検索処理量や索引容量の増加を抑えながら、検索ノイズをより低減することができる。
【発明を実施するための最良の形態】
【００２３】
図１は、本発明におけるテキスト検索装置の構成の一例を示す機能ブロック図である。
【００２４】
同図に示すようにテキスト検索装置１０は、テキスト検索の対象となる検索対象テキストから、テキスト検索時に用いる索引語（キーワード）を抽出する検索対象テキスト解析部１１と、索引を生成する索引生成部１２と、索引を、図示しないＨＤＤ(Hard Disk Drive)などの記憶装置に格納して保持する索引保持部１３と、テキストを検索する際の条件である検索条件内の各検索語について、語の切り出しを行う検索語解析部１４と、検索語から抽出した語の並びを利用して、後述する内部的な検索条件を生成する検索条件生成部１５と、内部的な検索条件に基づいて索引を検索する検索処理部１６と、検索の結果に基づいて、ユーザが必要とするテキストのテキスト識別子を索引から取得・出力する検索結果抽出部１７とを具備して構成されている。
【００２５】
なお、当該テキスト検索装置は、各機能を備えたモジュールなどの組合せによって実現されるほか、汎用サーバなどの情報処理装置にインストールされた、本発明におけるテキスト検索方法を実現することが可能なテキスト検索プログラムなどを用いて実現することができる。
【００２６】
ここで、図２は、検索対象テキストから索引語群を抽出し、索引を生成する際の処理の流れの一例を示す模式図である。
【００２７】
まず、検索対象テキストにおけるマルチバイトの英数文字をASCII文字（半角英数字）に統一すると共に、半角カタカナを全角カタカナに統一するなど、索引語を正規化するための処理を行う。
【００２８】
次に、以下に示す解析ルール（テキスト解析ルール）に従って検索対象テキストを解析し、索引語群を抽出する。
【００２９】
テキスト解析ルール：
・記号や空白などは区切り文字とし、索引語としない。
・ASCIIと非ASCIIの連接部分は、索引語の区切りとする。
・検索語が２文字以上で、最後の１文字が非ASCII文字の場合、最後の１文字のみの語を索引語として抽出する。
・上記の区切りルールに基づいて、検索対象テキスト内の処理単位文字列を決定する。
・処理単位文字列については、以下のルールとする。
・連続するASCII文字は、１つの索引語とする。
・非ASCII文字は、bi-gramによる索引語抽出をする。
・２文字以上の非ASCII文字列の場合、bi-gramの索引語を抽出する際に、最後の１文字のみの語を索引語として抽出する。
【００３０】
このため、例えば、図２(ａ)に示すように、“東京都に支社を持つXYZ Co., Ltd.は新製品を発表した。”というテキストを検索対象として解析を行うと、図２(ｂ)に直線で囲んで示したように、“東京”“京都”“都に”“に支”“支社”“社を”“を持”“持つ”“XYZ”“Co”“Ltd”“は新”“新製”“製品”“品を”“を発”“発表”“表し”“した”“た”を索引語群として抽出する。
【００３１】
そして、抽出した索引語群を、抽出順序を維持した状態でインバーテッドファイル化し、図２(ｃ)に示す索引を生成する。
【００３２】
この際、少なくとも次の索引を生成することが望ましい。
・１つの索引語から、その索引語が出現するテキスト識別子を求めることが可能なデータ構造の索引（なお、全索引語が文字コード順にソートされている状態であるのが望ましい。）。
・１つのテキスト識別子から、そのテキスト内に出現する索引語とその出現順を求めることが可能なデータ構造の索引。
【００３３】
なお、索引語からそれが出現するテキストの識別子情報を取得することが可能なデータ構造の索引（前者）に、テキスト識別子とテキスト内での出現位置（何番目の索引語か、など）の情報を持たせることにより、テキスト識別子からその中に出現する索引語とその出現順を求めることが可能なデータ構造の索引（後者）を省略してもよい。
【００３４】
また、データ構造は、図２を用いて示したデータ構造に限られるものではなく、例えば、従来から用いられているインバーテッド方式のデータ構造など、インバーテッド方式の任意のデータ構造を用いることができる。
【００３５】
図３は、検索語を解析し、内部的な検出条件を生成する際の処理の流れの一例を示す模式図である。なお、ダブルクォートで囲まれた文字列は、その文字列が１つの検索語であることを示している。
【００３６】
まず、検索語を正規化するための処理を行い、検索語が２文字以上で最後の１文字が非ASCII文字の場合は、最後の１文字のみの語を索引語として抽出しない点を除いて、図２を用いて説明した、検索対象テキストを解析して索引語群を抽出する際の処理と同様の処理を行って語を切り出す。
【００３７】
すなわち、以下に示す解析ルール（検索語解析ルール）に従って検索語を解析して語の切り出しを行う。
【００３８】
検索語解析ルール：
・検索対象テキスト解析ルールと同様に、検索語から索引語を抽出する。ただし、検索語が２文字以上であり、最後の１文字が非ASCII文字である場合は、最後の１文字のみは抽出しない。
【００３９】
次に、検索語から切り出された語が連続して存在するテキストを検索するための検索条件（内部的な検索条件）を生成する。
【００４０】
このため、例えば、図３(ａ)に示すように“東京都”and“ＸＹＺ”を検索条件とすると、“東京都”からは“東京”と“京都”の語が切り出され、“ＸＹＺ”からは“ＸＹＺ”の語が切り出され、内部的な検索条件は、“東京”、“京都”が連続して出現すると共に、“ＸＹＺ”が出現するという検索条件となる。
【００４１】
また、図３(ｂ)に示すように“東京／京都  ＸＹＺ”を検索条件とすると、“東京”、“京”、“京都”、“都”、“ＸＹＺ”の語が切り出され、内部的な検索条件は、“東京”、“京”、“京都”、“都”、“ＸＹＺ”が連続して出現するという検索条件となる。
【００４２】
従来のbi-gram方式のテキスト検索では、検索語を“東京都”としても、“東京／京都”としても、共に“東京”、“京都”の語が切り出され、どちらの検索条件で検索しても同じ検索結果となるが、本発明におけるテキスト検索方法では、“東京都”を索引に含むテキストは、検索条件１で検出され、“東京／京都”を索引に含むテキストは、検索条件２で検出され、検索条件に応じた検索結果が得られるため、検索ノイズを低減することができる。
【００４３】
上記構成を用いて、本発明におけるテキスト検索装置は、まず、検索の対象となる検索対象テキストを検索対象テキスト解析部１１で解析して索引語を抽出し、索引生成部１２索引を生成すると共に、索引保持部１３で索引を格納して保持する。
【００４４】
次に、検索語解析部１４で検索語から語の切り出しを行い、内部的な検索条件を検索条件生成部１５で生成する。
【００４５】
そして、内部的な検索条件に基づいて通常の検索方法で索引を検索処理部１６で検索し、ユーザが必要とするテキストのテキスト識別子を検索結果抽出部１７で索引から取得して出力する。
【００４６】
図４は、本発明における検索装置において、検索対象テキストの索引を生成する際の処理の流れを示すフローチャートである。
【００４７】
まず、検索対象テキストを取得する（ステップ１００）と、検索対象テキストの解析ルールに基づいて当該検索対象テキストを解析する（ステップ１０１）。
【００４８】
次に、解析結果に基づいて索引語群を抽出し、索引を生成・格納する（ステップ１０２）。
【００４９】
図５は、本発明における検索装置において、ユーザが入力した検索条件に基づいて検索対象テキストの検索を行う際の処理の流れを示すフローチャートである。
【００５０】
まず、ユーザから入力された検索条件を取得する（ステップ２００）と、検索語の解析ルールに基づいて検索語を解析する（ステップ２０１）。
【００５１】
次に、解析結果に基づいて内部的な検索条件を生成し（ステップ２０２）、内部的な検索条件に基づいて索引を検索する（ステップ２０３）と共に、検索結果を出力する（ステップ２０４）。
【００５２】
なお、本発明における検索処理は、bi-gram方式に限られるものではなく、N-gram方式に用いることができる。
【００５３】
また、１文字の検索語が与えられた場合、その文字から始まる索引語に展開して、検索を行う。
【００５４】
このように本発明では、 従来、検索対象テキストと検索語を同じ解析ルールに基づいて解析を行っていたところを、検索対象テキストから索引語を切り出すための検索対象テキスト解析部と、検索語から語を切り出す検索語解析部の２種類を用意し、異なる解析ルールを用いて解析を行っているため、検索語から切り出した語と、テキストから切り出した索引語の並びを異ならせることができる。
【００５５】
例えば、検索対象のテキスト（文字列）が「東京都港区,…」の場合は、「東京」「京都」「都港」「港区」「区」…が索引となり、「東京,京都, …」の場合は、「東京」「京」「京都」「都」…が索引となる。
【００５６】
そして、検索語の解析を、検索対象テキストの解析と同様に処理する（従来の方法）と、検索語「東京都」で、「東京」「京都」「都」が連続して出現するテキストを検索することとなり、テキスト「東京都港区,…」を検索することができない。
【００５７】
一方、本発明では、検索語の解析時と、検索対象テキストの解析時とで解析ルールが異なるため、検索語が「東京都」の場合は、「東京」「京都」の語が切り出され、検索語が「東京,京都」の場合は、「東京」「京」「京都」の語が切り出される。
【００５８】
このため、検索語「東京都」ではテキスト「東京都港区, …」、検索語「東京,京都」ではテキスト「東京,京都, …」のみが検索される。
【００５９】
従って、本発明では、検索語に応じた検索結果を得ることが可能であり、bi-gram（N-gram）方式を用いて、検索ノイズを低減することができる。
【図面の簡単な説明】
【００６０】
【図１】本発明おけるテキスト検索装置の構成の一例を示す機能ブロック図である。
【図２】索引を生成する際の処理の流れの一例を示す模式図である。
【図３】検索語を解析し、内部的な検出条件を生成する際の処理の流れの一例を示す模式図である。
【図４】検索対象テキストの索引を生成する際の処理の流れの一例を示すフローチャートである。
【図５】ユーザが入力した検索条件に基づいて検索対象テキストの検索を行う際の処理の流れの一例を示すフローチャートである。
【符号の説明】
【００６１】
１０…テキスト検索装置
１１…検索対象テキスト解析部
１２…索引生成部
１３…索引保持部
１４…検索語解析部
１５…検索条件生成部
１６…検索処理部
１７…検索結果抽出部
【図１】
2007219620.tif 000003
【図２】
2007219620.tif 000004
【図３】
2007219620.tif 000005
【図４】
2007219620.tif 000006
【図５】
2007219620.tif 000007