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.
Dernier runRéussi#28 · main · 3 min 34 s
0Étoiles
0Forks
3Issues
| 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 | |
| 27 | import bitmap |
| 28 | import std/dict.{type Dict} |
| 29 | import std/list |
| 30 | import 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. |
| 34 | pub 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`]. |
| 38 | pub 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. |
| 50 | pub fn empty :: -> Index |
| 51 | { |
| 52 | Index(dict.empty (), dict.empty ()) |
| 53 | } |
| 54 | |
| 55 | /// The number of documents. |
| 56 | pub fn size :: idx: Index -> Int |
| 57 | { |
| 58 | dict.size idx.docs |
| 59 | } |
| 60 | |
| 61 | pub 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. |
| 68 | pub fn normalize :: text: String -> String |
| 69 | { |
| 70 | string.trim (string.to_lower text) |
| 71 | } |
| 72 | |
| 73 | /// The distinct trigrams (3-character windows) of `text`. |
| 74 | pub fn trigrams :: text: String -> List<String> |
| 75 | { |
| 76 | dict.keys (windows text 0 (string.length text) (dict.empty ())) |
| 77 | } |
| 78 | |
| 79 | fn 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. |
| 98 | pub 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. |
| 127 | fn 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. |
| 140 | pub 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). |
| 155 | pub 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. |
| 188 | pub 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). |
| 220 | fn 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 | |
| 233 | fn 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. |
| 243 | fn 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 | } |