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

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

最近、あるソースコードを調べていたところ、Googleの人気JavaライブラリであるGuavaのメソッドに出くわしました。

［画像: Guavaの空白文字マッチの実装］

名前から推測できるように、このメソッドは与えられた文字が空白文字かどうかをチェックします。しかし、そのコードは単純な c == ' ' のチェックよりもはるかに複雑に見えました。これが私に好奇心を抱かせ、この複雑さがどこから来るのかを理解しようとする小さな探求へと駆り立てました。もしあなたもこのコードがどのように機能するのか気になるなら、この記事はあなたのためです。

そもそも、空白文字とは何か？

文字が空白文字かどうかをチェックする関数を調べる際に、まず必要なのは、空白文字が実際に何であるかを定義することです。SPACE (U+0020) はおそらく最もよく知られた空白文字ですが、それだけではありません。しばらくコードを書いていれば、他にもいくつか名前を挙げられるでしょう――ノンブレークスペース NO-BREAK SPACE (U+00A0)、タブ CHARACTER TABULATION (U+0009)、改行 LINE FEED (U+000A)。

実は、もっとあります。UnicodeはWhite_Spaceプロパティを定義しており、25文字のリストを提供しています。それらは以下の通りです――細心の注意を払ってコピーしました： , , ,\f, , ,…, , , , , , , , , , , , , ,
,
, , ,　。

これらの各文字には異なる目的があります。例えば、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) は、実際には表示可能な水平線としてレンダリングされることがあります。ステムラインを持つオガムフォントでは、スペースは文字間の線（例: ᚛ᚆᚓᚂᚂᚑ ᚒᚑᚏᚂᚇ᚜）を継続しますが、ステムレスフォントでは空白です。したがって、空白は常に空であるべきだという仮定さえ、常に真実であるとは限りません。

異なるランタイム、異なるルール

空白文字の単一の定義を持つことは、全員がそれに同意した場合にのみ有用です。しかし、単一のランタイム内でも、ライブラリによって空白文字の定義が異なる場合があります。

前述の NO-BREAK SPACE (U+00A0) を考えてみましょう。これはUnicodeの White_Space プロパティに含まれていますが、Javaは明示的にそれを、他の2つのノンブレークスペースと共に除外しています。Javadocは、このメソッドが以前見たUnicodeプロパティに従うのではなく、Javaに従って空白文字をチェックすることを有用に強調しています。

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

［画像: Java isWhitespace スクリーンショット］

では、他のランタイムはどうでしょうか？人気のあるPythonとJavaScriptの2つを見てみると、全員が同意する単一の権威ある文字リストが存在しないことがわかります。例えば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はUnicodeの25文字ではなく、29個の空白文字を認識します。

JavaScriptはさらに別の方法を取ります。Character.isWhitespace() メソッドに相当するものはありませんが、正規表現で egex 文字クラスを使用できます。

/\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がセットに含んでいないものです。

他のランタイムは調べていませんが、この不整合がこれら3つで止まるとは思えません。

確定的なものはない

さらに複雑さを増しているのは、Unicodeは固定されておらず、常に進化していることです。そしてこれは空白文字の定義に影響を与えます。例えば、Unicode 6.3 では、MONGOLIAN VOWEL SEPARATOR (U+180E) がスペースセパレーターからフォーマット文字に再分類され、White_Space プロパティが削除されました。その結果、Unicodeの空白セットは26文字から25文字に変更されました。後方互換性を維持しようとするランタイムやライブラリにとって、これらの変更は pretty significant な課題となり得ます。なぜなら、言語の標準ライブラリはできるだけ安定させたいからです。

空白文字を高速にチェックする

チェックしたい文字のセット、つまり現在の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文字の文字列です――これは事実上、各インデックス（キー）を文字（値）にマッピングするハッシュテーブルです。これには25個のUnicode空白文字すべてが含まれており、残りの位置は重複で埋められています。

最も興味深い部分はインデックスの計算です。1682554634 * c の乗算は32ビット整数を生成し、>>> 27 はそれを27ビット右にシフトし、上位5ビットを分離します――これは[0, 32) の範囲の数値であり、テーブルのルックアップに使用できます。もちろん、テーブルエントリよりも多くの可能な文字があるため、最終的な == c チェックは、見つけた文字が探していたものと一致することを確認するために必要です。

以下の文字をクリックすると、テーブルがどのように埋められているかを確認できます。

int value =

32

*

1682554634

=
-1992826560

10001
001001101111110000101000000
17
0·
1·
2·
3·
4·
5·
6·
7·
8·
9·
10·
11·
12·
13·
14·
15·
16·
170020
18·
19·
20·
21·
22·
23·
24·
25·
26·
27·
28·
29·
30·
31·

魔法のような 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がどのようにこの実装に至ったかを追跡できます。それは、よりシンプルなマッチャーから、Unicode文字セットに関する興味深い観察があるmod-79バージョンへと移行し、除算操作を伴うという欠点がありましたが、その後パーフェクトハッシュ関数へと続きました。

そして、パーフェクトハッシュの他の応用例に興味があるなら――この記事を書いているちょうどその頃、Daniel LemireはHTTPメソッドのチェックにパーフェクトハッシュを使用する例を挙げたブログを公開しました。

結論

Guavaの空白文字チェックコードを初めて見たとき、それは私の好奇心を刺激し、その結果、Unicodeについていくつか学び、パーフェクトハッシュ関数の興味深い応用例を見ることができました――これは、実際のところあまり使われないものです。

この記事からも何か興味深いことを学んでいただけたなら幸いです。そして、好奇心を刺激されるものを見つけたら、ぜひブログ記事を書いて共有してください。AI中心の世界では、isWhitespace のような単純な関数の内部を覗く理由がほとんどないため、これらの書き込みがますます希少になっていると感じています。

話題にする

• Lobsters
• Reddit

購読

この記事が気に入ったら、購読を検討してください――新しい投稿を公開するたびにメールを送信するか、Hacker Newsで共有しますので、ぜひ広めてください。

または、RSSで購読してください。

---