tobogganSe connecter

packages

The Louise packages, each released on its own

Clone avec HTTPS, un jeton personnel en mot de passe, ou avec SSH, une clé ajoutée dans vos paramètres.

Packages: search, a trigram inverted index89988a5 · il y a 3 sem.
261 lignes · 6875 octetsBrut · Historique
1/// A trigram inverted index over a small corpus — a user's notes, say
2/// (toki2's shape): [`build`] the documents, then [`search`] answers the
3/// ids of the documents containing a query, as a substring match on the
4/// [normalized](normalize) text.
5///
6/// import search
7///
8/// let idx = search.build [(1, "Toki Pona notes"), (2, "TODO: plant the toki pona stickers")]
9/// search.search idx "toki" // [1, 2]
10/// search.search idx "PONA" // [1, 2]: case-insensitive
11///
12/// Indexing extracts the distinct trigrams (3-character windows) of each
13/// normalized document and posts the document's id to each trigram's list.
14/// A query's trigrams intersect those lists (roaring-style compressed
15/// bitmaps, `search/bitmap`) into candidates, and each candidate is
16/// verified with a real substring test, so a search answers exactly the
17/// documents containing the query — the trigrams only narrow the scan.
18///
19/// Queries shorter than three characters have no trigram: they scan every
20/// document instead (fine for a per-user corpus). The index stores the
21/// normalized text of every document for verification: memory is the
22/// corpus's size on top of the postings.
23///
24/// The index is a value: `add` and `remove` return a new one and leave the
25/// old as it was, so a process can keep one per user and swap it in.
26
27import bitmap
28import std/dict.{type Dict}
29import std/list
30import std/string
31
32/// A document's id, chosen by the caller; non-negative. Ids are the values
33/// of the postings' bitmaps, so dense small ids compress best.
34pub type DocId = Int
35
36/// An inverted index over a corpus of documents. Build one with [`build`],
37/// change it with [`add`] and [`remove`], query it with [`search`].
38pub opaque type Index
39{ Index(
40 // The normalized text of each document, for verifying candidates.
41 docs: Dict<
42 DocId
43 , String
44 > // Each trigram's posting list: the documents containing it.
45 , postings: Dict<String, bitmap.Bitmap>
46 )
47}
48
49/// The empty index.
50pub fn empty :: -> Index
51{
52 Index(dict.empty (), dict.empty ())
53}
54
55/// The number of documents.
56pub fn size :: idx: Index -> Int
57{
58 dict.size idx.docs
59}
60
61pub fn is_empty :: idx: Index -> Bool
62{
63 dict.is_empty idx.docs
64}
65
66/// The text compared and indexed: lowercase, without leading or trailing
67/// whitespace.
68pub fn normalize :: text: String -> String
69{
70 string.trim (string.to_lower text)
71}
72
73/// The distinct trigrams (3-character windows) of `text`.
74pub fn trigrams :: text: String -> List<String>
75{
76 dict.keys (windows text 0 (string.length text) (dict.empty ()))
77}
78
79fn windows ::
80 text: String
81 i: Int
82 n: Int
83 acc: Dict<String, ()>
84 -> Dict<String, ()>
85{
86 if i + 3 <= n
87 {
88 windows text (i + 1) n (dict.insert acc (string.slice text i (i + 3)) ())
89 }
90 else
91 {
92 acc
93 }
94}
95
96/// An index of `docs`. A duplicate id keeps its last text. Panics on a
97/// negative id.
98pub fn build :: docs: List<(DocId, String)> -> Index
99{
100 let (docs_dict, lists) =
101 list.fold
102 docs
103 (dict.empty (), dict.empty ())
104 fn acc pair
105 {
106 let (d, lists) = acc
107 let (id, text) = pair
108 if id < 0
109 {
110 panic "search.build: negative id {id}"
111 }
112 else
113 {
114 let text = normalize text
115 (dict.insert d id text, collect (trigrams text) id lists)
116 }
117 }
118 Index( docs: docs_dict
119 , postings: dict.fold
120 lists
121 (dict.empty ())
122 fn acc t ids { dict.insert acc t (bitmap.from_list ids) }
123 )
124}
125
126/// `lists` with `id` prepended to each of `ts`' posting lists.
127fn collect ::
128 ts: List<String>
129 id: DocId
130 lists: Dict<String, List<DocId>>
131 -> Dict<String, List<DocId>>
132{
133 use lists, t <- list.fold ts lists
134 let ids = match dict.get lists t { Some(ids) -> ids, None -> [] }
135 dict.insert lists t [id, ..ids]
136}
137
138/// `idx` with `text` stored under `id`, replacing any text it had. Panics
139/// on a negative id.
140pub fn add :: idx: Index id: DocId text: String -> Index
141{
142 let idx = remove idx id
143 let text = normalize text
144 let postings =
145 {
146 use postings, t <- list.fold (trigrams text) idx.postings
147 let posting = match dict.get postings t
148 { Some(posting) -> posting, None -> bitmap.empty () }
149 dict.insert postings t (bitmap.add posting id)
150 }
151 Index(docs: dict.insert idx.docs id text, postings: postings)
152}
153
154/// `idx` without `id` (no change if it is absent).
155pub fn remove :: idx: Index id: DocId -> Index
156{
157 match dict.get idx.docs id
158 { None -> idx
159 , Some(old) ->
160 {
161 let postings =
162 {
163 use postings, t <- list.fold (trigrams old) idx.postings
164 match dict.get postings t
165 { None -> postings
166 , Some(posting) ->
167 {
168 let posting = bitmap.remove posting id
169 if bitmap.is_empty posting
170 {
171 dict.remove postings t
172 }
173 else
174 {
175 dict.insert postings t posting
176 }
177 }
178 }
179 }
180 Index(docs: dict.remove idx.docs id, postings: postings)
181 }
182 }
183}
184
185/// The ids of the documents containing `query`, ascending: a substring
186/// match on the normalized text. An empty query matches every document;
187/// one shorter than three characters scans every document.
188pub fn search :: idx: Index query: String -> List<DocId>
189{
190 let query = normalize query
191 let n = string.length query
192 if n == 0
193 {
194 dict.keys idx.docs
195 }
196 else if n < 3
197 {
198 scan idx query
199 }
200 else
201 {
202 match postings_of idx (trigrams query) []
203 { None -> []
204 , Some(postings) ->
205 {
206 let postings =
207 list.sort_by
208 postings
209 fn a b { compare (bitmap.size a) (bitmap.size b) }
210 use id <- list.filter (bitmap.to_list (intersect_all postings))
211 match dict.get idx.docs id
212 { Some(text) -> string.contains text query, None -> False }
213 }
214 }
215 }
216}
217
218/// Each trigram's posting list, or `None` when one has none (the query
219/// matches nothing).
220fn postings_of ::
221 idx: Index
222 ts: List<String>
223 acc: List<bitmap.Bitmap>
224 -> Option<List<bitmap.Bitmap>>
225{
226 match ts
227 { [] -> Some(list.reverse acc)
228 , [t, ..rest] -> match dict.get idx.postings t
229 { Some(posting) -> postings_of idx rest [posting, ..acc], None -> None }
230 }
231}
232
233fn intersect_all :: postings: List<bitmap.Bitmap> -> bitmap.Bitmap
234{
235 match postings
236 { [] -> bitmap.empty ()
237 , [first, ..rest] -> list.fold rest first bitmap.intersect
238 }
239}
240
241/// The ids of the documents containing `query`: a scan, for queries too
242/// short for a trigram.
243fn scan :: idx: Index query: String -> List<DocId>
244{
245 list.reverse
246 ( dict.fold
247 idx.docs
248 []
249 fn acc id text
250 {
251 if string.contains text query
252 {
253 [id, ..acc]
254 }
255 else
256 {
257 acc
258 }
259 }
260 )
261}