Expand description
The streaming k-mer counter (D1).
One pass over the normalised rows counts, for every position p (1 ≤ p ≤ L − k + 1), each distinct k-mer starting at p, and — with header metadata — the number of sequences per (k-mer, header value). Nothing proportional to sequences × positions is ever stored: memory is Σₚ (distinct k-mers × (k + 25) bytes + metadata cells × ~19 bytes) plus two batches.
- Exact interning. Each window is hashed with a Karp–Rabin rolling hash modulo the Mersenne prime 2⁶¹ − 1 (Karp & Rabin 1987), updated in O(1) per position, and looked up in a per-position table whose candidates are verified byte by byte, so collisions can never merge different k-mers. For k > 32 a transition cache maps (k-mer id at p − 1, next residue) to the id at p, which skips the O(k) comparison for repeated transitions.
- Any k. 1 ≤ k ≤ L; there is no packing into machine words.
- Parallelism. Positions are split into contiguous shards processed in parallel on the caller’s rayon pool; memory does not grow with the number of threads (each shard owns its positions), and results do not depend on the thread count or batch size (k-mer ids are internal; outputs are sorted by count and bytes).
Structs§
- Engine
- The streaming counter.
- Position
Counts - Counts of one position after all input was read.