qualia_core_db/nlp/
fst.rs1use super::span::DocSpan;
12use std::collections::HashMap;
13
14#[derive(Debug, Clone, PartialEq, Eq)]
16pub struct FstResult {
17 pub lemma: String,
18 pub features: String,
19 pub span: DocSpan,
23}
24
25struct 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
59pub struct FstDict {
61 nodes: Vec<HashMap<u8, usize>>,
63 out: Vec<Option<usize>>,
65 entries: Vec<(String, String)>,
67}
68
69impl FstDict {
70 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 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 for rule in SUFFIX_RULES {
122 if let Some(stem) = word.strip_suffix(rule.suffix) {
123 if stem.is_empty() {
124 continue;
125 }
126 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 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 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}