UTF8の文字数を数える

つい最近、UTF8文字列を扱う処理を書いたのでその実装方法についてのお話です。今日の問題設定は、天下一プログラマーコンテストの例題でも有名になりましたが、UTF8の文字数カウントです。

UTF8の文字列形式について詳しくはWikipediaを見て頂ければいいかと思いますが、

http://ja.wikipedia.org/wiki/UTF-8

簡単に紹介すると、UTF8は一文字1-6バイト(最近は1-4バイトのみ)からなるエンコード形式であり、各文字が何バイトから構成されているかはその文字の1バイト目を見ればわかります。

例えば1バイト文字の場合は7bitのASCII文字から構成されていて、1バイト目の上位ビットが「0」となります。 2バイトの場合は「110」, 3バイトの場合は「1110」という風に以降、上位ビットの1の数と1文字あたりのバイト数が等しくなります。また先頭バイト以外は上位ビットが「10」から始まるので、文字境界は一意に定まります。

例)
1バイト文字:
0XXXXXXXX

2バイト文字:
110xxxxxx 10XXXXXX

3バイト文字:
1110xxxxx 10XXXXXX 10XXXXXX

さてこの仕様からUTF8の文字数をカウントする方法を考えてみます。真面目にビットカウントをする方法は以下の方法だと思います。

1. 文字列を入力として受け取る
2. 1バイト取り出して1文字が何バイトか確認する
  2a. 入力の1bit目が0かどうかをチェック
  2b. 入力の1bit目, 2bit目が「10」かどうかチェック
  2c. 上位からビット数を数える。
3. 文字数カウントを1インクリメントする。
4. 1文字のバイト数分スキップして、また2-4を繰替えす。

ちょっと工夫してみたいと思います。僕が思いついた(以前そういう実装を見た記憶があったものを含む)のは以下の3パターンでした。ちょっと説明が難しいのでコードを見ながら確認してください。

https://github.com/shnya/snippets/blob/master/cpp/utf8len.cc

1. 文字列を全走査しながら、
   上位ビットが「10」から始まる文字列はスキップ、
   それ以外のバイトが入力の場合のみ文字数を1増加する方法
   (utf8len1)

2. 1バイト目のバイト数テーブルを持ってそのテーブルを参照しながら文字数を数える方法
   (utf8len2)

3. 1バイト目の取り得る範囲を確認し、
1文字あたりのバイト数を計算しながら文字数を数える方法。
   (utf8len3)

個人的には条件分岐を少なくできる"utf8len2"が一番高速だろうなぁ？と思ったのですが、実際に実行した結果は予想に反した結果となりました。

環境: Macbook Air (Mac OS X 10.6.5, DDR3 4GB)
実行結果：
$ g++ -O2 utf8len.cc -o utf8len
$ ./utf8len
utf8len1: 
 time = 0.6338099999999999845101683604298159480095
 length = 10
utf8len2: 
 time = 0.4933850000000000735056460143823642283678
 length = 10
utf8len3: 
 time = 0.4577480000000000437410108133917674422264
 length = 10

もちろん、"utf8len3"は4バイトの文字などが多ければもう少し遅くなるかと思いますが、まだまだコードの書き方と実行速度の関係が身に付いてないんだなーと思った今日この頃でした。ただ、あまりどれも時間差はないので、どの方法を使ってもいいと思うんですけどね。

ちなみにバイト数テーブルを参照する方法は@tkngさんのmicterで使われているコードを参考にさせて頂きました。(そういえばこういう処理してたなーと) 先頭バイト以外をスキップして数える方法(utf8len1)は天下一プログラマーコンテストの例題を解くのがネット上で流行った時に、いろんなプログラミング言語で行なわれてた方法を参考にしました。