形態素解析をせず、文字の 1〜3 文字で当てる
Matching with 1- to 3-character n-grams instead of morphological analysis
D02-4-T04-char-ngram-tfidf・技術・日本語入力でプレイする仕組み
「昨日の夜どこいた」と入力すると、助詞が抜けていても、佐伯の居場所を尋ねる意図に届きます。
単語に切らず、文字の並びを数えているからです。
名前で言えば character n-gram と tf–idf と cosine similarity。昔からある組です。
『霧走町 流氷に眠る』では、入力された日本語を、意図ごとに書いた言い換えの辞書と比べ、いちばん近い意図の証言を返します（返事は全部書き下ろしで、遊んでいる間に文は作りません）。
比べる物差しは二つあります。文字の側（表層）と、意味の側（文の埋め込み）。
この回は表層の側です。今日の版で言い換えは 2,845 文、意図は 248 個です。
この回の位置と、前後の回#
区切り: T03〜T24 日本語入力を解いて返すまで（22 回のうち 2 回目）
先に読むとよい回: T03（文字の正規化）
次に読む回: T05（文の埋め込み）
名前 — character n-gram#
- 正式名
- character n-gram（文字 n-gram）／term frequency–inverse document frequency（tf–idf）／cosine similarity（ベクトル空間モデル vector space model の上の）
- 日本語の呼び名
- 文字 n-gram、TF-IDF、コサイン類似度
初出:
IDF（逆文書頻度）は Karen Spärck Jones, "A statistical interpretation of term specificity and its application in retrieval", Journal of Documentation 28(1), 1972。
ベクトル空間モデルは Salton, Wong & Yang, "A vector space model for automatic indexing", Communications of the ACM 18(11), 1975。
文字 n-gram を言語に依らない類似度に使った代表は Damashek, "Gauging Similarity with n-Grams: Language-Independent Categorization of Text", Science 267, 1995（英語と日本語の例があります）。分類では Cavnar & Trenkle, "N-Gram-Based Text Categorization", SDAIR-94, 1994。
「tf–idf」という呼び名を最初に使った文献は、確かめられませんでした。
一般の解説 — character n-gram#
ベクトル空間モデル（vector space model）とは、文書を「特徴の重みの並び」で表し、二つの並びの角度（cosine similarity）で近さを測る考え方です。
特徴を単語にするか、文字の連なりにするかが、言語ごとの分かれ道です。
文字 n-gram（character n-gram）とは、文字列を n 文字ずつずらして切り出したものです。
「どこにいた」の 2-gram は「どこ・こに・にい・いた」。
分かち書きの無い日本語・中国語では、単語に切る前の手として古くから使われてきました。Lucene の CJK の解析器も、隣り合う 2 文字（bigram）を索引にします。
利点は三つです。辞書が要らない。誤字・語順違い・助詞の抜けに強い。未知の固有名詞にもそのまま効く。
重みは tf と idf の積です。
tf（term frequency）は、その文書の中での出現回数。生の回数、1+log、有無だけ、などの流儀があります。
idf（inverse document frequency）は、多くの文書に出る特徴ほど軽くする重みです。
Spärck Jones の 1972 年の論文の主張は、語の「特定性」を意味ではなく使われ方の統計で測れ、というものでした。
式は idf = log(N / df) が基本です。N は文書の数、df はその特徴を含む文書の数。
0 割りと、全文書に出る特徴の重みが 0 になるのを避けて、平滑化した形もよく使われます。たとえば scikit-learn の既定は ln((1+N)/(1+df)) + 1 です。
二つの重みの並びを L2 正規化すると、内積がそのままコサインになります。
0 が無関係、1 が同じ向きです。
よく知られた弱点は次のとおりです。
意味を見ません。「晩飯のあと」と「夜の居場所」は、文字が重ならなければ 0 です。
短い文ほど特徴が少なく、点が不安定です。
「ですか」「ました」のような、どの文にもある語尾が点を稼ぎます（idf がある程度は抑えます）。
特徴の種類が増えると次元が大きくなるので、大きな集合ではハッシュで畳む（feature hashing）のが普通です。
実際の検索では、tf の飽和と文書長の補正を入れた BM25（k1≈1.2、b≈0.75 あたりが定番）が、素の tf–idf より強い基準として使われます。
うちの実装 — character n-gram#
場所は Plugins/KaedeAdv/Source/KaedeAdv/Private/core/AdvMatcher.hpp です。
特徴は、正規化（昨日の夕方の T03 の norm/1）を通した文字列の、1-gram・2-gram・3-gram です。
キーは 64bit に詰めます。ソースから写しました。
using SparseVec = std::map<uint64_t, double>;
inline constexpr double kUnigramWeight = 0.5;
inline void AddGrams(const std::vector<char32_t>& Chars, SparseVec& Tf)
{
for (char32_t C : Chars)
{
Tf[((uint64_t)1 << 61) | (uint64_t)C] += kUnigramWeight;
}
for (size_t i = 0; i + 1 < Chars.size(); ++i)
{
Tf[((uint64_t)1 << 62) | ((uint64_t)Chars[i] << 21) | (uint64_t)Chars[i + 1]] += 1.0;
}
for (size_t i = 0; i + 2 < Chars.size(); ++i)
{
Tf[((uint64_t)Chars[i] << 42) | ((uint64_t)Chars[i + 1] << 21) | (uint64_t)Chars[i + 2]] += 1.0;
}
}
コードポイントは 21bit に収まるので、3-gram は 21bit×3＝63bit に入ります。
2-gram はビット 62、1-gram はビット 61 に印を立てて区別します。
3-gram の先頭の文字が U+80000 以上なら、ビット 61・62 の印と重なりえます。そこは未割り当ての面と私用面で、日本語の入力では起きません。
ハッシュで畳まないので、特徴どうしの衝突はありません。
tf は生の出現回数です。1-gram だけ 0.5 倍します。
idf は起動時に作ります。全部の言い換えを 1 文 1 文書として、特徴ごとに何文に出たかを数えます。
double Idf(uint64_t K) const
{
const auto It = Df.find(K);
const double D = (It != Df.end()) ? It->second : 0.0;
return std::log((N + 1.0) / (D + 1.0)) + 1.0;
}
N は言い換えの数（今日 2,845）です。
全文書に出る特徴の idf は 1.000、1 文にしか出ない特徴は 8.26 になります。
辞書に一度も出ない特徴は、df=0 で 8.95 です。
言い換えの側は、build で AddGrams → idf を掛ける → L2 正規化、まで済ませて持ちます。
入力の側も、query の頭で同じことをします。
const std::vector<char32_t> Norm = NormalizeText(InputUtf8);
SparseVec Q;
AddGrams(StripAttitudes(Norm), Q); // 態度語は照合に使わない（段の選択にだけ使う）
for (auto& [K, W] : Q) { W *= Idf(K); }
L2Normalize(Q);
内積は、小さい方の map を回して大きい方を引きます。
const SparseVec& S = (A.size() <= B.size()) ? A : B;
const SparseVec& L = (A.size() <= B.size()) ? B : A;
for (const auto& [K, V] : S)
{
const auto It = L.find(K);
if (It != L.end()) { Sum += V * It->second; }
}
言い換えは中央値 13 文字、最長 38 文字なので、1 本の特徴は数十個です。
2,845 本を毎手すべて回します。転置索引は作っていません。
今日のこの PC のコマンドライン版で、新しい文を 1 つ入力する 1 手が 16〜18ms でした（埋め込みの計算と、その後の判定を含む全体）。
意図の点は、その意図の言い換えの中の最大値です。
1 つの意図に平均 11.5 本の言い換えがあり、どれか 1 本に近ければよい、という当て方です。
態度を表す語（強く・丁寧に、など、同じ話題の中で返事の段を選ぶのに使う語）は、照合の前に入力からも辞書からも取り除きます（StripAttitudes）。
残すとベクトルが薄まり、強い言い方をしたときだけ意図に届かなくなったからです。
実際の値 — character n-gram#
今日（10月29日）、港で佐伯に入力した文の、表層の点です。
「昨日の夜はどこにいた」は辞書にある文そのもので、1.000 です。
▶ 昨日の夜どこいた 0.411（「は」「に」が抜けた）
▶ どこにいた、昨日の夜は 0.757（語順を入れ替えた）
▶ 昨日の夜はどこいいた 0.654（入力の間違い）
▶ きのうのよるはどこにいた 0.282（全部ひらがな）
▶ 事件の夜の行動を教えてください 0.526
▶ 晩飯のあとはどうしてたんだ 0.156（文字がほとんど重ならない）
語順を入れ替えても、2・3-gram の大半が残るので点はあまり落ちません。
入力の間違いは、間違えた文字を含む gram だけが消えます。
全部ひらがなにすると、漢字の gram がすべて消えて 0.282 まで下がります。
「晩飯のあと」は表層ではほぼ届かず、意味の側（明日の夕方の T05）に任せることになります。
表層だけだと、どれだけ当たるか#
adv-sim golden は、閾値を上書きして検査セットを流せます（Game/adv/thresholds.json は書き換えません）。
--embed 0 にすると、埋め込みを混ぜずに表層だけで判定します。数字は ACC（正しい意図に 1 回で着地した率）です。
表層だけ／いまの設定（埋め込みと混ぜる）
凍結した 176 件 97.7%／100%
進行に要る入力 244 件 73.0%／88.9%
自然な文 67 件 86.6%／100%
人物像を変えた入力 120 件 69.2%／83.3%
短い文 74 件 91.9%／95.9%
雑談 67 件 46.3%／71.6%
短い文では表層だけでも 9 割を超えます。
進行に要る入力では、4 件に 1 件以上を外します。
雑談がいちばん弱いのは、雑談の言い方が言い換えの辞書から最も遠いからです。
境界の扱い — character n-gram#
空の入力（または全部が記号で、正規化すると空になる入力）は、特徴が 1 つもありません。L2Normalize は二乗和が 0 なら何もしないので、どの言い換えとも内積 0 です。
1 文字の入力（「港」）は 1-gram だけ、2 文字の入力は 1-gram と 2-gram だけで比べます。1-gram の重み 0.5 が効くのはこういう短い入力です。
辞書に無い特徴は、内積には寄与しませんが、入力の側の正規化の分母には入ります。知らない語が多い入力ほど、知っている部分の点まで薄まります。
同点は、厳密な「より大きい」で 1 位を更新するので、先に見た意図が残ります。候補は std::map<const Intent*, double> に入っていて、並びは読み込んだ順の意図のアドレス順です。乱数も時刻も使わないので、同じ入力からは同じ 1 位が出ます。
1 位と 2 位の差（Margin）は、候補が 1 つ以下なら -1 を返します。
名前どおりでない所 — character n-gram#
一つ目。1-gram を重み 0.5 で混ぜています。
文字 n-gram は 1 つの n か、2 と 3 のように近い n を並べるのが普通です。
2・3-gram だけだと、「恨んでる」と「恨みを持つ」のように活用が違うだけで一致が 0 になり、短い文ほど不利でした（2026-08-03 に入れました）。
1-gram は語幹の 1 文字の一致を拾います。ただし、どの文にもある文字の点も拾うので、重みを半分にしています。
二つ目。文書は「意図」ではなく「言い換え 1 本」です。
idf は言い換え 1 本を 1 文書として数え、意図の点は言い換えの最大値です。
言い換えの多い意図は、その意図の語の idf を自分で下げます。
三つ目。tf は生の回数で、BM25 のような飽和も長さの補正もありません。
言い換えが短く、長さがそろっているので、補正の効き目は小さいと見ています。BM25 は試していません。
それ以外は名前どおりです（tf × idf、L2 正規化、内積＝コサイン）。
弱点と、採らなかった案 — character n-gram#
形態素解析は採っていません。
辞書と解析器が要り、UE・CLI・Linux のサーバの三つに同じ版を持ち込むことになります。誤字や助詞の抜けがあると、切れ目そのものを間違えます。開発の初めに比べて、文字 n-gram の方が強かったので、こちらにしました。
idf を 1.5 乗して鋭くする案は、試して全部の検査の点が下がったので採っていません。語尾より先に話題の語まで削れたと見ています。
意味は見ません。表層の点が高くても違う話のことがあり、低くても同じ話のことがあります。
その穴は、意味の側（文の埋め込み）と混ぜて埋めています。混ぜ方は T08 で書きます。
検索語#
character n-gram tf-idf cosine similarity
inverse document frequency Spärck Jones 1972
Damashek 1995 n-grams language-independent
CJK bigram indexing
助詞を抜いても、語順を入れ替えても、入力を間違えても届くか。第一章はブラウザ版で入力して確かめられます。プロフィールのリンクからどうぞ。