charsim: 参照平均型の文字 n-gram 類似度

0. この指標が解きたい問題

ある文字列が「いくつかの正解例にどれだけ似ているか」を、1文単位で数値にしたい場面があります。たとえば、生成モデルが出した候補を参照文と突き合わせて順位づけしたり、しきい値で足切りしたりするときです。

このとき欲しい性質は、だいたい次の4つに集約できます。

内容が参照に近いほどスコアが上がる。
参照より短すぎる候補（情報の取りこぼし）にはペナルティがかかる。
参照より長すぎる候補（余計な水増し）にもペナルティがかかる。
正解が複数あるとき、「たまたま1本だけに合っている候補」を過大評価しない。

既存の表層指標（BLEU や chrF など、文字列の一致だけからスコアを出す指標群）でもこれらは扱えますが、1文単位で使うと扱いづらい点が残ります。BLEU は短さの罰を本体とは別の項（brevity penalty）で入れ、ある次数で一致が0になると文スコア全体が0に崩れます。chrF は precision と recall を最後に F 値で合成するため、「短さと長さのどちらが効いているのか」が式から読み取りにくく、複数参照の扱い方も実装によって割れます。

charsim は、これらの性質を1本の式の中にまとめることを狙った指標です。中心となる考え方は一つだけで、各参照に対して precision と recall の小さい方を取り、それを参照全体で平均する、というものです。precision と recall の min を取ることで、長すぎても短すぎても自動的にペナルティがかかります。参照ごとに評価してから平均することで、複数参照を「平均的にどれだけ支持されるか」として読めます。

以下では、まずこの考え方をそのまま式にした基本形を示し、続いて実装・高速化に向いた簡約版を主定義として導入します。最後に BLEU / chrF などと比較します。

1. 記法

1.1 入力

1文単位の評価を考えます。

評価したい文字列（ターゲット）を $t$
参照文を $r$
複数の参照文の集合を $\mathcal{R} = \{r^{(1)}, \dots, r^{(K)}\}$

と書きます。

1.2 文字 n-gram

各文字列 $x$ について、$n = 1, 2, \dots$ の各次数で文字 $n$-gram を取り出します。次数 $n$ に定義上の上限はありません。ただし $n$ が比較対象の文字列長を超えると、n-gram は必ず境界記号の側へはみ出すようになり、内容の違いを反映しなくなります。そのため実効的な上限は文字列長で決まります（具体的な打ち切りは 2.5 で述べます）。

先頭・末尾の情報を扱うため、文字列の前後に境界記号を補ってから n-gram を取り出します。開始境界を ^、終了境界を $ と書くと、たとえば cat の 3-gram は、境界をまたぐものも含めて ^^c, ^ca, cat, at$, t$$ のように数えます。ただし、^^^ や $$$ のような境界記号だけからなる n-gram は数えません（内容を持たないため）。こうしておくと、前後に補う境界記号の個数によらず、有効な n-gram の総数は一定になります。

文字数を $|x|$ とすると、その有効な n-gram の総数は次のようになります。

\[ L_x^{(n)} = |x| + n - 1 \]

1.3 n-gram 頻度と重なり

文字列 $x$ における文字 $n$-gram $g$ の出現回数を $c_x^{(n)}(g)$ と書きます。以降の $\sum_g$ は、その次数で現れうる相異なる n-gram 型にわたる和です。

charsim は、同じ $g$ が1文中に複数回出たらその回数も評価に反映します。2つの文 $x, y$ の重なり個数は次で測ります。

\[ \sum_g \min\bigl(c_x^{(n)}(g),\, c_y^{(n)}(g)\bigr) \]

これは多重集合としての共通要素数にあたり、片方より多く繰り返しても、少ない側の回数で頭打ちになります。BLEU や chrF と同じ「多重集合 overlap」の考え方です。

2. 基本形

理屈の上で最もまっすぐな定義から示します。

2.1 各参照との重なり

参照 $r^{(i)}$ に対する次数 $n$ の重なりを次のように定めます。

\[ o_i^{(n)}(t) = \sum_g \min\bigl(c_{r^{(i)}}^{(n)}(g),\, c_t^{(n)}(g)\bigr) \]

これは、ターゲットと参照の文字 $n$-gram 多重集合がどれだけ共通かを表します。

2.2 長さで正規化する

ターゲットと参照の有効 n-gram 数を以下とします。

\[ L_t^{(n)} = |t| + n - 1, \qquad L_i^{(n)} = |r^{(i)}| + n - 1 \]

これを用いて、次数別スコアを次で定めます。

\[ \rho_i^{(n)}(t) = \frac{o_i^{(n)}(t)}{\max\bigl(L_t^{(n)},\, L_i^{(n)}\bigr)} \]

分母に長い方を取るのがポイントです。重なりは $o_i^{(n)}(t) \le L_t^{(n)}$ かつ $o_i^{(n)}(t) \le L_i^{(n)}$ を満たすので、

\[ o_i^{(n)}(t) \le \min\bigl(L_t^{(n)}, L_i^{(n)}\bigr) \le \max\bigl(L_t^{(n)}, L_i^{(n)}\bigr) \]

となり、$0 \le \rho_i^{(n)}(t) \le 1$ が常に成り立ちます。

2.3 これは min(precision, recall) である

precision と recall を以下のように書きます。

\[ P_i^{(n)}(t) = \frac{o_i^{(n)}(t)}{L_t^{(n)}}, \qquad R_i^{(n)}(t) = \frac{o_i^{(n)}(t)}{L_i^{(n)}} \]

分母に長い方を取ったことは分数を小さい方に取ることと同じなので、次が成り立ちます。

\[ \rho_i^{(n)}(t) = \frac{o_i^{(n)}(t)}{\max(L_t^{(n)}, L_i^{(n)})} = \min\bigl(P_i^{(n)}(t),\, R_i^{(n)}(t)\bigr) \]

これが charsim の核心です。

ターゲットが長すぎると分母が $L_t^{(n)}$ になり、precision 側が効く。
ターゲットが短すぎると分母が $L_i^{(n)}$ になり、recall 側が効く。
長さが近ければ重なりそのものが効く。

長さの罰を別項で足すのではなく、長短どちらの場合も同じ1本の式が処理します。

2.4 複数参照をまとめる

次数 $n$ の複数参照スコアは、各参照スコアの平均とします。

\[ \rho_n^{\ast}(t) = \frac{1}{K}\sum_{i=1}^{K} \rho_i^{(n)}(t) = \frac{1}{K}\sum_{i=1}^{K} \frac{o_i^{(n)}(t)}{\max\bigl(L_t^{(n)}, L_i^{(n)}\bigr)} \]

2.5 次数をまとめて最終スコアに

高次の n-gram が効きすぎないよう、各次数を $1/n$ で重み付けします。次数に固定の上限は設けず、$n$ は比較対象の最長文字列の長さ

\[ N = \max\bigl(|t|,\ \max_i |r^{(i)}|\bigr) \]

まで動かします。$N$ より大きい次数では、n-gram がどの文字列の内容にも収まりきらず境界記号の繰り返しが支配的になって内容を区別しなくなるため、ここで打ち切ります。正規化定数を

\[ H_N = \sum_{n=1}^{N}\frac{1}{n} \]

とおくと、基本形は次のようになります。

\[ \boxed{\;\operatorname{charsim}_{\mathrm{base}}(t;\mathcal R) = \frac{1}{H_N} \sum_{n=1}^{N} \frac{1}{n}\,\rho_n^{\ast}(t)\;} \]

$N$ は入力に応じて決まる値で、固定の定数ではありません。短い文字列どうしなら数項で和が終わり、長い文字列ならその長さまで自然に項が増えます。

2.6 基本形の性質

参照ごとに分母を取るので、長さ補正が参照ごとに正確に入る。
各次数のスコアがそのまま $\min(P, R)$ と読める。
単一参照に対する完全一致はちょうど1になる。
同じ参照文を重複して追加しても値は変わらない。

弱点は実装にあります。参照ごとに分母 $\max(L_t^{(n)}, L_i^{(n)})$ が変わるため、参照集合を一度前計算して大量のターゲットを高速に捌く、という使い方に向きません。そこで実用上は、次の簡約版を主定義に据えます。

3. 主定義（簡約版）

3.1 分子と分母を別々に平均する

基本形は参照ごとに分数を作ってから平均しました。簡約版は、分子（重なり）と分母（長さ）をそれぞれ先に平均してから割ります。

分子は平均重なりです。

\[ b_n(t) = \frac{1}{K}\sum_{i=1}^{K} o_i^{(n)}(t) = \frac{1}{K}\sum_{i=1}^{K} \sum_g \min\bigl(c_{r^{(i)}}^{(n)}(g),\, c_t^{(n)}(g)\bigr) \]

分母は平均参照長です。

\[ \bar L_r^{(n)} = \frac{1}{K}\sum_{i=1}^{K} L_i^{(n)} \]

これを用いて、次数別スコアを次で定めます。

\[ \rho_n(t) = \frac{b_n(t)}{\max\bigl(L_t^{(n)},\, \bar L_r^{(n)}\bigr)} \]

各参照で $o_i^{(n)}(t) \le L_t^{(n)}$ かつ $o_i^{(n)}(t) \le L_i^{(n)}$ なので、平均しても $b_n(t) \le L_t^{(n)}$ かつ $b_n(t) \le \bar L_r^{(n)}$ が保たれ、ここでも $0 \le \rho_n(t) \le 1$ です。

最終スコアは基本形と同じ形でまとめます。

\[ \boxed{\;\operatorname{charsim}(t;\mathcal R) = \frac{1}{H_N} \sum_{n=1}^{N} \frac{1}{n}\,\rho_n(t)\;} \]

展開すると次のとおりです。

\[ \operatorname{charsim}(t;\mathcal R) = \frac{1}{H_N} \sum_{n=1}^{N} \frac{1}{n} \cdot \frac{\dfrac{1}{K}\sum_{i=1}^{K} \sum_g \min\bigl(c_{r^{(i)}}^{(n)}(g),\, c_t^{(n)}(g)\bigr)}{\max\bigl(L_t^{(n)},\, \bar L_r^{(n)}\bigr)} \]

3.2 なぜ平均長を使うのか

参照長の代表値に中央値ではなく平均を選ぶのは、分子がすでに平均だからです。分子と分母で集約のしかたをそろえると、各参照の不等式 $o_i^{(n)}(t) \le L_i^{(n)}$ を平均した

\[ b_n(t) \le \frac{1}{K}\sum_i L_i^{(n)} = \bar L_r^{(n)} \]

がそのまま分母の上界になり、$\rho_n \le 1$ が代数的に保証されます。中央値は外れ値に強い一方、分子が平均である以上ひと手間ヒューリスティックが混ざります。整合性を取るなら平均、外れ値に強い「典型長」が欲しいなら中央値、という整理で、本稿は平均を主定義とします。

3.3 基本形との違い

簡約版は基本形と厳密には一致しません。基本形が「割ってから平均」

\[ \frac{1}{K}\sum_i \frac{o_i}{\max(L_t, L_i)} \]

であるのに対し、簡約版は「平均してから割る」

\[ \frac{\frac{1}{K}\sum_i o_i}{\max(L_t, \bar L_r)} \]

だからです。それでも簡約版を主定義に据えるのは、(1) 分母が1本にまとまり式が簡潔になること、(2) 前計算による高速化がしやすいこと（→ 7章）、(3) 短ければ recall 的・長ければ precision 的という基本形の直感をほぼそのまま保てること、の3点によります。

4. 簡約版はどう振る舞うか

以下、主定義 $\rho_n(t) = b_n(t) / \max(L_t^{(n)}, \bar L_r^{(n)})$ の挙動を場合分けで見ます。

4.1 長さも内容も近いとき

$L_t^{(n)} \approx \bar L_r^{(n)}$ で重なりがほぼ最大なら、$b_n(t) \approx L_t^{(n)} \approx \bar L_r^{(n)}$ なので $\rho_n(t) \approx 1$ です。狙いどおり、似ているほど1に近づきます。

4.2 ターゲットが短すぎるとき

$L_t^{(n)} < \bar L_r^{(n)}$ なら分母は $\bar L_r^{(n)}$ になります。

\[ \rho_n(t) = \frac{b_n(t)}{\bar L_r^{(n)}} \]

たとえばターゲットが参照の前半（prefix）と完全一致していても、重なりはせいぜい $L_t^{(n)}$ 止まりなので

\[ \rho_n(t) \lesssim \frac{L_t^{(n)}}{\bar L_r^{(n)}} \]

となり、短さがそのまま recall 的なペナルティになります。前半が完璧でも後半をまるごと欠いていれば1にはならない、という妥当な挙動です。

4.3 ターゲットが長すぎるとき

$L_t^{(n)} > \bar L_r^{(n)}$ なら分母は $L_t^{(n)}$ になります。

\[ \rho_n(t) = \frac{b_n(t)}{L_t^{(n)}} \]

参照全体を含みつつ余計な後半（suffix）を大量に足したターゲットでは、重なりは参照長あたりで頭打ちになるので

\[ \rho_n(t) \lesssim \frac{\bar L_r^{(n)}}{L_t^{(n)}} \]

となり、水増しに対して precision 的なペナルティがかかります。参照を丸ごと含んでいても、余計なものを足せば「似ている」とは言いにくい、という妥当な挙動です。

4.4 一致が増えるとどれだけ上がるか

長さを固定すると、$\rho_n(t)$ は平均重なり $b_n(t)$ に対して線形です。

\[ \rho_n(t) = \frac{b_n(t)}{\text{(固定の分母)}} \]

なので、一致が1個増えればスコアは一定幅だけ上がります。BLEU の幾何平均でも chrF の F 値合成でもないため、「どれだけ一致すればどれだけ上がるか」が読みやすいのが利点です。

具体的に $L_t^{(n)} = \bar L_r^{(n)} =: L^{(n)}$ とし、取りこぼしを $\Delta_n$ として $b_n(t) = L^{(n)} - \Delta_n$ なら

\[ \rho_n(t) = 1 - \frac{\Delta_n}{L^{(n)}} \]

です。各次数は「取りこぼした n-gram の割合」だけ素直に下がります。たとえば長さそのままで1文字だけタイプミスを直すと、低次の n-gram への影響は小さく、その位置をまたぐ高次の n-gram が一気に回復します。charsim ではその回復が各次数で線形に効き、$1/n$ 重みで合成されるので、1文字の修正がどの次数でどれだけ効いたかを追え、かつ高次一致が暴れすぎません。

4.5 完全一致とその近傍

単一参照 $\mathcal R = [s]$ に対して $t = s$ なら、各次数で $b_n(s) = L_s^{(n)}$ かつ $\bar L_r^{(n)} = L_s^{(n)}$ なので $\rho_n(s) = 1$、したがって $\operatorname{charsim}(s; [s]) = 1$ です。そこから1文字ずつ違いを増やすと、その位置をまたぐ n-gram だけが次数ごとに失われ、スコアは連続的・段階的に下がります。完全一致から少し離れたら少しだけ下がる、という直感に合います。

4.6 同じ断片の繰り返し

重なりを $\min(c_r^{(n)}(g), c_t^{(n)}(g))$ で数えるので、繰り返された断片もその回数ぶん拾えますが、参照側の回数で頭打ちです。したがって、参照にも繰り返しがあればきちんと拾い、ターゲット側だけが過剰に繰り返してもそれ以上は加点されません。

5. BLEU / chrF と比べてどこが読みやすいか

charsim の利点は、「何を測っているか」が式にそのまま出ていることです。

5.1 長さの扱いが1本の式で完結する

BLEU は本体が precision で、短さは brevity penalty という別項でした。chrF は precision と recall を別々に出して最後に F 値で合成しました。charsim では各参照・各次数が

\[ \frac{o_i^{(n)}(t)}{\max(L_t^{(n)}, L_i^{(n)})} = \min\left( \frac{o_i^{(n)}(t)}{L_t^{(n)}},\, \frac{o_i^{(n)}(t)}{L_i^{(n)}} \right) \]

であり、長すぎる場合も短すぎる場合も最初から同じ式の中で処理されます。長さ整合性が「似ている」の定義そのものに含まれているわけです。

5.2 sentence-level で壊れにくい

BLEU は高次 n-gram の一致が0になるとその次数の precision が0になり、文 BLEU 全体が崩れがちで、smoothing がほぼ必須です。charsim は各次数を $[0,1]$ に正規化してから加重平均するだけなので、高次一致が0でもその次数が0になるだけで、全体が不連続には落ちません。文単位の順位づけや足切りでは実用上大きな差です。

5.3 複数参照の意味が明確

BLEU の複数参照は語ごとに最大参照カウントで clip するため union 的で、chrF も best-ref / average が実装で揺れます。charsim は基本形が $\frac{1}{K}\sum_i \min(P_i, R_i)$、簡約版でも分子が「各参照との重なりの平均」なので、参照を1本ランダムに引いたときどれだけ合っているかの期待値として読めます。1本だけに偶然合う候補を持ち上げにくいのが利点です。

5.4 各次数の寄与が線形で診断しやすい

最終形が $\sum_n \frac{1}{n}\rho_n$ 型なので、どの次数がどれだけ効いたかを直接追えます。BLEU の幾何平均は「どこかが悪いと全体が引きずられる」構造で、chrF の F 値も最終的に P/R をまとめてしまいます。charsim は次数ごとの寄与が見えるぶん診断に向きます。

5.5 文字ベースの柔らかさは chrF と共有

charsim は単語ではなく文字 n-gram を使うので、活用の違い・かな漢字や表記ゆれ・軽微なスペル差・複合語の分割差に滑らかに反応します。これは chrF と同じ方向の強みです。違いは、charsim が「各参照ごとの $\min(P, R)$ を平均」という形のため、より局所的に解釈しやすい点です。F 値は片側だけ高くてもある程度点が出ますが、$\min(P, R)$ は precision か recall のどちらかが低ければそのまま下がる保守的な設計です。

6. 他指標との対応表

指標	基本単位	P/R の扱い	複数参照	文字ベースの柔らかさ
charsim	文字 n-gram	各参照で $\min(P,R)$	参照平均（average-ref）	あり
BLEU	単語 n-gram	precision + 別項の BP	clip（union 的）	なし
chrF	文字 n-gram	P/R を F 値で合成	実装依存	あり
chrF++	文字 + 短い単語 n-gram	P/R を F 値で合成	実装依存	あり（語順感度を一部回復）
ROUGE-N / L	単語 n-gram / LCS	recall 寄り	実装依存	なし
METEOR	単語 alignment	recall 重め（Fmean）+ chunk penalty	alignment ベース	語彙資源で柔らかい

補足は以下の通りです。

BLEU: 短さの罰が本体と分離し、文単位では smoothing がほぼ必須。clip により「1本でも持っていれば救われる」のに対し、charsim は参照平均で「どれだけ広く支持されるか」を見ます。
chrF: F 値はバランスがよい一方、片側だけ高くても点が出ます。charsim の $\min(P,R)$ はより保守的です。
chrF++: 単語 n-gram を足して語順感度を一部戻した指標。語順や単語単位の整合を強く見たいなら chrF++ に分があり、tokenization 非依存や文字の連続一致を見たいなら charsim が向きます。
ROUGE: recall 寄り（ROUGE-L は LCS 系）。charsim は長い候補では precision 側にも切り替わるので、被覆率と冗長さを同時に見たいときに向きます。
METEOR: 語彙資源と alignment を使う richer な指標。charsim はそこまで使わない代わりに、軽く・実装しやすく・式の意味が単純で・多参照の平均支持という解釈が明確です。

7. 実装メモ

7.1 ナイーブ実装

各次数 $n$ について、(1) ターゲット $t$ の文字 n-gram 頻度表を作り、(2) 各参照 $r^{(i)}$ の頻度表と重なりを取り、(3) 基本形または簡約版の式で $\rho_n$ を計算し、(4) $1/n$ 重みで平均する、で済みます。

7.2 参照固定なら簡約版が有利

参照集合を固定して大量のターゲットを評価するなら、簡約版が明確に有利です。各問い合わせで必要なのは、平均重なり $b_n(t)$、ターゲット長 $L_t^{(n)}$、参照側の固定量 $\bar L_r^{(n)}$ の3つだけです。

具体的には、各次数 $n$・各 n-gram $g$ について

\[ F_g^{(n)}(m) = \frac{1}{K}\sum_{i=1}^{K} \min\bigl(c_{r^{(i)}}^{(n)}(g),\, m\bigr) \]

を前計算しておくと、ターゲット側頻度 $c_t^{(n)}(g)$ に対して

\[ b_n(t) = \sum_g F_g^{(n)}\bigl(c_t^{(n)}(g)\bigr) \]

で求まり、ターゲットに出た n-gram だけ見れば足ります。さらに $\min(c, m) = \sum_{a=1}^{m}\mathbf 1[c \ge a]$ を使えば、各 $g$ について「何本の参照が1回以上・2回以上・… 持つか」という累積頻度表で $F_g^{(n)}$ をコンパクトに表現できます。

7.3 平均長版と中央値版

主定義は平均長版ですが、参照長の外れ値が極端で典型長を使いたい場合は、分母を $\max(L_t^{(n)}, \operatorname{median}_i L_i^{(n)})$ とする variant も考えられます。ただし分子が平均である以上、主定義よりヒューリスティック色が強くなります。

8. まとめ

charsim は、文字 n-gram の重なりを使って、複数参照に対する平均的な支持を測る表層類似度です。

基本形は、各参照ごとに $\min(P, R)$ を取り、それを平均する。
主定義（簡約版）は、平均重なりを平均参照長と組み合わせて $\rho_n = b_n / \max(L_t, \bar L_r)$ とする。
最終的に各次数を $1/n$ 重みで平均する。

この設計により、(1) sentence-level で壊れにくく、(2) 短すぎる候補にも長すぎる候補にも1本の式で対応でき、(3) 参照平均型なので多参照の意味づけが明確で、(4) 文字ベースなので表記差に比較的強く、(5) 簡約版は前計算しやすく大量評価に向く、という性質が得られます。

BLEU や chrF が強力な標準指標であることは変わりませんが、1文単位の滑らかな比較・多参照の平均支持・長さ差の対称的な扱いを重視するなら、charsim は素直で扱いやすい選択肢です。

9. 参考文献

この指標を考える前段階として、以下の自分たちの論文で文字 n-gram に基づく表層マッチング型の評価手法を実装・検討しています。

今城健太郎, 平野正徳, 鈴木脩司, 三上裕明. pfgen-bench: 日本語事前学習モデルのための文章生成性能評価ベンチマーク. Jxiv, 2024. 初期の Q&A ベンチマーク向け実装で、参照回答群中の文字 n-gram 出現頻度を足し上げる設計であり、同じ n-gram が複数回出たときの回数を現在の $\min(c_r,c_t)$ のような多重集合 overlap としては区別していませんでした。
今城健太郎, 平野正徳. 高精度翻訳モデルのための自動評価手法の検討. Jxiv, 2026. 文字 n-gram の出現回数を $f_{w,i}$ で扱う一方、長さ補正は参照訳長の中央値に対する別の罰則項として置いており、本稿のように各次数で平均 overlap を $\max(L_t,\bar L_r)$ で正規化する形とは異なります。