公開 2006-10-18
最終 2006-10-21

swatchとswash

ここではPerl 5.6以降のUnicodeサポートで内部的に使用されているデータ構造、swatchとswashについて概説します。

swatch/swashを必要とする処理は、正規表現では文字プロパティ (\p{ }, \P{ }) 、Unicodeに対する場合の \w や \W, 文字クラス等があり、それ以外には文字間の写像 (tr///, y///, uc, lc, ucfirst, lcfirst, \U, \L, \u, \l) があります。

swatchとは、平たく言えば、断片的なbit vectorです。例えばm個の連続した符号位置(code point)について、一符号位置当たりnビットの値を格納する場合、(m×n/8)バイト長の文字列に格納します。なお、perl内部では1バイト=8ビットは前提ですので、byteの定義についての議論は無用です。また、swashとは、swatchを値に持つハッシュ(hash)です。swatch hashを縮めてswashにしたものです。swashには、swatchのほか、実行時にswatchを生成するために必要な各種情報も格納されます。

1つのswatchが表す符号位置の範囲は、それらの符号位置をperlの内部で使用している符号化表現(現状はUTF-8またはUTF-EBCDICのいずれかとされていますが、perlがどの符号化表現を用いるかについて、ユーザやモジュール作者等はあまり仮定や意識をしてはいけません。)で符号化したとき、最終バイトのみが異なるグループに該当します。そして、最終バイトを除いたバイト列がswashの鍵(key)になります。なお、UTF-EBCDICとは、Unicode Technical Report #16で規定された符号化表現であり、識別子EBCDICを定義してコンパイルしたperlで使用されます。

つまり、ある符号位置がNバイト文字で表現されるとすると、第一バイトから第N-1バイトまでが共通する符号位置についての値は、1つのswatchに格納されます。また、第一バイトから第N-1バイトまでのバイト列がswashのkeyになります。これにより、swashにおいて各swatchが表す符号位置の範囲は、対応するkeyから容易に知ることができます。

したがって、UTF-8またはUTF-EBCDICで一バイト文字として符号化される文字 (UTF-8の場合U+0000..U+007F、UTF-EBCDICの場合U+0000..U+009F) は、1つのswatchに格納され、そのkeyは空文字列になります。また、複数バイト文字として符号化される文字の場合、UTF-8では64符号位置、UTF-EBCDICでは32符号位置についての値が1つのswatchに格納されます。swatch以外の情報をswashに格納するとき、通常の英大文字 (AからZ) からなる単語をkeyにしていますので、swatchのkeyと衝突することはありません。

この結果、UTF-8またはUTF-EBCDICで符号化された符号位置についてswashから値を得るためには、第一バイトから第N-1バイトまでのバイト列をkeyとしてswatchを取り出し、さらに第Nバイトの値に基づきswatchの何番目に望みの値が格納されているかを計算することによって、各符号位置についての値を得ることができます。

swashは、必要が生じたときに、lib/utf8_heavy.plで定義されたSWASHNEWメソッドを呼び出し、そこで生成されます。SWASHNEWでは、swashに必要なデータ (LISTと呼ばれる。) を、あるいはperl実装系に同梱されているデータファイルから、あるいは、ユーザ定義のサブルーチンから、受け取ります。データファイルは、lib/unicoreディレクトリの中にあります。ユーザ定義のサブルーチンについては、そのようなデータをperlに渡せばよいかの説明がperlunicode.podにありますのでそちらを参照してください。なお、これらのユーザ定義サブルーチンの返却値とは、LISTそのものです。文字クラスやtr///, y/// においては、従来の (Perl 5.005 以前の) 実装 ("\000"から"\377"までしかない。) では対応できない場合、コンパイル中に文字並びをLISTに変換し(regcomp.cのS_regclass関数、op.cのPerl_pmtrans関数)、SWASHNEWに渡せるようにしています。

swatchは、必要が生じたときに、swashに格納されたLIST等のデータに基づいて生成されます。生成されたswatchはswashにキャッシュされますので、キャッシュがあれば、それを利用します。swatchの生成は、例えば正規表現エンジンで検索している最中に実行されることもあるのですが、Perl 5.8.xまでは、swatchの生成はpure perlサブルーチン (lib/utf8_heavy.plで定義されたSWASHGETメソッド) として実装されていたため、そのつど正規表現エンジンの内部状態を保存してからサブルーチンを呼び出すことが必要となり、効率がよいものではありませんでした。しかし、Perl 5.9.3以降では、C言語でswatch生成関数 (utf8.cのS_swash_get関数) が実装されており、効率が大幅に改善されています。

文字プロパティや文字クラスの場合は、符号位置がそのプロパティやクラスに該当するかどうかだけが分かればよいので、swatchは一符号位置につき1ビットを使用します。文字間の写像の場合は、変換先の符号位置を知る必要があるので、8, 16, または 32ビットを使用します。一符号位置につき何ビットを使用するかは、変換先の符号位置を表す値を格納するのに十分な大きさが選ばれます。

また、tr/// やその別名である y/// については、「変換元として指定されていない」(例えば tr/ABC/XYZ/ の場合のDなど) や「変換先が指定されていない」(例えば tr/ABC/XY/ の場合の C) という特殊な状態もありますので、それらの状態をswatchにおいてどの値で表すようにしたかを指示する情報がswashに付加されます。

swash/swatchの利点は、swatchについてそのままビット演算ができる(例えば、ラテン用字 (latin script) にマッチするかどうかを表すswatchと、大文字 (capital letter) にマッチするかどうかを表すswatchとについて、バイト単位でAND演算を行うと、ラテン大文字 (latin capital letter) にマッチするかどうかを表すswatchを得ることができる。)ので、文字プロパティや文字クラスについて集合演算 (set operation) が容易に実装できること、必要になったときにswashからswatchを生成すればよいので、初期の記憶域が節約できることが挙げられます。

欠点としては、例えばブロックのように、LISTがごく短い単純な集合であっても、一々swatchを生成しなければならないこと、LISTが極めて長い場合(例えば「JIS X 0208で規定された漢字かどうかというプロパティ」のように、符号位置が広範囲に散らばっているもの)には、swatchの生成するときLISTの内容を読むために処理量が増加すること、swashからは一々swatchを生成してから出ないと値が得られないため、値を得ようとする符号位置の数が増えるほど多くのswatchを生成しなければならないことが挙げられます。

これらの点からすると、swash/swatchは、LISTの長さが中程度(例えば数十から数百の文字数) の場合で、対象となる符号位置の範囲が比較的まとまっている場合)に適しているものと考えられます。


Perlのページ