SentencePiece を持ち込まず、Unigram の分割を C++ で書き直した
Rewriting SentencePiece's Unigram segmentation in C++ instead of bundling it
D03-4-T06-sentencepiece-unigram・技術・日本語入力でプレイする仕組み
「佐伯さん、１０時まで番屋にいたと言いましたね」。
この一文は、文の埋め込みに入る前に、先頭と末尾の印と接頭辞を含めて 20 個の片（トークン）に切られます。
その切り方を、UE とコマンドライン版とブラウザ版のサーバで、1 片も違わないようにそろえています。
『霧走町 流氷に眠る』は、入力された日本語を、書き下ろした証言のどれかに当てるゲームです（遊んでいる間に文は作りません）。
当てる物差しの一つが、文の埋め込み multilingual-e5-small です（今日の夕方の T05）。
モデルに文を渡す前に、文を語彙の片に切る必要があります。この回はその分割器の話です。
この回の位置と、前後の回#
区切り: T03〜T24 日本語入力を解いて返すまで（22 回のうち 4 回目）
先に読むとよい回: T05（文の埋め込み）
次に読む回: T07（同じベクトルを出す ONNX Runtime）
名前 — SentencePiece#
- 正式名
- SentencePiece／Unigram language model（サブワード分割の）
- 日本語の呼び名
- センテンスピース、ユニグラム言語モデルによる分割
初出:
SentencePiece は Kudo & Richardson, "SentencePiece: A simple and language independent subword tokenizer and detokenizer for Neural Text Processing", EMNLP 2018 System Demonstrations。
Unigram による分割は Kudo, "Subword Regularization: Improving Neural Network Translation Models with Multiple Subword Candidates", ACL 2018。
あわせて使う名前: Viterbi algorithm（最良の分割を探す動的計画法）、Metaspace（Hugging Face tokenizers での、空白を ▁ に置き換える前処理の名前）
一般の解説 — SentencePiece#
サブワード分割（subword segmentation）とは、語彙を「単語」でも「文字」でもない中間の片にする方法です。
よく出る語は 1 片、まれな語は複数の片に切ります。語彙の大きさを固定したまま、未知語をほぼ無くせます。
代表は二つです。
BPE（byte-pair encoding）は、よく隣り合う片を一つにまとめる規則を順に覚えます。分割はその規則を順に当てる手続きです。
Unigram は、各片に出現確率を持たせ、文の分割の確率を片の確率の積で表します。
P(x) = p(x1) × p(x2) × … × p(xn)
学習では、大きな候補の集合から始め、EM で確率を推定し、削っても尤度があまり下がらない片を一定の割合ずつ削っていきます（1 文字の片は残す）。目標の語彙の大きさで止めます。
分割するときは、log p の和が最大になる分割を、Viterbi で探します。
論文の題にある subword regularization は、学習のときにわざと最良でない分割も確率に応じて選び、翻訳モデルを揺れに強くする使い方です。推論では最良の分割だけを使います。
SentencePiece は、この分割器を言語に依らずに使える形にした実装です。
特徴は二つ。
入力を事前に単語に切らない生の文字列として扱い、空白も「▁」（U+2581）という普通の文字にします。だから分割を元の文に戻せます。
分割の前に正規化をかけます。既定は NFKC に手を加えた nmt_nfkc で、表は precompiled_charsmap として語彙のファイルに埋め込まれています。
XLM-RoBERTa と、それを引き継ぐ multilingual-e5 は、語彙約 25 万の SentencePiece Unigram を使います。
よく知られた弱点もあります。
日本語の切れ目は、形態素とは一致しません（「時まで」「を出」のような片が出ます）。
語彙に無い文字は <unk> になります（byte fallback を持つ語彙なら UTF-8 の byte に落とせますが、この語彙は持っていません）。
そして、実装ごとの正規化の違いが、静かに別の id 列を生みます。今日の話の中心はこれです。
なぜ書き直したか#
UE のゲームに、SentencePiece の本体（と、その依存）を持ち込みたくありませんでした。
Unigram の推論は、語彙の片と点（log 確率）の表さえあれば、Viterbi で再現できます。BPE と違って、マージ規則の順番を持つ必要がありません。
そこで、Hugging Face の tokenizer.json から片と点だけを抜き出し、C++ で読む小さなバイナリにしました。
語彙ファイルの形（vocab.bin・KADVVOC1）#
Tools/adv-embed/export_vocab.py が書きます。リトルエンディアンです。
magic "KADVVOC1" | count u32 | unkId u32 | padId u32 | bosId u32 | eosId u32 |
count 回: { pieceLen u16, piece（UTF-8）, score f32 }
並びの添字がそのまま id です。
今日の版で 250,002 片、unk=3・pad=1・bos=0・eos=2。ファイルは 4,081,385 byte です。
特殊な片（<s> など）を除いた点は、-20.36 から -3.46 の幅にあります。
読み込むと、片 → id の unordered_map と、いちばん長い片の byte 数（MaxPieceBytes）を持ちます。
分割の実装（AdvTokenizer.hpp の UnigramTokenizer::encode）#
前処理は二段です。
- nfkcLite: 全角英数字（U+FF01〜U+FF5E）を半角に、全角空白（U+3000）を半角空白にする。それ以外は触らない。
- metaspace: 先頭に「▁」を付け、空白・タブ・改行を 1 つずつ「▁」に置き換える。
次に、byte の位置を節点にした格子で Viterbi を回します。ソースから写しました。
std::vector<double> Best(N + 1, -std::numeric_limits<double>::infinity());
std::vector<int32_t> BackId(N + 1, -1);
std::vector<size_t> BackPos(N + 1, 0);
Best[0] = 0.0;
for (size_t i = 0; i < N; ++i)
{
if (Best[i] == -std::numeric_limits<double>::infinity()) { continue; }
const size_t Limit = std::min(N, i + (size_t)MaxPieceBytes);
bool bAny = false;
for (size_t j = i + 1; j <= Limit; ++j)
{
// UTF-8 の途中で切らない
if (j < N && ((unsigned char)Norm[j] & 0xC0) == 0x80) { continue; }
const auto It = Index.find(Norm.substr(i, j - i));
if (It == Index.end()) { continue; }
const double S = Best[i] + Pieces[It->second].Score;
if (S > Best[j]) { Best[j] = S; BackId[j] = It->second; BackPos[j] = i; }
bAny = true;
}
if (!bAny)
{
// 語彙に無い1文字は <unk> として飛ばす
size_t j = i + 1;
while (j < N && ((unsigned char)Norm[j] & 0xC0) == 0x80) { ++j; }
const double S = Best[i] - 10.0; // unk への強めの罰則
if (S > Best[j]) { Best[j] = S; BackId[j] = (int32_t)UnkId; BackPos[j] = i; }
}
}
位置 i から始まる片を、MaxPieceBytes まで全部試します。UTF-8 の継続 byte（10xxxxxx）の手前では切りません。
位置 i から始まる片が 1 つも無いときだけ、その 1 文字を <unk> として、点 -10 で次の文字へ渡します。
最後に、末尾から BackPos をたどって片の列を作り、先頭に <s>、末尾に </s> を付けます。
最大長は 128（<s> と </s> を含む）。超えた分は末尾から捨てます。
実際の分割#
今日（10月29日）、いくつかの文を切って、片と点を並べました（点は log 確率）。2026-10-29 に測った値です。
▶ query: 昨日の夜はどこにいた
<s> ▁que ry : ▁昨日 の 夜 は どこに いた </s>
▶ query: 佐伯さん、１０時まで番屋にいたと言いましたね
<s> ▁que ry : ▁ 佐 伯 さん 、 10 時まで 番 屋 に いた と 言 いました ね </s>
▶ query: 番屋を出た時刻が話と違います。女将は八時前だと言っている
<s> ▁que ry : ▁ 番 屋 を出 た 時刻 が 話 と 違います 。 女 将 は 八 時 前 だと 言っている </s>
接頭辞の "query:" は「▁que」「ry」「:」の 3 片です。
「１０」は nfkcLite で「10」になり、1 片になりました。
「佐伯」「番屋」「女将」は 1 文字ずつに分かれます。この語彙にとっては、まれな語だということです。
「時まで」「を出」のように、形態素の切れ目をまたぐ片も出ます。
本家と同じ id 列が出るか#
adv-sim tokenize は、本家（Python の transformers）で作った正解の id 列と、この C++ の分割を 1 文ずつ突き合わせます。
正解は、語彙を書き出したときに、そのときの言い換えと検査の入力 1,039 文で作ってあります。
今日の結果は「一致 1039 / 不一致 0」でした。
この一致を最初から出せたわけではありません。
最初の版は全角→半角の処理を持っておらず、「？」「！」「０」を含む文で id 列がずれました。
本家は正規化の表で全角英数字を半角にするからです。1,039 文の照合で見つかり、nfkcLite を足しました。
三つの外側で同じになること#
UE（NNE）も、コマンドライン版も、Linux のサーバも、同じ AdvTokenizer.hpp を写さずにコンパイルし、同じ vocab.bin を読みます。
今日、Windows と Linux（WSL）の両方で、言い換えと検査の入力 4,459 文を焼き直したところ、出てきた vectors.bin はバイト単位で同じでした（T07 で詳しく書きます）。
同じトークン列が出ていなければ、こうはなりません。
境界の扱い — SentencePiece#
空の文字列でも、metaspace が先頭に「▁」を付けるので、<s> ▁ </s> の 3 片になります（実際には "query: " が付くので空にはなりません）。
語彙に無い文字は、1 文字ずつ <unk> になります。連続しても 1 つにまとめません。
点が同じ分割が二つあるときは、厳密な「より大きい」で更新するので、先に見つかった方（短い片で先に届いた経路）が残ります。
128 を超える入力は、先頭から 126 片を残して </s> を付けます。
名前どおりでない所 — SentencePiece#
推論の分割（Viterbi で最良の 1 つを選ぶ）は名前どおりです。学習と、確率に応じた分割の抽選はしません。
正規化が本家と違います。
本家の tokenizer.json の正規化は、Precompiled（precompiled_charsmap、今日のファイルで 316,720 文字の表）と、Replace（空白 2 つ以上を 1 つに）の 2 段です。
nfkcLite が持つのは、そのうち全角英数字と全角空白だけです。
今日、そのずれが 2 か所で見えました。
一つ目。半角カナ。
「ｱﾘﾊﾞｲ」は、こちらでは ▁ と <unk> 5 個になりました。
本家の表は NFKC に基づくので、全角の「アリバイ」に直してから切るはずです（本家を今日走らせてはいません）。
1,039 文の正解に半角カナが 1 文も無かったので、照合では見つかりませんでした。
二つ目。空白 2 つ。
「昨日の夜は どこにいた」（半角空白 2 つ）は、こちらでは ▁ が 2 片になりました。
本家は Replace で空白を 1 つにまとめるので、▁ は 1 片のはずです。
どちらも、UE・CLI・サーバの間では同じに間違えるので、三つの外側の一致は崩れません。崩れるのは「本家と同じ」の方です。
本家と同じでないと、モデルが学習で見たことのない id 列を渡すことになり、静かに意味の側の点が落ちます。
今日の時点で、半角カナで入力された入力は意味の側でもほぼ拾えません（T03 で、「ｱﾘﾊﾞｲ」が 0.001 差で受け流された例を書きました）。
未知語の点も、本家とは別に決めています。
こちらは「直前の経路の点から -10」。本家と同じ値かは、今日は確かめていません。
どちらにしても、未知語を含む分割は、未知語を含まない分割に必ず負けるくらい低い点です。
弱点と、採らなかった案 — SentencePiece#
本家の正規化の表（precompiled_charsmap）をそのまま読む案があります。
表は Darts の二重配列の trie で、読むには小さな解釈器が要ります。半角カナと空白の 2 件は直りますが、UE の核に表の解釈器を足すことになり、いまはやっていません。
SentencePiece の本体をリンクする案は、最初に捨てました。UE のプラグインに外部の C++ ライブラリを足すと、プラットフォームごとのビルドを抱えます。今回の範囲なら、200 行足らずの C++ で済みます。
正解の id 列（1,039 文）は、8 月に作ったものです。いまの言い換えは 2,845 文あり、そのうち正解を持たない文があります。
正解を作り直すには、本家を走らせる Python の環境が要ります。今日の環境にはありません。
そのぶん、本家との一致の保証は 1,039 文の範囲だけです。三つの外側どうしの一致は、焼いたベクトルのバイト一致と、実行時の計算との突き合わせ（embedcheck）で毎回見ています。
検索語#
SentencePiece Kudo Richardson 2018
unigram language model subword regularization
sentencepiece precompiled_charsmap nmt_nfkc
Viterbi tokenization unigram
全角でも、句読点を入れても、同じように届くか。第一章はブラウザで試せます。プロフィールのリンクから入れます。