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