Skip to main content

qualia_core_db/nlp/
fst.rs

1//! Finite-State Transducer for morphology.
2//!
3//! A simple trie of surface forms → `lemma|features`, walked for lookups.
4//! When an exact surface is absent, suffix-based morphology rules strip
5//! common English inflections (`-s`, `-ed`, `-ing`, `-es`) and re-lookup the
6//! stem, annotating the result with the corresponding feature tag.
7//!
8//! Deterministic, allocation-free in the hot lookup walk (results own their
9//! `String`s, which is Tier-2 authoring output). WASM-compatible.
10
11use super::span::DocSpan;
12use std::collections::HashMap;
13
14/// One morphology analysis result for a surface form.
15#[derive(Debug, Clone, PartialEq, Eq)]
16pub struct FstResult {
17    pub lemma: String,
18    pub features: String,
19    /// Byte span of the matched surface within the queried word (always
20    /// `0..word.len()` for a standalone lookup; included for provenance
21    /// symmetry with the rest of the NLP pipeline).
22    pub span: DocSpan,
23}
24
25/// Suffix rule: strip `suffix` from the surface, re-lookup the stem, and
26/// annotate with `feature` when the stem resolves.
27struct SuffixRule {
28    suffix: &'static str,
29    feature: &'static str,
30}
31
32const SUFFIX_RULES: &[SuffixRule] = &[
33    SuffixRule {
34        suffix: "ies",
35        feature: "PL",
36    },
37    SuffixRule {
38        suffix: "es",
39        feature: "PL",
40    },
41    SuffixRule {
42        suffix: "s",
43        feature: "PL",
44    },
45    SuffixRule {
46        suffix: "ied",
47        feature: "PAST",
48    },
49    SuffixRule {
50        suffix: "ed",
51        feature: "PAST",
52    },
53    SuffixRule {
54        suffix: "ing",
55        feature: "VING",
56    },
57];
58
59/// Compiled FST dictionary: a trie mapping surface bytes to an entry id.
60pub struct FstDict {
61    /// Trie nodes: `children[byte] = node_id`.
62    nodes: Vec<HashMap<u8, usize>>,
63    /// `out[node_id] = entry_id` when a surface terminates at that node.
64    out: Vec<Option<usize>>,
65    /// Entries: `(lemma, features)`.
66    entries: Vec<(String, String)>,
67}
68
69impl FstDict {
70    /// Build a dictionary from `(surface, "lemma|features")` pairs. If the
71    /// second element contains no `|`, the whole string is treated as the
72    /// lemma with empty features.
73    pub fn from_entries(entries: &[(String, String)]) -> Self {
74        let mut nodes: Vec<HashMap<u8, usize>> = vec![HashMap::new()];
75        let mut out: Vec<Option<usize>> = vec![None];
76        let mut stored: Vec<(String, String)> = Vec::with_capacity(entries.len());
77
78        for (surface, payload) in entries {
79            let (lemma, features) = split_payload(payload);
80            let id = stored.len();
81            stored.push((lemma, features));
82            let mut state = 0usize;
83            for &b in surface.as_bytes() {
84                let next = nodes[state].get(&b).copied();
85                state = match next {
86                    Some(n) => n,
87                    None => {
88                        let n = nodes.len();
89                        nodes.push(HashMap::new());
90                        out.push(None);
91                        nodes[state].insert(b, n);
92                        n
93                    }
94                };
95            }
96            out[state] = Some(id);
97        }
98
99        FstDict {
100            nodes,
101            out,
102            entries: stored,
103        }
104    }
105
106    /// Walk the trie for `word`. Returns exact matches first, then suffix-rule
107    /// derivations. The span covers the whole queried word.
108    pub fn lookup(&self, word: &str) -> Vec<FstResult> {
109        let mut results = Vec::new();
110        let span = DocSpan::new(0, word.len() as u32);
111        if let Some(id) = self.walk(word.as_bytes()) {
112            let (lemma, features) = &self.entries[id];
113            results.push(FstResult {
114                lemma: lemma.clone(),
115                features: features.clone(),
116                span,
117            });
118            return results;
119        }
120        // Suffix-based morphology: try stripping each suffix and re-walking.
121        for rule in SUFFIX_RULES {
122            if let Some(stem) = word.strip_suffix(rule.suffix) {
123                if stem.is_empty() {
124                    continue;
125                }
126                // Candidate stems to try, in priority order. For "ies" we also
127                // try the "y" re-write ("cities" → "city").
128                let mut candidates: Vec<String> = vec![stem.to_string()];
129                if rule.suffix == "ies" {
130                    candidates.push(format!("{}y", stem));
131                }
132                for cand in candidates {
133                    if let Some(id) = self.walk(cand.as_bytes()) {
134                        let (lemma, base_features) = &self.entries[id];
135                        let features = if base_features.is_empty() {
136                            rule.feature.to_string()
137                        } else {
138                            format!("{}|{}", base_features, rule.feature)
139                        };
140                        results.push(FstResult {
141                            lemma: lemma.clone(),
142                            features,
143                            span,
144                        });
145                    }
146                }
147                if !results.is_empty() {
148                    return results;
149                }
150            }
151        }
152        results
153    }
154
155    /// Pure trie walk — no allocation. Returns the entry id at the terminal
156    /// node, or `None` if the surface is absent.
157    fn walk(&self, bytes: &[u8]) -> Option<usize> {
158        let mut state = 0usize;
159        for &b in bytes {
160            state = self.nodes[state].get(&b).copied()?;
161        }
162        self.out[state]
163    }
164
165    /// Number of stored entries.
166    pub fn entry_count(&self) -> usize {
167        self.entries.len()
168    }
169}
170
171fn split_payload(payload: &str) -> (String, String) {
172    match payload.find('|') {
173        Some(idx) => (payload[..idx].to_string(), payload[idx + 1..].to_string()),
174        None => (payload.to_string(), String::new()),
175    }
176}
177
178#[cfg(test)]
179mod tests {
180    use super::*;
181
182    fn sample_dict() -> FstDict {
183        FstDict::from_entries(&[
184            ("cat".into(), "cat|N".into()),
185            ("dog".into(), "dog|N".into()),
186            ("walk".into(), "walk|V".into()),
187            ("carry".into(), "carry|V".into()),
188            ("city".into(), "city|N".into()),
189        ])
190    }
191
192    #[test]
193    fn lookup_known_word() {
194        let d = sample_dict();
195        let r = d.lookup("cat");
196        assert_eq!(r.len(), 1);
197        assert_eq!(r[0].lemma, "cat");
198        assert_eq!(r[0].features, "N");
199        assert_eq!(r[0].span, DocSpan::new(0, 3));
200    }
201
202    #[test]
203    fn lookup_unknown_word_returns_empty() {
204        let d = sample_dict();
205        let r = d.lookup("xyzzy");
206        assert!(r.is_empty());
207    }
208
209    #[test]
210    fn suffix_plural_s() {
211        let d = sample_dict();
212        let r = d.lookup("cats");
213        assert_eq!(r.len(), 1);
214        assert_eq!(r[0].lemma, "cat");
215        assert!(r[0].features.contains("PL"));
216    }
217
218    #[test]
219    fn suffix_past_ed() {
220        let d = sample_dict();
221        let r = d.lookup("walked");
222        assert_eq!(r.len(), 1);
223        assert_eq!(r[0].lemma, "walk");
224        assert!(r[0].features.contains("PAST"));
225    }
226
227    #[test]
228    fn suffix_ies_to_y() {
229        let d = sample_dict();
230        let r = d.lookup("cities");
231        assert!(!r.is_empty());
232        assert_eq!(r[0].lemma, "city");
233        assert!(r[0].features.contains("PL"));
234    }
235
236    #[test]
237    fn suffix_ing() {
238        let d = sample_dict();
239        let r = d.lookup("walking");
240        assert_eq!(r.len(), 1);
241        assert_eq!(r[0].lemma, "walk");
242        assert!(r[0].features.contains("VING"));
243    }
244
245    #[test]
246    fn entry_count() {
247        let d = sample_dict();
248        assert_eq!(d.entry_count(), 5);
249    }
250}