(57)【要約】任意のコード列の検索を行うことができ、従来よりも短時間で作成することのできる索引のデータ構造を求め、それを用いたコード列検索手法を提供するために、コード毎にそのコードＩＤの範囲を格納したコード別ＩＤ範囲表と各コードＩＤの次に位置するコードＩＤである次コードＩＤを格納したＩＤ関係表を作成し、検索対象コード列のコード別ＩＤ範囲表から検索コード列を構成するコードのコードＩＤの範囲を読み出し、読み出された検索コード列の先頭のコードのコードＩＤ範囲に含まれるコードＩＤに対応して格納された次コードＩＤをＩＤ関係表から読み出すとともに、該次のコードに対応して格納された次コードＩＤを順次ＩＤ関係表から読み出し、ＩＤ関係表から読み出した次コードＩＤがコード別ＩＤ範囲読出表から読み出したコードＩＤの範囲に含まれるか照合する。
2010035366.tif 000002
【特許請求の範囲】
【請求項１】
検索対象である検索対象コード列を検索コード列により検索するコード列検索装置において、
前記検索対象コード列に位置する全ての各コードを一意に識別するコードＩＤの範囲であるコードＩＤ範囲を同一種別のコード毎に格納したコード別ＩＤ範囲表と、
前記コードＩＤに対応して、前記検索対象コード列において該コードＩＤに係るコードの次に位置するコードのコードＩＤである次コードＩＤを格納したＩＤ関係表と、
前記コード別ＩＤ範囲表と前記ＩＤ関係表を参照して前記検索コード列による検索を実行する検索実行部を備え、
前記検索実行部は、
前記検索コード列を読み出す検索コード列読出手段と、
前記検索コード列読出手段により読み出された検索コード列を構成する先頭のコードからコード毎に、該コードの種別のコードＩＤ範囲を前記コード別ＩＤ範囲表から順次読み出すコード別ＩＤ範囲読出手段と、
前記コード別ＩＤ範囲読出手段により読み出された前記検索コード列の先頭のコードの種別のコードＩＤ範囲に含まれるコードＩＤに対応して格納された前記次コードＩＤを前記ＩＤ関係表から読み出し、以後、読み出された次コードＩＤに対応して格納された次コードＩＤを順次前記ＩＤ関係表から読み出すＩＤ関係読出手段と、
前記ＩＤ関係読出手段により読み出された次コードＩＤが前記コード別ＩＤ範囲読出手段により読み出されたコードＩＤの範囲に含まれるか照合するコードＩＤ照合手段を備える
ことを特徴とするコード列検索装置。
【請求項２】
請求項１に記載のコード列検索装置において、
前記コードＩＤ照合手段は、前記ＩＤ関係読出手段により読み出された、前記検索コード列の先頭のコードである第１のコードの種別のコードＩＤ範囲に含まれるコードＩＤである先頭コードＩＤを第１コードＩＤとしたとき該第１コードＩＤに対応して格納された前記次コードＩＤが、前記検索対象コード列において前記第１のコードの次に位置するコードである第２のコードの種別のコードＩＤ範囲に含まれるか照合し、以後、前記第１のコードと第２のコードの前記検索コード列における位置が前記コード別ＩＤ範囲読出手段及びＩＤ関係読出手段の読出動作により更新されると、該位置の更新された第１のコードのコードＩＤに対応して格納された前記次コードＩＤが、該位置の更新された第２のコードの種別の前記コードＩＤ範囲に含まれるかを照合する、
ことを特徴とするコード列検索装置。
【請求項３】
請求項２に記載のコード列検索装置において、
前記ＩＤ関係表は、前記コードＩＤに対応して、前記検索対象コード列において該コードＩＤに係るコードの位置を示すコード位置を格納しており、
前記コードＩＤ照合手段は、前記ＩＤ関係読出手段により読み出された次コードＩＤが前記コード別ＩＤ範囲読出手段により読み出されたコードＩＤの範囲に含まれるかの照合が前記検索コード列の先頭のコードから末尾のコードについてまで成功すると、該先頭のコードのコードＩＤに対応して前記ＩＤ関係表に格納されたコード位置を検索結果コード位置として出力する、
ことを特徴とするコード列検索装置。
【請求項４】
請求項３に記載のコード列検索装置において、
前記ＩＤ関係表に前記コードＩＤに対応して格納された次コードＩＤとコード位置は、同一種別のコードのコードＩＤ毎に連続してコード位置順で格納されている、
ことを特徴とするコード列検索装置。
【請求項５】
請求項４に記載のコード列検索装置において、
前記コードＩＤ照合手段は、前記検索コード列の先頭のコードの種別のコードＩＤ範囲に含まれる全てのコードＩＤを前記先頭コードＩＤとして、前記ＩＤ関係読出手段により読み出された次コードＩＤが前記コード別ＩＤ範囲読出手段により読み出されたコードＩＤの範囲に含まれるかを照合する、
ことを特徴とするコード列検索装置。
【請求項６】
請求項５に記載のコード列検索装置において、
前記コードＩＤ照合手段は、前記ＩＤ関係読出手段により読み出された次コードＩＤが前記コード別ＩＤ範囲読出手段により読み出されたコードＩＤの範囲に含まれるかの照合が失敗すると、前記ＩＤ関係表の該次コードＩＤと同一のエントリに格納されたコード位置と、前記先頭のコードのコードＩＤに対応して前記ＩＤ関係表に格納されたコード位置とを、検索結果コード位置として出力する、
ことを特徴とするコード列検索装置。
【請求項７】
請求項５に記載のコード列検索装置において、
前記検索コード列は任意のコードと照合する任意コードを含み、
前記コードＩＤ照合手段は、該任意コードを第２のコードとした前記ＩＤ関係読出手段により読み出された次コードＩＤが前記コード別ＩＤ範囲読出手段により読み出されたコードＩＤの範囲に含まれるかの照合に替えて、前記検索コード列において該任意コードの次に位置するコードを前記第２のコードとして前記照合を行う、
ことを特徴とするコード列検索装置。
【請求項８】
検索対象である検索対象コード列を検索コード列により検索するコード列検索装置であって、前記検索対象コード列に位置する全ての各コードを一意に識別するコードＩＤの範囲であるコードＩＤ範囲を同一種別のコード毎に格納したコード別ＩＤ範囲表と、前記コードＩＤに対応して、前記検索対象コード列において該コードＩＤに係るコードの次に位置するコードのコードＩＤである次コードＩＤを格納したＩＤ関係表を備えたコード列検索装置によるコード列検索方法において、
前記検索コード列を読み出す検索コード列読出ステップと、
前記検索コード列読出ステップで読み出された検索コード列を構成する先頭のコードからコード毎に、該コードの種別のコードＩＤ範囲を前記コード別ＩＤ範囲表から順次読み出すコード別ＩＤ範囲読出ステップと、
前記コード別ＩＤ範囲読出ステップで読み出された前記検索コード列の先頭のコードの種別のコードＩＤ範囲に含まれるコードＩＤに対応して格納された前記次コードＩＤを前記ＩＤ関係表から読み出し、以後、読み出された次コードＩＤに対応して格納された次コードＩＤを順次前記ＩＤ関係表から読み出すＩＤ関係読出ステップと、
前記ＩＤ関係読出ステップで読み出された次コードＩＤが前記コード別ＩＤ範囲読出ステップで読み出されたコードＩＤの範囲に含まれるか照合するコードＩＤ照合ステップと、
を備えることを特徴とするコード列検索方法。
【請求項９】
請求項８に記載のコード列検索方法において、
前記コードＩＤ照合ステップは、
前記ＩＤ関係読出ステップで読み出された、前記検索コード列の先頭のコードである第１のコードの種別のコードＩＤ範囲に含まれるコードＩＤである先頭コードＩＤを第１コードＩＤとしたとき該第１コードＩＤに対応して格納された前記次コードＩＤが、前記検索対象コード列において前記第１のコードの次に位置するコードである第２のコードの種別のコードＩＤ範囲に含まれるか照合し、
以後、前記第１のコードと第２のコードの前記検索コード列における位置が前記コード別ＩＤ範囲読出ステップ及びＩＤ関係読出ステップの読出動作により更新されると、該位置の更新された第１のコードのコードＩＤに対応して格納された前記次コードＩＤが、該位置の更新された第２のコードの種別の前記コードＩＤ範囲に含まれるかを照合する、
ことを特徴とするコード列検索方法。
【請求項１０】
請求項９に記載のコード列検索方法において、
前記ＩＤ関係表は、前記コードＩＤに対応して、前記検索対象コード列において該コードＩＤに係るコードの位置を示すコード位置を格納しており、
前記コードＩＤ照合ステップは、前記ＩＤ関係読出ステップで読み出された次コードＩＤが前記コード別ＩＤ範囲読出ステップで読み出されたコードＩＤの範囲に含まれるかの照合が前記検索コード列の先頭のコードから末尾のコードについてまで成功すると、該先頭のコードのコードＩＤに対応して前記ＩＤ関係表に格納されたコード位置を検索結果コード位置として出力する、
ことを特徴とするコード列検索方法。
【請求項１１】
請求項１０に記載のコード列検索方法において、
前記コードＩＤ照合ステップは、前記検索コード列の先頭のコードの種別のコードＩＤ範囲に含まれる全てのコードＩＤを前記先頭コードＩＤとして、前記ＩＤ関係読出ステップで読み出された次コードＩＤが前記コード別ＩＤ範囲読出ステップで読み出されたコードＩＤの範囲に含まれるかを照合する、
ことを特徴とするコード列検索方法。
【請求項１２】
検索対象である検索対象コード列を検索コード列により検索するコード列検索装置であって、前記検索対象コード列に位置する全ての各コードを一意に識別するコードＩＤの範囲であるコードＩＤ範囲を同一種別のコード毎に格納したコード別ＩＤ範囲表と、前記コードＩＤに対応して、前記検索対象コード列において該コードＩＤに係るコードの次に位置するコードのコードＩＤである次コードＩＤを格納したＩＤ関係表を備えたコード列検索装置の機能をコンピュータに実現させるコード列検索プログラムにおいて、
コンピュータに、
前記検索コード列を読み出す検索コード列読出機能、
前記検索コード列読出機能により読み出された検索コード列を構成する先頭のコードからコード毎に、該コードの種別のコードＩＤ範囲を前記コード別ＩＤ範囲表から順次読み出すコード別ＩＤ範囲読出機能、
前記コード別ＩＤ範囲読出機能により読み出された前記検索コード列の先頭のコードの種別のコードＩＤ範囲に含まれるコードＩＤに対応して格納された前記次コードＩＤを前記ＩＤ関係表から読み出し、以後、読み出された次コードＩＤに対応して格納された次コードＩＤを順次前記ＩＤ関係表から読み出すＩＤ関係読出機能、
前記ＩＤ関係読出機能により読み出された次コードＩＤが前記コード別ＩＤ範囲読出機能により読み出されたコードＩＤの範囲に含まれるか照合するコードＩＤ照合機能、
を実現させることを特徴とするコード列検索プログラム。
【請求項１３】
請求項１２に記載のコード列検索プログラムにおいて、
前記コードＩＤ照合機能は、
前記ＩＤ関係読出機能により読み出された、前記検索コード列の先頭のコードである第１のコードの種別のコードＩＤ範囲に含まれるコードＩＤである先頭コードＩＤを第１コードＩＤとしたとき該第１コードＩＤに対応して格納された前記次コードＩＤが、前記検索対象コード列において前記第１のコードの次に位置するコードである第２のコードの種別のコードＩＤ範囲に含まれるか照合する機能と、
以後、前記第１のコードと第２のコードの前記検索コード列における位置が前記コード別ＩＤ範囲読出機能及びＩＤ関係読出機能の読出動作により更新されると、該位置の更新された第１のコードのコードＩＤに対応して格納された前記次コードＩＤが、該位置の更新された第２のコードの種別の前記コードＩＤ範囲に含まれるかを照合する機能を含む、
ことを特徴とするコード列検索プログラム。
【請求項１４】
請求項１３に記載のコード列検索プログラムにおいて、
前記ＩＤ関係表は、前記コードＩＤに対応して、前記検索対象コード列において該コードＩＤに係るコードの位置を示すコード位置を格納しており、
前記コードＩＤ照合機能は、前記ＩＤ関係読出機能により読み出された次コードＩＤが前記コード別ＩＤ範囲読出機能により読み出されたコードＩＤの範囲に含まれるかの照合が前記検索コード列の先頭のコードから末尾のコードについてまで成功すると、該先頭のコードのコードＩＤに対応して前記ＩＤ関係表に格納されたコード位置を検索結果コード位置として出力する機能を含む、
ことを特徴とするコード列検索プログラム。
【請求項１５】
請求項１４に記載のコード列検索プログラムにおいて、
前記コードＩＤ照合機能は、前記検索コード列の先頭のコードの種別のコードＩＤ範囲に含まれる全てのコードＩＤを前記先頭コードＩＤとして、前記ＩＤ関係読出機能により読み出された次コードＩＤが前記コード別ＩＤ範囲読出機能により読み出されたコードＩＤの範囲に含まれるかを照合する機能を含む、
ことを特徴とするコード列検索プログラム。
【請求項１６】
請求項１２〜請求項１５のいずれか１項に記載のコード列検索プログラムを記録したコンピュータ読み取り可能な記録媒体。
【請求項１７】
検索対象である検索対象コード列を検索コード列により検索するコード列検索のためのデータ構造において、
前記検索対象コード列に位置する全ての各コードを一意に識別するコードＩＤの範囲であるコードＩＤ範囲を同一種別のコード毎に格納したコード別ＩＤ範囲表と、
前記コードＩＤに対応して、前記検索対象コード列において該コードＩＤに係るコードの次に位置するコードのコードＩＤである次コードＩＤを格納したＩＤ関係表と
を備え、
前記検索コード列を構成する先頭のコードからコード毎に、該コードの種別のコードＩＤ範囲を前記コード別ＩＤ範囲表から順次読み出し、
前記コード別ＩＤ範囲表から読み出された前記検索コード列の先頭のコードの種別のコードＩＤ範囲に含まれるコードＩＤに対応して格納された前記次コードＩＤを前記ＩＤ関係表から読み出し、以後、読み出された次コードＩＤに対応して格納された次コードＩＤを順次前記ＩＤ関係表から読み出し、
前記ＩＤ関係表から読み出された次コードＩＤが前記コード別ＩＤ範囲読出表から読み出されたコードＩＤの範囲に含まれるか照合することにより、
前記検索対象コード列を前記検索コード列による検索の実行を可能とする
ことを特徴とするコード列検索のためのデータ構造。
【請求項１８】
請求項１７に記載のコード列検索のためのデータ構造において、
前記ＩＤ関係表は、前記コードＩＤに対応して、前記検索対象コード列において該コードＩＤに係るコードの位置を示すコード位置を格納しており、
前記ＩＤ関係表から読み出された次コードＩＤが前記コード別ＩＤ範囲読出表から読み出されたコードＩＤの範囲に含まれるかの照合が前記検索コード列の先頭のコードから末尾のコードについてまで成功すると、該先頭のコードのコードＩＤに対応して前記ＩＤ関係表に格納されたコード位置を検索結果コード位置として出力することを可能とする、
ことを特徴とするコード列検索のためのデータ構造。
【請求項１９】
請求項１８に記載のコード列検索のためのデータ構造において、
前記ＩＤ関係表に前記コードＩＤに対応して格納された次コードＩＤとコード位置は、同一種別のコードのコードＩＤ毎に連続してコード位置順で格納されている、
ことを特徴とするコード列検索のためのデータ構造。
【請求項２０】
請求項１７〜請求項１９のいずれか１項に記載されたデータ構造を有するデータが記録されたコンピュータ読み取り可能な記録媒体。
【請求項２１】
検索対象である検索対象コード列を検索コード列により検索するコード列検索のための索引データ作成装置において、
前記検索対象コード列を読み出し、該読み出した検索対象コード列のコードの種別毎の出現回数を求める検索対象コード列読出手段と
前記検索対象コード列読出手段が求めたコードの種別毎の出現回数に基づいて、前記検索対象コード列に位置する全ての各コードを一意に識別するコードＩＤの範囲であるコードＩＤ範囲を同一種別のコード毎に格納したコード別ＩＤ範囲表を生成するコード別ＩＤ範囲表生成手段と、
前記検索対象コード列読出手段が読み出した検索対象コード列と前記コード別ＩＤ範囲表に基づき、前記コードＩＤに対応して、前記検索対象コード列において該コードＩＤに係るコードの次に位置するコードのコードＩＤである次コードＩＤを格納したＩＤ関係表を生成するＩＤ関係表生成手段と、
を備えたことを特徴とする索引データ作成装置。
【請求項２２】
請求項２１に記載の索引データ作成装置において、
前記ＩＤ関係表に前記コードＩＤに対応して格納された次コードＩＤとコード位置は、同一種別のコードのコードＩＤ毎に連続してコード位置順で格納されている、
ことを特徴とする索引データ作成装置。
【請求項２３】
検索対象である検索対象コード列を検索コード列により検索するコード列検索のための索引データ作成装置による索引データ作成方法において、
前記検索対象コード列を読み出し、該読み出した検索対象コード列のコードの種別毎の出現回数を求める検索対象コード列読出ステップと
前記検索対象コード列読出ステップで求めたコードの種別毎の出現回数に基づいて、前記検索対象コード列に位置する全ての各コードを一意に識別するコードＩＤの範囲であるコードＩＤ範囲を同一種別のコード毎に格納したコード別ＩＤ範囲表を生成するコード別ＩＤ範囲表生成ステップと、
前記検索対象コード列読出ステップで読み出した検索対象コード列と前記コード別ＩＤ範囲表生成ステップで生成されたコード別ＩＤ範囲表に基づき、前記コードＩＤに対応して、前記検索対象コード列において該コードＩＤに係るコードの次に位置するコードのコードＩＤである次コードＩＤを格納したＩＤ関係表を生成するＩＤ関係表生成ステップと、
を備えたことを特徴とする索引データ作成方法。
【請求項２４】
検索対象である検索対象コード列を検索コード列により検索するコード列検索のための索引データ作成装置の機能をコンピュータに実現させる索引データ作成プログラムにおいて、
コンピュータに、
前記検索対象コード列を読み出し、該読み出した検索対象コード列のコードの種別毎の出現回数を求める検索対象コード列読出機能、
前記検索対象コード列読出機能により求めたコードの種別毎の出現回数に基づいて、前記検索対象コード列に位置する全ての各コードを一意に識別するコードＩＤの範囲であるコードＩＤ範囲を同一種別のコード毎に格納したコード別ＩＤ範囲表を生成するコード別ＩＤ範囲表生成機能、
前記検索対象コード列読出機能により読み出した検索対象コード列と前記コード別ＩＤ範囲表生成機能により生成されたコード別ＩＤ範囲表に基づき、前記コードＩＤに対応して、前記検索対象コード列において該コードＩＤに係るコードの次に位置するコードのコードＩＤである次コードＩＤを格納したＩＤ関係表を生成するＩＤ関係表生成機能、
を実現させることを特徴とする索引データ作成プログラム。
【請求項２５】
請求項２４に記載の索引データ作成プログラムを記録したことを特徴とするコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ビット列で構成される文字コードあるいは文字コード列を検索する文字列検索のように、コンピュータにより、ビット列で構成されるコードあるいはコード列を検索するコード列検索に関するものである。
【背景技術】
【０００２】
近年、ビジネス文書を作成するためにワードプロセッサを使用することが通例となり、またインターネットが普及したことにより、ビット列からなる文字コードを用いた、コンピュータで処理可能な電子文書が世の中に大量に存在するようになっている。そのため、これら大量の電子文書の中からコンピュータを利用して必要なものを探し出すために、各種の文字列検索手法が開発されている。【０００３】
これらの文字列検索手法においては、高速な検索を実現するために予め索引を作成することが一般的である。索引としては、例えば、文書中の単語を抽出し、単語毎にそれの含まれている文書名を対応付けた転置インデックスがよく知られている。この転置インデックスはサイズが比較的小さく、検索が高速であり、インデックスの構成も簡単であるという特徴を持っている。しかしながら、単語の抽出が難しい言語もある。また、複数の単語の組み合わせの検索を行おうとすると、文書中の単語位置を突き合わせる処理が必要になるという欠点も存在する。そして、一文中の任意の文字列を検索することも難しい。【０００４】
そこで、任意の文字列を検索可能とする接尾辞配列という索引が開発されている。下記特許文献１及び非特許文献１には、接尾辞配列とそれを用いた検索手法が開示されている。
図１は、上述の接尾辞配列に関する従来の検索方法の例を説明するものである。図１の（ａ）に例示するのは、検索対象の文字列である。図に示すように、文字列１０は、アルファベットの文字Ａ、Ｂ、Ｃ、Ｅと区切り文字＄で構成されている。文字Ａは文字列１０の文字位置１、４、７に位置している。文字Ｂは文字列１０の文字位置２、５に位置している。文字Ｃは文字列１０の文字位置６、８に位置している。文字Ｅは文字列１０の文字位置３に位置している。区切り文字＄は、文字列１０の末尾の位置である文字位置９に位置している。【０００５】
図１の（ｂ）に示すのは、文字位置順の接尾辞２０、辞書順の接尾辞２０ａ及び接尾辞配列３０である。
文字列１０は、図１の（ｂ）に示すようにその部分文字列として９の接尾辞を持つと考えることができる。各接尾辞の先頭文字の文字位置順に接尾辞を並べた文字位置順の接尾辞２０を辞書順にソートすることにより、辞書順の接尾辞２０ａが得られる。このとき、辞書順に並べ替えた接尾辞の先頭文字の文字位置を配列に格納することにより、接尾辞配列３０が得られる。この接尾辞配列により、検索文字列のパターンと一致する検索対象文字列中の部分文字列の先頭の文字位置を求めることができる。【０００６】
図１の（ｃ）に示すのは、圧縮接尾辞配列による文字列検索の概念を説明するものであり、検索文字列４０と接尾辞配列３０に対応する圧縮接尾辞配列（概念図）５０が示されている。圧縮接尾辞配列（概念図）５０の配列番号（ｉ）には、次の配列番号（Ψ）が格納されている。次の配列番号（Ψ）は、接尾辞配列３０の配列番号（ｉ）に格納された文字位置に１を加えた文字位置が格納された接尾辞配列３０の配列番号である。【０００７】
配列に格納するものを文字位置から次の配列番号（Ψ）に変更することにより、文字毎に格納される値は図に示すように昇順になる。したがって、各配列要素に格納する値は次の配列番号（Ψ）そのものではなく１つ前の配列要素に格納された値の増分とすることができるのでビット幅を狭くすることができ、情報量を圧縮することができる。【０００８】
検索の概念については、例示された検索文字列４０の各文字から圧縮接尾辞配列（概念図）５０の配列番号（ｉ）への点線の矢印と配列番号（ｉ）の太字で示す３、６、９と次の配列番号（Ψ）の太字で示す６、９との間の矢印の検索ステップで示している。すなわち、検索文字列４０の先頭の文字Ａに対応する配列番号から例えば３が選ばれ、配列番号３の次の配列番号６が検索文字列４０の２番目の文字Ｂに対応する配列番号であり、配列番号６の次の配列番号９が検索文字列４０の３番目の文字Ｅに対応する配列番号であることにより、検索対象の文字列１０が検索文字列４０による検索でヒットすることがわかる。
【特許文献１】特許第３、６７２、２４２号公報
【非特許文献１】定兼、「圧縮接尾辞に関する考察」、電子情報通信学会技術研究報告（2000-7-19）Vol.100,No.226,p49-56
【発明の開示】
【０００９】
文字列検索に圧縮接尾辞配列を用いることにより、任意の文字列の検索を行うことができ、配列の容量も削減することができる。しかし、圧縮接尾辞配列を作成するには、その前に検索対象の文字列から接尾辞を作成しその接尾辞を辞書順にソートして接尾辞配列を作成する必要があり、検索対象の文字列から圧縮接尾辞配列を作成する処理時間が大きなものとなる。
【００１０】
そこで本発明の解決しようとする課題は、文字列に限らず、任意のコード列の検索を行うことができる索引データの作成時間を従来のものよりも短縮することである。そして、本発明の目的は、任意のコード列の検索を行うことができ、従来よりも短時間で作成することのできる索引のデータ構造を求め、それを用いたコード列検索手法を提供することである。
【００１１】
本発明によれば、まず、検索対象であるコード列に位置する全ての各コードを一意に識別するコードＩＤが、異なるコードの値（以下、誤解の恐れのない場合には、単にコードという場合がある。また、逆に異なるコード値であることを強調して、コード種別ということもある。）間でコードＩＤの範囲が重ならないように、上記全ての各コードに付与されるものとする。例えばコード毎にコード列中に出現する順に昇順のコードＩＤを付与することを、コード種別毎に最初のコードＩＤの値をそれまで付与されたコードＩＤより大きい値として繰り返すことにより、上記コードＩＤの付与を実現することができる。
そして本発明によれば、コード毎にそのコードＩＤの範囲を格納したコード別ＩＤ範囲表と各コードＩＤの次に位置するコードＩＤである次コードＩＤを格納したＩＤ関係表を作成し、コード別ＩＤ範囲表とＩＤ関係表を用いてコード列検索を実施する。
【００１２】
本発明の、検索コード列による検索対象コード列のコード列検索によれば、検索対象コード列のコード別ＩＤ範囲表から検索コード列を構成するコードのコードＩＤの範囲を読み出し、読み出された検索コード列の先頭のコードのコードＩＤ範囲に含まれるコードＩＤに対応して格納された次コードＩＤをＩＤ関係表から読み出すとともに、該次のコードに対応して格納された次コードＩＤを順次ＩＤ関係表から読み出し、ＩＤ関係表から読み出した次コードＩＤがコード別ＩＤ範囲読出表から読み出したコードＩＤの範囲に含まれるか照合する。
【００１３】
本発明によれば、簡単な構造のコード別ＩＤ範囲表とＩＤ関係表を用いて検索を実施することができるので、接尾辞配列を作成する必要がなく、コンピュータの索引作成の処理負担を小さくすることができる。
【図面の簡単な説明】
【００１４】
【図１】接尾辞配列に関する従来の検索方法の例を説明する図である。
【図２Ａ】本発明の一実施の形態における索引用のデータ構造を作成するための機能ブロックを説明する図である。
【図２Ｂ】本発明の一実施の形態におけるコード列検索を行うための機能ブロックを説明する図である。
【図２Ｃ】本発明の一実施の形態におけるハードウェア構成例を説明する図である。
【図３Ａ】本発明の一実施形態における索引データの構造を説明する図である。
【図３Ｂ】本発明の一実施の形態におけるコード列検索の概念を説明する図である。
【図４】本発明の一実施形態における索引データを作成する処理の概略フローを説明する図である。
【図５Ａ】本発明の一実施形態における検索対象のコード列に含まれるコードのコード種別毎の出現回数を計数する処理フローを説明する図である。
【図５Ｂ】本発明の一実施形態における出現回数をもとにコード種別毎のコードＩＤ範囲を設定する処理フローを説明する図である。
【図５Ｃ】本発明の一実施形態における検索対象コード列に含まれるコードをもとにＩＤ関係表を完成させる処理フローを説明する図である。
【図６Ａ】本発明の一実施形態におけるコード列検索処理に共通な前段の処理フローを説明する図である。
【図６Ｂ】本発明の一実施の形態における完全一致検索の後段の処理フローを説明する図である。
【図６Ｃ】本発明の一実施の形態における前方一致検索の後段の処理フローを説明する図である。
【図６Ｄ】本発明の一実施の形態における任意コードを含む検索の後段の処理フローを説明する図である。
【図７Ａ】本発明の一実施の形態における完全一致検索の流れを説明する図である。
【図７Ｂ】本発明の一実施の形態における任意コードを含む検索の流れを説明する図である。
【発明を実施するための最良の形態】
【００１５】
以下、本発明を実施するための最良の形態を、図面を参照しながら説明する。
図２Ａは、本発明の一実施の形態における索引用のデータ構造を作成するための機能ブロックを説明する図である。検索対象コード列が検索対象コード列読出手段１０１で読み出され、コード別ＩＤ範囲表生成手段１０２とＩＤ関係表生成手段１０３に渡される。【００１６】
コード別ＩＤ範囲表生成手段１０２は、コード毎にそのコードＩＤの範囲を格納したコード別ＩＤ範囲表を作成し、ＩＤ関係表生成手段１０３は、各コードＩＤの次に位置するコードＩＤである次コードＩＤを格納したＩＤ関係表を生成する。これらのコード別ＩＤ範囲表とＩＤ関係表は検索対象のコード列毎に生成される。【００１７】
図２Ｂは、本発明の一実施の形態におけるコード列検索を行うための機能ブロックを説明する図である。検索コード列が検索コード列読出手段１１１で読み出され、コード別ＩＤ範囲読出手段１１２に渡される。コード別ＩＤ範囲読出手段１１２は、コード別ＩＤ範囲表生成手段１０２で生成されたコード別ＩＤ範囲表より、検索コード列読出手段１１１から渡された検索コード列を構成するコードのコードＩＤの範囲を読み出してＩＤ関係読出手段１１３とコードＩＤ照合手段１１４に渡す。【００１８】
ＩＤ関係読出手段１１３は、コード別ＩＤ範囲読出手段１１２から渡された検索コード列の先頭のコードのコードＩＤ範囲に含まれるコードＩＤに対応して格納された次コードＩＤを、ＩＤ関係表生成手段１０３で生成されたＩＤ関係表から読み出すとともに、該次のコードに対応して格納された次コードＩＤを順次ＩＤ関係表から読み出してコードＩＤ照合手段１１４に渡す。【００１９】
コードＩＤ照合手段１１４は、ＩＤ関係読出手段１１３から渡された次コードＩＤがコード別ＩＤ範囲読出手段から渡されたコードＩＤの範囲に含まれるか照合し、検索結果を出力する。【００２０】
図２Ｃは、本発明の一実施の形態におけるハードウェア構成例を説明する図である。
本発明の検索装置による検索処理及び索引生成処理は中央処理装置３０２及びキャッシュメモリ３０３を少なくとも備えたデータ処理装置３０１によりデータ格納装置３０８を用いて実施される。コードＩＤ範囲表３０９とＩＤ関係表３１０を有するデータ格納装置３０８は、主記憶装置３０５または外部記憶装置３０６で実現することができ、あるいは通信装置３０７を介して接続された遠方に配置された装置を用いることも可能である。【００２１】
図２Ａ及び図２Ｂを参照して説明した検索対象コード列読出手段１０１等の各機能ブロックは、図２Ｃに例示するハードウェアと後に説明するステップを備えたソフトウェアにより実現可能である。【００２２】
図２Ｃの例示では、主記憶装置３０５、外部記憶装置３０６及び通信装置３０７が一本のバス３０４によりデータ処理装置３０１に接続されているが、接続方法はこれに限るものではない。また、主記憶装置３０５をデータ処理装置３０１内のものとすることもできる。
また、特に図示されてはいないが、処理の途中で得られた各種の値を後の処理で用いるためにそれぞれの処理に応じた一時記憶領域が用いられることは当然である。以下の説明では、一時記憶領域に格納されたあるいは設定された値を一時記憶領域の名前で呼ぶことがある。【００２３】
次に、本発明の一実施態様における検索手法の概要を説明する。
図３Ａは、本発明の一実施の形態における索引データの構造を説明する図である。図３Ａの（ａ）に示すのは、索引データを作成する対象となる検索対象のコード列の例である。例示された検索対象コード列１０ａは、コードＡ、Ｂ、Ｅ、Ａ、Ｂ、Ｃ、Ａ、Ｃの８つの英文字の文字コードから構成されている。それぞれの文字コードの下に記載されたＰ１〜Ｐ８は、検索対象コード列１０ａにおけるコードの位置を表している。コード位置ポインタ１１は、検索対象コード列１０ａにおけるコードの位置を示すポインタであり、図の例ではコード位置Ｐ１を指している。個々の検索対象コード列に対して、索引データとして、コード別ＩＤ範囲表とＩＤ関係表が生成される。【００２４】
図３Ａの（ｂ）に示すのは、コード列検索のための索引のデータ構造例であり、図３Ａの（ａ）に示す検索対象コード列に対応して生成されるコード別ＩＤ範囲表３０９とＩＤ関係表３１０が例示されている。
コード別ＩＤ範囲表３０９のエントリは、索引データを作成する対象である検索対象コード列に出現する異なるコードの種別毎に作成される。コード別ＩＤ範囲表３０９の左側に表示しているように、図に示す例では、アルファベットのうち、コードＡ〜Ｅからなるコード列である検索対象コード列が索引データを作成する対象であり、各コードに対応してエントリが作成されている。コード種別ポインタ３１１は、コード別ＩＤ範囲表３０９のエントリを指すポインタであり、図の例では、コードＡに対応するエントリを指している。
なお、各コードはビット列で構成されることから、そのビット列のビット値により表現される値を持つ。したがって、コード別ＩＤ範囲表３０９の各コードに対応するエントリの位置は各コードの値と対応付けることができることは明らかである。つまり、コード種別ポインタ３１１のとる値をコードそのものとすることもできる。そこで、以下の説明においては、各コードに対応するエントリを、各コードの指すエントリと表記することがある。【００２５】
コード別ＩＤ範囲表３０９の下側に表示しているように、コード別ＩＤ範囲表３０９のエントリは、設定表示、出現回数、先頭コードＩＤ、末尾コードＩＤ、コード別ＩＤカウンタの項目で構成されている。設定表示は、１あるいは０で対応する検索対象コード列にそのコードが出現するかを示すものであり、図の例では、検索対象コード列１０ａにはコードＤが出現しないので、コードＤのエントリでのみ０であり、他のエントリでは１である。出現回数は、検索対象コード列にそのコードが出現する回数であり、図の例では、検索対象コード列１０ａに対応して、コードＡからコードＥに対して、３、２、２、０、１が格納されている。【００２６】
先頭コードＩＤ及び末尾コードＩＤは、コード別のコードＩＤの範囲を示すものである。コードＩＤは、コード間で重ならないように、コード毎に検索対象コード列中の出現順に付与されたものであり、図に示す例では、コードＡについては出現回数が３であるのでＩＤ１からＩＤ３の範囲であり、次のコードＢについては出現回数が２であるのでＩＤ４からＩＤ５の範囲である。以下同様に、コードＣについてはＩＤ６からＩＤ７、コードＥについては、出現回数が１なので先頭コードと末尾コードは共にＩＤ８である。【００２７】
なお、ＩＤ１等の値は具体的には１から始まる整数値とすることが好適であるが、それに限ることなく、コード別のＩＤ範囲を識別することのできるものであればよい。また、図の例では、コードＩＤの範囲を先頭コードＩＤと末尾コードＩＤで示しているが、可変長データとなることをいとわなければ、すべてのコードＩＤを列挙することで示すこともできる。【００２８】
コード別ＩＤカウンタは、コード別ＩＤ範囲表を生成したのちＩＤ関係表を生成するときに必要なカウンタであり、索引データとして必要なものではない。したがって、異なるコードの種別毎にコード別ＩＤ範囲表とは別のカウンタとして設けることもできる。【００２９】
ＩＤ関係表３１０のエントリは、検索対象コード列１０ａのコードに対してつけられたコードＩＤ毎に作成される。ＩＤ関係表３１０の左側に表示しているように、図に示す例では、コードＩＤ１〜コードＩＤ８に対応してエントリが作成されている。各エントリは、コード位置と次コードＩＤの項目から構成されている。コードＩＤポインタ３１２は、ＩＤ関係表３１０のエントリを指すポインタであり、図の例ではＩＤ１を指している。【００３０】
各コードＩＤのエントリのコード位置は、そのコードＩＤのコードの位置する検索対象コード列１０ａにおけるコード位置であり、図に示す例では、ＩＤ１に対してＰ１、ＩＤ２に対してＰ４、ＩＤ３に対してＰ７、ＩＤ４に対してＰ２、ＩＤ５に対してＰ５、ＩＤ６に対してＰ６、ＩＤ７に対してＰ８、ＩＤ８に対してＰ３が格納されている。【００３１】
図の点線の矢印３１３ａで示すように、ＩＤ関係表３１０の１〜３番目のエントリはコードＡに対応するものである。同様に、点線の矢印３１３ｂで示すように、４、５番目のエントリはコードＢに、点線の矢印３１３ｃで示すように、６、７番目のエントリはコードＣに、点線の矢印３１３ｅで示すように、８番目のエントリはコードＥに対応する。【００３２】
各コードＩＤのエントリの次コードＩＤは、検索対象コード列１０ａにおけるそのコードＩＤのコードの次に位置するコードのコードＩＤである。図に示す例では、ＩＤ１に対してＩＤ４、ＩＤ２に対してＩＤ５、ＩＤ３に対してＩＤ７、ＩＤ４に対してＩＤ８、ＩＤ５に対してＩＤ６、ＩＤ６に対してＩＤ３、ＩＤ７に対してＩＤ１、ＩＤ８に対してＩＤ２が格納されている。なお、検索対象コード列１０ａの末尾のコードＣ（コードＩＤ７）に対しては、先頭のコードＡのコードＩＤであるＩＤ１が格納されている。【００３３】
ＩＤ関係表３１０は、コードＩＤで表した２つのコードが検索対象コード列において連続した位置関係にあることを索引データとして保持している。ＩＤ関係表３１０を図１の（ｃ）に示す従来例の圧縮接尾辞配列５０と比較すると、圧縮接尾辞配列５０では文字毎に次の配列番号がソートされているのに対して、ＩＤ関係表３１０では異なるコードの種別毎にコード位置がソートされている。したがって、同一コードを逐次検索する場合には、キャッシュ効果により高速化を図ることができる。【００３４】
図３Ｂは、本発明の一実施の形態におけるコード列検索の概念を説明する図である。
検索対象コード列を図３Ａに例示した検索対象コード列１０ａとし、検索コード列を図に示す検索コード列４０ａとして、コード列検索の概念を説明する。検索対象コード列１０ａに対応して、コード別ＩＤ範囲表３０９とＩＤ関係表３１０が生成されているものとする。【００３５】
検索コード列４０ａには、図に示すように、先頭からコードＥ、コードＡ、コードＢが位置している。そこで、図に点線の矢印３３１ａで示すように、１番目のコード３３２ａであるコードＥが読み出され、点線の矢印３３３ａで示すようにコード別ＩＤ範囲表３０９のコードＥに対応するエントリ３０９ａが読み出される。そして点線の矢印３３４ａで示すように、そのエントリからＩＤ範囲３３６ａに含まれるコードＩＤ、図の例ではコードＩＤ８に対応するエントリ３１０ａがＩＤ関係表３１０からさらに読み出される。【００３６】
次に点線の矢印３３１ｂで示すように、２番目のコード３３２ｂであるコードＡが読み出され、点線の矢印３３３ｂで示すように、コード別ＩＤ範囲表３０９のコードＡに対応するエントリ３０９ｂが読み出される。そして、双方向の点線の矢印３３５ｂで示すように、点線の矢印３３４ａでＩＤ関係表３１０から読み出されたコードＩＤ８に対応するエントリ３１０ａの次コードＩＤ３３７ａであるＩＤ２が、点線の矢印３３３ｂで読み出されたコードＡに対応するエントリ３０９ｂのコードＩＤの範囲３３６ｂ（ＩＤ１〜ＩＤ３）に含まれるかを判定する。図の例では、この判定はイエスになる。このことは、コードＥ、コードＡのコードの並びが、検索対象コード列１０ａに存在することを意味している。また、ＩＤ関係表３１０から読み出されたコードＩＤ８に対応するエントリ３１０ａのコード位置３３８ａがＰ３であることから、そのコードの並びの先頭位置がＰ３であることが分かる。【００３７】
さらに点線の矢印３３４ｂで示すように、次コードＩＤ３３７ａであるＩＤ２に対応するエントリ３１０ｂの次コードＩＤ３３７ｂであるＩＤ５が読み出される。一方、点線の矢印３３１ｃで示すように、３番目のコード３３２ｃであるコードＢが読み出され、点線の矢印３３３ｃで示すように、コード別ＩＤ範囲表３０９のコードＢに対応するエントリ３０９ｃが読み出される。そして、双方向の点線の矢印３３５ｃで示すように、点線の矢印３３４ｂでＩＤ関係表３１０から読み出されたコードＩＤ２に対応するエントリ３１０ｂの次コードＩＤ３３７ｂであるＩＤ５が、点線の矢印３３３ｃで読み出されたコードＢに対応するエントリ３０９ｃのコードＩＤの範囲３３６ｃ（ＩＤ４〜ＩＤ５）に含まれるかを判定する。図の例では、この判定はイエスになる。したがって、検索対象コード列１０ａは検索コード列ＥＡＢでヒットすることがわかる。また、ＩＤ関係表３１０から読み出されたコードＩＤ２に対応するエントリ３１０ｂのコード位置３３８ｂがＰ４であること、ＩＤ関係表３１０から読み出すコードＩＤ５に対応するエントリ３１０ｃのコード位置３３８ｃはＰ５であることから、ヒット位置はコード位置Ｐ３、Ｐ４、Ｐ５であることが分かる。
検索コード列４０ａの図示しない４番目のコードについても、エントリ３１０ｃの次コードＩＤ３３７ｃであるＩＤ６に対応するＩＤ関係表３１０のエントリの次コードＩＤが読み出され、４番目のコードのコード種別の指すコード別ＩＤ範囲表３０９のエントリのコードＩＤの範囲内であるかの判定が繰り返される。
以上のようにして、本発明の一実施の形態によるコード列検索が実施される。【００３８】
次に、本発明の一実施の形態における索引データの作成処理を説明する。
図４は、本発明の一実施形態における索引データを作成する処理の概略フローを説明する図である。【００３９】
まず、ステップＳ４０１において、検索対象のコード種別数をもとにコード別ＩＤ範囲表の領域を確保すると共に、検索対象コード列に含まれるコードを順次読み出してコード種別毎の出現回数とコードの総数を求める。ステップＳ４０１の処理の詳細は、後に図５Ａを参照して説明する。【００４０】
次に、ステップＳ４０２で、コード種別毎の出現回数をもとに、コード別ＩＤ範囲表にコード種別毎のコードＩＤの範囲を設定する。ステップＳ４０２の処理の詳細は、後に図５Ｂを参照して説明する。【００４１】
次にステップＳ４０３で、コード総数をもとにＩＤ関係表の領域を確保すると共に、コード別ＩＤ範囲表を参照しながら、検索対象コード列に含まれるコードを順次読み出してＩＤ関係表を完成させ、処理を終了する。ステップＳ４０２の処理の詳細は、後に図５Ｃを参照して説明する。【００４２】
図５Ａは、図４に示すステップＳ４０１の処理の詳細なフローを示すものであり、検索対象のコード列に含まれるコードのコード種別毎の出現回数を計数する処理フローを説明する図である。【００４３】
図に示すように、ステップＳ５０１において、検索対象コード列を設定する。検索対象コード列の設定は、データ格納装置に格納された検索対象となるコード列の集合から、１つのコード列を図２Ａに例示する検索対象コード列読出手段１０１で読み出して、図示しない検索対象コード列設定エリアに設定することを意味する。なお、上述の検索対象コード列設定エリアは、先に述べた「処理の途中で得られた各種の値を後の処理で用いるためにそれぞれの処理に応じた一時記憶装置」の１つである。以下の説明では、「図示しない検索対象コード列設定エリアに設定する」のような表現に変えて、「検索対象コード列として設定する」あるいは単に「検索対象コード列に設定する」のように記述することもある。検索対象コード列以外についても同様である。【００４４】
次にステップＳ５０２において、コードの種別数を設定する。コードの種別数は、コード体系により決定されるものであり、予め与えられるものとする。次にステップＳ５０３に進み、ステップＳ５０２で設定されたコードの種別数をもとにコード別ＩＤ範囲表の格納領域を確保し、出現回数を０に初期化する。続いてステップＳ５０４でコード位置ポインタに、ステップＳ５０１で設定したコード列の先頭位置を設定し、ステップＳ５０５でコード数カウンタに値０を設定する。以上のステップＳ５０１〜ステップＳ５０５の処理は、初期処理である。【００４５】
初期処理に続いてステップＳ５０６に進み、コード列より、コード位置ポインタの指すコードを取り出す。次にステップＳ５０７で、取り出したコードのコード種別に対応するコード別ＩＤ範囲表のエントリ（以下、コードの指すコード別ＩＤ範囲表ということがある。）の出現回数に値１を加え、ステップＳ５０８でコード数カウンタに値１を加えてステップＳ５０９に進む。【００４６】
ステップＳ５０９では、コード位置ポインタがコード列の末尾位置であるか判定し、末尾位置でなければステップＳ５１０でコード位置ポインタを次の位置に進めてステップＳ５０６に戻る。コード位置ポインタがコード列の末尾位置であれば、ステップＳ５１１でコード総数にコード数カウンタを設定して処理を終了する。上記ステップＳ５０９のコード位置ポインタがコード列の末尾位置であるかの判定は、例えば図１の（ａ）に例示したように、区切り文字を利用して行うことができる。
以上の処理により、コード別ＩＤ範囲表の出現回数が設定されると共に、コード総数が設定される。【００４７】
図５Ｂは、図４に示すステップＳ４０２の処理の詳細なフローを示すものであり、図５Ａに示す処理により設定された出現回数をもとにコード種別毎のコードＩＤ範囲を設定する処理フローを説明する図である。【００４８】
まずステップＳ５２１において、コード種別ポインタに、コード別ＩＤ範囲表の先頭位置を設定し、次にステップＳ５２２において、コードＩＤカウンタに初期値を設定する。次にステップＳ５２３に進み、コード種別ポインタの指すコード別ＩＤ範囲表より、出現回数を取り出し、ステップＳ５２４で取り出した出現回数が０か判定する。【００４９】
出現回数が０でなければ、ステップＳ５２５でコード種別ポインタの指すコード別ＩＤ範囲表の設定表示に「あり」を設定すると共に、先頭コードＩＤとコード別ＩＤカウンタにコードＩＤカウンタの値を設定する。次にステップＳ５２６でコードＩＤカウンタに出現回数を加え、ステップＳ５２７でコード種別ポインタの指すコード別ＩＤ範囲表の末尾コードＩＤに、コードＩＤカウンタの値より１を減じた値を設定してステップＳ５２９に進む。【００５０】
一方、ステップＳ５２４の判定で出現回数が０となった場合は、ステップＳ５２８でコード種別ポインタの指すコード別ＩＤ範囲表の設定表示に「なし」を設定してステップＳ５２９に進む。【００５１】
ステップＳ５２９では、コード種別ポインタはコード別ＩＤ範囲表の終端位置であるか判定し、終端位置でなければステップＳ５３０でコード種別ポインタを、コード別ＩＤ範囲表の次のコード種別の位置に進めてステップＳ５２３に戻る。終端位置であれば、コード別ＩＤ範囲表の設定は完了しているので、処理を終了する。【００５２】
図５Ｃは、図４に示すステップＳ４０３の処理の詳細なフローを示すものであり、検索対象コード列に含まれるコードをもとにＩＤ関係表を完成させる処理フローを説明する図である。【００５３】
まずステップＳ５４１で、図５Ｂに示す処理により求めたコード総数をもとに、ＩＤ関係表の格納領域を確保し、ステップＳ５４２で、コード位置ポインタに、検索対象コード列の先頭位置を設定する。次にステップＳ５４３で、検索対象コード列より、コード位置ポインタの指すコードを取り出し、ステップＳ５４４で、コードの指すコード別ＩＤ範囲表のコード別ＩＤカウンタを読み出し、コードＩＤポインタに設定する。次にステップＳ５４５で、最先頭コードＩＤに、コードＩＤポインタを設定し、ステップＳ５４６に進む。【００５４】
ステップＳ５４６では、コード位置ポインタは検索対象コード列の末尾位置か判定し、末尾位置でなければ、ステップＳ５４７〜ステップＳ５５４の処理を実行し、該当するコードＩＤの指すＩＤ関係表のコード位置と次コードＩＤを設定してステップＳ５４６に戻る。【００５５】
まずステップＳ５４７では、コードＩＤポインタの指すＩＤ関係表のコード位置に、コード位置ポインタを設定する。
次にステップＳ５５０で、ステップＳ５４３あるいは後記ステップＳ５５２で取り出したコードの指すコード別ＩＤ範囲表のコード別ＩＤカウンタに１を加え、ステップＳ５５１で、コード位置ポインタを次のコード位置に進める。【００５６】
次にステップＳ５５２において検索対象コード列より、コード位置ポインタの指すコードを取り出し、ステップＳ５５３で、該取り出したコードの指すコード別ＩＤ範囲表のコード別ＩＤカウンタを読み出し、コードＩＤカウンタの指すＩＤ関係表の次コードＩＤに設定する。【００５７】
次にステップＳ５５４において、ステップＳ５５３で読み出したコード別ＩＤカウンタをコードＩＤカウンタに設定してステップＳ５４６に戻る。以上のステップＳ５４６〜ステップＳ５５４の処理をコード位置ポインタが検索対象コード列の末尾位置を指すまで繰り返し、コード位置ポインタが検索対象コード列の末尾位置になるとステップＳ５５５に分岐する。ステップＳ５５５では、コードＩＤポインタの指すＩＤ関係表の、コード位置にコード位置ポインタを、次コードＩＤにステップＳ５４５で設定した最先頭コードＩＤを設定して処理を終了する。【００５８】
次に、図６Ａ〜図６Ｄを参照して、本発明の一実施の形態におけるコード列検索の処理を説明する。
図６Ａに示すのは、図６Ｂ〜図６Ｄに示す完全一致検索、前方一致検索及び任意コードを含む検索処理に共通な前段の処理フローを説明する図である。【００５９】
まず、ステップＳ６０１において、検索先頭位置に、検索コード列の先頭位置を設定する。検索コード列は、図２Ｂに示す検索コード列読出手段１１１により読み出されており、その読み出された検索コード列の先頭位置は与えられているものとする。【００６０】
次に、ステップＳ６０２で検索先頭位置の指す検索コード列より、検索コードを取り出し、ステップＳ６０３で、検索先頭位置の検索コードに、ステップＳ６０２で取り出した検索コードを設定し、さらにステップＳ６０４で、検索進行位置に、検索先頭位置を設定してステップＳ６０５に進む。【００６１】
ステップＳ６０５では、ステップＳ６０２あるいは後記ステップＳ６０９で取り出した検索コードの指すコード別範囲表より、設定表示を取り出し、次にステップＳ６０６で該取り出した設定表示は「あり」であるか判定する。設定表示が「あり」でなければ、検索コード列中の検索コードに検索対象コード列中に存在しないコードがあるということであるから、検索処理失敗として処理を終了する。【００６２】
ステップＳ６０６の判定の結果が設定表示は「あり」であれば、ステップＳ６０７に進み、ステップＳ６０４あるいは後記ステップＳ６０８で設定した検索進行位置は検索コード列の末尾位置か判定する。検索進行位置が検索コード列の末尾位置でなければステップＳ６０８で検索コード位置に次の検索コードの位置を設定し、さらにステップＳ６０９で、検索進行位置の指す検索コード列より検索コードを取り出してステップＳ６０５に戻る。【００６３】
上述のステップＳ６０５〜ステップＳ６０９のループ処理を、ステップＳ６０７で検索進行位置は検索コード列の末尾位置であると判定されるまで繰り返し、ステップＳ６０７で検索進行位置は検索コード列の末尾位置であると判定されるとステップＳ６１０に進む。上述のループ処理は、検索コード列中の検索コードが検索対象コード列中に存在することを予め確認する処理である。【００６４】
ステップＳ６１０では、検索末尾位置に、検索進行位置を設定する。次にステップＳ６１１で、ステップＳ６０１で設定した検索先頭位置の指す検索コード列より、検索コードを取り出し、ステップＳ６１２で、該取り出した検索コードの指すコード別ＩＤ範囲表より先頭コードＩＤを取り出して検索開始コードＩＤに設定し、ステップＳ６１３で、前記取り出した検索コードの指すコード別ＩＤ範囲表より末尾コードＩＤを取り出して検索終了コードＩＤに設定する。以上の処理により、図６Ｂ〜図６Ｄに示す完全一致検索、前方一致検索及び任意コードを含む検索処理に共通な前段の処理を完了し、図６Ｂ〜図６Ｄに示す完全一致検索、前方一致検索及び任意コードを含む検索処理の後段の処理に進む。【００６５】
以上の前段の処理により、検索コード列中の検索コードが検索対象コード列中に存在することが保証される。また、検索コード列の先頭位置である検索先頭位置、検索コード列の末尾位置である検索末尾位置、検索コード列の先頭のコードの指すコード別ＩＤ範囲表の先頭コードＩＤと末尾コードＩＤである検索開始コードＩＤと検索終了コードＩＤが後段の処理のために設定される。図３Ａ及び図３Ｂに示す例では、検索開始コードＩＤと検索終了コードＩＤの双方にＩＤ８が設定される。【００６６】
図６Ｂは、本発明の一実施の形態における完全一致検索を行う後段の処理フローを説明する図である。
図に示すように、ステップＳ６２０でコードＩＤポインタに、前段の処理で設定された検索開始コードＩＤを設定し、ステップＳ６２１で検索進行位置に、前段の処理で設定された検索先頭位置を設定してステップＳ６２２に進む。図３Ａ及び図３Ｂに示す例では、コードＩＤポインタにはＩＤ８が設定される。【００６７】
ステップＳ６２２では、コードＩＤポインタの指すＩＤ関係表より次コードＩＤを取り出し、検索コードＩＤに設定すると共に、コードＩＤポインタに設定される。図３Ａ及び図３Ｂに示す例の最初の処理では、次コードＩＤとしてＩＤ２が取り出され、検索コードＩＤとコードＩＤポインタに設定される。このように、コードＩＤポインタの指すＩＤ関係表の次コードＩＤが、次のコードＩＤポインタとなる。【００６８】
次にステップＳ６２３で検索進行位置は検索末尾位置か判定し、検索末尾位置でなければステップＳ６２４に分岐し、検索進行位置を、検索コード列の次の検索コードの位置に進め、ステップＳ６２５で、検索進行位置の指す検索コード列より検索コードを取り出し、ステップＳ６２７で、該取り出した検索コードの指すコード別ＩＤ範囲表より先頭コードＩＤと末尾コードＩＤを取り出す。【００６９】
そしてステップＳ６２８において、ステップＳ６２２で設定した検索コードＩＤがステップＳ６２７で取り出した先頭コードＩＤと末尾コードＩＤの範囲内か判定し、範囲内であればステップＳ６２２に戻り、範囲内でなければステップＳ６３０に進む。図３Ａ及び図３Ｂに示す例の最初の処理では、次に検索コードとして“Ａ”が取り出され、そのＩＤ範囲の先に述べた次コードＩＤであるＩＤ２が含まれることから、ステップＳ６２３に戻り、次のＩＤ範囲の照合処理に進む。【００７０】
なお、上述のステップＳ６２２〜ステップＳ６２８のループ処理は、検索対象コード列の、検索コード列の先頭コードと同一種別のコードが位置するコード位置を検索先頭位置として、検索コード列の先頭コードから末尾コードにかけて照合処理を繰り返すものである。【００７１】
一方、ステップＳ６２３で検索進行位置は検索末尾位置であると判定されると、ステップＳ６２９において、検索開始コードＩＤの指すＩＤ関係表よりコード位置を取り出し、検索結果コード位置に出力し、ステップＳ６３０に進む。図３Ａ及び図３Ｂに示す例では、ＩＤ８の指すＩＤ関係表３１０のコード位置Ｐ３が出力される。【００７２】
ステップＳ６３０では、検索開始コードＩＤは検索終了コードＩＤと等しいか判定し、等しくなければステップＳ６３１で、検索開始コードＩＤに値１を加えてステップＳ６２０に戻り、等しければ処理を終了する。上述の、ステップＳ６３０の判定からステップＳ６３１での検索開始コードＩＤの更新を経由してステップＳ６２０に戻る処理は、検索コード列の先頭コードの指すコード別ＩＤ範囲表の先頭コードＩＤから末尾コードＩＤまで検索開始コードＩＤを切り替えて、上述のステップＳ６２２〜ステップＳ６２８のループ処理を行うためのものである。別の言い方をすれば、検索対象コード列の、検索コード列の先頭コードと同一種別のコードが位置するコード位置を切り替えて、検索コード列の先頭コードから末尾コードにかけて照合処理を繰り返すためのものである。【００７３】
ステップＳ６３０で検索開始コードＩＤは検索終了コードＩＤと等しい判定されるのは、検索コード列の先頭コードと同一種別のコードが検索対象コード列において位置する全てのコード位置についての照合処理が終了したときであるから、全体の処理を終了する。処理結果は、ステップＳ６２９において出力されている。【００７４】
図６Ｃは、本発明の一実施の形態における前方一致検索を行う後段の処理フローを説明する図である。図６Ｂに示す完全一致検索を行う後段の処理フローと比較すると、図６Ｃに示すステップＳ６４０〜ステップＳ６５１の各ステップで実行する処理自体は、そのステップ番号から２０を引いたステップ番号の、図６Ｂに示すステップＳ６２０〜ステップＳ６３１の各ステップで実行する処理と同じである。しかし、図６Ｂに示す完全一致検索のステップＳ６２８では、検索コードＩＤは先頭コードＩＤと末尾コードＩＤの範囲内ではないと判定するとステップＳ６３０に分岐するのに対して、図６Ｃに示す前方一致検索のステップＳ６４８では、検索コードＩＤは先頭コードＩＤと末尾コードＩＤの範囲内ではないと判定するとステップＳ６４９に分岐して検索開始コードＩＤの指すＩＤ関係表よりコード位置を取り出し、検索結果位置に出力してからステップＳ６５０に進む。【００７５】
これは、図６Ａに示す前段の処理により、検索コード列中の検索コードが検索対象コード列中に存在することが保証されており、したがって、少なくとも検索コード列の先頭のコードまでは一致するコード列が検索対象コード列に存在するので、前方一致検索の検索結果として、検索開始コードＩＤの指すＩＤ関係表よりコード位置を取り出して出力する。
上述のステップＳ６４８での判定処理後の分岐先以外に関しては、先に述べたように全て図６Ｂに示すものと同じであるので、その説明は省略する。
なお、ステップＳ６４２において、コードＩＤポインタの指すＩＤ関係表のエントリより、次コードＩＤに加えてコード位置を順次取り出しておき、ステップＳ６４８において検索コードＩＤは先頭コードＩＤと末尾コードＩＤの範囲内ではないと判定したとき、ステップＳ６４２で最後に取り出したコード位置を、ステップＳ６４９において、検索開始コードＩＤの指すＩＤ関係表から取り出すコード位置とともに検索結果コード位置として出力してもよい。この最後に取り出したコード位置は、上述のステップＳ６４８での判定が否定的となったときの検索コードＩＤである次コードＩＤとＩＤ関係表の同一のエントリに含まれるコード位置であり、言い換えれば、ステップＳ６４８での判定が肯定的となる最後の検索コードＩＤの指すＩＤ関係表のエントリに格納されたコード位置である。
したがって、このコード位置に位置する検索対象コード列のコードまでは、検索コード列の検索コードと一致している。上記最後に取り出したコード位置と、検索開始コードＩＤの指すＩＤ関係表から取り出すコード位置を検索結果コード位置として出力することにより、検索コード列と前方一致する検索対象コード列のコード位置の範囲を知ることができる。【００７６】
図６Ｄは、本発明の一実施の形態における任意コードを含む検索を行う後段の処理フローを説明する図である。ここで任意コードとは、検索対象コード列の任意のコードと照合するコードである。検索コード列が任意コードを含み、任意コード以外の全てのコードが一致するコード列が検索対象コード列に存在すれば、その検索対象コード列は、前記任意コードを含む検索コード列でヒットする。【００７７】
図６Ｄに示すフローを図６Ｂに示す完全一致検索を行う後段の処理フローと比較すると、図６Ｄに示すステップＳ６６０〜ステップＳ６７１の各ステップで実行する処理は、ステップＳ６６６の処理がステップＳ６６５とステップＳ６６７の間に挿入されている以外は、そのステップ番号から４０を引いたステップ番号の、図６Ｂに示すステップＳ６２０〜ステップＳ６３１の各ステップで実行する処理と全く同じである。【００７８】
ステップＳ６６６では、ステップＳ６６５で取り出した検索コードは任意コードか判定する。ステップＳ６６６で任意コードと判定されると、ステップＳ６６７及びステップＳ６６８のコードＩＤの範囲の判定処理を経ることなくステップ６６２に戻る。ステップＳ６６６で任意コードと判定されなければ、ステップＳ６６７に進む。
上述のステップＳ６６６での判定処理以外は、先に述べたように全て図６Ｂに示すものと同じであるので、その説明は省略する。【００７９】
図７Ａは、本発明の一実施の形態における完全一致検索の流れを説明する図である。図７Ａに例示すものは、検索対象コード列を図３Ａに示すものとし、検索コード列をＡＢＣとしたものである。図７Ａの（ａ）、（ｂ）及び（ｃ）には、検索処理が進行するにつれて検索コード列、コード別ＩＤ範囲表及びＩＤ関係表を参照する流れが記載されている。【００８０】
図７Ａの（ａ）に示すのは、検索コード列ＡＢＣの検索開始コードＩＤを、コード列の先頭に位置するコードＡの先頭コードＩＤであるＩＤ１とした検索の流れである。なお、図６Ａに示すステップＳ６０１〜ステップＳ６０７の設定表示「あり」のチェックは終了しているものとする。
符号７０１ａを付した部分は検索コード列ＡＢＣの各検索コードを先頭から処理する流れを記載したものである。符号７０２ａを付した部分はコード別ＩＤ範囲表３０９の処理対象のコードＩＤ範囲が変わっていく流れを記載したものである。符号７０３ａを付した部分はＩＤ関係表３１０から順次次コードを求める流れを記載したものである。以下の説明においては、上述の３つの記載部分をその符号で参照する。図７Ａの（ｂ）、（ｃ）及び図７Ｂにおいても同様である。【００８１】
最初に検索コード列の先頭に位置するコードＡが７０１ａに示すように図６Ａの（以下の説明では、図面番号の表記は省略する。）ステップＳ６１１で取り出され、７０２ａへの矢印７２３ａで示すように、コードＡの指すコード別ＩＤ範囲表の先頭コードＩＤであるＩＤ１がステップＳ６１２で取り出されて検索開始コードＩＤに設定される。また末尾コードであるＩＤ３がステップＳ６１３で取り出されて検索終了コードＩＤに設定される。
次に、７０２ａのＩＤ１から７０３ａへの矢印７２４ａで示すように、ＩＤ１の指すＩＤ関係表３１０の次コードＩＤであるＩＤ４がステップＳ６２２で取り出される。【００８２】
一方、７０１ａのコードＡからコードＢへの矢印７２１ａに示すように、ステップＳ６２４で次のコード位置のコードが処理対象となり、ステップＳ６２５でコードＢが取り出される。７０２ａへの矢印７２３ｂで示すように、コードＢの指すコード別ＩＤ範囲表３０９の先頭コードＩＤであるＩＤ４と末尾コードＩＤであるＩＤ５がコードＩＤ範囲として取り出される。【００８３】
そして、７０３ａの、ＩＤ１の指すＩＤ関係表３１０の次コードＩＤであるＩＤ４と７０２ａの、コードＢの指すコード別ＩＤ範囲表３０９のコードＩＤ範囲の間の双方向の点線の矢印７２５ｂで示すように、ステップＳ６２８においてＩＤ１の指すＩＤ関係表３１０の次コードＩＤであるＩＤ４がコードＢの指すコード別ＩＤ範囲表３０９のコードＩＤ範囲であることが判定される。
すると次に、７０３ａ内の矢印７２４ｂで示すように、ＩＤ４の指すＩＤ関係表３１０の次コードＩＤであるＩＤ８がステップＳ６２２で取り出される。【００８４】
一方、７０１ａのコードＢからコードＣへの矢印７２１ｂに示すように、ステップＳ６２４で次のコード位置のコードが処理対象となり、ステップＳ６２５でコードＣが取り出される。７０２ａへの矢印７２３ｃで示すように、コードＣの指すコード別ＩＤ範囲表３０９の先頭コードＩＤであるＩＤ６と末尾コードＩＤであるＩＤ７がコードＩＤ範囲として取り出される。【００８５】
そして、７０３ａの、ＩＤ４の指すＩＤ関係表３１０の次コードＩＤであるＩＤ８と７０２ａの、コードＣの指すコード別ＩＤ範囲表３０９のコードＩＤ範囲の間の双方向の点線の矢印７２５ｃで示すように、ステップＳ６２８においてＩＤ４の指すＩＤ関係表３１０の次コードＩＤであるＩＤ８がコードＣの指すコード別ＩＤ範囲表３０９のコードＩＤ範囲外であることが判定される。
つまり、検索対象コード列１０ａのうち、コードＩＤがＩＤ１であるコードＡからのコード列は、検索コード列ＡＢＣと一致しないことを示している。これは、検索対象コード列１０ａのうち、コードＩＤがＩＤ１であるコードＡからのコード列は、図３Ａの（ａ）に示すようにＡＢＥであり、ＡＢＣではないことに整合している。【００８６】
図７Ａの（ｂ）に示すのは、検索コード列ＡＢＣの検索開始コードＩＤを、ステップＳ６３１でコードＡのＩＤ１の次のコードＩＤであるＩＤ２とした検索の流れである。図７Ａの（ａ）に示す流れに続いて、７０２ｂのＩＤ２から７０３ｂへの矢印７２４ａで示すように、ＩＤ２の指すＩＤ関係表３１０の次コードＩＤであるＩＤ５がステップＳ６２２で取り出される。【００８７】
一方、７０１ｂのコードＡからコードＢへの矢印７２１ａに示すように、ステップＳ６２４で次のコード位置のコードが処理対象となり、ステップＳ６２５でコードＢが取り出される。７０２ｂへの矢印７２３ｂで示すように、コードＢの指すコード別ＩＤ範囲表３０９の先頭コードＩＤであるＩＤ４と末尾コードＩＤであるＩＤ５がコードＩＤ範囲として取り出される。【００８８】
そして、７０３ｂの、ＩＤ２の指すＩＤ関係表３１０の次コードＩＤであるＩＤ５と７０２ｂの、コードＢの指すコード別ＩＤ範囲表３０９のコードＩＤ範囲の間の双方向の点線の矢印７２５ｂで示すように、ステップＳ６２８においてＩＤ１の指すＩＤ関係表３１０の次コードＩＤであるＩＤ５がコードＢの指すコード別ＩＤ範囲表３０９のコードＩＤ範囲であることが判定される。
すると次に、７０３ｂ内の矢印７２４ｂで示すように、ＩＤ５の指すＩＤ関係表３１０の次コードＩＤであるＩＤ６がステップＳ６２２で取り出される。【００８９】
一方、７０１ｂのコードＢからコードＣへの矢印７２１ｂに示すように、ステップＳ６２４で次のコード位置のコードが処理対象となり、ステップＳ６２５でコードＣが取り出される。７０２ｂへの矢印７２３ｃで示すように、コードＣの指すコード別ＩＤ範囲表３０９の先頭コードＩＤであるＩＤ６と末尾コードＩＤであるＩＤ７がコードＩＤ範囲として取り出される。【００９０】
そして、７０３ｂの、ＩＤ５の指すＩＤ関係表３１０の次コードＩＤであるＩＤ６と７０２ｂの、コードＣの指すコード別ＩＤ範囲表３０９のコードＩＤ範囲の間の双方向の点線の矢印７２５ｃで示すように、ステップＳ６２８においてＩＤ５の指すＩＤ関係表３１０の次コードＩＤであるＩＤ６がコードＣの指すコード別ＩＤ範囲表３０９のコードＩＤ範囲内であることが判定される。【００９１】
つまり、検索対象コード列１０ａのうち、コードＩＤがＩＤ２であるコードＡからのコード列は、検索コード列ＡＢＣと一致することを示している。これは、検索対象コード列１０ａのうち、コードＩＤがＩＤ２であるコードＡからのコード列は、図３Ａの（ａ）に示すようにＡＢＣであることに整合している。
そこでステップＳ６２９で、矢印７２８ａに示すように、符号７０４ｂで示す検索結果コード位置に、検索開始コードＩＤであるＩＤ２の指すＩＤ関係表３１０のコード位置Ｐ４を設定する。【００９２】
図７Ａの（ｃ）に示すのは、検索コード列ＡＢＣの検索開始コードＩＤを、ステップＳ６３１でコードＡのＩＤ２の次のコードＩＤであるＩＤ３とした検索の流れである。図７Ａの（ｂ）に示す流れに続いて、７０２ｃのＩＤ３から７０３ｃへの矢印７２４ａで示すように、ＩＤ３の指すＩＤ関係表３１０の次コードＩＤであるＩＤ７がステップＳ６２２で取り出される。【００９３】
一方、７０１ｃのコードＡからコードＢへの矢印７２１ａに示すように、ステップＳ６２４で次のコード位置のコードが処理対象となり、ステップＳ６２５でコードＢが取り出される。７０２ｃへの矢印７２３ｂで示すように、コードＢの指すコード別ＩＤ範囲表３０９の先頭コードＩＤであるＩＤ４と末尾コードＩＤであるＩＤ５がコードＩＤ範囲として取り出される。【００９４】
そして、７０３ｃの、ＩＤ３の指すＩＤ関係表３１０の次コードＩＤであるＩＤ７と７０２ｃの、コードＣの指すコード別ＩＤ範囲表３０９のコードＩＤ範囲の間の双方向の点線の矢印７２５ｂで示すように、ステップＳ６２８においてＩＤ３の指すＩＤ関係表３１０の次コードＩＤであるＩＤ７がコードＣの指すコード別ＩＤ範囲表３０９のコードＩＤ範囲外であることが判定される。
つまり、検索対象コード列１０ａのうち、コードＩＤがＩＤ３であるコードＡからのコード列は、検索コード列ＡＢＣと一致しないことを示している。これは、検索対象コード列１０ａのうち、コードＩＤがＩＤ３であるコードＡからのコード列は、図３Ａの（ａ）に示すようにＡＣであり、ＡＢＣではないことに整合している。【００９５】
以上の処理の流れに示すように、検索コード列の先頭に位置するコードのコード種別と同一種別のコードのすべてのコードＩＤを検索開始コードＩＤとして照合処理を行い、検索コード列のすべての検索コードについて一致している場合に、その検索開始コードＩＤの指すＩＤ関係表のコード位置を検索結果コード位置に出力する。
なお、前方一致検索の流れは図示しないが、図７Ａを援用して前方一致検索の流れを説明すると、図７Ａの（ａ）の双方向の点線の矢印７２５ｃ、図７Ａの（ｃ）の双方向の点線の矢印７２５ｂに示す判定においてコードＩＤ範囲外となったときであっても、少なくとも検索コード列の先頭のコードまでは一致するコード列が検索対象コード列に存在するので、前方一致検索の検索結果として、検索開始コードＩＤの指すＩＤ関係表よりコード位置を取り出して出力する。図７Ａの（ａ）、（ｃ）の例では、コード位置Ｐ１、Ｐ７を検索結果コード位置に出力する。【００９６】
図７Ｂは、本発明の一実施の形態における任意コードを含む検索の流れを説明する図である。図７Ｂに例示すものは、検索対象コード列を図３Ａに示すものとし、検索コード列をＢ？Ａとしたものである。“？”は任意コードである。図７Ｂの（ａ）及び（ｂ）には、検索処理が進行するにつれて検索コード列、コード別ＩＤ範囲表及びＩＤ関係表を参照する流れが記載されている。【００９７】
図７Ｂの（ａ）に示すのは、検索コード列Ｂ？Ａの検索開始コードＩＤを、コード列の先頭に位置するコードＢの先頭コードＩＤであるＩＤ４とした検索の流れである。なお、図７Ａの例示と同様に、図６Ａに示すステップＳ６０１〜ステップＳ６０７の設定表示「あり」のチェックは終了しているものとする。
符号７１１ａを付した部分は検索コード列Ｂ？Ａの各検索コードを先頭から処理する流れを記載したものである。符号７１２ａを付した部分はコード別ＩＤ範囲表３０９の処理対象のコードＩＤ範囲が変わっていく流れを記載したものである。符号７１３ａを付した部分はＩＤ関係表３１０から順次次コードを求める流れを記載したものである。【００９８】
最初に検索コード列の先頭に位置するコードＢが７１１ａに示すようにステップＳ６１１で取り出され、７１２ａへの矢印７３３ａで示すように、コードＢの指すコード別ＩＤ範囲表の先頭コードＩＤであるＩＤ４がステップＳ６１２で取り出されて検索開始コードＩＤに設定される。また末尾コードであるＩＤ５がステップＳ６１３で取り出されて検索終了コードＩＤに設定される。
次に、７１２ａのＩＤ４から７１３ａへの矢印７３４ａで示すように、ＩＤ４の指すＩＤ関係表３１０の次コードＩＤであるＩＤ８がステップＳ６２２で取り出される。【００９９】
一方、７１１ａのコードＢからコード？への矢印７３１ａに示すように、ステップＳ６６４で次のコード位置のコードが処理対象となり、ステップＳ６６５でコード？が取り出される。次にステップＳ６６６で、ステップＳ６６５で取り出された検索コードが任意コードであるかの判定が行わる。【０１００】
今の例では任意コードであるので、７１１ａの任意コード？から７１３ａのＩＤ４の指すＩＤ関係表３１０の次コードＩＤであるＩＤ８への点線の矢印７３３ｂで示すように、ＩＤ８についてのコードＩＤ範囲の照合処理は省略される。
そして、７１３ａ内の矢印７３４ｂで示すように、ＩＤ８の指すＩＤ関係表３１０の次コードＩＤであるＩＤ３がステップＳ６２２で取り出される。【０１０１】
一方、７１１ａの任意コード？からコードＡへの矢印７３１ｂに示すように、ステップＳ６６４で次のコード位置のコードが処理対象となり、ステップＳ６６５でコードＡが取り出される。７１２ａへの矢印７３３ｂで示すように、コードＡの指すコード別ＩＤ範囲表３０９の先頭コードＩＤであるＩＤ１と末尾コードＩＤであるＩＤ３がコードＩＤ範囲として取り出される。【０１０２】
そして、７１３ａの、ＩＤ８の指すＩＤ関係表３１０の次コードＩＤであるＩＤ２と７１２ａの、コードＡの指すコード別ＩＤ範囲表３０９のコードＩＤ範囲の間の双方向の点線の矢印７３５ｂで示すように、ステップＳ６６８においてＩＤ８の指すＩＤ関係表３１０の次コードＩＤであるＩＤ２がコードＡの指すコード別ＩＤ範囲表３０９のコードＩＤ範囲内であることが判定される。そこでステップＳ６６９で、矢印７３８ａで示すように、符号７１４ａで示す検索結果コード位置に、検索開始コードＩＤであるＩＤ４の指すＩＤ関係表３１０のコード位置Ｐ２を設定する。【０１０３】
図７Ｂの（ｂ）に示すのは、検索コード列Ｂ？Ａの検索開始コードＩＤを、ステップＳ６７１でコードＢのＩＤ４の次のコードＩＤであるＩＤ５とした検索の流れである。図７Ｂの（ａ）に示す流れに続いて、７１２ｂのＩＤ５から７１３ｂへの矢印７３４ａで示すように、ＩＤ５の指すＩＤ関係表３１０の次コードＩＤであるＩＤ６がステップＳ６２２で取り出される。【０１０４】
一方、７１１ｂのコードＢから任意コード？への矢印７３１ａに示すように、ステップＳ６６４で次のコード位置のコードが処理対象となり、ステップＳ６６５で任意コード？が取り出される。次にステップＳ６６６で、ステップＳ６６５で取り出された検索コードが任意コードであるかの判定が行わる。【０１０５】
今の例では任意コードであるので、７１１ｂの任意コード？から７１３ｂのＩＤ５の指すＩＤ関係表３１０の次コードＩＤであるＩＤ６への点線の矢印７３３ｂで示すように、ＩＤ６についてのコードＩＤ範囲の照合処理は省略される。
そして、７１３ｂ内の矢印７３４ｂで示すように、ＩＤ６の指すＩＤ関係表３１０の次コードＩＤであるＩＤ３がステップＳ６２２で取り出される。【０１０６】
一方、７１１ｂの任意コード？からコードＡへの矢印７３１ｂに示すように、ステップＳ６６４で次のコード位置のコードが処理対象となり、ステップＳ６６５でコードＡが取り出される。７１２ｂへの矢印７３３ｃで示すように、コードＡの指すコード別ＩＤ範囲表３０９の先頭コードＩＤであるＩＤ１と末尾コードＩＤであるＩＤ３がコードＩＤ範囲として取り出される。【０１０７】
そして、７１３ｂの、ＩＤ６の指すＩＤ関係表３１０の次コードＩＤであるＩＤ３と７１２ｂの、コードＡの指すコード別ＩＤ範囲表３０９のコードＩＤ範囲の間の双方向の点線の矢印７３５ｃで示すように、ステップＳ６６８においてＩＤ６の指すＩＤ関係表３１０の次コードＩＤであるＩＤ３がコードＡの指すコード別ＩＤ範囲表３０９のコードＩＤ範囲内であることが判定される。そこでステップＳ６６９で、矢印７３８ａで示すように、符号７１４ｂで示す検索結果コード位置に、検索開始コードＩＤであるＩＤ５の指すＩＤ関係表３１０のコード位置Ｐ５を設定する。【０１０８】
以上の処理により、検索対象コード列１０ａを検索コード列Ｂ？Ａで検索すると、検索結果として、検索コード列でヒットした検索対象コード列における検索コード列の先頭コードと同一種別のコードのコード位置であるＰ２とＰ５が得られる。
図３Ａの（ａ）に示すように、コード位置Ｐ２を先頭コードとする３コードのコード列はＢＥＡであり、コード位置Ｐ５を先頭コードとする３コードのコード列はＢＣＡである。【０１０９】
以上本発明を実施するための最良の形態について詳細に説明したが、本発明の実施の形態はそれに限ることなく種々の変形が可能であることは当業者に明らかである。
また、本発明のコード列装置が、コード別ＩＤ範囲表とＩＤ関係表を格納する記憶手段と図６Ａ〜図６Ｄに示した処理をコンピュータに実行させるプログラムによりコンピュータ上に構築可能なことは明らかである。【０１１０】
さらに、図５Ａ〜図５Ｃに示したコード列検索のための索引データを作成する処理とその均等物をコンピュータに実行させるプログラムにより、本発明の索引データ作成方法が実現可能であることも明らかである。そして、それらのプログラムにより、本発明の索引データを作成する手段等がコンピュータ上に実現される。
したがって、上記プログラム、及びプログラムを記録したコンピュータ読み取り可能な記録媒体は、本発明の実施の形態に含まれる。さらに、本発明のコード列検索のための索引データのデータ構造及びそのデータ構造を有する索引データを記録したコンピュータ読み取り可能な記録媒体も、本発明の実施の形態に含まれる。
以上詳細に説明した本発明が提供する新しい索引データ構造であるコード別ＩＤ範囲表とＩＤ関係表を採用することにより、索引データ作成の負荷を軽減すると共に、効率的にコード列検索を行うことが可能となる。
【図１】
2010035366.tif 000003
【図２Ａ】
2010035366.tif 000004
【図２Ｂ】
2010035366.tif 000005
【図２Ｃ】
2010035366.tif 000006
【図３Ａ】
2010035366.tif 000007
【図３Ｂ】
2010035366.tif 000008
【図４】
2010035366.tif 000009
【図５Ａ】
2010035366.tif 000010
【図５Ｂ】
2010035366.tif 000011
【図５Ｃ】
2010035366.tif 000012
【図６Ａ】
2010035366.tif 000013
【図６Ｂ】
2010035366.tif 000014
【図６Ｃ】
2010035366.tif 000015
【図６Ｄ】
2010035366.tif 000016
【図７Ａ】
2010035366.tif 000017
【図７Ｂ】
2010035366.tif 000018
【手続補正書】
【提出日】平成21年9月28日(2009.9.28)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】請求項１７
【補正方法】変更
【補正の内容】
【請求項１７】
検索対象である検索対象コード列を検索コード列により検索するコード列検索のためのデータ構造において、
前記検索対象コード列に位置する全ての各コードを一意に識別するコードＩＤの範囲であるコードＩＤ範囲を同一種別のコード毎に格納したコード別ＩＤ範囲表と、
前記コードＩＤに対応して、前記検索対象コード列において該コードＩＤに係るコードの次に位置するコードのコードＩＤである次コードＩＤを格納したＩＤ関係表と
を備え、
検索実行部と、前記コード別ＩＤ範囲表及びＩＤ関係表を記憶する記憶部とを備えたコード列検索装置が、
前記検索実行部により、
前記検索コード列を構成する先頭のコードからコード毎に、該コードの種別のコードＩＤ範囲を前記コード別ＩＤ範囲表から順次読み出し、
前記コード別ＩＤ範囲表から読み出された前記検索コード列の先頭のコードの種別のコードＩＤ範囲に含まれるコードＩＤに対応して格納された前記次コードＩＤを前記ＩＤ関係表から読み出し、以後、読み出された次コードＩＤに対応して格納された次コードＩＤを順次前記ＩＤ関係表から読み出し、
前記ＩＤ関係表から読み出された次コードＩＤが前記コード別ＩＤ範囲読出表から読み出されたコードＩＤの範囲に含まれるか照合することにより、
前記検索対象コード列の前記検索コード列による検索の実行を可能とする
ことを特徴とするコード列検索のためのデータ構造。
【国際調査報告】
2010035366.tif 000019
2010035366.tif 000020
2010035366.tif 000021
2010035366.tif 000022