Namaran

Code daily. Without assist.

2026-11-06

utf8_distance.cpp

#include <algorithm>
#include <print>
#include <string_view>

int dist(std::u8string_view a, std::u8string_view b) {
    if (a.empty() || b.empty()) {
        return a.size() + b.size();
    }
    int sub = dist(a.substr(1), b.substr(1)) + (a[0] != b[0]);
    return std::min({sub, dist(a.substr(1), b) + 1, dist(a, b.substr(1)) + 1});
}

int main() {
    std::println("{}", dist(u8"café", u8"café"));
}

これは何を出力するでしょうか?

Answer

Output

3

dist は、先頭の要素を置き換える・a から1つ消す・a に1つ足すの3通りを試し、一方が空になったら残りの長さを足す、という再帰で編集距離を求めています。比べる単位は std::u8string_view の要素、つまり char8_t の1バイトで、文字ではありません。u8 付きのリテラルは UTF-8 で符号化されるので、\u00e9 のように U+0080〜U+07FF の範囲にある文字はそれぞれ2バイトになります。

\u00e9 は1文字で「é」を表し、UTF-8 では C3 A9 です。\u0301 は直前の文字に鋭アクセントを重ねる結合文字1で、e の後ろに置くと画面には同じ「é」が出ます。こちらは UTF-8 で CC 81 です。そのため a は 63 61 66 C3 A9 の5バイト、b は 63 61 66 65 CC 81 の6バイトになります。先頭の caf の3バイトは一致して距離0のまま進み、残りの C3 A9 と 65 CC 81 には共通のバイトが1つもありません。1回の操作で直せるのは1バイトだけなので、長いほうの3バイトのそれぞれに1回ずつ操作が要り、2回の置き換えと1回の挿入で3になります。

画面に出る文字で比べると、どちらも「café」なので0に見えます。文字の並びとして比べても、é を e に置き換えてアクセントを1つ足すので2です。バイト単位で比べると気付いても、b 側の e が a と一致すると思うと2になりますが、a には 65 のバイトがありません。é の2バイトはどちらも0x80以上で、ASCII の e とは一致しないからです。

  1. 結合文字(combining character)は、単独では表示されず、直前の文字に記号を重ねる文字です。同じ見た目の文字列を1つの表現にそろえる処理は Unicode 正規化(Unicode normalization)と呼ばれ、é を1文字にまとめる形が NFC、e と結合文字に分ける形が NFD です。距離を文字の見た目で測りたいなら、比べる前に両方を同じ形にそろえます。