use crate::network::NetworkError;
use std::collections::HashMap;
#[derive(Clone, Debug)]
pub struct Bpe {
vocab: HashMap<String, u32>,
tokens: Vec<String>,
ranks: HashMap<(String, String), u32>,
specials: Vec<(String, u32)>,
end_of_word: Option<String>,
lowercase: bool,
byte_encoder: Vec<char>,
byte_decoder: HashMap<char, u8>,
}
impl Bpe {
pub fn from_file(path: impl AsRef<std::path::Path>) -> Result<Self, NetworkError> {
let text = std::fs::read_to_string(path)?;
Self::from_json(&text)
}
pub fn from_json(text: &str) -> Result<Self, NetworkError> {
let json: serde_json::Value = serde_json::from_str(text)
.map_err(|error| NetworkError::InvalidDataset(format!("tokenizer.json: {error}")))?;
let model = json
.get("model")
.ok_or_else(|| NetworkError::InvalidDataset("tokenizer.json has no model".into()))?;
let vocab: HashMap<String, u32> = model
.get("vocab")
.and_then(|vocab| vocab.as_object())
.ok_or_else(|| NetworkError::InvalidDataset("the model has no vocabulary".into()))?
.iter()
.map(|(token, id)| {
let id = id
.as_u64()
.ok_or_else(|| NetworkError::InvalidDataset(format!("{token} has no id")))?;
Ok((token.clone(), id as u32))
})
.collect::<Result<_, NetworkError>>()?;
let mut tokens =
vec![String::new(); vocab.values().map(|id| *id as usize + 1).max().unwrap_or(0)];
for (token, id) in &vocab {
tokens[*id as usize] = token.clone();
}
let mut ranks = HashMap::new();
if let Some(merges) = model.get("merges").and_then(|merges| merges.as_array()) {
for (rank, merge) in merges.iter().enumerate() {
let pair = match merge {
serde_json::Value::String(merge) => {
let mut parts = merge.splitn(2, ' ');
match (parts.next(), parts.next()) {
(Some(first), Some(second)) => (first.to_string(), second.to_string()),
_ => continue,
}
}
serde_json::Value::Array(pair) if pair.len() == 2 => (
pair[0].as_str().unwrap_or_default().to_string(),
pair[1].as_str().unwrap_or_default().to_string(),
),
_ => continue,
};
ranks.insert(pair, rank as u32);
}
}
let mut specials: Vec<(String, u32)> = json
.get("added_tokens")
.and_then(|added| added.as_array())
.map(|added| {
added
.iter()
.filter_map(|token| {
Some((
token.get("content")?.as_str()?.to_string(),
token.get("id")?.as_u64()? as u32,
))
})
.collect()
})
.unwrap_or_default();
specials.sort_by_key(|(token, _)| std::cmp::Reverse(token.len()));
let end_of_word = model
.get("end_of_word_suffix")
.and_then(|suffix| suffix.as_str())
.map(str::to_string);
let lowercase = json
.get("normalizer")
.map(|normalizer| normalizer.to_string().contains("Lowercase"))
.unwrap_or(false);
let mut vocab = vocab;
for (token, id) in &specials {
if tokens.len() <= *id as usize {
tokens.resize(*id as usize + 1, String::new());
}
tokens[*id as usize] = token.clone();
vocab.entry(token.clone()).or_insert(*id);
}
let byte_encoder = byte_alphabet();
let byte_decoder = byte_encoder
.iter()
.enumerate()
.map(|(byte, character)| (*character, byte as u8))
.collect();
Ok(Self {
vocab,
tokens,
ranks,
specials,
end_of_word,
lowercase,
byte_encoder,
byte_decoder,
})
}
pub fn vocab_size(&self) -> usize {
self.tokens.len()
}
pub fn token_id(&self, token: &str) -> Option<u32> {
self.vocab.get(token).copied()
}
pub fn encode(&self, text: &str) -> Result<Vec<u32>, NetworkError> {
let owned;
let text = if self.lowercase {
owned = text.to_lowercase();
&owned
} else {
text
};
let mut ids = Vec::new();
let mut rest = text;
while !rest.is_empty() {
let special = self
.specials
.iter()
.filter_map(|(token, id)| rest.find(token.as_str()).map(|at| (at, token, *id)))
.min_by_key(|(at, token, _)| (*at, usize::MAX - token.len()));
let (head, tail) = match special {
Some((at, token, id)) => {
let head = &rest[..at];
let tail = &rest[at + token.len()..];
self.encode_plain(head, &mut ids)?;
ids.push(id);
("", tail)
}
None => (rest, ""),
};
if !head.is_empty() {
self.encode_plain(head, &mut ids)?;
}
rest = tail;
}
Ok(ids)
}
fn encode_plain(&self, text: &str, ids: &mut Vec<u32>) -> Result<(), NetworkError> {
let words: Vec<String> = match self.end_of_word.is_some() {
true => pre_tokenize(text)
.iter()
.map(|word| word.trim())
.filter(|word| !word.is_empty())
.flat_map(|word| match word.chars().all(char::is_numeric) {
true => word.chars().map(|digit| digit.to_string()).collect(),
false => vec![word.to_string()],
})
.collect(),
false => pre_tokenize(text),
};
for word in words {
let mut symbols: Vec<String> = word
.bytes()
.map(|byte| self.byte_encoder[byte as usize].to_string())
.collect();
if symbols.is_empty() {
continue;
}
if let Some(suffix) = &self.end_of_word {
symbols
.last_mut()
.expect("the word is not empty")
.push_str(suffix);
}
self.merge(&mut symbols);
for symbol in symbols {
let id = self.vocab.get(&symbol).copied().ok_or_else(|| {
NetworkError::InvalidDataset(format!(
"the vocabulary has no token for {symbol:?}, so this file's merges and \
its vocabulary disagree"
))
})?;
ids.push(id);
}
}
Ok(())
}
fn merge(&self, symbols: &mut Vec<String>) {
while symbols.len() > 1 {
let best = symbols
.windows(2)
.enumerate()
.filter_map(|(index, pair)| {
let rank = self.ranks.get(&(pair[0].clone(), pair[1].clone()))?;
Some((*rank, index))
})
.min();
let Some((_, index)) = best else {
return;
};
let second = symbols.remove(index + 1);
symbols[index].push_str(&second);
}
}
pub fn decode(&self, ids: &[u32]) -> String {
let mut bytes = Vec::new();
for id in ids {
let Some(token) = self.tokens.get(*id as usize) else {
continue;
};
let token = match &self.end_of_word {
Some(suffix) => token.replace(suffix.as_str(), " "),
None => token.clone(),
};
if self.specials.iter().any(|(special, _)| *special == token) {
bytes.extend_from_slice(token.as_bytes());
continue;
}
for character in token.chars() {
match self.byte_decoder.get(&character) {
Some(byte) => bytes.push(*byte),
None => bytes.extend_from_slice(character.to_string().as_bytes()),
}
}
}
String::from_utf8_lossy(&bytes).into_owned()
}
}
fn byte_alphabet() -> Vec<char> {
let printable: Vec<u32> = (33..=126).chain(161..=172).chain(174..=255).collect();
let mut alphabet = vec!['\0'; 256];
let mut next = 0u32;
for byte in 0..256u32 {
let character = if printable.contains(&byte) {
byte
} else {
let character = 256 + next;
next += 1;
character
};
alphabet[byte as usize] = char::from_u32(character).expect("a valid code point");
}
alphabet
}
fn pre_tokenize(text: &str) -> Vec<String> {
const CONTRACTIONS: [&str; 7] = ["'s", "'t", "'re", "'ve", "'m", "'ll", "'d"];
let characters: Vec<char> = text.chars().collect();
let mut words = Vec::new();
let mut index = 0;
while index < characters.len() {
let rest: String = characters[index..].iter().collect();
if let Some(contraction) = CONTRACTIONS
.iter()
.find(|contraction| rest.starts_with(**contraction))
{
words.push((*contraction).to_string());
index += contraction.chars().count();
continue;
}
let start = index;
let space = characters[index] == ' ' && index + 1 < characters.len();
let first = if space { index + 1 } else { index };
let kind = characters
.get(first)
.copied()
.map(classify)
.unwrap_or(Kind::Space);
if space && kind != Kind::Space {
index += 1;
} else if space {
while index < characters.len() && characters[index].is_whitespace() {
index += 1;
}
let trailing = index < characters.len();
let end = if trailing && index - start > 1 {
index - 1
} else {
index
};
words.push(characters[start..end].iter().collect());
index = end;
continue;
}
let body = index;
while index < characters.len() && classify(characters[index]) == kind {
index += 1;
}
if index == body {
index += 1;
}
words.push(characters[start..index].iter().collect());
}
words
}
#[derive(Clone, Copy, PartialEq)]
enum Kind {
Letter,
Number,
Other,
Space,
}
fn classify(character: char) -> Kind {
if character.is_alphabetic() {
Kind::Letter
} else if character.is_numeric() {
Kind::Number
} else if character.is_whitespace() {
Kind::Space
} else {
Kind::Other
}
}
#[derive(Clone, Debug)]
pub struct Unigram {
pieces: HashMap<String, (u32, f32)>,
tokens: Vec<String>,
unk: u32,
unk_score: f32,
longest: usize,
specials: Vec<(String, u32)>,
space: char,
prefix_space: bool,
}
impl Unigram {
pub fn from_file(path: impl AsRef<std::path::Path>) -> Result<Self, NetworkError> {
Self::from_json(&std::fs::read_to_string(path)?)
}
pub fn from_json(text: &str) -> Result<Self, NetworkError> {
let json: serde_json::Value = serde_json::from_str(text)
.map_err(|error| NetworkError::InvalidDataset(format!("tokenizer.json: {error}")))?;
let model = json
.get("model")
.ok_or_else(|| NetworkError::InvalidDataset("tokenizer.json has no model".into()))?;
if model.get("type").and_then(|kind| kind.as_str()) != Some("Unigram") {
return Err(NetworkError::InvalidDataset(
"this tokenizer.json is not a unigram model".into(),
));
}
let entries = model
.get("vocab")
.and_then(|vocab| vocab.as_array())
.ok_or_else(|| NetworkError::InvalidDataset("the model has no vocabulary".into()))?;
let mut pieces = HashMap::with_capacity(entries.len());
let mut tokens = Vec::with_capacity(entries.len());
let mut lowest = 0.0f32;
for (id, entry) in entries.iter().enumerate() {
let piece = entry
.get(0)
.and_then(|piece| piece.as_str())
.ok_or_else(|| {
NetworkError::InvalidDataset(format!("vocabulary entry {id} has no piece"))
})?
.to_string();
let score = entry.get(1).and_then(|score| score.as_f64()).unwrap_or(0.0) as f32;
lowest = lowest.min(score);
pieces.insert(piece.clone(), (id as u32, score));
tokens.push(piece);
}
let longest = tokens.iter().map(String::len).max().unwrap_or(1);
let mut specials: Vec<(String, u32)> = json
.get("added_tokens")
.and_then(|added| added.as_array())
.map(|added| {
added
.iter()
.filter_map(|token| {
Some((
token.get("content")?.as_str()?.to_string(),
token.get("id")?.as_u64()? as u32,
))
})
.collect()
})
.unwrap_or_default();
specials.sort_by_key(|(token, _)| std::cmp::Reverse(token.len()));
let metaspace = pre_tokenizer(&json, "Metaspace");
Ok(Self {
unk: model.get("unk_id").and_then(|id| id.as_u64()).unwrap_or(0) as u32,
unk_score: lowest - 10.0,
longest,
specials,
space: metaspace
.as_ref()
.and_then(|metaspace| metaspace.get("replacement"))
.and_then(|replacement| replacement.as_str())
.and_then(|replacement| replacement.chars().next())
.unwrap_or('\u{2581}'),
prefix_space: metaspace
.as_ref()
.map(|metaspace| {
metaspace
.get("add_prefix_space")
.and_then(|flag| flag.as_bool())
.unwrap_or_else(|| {
metaspace.get("prepend_scheme").and_then(|s| s.as_str())
!= Some("never")
})
})
.unwrap_or(true),
pieces,
tokens,
})
}
pub fn vocab_size(&self) -> usize {
self.tokens.len()
}
pub fn token_id(&self, token: &str) -> Option<u32> {
self.pieces.get(token).map(|(id, _)| *id)
}
pub fn encode(&self, text: &str) -> Result<Vec<u32>, NetworkError> {
let mut ids = Vec::new();
let mut rest = text;
while !rest.is_empty() {
let special = self
.specials
.iter()
.filter_map(|(token, id)| rest.find(token.as_str()).map(|at| (at, token, *id)))
.min_by_key(|(at, token, _)| (*at, usize::MAX - token.len()));
match special {
Some((at, token, id)) => {
self.encode_plain(&rest[..at], &mut ids);
ids.push(id);
rest = &rest[at + token.len()..];
}
None => {
self.encode_plain(rest, &mut ids);
rest = "";
}
}
}
Ok(ids)
}
pub fn decode(&self, ids: &[u32]) -> String {
let text: String = ids
.iter()
.filter_map(|id| self.tokens.get(*id as usize))
.map(String::as_str)
.collect::<String>()
.replace(self.space, " ");
match self.prefix_space {
true => text.strip_prefix(' ').unwrap_or(&text).to_string(),
false => text,
}
}
fn encode_plain(&self, text: &str, ids: &mut Vec<u32>) {
let text = self.normalize(text);
if text.is_empty() {
return;
}
let mut best = vec![f32::NEG_INFINITY; text.len() + 1];
let mut from: Vec<(usize, u32)> = vec![(0, self.unk); text.len() + 1];
best[0] = 0.0;
for end in 1..=text.len() {
if !text.is_char_boundary(end) {
continue;
}
let earliest = end.saturating_sub(self.longest);
for start in earliest..end {
if best[start] == f32::NEG_INFINITY || !text.is_char_boundary(start) {
continue;
}
let piece = &text[start..end];
let (id, score) = match self.pieces.get(piece) {
Some((id, score)) => (*id, *score),
None if piece.chars().count() == 1 => (self.unk, self.unk_score),
None => continue,
};
let total = best[start] + score;
if total > best[end] {
best[end] = total;
from[end] = (start, id);
}
}
}
let mut path = Vec::new();
let mut at = text.len();
while at > 0 {
let (start, id) = from[at];
path.push(id);
at = start;
}
path.reverse();
ids.extend(path);
}
fn normalize(&self, text: &str) -> String {
let mut normalized = String::with_capacity(text.len() + 1);
if self.prefix_space {
normalized.push(self.space);
}
let mut spaced = self.prefix_space;
for character in text.trim().chars() {
match character.is_whitespace() {
true if spaced => {}
true => {
normalized.push(self.space);
spaced = true;
}
false => {
normalized.push(character);
spaced = false;
}
}
}
normalized
}
}
fn pre_tokenizer(json: &serde_json::Value, kind: &str) -> Option<serde_json::Value> {
let is_kind =
|value: &serde_json::Value| value.get("type").and_then(|name| name.as_str()) == Some(kind);
let pre = json.get("pre_tokenizer")?;
if is_kind(pre) {
return Some(pre.clone());
}
pre.get("pretokenizers")?
.as_array()?
.iter()
.find(|value| is_kind(value))
.cloned()
}
#[cfg(test)]
pub(crate) mod tests {
use super::*;
pub(crate) fn tokenizer(merges: &[&str], extra: &[&str], suffix: Option<&str>) -> Bpe {
Bpe::from_json(&tokenizer_json(merges, extra, suffix)).unwrap()
}
pub(crate) fn write(
path: &std::path::Path,
merges: &[&str],
extra: &[&str],
suffix: Option<&str>,
) {
std::fs::write(path, tokenizer_json(merges, extra, suffix)).unwrap();
}
fn tokenizer_json(merges: &[&str], extra: &[&str], suffix: Option<&str>) -> String {
let alphabet = byte_alphabet();
let mut vocab = serde_json::Map::new();
for (id, character) in alphabet.iter().enumerate() {
vocab.insert(character.to_string(), serde_json::json!(id));
}
let mut next = alphabet.len();
for token in extra {
vocab.insert((*token).to_string(), serde_json::json!(next));
next += 1;
}
let mut model = serde_json::json!({
"vocab": vocab,
"merges": merges.iter().map(|merge| serde_json::json!(merge)).collect::<Vec<_>>(),
});
if let Some(suffix) = suffix {
model["end_of_word_suffix"] = serde_json::json!(suffix);
}
let json = serde_json::json!({
"model": model,
"added_tokens": [{"id": next, "content": "<|end|>"}],
});
json.to_string()
}
#[test]
fn text_survives_the_round_trip_through_ids() {
let bpe = tokenizer(&[], &[], None);
for text in [
"hello world",
"a café, 3 times!",
" spaced\n\ttext",
"日本語",
] {
let ids = bpe.encode(text).unwrap();
assert_eq!(bpe.decode(&ids), text, "{text:?}");
}
}
#[test]
fn merges_are_applied_in_rank_order() {
let bpe = tokenizer(&["l o", "h e", "he l"], &["lo", "he", "hel"], None);
let ids = bpe.encode("hello").unwrap();
assert_eq!(ids.len(), 2);
assert_eq!(bpe.decode(&ids), "hello");
assert_eq!(bpe.encode("xyz").unwrap().len(), 3);
}
#[test]
fn the_pre_tokenizer_splits_the_way_gpt_two_does() {
assert_eq!(pre_tokenize("Hello world"), vec!["Hello", " world"]);
assert_eq!(
pre_tokenize("it's a test, really!"),
vec!["it", "'s", " a", " test", ",", " really", "!"]
);
assert_eq!(pre_tokenize("x y"), vec!["x", " ", " y"]);
assert_eq!(pre_tokenize("value = 42"), vec!["value", " =", " 42"]);
assert_eq!(pre_tokenize("trailing "), vec!["trailing", " "]);
}
#[test]
fn a_special_token_is_matched_whole_and_never_merged() {
let bpe = tokenizer(&["h i"], &["hi"], None);
let end = bpe.token_id("<|end|>").unwrap();
let ids = bpe.encode("hi<|end|>hi").unwrap();
assert_eq!(ids.len(), 3);
assert_eq!(ids[1], end);
assert_eq!(bpe.decode(&ids), "hi<|end|>hi");
}
#[test]
fn a_word_suffix_vocabulary_marks_the_end_of_each_word() {
let bpe = tokenizer(&[], &["a</w>", "b</w>"], Some("</w>"));
let ids = bpe.encode("ab").unwrap();
assert_eq!(ids.len(), 2);
assert_eq!(bpe.decode(&ids), "ab ");
}
#[test]
fn a_word_suffix_vocabulary_drops_the_space_between_words() {
let bpe = tokenizer(&[], &["a</w>", "b</w>", "1</w>", "2</w>"], Some("</w>"));
let space = bpe
.token_id("\u{0120}")
.expect("the byte alphabet holds a space");
let ids = bpe.encode("a b 12").unwrap();
assert!(!ids.contains(&space), "{ids:?} carries a space as a token");
assert_eq!(ids.len(), 4);
}
#[test]
fn a_file_that_is_not_a_tokenizer_is_refused() {
assert!(Bpe::from_json("{}").is_err());
assert!(Bpe::from_json("{\"model\": {}}").is_err());
assert!(Bpe::from_json("not json").is_err());
}
pub(crate) fn unigram_json() -> String {
let vocab: Vec<serde_json::Value> = [
("<pad>", 0.0),
("</s>", 0.0),
("<unk>", 0.0),
("\u{2581}", -3.0),
("\u{2581}a", -1.5),
("\u{2581}ab", -0.6),
("\u{2581}abc", -0.4),
("b", -2.0),
("c", -2.0),
("\u{2581}c", -2.5),
]
.iter()
.map(|(piece, score)| serde_json::json!([piece, score]))
.collect();
serde_json::json!({
"model": {"type": "Unigram", "unk_id": 2, "vocab": vocab},
"pre_tokenizer": {"type": "Metaspace", "replacement": "\u{2581}",
"add_prefix_space": true},
"added_tokens": [{"id": 1, "content": "</s>"}],
})
.to_string()
}
#[test]
fn unigram_cuts_the_text_the_highest_scoring_way() {
let tokenizer = Unigram::from_json(&unigram_json()).unwrap();
assert_eq!(tokenizer.encode("abc").unwrap(), vec![6]);
assert_eq!(tokenizer.encode("ac").unwrap(), vec![4, 8]);
assert_eq!(tokenizer.decode(&[6]), "abc");
assert_eq!(tokenizer.decode(&tokenizer.encode("a b").unwrap()), "a b");
}
#[test]
fn unigram_folds_whitespace_and_keeps_special_tokens_whole() {
let tokenizer = Unigram::from_json(&unigram_json()).unwrap();
assert_eq!(
tokenizer.encode(" ab \n c ").unwrap(),
tokenizer.encode("ab c").unwrap()
);
let ids = tokenizer.encode("ab</s>").unwrap();
assert_eq!(ids.last(), Some(&1));
assert_eq!(tokenizer.encode("\u{1F600}").unwrap(), vec![3, 2]);
}
#[test]
fn unigram_refuses_a_file_that_is_not_one() {
assert!(Unigram::from_json(&tokenizer_json(&[], &[], None)).is_err());
}
}