Precompiled normalizer diverges from SentencePiece: shortest-prefix match + discarded remainder silently drops codepoints #2334

Summary

normalizers.Precompiled does not reproduce SentencePiece's normalization. For multi-codepoint graphemes under 6 bytes it silently deletes codepoints, producing text that SentencePiece never would.

Two independent defects compound:

1. spm_precompiled::transform() picks the shortest prefix match, not the longest. SentencePiece uses leftmost-longest matching.
2. The match is not required to cover the input chunk, and the remainder is discarded. The caller replaces the entire grapheme with the mapping of a proper prefix.

The user-visible effect: NFD-form text loses its diacritics. For example, NFD Vietnamese Tiếng Việt rất đẹp normalizes to Tiêng Viẹt rât đẹp — tone marks vanish, changing meaning. This is silent; there is no error or warning.

Reproduction

Self-contained — no model download needed. Trains a 2-rule charsmap where one rule is a proper prefix of the other.

import tempfile, os
import sentencepiece as spm
from sentencepiece import sentencepiece_model_pb2
from tokenizers import normalizers

d = tempfile.mkdtemp()

# Two rules; the first key is a proper prefix of the second.
#   U+00AA        -> U+0061
#   U+00AA U+0300 -> U+00E0
tsv = os.path.join(d, "rules.tsv")
with open(tsv, "w", encoding="utf-8") as f:
    f.write("00AA\t0061\n")
    f.write("00AA 0300\t00E0\n")

corpus = os.path.join(d, "corpus.txt")
with open(corpus, "w", encoding="utf-8") as f:
    for _ in range(200):
        f.write("hello world abcdefghijklmnopqrstuvwxyz\n")
        f.write("ª̀ ª test\n")

spm.SentencePieceTrainer.train(
    input=corpus, model_prefix=os.path.join(d, "m"), vocab_size=32,
    normalization_rule_tsv=tsv, character_coverage=1.0,
    add_dummy_prefix=False, remove_extra_whitespaces=False,
)

proto = sentencepiece_model_pb2.ModelProto()
proto.ParseFromString(open(os.path.join(d, "m.model"), "rb").read())
sp = spm.SentencePieceProcessor(model_proto=proto.SerializeToString())
hf = normalizers.Precompiled(proto.normalizer_spec.precompiled_charsmap)

U = lambda s: " ".join(f"U+{ord(c):04X}" for c in s)
for s in ["ª", "ª̀"]:
    a, b = sp.normalize(s), hf.normalize_str(s)
    print(f"{U(s):18} SP={U(a):10} HF={U(b):10} {'' if a == b else '<-- MISMATCH'}")

Output:

U+00AA             SP=U+0061     HF=U+0061
U+00AA U+0300      SP=U+00E0     HF=U+0061     <-- MISMATCH

U+0300 is dropped. Note the single-codepoint case is fine — the bug needs a multi-codepoint grapheme.

Root cause

1. transform() returns the shortest match

spm_precompiled 0.1.4 (the version tokenizers v0.22.2 resolves to, per bindings/python/Cargo.lock:1066-1067), src/lib.rs:175-191. Current master is unchanged in this logic — it differs only by a base64 API migration, which shifts these to lib.rs:178-194:

pub fn transform(&self, chunk: &str) -> Option<&str> {
    let results = self.trie.common_prefix_search(chunk.as_bytes());
    if results.is_empty() {
        None
    } else {
        let index = results[0] as usize;   // <-- results[0]

common_prefix_search (lib.rs:108-129; master: lib.rs:111-132) walks the key bytes and pushes a value at every prefix that has a leaf, so the vector is ordered by increasing prefix length. results[0] is therefore the shortest match. SentencePiece takes the longest (sentencepiece/src/normalizer.cc, NormalizePrefix).

common_prefix_search also never checks that the key was fully consumed, and it returns only values — not the match lengths — so a caller cannot tell how many bytes a match covered.

2. The caller replaces the whole grapheme

tokenizers/src/normalizers/precompiled.rs:45-53:

normalized.get().graphemes(true).for_each(|grapheme| {
    if grapheme.len() < 6 {
        if let Some(norm) = self.transform(grapheme) {
            modified = true;
            replace(&mut transformations, grapheme, norm);  // whole grapheme replaced
            return;                                          // remainder dropped
        }
    }
    ...

Walking the repro through: the grapheme is 4 bytes, so it enters the < 6 fast path. transform matches the 2-byte prefix U+00AA, returns "a", and the whole 4-byte grapheme is replaced by "a". U+0300 is gone.

The >= 6 byte path is not affected the same way — it goes per-character and the else branch (transformations.push((c, 0))) preserves unmatched characters. So the "fast path" is the one that loses data:

U+00AA U+0300          4 bytes   fast path      -> U+0061                  2 codepoints -> 1
U+00AA U+0302 U+0301   6 bytes   per-char path  -> U+0061 U+0302 U+0301    3 -> 3
U+FF76 U+FF9E          6 bytes   per-char path  -> U+30AB U+3099           2 -> 2

I realize the < 6 heuristic is deliberate and load-bearing — the comment at precompiled.rs:36-44 is explicit about that, and about it seeming broken. This report is narrower than "remove the heuristic": the data loss comes from combining the whole-chunk replacement with a shortest-prefix lookup.

Proposed fix

Replace the grapheme-segmented loop with SentencePiece's own algorithm: longest-prefix match, then advance by the number of bytes consumed.

This needs a small addition to spm_precompiled, because match lengths are currently not exposed:

// spm_precompiled: additive, non-breaking
impl Precompiled {
    /// Longest prefix match. Returns (bytes_consumed, replacement).
    pub fn transform_prefix(&self, chunk: &str) -> Option<(usize, &str)> {
        // same trie walk as common_prefix_search, but tracking byte position
        // and keeping the LAST match instead of the first
    }
}

and then in tokenizers/src/normalizers/precompiled.rs:

let mut rest = normalized.get();
while !rest.is_empty() {
    if let Some((len, norm)) = self.transform_prefix(rest) {
        replace(&mut transformations, &rest[..len], norm);
        rest = &rest[len..];
    } else {
        let c = rest.chars().next().unwrap();
        transformations.push((c, 0));
        rest = &rest[c.len_utf8()..];
    }
}

This removes the need for grapheme segmentation and the < 6 fence entirely, and mirrors normalizer.cc directly.

Scope: roughly 20 lines added in spm_precompiled and 20 lines changed in precompiled.rs. Existing transform() can stay for backwards compatibility.