(57)【要約】【課題】ダブル配列による前方一致検索を高速に行うことのできる辞書検索装置を得る。【解決手段】ダブル配列索引探索手段１０２は、ダブル配列索引１１１に基づいて、与えられた検索文字列に該当するノードを探索する。最小・最大子ノード探索手段１０３は、最小・最大子ノード索引１１２に基づいて、ダブル配列索引探索手段１０２で探索されたノードの子ノードのうち、辞書順で最小の文字列となるノードと最大の文字列となるノードとを探索する。単語抽出手段１０４は、単語リスト１１３より、最小・最大子ノード探索手段１０３で探索された最小ノードに対応する単語から最大ノードに対応する単語までの単語を抽出する。【選択図】図１
2010205119.tif 000002
【特許請求の範囲】
【請求項１】
検索文字列が与えられた場合、ダブル配列索引より当該検索文字列に該当するノードを探索するダブル配列索引探索手段と、
前記ダブル配列索引中のトライ構造における子ノードのうち辞書順で最小となる登録単語へ遷移するための情報と最大となる登録単語へ遷移するための情報とを格納する最小・最大子ノード索引に基づいて、前記ダブル配列索引探索手段で探索されたノードの子ノードのうち、辞書順で最小の文字列となるノードと最大の文字列となるノードとを探索する最小・最大子ノード探索手段と、
前記登録単語を辞書順にソートして格納する単語リストから、前記最小・最大子ノード探索手段で探索された最小ノードに対応する単語から最大ノードに対応する単語までの単語を抽出する単語抽出手段とを備えた辞書検索装置。
【請求項２】
単語リストは、登録単語を所定の数ごとに分割した複数のブロックからなり、
前記単語リストに新たな単語を登録する場合は、前記登録単語のうち、前記新たな単語よりも辞書順で小さい最大の単語を検索し、当該検索した単語のブロックに前記新たな単語を追加するブロック化単語リスト作成手段を備えたことを特徴とする請求項１記載の辞書検索装置。
【請求項３】
単語リストは、登録単語を所定の数ごとに分割した複数のブロックからなり、かつ、各登録単語にスコアが付与されていると共に、ブロックごとにそのブロックに属する登録単語の最大スコアを有し、
単語抽出手段は、前記単語リストから、前記スコアが上位である任意の件数の単語を抽出する場合、出力候補最小スコアより前記最大スコアが小さいブロックは抽出対象から除外することを特徴とする請求項１または請求項２記載の辞書検索装置。
【請求項４】
単語リストは、同一の形態素を持つ単語の集合でブロックごとに分割され、各登録単語にスコアが付与されていると共に、ブロックごとにそのブロックに属する登録単語の最大スコアを有し、
単語抽出手段は、前記スコアが上位である任意の件数の単語を抽出する場合、出力候補最小スコアより前記最大スコアが小さいブロックは抽出対象から除外することを特徴とする請求項１記載の辞書検索装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ダブル配列を用いて辞書検索を行う辞書検索装置に関する。
【背景技術】
【０００２】
従来のダブル配列による辞書検索では、ＢａｓｅとＣｈｅｃｋと呼ばれる２つの配列によってトライ構造を実現し、高速な辞書検索と共通接頭辞検索を行っていた（例えば、非特許文献１参照）。また、トライ構造による辞書検索において、逆方向トライによってワイルドカードや正規表現を含む文字列検索を高速に行う方法も提案されている（例えば、特許文献１参照）。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特許第２６８３８７０号公報
【非特許文献】
【０００４】
【非特許文献１】青江：ダブル配列による高速ディジタル検索アルゴリズム，電子通信学会論文誌，Ｊ７１−Ｄ，Ｎｏ．９，ｐｐ．１５９２−１６００（１９８７）
【発明の概要】
【発明が解決しようとする課題】
【０００５】
従来の検索方式では、入力文字を元に１文字ずつ遷移し、その都度遷移先が正しいか確認する。このため、形態素解析器における辞書検索のように入力文字列の先頭部分が辞書中の単語として登録されているか判定する共通接頭辞検索は高速に実現できる一方、数文字の入力文字列に対して、これを先頭に含む単語を辞書から検索する前方一致検索は高速にはできないという問題があった。
【０００６】
以下、従来方式の問題点を明らかにするため、ダブル配列による単語検索について簡単に説明する。
ダブル配列はトライ構造を２つの配列上で表現したものであり、図１５は｛“ａａａ”，“ａｂｃ”，“ａｂｃｄ”，“ａｂｆｇｈ”，“ａｆｇｈｉ”｝を登録したダブル配列の例を示したものである。ダブル配列は、Ｂａｓｅ配列とＣｈｅｃｋ配列からなり、Ｓｔａｔｅは配列のインデックスを示し、トライ構造のノードに相当する。図１６はこのダブル配列が表現するトライ構造を図示したものである。図１５のＳｔａｔｅが図１６のノード番号に対応する。ダブル配列によるトライの遷移（ノードの移動）はＢａｓｅ配列とＣｈｅｃｋ配列を参照しながら行う。
【０００７】
以降では文字集合をＳｃ＝｛‘＃’，‘ａ’，‘ｂ’，…，‘ｚ’｝、文字集合と１：１に対応する内部コード集合をＳｃｏｄｅ＝｛１，２，３，…，２７｝とし、ＳｃからＳｃｏｄｅへの写像をＣｏｄｅ（）で表す。例えばＣｏｄｅ（‘ｂ’）＝３となる。‘＃’は文字列の終端を表す特殊な文字であるとし、終端記号と呼ぶことにする。
ダブル配列における遷移では、現在のＳｔａｔｅをｓ、遷移先のＳｔａｔｅをｔ、入力文字をｃとすると下記の（式１）に従ってｔを求める。
【０００８】
ｔ＝Ｂａｓｅ［ｓ］＋Ｃｏｄｅ（ｃ）        （式１）
このとき、
Ｃｈｅｃｋ［ｔ］＝ｓ                      （式２）
であれば遷移は成功となる。Ｂａｓｅ［ｔ］＝−１のとき単語の終端であることを示し、そこで遷移は終了する。もし、Ｃｈｅｃｋ［ｔ］≠ｓであれば、文字ｃによる遷移はできず、つまり、そのような文字列が登録されていないということになる。遷移できなくなるか、文字列の終端に辿りつくまで（式１）により遷移することで単語の検索が可能である。
このようなＢａｓｅ配列とＣｈｅｃｋ配列を構成する方法は上記の非特許文献１に示されているように公知である。以下に文字列を検索する例を示す。
【０００９】
（例１）“ａｂｃ”が存在するか検索する。
１．Ｓｔａｔｅ＝１から“ａ”（Ｃｏｄｅ（‘ａ’）＝２）により遷移し、Ｂａｓｅ［１］＝１なので、Ｓｔａｔｅ＝Ｂａｓｅ［１］＋Ｃｏｄｅ（‘ａ’）＝３となる。Ｃｈｅｃｋ［３］＝１なので遷移は成功する。
２．Ｓｔａｔｅ＝３から“ｂ”（Ｃｏｄｅ（‘ｂ’）＝３）により遷移し、Ｂａｓｅ［３］＝２なのでＳｔａｔｅ＝５となる。Ｃｈｅｃｋ［５］＝３なので遷移は成功する。
３．Ｓｔａｔｅ＝５から“ｃ”（Ｃｏｄｅ（‘ｃ’）＝４）により遷移し、Ｂａｓｅ［５］＝３なのでＳｔａｔｅ＝７となる。Ｃｈｅｃｋ［７］＝５なので遷移は成功する。
４．Ｓｔａｔｅ＝７から“＃”（終端記号，Ｃｏｄｅ（‘＃’）＝１）により遷移し、Ｂａｓｅ［７］＝７なので状態８となる。Ｃｈｅｃｋ［８］＝７なので遷移は成功する。
５．Ｂａｓｅ［８］＝−１なので文字列の終端であることが分かり、“ａｂｃ”が登録されていることが分かる。
【００１０】
（例２）“ａｂａ”が存在するか検索する。
１．Ｓｔａｔｅ＝１から“ａ”（Ｃｏｄｅ（‘ａ’）＝２）により遷移し、Ｂａｓｅ［１］＝１なのでＳｔａｔｅ＝３となる。Ｃｈｅｃｋ［３］＝１なので遷移は成功する。
２．Ｓｔａｔｅ＝３から“ｂ”（Ｃｏｄｅ（‘ｂ’）＝３）により遷移し、Ｂａｓｅ［３］＝２なのでＳｔａｔｅ＝５となる。Ｃｈｅｃｋ［５］＝３なので遷移は成功する。
３．Ｓｔａｔｅ＝５から“ａ”（Ｃｏｄｅ（‘ａ’）＝２）により遷移し、Ｂａｓｅ［５］＝３なのでＳｔａｔｅ＝５となる。Ｃｈｅｃｋ［５］＝３なので遷移は失敗し、“ａｂａ”が登録されていないことが分かる。
【００１１】
しかしながら、上記のように入力文字を元に１文字ずつ遷移し、その都度遷移先が正しいか確認することで遷移を確定させるため、前方一致検索を行うためには遷移可能な文字を再帰的に探索する必要がある。例えば“ａｂ”に前方一致する単語を探索するには、以下のようになる。
【００１２】
（例３）“ａｂ”に前方一致する単語を検索する。
１．Ｓｔａｔｅ＝１から“ａ”（Ｃｏｄｅ（‘ａ’）＝２）により遷移し、Ｂａｓｅ［１］＝１なのでＳｔａｔｅ＝３となる。Ｃｈｅｃｋ［３］＝１なので遷移は成功する。
２．Ｓｔａｔｅ＝３から“ｂ”（Ｃｏｄｅ（‘ｂ’）＝３）により遷移し、Ｂａｓｅ［３］＝２なのでＳｔａｔｅ＝５となる。Ｃｈｅｃｋ［５］＝３なので遷移は成功する。
３．Ｓｔａｔｅ＝５から∀ｘ∈Ｓｃについて（式１）により新しいＳｔａｔｅ＝ｔを計算し、Ｃｈｅｃｋ［ｔ］＝５であるものを列挙する。｛‘ｃ’，‘ｆ’｝が得られる。
４．Ｓｔａｔｅ＝５から上記３．で得られた“ｃ”（Ｃｏｄｅ（‘ｃ’）＝４）により遷移し、Ｂａｓｅ［５］＝３なのでＳｔａｔｅ＝７となる。Ｃｈｅｃｋ［７］＝５なので遷移は成功する。
５．Ｓｔａｔｅ＝７から上記３．と同様の処理を再帰的に行い、｛“ａｂｃ”，“ａｂｃｄ”｝を発見する（得られる文字集合が終端記号のみになれば終了。終端記号以降は遷移はしない）。
６．上記４．〜５．と同様に、Ｓｔａｔｅ＝５から“ｆ”により遷移し、再帰的に探索することで｛“ａｂｆｇｈ”｝を発見する。
【００１３】
このように、従来の検索方式では再帰的に探索しなければならないため、前方一致検索を高速には行えないという問題があった。
【００１４】
この発明は上記のような課題を解決するためになされたもので、ダブル配列による前方一致検索を高速に行うことのできる辞書検索装置を得ることを目的とする。
【課題を解決するための手段】
【００１５】
この発明に係る辞書検索装置は、検索文字列が与えられた場合、ダブル配列索引より検索文字列に該当するノードを探索するダブル配列索引探索手段と、ダブル配列索引中のトライ構造における子ノードのうち辞書順で最小となる登録単語へ遷移するための情報と最大となる登録単語へ遷移するための情報とを格納する最小・最大子ノード索引に基づいて、ダブル配列索引探索手段で探索されたノードの子ノードのうち、辞書順で最小の文字列となるノードと最大の文字列となるノードとを探索する最小・最大子ノード探索手段と、登録単語を辞書順にソートして格納する単語リストから、最小・最大子ノード探索手段で探索された最小ノードに対応する単語から最大ノードに対応する単語までの単語を抽出する単語抽出手段とを備えたものである。
【発明の効果】
【００１６】
この発明の辞書検索装置は、ダブル配列索引探索手段で探索されたノードの子ノードのうち、辞書順で最小の文字列となるノードと最大の文字列となるノードとを探索し、最小ノードに対応する単語から最大ノードに対応する単語までの単語を抽出するようにしたので、ダブル配列による前方一致検索を高速に行うことができる。
【図面の簡単な説明】
【００１７】
【図１】この発明の実施の形態１による辞書検索装置を示す構成図である。
【図２】この発明の実施の形態１による辞書検索装置の検索手順を示すフローチャートである。
【図３】この発明の実施の形態１による辞書検索装置のダブル配列索引と最小・最大子ノード索引の一例を示す説明図である。
【図４】この発明の実施の形態１による辞書検索装置の単語リストの一例を示す説明図である。
【図５】この発明の実施の形態１による辞書検索装置の索引作成手順を示すフローチャートである。
【図６】この発明の実施の形態１による辞書検索装置の単語登録の手順を示すフローチャートである。
【図７】この発明の実施の形態２による辞書検索装置の構成図である。
【図８】この発明の実施の形態２による辞書検索装置のブロック化単語リストの一例を示す説明図である。
【図９】この発明の実施の形態２による辞書検索装置の単語登録の手順を示すフローチャートである。
【図１０】この発明の実施の形態２による辞書検索装置の単語登録における単語Ｗの探索手順を示すフローチャートである。
【図１１】この発明の実施の形態３による辞書検索装置の構成図である。
【図１２】この発明の実施の形態３による辞書検索装置のスコア付きブロック化単語リストの一例を示す説明図である。
【図１３】この発明の実施の形態３による辞書検索装置のスコア上位抽出の手順を示すフローチャートである。
【図１４】この発明の実施の形態４による辞書検索装置のスコア付きブロック化単語リストの一例を示す説明図である。
【図１５】一般的なダブル配列の一例を示す説明図である。
【図１６】図１５のダブル配列を木構造で示す説明図である。
【発明を実施するための形態】
【００１８】
実施の形態１．
図１は、実施の形態１の辞書検索装置を示す構成図である。
図示の辞書検索装置は、検索文字列入力手段１０１、ダブル配列索引探索手段１０２、最小・最大子ノード探索手段１０３、単語抽出手段１０４、検索結果出力手段１０５、索引作成手段１０６、ダブル配列索引１１１、最小・最大子ノード索引１１２、単語リスト１１３、単語集合１１４を備えている。
【００１９】
図１において、ダブル配列索引１１１は、ダブル配列法におけるＢａｓｅ配列とＣｈｅｃｋ配列を格納するデータである。最小・最大子ノード索引１１２は、辞書順で最小となる文字列へ遷移するための内部コードおよび最大となる文字列へ遷移するための内部コードを値に持つ配列を格納するデータである。単語リスト１１３は、登録されている単語の文字列を辞書順にソートして格納するデータである。単語集合１１４は、索引を作成する対象とする単語のリストである。
【００２０】
検索文字列入力手段１０１は、検索する文字列を入力するものである。ダブル配列索引探索手段１０２は、ダブル配列索引１１１に検索文字列入力手段１０１で入力された文字列が登録されているか探索し、該当するノードを取得するものである。最小・最大子ノード探索手段１０３は、ダブル配列索引探索手段１０２で探索されたノードの子ノードのうち、辞書順で最小の文字列となるノードと最大の文字列となるノードを最小・最大子ノード索引１１２より探索し、該当するノードを取得するものである。単語抽出手段１０４は、最小・最大子ノード探索手段１０３で取得した最小ノードと最大ノードより、単語リスト１１３から最小ノードに対応する単語および最大ノードに対応する単語およびその間に含まれる単語の集合を取得するものである。検索結果出力手段１０５は単語抽出手段１０４で取得した単語の集合を出力する手段である。索引作成手段１０６は単語集合１１４を入力とし、ダブル配列索引１１１、最小・最大子ノード索引１１２、単語リスト１１３を作成または更新し単語を登録するものである。
【００２１】
尚、辞書検索装置はコンピュータを用いて実現され、ダブル配列索引探索手段１０２〜単語抽出手段１０４および索引作成手段１０６は、それぞれの機能に対応したソフトウェアとこれを実行するためのＣＰＵやメモリといったハードウェアから構成されている。あるいは、これら手段をそれぞれ専用のハードウェアで構成してもよい。また、ダブル配列索引１１１〜単語集合１１４は、辞書検索装置と一体に設けてもよいが、辞書検索装置の外部に設け、ネットワークを介してダブル配列索引探索手段１０２〜単語抽出手段１０４がアクセスするといった構成であってもよい。
【００２２】
次に、実施の形態１の辞書検索装置の動作について説明する。
本実施の形態では単語の検索動作と単語の登録（索引作成）動作に分かれるため、まず検索動作について説明する。
図２は、本実施形態における検索の手順を示したフローチャートである。検索の手順は次の通りである。
まず、検索文字列入力手段１０１より検索する文字列を取得する（ステップＳＴ１）。ダブル配列索引探索手段１０２により検索文字列が登録されているか調べる（ステップＳＴ２）。ステップＳＴ３において、もし登録単語であればノード情報から単語抽出手段１０４により該当単語を取得する（ステップＳＴ４）。一方、ステップＳＴ３において登録単語ではないが前方一致する単語が存在する場合（ステップＳＴ５）、最小・最大子ノード探索手段１０３により前方一致する単語のうち辞書順で最小となる単語と最大となる単語のノードを取得し（ステップＳＴ６）、次に単語抽出手段１０４により前方一致するすべての単語を抽出する（ステップＳＴ４）。単語抽出手段１０４による単語抽出後、検索結果出力手段１０５により検索結果を出力し（ステップＳＴ７）、検索を終了する。登録単語ではなく前方一致する単語も存在しない場合はそのまま検索を終了する。
【００２３】
以下、図３から図６を参照しつつ、実施の形態１の動作の概要について説明する。
図３は、単語集合１１４を｛“ａａａ”，“ａｂｃ”，“ａｂｃｄ”，“ａｂｆｇｈ”，“ａｆｇｈｉ”｝とした場合のダブル配列索引１１１と最小・最大子ノード索引１１２の例である。同様に、図４は単語リスト１１３の例である。アドレス部１００１は単語リスト１１３に登録されている単語へアクセスするためのアドレスを示すものである。エントリ部１００２は登録されている単語を格納するものである。図３のＣｈｉｌｄ＿Ｆｉｒｓｔ配列には各Ｓｔａｔｅから遷移できる子ノードのうち、辞書順で最小となる単語に遷移するための内部コードを格納しておき、Ｃｈｉｌｄ＿Ｌａｓｔには辞書順で最大と成る単語に遷移するための内部コードを格納しておく。また、単語の終端に対応するノードのＢａｓｅ配列の値を従来では−１としていたが、本実施の形態では、対応する単語が登録されている単語リスト１１３へのアドレス値を負の値として格納する。
【００２４】
このように構成したダブル配列索引１１１、最小・最大子ノード索引１１２、単語リスト１１３を用いて、前方一致検索を行うには次のようにする。まず、ダブル配列索引探索手段１０２はダブル配列索引１１１上で検索文字列の先頭から１文字ずつ（式１）および（式２）を用いて遷移する。検索文字列の終端まで達したときのＳｔａｔｅをｔとしたとき、ｔ以降の遷移は最小・最大子ノード探索手段１０３によりＣｈｉｌｄ＿Ｆｉｒｓｔ配列に格納されている内部コードを用いて遷移する。Ｂａｓｅ配列の要素が負の値になるまで遷移したとき、それが検索単語に前方一致する単語のうち辞書順で最小となる単語の終端である。さらに、Ｓｔａｔｅ＝ｔからＣｈｉｌｄ＿Ｌａｓｔ配列に格納されている内部コードにより遷移する。Ｂａｓｅ配列の要素が負の値になるまで遷移したとき、それが検索単語に前方一致する単語のうち辞書順で最大となる単語の終端である。具体例として図３のダブル配列索引１１１、最小・最大子ノード索引１１２において“ａｂ”に前方一致する単語を検索する例を次に示す。
【００２５】
（例４）“ａｂ”に前方一致する単語をすべて取得する。
１．Ｓｔａｔｅ＝１から“ａ”（Ｃｏｄｅ（‘ａ’）＝２）により遷移し、Ｂａｓｅ［１］＝１なのでＳｔａｔｅ＝Ｂａｓｅ［１］＋Ｃｏｄｅ（‘ａ’）＝３となる。Ｃｈｅｃｋ［３］＝１なので遷移は成功する。
２．Ｓｔａｔｅ＝３から“ｂ”（Ｃｏｄｅ（‘ｂ’）＝３）により遷移し、Ｂａｓｅ［３］＝２なのでＳｔａｔｅ＝５となる。Ｃｈｅｃｋ［５］＝３なので遷移は成功する。
３．入力は終了したので、前方一致する最小単語を探索するためＣｈｉｌｄ＿Ｆｉｒｓｔ［５］を次の入力の内部コードとみなし遷移する。Ｂａｓｅ［５］＝３，Ｃｈｉｌｄ＿Ｆｉｒｓｔ［５］＝４なのでＳｔａｔｅ＝７となる。
４．Ｓｔａｔｅ＝７からＣｈｉｌｄ＿Ｆｉｒｓｔ［７］を入力の内部コードとみなし遷移する。Ｂａｓｅ［７］＝７，Ｃｈｉｌｄ＿Ｆｉｒｓｔ［７］＝１なのでＳｔａｔｅ＝８に遷移する。
５．Ｂａｓｅ［８］＝−５０１＜０なので単語の終端であり、これが最小単語にアクセスするための単語リスト１１３のアドレス値となる。−５０１をＦｉｒｓｔ＿Ｉｎｄｅｘとして記憶しておく。
【００２６】
６．Ｓｔａｔｅ＝５から前方一致する最大単語を探索するためＣｈｉｌｄ＿Ｌａｓｔ［５］を次の入力の内部コードとみなし遷移する。Ｂａｓｅ［５］＝３，Ｃｈｉｌｄ＿Ｌａｓｔ［５］＝７なのでＳｔａｔｅ＝１０に遷移する。以降同様にＣｈｉｌｄ＿Ｌａｓｔを入力の内部コードとみなし、Ｓｔａｔｅ＝１５に遷移する。
７．Ｂａｓｅ［１５］＝−５０３＜０なので単語の終端であり、これが最大単語にアクセスするための単語リスト１１３のアドレス値となる。−５０３をＬａｓｔ＿Ｉｎｄｅｘとして記憶する。
８．単語リスト１１３のＦｉｒｓｔ＿ＩｎｄｅｘからＬａｓｔ＿Ｉｎｄｅｘまでを順次取得する。図４を参照すると、５０１から５０３の単語集合｛“ａｂｃ”，“ａｂｃｄ”，“ａｂｆｇｈ”｝を得ることができる。ここで得られた単語はすべて“ａｂ”に前方一致する単語となる。
【００２７】
以上のように、Ｃｈｉｌｄ＿ＦｉｒｓｔとＣｈｉｌｄ＿Ｌａｓｔを辿って前方一致する単語の範囲を取得するようにしているので、単語の登録数には依らず高速にすべての前方一致単語を取得することができる。
【００２８】
次に、最小・最大子ノード索引１１２と単語リスト１１３を構築する方法について説明する。尚、ダブル配列索引１１１の構築については、例えば非特許文献１に記載されている方法を用いる。
図５は、単語集合からダブル配列索引１１１、最小・最大子ノード索引１１２、単語リスト１１３を作成する手順を示した図である。図６は、図５における１単語の登録について、ダブル配列索引１１１と最小・最大子ノード索引１１２を構築する手順を示した図である。
索引を作成するには、単語集合から１単語ずつ取り出し、図６の手順に従ってダブル配列索引１１１と最小・最大子ノード索引１１２を構築する（ステップＳＴ１１〜ＳＴ１３）。すべての単語を登録後、この段階ではダブル配列索引１１１におけるＢａｓｅ配列中の終端記号に対応する終端ノードの値は従来通り−１となっている。次にこの値を単語リスト１１３中の対応する単語へのアドレス値に更新する（ステップＳＴ１４〜ＳＴ１８）。まず、単語リスト１１３を辞書順で昇順ソートする（ステップＳＴ１４）。次に、単語リスト１１３の先頭から順に単語を取り出し（ステップＳＴ１５）、ダブル配列索引探索手段１０２により検索を行う（ステップＳＴ１６）。そして、この探索で、単語の終端記号に該当するノードを取得し、Ｂａｓｅ配列の値を単語リスト１１３へのアドレス値に置換する（ステップＳＴ１７）。ステップＳＴ１８において、すべての単語についてＢａｓｅ配列の値を置換すれば索引作成が終了する。
【００２９】
図６に示した１単語ごとの登録処理については次のようにする。最小・最大子ノード索引１１２は、Ｃｈｉｌｄ＿ＦｉｒｓｔとＣｈｉｌｄ＿Ｌａｓｔをすべて０に設定しておく。Ｃｈｉｌｄ＿ＦｉｒｓｔとＣｈｉｌｄ＿Ｌａｓｔの更新は、トライ構造の新規枝分かれ時に枝分かれするＳｔａｔｅでＣｈｉｌｄ＿ＦｉｒｓｔとＣｈｉｌｄ＿Ｌａｓｔの値を参照し行う。各単語を登録する場合、Ｓｔａｔｅの初期値をｓ＝１とし（ステップＳＴ２１）、
単語の文字列を１文字ずつ取得しながら（式１）と（式２）に従ってダブル配列索引１１１上で遷移する（ステップＳＴ２２〜ＳＴ２５）。
【００３０】
上記ステップＳＴ２２〜ＳＴ２５において、（式２）が成立しないＳｔａｔｅ＝ｓの場合は、例えば従来の方法を用いてＳｔａｔｅ［ｔ］におけるＢａｓｅ配列、Ｃｈｅｃｋ配列の値を設定する（ステップＳＴ２６）。そして、次の遷移文字ｃの内部コードがＣｈｉｌｄ＿Ｆｉｒｓｔ［ｓ］よりも小さいかあるいはＣｈｉｌｄ＿Ｆｉｒｓｔ［ｓ］が０の場合はＣｈｉｌｄ＿Ｆｉｒｓｔ［ｓ］＝Ｃｏｄｅ（ｃ）とする（ステップＳＴ２７〜ステップＳＴ２８）。同時に、ｃの内部コードがＣｈｉｌｄ＿Ｌａｓｔ［ｓ］よりも大きいかあるいはＣｈｉｌｄ＿Ｌａｓｔ［ｓ］が０の場合はＣｈｉｌｄ＿Ｌａｓｔ［ｓ］＝Ｃｏｄｅ（ｃ）とする（ステップＳＴ２９〜ステップＳＴ３０）。次に、現在のＳｔａｔｅ［ｓ］に遷移先のＳｔａｔｅ［ｔ］を代入し（ステップＳＴ３１）、ステップＳＴ２２からの処理を繰り返す。ｃが終端記号である場合はＣｈｉｌｄ＿Ｆｉｒｓｔ［ｓ］とＣｈｉｌｄ＿Ｌａｓｔ［ｓ］は更新せず、単語リスト１１３に登録中の単語を追加する。
【００３１】
図３のダブル配列索引１１１、最小・最大子ノード索引１１２に単語“ａｂｚ”を追加する例を示す。
（例５）“ａｂｚ”を追加する。
１．Ｓｔａｔｅ＝１から“ａ”（Ｃｏｄｅ（‘ａ’）＝２）により遷移し、Ｂａｓｅ［１］＝１なのでＳｔａｔｅ＝Ｂａｓｅ［１］＋Ｃｏｄｅ（‘ａ’）＝３となる。Ｃｈｅｃｋ［３］＝１なので遷移は成功する。
２．Ｓｔａｔｅ＝３から“ｂ”（Ｃｏｄｅ（‘ｂ’）＝３）により遷移し、Ｂａｓｅ［３］＝２なのでＳｔａｔｅ＝５となる。Ｃｈｅｃｋ［５］＝３なので遷移は成功する。
３．Ｓｔａｔｅ＝５から“ｚ”（Ｃｏｄｅ（‘ｚ’）＝２７）により遷移し、Ｂａｓｅ［５］＝３なのでＳｔａｔｅ＝３０となる。Ｂａｓｅ配列およびＣｈｅｃｋ配列はＳｔａｔｅ＝１９までしかないのでまだ登録されていないことが分かり、Ｓｔａｔｅ＝５からの新規子ノードとしてＳｔａｔｅ＝３０を作成する。すなわち、Ｂａｓｅ［３０］の値を然るべき値に設定し、Ｃｈｅｃｋ［３０］＝５とする。Ｂａｓｅ［３０］の値の求め方は、非特許文献１に記載の方法を用いる。ここではＢａｓｅ［３０］の値を３０とする。
【００３２】
４．Ｓｔａｔｅ＝５において、Ｃｏｄｅ（‘ｚ’）＝２７はＣｈｉｌｄ＿Ｆｉｒｓｔ［５］の値４より大きいためＣｈｉｌｄ＿Ｆｉｒｓｔ［５］は更新しない。
５．Ｓｔａｔｅ＝５において、Ｃｏｄｅ（‘ｚ’）＝２７はＣｈｉｌｄ＿Ｌａｓｔ［５］の値７より大きいためＣｈｉｌｄ＿Ｌａｓｔ［５］の値を更新しＣｈｉｌｄ＿Ｌａｓｔ［５］＝２７とする。
６．Ｓｔａｔｅ＝３０から“＃”（Ｃｏｄｅ（‘＃’）＝１）により遷移し、Ｂａｓｅ［３０］＝３０なのでＳｔａｔｅ＝３１となる。Ｂａｓｅ配列およびＣｈｅｃｋ配列はＳｔａｔｅ＝３０までしかないのでまだ登録されていないことが分かり、Ｓｔａｔｅ＝３０からの新規子ノードとしてＳｔａｔｅ＝３１を作成する。終端記号なのでＢａｓｅ［３１］の値を−１にし、Ｃｈｅｃｋ［３１］＝３０とする。
７．単語リスト１１３に“ａｂｚ”を追加する。
【００３３】
以上により、本実施の形態におけるダブル配列索引１１１、最小・最大子ノード索引１１２、単語リスト１１３を作成することができる。上記例ではノード作成時に枝分かれがないＳｔａｔｅ＝３０以降もＢａｓｅ配列とＣｈｅｃｋ配列に格納したが、非特許文献１のようにＴａｉｌ配列を用いても良い。
【００３４】
本実施の形態では登録する単語はアルファベットから構成されるものとし、内部コードをＳｃｏｄｅ＝｛１，２，３，…，２７｝としたが、一般の文字列（平仮名、漢字、中国語など）の場合も文字列を１バイト単位で区切り、内部コードとみなすことで全く同じように適用できる。また、その場合、Ｃｈｉｌｄ＿ＦｉｒｓｔとＣｈｉｌｄ＿Ｌａｓｔはそれぞれ１バイトで済むので、ダブル配列索引１１１と最小・最大子ノード索引１１２の容量は従来のダブル配列索引に比べて（Ｂａｓｅ配列サイズ×２）バイト大きくなるだけである。尚、これは、以降の実施の形態についても同様に適用可能である。
【００３５】
また、本実施の形態では単語リスト１１３に登録した単語の読みまたは見出しを格納することとしたが、単語の読みまたは見出しを含むその他の詳細情報を格納するデータベース上のインデックスを持つだけでも良い。その場合、単語リスト１１３から単語文字列を取得するにはデータベースからインデックスにより取得すればよい。
【００３６】
以上のように、実施の形態１の辞書検索装置によれば、検索文字列が与えられた場合、ダブル配列索引より検索文字列に該当するノードを探索するダブル配列索引探索手段と、ダブル配列索引中のトライ構造における子ノードのうち辞書順で最小となる登録単語へ遷移するための情報と最大となる登録単語へ遷移するための情報とを格納する最小・最大子ノード索引に基づいて、ダブル配列索引探索手段で探索されたノードの子ノードのうち、辞書順で最小の文字列となるノードと最大の文字列となるノードとを探索する最小・最大子ノード探索手段と、登録単語を辞書順にソートして格納する単語リストから、最小・最大子ノード探索手段で探索された最小ノードに対応する単語から最大ノードに対応する単語までの単語を抽出する単語抽出手段とを備えたので、ダブル配列による前方一致検索を高速に行うことができる。
【００３７】
実施の形態２．
上述した実施の形態１では、単語リスト１１３を全体で連続するデータとしたものであるが、単語リスト１１３を分割することで単語の追加または削除を高速に行う例を実施の形態２として次に示す。
図７は、実施の形態２の辞書検索装置の構成図である。
図において、ブロック化単語リスト１２１は実施の形態１における単語リスト１１３をブロック化して分割したものである。ブロック化単語リスト作成手段１０７は、ブロック化単語リスト１２１を作成または更新する手段である。
【００３８】
図８は、単語リスト１１３をブロック化単語リスト１２１のようにブロックに分割する例である。ブロックアドレス部１００１ａはブロック番号とブロック内アドレスを持ち、図８では「：」で区切って示している。「：」の左側がブロック番号、右側がブロック内アドレスを示す。また、エントリ部１００２ａは、ブロックアドレス部１００１ａに対応した登録単語である。単語リスト１１３をこのように分割するには、辞書順で昇順ソート済みの単語リスト１１３を固定の単語数ごとに分割すればよい。ただし、ブロックアドレス部１００１ａはブロック番号とブロック内アドレスの二つの値が必要になるため、ダブル配列索引１１１におけるＢａｓｅ配列の要素に格納できない。そこで、Ｃｈｉｌｄ＿Ｆｉｒｓｔ配列およびＣｈｉｌｄ＿Ｌａｓｔ配列を用いることにし、Ｂａｓｅ配列中の終端記号に対応する要素には実施の形態１のように負の値としてブロック内アドレスを格納する。このときＣｈｉｌｄ＿ＦｉｒｓｔとＣｈｉｌｄ＿Ｌａｓｔはいずれも０になっているが、実施の形態１における索引作成処理でＢａｓｅ配列中の単語の終端ノードに対応する要素の値を−１から単語リストへのアドレス値に置換する際、Ｃｈｉｌｄ＿ＦｉｒｓｔとＣｈｉｌｄ＿Ｌａｓｔも変更し、ブロック番号を格納するようにする。
【００３９】
次に、ブロック化単語リスト１２１およびダブル配列索引１１１のＢａｓｅ配列を更新する手順を説明する。図９はブロック化単語リスト１２１に対して、新規に単語を追加する場合の手順を示した図である。図１０は図９における単語Ｗを検索する手順を示した図である。ブロック化単語リスト作成手段１０７は以下のように動作する。
１．ダブル配列索引１１１に登録されている単語のうち、追加する単語よりも辞書順で小さい最大の単語Ｗを検索する（ステップＳＴ４１）。
２．検索された単語Ｗが登録されているブロック番号をＣｈｉｌｄ＿ＦｉｒｓｔとＣｈｉｌｄ＿Ｌａｓｔから取得する（ステップＳＴ４２）。
３．対応するブロックに単語を追加し、ブロック内で昇順ソートする（ステップＳＴ４３，ＳＴ４４）。
４．対応するブロックの新しく追加された単語以降の単語は、ブロック内アドレスが変更されるため、これらの単語をダブル配列索引１１１より検索し、終端記号に対応するＢａｓｅ配列の要素を新しいブロック内アドレスに置換する（ステップＳＴ４５）。
【００４０】
上記１．でダブル配列索引１１１に登録されている単語のうち、追加する単語よりも辞書順で小さい最大の単語Ｗを検索するには図１０に示した手順に従い、次のようにする。
１．追加する単語の先頭文字から順に（式１）により遷移する（ステップＳＴ５１〜ＳＴステップＳＴ５４）。
２．ステップＳＴ５４において（式２）が成立しないとき、そのとき遷移に利用した文字の内部コードをｙに保存する（ステップＳＴ５５）。
３．ｙをｙ−１とし、（式２）により遷移する（ステップＳＴ５６〜ＳＴ５８）。
４．ステップＳＴ５８において（式２）が成立しないとき３．に戻る。
５．追加する単語よりも辞書順で小さい最大の単語Ｗが存在するとき、ｙ＝０となる前に（式２）が成立するｙを必ず発見できる。次にこのｙで遷移するため、ｓにｔを代入する（ステップＳＴ５９）。
６．Ｂａｓｅ配列値が負であるとき（ステップＳＴ６０）、それが追加する単語よりも辞書順で小さい最大の単語Ｗの終端ノードであり、検索を終了する。
７．Ｂａｓｅ配列値が負でないとき、次の文字での遷移を探索するため、ｙに内部コードの最大値を代入し（ステップＳＴ６１）、４．に戻る。
【００４１】
以上のように単語リスト１１３をブロックに分割することにより、単語リスト１１３全体を変更する必要がなくなり、ブロック内だけの変更で済むため単語の追加にかかるコストを削減できる。
単語を削除する場合は、削除する単語を検索し、ダブル配列索引１１１から削除すればよい。単語リスト１１３ａからも削除する場合、削除した単語より辞書順で大きい単語についてはブロック内アドレスが変更されるため、追加するときと同様にそれらの単語をダブル配列索引１１１から検索し、終端記号に対応するＢａｓｅ配列の要素を新しいブロック内アドレスに置換すればよい。
【００４２】
以上のように、実施の形態２の辞書検索装置によれば、単語リストは、登録単語を所定の数ごとに分割した複数のブロックからなり、単語リストに新たな単語を登録する場合は、登録単語のうち、新たな単語よりも辞書順で小さい最大の単語を検索し、検索した単語のブロックに新たな単語を追加するブロック化単語リスト作成手段を備えたので、単語を登録する場合でも単語リスト全体を変更する必要がなく、単語リストのメンテナンスが容易となる。
【００４３】
実施の形態３．
以上の実施の形態では、検索単語に前方一致する単語を全件取得するものであるが、単語ごとに予め付与されたスコアで上位Ｍ件を取得する場合に、単語リストのブロック分割とブロック内最大スコアにより高速にＭ件を取得する例を次に実施の形態３として説明する。
【００４４】
図１１は、実施の形態３の辞書検索装置の構成図である。
スコア付きブロック化単語リスト１２２は単語ごとにスコアを持つブロックに分割された単語リストである。スコア付きブロック化単語リスト作成手段１０８はスコア付きブロック化単語リスト１２２を作成または更新する手段である。スコア上位単語抽出手段１０９は前方一致検索の結果得られた単語集合のうちスコアの上位Ｍ件を抽出する単語抽出手段である。
まず、説明のため、ブロック化されていないスコア付き単語リストから、検索文字列に前方一致する単語を検索し、スコアが上位のＭ件を取得する方法を述べる。
【００４５】
図１２における左側の図はスコア情報を持つスコア付き単語リスト１１３ａの例である。アドレス部１００１、エントリ部１００２、スコア部１００３から成る。各単語に付与するスコアは特に限定する必要はなく、例えばある文書内に単語が出現する頻度などでよい。まず実施の形態１のように前方一致する単語の単語リスト１１３上での範囲を検索する。その範囲の単語を順次取得し、スコアが上位のものだけを残すようにする。次に具体例を示す。
【００４６】
（例６）図１２のスコア付き単語リスト１１３から“ａ”に前方一致する単語を２件出力する。
１．実施の形態１と同様の方法により辞書順で最小の前方一致単語“ａａａ”と最大の前方一致単語“ａｚｚｚ”を検索し、それぞれが指すアドレス５００と５０５を取得する。
２．アドレス５００から順に単語リスト１１３を走査し、“ａａａ”，“ａｂｃ”を出力候補に追加する。
３．次に“ａｂｃｄ”を取得するが、上記手順２．の時点で出力候補のスコア最小値は３０となっており、“ａｂｃｄ”のスコアは５であるため出力候補に追加しない。
４．次に“ａｂｆｇｈ”を取得するが、スコアが最小スコア以下であるため出力候補には追加しない。
５．次に“ａｆｇｈｉ”を取得するが、スコアが最小スコア以下であるため出力候補には追加しない。
６．次に“ａｚｚｚ”を取得する。スコアは４０であり、現在のスコア最小値３０より大きいため現在の最小スコアである“ａａａ”を削除して“ａｚｚｚ”を出力候補に追加し、最小スコアを４０に更新する。
７．アドレス５０５に達したので現在の出力候補を出力とする。｛“ａｂｃ”，“ａｚｚｚ”｝
【００４７】
しかし、上記の方法では前方一致する単語がＮ個ある場合、Ｎ回の単語リストアクセスとスコア比較が発生するため効率が悪い。そこで単語リスト１１３を図１２のスコア付きブロック化単語リスト１２２のように所定の数ごとに複数のブロックに分割する。ブロックアドレス部１００１ａは実施の形態２と同様に「ブロック番号：ブロック内アドレス」と表記している。スコア部１００３ａは単語リスト１１３のスコア部１００３に対応する部分で各単語のスコアを格納するものである。ブロック内最大スコア部１００４は各ブロック内で最大のスコアを格納する。スコア付きブロック化単語リスト作成手段１０８は、単語追加時に実施の形態２のブロック化単語リスト作成手段１０７と同様に追加すべきブロックを検索して単語を追加する。ただし、その際、ブロック内最大スコア部１００４を参照し、追加する単語のスコアがブロック内最大スコアよりも大きければブロック内最大スコア部１００４を追加する単語のスコアに更新する。
【００４８】
図１３は、このような構成によりスコアの上位Ｍ件を取得する手順を示した図である。（例６）のように単語リストから順次単語を取得してスコアを比較する際に、ブロック内最大スコアと比較することによりブロック単位で読み飛ばすことができ、効率的に上位Ｍ件を取得できる。具体例を次に示す。
【００４９】
（例７）図１２のスコア付きブロック化単語リスト１２２から“ａ”に前方一致する単語を２件出力する。
１．出力候補のスコア最小値を０に初期化し、ブロック番号Ｂを最小単語のブロック番号、ブロック内アドレスＡを最小単語のブロック内アドレスとして初期化する（ステップＳＴ７１，ＳＴ７２）。そして、実施の形態１と同様の方法により辞書順で最小の前方一致単語“ａａａ”と最大の前方一致単語“ａｚｚｚ”を検索し、それぞれが指すブロックアドレス５：１４と７：１を取得する。
２．ブロックアドレス５：１４から順にスコア付きブロック化単語リスト１２２ｃを走査し、“ａａａ”を取得する。まだ１件も取得していないので出力候補に追加し、ブロック終了ではないのでブロック内アドレスＡをインクリメントする（ステップＳＴ７３→ＳＴ７４→ＳＴ７５→ＳＴ７８→ＳＴ７９→ＳＴ８０）。
３．次に“ａｂｃ”を取得する。まだ１件しか取得していないので出力候補に追加する。この時点で最小スコアは３０となる。ブロック内アドレスＡをインクリメントする（ステップＳＴ７３→ＳＴ７４→ＳＴ７５→ＳＴ７８→ＳＴ７９→ＳＴ８０）。
４．次に“ａｂｃａ”を取得するが、すでに出力候補を２件取得済みのため出力候補最小スコアとスコアを比較する（ステップＳＴ７３→ＳＴ７４→ＳＴ７６）。出力候補最小スコアのほうが大きいので出力候補には追加しない。ブロックの終了であるのでブロック番号Ｂをインクリメントする（ステップＳＴ７８→ＳＴ７９→ＳＴ８１）。
【００５０】
５．Ｂのインクリメントの結果、ブロック６を参照するが、ブロック６のブロック内最大スコアは２０であり、現在の最小スコア３０より小さいためこのブロック内には出力候補に追加すべき単語は存在しないことが分かる（ステップＳＴ８２）。ブロック６からの単語取得を行わず、Ｂをインクリメントしブロック７へ移動する（ステップＳＴ７９→ＳＴ８１）。
６．ステップＳＴ８２において、ブロック７のブロック内最大スコアは７０であり、現在の最小スコア３０より大きいため、このブロック内に出力候補に追加すべき単語が存在する可能性がある。そのため“ａｚｚｚ”を取得し、スコアは４０なので、現在のスコア最小値３０より大きいため現在の最小スコアである“ａａａ”を削除して“ａｚｚｚ”を出力候補に追加し、最小スコアを４０に更新する（ステップＳＴ８３→ＳＴ７３→ＳＴ７４→ＳＴ７６→ＳＴ７７）。
７．ステップＳＴ７８において、アドレス７：１に達したので現在の出力候補を出力とする｛“ａｂｃ”，“ａｚｚｚ”｝。
以上のように、単語リストを分割した上でブロック内最大スコアを格納することにより、ダブル配列による文字列の高速な検索と、効率的なスコアの上位抽出を行うことができる。
【００５１】
以上のように、実施の形態３の辞書検索装置によれば、単語リストは、登録単語を所定の数ごとに分割した複数のブロックからなり、かつ、各登録単語にスコアが付与されていると共に、ブロックごとにそのブロックに属する登録単語の最大スコアを有し、単語抽出手段は、単語リストから、スコアが上位である任意の件数の単語を抽出する場合、出力候補最小スコアより最大スコアが小さいブロックは抽出対象から除外するようにしたので、検索を高速に行うことができると共に、スコアが上位の単語を効率的に抽出することができる。
【００５２】
実施の形態４．
実施の形態３では単語リストの分割方法を所定の数ごととしたが、同一の形態素を持つ単語集合ごとにグループ化して分割することによって、グループ単位で効率的に検索結果を取得する例を次に実施の形態４として説明する。尚、実施の形態４における辞書検索装置の図面上の構成は実施の形態３と同様であるため、図１１の構成を用いて説明する。
【００５３】
図１４に、実施の形態４におけるスコア付きブロック化単語リスト１２２の例を示す。図１４における左側の図は形態素の区切りに「／」を挿入した単語リスト１１３ｂの例である。例えば、エントリ部１００２ｂの「とうかい／だいがく」は「とうかい」と「だいがく」の２つの形態素から成ることを示す。また、スコア部１００３ｂは、エントリ部１００２ｂに対応したスコアである。このような単語リストから検索文字列に前方一致する単語を検索して、該当する単語の先頭形態素を出力することを考える。スコア上位のＭ件だけを出力する場合は、グループ内のスコアの最大値をグループのスコアとみなしてスコア上位のグループを出力する。
【００５４】
図１４左の単語リスト１１３ｂの場合、「とう」に前方一致する単語は「とうかい／だいがく」，「とうかい／ほんせん」，「とうきょう／えき」，「とうきょう／だいがく／ひろば」，「とうきょう／だいがく／まえ」，「とうほく／だいがく」，「とうほく／ほてる」の７個であるが、それぞれの先頭グループは「とうかい」，「とうかい」，「とうきょう」，「とうきょう」，「とうきょう」，「とうほく」，「とうほく」となるので重複するものがある。重複を除去すると「とうかい」，「とうきょう」，「とうほく」の３つが出力となる。
【００５５】
スコアの上位２件を出力する場合、「とうかい」グループはグループ内の最大スコアが４５、「とうきょう」グループは７０、「とうほく」グループが４０なので、「とうかい」と「とうきょう」を出力する。
【００５６】
次に、本実施の形態が、単語リスト１１３ｂを同一の先頭形態素でグループ化してブロック分割することにより、効率的に上位Ｍ件を出力する例を示す。
スコア付きブロック化単語リスト１２２の例を図１４の右側に示す。エントリ部１００２ｃが「とうかい」，「とうきょう」，「とうほく」でグループ化し、ブロック分割してある。また、スコア部１００３ｃはエントリ部１００２ｃに対応したスコア、ブロック内最大スコア部１００４ａは、ブロック内の最大スコアを示している。ブロック７は同一の先頭形態素が複数無いため実施の形態３のように所定の単語数でブロック分割している。実施の形態３と同様に、単語抽出手段であるスコア上位単語抽出手段１０９は、ブロック単位で読み飛ばすことで、スコア上位のグループを効率的に取得できる。
【００５７】
例えば図１４右のスコア付きブロック化単語リスト１２２において、「と」に前方一致するスコア上位２件の単語の先頭グループを検索する場合、実施の形態２と同様に、まずブロックアドレス「４：１」から「７：１」までが前方一致する単語として検索する。
ブロックアドレス「４：１」から順次単語を取得し、先頭形態素「とうかい」とブロック内最大スコア４５を取得し出力候補に追加する。次にブロック５から先頭形態素「とうきょう」とブロック内最大スコア７０を取得し出力候補に追加する。この時点で出力候補グループの最小スコア４５であり、次のブロック６はブロック内最大スコアが４０なので読み飛ばすことができる。さらに次のブロック７はブロック内最大スコアが６５であるため順次単語を取得し、先頭形態素「とりつ」とスコア５０を取得し、出力候補中の「とうかい」を「とりつ」と入れ替える。ここで前方一致単語が終了するので、「とうきょう」と「とりつ」が出力となる。
【００５８】
以上のように出力形式に合わせてグループ化することで、効率的にスコア上位のグループを取得することができる。
本実施の形態では先頭形態素のみでグループ化したが、第二形態素以降でも階層的にグループ化することで出力の単位を任意の階層にすることも可能である。
【００５９】
以上のように、実施の形態４の辞書検索装置によれば、単語リストは、同一の形態素を持つ単語の集合でブロックごとに分割され、各登録単語にスコアが付与されていると共に、ブロックごとにそのブロックに属する登録単語の最大スコアを有し、単語抽出手段は、スコアが上位である任意の件数の単語を抽出する場合、出力候補最小スコアより最大スコアが小さいブロックは抽出対象から除外するようにしたので、単語リストを同一の形態素を持つ単語集合とした場合でも、検索を高速に行うことができると共に、スコアが上位の単語を効率的に抽出することができる。
【符号の説明】
【００６０】
１０１  検索文字列入力手段、１０２  ダブル配列索引探索手段、１０３  最小・最大子ノード探索手段、１０４  単語抽出手段、１０５  検索結果出力手段、１０６  索引作成手段、１０７  ブロック化単語リスト作成手段、１０８  スコア付きブロック化単語リスト作成手段、１０９  スコア上位単語抽出手段、１１１  ダブル配列索引、１１２  最小・最大子ノード索引、１１３  単語リスト、１１４  単語集合、１２１  ブロック化単語リスト、１２２  スコア付きブロック化単語リスト。
【図１】
2010205119.tif 000003
【図２】
2010205119.tif 000004
【図３】
2010205119.tif 000005
【図４】
2010205119.tif 000006
【図５】
2010205119.tif 000007
【図６】
2010205119.tif 000008
【図７】
2010205119.tif 000009
【図８】
2010205119.tif 000010
【図９】
2010205119.tif 000011
【図１０】
2010205119.tif 000012
【図１１】
2010205119.tif 000013
【図１２】
2010205119.tif 000014
【図１３】
2010205119.tif 000015
【図１４】
2010205119.tif 000016
【図１５】
2010205119.tif 000017
【図１６】
2010205119.tif 000018