UnicodeData Canonical Combining Class のダブル配列トライ

Unicode の合成文字は、 UnicodeData.txt の第 3 欄 Canonical Combining Class の数値がゼロでないものを抽出します。 以前は狭い範囲で収まっていて単純なテーブル参照で済んでいたのですけど、 広い範囲にばらけながら増える一方なので、 ダブル配列のトライを作ることにしました。

コードポイントの下 3 バイトを使い、 それぞれのバイトでトライ木の枝分かれをしていくようにします。

int
canonincal_combining_class (char32_t codepoint)
{
    static const short base[] = {
        // Perl で生成
    };
    static const short check[] = {
        // Perl で生成
    };
    int const ncheck = sizeof (check) / sizeof (check[0]);
    int const k0 = (codepoint >> 16) & 0xff;
    int const k1 = (codepoint >>  8) & 0xff;
    int const k2 = (codepoint      ) & 0xff;

    int state = 1;
    int next_state = base[state] + k0;
    if (0 < next_state && next_state < ncheck && check[next_state] == state) {
        state = next_state;
        next_state = base[state] + k1;
        if (0 < next_state && next_state < ncheck && check[next_state] == state) {
            state = next_state;
            next_state = base[state] + k2;
            if (0 < next_state && next_state < ncheck && check[next_state] == state) {
                return base[next_state];
            }
        }
    }
    return 0;
}

ダブル配列は Perl で生成します。

#/usr/bin/env perl
use strict;
use warnings;
use List::Util qw(any shuffle);

my %trie;
#@<UnicodeData.txt を読んで、第 0 欄をキー、第 3 欄を値とするトライ木を作ります@>

my @base = (0);
my @check = (-1, -1);
#@<トライ木からダブル配列を作ります@>

print "static const short base[] = {\n    ";
for my $i (0 .. $#check) {
    printf "%4d,%s", defined $base[$i] ? $base[$i] : 0,
        $i % 10 < 9 ? " " : "\n    ";
}
print "\n};\nstatic const short check[] = {\n    ";
for my $i (0 .. $#check) {
    printf "%4d,%s", defined $check[$i] ? $check[$i] : 0,
        $i % 10 < 9 ? " " : "\n    ";
}
print "\n};\n";

Unicode 8.0 での対象コードポイントは 751 個にすぎないので、 トライ木を作って、 それから静的にダブル配列を作ることにします。

#@<UnicodeData.txt を読んで、第 0 欄をキー、第 3 欄を値とするトライ木を作ります@>=
while (<>) {
    my @f = split /;/, $_, -1;
    next if $f[3] == 0;     # Start コードポイントは対象外
    my $codepoint = hex($f[0]);
    my $k0 = ($codepoint >> 16) & 0xff;
    my $k1 = ($codepoint >>  8) & 0xff;
    my $k2 = ($codepoint      ) & 0xff;
    $trie{$k0}{$k1}{$k2} = $f[3];
}

初期状態を 1 として、 ダブル配列を作ります。 トライ木からダブル配列を作るには、 分岐の節のキーをストアップし、 それを check 配列の隙間にはめ込んでいきます。 深さ優先と幅優先の両方で動かしてみて、 どちらが小さなダブル配列になるか比較してみたのですが、 優位差は生じなかったので、 深さ優先の方を書いておきます。

#@<トライ木からダブル配列を作ります@>=
my $s0 = 1;
my @key0 = sort { $a <=> $b } keys %trie;
$base[$s0] = 2 - $key0[0];
for my $k0 (@key0) {
    $check[$base[$s0] + $k0] = $s0;
}
for my $k0 (@key0) {
    my $s1 = $base[$s0] + $k0;
    my @key1 = sort { $a <=> $b } keys %{$trie{$k0}};
    $base[$s1] = 1 - $key1[0];
    while (any { defined $check[$base[$s1] + $_] } @key1) {
        ++$base[$s1];
    }
    for my $k1 (@key1) {
        $check[$base[$s1] + $k1] = $s1;
    }
    for my $k1 (shuffle @key1) {
        my $s2 = $base[$s1] + $k1;
        my @key2 = sort { $a <=> $b } keys %{$trie{$k0}{$k1}};
        $base[$s2] = 1 - $key2[0];
        while (any { defined $check[$base[$s2] + $_] } @key2) {
            ++$base[$s2];
        }
        for my $k2 (@key2) {
            $base[$base[$s2] + $k2] = $trie{$k0}{$k1}{$k2};
            $check[$base[$s2] + $k2] = $s2;
        }
    }
}

key1 をシャッフルして、 割り当て順をランダムに変えています。 これで、 何度かスクリプトを走らせて、 一番行数が少ないものを選んで利用しています。 1 行 10 個ずつで折り返して、 base と check あわせて少ない方は 2100 行前後になります。