qualia_core_db/nlp/
gazetteer.rs1use std::collections::HashMap;
4use std::collections::VecDeque;
5
6use super::span::DocSpan;
7use super::terms::{Lexeme, DEFAULT_LEXICON};
8
9#[derive(Debug, Clone, PartialEq, Eq)]
10pub struct Hit {
11 pub span: DocSpan,
12 pub iri: &'static str,
13 pub surface: &'static str,
14}
15
16struct Node {
17 next: HashMap<u8, u16>,
18 fail: u16,
19 out: Vec<u16>,
20}
21
22pub struct Gazetteer {
24 nodes: Vec<Node>,
25 patterns: Vec<&'static Lexeme>,
26}
27
28impl Default for Gazetteer {
29 fn default() -> Self {
30 Self::from_lexicon(DEFAULT_LEXICON)
31 }
32}
33
34impl Gazetteer {
35 pub fn from_lexicon(lex: &'static [Lexeme]) -> Self {
37 let mut nodes = vec![Node {
38 next: HashMap::new(),
39 fail: 0,
40 out: Vec::new(),
41 }];
42 let mut patterns = Vec::new();
43 for lexeme in lex {
44 let id = patterns.len() as u16;
45 patterns.push(lexeme);
46 let mut state = 0u16;
47 for &b in ascii_fold(lexeme.surface).as_bytes() {
48 if let Some(&n) = nodes[state as usize].next.get(&b) {
49 state = n;
50 } else {
51 let next_id = nodes.len() as u16;
52 nodes.push(Node {
53 next: HashMap::new(),
54 fail: 0,
55 out: Vec::new(),
56 });
57 nodes[state as usize].next.insert(b, next_id);
58 state = next_id;
59 }
60 }
61 nodes[state as usize].out.push(id);
62 }
63 build_fail_links(&mut nodes);
64 Self { nodes, patterns }
65 }
66
67 pub fn pattern_count(&self) -> usize {
69 self.patterns.len()
70 }
71
72 pub fn find(&self, source: &str) -> Vec<Hit> {
74 let folded = ascii_fold(source);
75 let bytes = folded.as_bytes();
76 let mut state = 0u16;
77 let mut raw = Vec::new();
78 for (i, &b) in bytes.iter().enumerate() {
79 while state != 0 && !self.nodes[state as usize].next.contains_key(&b) {
80 state = self.nodes[state as usize].fail;
81 }
82 if let Some(&n) = self.nodes[state as usize].next.get(&b) {
83 state = n;
84 }
85 let mut walk = state;
86 loop {
87 for &pid in &self.nodes[walk as usize].out {
88 let lex = self.patterns[pid as usize];
89 let len = lex.surface.len();
90 if i + 1 < len {
91 continue;
92 }
93 let start = i + 1 - len;
94 if !byte_boundary_ok(source, start, i + 1) {
95 continue;
96 }
97 raw.push(Hit {
98 span: DocSpan::new(start as u32, (i + 1) as u32),
99 iri: lex.iri,
100 surface: lex.surface,
101 });
102 }
103 if walk == 0 {
104 break;
105 }
106 walk = self.nodes[walk as usize].fail;
107 }
108 }
109 prefer_longest_nonoverlapping(raw)
110 }
111}
112
113fn build_fail_links(nodes: &mut [Node]) {
114 let mut q = VecDeque::new();
115 let roots: Vec<(u8, u16)> = nodes[0].next.iter().map(|(&b, &n)| (b, n)).collect();
116 for (_, n) in roots {
117 nodes[n as usize].fail = 0;
118 q.push_back(n);
119 }
120 while let Some(v) = q.pop_front() {
121 let edges: Vec<(u8, u16)> = nodes[v as usize]
122 .next
123 .iter()
124 .map(|(&b, &n)| (b, n))
125 .collect();
126 for (b, u) in edges {
127 let mut f = nodes[v as usize].fail;
128 while f != 0 && !nodes[f as usize].next.contains_key(&b) {
129 f = nodes[f as usize].fail;
130 }
131 let fail = nodes[f as usize].next.get(&b).copied().unwrap_or(0);
132 nodes[u as usize].fail = fail;
133 let inherited = nodes[fail as usize].out.clone();
134 nodes[u as usize].out.extend(inherited);
135 q.push_back(u);
136 }
137 }
138}
139
140fn ascii_fold(s: &str) -> String {
141 s.chars()
142 .map(|c| {
143 if c.is_ascii_alphabetic() {
144 c.to_ascii_lowercase()
145 } else {
146 c
147 }
148 })
149 .collect()
150}
151
152fn byte_boundary_ok(source: &str, start: usize, end: usize) -> bool {
153 if start > end || end > source.len() {
154 return false;
155 }
156 if !source.is_char_boundary(start) || !source.is_char_boundary(end) {
157 return false;
158 }
159 let prev_ok = start == 0 || !is_word_byte(source.as_bytes()[start - 1]);
160 let next_ok = end == source.len() || !is_word_byte(source.as_bytes()[end]);
161 prev_ok && next_ok
162}
163
164fn is_word_byte(b: u8) -> bool {
165 b.is_ascii_alphanumeric() || b == b'_'
166}
167
168fn prefer_longest_nonoverlapping(mut hits: Vec<Hit>) -> Vec<Hit> {
169 hits.sort_by(|a, b| {
170 a.span
171 .start_utf8
172 .cmp(&b.span.start_utf8)
173 .then_with(|| b.span.end_utf8.cmp(&a.span.end_utf8))
174 });
175 let mut out = Vec::new();
176 let mut cursor = 0u32;
177 for hit in hits {
178 if hit.span.start_utf8 >= cursor {
179 cursor = hit.span.end_utf8;
180 out.push(hit);
181 }
182 }
183 out
184}
185
186#[cfg(test)]
187mod tests {
188 use super::*;
189
190 #[test]
191 fn finds_north_spring_not_bare_north() {
192 let g = Gazetteer::default();
193 let src = "North Spring is the reference catchment.";
194 let hits = g.find(src);
195 assert!(hits.iter().any(|h| h.surface == "North Spring"));
196 assert!(hits.iter().any(|h| h.surface == "reference catchment"));
197 assert!(!hits
198 .iter()
199 .any(|h| h.surface == "catchment" && h.span.start_utf8 > 20));
200 }
201
202 #[test]
203 fn principal_identity_only() {
204 let g = Gazetteer::default();
205 let hits = g.find("Recorded by Timothy Charles Holborn.");
206 assert_eq!(hits.len(), 1);
207 assert_eq!(hits[0].iri, "did:qualia:timothy_charles_holborn");
208 }
209}