マルチバイト文字セット用正規表現コンパイラ構成方法及びプログラム

マルチバイト文字セットは、２５６文字を超える文字集合を扱うために用いられる文字符号法であり、表現する文字によって符号長が異なるという特徴を持つ。マルチバイト文字セットの代表的なものに、Ｓｈｉｆｔ＿ＪＩＳやＥＵＣ−ＪＰやＵＴＦ−８がある。

マルチバイト文字セットは、符号化し得る文字数がシングルバイト文字セットの２５６文字に比較して多い。その大きさはそれぞれのマルチバイト文字セットによってまちまちであるが、約１万字を表現し得るもの（Ｓｈｉｆｔ＿ＪＩＳ）、約２万字を表現し得るもの（ＥＵＣ−ＪＰ）、約４２億字を表現し得るもの（ＵＴＦ−８）と、シングルバイト文字セットとの差は甚大である。この文字空間の大きさは、実用上のメリットをもたらすと共に、検索速度の低下というデメリットも同時にもたらしてきた。

正規表現は、プログラミング言語処理及び文字列検索に広範に用いられる文字列集合の表記法である。正規表現は、プログラミング言語処理の応用においては、コンパイラの字句解析部において、字句の文字の並びを指定するために用いられる。また、正規表現は、全文テキスト検索の応用において、一般的な表記法を提供し、検索対象となる複数文字列の指定や、複雑なパターンの指定のために用いられる。

正規表現エンジンとは、正規表現を変換して有限状態機械を構築する正規表現コンパイラと、得られた有限状態機械を用いて入力文字列との文字列照合を行うプログラムの組である。正規表現エンジンには、これを構成する正規表現コンパイラが非決定性有限状態機械（ＮＦＡ）を利用するＮＦＡエンジンと、決定性有限状態機械（ＤＦＡ）を利用するＤＦＡエンジンがある（非特許文献１）。

エンジン

燃焼室で燃料を燃焼させて熱エネルギを発生させ、その熱エネルギを運動エネルギに変換して出力軸から出力する装置

文字列検索及びパターン検索に、正規表現からコンパイルされたＤＦＡ表引きを利用すると、パターンの複雑さに依存しない速度が得られるため、極めて高速な動作がもたらされることに加えて、最大一致文字列を検出できるため、均質で統制のとれた結果が得られる（非特許文献３）。

既存技術の正規表現エンジンとしては、シングルバイト文字セット用のものに高速なＤＦＡ表引きに依るものが既に得られているが（非特許文献２）、マルチバイト文字セット用には低速なＮＦＡ構造のバックトラッキングに頼るしかないのが実情であった。

エンジン

燃焼室で燃料を燃焼させて熱エネルギを発生させ、その熱エネルギを運動エネルギに変換して出力軸から出力する装置

いっぽう、文字列検索や字句解析の多国語対応に目を転じると、高度な文字列処理のために、文字コードの変換を伴う例（特許文献１）があるものの、マルチバイト文字セットによりエンコードされた文字列をそのまま扱う仕組みは希少であった。また、テキストデータの変換を伴うもの（特許文献２）があるものの、テキストデータを保持したままで検索を行えるシステムは少なかった。 特開２００４−２５８７５９公報特開２００４−２２０２４６公報Ｊｅｆｆｒｅｙ Ｅ．Ｆ．Ｆｒｉｅｄｌ著，田和 勝 訳 「『詳説 正規表現 第２版」オライリー・ジャパン２００３年発行Ａ．Ｖ．エイホ，Ｒ．セシィ，Ｊ．Ｄ．ウルマン共著，原田 賢一 訳， 「コンパイラＩ」サイエンス社１９９０年発行守屋 悦朗「形式言語とオートマトン」サイエンス社２００１年発行

正規表現コンパイラと文字列照合機からなる正規表現エンジンには、低速なＮＦＡエンジンと、高速なＤＦＡエンジンの２種類が存在する。シングルバイト文字セット用には高速なＤＦＡエンジンが存在するが、マルチバイト文字セット用には低速なＮＦＡエンジンが実存するのみであった。 本発明は、マルチバイト文字セット用に書かれた正規表現を、ＤＦＡへの変換が容易な構造に変換する方法を提供し、結果としてマルチバイト文字セット用ＤＦＡ正規表現エンジンを得るものである。 本発明は、正規表現中に現れる任意文字を表す記号に対しては、バイト長毎に分岐するＮＦＡ構造を割り当て、正規表現中に現れる文字クラスを表す記号列に対しては、バイト毎の決定性分解を実現するＮＦＡ構造を割り当てる。この翻訳規則と従来の方法をあわせて適用し、正規表現に対応するＮＦＡ構造を得、ＮＦＡ構造から既知の手続きによってＤＦＡ遷移表を得る。得られたＤＦＡ遷移表は後段階のＤＦＡ用文字列照合機と接続される。

エンジン

燃焼室で燃料を燃焼させて熱エネルギを発生させ、その熱エネルギを運動エネルギに変換して出力軸から出力する装置

本発明は上記の問題を鑑みてなされたもので、正規表現をマルチバイト文字セットに対応させ、しかも効率の低下を招かない正規表現エンジン構成方法およびプログラムを提供するものである。

エンジン

燃焼室で燃料を燃焼させて熱エネルギを発生させ、その熱エネルギを運動エネルギに変換して出力軸から出力する装置

この発明により、従来のシングルバイト文字セット用に書かれた正規表現エンジンを、マルチバイト文字セット用に改良することが可能になる。改良された正規表現エンジンは、決定性有限状態機械（ＤＦＡ）による高速性を保持しているため、正規表現を使ったプログラムのマルチバイト化及び高速化が可能になる。