Skip to main content

unitoken/
counter.rs

1use std::{collections::BTreeMap, hash::Hash, io::{Read, Write}};
2
3use ahash::AHashMap;
4use hashbrown::HashMap;
5use rayon::iter::{IntoParallelRefIterator, ParallelIterator};
6
7use crate::{
8  MyError, MyResult,
9  bpe::Freq,
10  pretokenizer::{
11    PreTokenPiece, PreTokenizer, UnicodeBigramSelection, count_unicode_bigrams,
12    for_each_regular_chunk, is_unicode_bigram_script, select_unicode_bigrams,
13  },
14};
15
16type WordCounts = HashMap<String, Freq, ahash::RandomState>;
17type BorrowedWordCounts<'a> = HashMap<&'a str, Freq, ahash::RandomState>;
18
19#[derive(Clone, Copy, Debug, PartialEq, Eq)]
20pub struct SourceBatchOptions {
21  pub max_records: usize,
22  pub max_bytes: usize,
23}
24
25impl Default for SourceBatchOptions {
26  fn default() -> Self {
27    Self {
28      max_records: 4096,
29      max_bytes: 64 * 1024 * 1024,
30    }
31  }
32}
33
34impl SourceBatchOptions {
35  pub fn validate(self) -> MyResult<Self> {
36    if self.max_records == 0 {
37      return Err(MyError::SourceBatch("max_records must be at least 1"));
38    }
39    if self.max_bytes == 0 {
40      return Err(MyError::SourceBatch("max_bytes must be at least 1"));
41    }
42    Ok(self)
43  }
44}
45
46fn checked_add<K: Eq + Hash>(counts: &mut AHashMap<K, Freq>, key: K, value: Freq) -> MyResult<()> {
47  let current = counts.entry(key).or_default();
48  *current = current.checked_add(value).ok_or(MyError::FrequencyOverflow)?;
49  Ok(())
50}
51
52fn merge_counts<K: Eq + Hash>(target: &mut AHashMap<K, Freq>, source: AHashMap<K, Freq>) -> MyResult<()> {
53  for (key, value) in source {
54    checked_add(target, key, value)?;
55  }
56  Ok(())
57}
58
59fn count_bigrams_into(
60  pre_tokenizer: &PreTokenizer,
61  text: &str,
62  counts: &mut AHashMap<(char, char), Freq>,
63) -> MyResult<()> {
64  if text.is_empty() {
65    return Ok(());
66  }
67  if pre_tokenizer.re_special_tokens.as_str() == "$^" {
68    return count_unicode_bigrams(text, counts, is_unicode_bigram_script);
69  }
70  for_each_regular_chunk(text, &pre_tokenizer.re_special_tokens, |chunk| {
71    count_unicode_bigrams(chunk, counts, is_unicode_bigram_script)
72  })
73}
74
75fn count_words_borrowed<'a>(
76  pre_tokenizer: &PreTokenizer,
77  text: &'a str,
78  counts: &mut BorrowedWordCounts<'a>,
79) -> MyResult<()> {
80  pre_tokenizer.for_each_piece(text, |piece| {
81    if let PreTokenPiece::Word(word) = piece {
82      let frequency = counts.entry(word).or_insert(0);
83      *frequency = frequency.checked_add(1).ok_or(MyError::FrequencyOverflow)?;
84    }
85    Ok(())
86  })
87}
88
89fn merge_borrowed_word_counts<'a>(
90  mut left: BorrowedWordCounts<'a>,
91  mut right: BorrowedWordCounts<'a>,
92) -> MyResult<BorrowedWordCounts<'a>> {
93  if left.len() < right.len() {
94    std::mem::swap(&mut left, &mut right);
95  }
96  for (word, frequency) in right {
97    let current = left.entry(word).or_default();
98    *current = current.checked_add(frequency).ok_or(MyError::FrequencyOverflow)?;
99  }
100  Ok(left)
101}
102
103fn merge_borrowed_into_word_counts(
104  target: &mut WordCounts,
105  source: BorrowedWordCounts<'_>,
106) -> MyResult<()> {
107  target.reserve(source.len());
108  for (word, frequency) in source {
109    let current = target.entry_ref(word).or_insert(0);
110    *current = current.checked_add(frequency).ok_or(MyError::FrequencyOverflow)?;
111  }
112  Ok(())
113}
114
115fn merge_word_counts(target: &mut WordCounts, source: WordCounts) -> MyResult<()> {
116  for (word, frequency) in source {
117    let current = target.entry(word).or_default();
118    *current = current.checked_add(frequency).ok_or(MyError::FrequencyOverflow)?;
119  }
120  Ok(())
121}
122
123#[derive(Clone)]
124#[cfg_attr(feature = "py", pyo3::pyclass(from_py_object))]
125pub struct BigramCounter {
126  pre_tokenizer: PreTokenizer,
127  counts: AHashMap<(char, char), Freq>,
128}
129
130impl BigramCounter {
131  pub fn new(pre_tokenizer: PreTokenizer) -> Self {
132    Self {
133      pre_tokenizer,
134      counts: AHashMap::new(),
135    }
136  }
137
138  pub fn add_text(&mut self, text: &str) -> MyResult<()> {
139    count_bigrams_into(&self.pre_tokenizer, text, &mut self.counts)
140  }
141
142  pub fn add_batch<S: AsRef<str> + Sync>(&mut self, texts: &[S]) -> MyResult<()> {
143    let batch_counts = texts
144      .par_iter()
145      .try_fold(AHashMap::new, |mut counts, text| {
146        count_bigrams_into(&self.pre_tokenizer, text.as_ref(), &mut counts)?;
147        Ok::<_, MyError>(counts)
148      })
149      .try_reduce(AHashMap::new, |mut left, right| {
150        merge_counts(&mut left, right)?;
151        Ok::<_, MyError>(left)
152      })?;
153    merge_counts(&mut self.counts, batch_counts)
154  }
155
156  pub fn add_source<I, S>(&mut self, source: I, options: SourceBatchOptions) -> MyResult<()>
157  where
158    I: IntoIterator<Item = S>,
159    S: AsRef<str> + Sync,
160  {
161    let options = options.validate()?;
162    let mut batch = Vec::new();
163    let mut bytes: usize = 0;
164    for text in source {
165      let text_bytes = text.as_ref().len();
166      if !batch.is_empty()
167        && (batch.len() >= options.max_records
168          || bytes.saturating_add(text_bytes) > options.max_bytes)
169      {
170        self.add_batch(&batch)?;
171        batch.clear();
172        bytes = 0;
173      }
174      bytes = bytes.checked_add(text_bytes).ok_or(MyError::SourceBatch("batch byte size overflow"))?;
175      batch.push(text);
176    }
177    if !batch.is_empty() {
178      self.add_batch(&batch)?;
179    }
180    Ok(())
181  }
182
183  pub fn merge(&mut self, other: Self) -> MyResult<()> {
184    merge_counts(&mut self.counts, other.counts)
185  }
186
187  pub fn selected(&self, top_k: usize, min_freq: Freq) -> Vec<(char, char)> {
188    let mut selected = self
189      .selection(top_k, min_freq)
190      .bigrams
191      .into_iter()
192      .collect::<Vec<_>>();
193    selected.sort_unstable();
194    selected
195  }
196
197  /// Select Unicode bigrams and preserve their effective frequency boundary.
198  pub fn selection(&self, top_k: usize, min_freq: Freq) -> UnicodeBigramSelection {
199    select_unicode_bigrams(self.counts.clone(), top_k, min_freq)
200  }
201
202  pub fn counts(&self) -> &AHashMap<(char, char), Freq> {
203    &self.counts
204  }
205}
206
207#[derive(Clone)]
208#[cfg_attr(feature = "py", pyo3::pyclass(from_py_object))]
209pub struct WordCounter {
210  pre_tokenizer: PreTokenizer,
211  counts: WordCounts,
212}
213
214impl WordCounter {
215  pub fn new(pre_tokenizer: PreTokenizer) -> Self {
216    Self {
217      pre_tokenizer,
218      counts: WordCounts::default(),
219    }
220  }
221
222  pub fn add_text(&mut self, text: &str) -> MyResult<()> {
223    let mut counts = BorrowedWordCounts::default();
224    count_words_borrowed(&self.pre_tokenizer, text, &mut counts)?;
225    merge_borrowed_into_word_counts(&mut self.counts, counts)
226  }
227
228  pub fn add_batch<'a, S: AsRef<str> + Sync>(&mut self, texts: &'a [S]) -> MyResult<()> {
229    let batch_counts = texts
230      .par_iter()
231      .try_fold(BorrowedWordCounts::default, |mut counts, text| {
232        count_words_borrowed(&self.pre_tokenizer, text.as_ref(), &mut counts)?;
233        Ok::<_, MyError>(counts)
234      })
235      .try_reduce(BorrowedWordCounts::default, merge_borrowed_word_counts)?;
236    merge_borrowed_into_word_counts(&mut self.counts, batch_counts)
237  }
238
239  pub fn add_source<I, S>(&mut self, source: I, options: SourceBatchOptions) -> MyResult<()>
240  where
241    I: IntoIterator<Item = S>,
242    S: AsRef<str> + Sync,
243  {
244    let options = options.validate()?;
245    let mut batch = Vec::new();
246    let mut bytes: usize = 0;
247    for text in source {
248      let text_bytes = text.as_ref().len();
249      if !batch.is_empty()
250        && (batch.len() >= options.max_records
251          || bytes.saturating_add(text_bytes) > options.max_bytes)
252      {
253        self.add_batch(&batch)?;
254        batch.clear();
255        bytes = 0;
256      }
257      bytes = bytes.checked_add(text_bytes).ok_or(MyError::SourceBatch("batch byte size overflow"))?;
258      batch.push(text);
259    }
260    if !batch.is_empty() {
261      self.add_batch(&batch)?;
262    }
263    Ok(())
264  }
265
266  pub fn merge(&mut self, other: Self) -> MyResult<()> {
267    merge_word_counts(&mut self.counts, other.counts)
268  }
269
270  pub fn words(&self) -> BTreeMap<String, Freq> {
271    self.counts.iter().map(|(word, frequency)| (word.clone(), *frequency)).collect()
272  }
273
274  pub fn len(&self) -> usize {
275    self.counts.len()
276  }
277
278  pub fn is_empty(&self) -> bool {
279    self.counts.is_empty()
280  }
281
282  pub fn clear(&mut self) {
283    self.counts.clear();
284  }
285
286  pub fn take_counts(&mut self) -> WordCounts {
287    std::mem::take(&mut self.counts)
288  }
289
290  pub fn save<W: Write>(&self, writer: W) -> MyResult<()> {
291    serde_json::to_writer(writer, &self.counts)?;
292    Ok(())
293  }
294
295  pub fn load<R: Read>(pre_tokenizer: PreTokenizer, reader: R) -> MyResult<Self> {
296    let counts = serde_json::from_reader(reader)?;
297    Ok(Self { pre_tokenizer, counts })
298  }
299
300  pub fn counts(&self) -> &WordCounts {
301    &self.counts
302  }
303}
304
305#[cfg(test)]
306mod tests {
307  use super::*;
308  use crate::bigram::{Bigram, VocabBigramIndex};
309  use crate::pretokenizer::parse_unicode_bigrams;
310
311  #[test]
312  fn bigram_counter_batches_and_merges() {
313    let pre_tokenizer = PreTokenizer::new(&[], None);
314    let mut left = BigramCounter::new(pre_tokenizer.clone());
315    left.add_source(
316      ["你好世界", "你好"],
317      SourceBatchOptions { max_records: 1, max_bytes: 8 },
318    ).unwrap();
319    let mut right = BigramCounter::new(pre_tokenizer);
320    right.add_text("世界").unwrap();
321    left.merge(right).unwrap();
322
323    assert_eq!(left.counts().get(&('你', '好')), Some(&2));
324    assert_eq!(left.counts().get(&('世', '界')), Some(&2));
325    let selection = left.selection(1, 1);
326    assert_eq!(selection.cutoff_freq, Some(2));
327    assert_eq!(selection.max_excluded_freq, Some(1));
328    assert_eq!(selection.bigrams.len(), 2);
329  }
330
331  #[test]
332  fn bigram_counter_ignores_vocab_bigram_word_boundaries() {
333    let pre_tokenizer = PreTokenizer::new(&[], None)
334      .with_vocab_bigram_index(VocabBigramIndex::unicode(ahash::AHashSet::new()));
335    let mut counter = BigramCounter::new(pre_tokenizer);
336
337    counter.add_text("你好").unwrap();
338
339    assert_eq!(counter.counts().get(&('你', '好')), Some(&1));
340  }
341
342  #[test]
343  fn word_counter_uses_frozen_bigrams_and_skips_special_tokens() {
344    let bigrams = parse_unicode_bigrams(&["你好".to_string()]).unwrap();
345    let pre_tokenizer = PreTokenizer::new(&["<eot>".to_string()], Some("<eot>"))
346      .with_unicode_bigrams(bigrams);
347    let mut counter = WordCounter::new(pre_tokenizer);
348    counter.add_batch(&["你好世界<eot>", "你好"]).unwrap();
349
350    let words = counter.words();
351    assert_eq!(words.get("你好"), Some(&2));
352    assert_eq!(words.get("世"), Some(&1));
353    assert_eq!(words.get("界"), Some(&1));
354    assert!(!words.contains_key("<eot>"));
355  }
356
357  #[test]
358  fn word_counter_uses_vocab_bigram_pretokenization() {
359    let vocab_bigrams = [Bigram::new('a', 'b'), Bigram::new('b', 'c')]
360      .into_iter()
361      .collect();
362    let pre_tokenizer = PreTokenizer::try_new(
363      &["<eot>".to_string()],
364      Some("<eot>"),
365      Some(r"\p{L}+"),
366    )
367    .unwrap()
368    .with_vocab_bigram_index(VocabBigramIndex::unicode(vocab_bigrams));
369    let mut counter = WordCounter::new(pre_tokenizer);
370
371    counter.add_batch(&["abcz<eot>", "abcx"]).unwrap();
372
373    assert_eq!(
374      counter.words(),
375      [
376        ("abc".to_string(), 2),
377        ("x".to_string(), 1),
378        ("z".to_string(), 1),
379      ]
380      .into_iter()
381      .collect(),
382    );
383  }
384
385  #[test]
386  fn word_counter_borrowed_batch_matches_owned_pretokenization() {
387    let bigrams = parse_unicode_bigrams(&["世界".to_string(), "你好".to_string()]).unwrap();
388    let pre_tokenizer = PreTokenizer::new(&[], None).with_unicode_bigrams(bigrams);
389    let texts = ["Hello 世界你好 world", "世界你好", "Hello"];
390    let mut expected = BTreeMap::new();
391    for text in texts {
392      for (word, frequency) in pre_tokenizer.get_words_owned(text).unwrap() {
393        *expected.entry(word).or_default() += frequency;
394      }
395    }
396
397    let mut counter = WordCounter::new(pre_tokenizer);
398    counter.add_batch(&texts).unwrap();
399
400    assert_eq!(counter.words(), expected);
401  }
402
403  #[test]
404  fn word_counter_streams_around_adjacent_special_tokens() {
405    let pre_tokenizer = PreTokenizer::new(&["<eot>".to_string()], Some("<eot>"));
406    let mut counter = WordCounter::new(pre_tokenizer);
407    counter.add_text("<eot>Hello<eot><eot> world<eot>").unwrap();
408
409    assert_eq!(
410      counter.words(),
411      [("Hello".to_string(), 1), (" world".to_string(), 1)].into_iter().collect(),
412    );
413  }
414
415  #[test]
416  fn word_counter_preserves_empty_custom_pattern_matches() {
417    let pre_tokenizer = PreTokenizer::try_new(&[], None, Some("")).unwrap()
418      .with_unicode_bigrams(ahash::AHashSet::new());
419    let expected = pre_tokenizer.get_words_owned("ab").unwrap();
420    let mut counter = WordCounter::new(pre_tokenizer);
421    counter.add_text("ab").unwrap();
422
423    assert_eq!(counter.words(), expected);
424  }
425}