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.

506 lignes · 10661 octetsBrut · Historique
1/// Roaring-style compressed bitmaps over non-negative `Int`s: the posting
2/// lists of the trigram index (`search`). A set is split into containers of
3/// 65,536 values each (the low 16 bits), keyed by the high bits; a container
4/// is a sorted list while it holds at most 4,096 values and a 65,536-bit
5/// bitmap (a big `Int`) past that, so intersections stay cheap for both
6/// sparse and dense postings. Intersecting two bitmap containers is one
7/// `int.and`; the result drops back to a list when it gets sparse again.
8///
9/// (After "Roaring Bitmaps" by Chambi, Lemire et al., arXiv:1402.6407, with
10/// a persistent list for the array container.)
11
12import std/dict.{type Dict}
13import std/int
14import std/list
15
16/// A set of non-negative `Int`s. `add` and `remove` return a new set and
17/// leave the old one as it was.
18pub opaque type Bitmap { Bitmap(containers: Dict<Int, Container>, size: Int) }
19
20/// The values of one 16-bit container: a sorted list (at most
21/// `container_max()` values) or a bitmap of `container_bits()` bits with its
22/// population count.
23type Container { Arr(List<Int>), Bits(bits: Int, card: Int) }
24
25/// The most values an `Arr` holds before it becomes a `Bits`: the point
26/// where both take 65,536 bits.
27fn container_max :: -> Int
28{
29 4096
30}
31
32/// The values a container covers: its key shifted left by 16.
33fn container_bits :: -> Int
34{
35 65536
36}
37
38/// The empty set.
39pub fn empty :: -> Bitmap
40{
41 Bitmap(dict.empty (), 0)
42}
43
44/// The number of values.
45pub fn size :: b: Bitmap -> Int
46{
47 b.size
48}
49
50pub fn is_empty :: b: Bitmap -> Bool
51{
52 b.size == 0
53}
54
55/// `(array containers, bitmap containers)`: which containers the set uses,
56/// for tests and tuning.
57pub fn stats :: b: Bitmap -> (Int, Int)
58{
59 dict.fold
60 b.containers
61 (0, 0)
62 fn acc _ c
63 {
64 let (arrays, bitmaps) = acc
65 match c
66 { Arr(_) -> (arrays + 1, bitmaps), Bits(_, _) -> (arrays, bitmaps + 1) }
67 }
68}
69
70/// `b` with `id` added (no change if it is present). Panics on a negative
71/// `id`.
72pub fn add :: b: Bitmap id: Int -> Bitmap
73{
74 if id < 0
75 {
76 panic "search/bitmap.add: negative id {id}"
77 }
78 else
79 {
80 let high = id / container_bits ()
81 let low = id % container_bits ()
82 let ( containers
83 , added
84 ) = match dict.get b.containers high
85 { None -> (dict.insert b.containers high (Arr([low])), True)
86 , Some(c) ->
87 {
88 let (c2, added) = add_to c low
89 (dict.insert b.containers high c2, added)
90 }
91 }
92 Bitmap(containers, if added { b.size + 1 } else { b.size })
93 }
94}
95
96/// `b` without `id` (no change if it is absent).
97pub fn remove :: b: Bitmap id: Int -> Bitmap
98{
99 if id < 0
100 {
101 b
102 }
103 else
104 {
105 let high = id / container_bits ()
106 let low = id % container_bits ()
107 match dict.get b.containers high
108 { None -> b
109 , Some(c) ->
110 {
111 let (c2, removed) = remove_from c low
112 if !removed
113 {
114 b
115 }
116 else if card c2 == 0
117 {
118 Bitmap(dict.remove b.containers high, b.size - 1)
119 }
120 else
121 {
122 Bitmap(dict.insert b.containers high c2, b.size - 1)
123 }
124 }
125 }
126 }
127}
128
129pub fn contains :: b: Bitmap id: Int -> Bool
130{
131 if id < 0
132 {
133 False
134 }
135 else
136 {
137 match dict.get b.containers (id / container_bits ())
138 { None -> False, Some(c) -> member c (id % container_bits ()) }
139 }
140}
141
142/// The values in both, container by container.
143pub fn intersect :: a: Bitmap b: Bitmap -> Bitmap
144{
145 walk (dict.to_list a.containers) (dict.to_list b.containers) [] 0
146}
147
148fn walk ::
149 xs: List<(Int, Container)>
150 ys: List<(Int, Container)>
151 acc: List<(Int, Container)>
152 size: Int
153 -> Bitmap
154{
155 match (xs, ys)
156 { ( [(ka, ca), ..xs1]
157 , [(kb, cb), ..ys1]
158 ) -> if ka == kb
159 {
160 let c = intersect_container ca cb
161 if card c == 0
162 {
163 walk xs1 ys1 acc size
164 }
165 else
166 {
167 walk xs1 ys1 [(ka, c), ..acc] (size + card c)
168 }
169 }
170 else if ka < kb
171 {
172 walk xs1 ys acc size
173 }
174 else
175 {
176 walk xs ys1 acc size
177 }
178 , _ -> Bitmap(dict.from_list (list.reverse acc), size)
179 }
180}
181
182/// The values, ascending.
183pub fn to_list :: b: Bitmap -> List<Int>
184{
185 use (high, c) <- list.flat_map (dict.to_list b.containers)
186 list.map (values c) fn low { high * container_bits () + low }
187}
188
189/// A set of `ids` (duplicates are ignored). Panics on a negative id.
190pub fn from_list :: ids: List<Int> -> Bitmap
191{
192 if list.any ids fn id { id < 0 }
193 {
194 panic "search/bitmap.from_list: negative id"
195 }
196 else
197 {
198 from_sorted_list (list.sort ids)
199 }
200}
201
202/// A set of `ids`, which must be ascending (duplicates are dropped):
203/// [`from_list`] without the sort. Panics on a negative id or one below
204/// its predecessor.
205pub fn from_sorted_list :: ids: List<Int> -> Bitmap
206{
207 group (dedupe_checked ids (0 - 1)) [] 0
208}
209
210/// `xs` without duplicates; panics unless `xs` is ascending, every id
211/// above `prev`.
212fn dedupe_checked :: xs: List<Int> prev: Int -> List<Int>
213{
214 match xs
215 { [] -> []
216 , [ x
217 , ..rest
218 ] -> if x < 0
219 {
220 panic "search/bitmap.from_sorted_list: negative id"
221 }
222 else if x < prev
223 {
224 panic "search/bitmap.from_sorted_list: ids not ascending"
225 }
226 else if x == prev
227 {
228 dedupe_checked rest prev
229 }
230 else
231 {
232 [x, ..dedupe_checked rest x]
233 }
234 }
235}
236
237/// Containers of the sorted distinct `ids`, grouped by their high bits.
238fn group :: ids: List<Int> acc: List<(Int, Container)> size: Int -> Bitmap
239{
240 match ids
241 { [] -> Bitmap(dict.from_list (list.reverse acc), size)
242 , [id, ..] ->
243 {
244 let high = id / container_bits ()
245 let (run, rest) = span_run ids high []
246 let c = container_of run
247 group rest [(high, c), ..acc] (size + card c)
248 }
249 }
250}
251
252/// The longest prefix of `ids` (sorted) with high bits `high`, and the rest.
253fn span_run :: ids: List<Int> high: Int acc: List<Int> -> (List<Int>, List<Int>)
254{
255 match ids
256 { [id, ..rest] if id / container_bits () == high ->
257 span_run rest high [id % container_bits (), ..acc]
258 , _ -> (list.reverse acc, ids)
259 }
260}
261
262/// A container of the sorted distinct low bits `run`.
263fn container_of :: run: List<Int> -> Container
264{
265 if list.length run > container_max ()
266 {
267 bits_of_list run
268 }
269 else
270 {
271 Arr(run)
272 }
273}
274
275// ---- containers ----------------------------------------------------------
276
277fn card :: c: Container -> Int
278{
279 match c { Arr(xs) -> list.length xs, Bits(_, n) -> n }
280}
281
282fn member :: c: Container v: Int -> Bool
283{
284 match c { Arr(xs) -> sorted_member xs v, Bits(bits, _) -> int.bit bits v }
285}
286
287fn sorted_member :: xs: List<Int> v: Int -> Bool
288{
289 match xs
290 { [] -> False
291 , [ x
292 , ..rest
293 ] -> if x == v
294 {
295 True
296 }
297 else if x > v
298 {
299 False
300 }
301 else
302 {
303 sorted_member rest v
304 }
305 }
306}
307
308/// The container's values, ascending.
309fn values :: c: Container -> List<Int>
310{
311 match c { Arr(xs) -> xs, Bits(bits, _) -> bits_to_list bits }
312}
313
314/// `c` with `v`, and whether that changed it.
315fn add_to :: c: Container v: Int -> (Container, Bool)
316{
317 match c
318 { Arr(xs) ->
319 {
320 let (ys, added) = insert_sorted xs v
321 if added && list.length ys > container_max ()
322 {
323 (bits_of_list ys, True)
324 }
325 else
326 {
327 (Arr(ys), added)
328 }
329 }
330 , Bits(bits, n) -> if int.bit bits v
331 {
332 (c, False)
333 }
334 else
335 {
336 (Bits(int.or bits (int.shift_left 1 v), n + 1), True)
337 }
338 }
339}
340
341/// `c` without `v`, and whether that changed it.
342fn remove_from :: c: Container v: Int -> (Container, Bool)
343{
344 match c
345 { Arr(xs) ->
346 {
347 let (ys, removed) = remove_sorted xs v
348 (Arr(ys), removed)
349 }
350 , Bits
351 ( bits
352 , n
353 ) -> if int.bit bits v
354 {
355 let bits2 = int.and bits (int.not (int.shift_left 1 v))
356 if n - 1 <= container_max ()
357 {
358 (Arr(bits_to_list bits2), True)
359 }
360 else
361 {
362 (Bits(bits2, n - 1), True)
363 }
364 }
365 else
366 {
367 (c, False)
368 }
369 }
370}
371
372fn intersect_container :: a: Container b: Container -> Container
373{
374 match (a, b)
375 { (Arr(xs), Arr(ys)) -> Arr(intersect_lists xs ys)
376 , (Arr(xs), Bits(bits, _)) -> Arr(list.filter xs fn v { int.bit bits v })
377 , (Bits(bits, _), Arr(ys)) -> Arr(list.filter ys fn v { int.bit bits v })
378 , (Bits(b1, _), Bits(b2, _)) ->
379 {
380 let bits = int.and b1 b2
381 let n = popcount bits
382 if n <= container_max ()
383 {
384 Arr(bits_to_list bits)
385 }
386 else
387 {
388 Bits(bits, n)
389 }
390 }
391 }
392}
393
394/// The values in both sorted lists, ascending.
395fn intersect_lists :: xs: List<Int> ys: List<Int> -> List<Int>
396{
397 merge xs ys []
398}
399
400fn merge :: xs: List<Int> ys: List<Int> acc: List<Int> -> List<Int>
401{
402 match (xs, ys)
403 { ([x, ..xs1], [y, ..ys1]) -> if x == y
404 {
405 merge xs1 ys1 [x, ..acc]
406 }
407 else if x < y
408 {
409 merge xs1 ys acc
410 }
411 else
412 {
413 merge xs ys1 acc
414 }
415 , _ -> list.reverse acc
416 }
417}
418
419/// `xs` (sorted) with `v`, and whether that inserted it.
420fn insert_sorted :: xs: List<Int> v: Int -> (List<Int>, Bool)
421{
422 match xs
423 { [] -> ([v], True)
424 , [x, ..rest] -> if v < x
425 {
426 ([v, ..xs], True)
427 }
428 else if v == x
429 {
430 (xs, False)
431 }
432 else
433 {
434 let (ys, inserted) = insert_sorted rest v
435 ([x, ..ys], inserted)
436 }
437 }
438}
439
440/// `xs` (sorted) without `v`, and whether that removed it.
441fn remove_sorted :: xs: List<Int> v: Int -> (List<Int>, Bool)
442{
443 match xs
444 { [] -> ([], False)
445 , [x, ..rest] -> if v == x
446 {
447 (rest, True)
448 }
449 else if v < x
450 {
451 (xs, False)
452 }
453 else
454 {
455 let (ys, removed) = remove_sorted rest v
456 ([x, ..ys], removed)
457 }
458 }
459}
460
461// ---- bitmaps as big Ints ---------------------------------------------------
462
463/// The bits set in `n`.
464fn popcount :: n: Int -> Int
465{
466 popcount_acc n 0
467}
468
469fn popcount_acc :: n: Int acc: Int -> Int
470{
471 if n == 0
472 {
473 acc
474 }
475 else
476 {
477 // Clear the lowest set bit.
478 popcount_acc (int.and n (n - 1)) (acc + 1)
479 }
480}
481
482/// The positions of the set bits of `n`, ascending.
483fn bits_to_list :: bits: Int -> List<Int>
484{
485 bits_up bits []
486}
487
488fn bits_up :: bits: Int acc: List<Int> -> List<Int>
489{
490 if bits == 0
491 {
492 list.reverse acc
493 }
494 else
495 {
496 // The lowest set bit of `bits` alone (two's complement).
497 let low = int.and bits (0 - bits)
498 bits_up (int.xor bits low) [int.bit_length low - 1, ..acc]
499 }
500}
501
502/// A bitmap container of the sorted `xs` (more than `container_max()`).
503fn bits_of_list :: xs: List<Int> -> Container
504{
505 Bits(list.fold xs 0 fn b v { int.or b (int.shift_left 1 v) }, list.length xs)
506}