(57)【特許請求の範囲】
【請求項１】
テキストを記憶するテキストバッファと、前記テキスト中の接尾の出現位置を記憶する整数配列を格納する第１の記憶装置と、前記テキスト中の各文字の頻度を記憶する文字頻度表を格納する第２の記憶装置と、前記整数配列のサイズと前記文字頻度表に記憶されている頻度とに基づいて前記テキスト中の各文字の範囲を定める範囲決定手段と、この定められた範囲内の文字を先頭文字とする前記テキスト中の前記接尾の出現位置を前記整数配列に格納する初期化手段と、この初期化手段による処理後の整数配列上の前記接尾の出現位置を、該接尾を構成する各文字に予め設定されている値に基づいてソートするソート手段と、このソート後の整数配列上の前記接尾の出現位置を第３の記憶装置に記憶する記憶手段と、前記範囲決定手段、前記初期化手段、前記ソート手段および前記記憶手段による処理を、前記テキスト中のすべての範囲について処理が完了するまで繰り返えさせて、前記テキストの接尾配列を複数に分割して求めて前記第３の記憶装置に順次記憶する制御手段と、を備えている索引作成装置。
【請求項２】
予め記憶されているテキスト中の各文字の範囲を定める処理を、予め格納されていて前記テキスト中の接尾の出現位置を記憶する整数配列のサイズと、予め格納されていて前記テキスト中の各文字の頻度を記憶する文字頻度表に記憶されている頻度とに基づいて範囲決定手段が行う範囲決定工程と、この定められた範囲内の文字を先頭文字とする前記テキスト中の前記接尾の出現位置を前記整数配列に格納する処理を初期化手段が行う初期化工程と、この初期化工程による処理後の整数配列上の前記接尾の出現位置を、該接尾を構成する各文字に予め設定されている値に基づいてソート手段がソートするソート工程と、このソート後の整数配列上の前記接尾の出現位置を所定の記憶装置に記憶する処理を記憶手段が行う記憶工程と、の各工程からなる処理を、前記テキスト中のすべての範囲について処理が完了するまで制御手段が繰り返して、前記テキストの接尾配列を複数に分割して求めて前記所定の記憶装置に順次記憶する索引作成方法。
【請求項３】
予め記憶さているテキスト中の各文字の範囲を定める処理を、予めに格納されていて前記テキスト中の接尾の出現位置を記憶する整数配列のサイズと、予め格納されていて前記テキスト中の各文字の頻度を記憶する文字頻度表に記憶されている頻度とに基づいて行う範囲決定工程と、この定められた範囲内の文字を先頭文字とする前記テキスト中の前記接尾の出現位置を前記整数配列に格納する初期化工程と、この初期化工程による処理後の整数配列上の前記接尾の出現位置を、該接尾を構成する各文字に予め設定されている値に基づいてソートするソート工程と、このソート後の整数配列上の前記接尾の出現位置を所定の記憶装置に記憶する記憶工程と、の各工程からなる処理を、前記テキスト中のすべての範囲について処理が完了するまで繰り返して、前記テキストの接尾配列を複数に分割して求めて前記所定の記憶装置に順次記憶することをコンピュータに実行させるプログラムを記憶しているコンピュータに読み取り可能な記憶媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
この発明は、索引作成装置、索引作成方法および記録媒体に関する。
【０００２】
【従来の技術】
テキストＴ中での文字列Ｐの出現位置を求める問題を、文字列照合（string matching）という。テキストＴが既知である場合、このテキストＴについて予め索引を作成して、その索引を利用して文字列照合を行うことで、高速な文字列照合が実現できる。
【０００３】
このような索引の例として、接尾配列(suffix array)が提案されている（U.Manber and G.Myers, "Suffix arrays: a new method for on-line string searches", SIAM jounal of computing, 22(5), pp.935-948, 1993を参照）。
【０００４】
この接尾配列の例を、テキストＴが“ＢＡＮＡＮＡ”である例について、以下の表１に示す。
【０００５】
【表１】
0004181723.tif 000002
【０００６】
テキストＴには、その末尾を表す記号“＄”を末尾に付与しておく。接尾とは、テキストＴ中の各文字からテキストＴの末尾までの範囲の文字列であり、Ｎ文字からなるテキストにはＮ個の接尾が定義できる。そして接尾の先頭文字と、テキストＴ中での接尾の出現位置とは１対１に対応する。この出現位置をポインタと呼ぶ。接尾配列とは、全てのポインタをそのポインタに対する接尾が辞書順になるように並べて得られるポインタ列である。ここで、接尾の辞書順はその接尾を構成する文字（接尾の構成文字と呼ぶ）に対して予め定義された文字値に基づいて定義される。この明細書においては各文字の文字値の大小を以下のように定める。
【０００７】
＄  ＜  Ａ  ＜  Ｂ  ＜  Ｎ
よって、上記の例からは以下の接尾配列が得られる。
【０００８】
接尾配列：  ５  ３  １  ０  ４  ２
この例で、最初のポインタ５に対応する接尾は“Ａ＄”であり、ポインタ３に対応する接尾“ＡＮＡ＄”より辞書順において若い。
【０００９】
そして、テキストＴ中での文字列Ｐの出現位置は、上記の接尾配列上の２分探索によって求めることができる。すなわち文字列Ｐを接頭とする接尾に対するポインタは文字列ＰのテキストＴ中での出現位置であり、それらポインタは接尾配列中に連続して並ぶため、その連続範囲を２分探索で求めればよい。
【００１０】
【発明が解決しようとする課題】
接尾配列を作成するには、対応する接尾を文字列とみなし、それをキーとしてクイックソート法等により接尾配列上のポインタをソートすることで実現できる。テキストがＮ文字からなり、各文字を１バイト、各ポインタを４バイトで１律に記憶する場合、（１＋４）×Ｎ＝５Ｎバイトの主記憶の記憶量が必要となる。
【００１１】
しかし、この場合に、テキストＴ中に文字列Ｄが重複して含まれているときは、文字列Ｄ中の全接尾について先頭から末までの文字比較を行うことになり、計算時間が急激に増大する（Ｄのサイズの２乗のオーダの計算量を要する）。例えば、文字列Ｄを“ＢＡＮＡＮＡ”とし、テキストＴを“ＢＡＮＡＮＡ＋ＢＡＮＡＮＡ＄”とする場合、ソートの過程において、表２に示すように、文字列Ｄ中の全接尾をその先頭から末まで比較しなければ、両者の辞書順は決定できない。
【００１２】
【表２】
0004181723.tif 000003
【００１３】
このように、かかる技術では、必要とする主記憶の記憶量が５Ｎバイトと、比較的少ない記憶量で済むものの、前記のようにテキストＴが重複する文字列を含む場合には、計算時間が急激に増大するという不具合がある。
【００１４】
一方、前記のU.Manberらによる従来技術においては、ダブリング法と呼ばれる技法により、テキストＴ中に重複文字列（一般には長い文字列の反復）がある場合でも、急激な計算時間の増大を招かない接尾配列の構成手段も提案されている。
【００１５】
しかし、かかる技術は、重複文字列への耐性がある（ロバストな）ものではあるが、必要とする主記憶の記憶量が８Ｎバイトとなり、前記の５Ｎバイト必要な技術に比べ、比較的多くの記憶量を要するという不具合がある。
【００１６】
別の課題として、前記した接尾配列の構成手段は、いずれも主記憶上で行うことを前提としている。そこで、必要となる主記憶の記憶量をより少なくするために、テキストＴを分割し、それら部分テキスト毎に接尾配列を構成し、それを外部記憶に記憶し、最後にそれら外部記憶上の部分接尾配列をマージする手段も提案されている。しかし、かかる手段では、外部記憶の読み込み、書き込み処理が多くなり、そのため多くの処理時間を要するという不具合がある。
【００１７】
この発明の目的は、高速処理で、かつ、コンパクトな記憶容量を用いて、テキストの接尾配列を求めることができるようにすることである。
【００１８】
【課題を解決するための手段】
請求項１に記載の発明は、テキストを記憶するテキストバッファと、前記テキスト中の接尾の出現位置を記憶する整数配列を格納する第１の記憶装置と、前記テキスト中の各文字の頻度を記憶する文字頻度表を格納する第２の記憶装置と、前記整数配列のサイズと前記文字頻度表に記憶されている頻度とに基づいて前記テキスト中の各文字の範囲を定める範囲決定手段と、この定められた範囲内の文字を先頭文字とする前記テキスト中の前記接尾の出現位置を前記整数配列に格納する初期化手段と、この初期化手段による処理後の整数配列上の前記接尾の出現位置を、該接尾を構成する文字の数に基づいてソートするソート手段と、このソート後の整数配列上の前記接尾の出現位置を第３の記憶装置に記憶する記憶手段と、前記範囲決定手段、前記初期化手段、前記ソート手段および前記記憶手段による処理を、前記テキスト中のすべての範囲について処理が完了するまで繰り返えさせて、前記テキストの接尾配列を複数に分割して求めて前記第３の記憶装置に順次記憶する制御手段と、を備えている索引作成装置である。
【００２１】
したがって、マージを必要とすることなく、接尾配列を数回に分けて作成できるので、重複文書を含むテキストに対しても、接尾配列の作成を高速に処理できる。また、接尾配列を複数に分割して求めるので、処理の実行に必要な記憶容量はコンパクトである。
【００２６】
請求項２に記載の発明は、予め記憶されているテキスト中の各文字の範囲を定める処理を、予め格納されていて前記テキスト中の接尾の出現位置を記憶する整数配列のサイズと、予め格納されていて前記テキスト中の各文字の頻度を記憶する文字頻度表に記憶されている頻度とに基づいて範囲決定手段が行う範囲決定工程と、この定められた範囲内の文字を先頭文字とする前記テキスト中の前記接尾の出現位置を前記整数配列に格納する処理を初期化手段が行う初期化工程と、この初期化工程による処理後の整数配列上の前記接尾の出現位置を、該接尾を構成する文字の数に基づいてソート手段がソートするソート工程と、このソート後の整数配列上の前記接尾の出現位置を所定の記憶装置に記憶する処理を記憶手段が行う記憶工程と、の各工程からなる処理を、前記テキスト中のすべての範囲について処理が完了するまで制御手段が繰り返して、前記テキストの接尾配列を複数に分割して求めて前記所定の記憶装置に順次記憶する索引作成方法である。
【００２７】
したがって、マージを必要とすることなく、接尾配列を数回に分けて作成できるので、重複文書を含むテキストに対しても、接尾配列の作成を高速に処理できる。また、接尾配列を複数に分割して求めるので、処理の実行に必要な記憶容量はコンパクトである。
【００３２】
請求項３に記載の発明は、予め記憶さているテキスト中の各文字の範囲を定める処理を、予めに格納されていて前記テキスト中の接尾の出現位置を記憶する整数配列のサイズと、予め格納されていて前記テキスト中の各文字の頻度を記憶する文字頻度表に記憶されている頻度とに基づいて行う範囲決定工程と、この定められた範囲内の文字を先頭文字とする前記テキスト中の前記接尾の出現位置を前記整数配列に格納する初期化工程と、この初期化工程による処理後の整数配列上の前記接尾の出現位置を、該接尾を構成する文字の数に基づいてソートするソート工程と、このソート後の整数配列上の前記接尾の出現位置を所定の記憶装置に記憶する記憶工程と、の各工程からなる処理を、前記テキスト中のすべての範囲について処理が完了するまで繰り返して、前記テキストの接尾配列を複数に分割して求めて前記所定の記憶装置に順次記憶することをコンピュータに実行させるプログラムを記憶しているコンピュータに読み取り可能な記憶媒体である。
【００３３】
したがって、マージを必要とすることなく、接尾配列を数回に分けて作成できるので、重複文書を含むテキストに対しても、接尾配列の作成を高速に処理できる。また、接尾配列を複数に分割して求めるので、処理の実行に必要な記憶容量はコンパクトである。
【００３６】
【発明の実施の形態】
［発明の実施の形態１］
この発明の一実施の形態を発明の実施の形態１として説明する。
【００３７】
図１は、この発明の実施の形態１である文字列照合装置の電気的な接続を示すブロック図である。この文字列照合装置１は、この発明の索引作成装置および文字列照合装置を実施するもので、発明の各種の演算を行い、文字列照合装置１の各部を集中的に制御するＣＰＵ２と、ＢＩＯＳなどを記憶した読出し専用メモリであるＲＯＭ３と、各種データを書換え可能に記憶し、ＣＰＵ２の作業エリアとなるＲＡＭ４とがバス５で接続されている。さらにバス５には、外部記憶となるハードディスク６と、ＣＤ（Compact Disc）７を読み取るＣＤドライブ８と、文字列照合装置１とネットワーク９との通信を司る通信制御装置１０と、キーボード、マウスなどの入力装置１１と、ＣＲＴ、ＬＣＤなどの出力装置１２とが、図示しないＩ／Ｏを介して接続されている。
【００３８】
ＣＤ７は、所定のプログラムが記憶されている。ＣＰＵ２は、ＣＤ７に記憶されているプログラムをＣＤドライブ８で読み取り、ハードディスク６にインストールする。これにより、文字列照合装置１は、以下に説明するような各種の処理を行うことが可能な状態となる。
【００３９】
なお、記憶媒体としては、ＣＤのみならず、ＤＶＤなどの各種の光ディスク、各種光磁気ディスク、フロッピーディスクなどの各種磁気ディスク等、各種方式のメディアを用いることができる。また、通信制御装置１０を介してインターネットなどのネットワーク９から前記プログラムをダウンロードし、ハードディスク６にインストールするようにしてもよい。この場合に、送信側のサーバで前記プログラムを記憶している記憶装置も、この発明の記憶媒体である。なお、前記プログラムは、所定のＯＳ上で動作するものであってもよいし、その場合に後述の各種処理の一部の実行をＯＳに肩代わりさせるものであってもよいし、ワープロソフトなど所定のアプリケーションソフトやＯＳなどを構成する一群のプログラムファイルの一部として含まれているものであってもよい。
【００４０】
次に、文字列照合装置１が行う各種処理の内容について説明する。
【００４１】
まず、接尾配列の構成手法を、接尾配列の作成の対象となるテキストＴが“ＢＡＮＡＮＡ”である場合を例にして、図２の説明図、および、図３、図４のフローチャートを参照して説明する。
【００４２】
すなわち、図２（ａ）に示すように、入力装置１１で入力され、または、ハードディスク６などの外部記憶から呼び出されるなどして与えられたテキストＴ中の各文字には、１以上の文字値が予め定義されており（この例では、Ａ，Ｂ，Ｃ、…の各文字値が、１，２，３，…）、テキストＴの末尾に０を文字値とする仮想的な文字＄を付加して、ＲＡＭ４内に構築した（図１参照）テキストバッファ１３に格納する（ステップＳ１）。図２（ａ）中でテキストＴの上に記されている数字（０〜６）は、テキストＴの配列の添え字であり０起算とする。この添え字は、テキストＴ中の接尾の出現位置（ポインタ）を表す。例えば，接尾“ＡＮＡＮＡ＄”の出現位置（ポインタ）は１である。
【００４３】
図２（ｂ）に示すＢ１、Ｂ２は、後述するバケットソートに用いるバケット表である。図２（ｃ）〜（ｆ）に示すＡは、テキストＴ中の接尾の出現位置（テキストＴの配列の添え字）または辞書順位を記憶する整数配列である。ここで、バケットとは整数配列Ａ上の部分配列であり、各バケット中には先頭文字が同じ接尾の出現位置が格納される。バケット表にはバケットのサイズＢ１とバケットの整数配列Ａ上での開始位置Ｂ２とが格納される。バケット表Ｂ１、Ｂ２、整数配列Ａは、何れもＲＡＭ４内に用意される（図１参照）。これにより記憶装置、第１、第２の記憶装置を実現している。
【００４４】
バケット表Ｂ１，Ｂ２中の値は、次のようにセットされる。テキストバッファ１３に格納されているテキストＴを走査し、テキストＴ中の各文字の出現頻度をカウントし、バケット表のＢ１に、そのカウント値をセットする（ステップＳ２）。すなわち、バケット表のＢ１は、文字値の小さい順に、この例では、＄，Ａ，Ｂ，…，Ｎ，…の文字順にテキストＴ中の各文字の出現頻度が格納される。
【００４５】
次に、文字値が小さい順にバケット表のＢ１の値を累計し、この累計した値をバケット表のＢ２にセットしてゆく。具体的には、累計値Ｎ、文字値Ｃの初期値を何れも０として（Ｎ＝０、Ｃ＝０）（ステップＳ３）、ステップＳ４〜Ｓ７の処理を開始する。すなわち、文字値がＣである文字のバケット表についてＢ１の値（Ｂ１［Ｃ］）を見て、その値が０より大きいか（Ｂ１［Ｃ］＞０）否かを判断する処理を始める（ステップＳ４）。Ｂ１［Ｃ］＞０というのは（ステップＳ４のＹ）、その文字値Ｃの文字がテキストＴに含まれているということである。この場合は、前回の累計値Ｎ（文字値Ｃが初期値０のときは、前回の累計値Ｎも初期値０）に今回の文字値Ｃを加算し（Ｎ＝Ｎ＋Ｃ）、この加算後の累計値Ｎをバケット表のＢ２の値とする（Ｂ２［Ｃ］＝Ｎ）（ステップＳ５）。そして、文字値Ｃの値を＋１だけインクリメントする（Ｃ＝Ｃ＋１）（ステップＳ６）。Ｂ１［Ｃ］＝０の場合（ステップＳ４のＮ）、すなわち、文字値Ｃの文字がテキストＴに含まれていないときも、文字値Ｃの値を＋１だけインクリメントする（ステップＳ６）。このステップＳ４〜Ｓ６の処理を、文字値Ｃが文字値Ｃの採り得る最大値を超えるまで繰り返し（ステップＳ７のＮ）、超えたときは（ステップＳ７のＹ）、ステップＳ８に進む。
【００４６】
ステップＳ４〜Ｓ７の処理の結果、バケット表Ｂ１，Ｂ２は、以下の表３のとおりになる。
【００４７】
【表３】
0004181723.tif 000004
【００４８】
次に、再度テキストＴを走査し、テキストＴの文字毎にその出現位置（テキストＴの配列の添え字）を整数配列Ａにセットする。セットする位置はその文字に対するバケット表のＢ２の値（Ｂ２［Ｃ］）を参照し、“Ｂ２［Ｃ］−１”によって得る。そしてＢ２［Ｃ］の値を“Ｂ２［Ｃ］−１”に更新する。例えば、テキストＴの最初の文字“Ｂ”の出現位置０は、“Ｂ”に対するバケット表のＢ２の値“５”を参照し、“５−１＝４”により、整数配列Ａの添え字“４”の場所に格納する（整数配列Ａの各欄も、０，１，３，…の添え字が付されている）。その際、Ｂ２の値を“５”から“４”に更新する。この処理をテキストＴの最後まで行うことで、図２に示したようにバケット表の値がセットされる。ただし図２（ｂ）においてバケット表のＢ２は、その値に対応する整数配列Ａの添え字への矢印で表現している。
【００４９】
具体的には、テキストＴの添え字（出現位置）Ｉの初期値を０とする（Ｉ＝０）（ステップＳ８）。そして、テキストＴの添え字Ｉの文字の文字値Ｃ（＝Ｔ［Ｉ］）を求め、その文字値Ｃの文字のバケット表のＢ２の値Ｂ２［Ｃ］を参照し、“Ｂ２［Ｃ］−１”を求める（Ｂ２［Ｃ］＝Ｂ２［Ｃ］−１）。そして、このように１だけ減算したＢ２［Ｃ］の値が添え字である整数配列Ａの欄に、その文字値Ｃを格納する（Ａ［Ｂ２［Ｃ］］＝Ｃ）（ステップＳ９）。このステップＳ９の処理を、Ｍが１になるまで繰り返し、すなわち、テキストＴのすべての文字について行い（ステップＳ１０のＮ）、Ｍが１になったときは、ステップＳ１１にすすむ。ステップＳ２〜Ｓ１０の処理により、初期化手段、初期化工程が実現される。
【００５０】
次に、文字値が大きい順に（つまり図２で右から左に）バケット表を参照し、各バケットのサイズＢ１と開始位置Ｂ２を取り出す。そして、そのバケット内に格納されているポインタ（テキストＴの配列の添え字）をソートする。図２の例では、最初に文字“Ｎ”に対するバケット（サイズ２、開始位置５）中のポインタ（２と４）がソートの対象になる。具体的には、文字値Ｃの初期値を文字値の最大値に設定し（ステップＳ１１）、文字値がＣであるバケット表のＢ１の値Ｂ１［Ｃ］が０より大きい場合（ステップＳ１２のＹ）、すなわち、テキストＴ中に存在する文字については、バケット毎にポインタをソートして（ステップＳ１３）、バケット表のＢ１の値Ｂ１［Ｃ］が０である場合（ステップＳ１２のＮ）、すなわち、テキストＴ中に存在しない文字については、ステップＳ１３の処理を行わずに、文字値Ｃを−１だけデクリメントする（Ｃ＝Ｃ−１）（ステップＳ１４）。このステップＳ１２〜Ｓ１４の処理はＣがマイナスの値になるまで繰り返し（ステップＳ１５のＹ）、Ｃがマイナスの値になったときは（ステップＳ１５のＮ）、ステップＳ１６にすすむ。
【００５１】
ソートの対象となるポインタは、ステップＳ１３で次のようにしてソートする。すなわち、ポインタに対応する接尾を構成する文字を先頭から順に比較する。この比較には、その構成文字に対するバケット表中のＢ２の値を用いる（Ｂ２の値はこの時点では、その構成文字を先頭文字とする接尾に対する最小の辞書順位と等しい）。前記の文字“Ｎ”の例では、ポインタと接尾の関係は、以下の表４のようになる。
【００５２】
【表４】
0004181723.tif 000005
【００５３】
この例では、各接尾の先頭文字（ＮとＮ）に関するＢ２の値、すなわち、“５”を取りだして比較することとなる。するとこれは同一の“５”なので、次の文字（ＡとＡ）に関するＢ２の値１を取りだして同様に比較する。するとこれも同一なので、その次の文字（Ｎと＄）のＢ２の値５と０を得て、５＞０より、ポインタ２と４の順序は、
４  ＜  ２
となり、整数配列Ａの添え字の大きい順に、Ａ[６]＝２、Ａ[５]＝４のように、ポインタ２と４のソート後における整数配列Ａ上の位置が確定する（図２（ｃ））。
【００５４】
このようにステップＳ１３のソートによってポインタＰの整数配列Ａ上の位置が整数配列Ａの添え字Ｒの位置に確定する度に、Ｐの値をＡ[Ｒ]に格納し、その後、Ａ[Ｐ]の位置に−Ｒを格納する。図２の例では、ステップＳ１３のソートにより、Ａ[５]＝４のようにポインタ４の整数配列Ａ上の位置５が確定したので、Ａ[５]にＡ[４]の値０を格納し、Ａ[４]に−５を格納する。
【００５５】
ここで整数配列Ａの添え字ＲはポインタＰに対する接尾の辞書順位に相当している。Ａ[６]＝２についても同様に辞書順位を格納すると、Ａ[６]にＡ［２］の値３を格納し、Ａ［２］に−６を格納することとなり、整数配列Ａは、図２（ｃ）から図２（ｄ）の状態に変化する。
【００５６】
この段階で、整数配列Ａには辞書順位とポインタとが混在することになるため、両者を負の値か負でない値（正または０）かにより区別して格納する。即ち、負ならば辞書順位であり、そうでなければポインタとする。
【００５７】
このようにして、ステップＳ１３において、文字“Ｎ”に関するバケットの処理を終わり、文字“Ｂ”に関するバケット中のポインタをソート対象とする。この場合、バケット表Ｂ１にあるように、バケットのサイズは“１”であるので、ソートは既に完了している。このバケットの開始位置は、整数配列Ａの添え字４の位置であり、Ａ[４]に格納されたポインタ０は、前記の処理によりＡ[５]に移動されている。このことは、Ａ[４]の値が−５であることからわかる。よってＡ[５]の値０を取り出し、Ａ[４]＝０のようにソート後のポインタ０の位置が確定することがわかる。そして同様に、Ａ[４]にＡ[０]の値６を格納し、Ａ[０]に−４を格納するわけだが、Ａ[４]には辞書順位−５が既に格納されているため、Ａ[４]ではなくＡ[５]に値６を格納する。こうして、図２（ｅ）に示すような整数配列Ａが得られる。
【００５８】
次に、文字“Ａ”のバケットをソートの対象とする。そのサイズはバケット表Ｂ１から３であり、整数配列Ａ上の開始位置はバケット表Ｂ２から１である。Ａ[１]、Ａ[２]、Ａ[３]の値は１，−６，５であり、辞書順位６からポインタ３（Ａ[６]を参照して）を得る。よってソート対象とするポインタは、１，３，５であることがわかる。対応する接尾は以下の表５のようになる。
【００５９】
【表５】
0004181723.tif 000006
【００６０】
ステップＳ１３のソートにおいて、先頭文字“Ａ”のバケット表Ｂ２の値１は全て同一なので、次の文字Ｎ，Ｎ，＄を比較する。この場合、“Ｎ”は“＄”と異なり、先頭文字“Ａ”より大きいので、“Ｎ”を先頭とする接尾の辞書順位は確定している。そこで、それら辞書順位を、
Ａ[１＋１]＝Ａ[２]＝−６    →  辞書順位は６
Ａ[３＋１]＝Ａ[４]＝−５    →  辞書順位は５
により得る。一方、文字“＄”については、バケット表Ｂ２の値０を得る。Ｂ２の値はその文字を先頭とする接尾の最小の辞書順位と見なすこともできる。
【００６１】
以上、ポインタ１，３，５に対して、辞書順位６，５，０を得て、それらを比較することで、
５  ＜  ３  ＜  １
のようにポインタがソートされ、Ａ[１]＝５、Ａ[２]＝３、Ａ[３]＝１のように確定する。その後、前記と同様、辞書順位を負数で表す処理を行う。
【００６２】
以上のようにして、最終的には図２（ｆ）に表す整数配列Ａを得る。図２（ｆ）に示すように、最終的には整数配列Ａの要素は全て負数で表された接尾の辞書順位となる。ステップＳ１１〜Ｓ１５の処理により、ソート手段、ソート工程が実現される。
【００６３】
以上のようにしてステップＳ１３の処理をすべて行った後、整数配列Ａの辞書順位をポインタ値に変換する（ステップＳ１６）。すなわち、まず、整数配列Ａの値を順に取り出す。例えば図２（ｆ）で左から右へ（添え字の若い順に）取り出す場合、最初はＡ［０］＝−４を得る。そこで、Ａ［４］の値である−５を取り出した後、Ａ［４］に０を格納する。次にＡ［５］の値−１を取り出した後、Ａ［５］に４を格納する。次に、Ａ［１］の値−３を取り出した後、Ａ［１］に５を格納する。このように変換する過程で格納先の値が負数でない場合が生じたときは、整数配列Ａ中で未だ負数のものを見つけて変換処理を続行する。整数配列Ａ中に負数が１つもなくなった時点で、この変換処理は終了する。最終的に整数配列Ａの各値は、左から順に、“  ６  ５  ３  １  ０  ４  ２  ”となり、先頭の６を除いた部分が、テキストＴの辞書である接尾配列になる。ステップＳ１６により、変換手段、変換工程が実現される。
【００６４】
このようにして求められた接尾配列をテキストＴの辞書として用い、文字列照合は次のように行われる。すなわち、入力装置１１で入力されるなどして与えられた、テキストＴ中での文字列照合を行うための文字列Ｐは、ＲＡＭ４の所定の領域に記憶され（これにより第４の記憶装置を実現している）、整数配列Ａに記憶されている接尾配列を辞書として参照し、テキストＴ中の文字列Ｐの出現位置が２分探索によって求められる。その処理の詳細については、周知の技術であるので説明を省略する。これにより、文字列照合手段、文字列照合工程を実現している。
【００６５】
以上説明した文字列照合装置１によれば、ポインタをソートする際に、辞書順位をキーとするため（ステップＳ１３）、重複文書を含むテキストに対しても、計算時間が急激に増大することがない（つまりロバストである）。
【００６６】
なぜなら、例えば、前記のように末尾に＄を付した後のテキストＴが“ＢＡＮＡＮＡ＋ＢＡＮＡＮＡ＄”である場合、従来の技術においては、次の表４に示すように、“ＢＡＮＡＮＡ”の６文字を比較して後、次の７文字目“＋”と“＄”の違いにより、はじめてポインタ０と７に対応する接尾の辞書順位が決定されるが、この発明の実施の形態１の文字列照合装置１によれば、文字“Ｂ”より辞書順位が大きい文字“Ｎ”を先頭とする接尾の辞書順位が、以下の表５のように先に決定される。よって、表６に示すポインタ０，７のソートでは、その各ポインタに対応した接尾の３文字目の“Ｎ”を先頭とする接尾の辞書順位を参照することで、両者の大小関係が決定されるからである。
【００６７】
【表６】
0004181723.tif 000007
【００６８】
【表７】
0004181723.tif 000008
【００６９】
つまり、辞書順位をキーとすることで、ソート（ステップＳ１３）の過程における接尾間の辞書順位の比較が従来技術に比べて早期に完了するため、計算時間が急激に増大することがないのである。
【００７０】
さらに、接尾の辞書順位と出現位置（ポインタ）とを整数配列Ａ上に混在させて記憶し、最後に全て出現位置に変換するので、対象となるテキストがＮ文字からなる場合に、必要記憶装置は５Ｎバイトとなり（各文字を１バイト、各ポインタを４バイトで一律に記憶する場合）、処理の実行に必要な記憶容量がコンパクトである。つまり、記憶容量のコンパクト性を犠牲にすることなく、ロバストな接尾配列の構成が可能となる。
【００７１】
［発明の実施の形態２］
別の発明の実施の形態を発明の実施の形態２として説明する。
【００７２】
図５は、この発明の実施の形態２である文字列照合装置の電気的な接続を示すブロック図である。図６は、この文字照合装置が行う処理を説明するフローチャートである。以下の説明において、図１〜図４と同一符号の回路要素などは発明の実施の形態１と同様であるため、詳細な説明は省略する。
【００７３】
この発明の実施の形態２である文字列照合装置１は、この発明の索引作成装置および文字列照合装置を実施するもので、この文字列照合装置１が発明の実施の形態１と相違するのは、図２〜図４を参照して説明した処理に代えて、以下のような処理を行う点である。かかる処理の内容について、テキストＴが“ＢＡＮＡＮＡ”の場合を例に説明する。
【００７４】
図４に示すように、入力装置１１で入力され、または、ハードディスク６などの外部記憶から呼び出されるなどして与えられたテキストＴを、ＲＡＭ４内に構築した（図５参照）テキストバッファ１３に格納する（ステップＳ２１）。表８に示すように、テキストＴの各文字には、０起算とする添え字０〜５が付されており、この添え字はテキストＴ中の接尾の出現位置（ポインタ）を表す。
【００７５】
【表８】
0004181723.tif 000009
【００７６】
次に、テキストバッファ１３内のテキストＴを走査し、テキストＴ中の各文字の頻度をカウントし、ＲＡＭ４内に構築した文字頻度表１４（これにより第２の記憶装置を実現している）に格納する（ステップＳ２２）。文字頻度表１４は表９に示すように各文字の辞書順にその頻度を格納するものとする。
【００７７】
【表９】
0004181723.tif 000010
【００７８】
この後、ステップＳ２３〜Ｓ２６において、テキストＴ中の接尾に対するポインタを数回に分けてソートする。
【００７９】
まず、テキストＴ中の接尾の出現位置（ポインタ）を記憶するためにＲＡＭ４に構築された整数配列Ａ（これにより第１の記憶手段を実現している）のサイズＮに対して、文字頻度表１４の頻度を、順に累計する。この累計はサイズＮを超える直前で中止する。例えば、Ｎ＝３の場合、文字頻度表１４（表９）の最初の文字“Ａ”の文字頻度３を得て、その累計は３となる。次の文字“Ｂ”の頻度１を得て、累計は、３＋１＝４となるが、これはサイズＮを超えるので、ここで中断する。そこで、文字“Ａ”から文字“Ａ”までの範囲をソートの対象とする（ステップＳ２３）。ステップＳ２３により範囲決定手段、範囲決定工程を実現している。
【００８０】
次に、テキストバッファ１３中のテキストＴを走査し、文字“Ａ”から文字“Ａ”までの範囲の文字（つまりこの場合、文字“Ａ”）を先頭とする接尾の出現位置（ポインタ）を整数配列Ａに格納する（ステップＳ２４）。ステップＳ２４により初期化手段、初期化工程を実現している。この場合、表１０のようにポインタがセットされる。
【００８１】
【表１０】
0004181723.tif 000011
【００８２】
次に、整数配列Ａ中のポインタを、それに対応する接尾を文字列キーと見なして、文字列ソートアルゴリズムによりソートする（ステップＳ２５）。ステップＳ２５によりソート手段、ソート工程を実現している。すなわち、ポインタと接尾の対応が表１１のとおりであるとすると、表１２のように整数配列Ａ上にポインタがソートされる。
【００８３】
【表１１】
0004181723.tif 000012
【００８４】
【表１２】
0004181723.tif 000013
【００８５】
次に、このポインタ列を外部記憶であるハードディスク６（第３の記憶装置、所定の記憶装置）上の所定のファイルに記憶する（ステップＳ２６）。ステップＳ２６により記憶手段、記憶工程を実現している。
【００８６】
ステップＳ２３〜Ｓ２６の処理は、テキストＴ中の接尾に対するポインタのソートがすべての範囲について済むまで繰り返す（ステップＳ２７のＮ）。この場合、辞書順で、未だソートが済んでいない文字から文字頻度の累計を開始する。すなわち、文字“Ｂ”から開始し、最後の文字“Ｎ”まで累計が３となり、整数配列ＡのサイズＮを超えないので、文字“Ｂ”から文字“Ｎ”までをソートの対象とする文字範囲とする（ステップＳ２３）。
【００８７】
そして、ステップＳ２４では、同様にテキストＴ中の文字“Ｂ”から“Ｎ”までの範囲の文字を先頭文字とする接尾のポインタ０、２、４を整数配列Ａの先頭から順に格納する。ステップＳ２５では、整数配列Ａに格納されたポインタをソートし、ステップＳ２６では、ソート済みのポインタ“０，４，２”を、外部記憶であるハードディスク６に追加出力する。この結果、ハードディスク６上に、“５、３、１、０、４、２”というポインタ列（接尾配列）を得る。このステップＳ２３〜Ｓ２６の処理の繰り返しにより制御手段、制御工程を実現している。全ての範囲がソート済みとなったところで（ステップＳ２７のＹ）、処理は終了する。
【００８８】
このようにして求められた接尾配列をテキストＴの辞書として用い、文字列照合は次のように行われる。すなわち、入力装置１１で入力されるなどして与えられた、テキストＴ中での文字列照合を行うための文字列Ｐは、ＲＡＭ４の所定の領域に記憶され（これにより第４の記憶装置を実現している）、ハードディスク６に記憶されている接尾配列をＲＡＭ４の所定の領域に読み込んで、この接尾配列を辞書として参照し、テキストＴ中の文字列Ｐの出現位置が２分探索によって求められる。その処理の詳細については、周知の技術であるので説明を省略する。これにより、文字列照合手段、文字列照合工程を実現している。
【００８９】
以上説明した文字列照合装置１によれば、従来の技術のようにマージを必要とすることなく、接尾配列を数回に分けて作成できるので、外部記憶の読み込み、書き込み処理を少なくして、接尾配列の作成を高速に処理できる。つまり、処理の高速性を犠牲にすることなく、非常にコンパクト（必要記憶量がテキスト容量に近い）に接尾配列の構成が可能になる。
【００９０】
【発明の効果】
請求項１に記載の発明は、マージを必要とすることなく、接尾配列を数回に分けて作成できるので、重複文書を含むテキストに対しても、接尾配列の作成を高速に処理できる。また、接尾配列を複数に分割して求めるので、処理の実行に必要な記憶容量はコンパクトである。
【００９４】
請求項２に記載の発明は、マージを必要とすることなく、接尾配列を数回に分けて作成できるので、重複文書を含むテキストに対しても、接尾配列の作成を高速に処理できる。また、接尾配列を複数に分割して求めるので、処理の実行に必要な記憶容量はコンパクトである。
【００９７】
請求項３に記載の発明は、マージを必要とすることなく、接尾配列を数回に分けて作成できるので、重複文書を含むテキストに対しても、接尾配列の作成を高速に処理できる。また、接尾配列を複数に分割して求めるので、処理の実行に必要な記憶容量はコンパクトである。
【図面の簡単な説明】
【図１】この発明の実施の形態１である文字列照合装置の電気的な接続を示すブロック図である。
【図２】前記文字列照合装置の処理を説明する説明図である。
【図３】前記文字列照合装置の処理を説明するフローチャートである。
【図４】前記文字列照合装置の処理を説明するフローチャートである。
【図５】この発明の実施の形態２である文字列照合装置の電気的な接続を示すブロック図である。
【図６】前記文字列照合装置の処理を説明するフローチャートである。
【符号の説明】
１      索引作成装置、文字列照合装置
４      記憶装置、第１の記憶装置、第２の記憶装置
６      所定の記憶装置、第３の記憶装置
７      記憶媒体
１３    テキストバッファ
１４    文字頻度表
Ａ      整数配列
Ｂ１    バケット表
Ｂ２    バケット表
【図１】
0004181723.tif 000014
【図２】
0004181723.tif 000015
【図３】
0004181723.tif 000016
【図４】
0004181723.tif 000017
【図５】
0004181723.tif 000018
【図６】
0004181723.tif 000019