Skip to main content

qualia_core_db/nlp/
gazetteer.rs

1//! Aho-Corasick gazetteer over interned lexicon surfaces.
2
3use 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
22/// Compiled automaton. Cold construction; scan is a byte walk.
23pub 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    /// Builds `Gazetteer` from `lexicon`.
36    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    /// Number of patterns in the compiled automaton.
68    pub fn pattern_count(&self) -> usize {
69        self.patterns.len()
70    }
71
72    /// `Gazetteer::find`.
73    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}