meta_language/
language_identification.rs

1//! Trigram language identification shared with the JavaScript runtime.
2//!
3//! This is franc's algorithm over `data/language-trigrams.json`, which
4//! `js/scripts/build-language-identification.mjs` generates from franc-min
5//! together with the JavaScript copy. Both runtimes count Unicode scalar
6//! values, so they reach the same verdict for the same text.
7
8use std::collections::HashMap;
9use std::sync::OnceLock;
10
11use serde_json::Value;
12
13const LANGUAGE_TRIGRAMS_JSON: &str = include_str!("data/language-trigrams.json");
14const MAX_LENGTH: usize = 2048;
15const MAX_DIFFERENCE: usize = 300;
16
17/// Engine term recorded on identification annotations.
18pub const LANGUAGE_IDENTIFIER_TERM: &str = "identifier:trigram";
19
20struct Script {
21    name: String,
22    ranges: Vec<(u32, u32)>,
23}
24
25/// A language code with its trigram ranks.
26type LanguageModel = (String, HashMap<String, usize>);
27
28struct TrigramData {
29    languages: HashMap<String, &'static str>,
30    scripts: Vec<Script>,
31    models: HashMap<String, Vec<LanguageModel>>,
32}
33
34fn trigram_data() -> &'static TrigramData {
35    static DATA: OnceLock<TrigramData> = OnceLock::new();
36    DATA.get_or_init(parse_trigram_data)
37}
38
39fn parse_trigram_data() -> TrigramData {
40    let value: Value =
41        serde_json::from_str(LANGUAGE_TRIGRAMS_JSON).expect("language trigram data is valid JSON");
42    let languages = value["languages"]
43        .as_object()
44        .expect("languages object")
45        .iter()
46        .map(|(code, name)| {
47            let name = crate::natural_language::canonical_natural_language(
48                name.as_str().expect("language name"),
49            )
50            .expect("supported natural language");
51            (code.clone(), name)
52        })
53        .collect();
54    let scripts = value["scripts"]
55        .as_array()
56        .expect("scripts array")
57        .iter()
58        .map(|script| Script {
59            name: script["name"].as_str().expect("script name").to_string(),
60            ranges: script["ranges"]
61                .as_array()
62                .expect("script ranges")
63                .iter()
64                .map(|range| {
65                    let bound = |index: usize| {
66                        u32::try_from(range[index].as_u64().expect("range bound"))
67                            .expect("code point")
68                    };
69                    (bound(0), bound(1))
70                })
71                .collect(),
72        })
73        .collect();
74    let models = value["models"]
75        .as_array()
76        .expect("models array")
77        .iter()
78        .map(|model| {
79            let languages = model["languages"]
80                .as_array()
81                .expect("model languages")
82                .iter()
83                .map(|language| {
84                    let ranks = language["trigrams"]
85                        .as_str()
86                        .expect("trigram model")
87                        .split('|')
88                        .enumerate()
89                        .map(|(rank, trigram)| (trigram.to_string(), rank))
90                        .collect();
91                    (language["code"].as_str().expect("code").to_string(), ranks)
92                })
93                .collect();
94            (
95                model["script"].as_str().expect("script").to_string(),
96                languages,
97            )
98        })
99        .collect();
100    TrigramData {
101        languages,
102        scripts,
103        models,
104    }
105}
106
107/// Returns the canonical name of the supported natural language the text is
108/// written in, or `None` when the text carries no usable evidence.
109#[must_use]
110pub fn identify_language(text: &str) -> Option<&'static str> {
111    let data = trigram_data();
112    let characters: Vec<char> = text.chars().take(MAX_LENGTH).collect();
113    if characters.is_empty() {
114        return None;
115    }
116
117    let script = top_script(&data.scripts, &characters)?;
118    let Some(models) = data.models.get(script) else {
119        return data.languages.get(script).copied();
120    };
121
122    let trigrams = trigram_counts(&characters);
123    let (code, distance) = models
124        .iter()
125        .map(|(code, model)| (code, trigram_distance(&trigrams, model)))
126        .fold(
127            None,
128            |best: Option<(&String, usize)>, candidate| match best {
129                Some(best) if best.1 <= candidate.1 => Some(best),
130                _ => Some(candidate),
131            },
132        )?;
133    // A distance of MAX_DIFFERENCE per character means no trigram matched.
134    if distance >= characters.len() * MAX_DIFFERENCE {
135        return None;
136    }
137    data.languages.get(code).copied()
138}
139
140fn top_script<'a>(scripts: &'a [Script], characters: &[char]) -> Option<&'a str> {
141    let mut top = None;
142    let mut top_count = 0;
143    for script in scripts {
144        let count = characters
145            .iter()
146            .filter(|character| in_ranges(u32::from(**character), &script.ranges))
147            .count();
148        if count > top_count {
149            top = Some(script.name.as_str());
150            top_count = count;
151        }
152    }
153    top
154}
155
156fn in_ranges(code_point: u32, ranges: &[(u32, u32)]) -> bool {
157    ranges
158        .binary_search_by(|&(start, end)| {
159            if code_point < start {
160                std::cmp::Ordering::Greater
161            } else if code_point > end {
162                std::cmp::Ordering::Less
163            } else {
164                std::cmp::Ordering::Equal
165            }
166        })
167        .is_ok()
168}
169
170/// ECMAScript `\s`, which franc collapses.
171const fn is_ecmascript_whitespace(character: char) -> bool {
172    matches!(
173        character,
174        '\t' | '\n' | '\u{0b}' | '\u{0c}' | '\r' | ' ' | '\u{a0}' | '\u{1680}' | '\u{2000}'
175            ..='\u{200a}'
176                | '\u{2028}'
177                | '\u{2029}'
178                | '\u{202f}'
179                | '\u{205f}'
180                | '\u{3000}'
181                | '\u{feff}'
182    )
183}
184
185/// franc's `clean`: ASCII punctuation and digits become spaces, whitespace
186/// runs collapse to one space, the result is trimmed and lowercased.
187fn clean_characters(characters: &[char]) -> Vec<char> {
188    let mut cleaned = String::new();
189    for &character in characters {
190        if ('\u{21}'..='\u{40}').contains(&character) || is_ecmascript_whitespace(character) {
191            if !cleaned.is_empty() && !cleaned.ends_with(' ') {
192                cleaned.push(' ');
193            }
194        } else {
195            cleaned.push(character);
196        }
197    }
198    if cleaned.ends_with(' ') {
199        cleaned.pop();
200    }
201    cleaned.to_lowercase().chars().collect()
202}
203
204/// Trigram counts in first-occurrence order, stably sorted by count.
205fn trigram_counts(characters: &[char]) -> Vec<(String, usize)> {
206    let mut padded = vec![' '];
207    padded.extend(clean_characters(characters));
208    padded.push(' ');
209    let mut counts: Vec<(String, usize)> = Vec::new();
210    let mut positions: HashMap<String, usize> = HashMap::new();
211    for window in padded.windows(3) {
212        let trigram: String = window.iter().collect();
213        if let Some(&position) = positions.get(&trigram) {
214            counts[position].1 += 1;
215        } else {
216            positions.insert(trigram.clone(), counts.len());
217            counts.push((trigram, 1));
218        }
219    }
220    counts.sort_by_key(|(_, count)| *count);
221    counts
222}
223
224fn trigram_distance(trigrams: &[(String, usize)], model: &HashMap<String, usize>) -> usize {
225    trigrams
226        .iter()
227        .map(|(trigram, count)| {
228            model
229                .get(trigram)
230                .map_or(MAX_DIFFERENCE, |rank| count.abs_diff(rank + 1))
231        })
232        .sum()
233}
meta_language/language_identification.rs

meta_language/
language_identification.rs
