JPH1115836A - 文字列探索用テーブル、その作成方法及び文字列探索方法 - Google Patents

Abstract

(57)【要約】 【課題】 ハッシュ法よりも演算時間が少なく高速な文
字列探索方法を提供する。 【解決手段】 入力されうる全ての文字を行、文字列探
索状況を示す状態値を列とする二次元の配列状で、その
各要素に、あらかじめ全ての予約語の探索状態に応じて
状態値を変更する処理へのアドレスもしくは予約語を探
索した場合の処理へのアドレスを格納した文字列探索用
テーブルを使い、一文字入力される毎に入力文字と状態
値に応じた文字列探索用テーブルの要素内に設定されて
いるアドレスへジャンプして上記の処理を実行し、再び
一文字入力に戻り、これを繰り返す。また、文字列探索
用テーブルには、登録するべき予約語をソートしてか
ら、それまでの登録状況を考慮しながら独自の方法によ
り状態数を拡張しながら１語つづ登録していく。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は文字列探索方法に関
し、特に文字列探索用テーブルを用いることにより高速
に文字列探索可能とした文字列探索方法に関する。ま
た、その文字列探索用テーブルと、その作成方法に関す
る。

【０００２】

【従来の技術】従来の一般的な文字列探索方法として、
逐次探索方法、２分木探索方法、ハッシュ探索方法があ
るが、各々の探索方法の平均探索回数は、与えられた文
字列がそれらの中のどれかに一致しているかどうかを探
索する予約語数をＮとおくと、逐次探索方法：（Ｎ＋
１）／２回、２分木探索方法：Ｌｏｇ₂ Ｎ回、ハッシュ
探索方法：１回（ただし条件による）となり、ハッシュ
探索方法を除き、予約語数が増加するにつれ探索回数も
増加するため高速に予約語の探索をすることが困難であ
った。そのため、従来技術ではハッシュ探索方法が最も
高速な探索方法であった。

【０００３】以下、各方法について詳述する。

【０００４】［従来の技術１］ 逐次探索方法 逐次探索方法とは、予めＮ個（Ｎ＞０）の予約語を文字
列の配列に格納しておき、入力された文字列に対し、こ
の配列の配列要素を１からＮまで増加させながら、順次
配列要素内に格納しておいた予約語を参照し、入力され
た文字列と参照した予約語間の文字列の比較を行うこと
で予約語の探索を行う方法である。探索方向が線形なた
め、線形探索方法とも呼ばれる。

【０００５】［従来の技術２］ ２分木探索方法 ２分木探索方法とは、予めＮ個（Ｎ＞０）の予約語を、
各ノード（節点）にデータと左右２個のポインタｌｅｆ
ｔ、ｒｉｇｈｔを持ち、左のポインタｌｅｆｔでつなが
る子孫のデータは自分より小さく、右のポインタｒｉｇ
ｈｔでつながる子孫のデータはすべて自分より大きいよ
うな２分木構造に格納しておき、入力文字列に対し、こ
の２分木構造の根のノードから探索を始め、入力文字列
と予約語の文字列の大小比較を行い、比較した結果が同
じであれば探索終了で、比較した結果が小さい場合はｌ
ｅｆｔポインタにつながっている子孫のノードに移動
し、比較した結果が大きい場合はｒｉｇｈｔポインタに
つながっている子孫のノードに移動し、再び先の入力文
字列と移動先のノードに格納してある予約語との比較を
行い文字列の探索を行う方法である。

【０００６】［従来の技術３］ ハッシュ探索方法 データｘを０≦ｈ（ｘ）＜ｎの範囲のなるべく一様に分
布する整数に変換する関数ｈ（ｘ）をハッシュ関数とい
い、このハッシュ関数を使って予約語を探索する方法を
ハッシュ探索方法という。簡単なハッシュ関数として
は、データｘを整数化して値Ｍで割り、その余りを関数
値とする。また通例、値Ｍは素数とする。

【０００７】ハッシュ関数の値を予約語の登録場所に結
びつける代表的な方法は、先の２分探索木をｎ本用意
し、データｘをｈ（ｘ）番の木に登録する方法と、ｎ個
の予約語を格納する配列を用意しておいて、値ｈ（ｘ）
をこの配列の要素として要素内に直接予約語を登録する
方法である。２分木を用いる方法はｎ個の予約語を格納
する配列を用意する方法に比較して検索時間がかかるた
め、以下はｎ個の予約語を格納する配列を使う方法につ
いて述べる。

【０００８】これは、予めこのハッシュ関数を用いて、
予約語を整数値化して、この整数値を予約語を格納する
配列の要素として予約語を格納しておき、入力された文
字列をハッシュ関数にかけて整数値を得て、この整数値
を予約語を格納しておいた配列の要素として文字列の探
索をする方法である。

【０００９】例として、図９にハッシュ探索方法におけ
る予約語テーブルの作成フロー、図１０にハッシュ関数
の処理フローおよび図１１にハッシュ探索方法の処理フ
ローを示す。

【００１０】ハッシュ探索方法の前処理として、９０１
にて予約語を格納する配列（ハッシュ表）を用意する。
次に９０２にてハッシュ関数を作成する（後述）。次に
９０３にて予約語を９０２のハッシュ関数に渡し、ハッ
シュ値を得て、このハッシュ値を９０１の配列の要素と
して、要素内に予約語を格納する。予約語の数だけ９０
２から９０３の処理を繰り返す。

【００１１】ここで９０２のハッシュ関数の内部処理に
ついて説明する。図１０に示すのは、入力された文字列
を整数化して値Ｍの素数で割り、その余りを関数値とす
る簡単なハッシュ関数９０２の内部処理の一例である。
まず、１００１にて内部変数のうちの１つであるハッシ
ュ値ｈの値を０で初期化する。同様に内部変数のうちの
１つである文字ポインタｓを入力された文字列の頭文字
を示すように初期化する。１００２にてポインタｓが示
す文字を得て、１００３にてこの文字が文字列の終わり
かどうか判断する。終わりであれば１００８に進み、終
わりでなければ１００４に進む。１００４にて変数ｈの
値を左に８ビットシフト（２５６倍化）して、さらに１
００５にて変数ｈにポインタｓの示す文字の文字コード
値を加算する。次に１００６にて変数ｈの値を先の９０
１にて用意したハッシュ表の要素数で割り、これの余り
値を再びｈに代入する。次に１００７にて文字ポインタ
ｓを１つ進めて、再び１００２からの処理を繰り返す。
この繰り返し処理にて入力された文字列をすべて読み終
えたら、１００８にて確定されたハッシュ値ｈを戻す。

【００１２】最後にハッシュ探索方法の処理フローを図
１１を参照して述べる。１１０１にて入力された文字列
を得て、１１０２で例えば入力文字列長が０であるかど
うかをみることにより文字列入力を終了するかどうかを
判断し、終了でなければ１１０３に進む。１１０３にて
入力された文字列を先の９０２のハッシュ関数に渡し、
これの戻り値を先の９０１の配列の要素とする。この要
素内に予約語が格納されているかどうかを調べる。１１
０４にて予約語があった場合、１１０５の予約語が見つ
かった場合の処理を実行し、再び１１０１の文字列の入
力に戻る。１１０３にて予約語が見つからなかった場合
でも、同様に１１０１に戻る。入力文字列が終わった場
合、１１０２にて文字列入力の終わりを認識して処理フ
ローを終える。

【００１３】

【発明が解決しようとする課題】ところで、ここでの第
１の問題点は、ハッシュ探索方法はあらかじめそれぞれ
の予約語を、ハッシュ関数にてなるべく一様に分布する
整数値に変換し、その整数値を予約語を格納する配列の
要素番号として各々の予約語を格納するが、登録を行う
予約語数および１予約語を構成する文字数によってはハ
ッシュ値が重複する場合がある。

【００１４】その理由は、一般に、計算機の内部表現に
おいて１文字をｎビットで表現している場合、１文字列
を構成する文字数をｍとおくと、文字列固有の整数値を
表現するにはｎ×ｍビットが必要となるが、ハッシュ値
もｎ×ｍビットで表現できなければ、その整数値を１対
１に写像することができないということである。例え
ば、３２ビットのＣＰＵのレジスタ長（３２ビット）で
扱えるハッシュ値をもとの文字列から写像しようとした
場合、文字がＡＳＣＩＩコード（１文字＝８ビット）で
あるとしても、４文字長の文字列しか１対１に写像でき
ないことになる。よって４文字を超える文字列のハッシ
ュ値を求める際にハッシュ値が重複する可能性がある。

【００１５】また、第２の問題点は、ハッシュ関数を複
数化（多段化）して必ずユニークな値を生成できるよう
にしてもハッシュ関数内の演算に要する時間が増えてし
まいユニークな値の生成に時間がかかることである。

【００１６】その理由は、現状のＣＰＵの中では演算命
令、特に乗除算命令は他の命令、例として分岐命令と比
較して時間がかかるものであるが、特に第１の問題点に
て述べたように、ハッシュ関数内にて、ハッシュ関数値
がＣＰＵの扱えるデータビット数を超えるような場合に
は必ず除算は必要となるということである。ハッシュ関
数を複数化すると乗除算命令を多数回使用しなければな
らなくなり、演算時間が増えてしまう。

【００１７】例としてμＰＤ７０２０８における各演算
時間は以下の通りである。

【００１８】 加算： １４クロック 減算： １４クロック 乗算： ３９クロック 除算： ３４クロック 比較： １６クロック ８ビット左シフト： １５クロック 分岐： １５クロック 以上、２つの問題が文字列探索の高速化を妨げている。

【００１９】そこで本発明は、高速な文字列探索方法を
提供することを目的とする。

【００２０】

【課題を解決するための手段】本発明による文字列探索
方法は、入力されうる全ての文字種類を行とし、文字列
探索処理状態を示す状態値種類を列とする２次元配列構
造のテーブルであり、各配列要素に、予め全ての予約語
の探索処理状態に応じて決められた状態値を変更する処
理手順へ分岐する分岐先アドレス、もしくは前記予約語
が探索された場合の処理手順へ分岐する分岐先アドレス
が格納されている文字列探索用テーブルを用いて、入力
された文字列が予め定められた予約語であるかどうか探
索する文字列探索方法において、状態値を０に初期化す
る第１の手順と、一文字ずつ入力文字を得る第２の手順
と、前記得られた入力文字を行、状態値を列として前記
文字列探索用テーブルを参照し、要素内に格納されてい
るアドレスに分岐する第３の手順と、分岐アドレスに従
い、状態値の変更処理もしくは予約語一致処理を実行
し、再び第２の手順に戻る第４の手順とを有することを
特徴とする。

【００２１】本発明による文字列探索用テーブル作成方
法は、入力されうる全ての文字種類を行とし、文字列探
索処理状態を示す状態値種類を列とする２次元配列構造
のテーブルであり、各配列要素に、予め全ての予約語の
探索処理状態に応じて決められた状態値を変更する処理
手順へ分岐する分岐先アドレス、もしくは前記予約語が
探索された場合の処理手順へ分岐する分岐先アドレスが
格納されている文字列探索用テーブルを作成する文字列
探索用テーブル作成方法において、入力されうる全ての
文字種類を前記文字列探索用テーブルの行方向の大きさ
とする第１の手順と、文字列探索状況の初期値を示す状
態値「０」と状態値を「０」に変更する処理部「処理
０」を用意する第２の手順と、前記文字列探索用テーブ
ルに登録する全ての予約語をソートする第３の手順と、
前記ソートされた全ての予約語から第１の予約語「予約
語１」を取り出し、「予約語１」を構成する１文字目か
らｎ文字目（ｎは予約語１の文字列長）までを各々状態
値「１」から状態値「ｎ」として用意する第４の手順
と、状態値「０」から状態値「ｎ」までを前記文字列探
索用テーブルの列方向の大きさとする第５の手順と、状
態値を「１」に変更する処理部「処理１」から、状態値
を「ｎ」に変更する処理部「処理ｎ」までのｎ個の処理
部を用意する第６の手順と、予約語「予約語１」を探索
した場合の処理「処理予約語１」を用意する第７の手順
と、前記文字列探索用テーブルにおいて、「予約語１」
の１文字目からｎ文字目までの各文字を行、状態値
「０」から状態値「ｎ−１」までを列とする各々の要素
内に「処理１」から「処理ｎ」への分岐アドレスを格納
する第８の手順と、前記文字列探索用テーブルにおい
て、デリミタ文字を行、状態値「ｎ」を列とする要素内
に処理「処理予約語１」へのアドレスを格納する第９の
手順と、前記ソート後の次の予約語「予約語ｍ」を取り
出し「予約語ｍ」の構成文字数Ａを求める第１０の手順
と、予約語「予約語ｍ」と予約語「予約語ｍ−１」を比
較し両予約語の１文字目からｎ文字目まで連続した同じ
文字の数Ｂを求める第１１の手順と、Ａ−Ｂの分だけ新
規に状態値「ｎ＋１」から状態値「ｎ＋Ａ−Ｂ」までを
用意する第１２の手順と、改めて状態値「０」から状態
値「ｎ＋Ａ−Ｂ」までを前記文字列検索用テーブルの列
方向の大きさとする第１３の手順と、状態値を「ｎ＋
１」に変更する処理部「処理ｎ＋１」から、状態値を
「ｎ＋Ａ−Ｂ」に変更する処理部「処理ｎ＋Ａ−Ｂ」ま
でＡ−Ｂ個の処理部を各々用意する第１４の手順と、予
約語「予約語ｍ」を探索した場合の処理「処理予約語
ｍ」を用意する第１５の手順と、前記文字列探索用テー
ブルにおいて、前記「予約語ｍ」のＢ＋１文字目を行、
状態値「Ｂ」を列とする要素内に処理部「処理ｎ＋１」
への分岐アドレスを格納する第１６の手順と、前記文字
列探索用テーブルにおいて、前記「予約語ｍ」のＢ＋２
文字目からＡ文字目までの各文字を行、前記状態値「ｎ
＋1 」から「ｎ＋Ａ−Ｂ−１」を列とする各々の要素内
に「処理ｎ＋２」から処理「ｎ＋Ａ−Ｂ」への分岐アド
レスを格納する第１７の手順と、前記文字列探索用テー
ブルにおいて、デリミタ文字を行、状態値「ｎ＋Ａ−
Ｂ」を列とする要素内に処理「処理予約語ｍ」へのアド
レスを格納する第１８の手順と、状態値「ｎ」に状態値
「ｎ＋Ａ−Ｂ」を代入する第１９の手順と、前記ソート
した残りの全ての予約語について、第１０の手順から第
１９の手順まで繰り返し、全ての予約語の登録が終わっ
た後、前記文字列探索用テーブルの要素内のうち、何も
格納していない要素内に処理部「処理０」への分岐アド
レスを格納する第２０の手順とを有することを特徴とす
る。

【００２２】本発明による記録媒体は、上記の文字列探
索方法をコンピュータに実行させるためのプログラムを
記録したことを特徴とする。

【００２３】また、本発明による記録媒体は、上記の文
字列探索用テーブル作成方法をコンピュータに実行させ
るためのプログラムを記録したことを特徴とする。

【００２４】更に、本発明による記録媒体は、入力され
た文字列が予め定められた予約語であるかどうか探索す
る文字列探索方法で用いる文字列探索用テーブルを記録
した記録媒体において、入力されうる全ての文字種類を
行とし、文字列探索処理状態を示す状態値種類を列とす
る２次元配列構造のテーブルであり、各配列要素に、予
め全ての予約語の探索処理状態に応じて決められた状態
値を変更する処理手順へ分岐する分岐先アドレス、もし
くは前記予約語が探索された場合の処理手順へ分岐する
分岐先アドレスが格納されている文字列探索用テーブル
を記録したことを特徴とする。

【００２５】

【発明の実施の形態】以下に示す順序で説明を進める。

【００２６】Ａ．文字列探索用テーブルの作成方法 Ｂ．文字列探索用テーブルを使用した文字列探索方法

【００２７】本実施形態では扱う文字をASCIIコード系
の文字とし、入力されうる文字は１６進表記で0x00から
0x7Fまでの１２８種の文字とする。入力されうる文字は
１２８種なので文字列探索用テーブルの文字要素数は１
２８個となる。また、文字列と文字列を区切る文字（こ
れをデリミタと定義する）を空白文字（文字コード0x2
0）とする。ここで予約語を以下のように定義する。

【００２８】 NEC XYZ NIMS NET まず、文字列探索処理状態の状態値「0」を用意して、
状態値を「0」に変更する処理部「処理0」を以下のよう
に定義する。

【００２９】

【表１】 次に予約語をソートする。これは昇順でも降順でもかま
わない。本例では昇順にソートする。ソート後は以下の
ような並びになる。

【００３０】 NEC NET NIMS XYZ まず初めの予約語NECは３文字から構成されているた
め、３つの新規状態値「1」、「2」、「3」を用意す
る。よって予約語NECを認識するための文字列探索用テ
ーブルは図４のように用意する。

【００３１】次にこれら３つの状態値に対応した状態値
を更新する処理部を３つ用意する。ここで３つの各処理
部を「処理1」、「処理2」、「処理3」と定義し、各処
理部へのアドレスが得られるようにラベル化しておく。
また予約語NECを探索した場合の処理部「処理NEC」も作
成する。

【００３２】これら各処理部を以下に示す。

【００３３】

【表２】 各処理内容中の「読み出し処理部」は後述のフロー説明
で述べる。また、「処理NEC」内の予約語NECを探索した
場合の処理は任意の処理である。

【００３４】次に予約語NECの１文字目「N」と状態値
「0」より図４の文字列探索用テーブルを参照して、状
態値が「0」で文字要素が「N」の要素内に「処理1」へ
の分岐アドレスを格納する。同様に２文字目の「E」と
状態値「1」より図４の文字列探索用テーブルを参照し
て、状態値が「1」で文字要素が「E」の要素内に「処理
2」への分岐アドレスを格納する。同様に３文字目の
「C」と状態値「2」より図４の文字列探索用テーブルを
参照して、状態値が「2」で文字要素が「C」の要素内に
「処理3」への分岐アドレスを格納する。最後にデリミ
タの「空白文字」と状態値「3」より図４の文字列探索
用テーブルを参照して、状態値が「3」で文字要素がデ
リミタの要素内に「処理NEC」への分岐アドレスを格納
する。以上で予約語NECを探索するための文字列探索用
テーブルは完成である。この結果得られた文字列探索用
テーブルを図５に示す。

【００３５】続いて２つ目以降の予約語を登録してい
く。２つ目以降の予約語を登録する場合、新規に状態値
を用意する必要があるかどうか、以下に述べる計算式に
従い判断する必要がある。

【００３６】これから登録する予約語を構成する文字数
をＡとおき、直前に登録した予約語とこれから登録する
予約語において、頭文字から任意文字目まで連続した同
じ文字の数をＢとおいた場合、Ａ−Ｂが新規に必要な状
態数である。新規状態値が必要な場合、必然的に文字列
探索用テーブルを状態値要素方向に拡張しなければなら
ない。

【００３７】本例では、第２に登録する予約語はNET
で、予約語NETは計３文字であるのでＡ＝３である。次
に直前に登録した予約語NECと今回登録する予約語NETに
おいて、頭文字から任意文字目まで同じ文字数を調べ
る。予約語NECと予約語NETでは、「N」、「E」が同じで
あり、計２文字が同じであるのでＢ＝２である。ゆえ
に、Ａ−Ｂ＝１となり、新規の状態値を１つ用意する必
要がある。よって新たに状態値「4」を用意し、文字列
探索用テーブルの状態値要素方向（列方向）の要素を状
態値「0」から状態値「4」までとする。また新たに状態
値を更新する処理「処理4」および予約語NETを探索した
場合の処理「処理NET」を設ける。この「処理4」と「処
理NET」を以下のように定義する。

【００３８】

【表３】 次に、予約語NETにおける３文字目（Ｂ＋１文字目）の
「T」と状態値「2」（状態値「Ｂ」）より文字列探索用
テーブルを参照し、状態値が「2」で文字要素が「T」の
要素内に処理部「処理4」への分岐アドレスを格納す
る。次にデリミタ文字と状態値「4」（状態値「ｎ＋Ａ
−Ｂ」、但しｎは１つ前の予約後の登録を終了した時点
での最高の状態値）より文字列探索用テーブルを参照
し、状態値が「4」で文字要素がデリミタの要素内に処
理「予約語NET」への分岐アドレスを格納する。この結
果得られた文字列探索用テーブルを図６に示す。

【００３９】同様に次の予約語NIMSについて考える。直
前に登録した予約語はNETである。これから登録する予
約語を構成する文字数Ａ＝４（文字）、直前に登録した
予約語とこれから登録する予約語において、頭文字から
任意文字目まで連続した同じ文字の数Ｂ＝１（文字）な
ので、Ａ−Ｂ＝３となり、新たに３つの状態値「5」、
「6」、「7」を設け、改めて文字列探索用テーブルの状
態値要素方向（列方向）の大きさを状態値「0」から状
態値「7」までの大きさとする。また状態値を各々
「5」、「6」、「7」に変更する処理部「処理5」、「処
理6」、「処理7」を設ける。また予約語NIMSを探索した
場合の処理部「処理NIMS」も設ける。これら各処理部を
以下に示す。

【００４０】

【表４】 次に予約語NIMSの２文字目「I」と状態値「1」（最初の
文字が「N」だと状態値は「1」になるので）より文字列
探索用テーブルを参照し、状態値が「1」で文字要素が
「I」の要素内に処理部「処理5」への分岐アドレスを格
納する。同様に予約語NIMSの３文字目から４文字目まで
と、状態値「5」、「6」より文字列探索用テーブルを参
照し、状態値が「5」で文字要素が「M」の要素内に処理
部「処理6」、状態値が「6」で文字要素が「S」の要素
内に「処理7」への分岐アドレスを格納する。最後にデ
リミタ文字と状態値「7」より文字列探索用テーブルを
参照し、状態値が「7」で文字要素がデリミタの要素内
に処理部「処理NIMS」への分岐アドレスを格納する。こ
の結果得られた文字列探索用テーブルを図７に示す。

【００４１】同様に最後の予約語XYZについて考える。
直前に登録した予約語はNIMSである。前回と同様にＡ、
Ｂを求めると、Ａ＝３文字、Ｂ＝０文字なので、Ａ−Ｂ
＝３となり、新たに３つの状態値「8」、「9」、「10」
を設け、改めて状態値「0」から状態値「10」までを文
字列探索用テーブルの列方向の大きさとする。また各々
状態値を「8」、「9」、「10」に変更する各処理部「処
理8」、「処理9」、「処理10」を設ける。また予約語XY
Zを探索した場合の処理「処理XYZ」も設ける。これら処
理部を以下に示す。

【００４２】

【表５】 次に予約語XYZの１文字目「X」と状態値「0」より文字
列探索用テーブルを参照し、状態値が「0」で文字要素
が「X」の要素内に処理部「処理8」への分岐アドレスを
格納する。同様に予約語XYZの２文字目「Y」から３文字
目「X」と、状態値「8」、「9」より文字列探索用テー
ブルを各々参照して、状態値が「8」で文字要素が「Y」
の要素内に処理部「処理9」、状態値が「9」で文字要素
が「Z」の要素内に「処理10」への分岐アドレスを格納
する。次にデリミタの文字と状態値「10」より文字列探
索用テーブルを参照し、要素内に「処理XYZ」への分岐
アドレスを格納する。この結果得られた文字列探索用テ
ーブルを図８に示す。

【００４３】最後に図８の文字列探索用テーブルにおい
て、予約語NECおよびNETおよびNIMSおよびXYZを登録す
る際に使用しなかった他の全ての要素内に「処理0」へ
の分岐アドレスを格納する。これで予約語NEC、NET、NI
MS、XYZに対する文字列探索用テーブルの設定は終わり
である。

【００４４】図２を参照して一般化した文字列探索用テ
ーブルの作成手順を説明する。

【００４５】第１の手順（２０１）において、入力され
うる全ての文字種類を文字列探索用テーブルの行方向の
大きさとする。

【００４６】第２の手順（２０２）において、初期状態
値「0」を用意して、状態値を初期状態値にする初期化
処理部「処理0」を用意する。

【００４７】第３の手順（２０３）において、登録する
全ての予約語をソート基準に従って、昇順又は降順にソ
ートする。

【００４８】第４の手順（２０４）において、第１の予
約語に対応した状態値を用意する。この状態値の数
「n」は第１の予約語の文字列長である。通常は状態値
は１から順に用意する。

【００４９】第５の手順（２０５）において、文字列探
索用テーブルの列方向の大きさを決定する。列は「0」
から「n」まであり、列方向の大きさは、第１の予約語
の文字列長＋１である。

【００５０】第６の手順（２０６）において、状態値変
更（更新）処理部を用意する。上記の例では、状態値を
「1」に変更（更新）する処理部「処理1」から状態値を
「3(=n)」に変更する処理部「処理3」までを用意する。

【００５１】第７の手順（２０７）において、第１の予
約語を探索した場合の処理部を用意する。上記の例で
は、「処理NEC」を用意する。

【００５２】第８の手順（２０８）において、文字列探
索用テーブルに各状態変更処理部への分岐アドレスを格
納する。上記の例では、例えば、状態値が「0」で文字
要素が「N」の要素内に「処理1」への分岐アドレスを格
納する。

【００５３】第９の手順（２０９）において、文字列探
索用テーブルのデリミタ文字を行、状態値「n」を列と
する要素内に第１の予約語を探索した場合の処理部への
分岐アドレスを格納する。上記の例では、状態値が
「3」で文字要素がデリミタの要素内に「処理NEC」への
分岐アドレス格納する。

【００５４】次の予約語がある場合に進む第１０の手順
（２１１）において、これから予約しようとする第ｍ
（ｍは２以上の整数）の予約語よりこの予約語の構成文
字数Ａを求める。

【００５５】第１１の手順（２１２）において、第ｍの
予約語と第（ｍ−１）の予約語の頭文字から連続して一
致する文字の数Ｂを求める。

【００５６】第１２の手順（２１３）において、Ａ−Ｂ
個の状態値「n+1」から状態値「n+A-B」までを用意する
新規状態を用意する。

【００５７】第１３の手順（２１４）において、文字列
探索用テーブルの列方向の大きさをＡ−Ｂだけ拡大し
て、範囲を状態値「0」から状態値「n+A-B」にして更新
する。

【００５８】第１４の手順（２１５）において、状態値
を「n+1」に変更する処理部「処理n+1」から、状態値を
「n+A-B」に変更する処理部「処理n+A-B」までＡ−Ｂ個
の処理部を各々用意する上記の例では、例えば「NIMS」
を扱っているときに、状態値を「5」に更新する処理部
「処理5」などを用意する。

【００５９】第１５の手順（２１６）において、第ｍの
予約語を探索した場合の処理部を用意する。上記の例で
は、例えば、「処理NIMS」を用意する。

【００６０】第１６の手順（２１７）において、文字列
探索用テーブルにおいて、「予約語m」のＢ＋１文字目
を行、状態値「B」を列とする要素内に処理部「処理n+
1」への分岐アドレスを格納する。上記の例では、例え
ば「NIMS」を扱っているときに、「NIMS」の２文字目で
ある「I」を行、状態値「1」を列とする要素内に「処理
5」への分岐アドレスを格納する。

【００６１】第１７の手順（２１８）において、文字列
探索用テーブルにおいて、「予約語m」のＢ＋２文字目
からＡ文字目までの各文字を行、前記状態値「n+1」か
ら「n+A-B-1」を列とする各々の要素内に「処理n+2」か
ら処理「n+A-B」への分岐アドレスを格納する。上記の
例では、例えば「NIMS」を扱っているときに、「NIMS」
の３文字目から４文字目までの各文字を行、状態値「5
(=4+1)」から状態値「6(=4+4-1-1)」を列とする各々の
要素内に「処理6」から「処理7」への分岐アドレスを格
納する。

【００６２】第１８の手順（２１９）において、文字列
探索用テーブルにおいて、デリミタ文字を行、状態値
「n+A-B」を列とする要素内に処理「処理予約語m」への
アドレスを格納する。上記の例では、例えば「NIMS」を
扱っているときに、デリミタ文字を行、状態値「7(=4+4
-1)」を列とする要素内に「処理NIMS」へのアドレスを
格納する。

【００６３】第１９の手順（２２０）において、状態値
「n」に状態値「n+A-B」を代入する。上記の例では、例
えば「NET」を扱っているときに状態値「3」に状態値
「4(=3+3-2)」を代入する。

【００６４】次の予約語がない場合にすすむ第２０の手
順（２２１）において、文字列探索用テーブルの要素内
のうち、何も格納していない要素内に処理部「処理０」
への分岐アドレスを格納する。

【００６５】次に本実施形態の文字列探索の処理フロー
について述べる。図３が本実施形態における文字列探索
方法の処理フローである。まず３００にて状態値を
「0」に初期化する。ここで例として文字列NEC、次いで
デリミタの空白文字が入力される場合を考える。はじめ
に読み出し処理部３０１にて文字「N」が読み込まれ
る。

【００６６】次に３０２にて図６に示す文字列探索用テ
ーブル内の文字要素が「N」で状態値要素が「0」の位置
に格納されている「処理1」のアドレスを得て、３０３
の中の一つの処理「処理1」にジャンプし、「処理1」に
おいて状態値を「1」に更新して、再び３０１の読み出
し処理部へ戻る。同様に、３０２にて図６に示す文字列
探索用テーブル内の文字要素が次の入力文字「E」で状
態値要素が「1」の位置に格納されている「処理2」のア
ドレスを得て、３０２の「処理2」へジャンプし、「処
理2」において状態値を「2」に更新して再び３０１の読
み出し処理部へ戻る。

【００６７】更に、３０２にて図６に示す文字列探索用
テーブル内の文字要素が次の入力文字「C」で状態値要
素が「2」の位置に格納されている「処理3」のアドレス
を得て、３０３の「処理3」へジャンプし、「処理3」に
おいて状態値を「3」に更新して再び３０１の読み出し
処理部へ戻る。

【００６８】更に、３０２にて図６に示す文字列探索用
テーブル内の文字要素が次の入力文字「空白文字」で状
態値要素が「3」の位置に格納されている「処理NEC」の
アドレスを得て、３０３の「処理NEC」へジャンプす
る。「処理NEC」にジャンプした時点で予約語NECを探索
したことになる。

【００６９】次に、「処理NEC」内の予約語NECを探索し
た場合の処理を実行し、状態値を「0」に更新して、再
び３０１の文字読み出し部に戻り、次の文字列の探索に
備える。

【００７０】また別の例として予約語に含まれない文字
列「ABC」が入力された場合を考える。プログラムの初
期状態において、状態値は「0」である。はじめに３０
１の読み出し処理部にて文字「A」が読み込まれる。次
に３０２にて図６の示す文字列探索用テーブル内の文字
要素が「A」で状態値要素が「0」の位置に格納されてい
るアドレス「処理0」を得て、３０３の「処理0」にジャ
ンプし、「処理0」において状態値を「0」に更新して、
再び読み出し処理部へ戻る。すなわち状態値は「0」か
ら変わらない。以降の入力文字「B」、「C」に関しても
同様であるため、入力された文字列ＡＢＣは無視される
のである。

【００７１】文字列探索の処理フローを一般化すると図
１に示すようになる。図１において、符号１００から符
号１０２で示す処理ブロックは、符号３００から符号３
０２で示す処理ブロックと同一である。「処理M+1」
（符号１０５）は、「処理NEC」、「処理NET」、「処理
NIMS」、「処理XYZ」に対応する。「処理N」は、「処理
10」に対応する。

【００７２】なお、本実施形態においては、扱う文字を
ASCIIコード系のものとしたが、文字はこの体系のもの
に限定されるものではなく、ＪＩＳ漢字、UNICODEな
ど、どのような体系の文字にも本発明を適用することが
できる。

【００７３】また、本実施形態における文字列探索方
法、及び文字列探索用テーブル作成方法は、コンピュー
タが実行可能なプログラムにより実現され、これはコン
ピュータで読み取り可能な記録媒体に記録される。

【００７４】また、本実施形態における文字列探索用テ
ーブルはコンピュータで読み取り可能な記録媒体に記録
さる。この文字列探索用テーブルは、コンピュータが本
実施形態による作成方法のプログラムで作成し、記録媒
体に記録し、コンピュータが本実施形態による探索方法
のプログラムを実行する際に記録媒体より読み取り、使
用する。

【００７５】

【発明の効果】以上説明したように本発明によれば、ハ
ッシュ探索方法と比較して高速に文字列の探索ができる
ことである。

【００７６】その理由は、本発明による文字列探索方法
は入力文字およびその時の状態値を文字列探索用テーブ
ルの配列の要素の位置情報として、状態要素値と文字要
素値で指定される位置にある要素内として格納されてい
る分岐先処理のアドレスを参照し分岐し、分岐先の処理
を繰り返すことで文字列の認識を行うため、ＣＰＵ演算
の中で時間がかかる乗算や除算などの演算命令を使用し
ないためである。また入力された文字列は一回の探索に
よって、予約語かどうか判断できるため高速に文字列の
探索ができる。

【００７７】ここで目安として、入力された文字列を整
数化して値Ｍの素数で割り、その余りを関数値とする簡
単な図１０に示すハッシュ検索方法と本発明による文字
列探索方法を比較して、本発明による文字列探索方法が
どの位高速になるか述べる。

【００７８】ＮＥＣのμＰＤ７０２０８ＣＰＵを例に取
ると、各演算に必要なクロック数は以下の通りである。

【００７９】 加算： １４クロック 減算： １４クロック 乗算： ３９クロック 除算： ３４クロック 比較： １６クロック ８ビット左シフト： １５クロック 分岐： １５クロック これらより、ハッシュ探索方法に必要なＣＰＵ時間と当
方法の探索方法に必要なＣＰＵ時間を比較すると以下の
ようになる。

【００８０】 ハッシュ探索方法におけるＣＰＵ時間＝７７クロック×文字数 （左８ビットシフト演算 １５クロック×１回＝１５クロック） （加算 １４クロック×２回＝２８クロック） （除算 ３４クロック×１回＝３４クロック） 本発明による探索方法におけるＣＰＵ時間＝３０クロック×文字数 （分岐 １５クロック×２回＝３０クロック） よって本発明による探索方法を使用するとＣＰＵ時間が
およそ１／２に短縮され高速に文字列の探索を行うこと
が可能となる。また、ハッシュ関数が複数になり演算が
増えれば増えるほど両者の差が開く。

【図面の簡単な説明】

【図１】本発明による文字列探索用テーブルを用いた文
字列探索方法のフローチャートである。

【図２】本発明による文字列探索用テーブルを作成する
方法のフローチャートである。

【図３】本発明の実施形態における文字列探索用テーブ
ルを用いた文字列探索方法のフローチャートである。

【図４】本発明の実施形態における予約語「NEC」を探
索するために必要になる文字列探索用テーブルのテーブ
ルサイズを示す図である。

【図５】本発明の実施形態における予約語「NEC」を探
索するための文字列探索用テーブルを示す図である。

【図６】本発明の実施形態における予約語「NEC」及び
「NET」を探索するための文字列探索用テーブルを示す
図である。

【図７】本発明の実施形態における予約語「NEC」、「N
ET」及び「NIMS」を探索するための文字列探索用テーブ
ルを示す図である。

【図８】本発明の実施形態における予約語「NEC」、「N
ET」、「NIMS」及び「XYZ」を探索するための文字列探
索用テーブルを示す図である。

【図９】ハッシュ探索方法におけるハッシュ表作成方法
のフローチャートである。

【図１０】ハッシュ関数内部の処理フローチャートであ
る。

【図１１】ハッシュ探索方法のフローチャートである。

【符号の説明】

１００ 初期化 １０１ 読み出し処理部 １０２ ジャンプ １０３ 処理０ １０４ 処理１ １０５ 処理Ｍ＋１ １０６ 処理Ｎ

Claims (5)

【特許請求の範囲】
1. 【請求項１】 入力されうる全ての文字種類を行とし、
   文字列探索処理状態を示す状態値種類を列とする２次元
   配列構造のテーブルであり、各配列要素に、予め全ての
   予約語の探索処理状態に応じて決められた状態値を変更
   する処理手順へ分岐する分岐先アドレス、もしくは前記
   予約語が探索された場合の処理手順へ分岐する分岐先ア
   ドレスが格納されている文字列探索用テーブルを用い
   て、入力された文字列が予め定められた予約語であるか
   どうか探索する文字列探索方法において、 状態値を０に初期化する第１の手順と、 一文字ずつ入力文字を得る第２の手順と、 前記得られた入力文字を行、状態値を列として前記文字
   列探索用テーブルを参照し、要素内に格納されているア
   ドレスに分岐する第３の手順と、 分岐アドレスに従い、状態値の変更処理もしくは予約語
   一致処理を実行し、再び第２の手順に戻る第４の手順と
   を有することを特徴とする文字列探索方法。
2. 【請求項２】 入力されうる全ての文字種類を行とし、
   文字列探索処理状態を示す状態値種類を列とする２次元
   配列構造のテーブルであり、各配列要素に、予め全ての
   予約語の探索処理状態に応じて決められた状態値を変更
   する処理手順へ分岐する分岐先アドレス、もしくは前記
   予約語が探索された場合の処理手順へ分岐する分岐先ア
   ドレスが格納されている文字列探索用テーブルを作成す
   る文字列探索用テーブル作成方法において、 入力されうる全ての文字種類を前記文字列探索用テーブ
   ルの行方向の大きさとする第１の手順と、 文字列探索状況の初期値を示す状態値「０」と状態値を
   「０」に変更する処理部「処理０」を用意する第２の手
   順と、 前記文字列探索用テーブルに登録する全ての予約語をソ
   ートする第３の手順と、 前記ソートされた全ての予約語から第１の予約語「予約
   語１」を取り出し、「予約語１」を構成する１文字目か
   らｎ文字目（ｎは予約語１の文字列長）までを各々状態
   値「１」から状態値「ｎ」として用意する第４の手順
   と、 状態値「０」から状態値「ｎ」までを前記文字列探索用
   テーブルの列方向の大きさとする第５の手順と、 状態値を「１」に変更する処理部「処理１」から、状態
   値を「ｎ」に変更する処理部「処理ｎ」までのｎ個の処
   理部を用意する第６の手順と、 予約語「予約語１」を探索した場合の処理「処理予約語
   １」を用意する第７の手順と、 前記文字列探索用テーブルにおいて、「予約語１」の１
   文字目からｎ文字目までの各文字を行、状態値「０」か
   ら状態値「ｎ−１」までを列とする各々の要素内に「処
   理１」から「処理ｎ」への分岐アドレスを格納する第８
   の手順と、 前記文字列探索用テーブルにおいて、デリミタ文字を
   行、状態値「ｎ」を列とする要素内に処理「処理予約語
   １」へのアドレスを格納する第９の手順と、 前記ソート後の次の予約語「予約語ｍ」を取り出し「予
   約語ｍ」の構成文字数Ａを求める第１０の手順と、 予約語「予約語ｍ」と予約語「予約語ｍ−１」を比較し
   両予約語の１文字目からｎ文字目まで連続した同じ文字
   の数Ｂを求める第１１の手順と、 Ａ−Ｂの分だけ新規に状態値「ｎ＋１」から状態値「ｎ
   ＋Ａ−Ｂ」までを用意する第１２の手順と、 改めて状態値「０」から状態値「ｎ＋Ａ−Ｂ」までを前
   記文字列検索用テーブルの列方向の大きさとする第１３
   の手順と、 状態値を「ｎ＋１」に変更する処理部「処理ｎ＋１」か
   ら、状態値を「ｎ＋Ａ−Ｂ」に変更する処理部「処理ｎ
   ＋Ａ−Ｂ」までＡ−Ｂ個の処理部を各々用意する第１４
   の手順と、 予約語「予約語ｍ」を探索した場合の処理「処理予約語
   ｍ」を用意する第１５の手順と、 前記文字列探索用テーブルにおいて、前記「予約語ｍ」
   のＢ＋１文字目を行、状態値「Ｂ」を列とする要素内に
   処理部「処理ｎ＋１」への分岐アドレスを格納する第１
   ６の手順と、 前記文字列探索用テーブルにおいて、前記「予約語ｍ」
   のＢ＋２文字目からＡ文字目までの各文字を行、前記状
   態値「ｎ＋1 」から「ｎ＋Ａ−Ｂ−１」を列とする各々
   の要素内に「処理ｎ＋２」から処理「ｎ＋Ａ−Ｂ」への
   分岐アドレスを格納する第１７の手順と、 前記文字列探索用テーブルにおいて、デリミタ文字を
   行、状態値「ｎ＋Ａ−Ｂ」を列とする要素内に処理「処
   理予約語ｍ」へのアドレスを格納する第１８の手順と、 状態値「ｎ」に状態値「ｎ＋Ａ−Ｂ」を代入する第１９
   の手順と、 前記ソートした残りの全ての予約語について、第１０の
   手順から第１９の手順まで繰り返し、全ての予約語の登
   録が終わった後、前記文字列探索用テーブルの要素内の
   うち、何も格納していない要素内に処理部「処理０」へ
   の分岐アドレスを格納する第２０の手順とを有すること
   を特徴とする文字列探索用テーブル作成方法。
3. 【請求項３】 請求項１に記載の文字列探索方法をコン
   ピュータに実行させるためのプログラムを記録したこと
   を特徴とする記録媒体。
4. 【請求項４】 請求項２に記載の文字列探索用テーブル
   作成方法をコンピュータに実行させるためのプログラム
   を記録したことを特徴とする記録媒体。
5. 【請求項５】 入力された文字列が予め定められた予約
   語であるかどうか探索する文字列探索方法で用いる文字
   列探索用テーブルを記録した記録媒体において、 入力されうる全ての文字種類を行とし、文字列探索処理
   状態を示す状態値種類を列とする２次元配列構造のテー
   ブルであり、 各配列要素に、予め全ての予約語の探索処理状態に応じ
   て決められた状態値を変更する処理手順へ分岐する分岐
   先アドレス、もしくは前記予約語が探索された場合の処
   理手順へ分岐する分岐先アドレスが格納されている文字
   列探索用テーブルを記録したことを特徴とする記録媒
   体。