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