2010/08/15

文字クラスのマッチ

正規表現の[]でくくった文字列クラス内の文字の並びがマッチ速度に 影響を与えるかどうか、という話題。

実装依存です - ときどきの雑記帖

対象となるコードが1バイト(つーかオクテット?)の範囲に収まるくらいなら、 ビットベクトルを使うのが多分常道で、その場合はどう書いても実行結果は同じのはず。 マルチバイト文字やらワイド文字やらUnicode なんかが対象に入ってくると これはもう実装次第としかいいようがないわけで。 仮に対象を Unicode としてその大きさがほぼ100万文字というパターンを考えると、 ビットベクトルでこれを収めるには…と。 まあイマドキの環境だったらどうってことないのかなあそれでも。

GaucheではASCIIの範囲はビットベクタ、それ以降は連続する文字の「範囲」を treemapで管理してる。各範囲の下限をキー、上限を値として。 なので順番は関係なく、ルックアップ速度は「範囲」の個数nに対してO(log n)。

まあ、treemapは内部的に既に持ってたから使っただけで、 単純に範囲をソートして配列で持っておくだけでもバイナリサーチかけられるので、 そうしない手はないと思う。 なので「順序で影響が出るような実装を使うメリットが思い当たらない」かなあ。

範囲で管理するのは、不連続な小領域が大量にある場合にえらく不利になる。 実用上たぶんそんなことは滅多に無さそうだとは思うけれど、最悪値を 良くしたいなら、範囲の数が閾値を越えたらビットベクタに切り替えるって手はある。 全部ビットベクタにしなくても、ある深さまでは範囲で、その下は その範囲だけのビットマップ、というふうにもできるだろう。

話はずれるんだけど、Gaucheは文字列をマルチバイト表現 (デフォルトutf-8) で 持ってるので、正規表現エンジンは文字単位ではなくオクテット列に直接 マッチをかける (マッチ開始位置は常に文字境界なので、euc-jpやshift_jisでも 非文字境界でマッチしてしまうことはない)。 なので基本的に utf-8 <-> ucs-4 の変換は 起きないのだけれど、ASCIIをはみ出す文字クラスの時だけはこの変換を行わないと ならない。

でも、ucs-4での文字範囲は、utf-8で表現したオクテットの範囲のツリーに 変換できるはずなので、それをやれば完全にutf-8のままマッチがかけられる。 もう何年も前から試したいとは思っているのだけど手をつけられていない。 そういう実装をやってるエンジンってあるのかな?

Tags: Programming, Gauche