token-align

token-align maps overlaps between two token sequences that represent the same text. It also maps Unicode scalar positions between two strings. The library supports no_std programs with an allocator and has no runtime dependencies.

The default comparison form removes common subword markers, ignores fixed vocabulary control tokens, applies Unicode 17.0.0 compatibility decomposition, and uses simple lowercase mappings. A custom normalizer can replace those rules.

Token alignment

use token_align::get_alignments;

let words = ["untouchable"];
let pieces = ["un", "##touch", "##able"];
let (word_to_piece, piece_to_word) = get_alignments(&words, &pieces);

assert_eq!(word_to_piece, vec![vec![0, 1, 2]]);
assert_eq!(piece_to_word, vec![vec![0], vec![0], vec![0]]);

Each outer index names an input token. Its inner list contains the overlapping indices on the other side. A token without a matched character has an empty list.

Character mapping

use token_align::get_charmap;

let (left, right) = get_charmap("Å", "A");
assert_eq!(left, vec![vec![0]]);
assert_eq!(right, vec![vec![0]]);

Character indices count Unicode scalar values.

Custom comparison forms

Implement Normalizer or pass a closure to get_alignments_with. The output string is reusable scratch space and is empty at the start of each call.

use token_align::get_alignments_with;

let strip_suffix = |token: &str, out: &mut String| {
    out.push_str(token.strip_suffix("@@").unwrap_or(token));
};

let whole = ["hashtag"];
let pieces = ["hash@@", "tag"];
let (whole_to_piece, _) = get_alignments_with(&whole, &pieces, &strip_suffix);
assert_eq!(whole_to_piece, vec![vec![0, 1]]);

Exact copies tokens without case conversion, marker removal, or Unicode decomposition.

Complexity

Equal normalized unit streams use linear time. Different streams use a linear-space Myers comparison over unit keys. Its time is proportional to the combined length times the edit distance, with quadratic worst-case time for unrelated inputs.

The default rules do not decode byte-level encodings of non-ASCII text. Supply a normalizer when tokens require that decoding. The comparison also keeps simple lowercase behavior, so mappings such as ß to ss are outside its scope.

License