空白文字のチェックはどれほど難しいのか？

最近ソースコードを眺めていて、Guava のこのメソッドにたまたま出くわした。Guava は Google が公開している人気の Java ライブラリだ。

名前からおおよそ見当がつく通り、このメソッドは与えられた文字が空白文字かどうかを判定する。ところがコードは、単純な c == ' ' の判定よりはるかに複雑に見える。それが気になって、この複雑さがどこから来るのかを突き止めようと、糸口をたどって掘り下げてみた。このコードがどう動くのか気になったなら、この記事はあなたのためのものだ。

空白文字とは何か

ある文字が空白文字かどうかを判定する関数を検討するには、まず空白文字とは何かをはっきり定義しなければならない。SPACE (U+0020) はおそらく最もよく知られた空白文字だが、唯一のものではない。しばらくコードを書いている人なら、ほかにもいくつか挙げられるだろう。ノーブレークスペース NO-BREAK SPACE (U+00A0)、タブ CHARACTER TABULATION (U+0009)、改行 LINE FEED (U+000A)。

実はもっとある。Unicode は White_Space プロパティ を定義していて、25 文字のリストを定めている。以下がそのリストだ。一字一句そのままコピーしたもの： , ,,, , ,…, , , , , , , , , , , , , ,
,
, , ,　。

これらの文字にはそれぞれ用途がある。たとえば FIGURE SPACE (U+2007) は表の中で数字ひとつ分の幅を持ち、THIN SPACE (U+2009) と HAIR SPACE (U+200A) は隙間の広さがこの順に狭くなる。NO-BREAK SPACE (U+00A0) は普通のスペースと同じ幅だが、改行の際に前後のテキストをつなぎ止める。

名前や字形を見ただけでは、その文字が空白文字の集合に属するかどうか判断できないこともある。たとえば ZERO WIDTH SPACE (U+200B) は空白文字ではまったくない。名前とは裏腹に、これは書式制御文字で、単語や改行の可能な位置を示すものの、目に見える隙間は生まない。

この集合には目立たないメンバーもいる。OGHAM SPACE MARK (U+1680) は実際には目に見える水平線として描画されうる。幹線を持つ Ogham フォントでは、この空白は文字の間でその線を途切れさせずにつなぐ（例：᚛ᚆᚓᚂᚂᚑ ᚒᚑᚏᚂᚇ᚜）。幹線のないフォントでは空白のままだ。つまり「空白文字は見た目が空でなければならない」という前提すら、常に成り立つわけではない。

ランタイムが違えばルールも違う

統一された定義が意味を持つのは、空白文字とは何かについて全員が合意している場合だけだ。ところが同じランタイムの中ですら、ライブラリによって空白とみなす範囲が食い違うことがある。

先ほど挙げた NO-BREAK SPACE (U+00A0) を例に取ろう。これは Unicode の White_Space プロパティには含まれているが、Java は明示的に除外している。ほかのノーブレークスペース2つも同様に除外される。javadoc にはこう書かれている。このメソッドが空白とみなすのは Java 自身のルール に基づいており、先ほど見た Unicode プロパティではない、と。

Character.isWhitespace(' ');      // true
Character.isWhitespace('\u00A0'); // false

では他のランタイムはどうか。より広く使われている Python と JavaScript を見ると、誰もが認める権威的な空白文字の一覧など存在しないことがわかる。たとえば Python には便利な str.isspace() メソッドがある。Java と違い、U+00A0 も空白文字として扱う。

では Python は Unicode の White_Space プロパティに従っているのか。そうでもない。

"\u00A0".isspace()  # True
"\u0085".isspace()  # True
"\u001C".isspace()  # True
"\uFEFF".isspace()  # False

ここで注目すべきは FILE SEPARATOR (U+001C) だ。ASCII の制御文字で、もともとは情報の区切りに使われていたもので、Unicode の White_Space プロパティには含まれない。つまり Python が空白文字とみなすのは 29 個で、Unicode の 25 個とは一致しない。

JavaScript はまた別の流儀をとる。Character.isWhitespace() メソッドに相当するものはないが、正規表現で \s 文字クラスが使える。

/\s/.test("\u00A0");  // true
/\s/.test("\u0085");  // false
/\s/.test("\uFEFF");  // true

上の例外が NEXT LINE (U+0085) だ。Unicode はこれを明確に White_Space に含めており、Python も受け入れるが、JavaScript は認めない。逆に JavaScript が認める ZERO WIDTH NO-BREAK SPACE (U+FEFF) を、Unicode はこの集合に含めていない。

他のランタイムは調べていないが、食い違いはこの三つにとどまらないだろう。

何も固定されていない

さらに厄介なのは、Unicode が不変ではないことだ。今も進化を続けており、それが空白の定義にも影響する。たとえば Unicode 6.3 は MONGOLIAN VOWEL SEPARATOR (U+180E) を空白区切り文字から書式文字へと再分類し、White_Space プロパティを外した。これにより Unicode の空白文字集合は 26 個から 25 個になった。後方互換性を重視するランタイムやライブラリにとって、こうした変更は大きな負担になる。言語の標準ライブラリはできるだけ安定していてほしいからだ。

空白をすばやく判定する

調べたい文字集合について合意が得られたとしよう。つまり現在の Unicode の空白文字集合だ。最も素直な実装は文字のリストを走査し、一致するものがあるか一つずつ確かめる方法だ。動きはするが、明らかに効率的ではない。

記事冒頭で示したコードで Guava の実装 がやっているのは、完全ハッシュ関数の実装だ。既知の集合に含まれる文字についてハッシュ衝突が起きないことを保証するハッシュ関数である。

static final String TABLE = "\u2002...";

@Override
public boolean matches(char c) {
    int slot = (1682554634 * c) >>> 27;
    return TABLE.charAt(slot) == c;
}

上の TABLE は 32 文字の文字列で、実質的には各インデックス（キー）を文字（値）に対応させるハッシュテーブルだ。Unicode の空白文字 25 個をすべて含み、残りの位置はいくつかの文字を繰り返して埋めてある。

最も興味深いのはインデックスの計算だ。乗算 1682554634 * c で 32 ビット整数を得て、>>> 27 で 27 ビット右シフトし、最上位 5 ビットを取り出す。これは [0, 32) の範囲に収まる数で、表を引くのにちょうどよい。もちろん文字の種類は表の項目より多いので、最後に == c で、引いた文字が求めている文字そのものかどうかを確認する。

この表がどう埋まるかを以下に示す。

マジックナンバー 1682554634 はたしかに魔法のように見えるし、どうやって選ばれたのかは私にも分からない（答えを知っている人は教えてほしい）。だが使える乗数はこれだけではない。簡単な総当たり検索を一度走らせれば、適切な候補はすべて洗い出せる。

static final char[] ALL_CHARS = (
        "\u2002\u3000\r\u0085"
        + "\u200A\u2005\u2000"
        + "\u2029\u000B\u2008"
        + "\u2003\u205F\u1680"
        + "\u0009\u0020\u2006"
        + "\u2001\u202F\u00A0"
        + "\u000C\u2009\u2004"
        + "\u2028\n\u2007"
).toCharArray();

public static void main(String[] a) {
    var slots = new BitSet(32);
    outer:
    for (int mul = 1; mul != 0; mul++) {
        slots.clear();
        for (char c : ALL_CHARS) {
            int index = (mul * c) >>> 27;
            if (slots.get(index)) {
                continue outer;
            }
            slots.set(index);
        }
        System.out.println(mul);
    }
}

面白いのは、腰を据えて調べる気のある人なら git の履歴をたどり、Guava がどうこの実装にたどり着いたかを追えることだ。最初はもっと単純なマッチャーだったのが、後に mod-79 版へと置き換わる。この版には Unicode の文字集合について興味深い観察があるが、除算が一度入るのが難点で、そのさらに後になって完全ハッシュ関数に切り替わった。

完全ハッシュの他の用途に興味があれば、ちょうどこの記事を書いている最中に、Daniel Lemire が同じテーマのブログを公開している。完全ハッシュで HTTP メソッドを判定する例が載っている。

おわりに

Guava でこの空白文字チェックのコードを初めて見たとき、好奇心をかき立てられた。おかげで Unicode についていろいろ学べたし、完全ハッシュ関数の面白い使い方も知ることができた。実際のコードではなかなかお目にかかれないものだ。

この記事が、読んでいるあなたにとっても何か面白いものを持ち帰るきっかけになればと思う。身の回りで好奇心をそそられたことがあれば、ブログに書いて公開してみてはどうだろう。AI 優先の今、こういう記事はますます減っていると感じる。isWhitespace のような単純な関数の蓋を、わざわざ開けて中を覗いてみようと思う人は、もうほとんどいないのだから。