N-grams

use ngrams.qweruse ngrams_words, ngrams_chars from ngrams      // Quillo 0.6: only these

unicode-segmentation = "1"serde_json = { version = "1", features = ["preserve_order"] }

// A shop's reviews: the phrases customers use most, product names matched despite typos, and copy-pasted reviews caught.////   quillo run ngrams.qwe      then open http://localhost:8080/reviewsuse "ngrams.qwer"let REVIEWS = [    "Great coffee and friendly staff, the customer service was excellent.",    "The customer service was slow but the coffee was great.",    "Out of stock again! Third time the beans were out of stock.",    "Great coffee and friendly staff, the customer service was excellent!!",    "Lovely place. Great coffee, great cake, great customer service.",    "Beans out of stock, customer service could not say when they return.",]route GET /reviews {    let all = join(REVIEWS, " ")    {        bigrams: ngrams_words("the quick brown fox", 2)?,        trigrams: slice(ngrams_chars("Coffee", 3)?, 0, 3),        phrases: ngrams_top(all, 2, 3, true)?,        long_phrases: ngrams_top(all, 3, 1, true)?,        same_product: ngrams_similarity("Ethiopia Yirgacheffe 250g", "Ethiopia Yirgachefe 250 g", 3)?,        other_product: ngrams_similarity("Ethiopia Yirgacheffe 250g", "Colombia Supremo 1kg", 3)?,        copies: ngrams_near_duplicates(REVIEWS, 0.6)?,    }}

//! N-grams and shingles of text: word and character n-grams, the most frequent phrases ("customer service", "out of stock"), how alike two texts are by their shared shingles, and near-duplicate texts found among thousands with MinHash.//! version: 1.0.0//!//! [dependencies]//! unicode-segmentation = "1"//! serde_json = { version = "1", features = ["preserve_order"] }use serde_json::{json, Value};use std::collections::{HashMap, HashSet};use unicode_segmentation::UnicodeSegmentation;const STOP: &str = "a an and are as at be but by for from has have he her his i if in into is it its me my no not of on or our she so than that the their them then there these they this to too us was we were what when which who will with you your";fn words(text: &str) -> Vec<String> {    text.unicode_words().map(|w| w.to_lowercase()).collect()}// Word n-grams never cross the end of a sentence or clause: "great. Out" is no n-gram.fn pieces(text: &str) -> Vec<Vec<String>> {    text.split(|c: char| matches!(c, '.' | '!' | '?' | ';' | ':' | '\n' | '…' | '。' | '！' | '？')).map(words).filter(|w| !w.is_empty()).collect()}fn word_grams(text: &str, n: usize) -> Vec<String> {    if n == 0 { return vec![] }    pieces(text).iter().filter(|w| w.len() >= n).flat_map(|w| w.windows(n).map(|g| g.join(" ")).collect::<Vec<_>>()).collect()}fn char_grams(text: &str, n: usize) -> Vec<String> {    // Lower case, runs of spaces as one: "Hello  World" and "hello world" give the same grams.    let norm: Vec<char> = text.to_lowercase().split_whitespace().collect::<Vec<_>>().join(" ").chars().collect();    if n == 0 || norm.len() < n { return if norm.is_empty() || n == 0 { vec![] } else { vec![norm.iter().collect()] } }    norm.windows(n).map(|g| g.iter().collect()).collect()}fn check_n(n: i64) -> Result<usize, String> {    if !(1..=20).contains(&n) { return Err(format!("n is 1 to 20, not {}", n)) }    Ok(n as usize)}/// The word n-grams of `text`, lower case, in order, none across a sentence's end: `ngrams_words("the quick brown fox", 2)` is `["the quick", "quick brown", "brown fox"]`.pub fn ngrams_words(text: &str, n: i64) -> Result<Vec<String>, String> {    Ok(word_grams(text, check_n(n)?))}/// The character n-grams of `text`, lower case, spaces counted (runs of them as one): for fuzzy search indexes and language guessing.pub fn ngrams_chars(text: &str, n: i64) -> Result<Vec<String>, String> {    Ok(char_grams(text, check_n(n)?))}/// The `limit` most frequent word n-grams of `text`: `[{ gram, count }]`, most frequent first, ties in order of first use; n-grams that begin or end with an English stop word ("of the") are left out when `skip_stop_words`.pub fn ngrams_top(text: &str, n: i64, limit: i64, skip_stop_words: bool) -> Result<Vec<Value>, String> {    let n = check_n(n)?;    let stop: HashSet<&str> = STOP.split_whitespace().collect();    let mut counts: HashMap<String, (usize, usize)> = HashMap::new();    let mut i = 0usize;    for w in pieces(text).iter().filter(|w| w.len() >= n) {        for g in w.windows(n) {            i += 1;            if skip_stop_words && (stop.contains(g[0].as_str()) || stop.contains(g[n - 1].as_str())) { continue }            if g.iter().all(|x| x.chars().all(|c| c.is_numeric())) { continue }            let e = counts.entry(g.join(" ")).or_insert((0, i));            e.0 += 1;        }    }    let mut v: Vec<(String, (usize, usize))> = counts.into_iter().collect();    v.sort_by(|a, b| b.1 .0.cmp(&a.1 .0).then(a.1 .1.cmp(&b.1 .1)));    Ok(v.into_iter().take(limit.max(0) as usize).map(|(g, (c, _))| json!({ "gram": g, "count": c })).collect())}fn jac(a: &HashSet<String>, b: &HashSet<String>) -> f64 {    if a.is_empty() && b.is_empty() { return 1.0 }    let inter = a.intersection(b).count() as f64;    let union = a.union(b).count() as f64;    inter / union}/// How alike two texts are, from 0 to 1: the Jaccard similarity of their character `n`-gram sets (3 is a good start), so typos and reordered words still score high. For "is this the same product name, address, review?".pub fn ngrams_similarity(a: &str, b: &str, n: i64) -> Result<f64, String> {    let n = check_n(n)?;    let sa: HashSet<String> = char_grams(a, n).into_iter().collect();    let sb: HashSet<String> = char_grams(b, n).into_iter().collect();    Ok((jac(&sa, &sb) * 10000.0).round() / 10000.0)}fn fnv(s: &str, seed: u64) -> u64 {    let mut h: u64 = 0xcbf29ce484222325 ^ seed.wrapping_mul(0x9E3779B97F4A7C15);    for b in s.as_bytes() { h ^= *b as u64; h = h.wrapping_mul(0x100000001b3); }    // A final mix, so nearby seeds give independent hashes.    h ^= h >> 33; h = h.wrapping_mul(0xff51afd7ed558ccd); h ^= h >> 33; h = h.wrapping_mul(0xc4ceb9fe1a85ec53); h ^= h >> 33;    h}/// The pairs of near-duplicate texts among `texts` (reviews, listings, support tickets), whose word 3-shingles overlap by at least `threshold` (0 to 1; 0.5 is a good start): `[{ a, b, similarity }]`, `a` and `b` positions in the list counted from 0, most alike first./// Candidates are found with MinHash and banding, then measured exactly, so thousands of texts take a moment, not hours.pub fn ngrams_near_duplicates(texts: Vec<String>, threshold: f64) -> Result<Vec<Value>, String> {    if !(0.0..=1.0).contains(&threshold) { return Err(format!("the threshold is 0 to 1, not {}", threshold)) }    if texts.len() > 200_000 { return Err("at most 200,000 texts at a time".into()) }    const HASHES: usize = 128;    const BANDS: usize = 32;    let rows = HASHES / BANDS;    let shingles: Vec<HashSet<String>> = texts.iter().map(|t| {        let g = word_grams(t, 3);        if g.is_empty() { words(t).into_iter().collect() } else { g.into_iter().collect() }    }).collect();    let sigs: Vec<Vec<u64>> = shingles.iter().map(|s| (0..HASHES as u64).map(|k| s.iter().map(|x| fnv(x, k)).min().unwrap_or(u64::MAX)).collect()).collect();    let mut candidates: HashSet<(usize, usize)> = HashSet::new();    for band in 0..BANDS {        let mut buckets: HashMap<Vec<u64>, Vec<usize>> = HashMap::new();        for (i, sig) in sigs.iter().enumerate() {            if shingles[i].is_empty() { continue }            buckets.entry(sig[band * rows..(band + 1) * rows].to_vec()).or_default().push(i);        }        for ids in buckets.values() {            if ids.len() > 1 && ids.len() <= 1000 {                for x in 0..ids.len() { for y in (x + 1)..ids.len() { candidates.insert((ids[x], ids[y])); } }            }        }    }    let mut out: Vec<(usize, usize, f64)> = candidates.into_iter().map(|(a, b)| (a, b, jac(&shingles[a], &shingles[b]))).filter(|x| x.2 >= threshold).collect();    out.sort_by(|x, y| y.2.partial_cmp(&x.2).unwrap_or(std::cmp::Ordering::Equal).then((x.0, x.1).cmp(&(y.0, y.1))));    Ok(out.into_iter().map(|(a, b, s)| json!({ "a": a, "b": b, "similarity": (s * 10000.0).round() / 10000.0 })).collect())}