Skip to content

fix(dedup): map exact-substring ranges to original text - #516

Open
Excelius-Wang wants to merge 1 commit into
huggingface:mainfrom
Excelius-Wang:fix/exact-substrings-unicode-offsets
Open

Excelius-Wang wants to merge 1 commit into
huggingface:mainfrom
Excelius-Wang:fix/exact-substrings-unicode-offsets

Conversation

@Excelius-Wang

@Excelius-Wang Excelius-Wang commented Aug 27, 2026

Copy link
Copy Markdown

Summary

  • map duplicate token ranges through tokenizer offsets instead of decoded-string replacement
  • merge overlapping ranges and remove only the detected spans from the original text
  • include trailing combining marks omitted from tokenizer offset alignment
  • retain the decode-based sync fast path for documents without duplicate ranges
  • add regressions for Unicode normalization, repeated occurrences, multibyte characters, and overlapping ranges

Problem

ESRangeRemover currently decodes duplicate token IDs and removes the decoded string with
str.replace. This assumes encoding and decoding round-trip to the same Unicode code points. With
tokenizer normalization, decomposed text such as u\u0303 can encode to the same token as NFC ũ
but decode to different underlying text, causing the Stage 3 sync check or duplicate removal to fail.
str.replace can also remove identical occurrences that were not part of the detected token range.
Some normalizers also omit a trailing combining mark from the aligned token offset, so the mapped
text span must include unaligned marks attached to its final character.

This follows the retokenization-and-offset direction suggested in #121 and leaves all three stage
file formats unchanged.

Validation

  • pytest -q tests/pipeline/dedup — 27 passed, 3 existing lighteval/NumPy 2.0 skips
  • make quality
  • git diff --check

Synthetic Stage 3 benchmark: 10,000 documents, 50 tokens per document, five-run median. Stage 1 and
Stage 2 are excluded from timing.

Documents with duplicate ranges main This PR Python peak memory (main → PR)
1% 0.521 s 0.533 s 0.128 MiB → 0.133 MiB
100% stress case 1.092 s 1.931 s 3.24 MiB → 3.85 MiB

The common no-range path keeps the existing decode check. Re-tokenization is limited to documents
with duplicate ranges, or to the non-round-trippable fallback needed for token-ID synchronization.

This is related to #121 but does not change the Stage 1 uint16 token format; tokenizers with IDs
above 65,535 remain outside this PR's scope.


Note

Medium Risk
Changes core dedup text mutation logic for exact substrings; incorrect offset mapping could drop wrong spans, though behavior is guarded by asserts and new regression tests.

Overview
Stage 3 exact-substring dedup no longer decodes duplicate token spans and strips them with str.replace. Duplicate byte ranges are converted to token indices, mapped to character spans in the original doc.text via the tokenizer’s encode offsets, with trailing combining marks included when normalization left them outside the offset window. Overlapping spans are merged, then removed by slicing the original string (newest ranges first).

Documents without duplicate ranges keep a lightweight sync path (decode comparison, with encode-ID assert only when decode doesn’t round-trip). The per-document decode equality assert in run() is removed in favor of checks inside remove_duplicate when ranges apply.

Tests add a normalizing tokenizer harness and cases for NFC/decomposed Unicode, single-occurrence removal, emoji offsets, and overlapping ranges.

Reviewed by Cursor Bugbot for commit 1a40e8c. Bugbot is set up for automated code reviews on this repo. Configure here.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

None yet

Projects

None yet

Development

Successfully merging this pull request may close these issues.

1 participant