C++でUTF-8エンコーディングの妥当性を検証する方法

本記事では、整数のリストとして与えられたデータが、有効なUTF-8エンコーディングであるかどうかを判定するアルゴリズムについて解説します。1つのUTF-8文字は1バイトから4バイトの長さになり、それぞれのバイト長に応じて特定のビットパターンを持つという特徴があります。

UTF-8エンコーディングの基本ルール

UTF-8には以下のような性質があります。

• 1バイト文字：先頭ビットが0で、その後にUnicodeコードポイントが続きます。
• nバイト文字：先頭のnビットがすべて1であり、n+1番目のビットが0。その後ろに続くn-1個のバイトは、いずれも上位2ビットが「10」で始まります。

これらのルールを表にまとめると、次のようになります。

具体例

例として、入力が [197, 130, 1] の場合を考えてみましょう。これはオクテット列 11000101 10000010 00000001 を表しています。

最初のバイト「11000101」は先頭3ビットが「110」なので2バイト文字の始まりです。次のバイト「10000010」は上位2ビットが「10」なので継続バイトとして正しく、最後のバイト「00000001」は先頭ビットが0の1バイト文字です。したがって、この入力は「2バイト文字＋1バイト文字」として有効なUTF-8エンコーディングであり、結果は true となります。

アルゴリズムの考え方

この問題は、継続バイトのカウンタを使って以下の手順で解くことができます。

1. カウンタ cnt を0で初期化します。
2. データ配列の各要素 x に対して以下を繰り返します。
   • cnt が0の場合（新しい文字の開始バイト）：
     ・x >> 5 が 110 なら、2バイト文字なので cnt = 1
     ・x >> 4 が 1110 なら、3バイト文字なので cnt = 2
     ・x >> 3 が 11110 なら、4バイト文字なので cnt = 3
     ・x >> 7 が0でなければ、無効な開始バイトなので false を返す
   • cnt が0以外の場合（継続バイト）：
     ・x >> 6 が 10 でなければ false を返す
     ・そうでなければ cnt を1減らす
3. ループ終了後、cnt が0であれば true を返します。

C++での実装例

以下に、上記のアルゴリズムを実装したC++のコードを示します。

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   bool validUtf8(vector<int>& data) {
      int cnt = 0;
      for(int i = 0; i <data.size(); i++){
         int x = data[i];
         if(!cnt){
            if((x >> 5) == 0b110){
               cnt = 1;
            }
            else if((x >> 4) == 0b1110){
               cnt = 2;
            }
            else if((x >> 3) == 0b11110){
               cnt = 3;
            }
            else if((x >> 7) != 0) return false;
          } else {
             if((x >> 6) != 0b10) return false;
             cnt--;
          }
      }
      return cnt == 0;
   }
};
main(){
   Solution ob;
   vector<int> v = {197,130,1};
   cout << (ob.validUtf8(v));
}

入力

[197,130,1]

出力

1

出力が「1」となっており、入力 [197, 130, 1] が有効なUTF-8エンコーディングであることが確認できます。このアルゴリズムの計算量はO(n)（nはデータの要素数）、空間計算量はO(1)と非常に効率的です。