DEV Community: SEN LLC

Building a Cuckoo Filter CLI in Rust — the Deletion a Bloom Filter Can't Do, Partial-Key Cuckoo Hashing, and a High Load Factor via Relocation

SEN LLC — Tue, 30 Jun 2026 01:07:19 +0000

A Cuckoo filter as a Rust CLI. Like a Bloom filter it answers "is X in the set?" with "definitely absent" or "probably present" and stores no keys — but it adds the one thing Bloom famously can't do: delete. The hinges: (1) partial-key cuckoo hashing — an item's two candidate buckets are i2 = i1 XOR hash(fingerprint), so you can find a stored fingerprint's alternate bucket from the fingerprint alone (alt(alt(i)) == i); (2) when buckets fill, it relocates occupants to pack the table to ~95%; and (signature) deletion. A companion to #274's Bloom filter — the same question, a different design.

📦 GitHub: https://github.com/sen-ltd/cuckoo-filter

What a Cuckoo filter is

Like a Bloom filter it answers "is X in the set?" with "definitely absent"
(always correct) or "probably present" (a false positive at a rate you pick),
storing no keys. What it adds is the thing a Bloom filter can't do: delete.
And each lookup touches at most two buckets, so it's friendlier to cache than a
Bloom filter's k scattered bit probes.

Instead of setting bits, it stores a short fingerprint of each item in one of
two candidate buckets of a hash table (4 slots each).

Here's the CLI, real output:

$ cuckoo check apple mango dragonfruit
apple        probably present
mango        probably present
dragonfruit  definitely absent

$ cuckoo delete mango          # ← a Bloom filter cannot do this
mango  deleted

$ cuckoo check apple mango
apple  probably present
mango  definitely absent

Delete mango and it flips to "definitely absent" while apple stays present —
the defining difference from Bloom.

Hinge 1: partial-key cuckoo hashing

An item's two candidate buckets are

i1 = hash(x)
i2 = i1 XOR hash(fingerprint(x))

The second is the first XORed with something derived only from the fingerprint.
So given a fingerprint sitting in bucket i, you can compute its alternate
bucket without knowing the original item — and doing it twice returns you home.
That involution is the whole trick:

fn alt(&self, i: usize, fp: u16) -> usize {
    let hf = mix64(fp as u64) as usize & self.mask();
    i ^ hf
}

#[test]
fn alt_is_an_involution() {
    let cf = CuckooFilter::new(1024, 12);
    assert_eq!(cf.alt(cf.alt(i, fp), fp), i); // always returns home
}

Because the table size is a power of two, XOR keeps the alternate index in
range and alt(alt(i)) == i holds exactly.

Hinge 2: relocation buys a high load factor

On insert, if both candidate buckets are full, the filter doesn't give up — it
kicks: evict a random occupant, carry it to its alternate bucket, repeat
(up to 500 hops). Because any fingerprint can find its alternate home from itself
alone, this cascade works, and it packs the table tight:

let mut i = if self.next_rng() & 1 == 0 { i1 } else { i2 };
let mut carry = fp;
for _ in 0..MAX_KICKS {
    let slot = (self.next_rng() as usize) % BUCKET;
    std::mem::swap(&mut carry, &mut self.data[i * BUCKET + slot]); // evict
    i = self.alt(i, carry);
    if self.try_put(i, carry) { return true; }
}

high_load_factor packs a fixed table and asserts it passes 92% occupancy; with
4 slots per bucket it reaches ~95–99% in practice.

The signature property: delete

Find the fingerprint in either candidate bucket and clear the slot. A Bloom
filter can't — clearing bits there would risk removing other items:

pub fn delete(&mut self, item: &str) -> bool { /* clear fp from i1 or i2 */ }

delete_removes_membership adds two keys, deletes one, and checks the deleted
one reads absent while the other still reads present. (Caveat, as with any Cuckoo
filter: only delete items you actually inserted — deleting a never-added item
could clear a colliding item's fingerprint.)

Persistence

State is a compact binary blob — "CKF1" | num_buckets | fp_bits | count | slots — written hand-rolled, no serde:

src/cuckoo.rs — filter: partial-key hashing, kicking, delete, (de)serialize (12 tests)
src/main.rs   — clap CLI: new / add / check / delete / info, file or stdin

Takeaway

A Cuckoo filter keeps Bloom's strengths — small, no false negatives, no stored
keys — and adds deletion plus better cache locality. The keys are the
involution of partial-key cuckoo hashing, relocation for a high load
factor, and delete itself. Put next to a Bloom filter (#274), it's a clean
study in answering the same question with a different structure.

📦 GitHub: https://github.com/sen-ltd/cuckoo-filter

Building a t-digest CLI in Go — Stream p50/p99/p99.9 in a Few KB, a Scale Function That Keeps Tails Sharp, Exact min/max, and Mergeable Digests

SEN LLC — Sun, 28 Jun 2026 22:57:43 +0000

A t-digest as a Go CLI. It estimates quantiles (p50, p99, p99.9…) of a stream in a few KB instead of sorting the whole thing. The hinges: (1) a scale function k(q) controls centroid size so the median is coarse and the tails stay sharp — p99.9 ends up more precise than the median, by design; (2) q=0/q=1 return the exact min/max while the middle interpolates between centroid means. Plus digests merge. Part four of a probabilistic-data-structure series after #274–276 (membership / cardinality / frequency) — this one is quantiles.

📦 GitHub: https://github.com/sen-ltd/t-digest-cli

What a t-digest is

Exact quantiles need every value in memory, sorted — O(N) space. A t-digest
keeps instead a few hundred centroids, each a (mean, weight) pair
summarizing a cluster of nearby values, and answers any quantile by walking
them. For 500k points that's ~100 centroids and a few KB, regardless of N.

The trap with naive bucketing is the tails: lump values into equal-sized buckets
and your p99.9 is as coarse as your median. A t-digest fixes exactly that — it's
the whole reason the structure exists.

Here's the CLI, real output:

$ td summary --from latencies-ms.txt --exact -c 200
count        500000
min / max    0.3 / 1655.8
centroids    122  (δ=200, 1952 bytes)
p50        20.1183        exact 20.1     (+0.09%)
p90        63.736         exact 63.7     (+0.06%)
p99        162.803        exact 161.9    (+0.56%)
p99.9      322.033        exact 312.6    (+3.02%)

Half a million latency samples summarized in under 2 KB, p99 off by half a
percent.

Hinge 1: a scale function that keeps the tails sharp

Centroids aren't allowed to grow uniformly. A scale function k(q) maps the
quantile q into a "k-space" where each centroid may span at most 1 unit.
With the standard k1 scale,

k(q)    = δ/(2π) · asin(2q − 1)
k⁻¹(k)  = (sin(2π k/δ) + 1) / 2

k is steep near q=0 and q=1, flat near q=0.5. So a centroid covering one
k-unit spans a wide band of quantiles around the median (where precision is
cheap) and a razor-thin band at the tails (where p99.9 lives). The compression
δ is the single knob: more δ → more centroids → tighter quantiles.

q := q0 + (cur.Weight+x.Weight)/total
if q <= qLimit {              // still within 1 k-unit → absorb
    cur = mergeInto(cur, x)
} else {                      // would overflow → seal cur, start a new centroid
    out = append(out, cur)
    q0 += cur.Weight / total
    qLimit = kInv(k(q0) + 1)
    cur = x
}

A test on a uniform stream pins the payoff: p50 is accurate to ~1% while p999 is
held to ~0.2% — tighter at the tail (TestUniformQuantiles).

Hinge 2: exact min/max, interpolated middle

Quantiles are read by walking centroids, accumulating half-weights, and linearly
interpolating between adjacent centroid means. The two ends are special: q=0
and q=1 return the exact min/max (tracked separately), and the tails
interpolate between those extremes and the outermost centroids:

func (t *TDigest) Quantile(q float64) float64 {
    if q <= 0 { return t.min }
    if q >= 1 { return t.max }
    index := q * t.total
    // ... walk centroids, interpolate between means ...
}

TestExactExtremes checks the ends are exact; TestMonotonic checks the whole
curve is non-decreasing.

The signature property: merge

t-digests combine: dump one digest's centroids into another and recompress. The
merged digest answers quantiles as if it had seen both streams — so per-shard or
per-minute digests roll up into a global one with no re-scan:

func (t *TDigest) Merge(other *TDigest) { /* absorb centroids, recompress */ }

$ td merge -o all.tdigest a.tdigest b.tdigest
merged 2 digests → all.tdigest  count=500000  centroids=112

TestMergeApproximatesCombined pins that a merge of two disjoint-range digests
matches the digest of the combined stream across p10…p99 — the same composability
as HyperLogLog's merge-by-max (#275) and Count-Min's merge-by-sum (#276).

Persistence

A digest serializes to a compact blob — "TDG1" | δ | min | max | total | n | (mean, weight)*n — a handful of bytes per centroid. Hand-rolled, no codec.

tdigest/tdigest.go — digest: k1 scale, compress, quantile, merge, (de)serialize (11 tests)
main.go            — CLI: summary / add / quantile / merge / info, file or stdin

Takeaway

The t-digest is the go-to for "measure p99 latency without keeping every sample."
The keys are a scale function that keeps the tails sharp, exact min/max,
and mergeability. With it the probabilistic series now spans membership
(#274), cardinality (#275), frequency (#276), and quantiles (#277) — all the same
instinct of approximating in fixed memory, here expressed as pushing precision
out to the tail where it matters.

📦 GitHub: https://github.com/sen-ltd/t-digest-cli

Building a Count-Min Sketch CLI in Rust — Sizing from a Target Error, d Counters from Two Hashes, No Underestimates, and Mergeable Sketches

SEN LLC — Sat, 27 Jun 2026 23:36:49 +0000

A Count-Min sketch as a Rust CLI. It answers "how many times have I seen X?" with fixed memory and an estimate that always rounds up. The hinges: (1) the table width w and depth d aren't guesses — they're determined by your error factor ε and failure probability δ; (2) you don't need d independent hashes — two are enough, via double hashing (Kirsch–Mitzenmacher); (3) it returns the minimum of its rows, so it can never underestimate — that's a guarantee, not a hope. Part three of a probabilistic-data-structure series after #274's Bloom filter (membership) and #275's HyperLogLog (cardinality) — this one is frequency, completing the trilogy.

📦 GitHub: https://github.com/sen-ltd/count-min-sketch

What a Count-Min sketch is

Where a Bloom filter answers "is X in the set?", a Count-Min sketch answers
"how many times have I seen X?" — approximately, and always rounding up:

the estimate is never below the true count. There are no underestimates.
it may overestimate, by a bounded amount, at a probability you choose.

In return you get a fixed-size table of counters, O(d) updates, and no stored
keys at all. That one-sided error — an honest floor, a hedged ceiling — is
the entire design. It's what you want for "top URLs", "heavy-hitter IPs", or
"trending queries" over a stream too large to count exactly.

Here's the CLI, real output:

$ cms new -e 0.0005 -d 0.01
created .cms  ε=0.0005  δ=0.01  w=5437  d=5  table=27185 counters (106 KiB)

$ cms add --from access.log
added 144000 occurrences  total N=144000  w=5437  d=5  error bound ε·N≈72

$ cms query / /login /api/search /favicon.ico /never-requested
/                 40002      (exact 40000)
/login            18002      (exact 18000)
/api/search       12005      (exact 12000)
/favicon.ico      9001       (exact  9000)
/never-requested  3          (exact     0)

144k log lines summarized in a 106 KiB counter table, heavy hitters estimated to
within a handful (overshoot only, inside the guaranteed ε·N ≈ 72), no keys kept.

Hinge 1: sizing from a target error and confidence

You don't pick the width w and depth d by feel. Given an error factor ε
and a failure probability δ, they're determined:

pub fn optimal_params(epsilon: f64, delta: f64) -> (usize, usize) {
    let w = (std::f64::consts::E / epsilon).ceil();   // columns
    let d = (1.0 / delta).ln().ceil();                // rows
    (w as usize, d as usize)
}

The guarantee they buy: an estimate overshoots the true count by at most ε·N
(N = total of all counts) with probability ≥ 1−δ. A test pins the exact
numbers so a refactor can't silently drift the math:

#[test]
fn optimal_params_match_formula() {
    // ε=0.001, δ=0.01 → w = ceil(e/0.001) = 2719, d = ceil(ln 100) = 5
    let (w, d) = CountMinSketch::optimal_params(0.001, 0.01);
    assert_eq!(w, 2719);
    assert_eq!(d, 5);
}

Hinge 2: d counters from two hashes (Kirsch–Mitzenmacher)

Each item needs one column per row — d independent hashes. Computing five
independent hashes per item would be wasteful, and unnecessary. Two base hashes
are enough:

fn columns(&self, item: &str) -> Vec<usize> {
    let h1 = fnv1a_64(item.as_bytes());
    let h2 = djb2_64(item.as_bytes()) | 1; // force odd so it never collapses
    (0..self.d)
        .map(|i| (h1.wrapping_add((i as u64).wrapping_mul(h2)) % self.w as u64) as usize)
        .collect()
}

Two cheap hashes (FNV-1a and DJB2), d columns. h2 is forced odd so the step
never degenerates to stamping the same column in every row — the same trick as

274's Bloom filter.

Hinge 3: take the minimum — and why it can't underestimate

add bumps the item's counter in every row. Collisions from other items only
ever add to a counter, so the true count sits at or below every row's value.
estimate returns the minimum across rows — the tightest upper bound the
table can give:

pub fn estimate(&self, item: &str) -> u32 {
    self.columns(item).into_iter().enumerate()
        .map(|(row, col)| self.counters[row * self.w + col])
        .min().unwrap_or(0)
}

It's a property, not a hope, and it's tested directly: insert 5000 items with
known true counts and assert estimate ≥ true for every one
(never_underestimates). A second test (overestimate_within_bound) confirms a
heavy hitter among 100k items lands inside the ε·N envelope.

The signature property: merge

Count-Min sketches are linear — two sketches of identical dimensions union by
summing counters element-wise:

pub fn merge(&mut self, other: &CountMinSketch) -> Result<(), CmsError> { /* a[i] += b[i] */ }

The result is exactly the sketch you'd have built from both streams combined,
so per-shard or per-day counts merge with no loss. merge_equals_combined_stream
pins this — a nice mirror of HyperLogLog's (#275) merge-by-max.

Persistence

State is a compact binary blob — "CMS1" | w | d | total | counters — written
hand-rolled, no serde:

src/cms.rs  — sketch: sizing, double hashing, estimate, merge, (de)serialize (12 tests)
src/main.rs — clap CLI: new / add / query / merge / info, file or stdin

Takeaway

The probabilistic trilogy is complete: Bloom = membership (#274),
HyperLogLog = cardinality (#275), Count-Min = frequency (this one). All
share the same instinct — push the error to one side and accept it to buy a tiny,
fixed memory budget. In Count-Min that shows up as a one-sided "never
underestimate" error and a min-of-rows upper bound, with ε/δ as direct
dials on the memory-vs-accuracy trade.

📦 GitHub: https://github.com/sen-ltd/count-min-sketch

Building a HyperLogLog CLI in Go — One Billion Distinct in 16 KB, a Harmonic Mean, a Hash Finalizer, and Mergeable Sketches

SEN LLC — Sat, 27 Jun 2026 13:53:37 +0000

A HyperLogLog cardinality estimator as a Go CLI. It counts the number of distinct items in a massive stream using ~16 KB of fixed memory. The hinges: (1) it records the leading-zero run of each hash into m registers and combines them with a harmonic mean, so one lucky outlier can't blow up the estimate; (2) FNV-1a's weak low bits will wreck the estimate on structured input unless you run a finalizer mixer; (3) two sketches merge with zero loss of accuracy by taking the per-register max. Part two of a probabilistic-data-structure series after #274's Bloom filter.

📦 GitHub: https://github.com/sen-ltd/hyperloglog-cli

What HyperLogLog is

It answers "how many distinct values are in this stream?" Counting exactly means
remembering every key you've seen — a hash set whose memory grows with the answer.
HyperLogLog gives up exactness to make memory constant: count a billion
distinct values to ~1% accuracy in 16 KB, regardless of stream size.

It's what you want for "unique visitors", "distinct IPs", "distinct search
terms" — anywhere an approximate count in a single pass beats an exact count you
can't afford to keep in memory.

Here's the CLI, real output:

$ hll count --from visitors.txt --exact
lines read     100000
estimate       28547
registers      m=16384 (p=14), 16 KB, std error ~0.81%
exact distinct 28905
error          -1.24%

100,000 lines (28,905 truly distinct) estimated as 28,547 from 16 KB of
registers — with not a single key stored.

The idea: rare hash patterns leak scale

Hash each item to 64 random-looking bits. A hash that starts with k zeros is
about as likely as flipping k heads in a row, so spotting one hints you've seen
~2ᵏ distinct values. Tracking a single longest run would be wildly noisy, so HLL
takes the first p bits of the hash to pick a register (bucket), stores the
rank (leading-zero run + 1) of the rest in that bucket, and combines all
m = 2^p registers.

func (h *HLL) Add(item string) bool {
    x := hash(item)
    idx := x >> (64 - h.p) // top p bits select the register
    r := rank(x, h.p)      // leading-zero run of the rest, +1
    if r > h.registers[idx] {
        h.registers[idx] = r
        return true
    }
    return false
}

Hinge 1: a harmonic mean over m buckets

The estimate combines every register:

est := alpha(m) * m * m / sum   // sum = Σ 2^(-register)

Summing 2^(-rank) is a harmonic mean in disguise — buckets that saw long
zero-runs contribute little, so a single lucky outlier can't blow up the estimate
the way an arithmetic mean would. Averaging over m registers drops the relative
standard error to 1.04/√m: at p = 14 that's m = 16384 registers and
~0.81% error, for 16 KB of state (one byte per register).

At low cardinality most registers are still empty and the raw formula is biased,
so HLL hands off to linear counting:

if est <= 2.5*m && zeros > 0 {
    return m * math.Log(m/float64(zeros)) // linear counting
}

TestSmallRangeLinearCounting pins that 50 distinct items estimate to within 3.

Hinge 2: why the hash needs a finalizer

We take the register from the high bits and the rank from the rest. FNV-1a is
fast and dependency-free but has poor avalanche in its low bits — structured
inputs like user00001, user00002 share low-bit structure, which biases bucket
assignment and rank together and drifts the estimate. One MurmurHash3 fmix64
finalizer scrambles all 64 bits so they look independent:

func hash(item string) uint64 {
    f := fnv.New64a()
    _, _ = f.Write([]byte(item))
    x := f.Sum64()
    x ^= x >> 33
    x *= 0xff51afd7ed558ccd
    x ^= x >> 33
    x *= 0xc4ceb9fe1a85ec53
    x ^= x >> 33
    return x
}

TestFinalizerHandlesStructuredInput feeds 100k highly structured keys and
asserts the estimate still lands within tolerance.

Because we hash to 64 bits, the original 2007 paper's large-range correction —
which existed only to undo collisions as a 32-bit space fills near 2³² — is
unnecessary, and omitted.

The signature property: merge

Two sketches union by taking the per-register maximum:

func (h *HLL) Merge(other *HLL) error {
    if h.p != other.p {
        return fmt.Errorf("precision mismatch: %d vs %d", h.p, other.p)
    }
    for i, r := range other.registers {
        if r > h.registers[i] {
            h.registers[i] = r
        }
    }
    return nil
}

The result is exactly the sketch you'd have built by feeding both streams into
one — so distinct counts from different machines, days, or shards combine with
zero loss of accuracy. That's why HLL is a staple of log analytics and
distributed counting.

$ hll merge -o week.hll mon.hll tue.hll
merged 2 sketches → week.hll  union estimate=36248

TestMergeEqualsCombinedStream pins this: merging two disjoint 30k-key sketches
reproduces the combined sketch register for register, and estimates the 60k-key
union to within tolerance.

Persistence

A sketch serializes to a compact blob — "HLL1" | p | registers — exactly
5 + 2^p bytes, the same footprint it occupies in memory. Hand-rolled, no codec.

hll/hll.go — sketch: hashing, rank, estimate, merge, (de)serialize (11 tests)
main.go    — CLI: count / add / estimate / merge / info, file or stdin

Takeaway

HyperLogLog is the textbook case of "give up a little accuracy, get constant
memory." The keys are combining buckets with a harmonic mean so outliers
don't dominate, running a hash finalizer so structured input doesn't drift
the estimate, and the fact that sketches merge by max. Put next to a Bloom
filter (#274), you can see the shared design instinct of probabilistic data
structures: accept a bounded error to buy a tiny, fixed memory budget.

📦 GitHub: https://github.com/sen-ltd/hyperloglog-cli

Building a Bloom Filter CLI in Rust — Sizing from a Target FP Rate, k Hashes from Two, and Guaranteed No False Negatives

SEN LLC — Fri, 26 Jun 2026 00:32:17 +0000

A Bloom filter as a Rust CLI. It answers "is X in the set?" with one of two replies: "definitely absent" or "probably present." The hinges: (1) the bit count m and hash count k aren't guesses — they're determined by your item count n and target false-positive rate p; (2) you don't need k independent hashes — two are enough, via double hashing (Kirsch–Mitzenmacher); (3) there are no false negatives, and that's a guarantee, not a hope. First Rust entry since #272 dijkstra.

📦 GitHub: https://github.com/sen-ltd/bloom-filter-cli

What a Bloom filter is

It answers "is X in the set?" with exactly two possible replies:

"definitely absent" — always correct. There are never false negatives.
"probably present" — wrong some of the time (a false positive), at a rate you choose.

In return you get a tiny, fixed-size bit array, O(k) lookups, and no stored keys at all. That asymmetry — a confident no, a hedged yes — is the entire design. It's what you want when an occasional wrong "yes" is acceptable in exchange for a fraction of the memory: "have I seen this URL?", "is this in the spam set?", a cache admission filter.

Here's the CLI, real output:

$ bloom new --capacity 1000 --fp 0.01
created .bloom  capacity=1000  fp-target=0.01  m=9586 bits (2 KiB)  k=7

$ bloom add --from words.txt
added 18 new (18 seen)  total=18  m=9586 bits  k=7  fp≈0.000%

$ bloom check apple pineapple dragonfruit
apple        probably present
pineapple    probably present
dragonfruit  definitely absent

Hinge 1: sizing from a target false-positive rate

You don't pick m (bits) and k (hashes) by feel. Given item count n and target false-positive rate p, both fall out of the math:

m = ceil( -(n · ln p) / (ln 2)^2 )
k = round( (m / n) · ln 2 )

pub fn optimal_params(capacity: u64, fp: f64) -> (usize, u32) {
    let n = capacity.max(1) as f64;
    let ln2 = std::f64::consts::LN_2;
    let m = (-(n * fp.ln()) / (ln2 * ln2)).ceil();   // bits
    let k = ((m / n) * ln2).round();                 // hashes
    (m as usize, k as u32)
}

For n = 1000, p = 0.01 that's m = 9586 bits (~1.2 KB) and k = 7. Pin the exact numbers so a refactor can't silently drift the formula:

#[test]
fn optimal_params_match_formula() {
    let (m, k) = BloomFilter::optimal_params(1000, 0.01);
    assert_eq!(m, 9586); // ceil(-(1000·ln 0.01)/(ln 2)^2)
    assert_eq!(k, 7);    // round((m/n)·ln 2)
}

Intuitively, a tighter p needs more bits — also tested (smaller_fp_needs_more_bits).

Hinge 2: k hashes from two (Kirsch–Mitzenmacher)

Each item needs k bit positions, i.e. k independent hashes. Computing seven independent hashes per item would be wasteful — and isn't necessary. Kirsch & Mitzenmacher showed two base hashes suffice:

g_i(x) = h1(x) + i · h2(x)   (mod m),   i = 0 .. k-1

behaves, for filter purposes, like k independent hashes:

fn indices(&self, item: &str) -> Vec<usize> {
    let h1 = fnv1a_64(item.as_bytes());
    let h2 = djb2_64(item.as_bytes()) | 1; // force odd so it never collapses
    (0..self.k)
        .map(|i| (h1.wrapping_add((i as u64).wrapping_mul(h2)) % self.m as u64) as usize)
        .collect()
}

Two cheap hashes (FNV-1a and DJB2), k indices. h2 is forced odd so the step never degenerates to stamping the same bit over and over.

Hinge 3: no false negatives — guaranteed

Insertion only ever sets bits; it never clears them. So an inserted item's bits stay set and contains can't miss it. That's a property, not a hope, so it's a test:

#[test]
fn no_false_negatives() {
    let mut bf = BloomFilter::with_capacity(1000, 0.01);
    let words = ["apple", "banana", "δ-encoder", "🍎", ""];
    for w in &words { bf.add(w); }
    for w in &words { assert!(bf.contains(w)); } // always true
}

The false-positive rate, by contrast, is checked empirically: fill to design capacity, probe 20,000 absent keys, confirm the measured rate lands near the 1% target:

#[test]
fn measured_fp_rate_near_target() {
    let cap = 2000u64;
    let mut bf = BloomFilter::with_capacity(cap, 0.01);
    for i in 0..cap { bf.add(&format!("present-{}", i)); }
    let (mut fp, trials) = (0, 20_000);
    for i in 0..trials {
        if bf.contains(&format!("absent-query-{}", i)) { fp += 1; }
    }
    assert!(fp as f64 / trials as f64 < 0.03); // ~1%
}

The closed form is p ≈ (1 - e^(-k·n/m))^k; the info subcommand reports that estimate.

Counting distinct items honestly

The false-positive estimate depends on n — the number of distinct items inserted. Duplicate inserts would inflate it. So add returns whether the item was new (at least one bit was unset) and only then bumps n:

assert!(bf.add("x"));   // new
assert!(!bf.add("x"));  // duplicate → n unchanged

That's the added 1 new (2 seen) line: adding mango pineapple reports "1 new / 2 seen" because mango was already in words.txt.

Persistence

State is a hand-rolled compact binary blob — "BLM1" | m | k | n | bits — no serde:

pub fn serialize(&self) -> Vec<u8> {
    let mut out = Vec::with_capacity(24 + self.bits.len());
    out.extend_from_slice(b"BLM1");
    out.extend_from_slice(&(self.m as u64).to_le_bytes());
    out.extend_from_slice(&self.k.to_le_bytes());
    out.extend_from_slice(&self.n.to_le_bytes());
    out.extend_from_slice(&self.bits);
    out
}

deserialize validates the magic and bit-array length, rejecting corrupt input.

Architecture

src/bloom.rs — filter: sizing, double hashing, fp estimate, (de)serialize (12 tests)
src/main.rs  — clap CLI: new / add / check / info, file or stdin

A single clap dependency; bit ops, hashing and serialization are all hand-rolled.

Try it

cargo run -- new --capacity 1000 --fp 0.01
cargo run -- add --from examples/words.txt
cargo run -- check apple dragonfruit
cargo run -- info

Or Docker (static Alpine binary, non-root):

docker build -t bloom .
docker run --rm -v "$PWD":/data bloom add apple banana
docker run --rm -v "$PWD":/data bloom check apple

Takeaways

A Bloom filter says "definitely absent" with certainty, "probably present" with a hedge. No false negatives; tunable false positives.
(m, k) aren't guessed — they come from n and the target rate p.
You don't need k independent hashes — two suffice via h1 + i·h2 (keep h2 odd).
No false negatives is a guarantee; the false-positive rate is measured in a test.
Count distinct items for n and the fp estimate stays honest.
One dependency (clap); persistence is a hand-rolled binary format.

This is OSS portfolio entry #274 from SEN LLC. https://sen.ltd/portfolio/

Building a CSS Specificity Calculator — Counting (a,b,c) and the :is() / :where() Trap Most Implementations Fall Into

SEN LLC — Wed, 24 Jun 2026 23:14:51 +0000

A tool that computes the specificity of any CSS selector, breaks it down token by token, and tells you which of several selectors wins. Specificity is a (a, b, c) triple and looks like "just count IDs, classes, and elements." But the real hinge is how you treat :is() / :not() / :has() / :where() — count the :name itself and your winner prediction is simply wrong. Fully in-browser.

🌐 Demo: https://sen.ltd/portfolio/css-specificity-calculator/
📦 GitHub: https://github.com/sen-ltd/css-specificity-calculator

What specificity is

When two rules set the same property, specificity decides the winner first (source order only breaks a tie). It's a 3-tuple (a, b, c), compared left to right — a higher bucket beats any amount in a lower one.

bucket	counts	examples
a	ID selectors	`#header`
b	class, attribute, pseudo-class	`.btn` `[type=x]` `:hover`
c	type, pseudo-element	`div` `::before`

// compare two (a,b,c) tuples left-to-right → -1 / 0 / 1
export function compare(x, y) {
  for (let i = 0; i < 3; i++) {
    if (x[i] !== y[i]) return x[i] < y[i] ? -1 : 1;
  }
  return 0;
}

1,0,0 beats 0,99,99 — one ID outranks ninety-nine classes. There is no carry between buckets. Pin it with a test:

test("compare is lexicographic", () => {
  assert.equal(compare([0,1,0], [0,0,9]), 1); // one class > nine types
  assert.equal(compare([1,0,0], [0,9,9]), 1); // one id > everything below
});

The universal selector * and all combinators (> + ~ and descendant whitespace) contribute nothing.

The hinge: functional pseudo-classes

Here's the part most hand-rolled calculators get wrong. The weight of :is(), :not() and :has() is not the :name itself — it's the most specific selector inside the argument list. And :where() is always zero, with free arguments:

const MATCHES_ANY = new Set(["is", "not", "has"]); // weight = max of args
const ZERO_PSEUDO = new Set(["where"]);            // weight = 0, args free

function contribution(tok) {
  // ...
  if (tok.type === "pseudo-class") {
    const name = tok.name;
    if (ZERO_PSEUDO.has(name)) return { value: [0,0,0] };            // :where
    if (MATCHES_ANY.has(name)) return { value: maxOfList(tok.args) }; // :is/:not/:has
    return { value: [0,1,0] };                                       // :hover etc.
  }
}

maxOfList splits the argument's selector list and recursively computes the max:

function maxOfList(listStr) {
  let best = [0,0,0];
  for (const sel of splitList(listStr)) {
    const { value } = specificityOf(sel);  // recurse
    if (compare(value, best) > 0) best = value;
  }
  return best;
}

So:

:is(#a, p) → 1,0,0 (same as #a)
:where(#a, p) → 0,0,0 (the id becomes free)
a:is(.b) → 0,1,1 (same as a.b; the :is adds nothing of its own)

Tests nail every one, including nesting:

test(":is(#a, p) weighs like #a", () => assert.equal(spec(":is(#a, p)"), "1,0,0"));
test(":where(#a, .b, p) → (0,0,0)", () => assert.equal(spec(":where(#a, .b, p)"), "0,0,0"));
test("the :is() token itself adds nothing", () => {
  assert.equal(spec("a:is(.b)"), "0,1,1"); // not (0,2,1)
});
test("nested :is keeps taking the max", () => {
  assert.equal(spec(":is(:is(#deep), span)"), "1,0,0");
});

:where() exists precisely so library and reset styles can sit at specificity zero, trivially overridable by consumers. Miss this in your calculator and you overestimate how strong :where-wrapped rules are.

A small `:nth-child(... of S)` trap

:nth-child() is a pseudo-class, so normally it adds one b. But with the of S form it becomes one b plus the max specificity of S:

const NTH_OF = new Set(["nth-child", "nth-last-child"]);
// ...
if (NTH_OF.has(name) && /\bof\b/i.test(tok.args)) {
  const ofPart = tok.args.replace(/^[\s\S]*?\bof\b/i, ""); // text after "of"
  return { value: add([0,1,0], maxOfList(ofPart)) };
}

test("plain :nth-child is one pseudo-class", () => {
  assert.equal(spec("li:nth-child(2n+1)"), "0,1,1");
});
test("of S adds the selector's specificity", () => {
  assert.equal(spec(":nth-child(2 of .foo)"), "0,2,0"); // pseudo-class + .foo
});

The unglamorous part: commas and brackets

A selector list splits on commas — but not the commas inside :is(a, b), and not the comma inside [data-x="a,b,c"]. You have to split on top-level commas only:

export function splitList(selector) {
  const out = [];
  let depthParen = 0, depthBracket = 0, quote = null, start = 0;
  for (let i = 0; i < selector.length; i++) {
    const ch = selector[i];
    if (quote) { if (ch === quote && selector[i-1] !== "\\") quote = null; continue; }
    if (ch === '"' || ch === "'") quote = ch;
    else if (ch === "(") depthParen++;
    else if (ch === ")") depthParen--;
    else if (ch === "[") depthBracket++;
    else if (ch === "]") depthBracket--;
    else if (ch === "," && depthParen === 0 && depthBracket === 0) {
      out.push(selector.slice(start, i).trim());
      start = i + 1;
    }
  }
  const last = selector.slice(start).trim();
  if (last) out.push(last);
  return out.filter(Boolean);
}

test("commas inside :is() stay together", () => {
  assert.deepEqual(splitList(":is(a, b), c"), [":is(a, b)", "c"]);
});
test("commas inside [] do not split", () => {
  assert.equal(analyze('[data-x="a,b,c"]').length, 1);
});

The tokenizer uses the same idea: it scans [...] and (...) as a single balanced token, respecting quotes and nesting, so a nasty input like a[title="]"] (a close bracket inside the attribute value) doesn't break parsing.

Picking the winner

export function winnerIndex(results) {
  let best = 0, tie = false;
  for (let i = 1; i < results.length; i++) {
    const cmp = compare(results[i].value, results[best].value);
    if (cmp > 0) { best = i; tie = false; }
    else if (cmp === 0) tie = true;
  }
  return tie ? -1 : best; // -1 = tie, where CSS would fall back to source order
}

The demo highlights the winner in green and renders each selector as colored chips showing exactly which bucket each token added to.

Architecture

specificity.js — tokenizer, per-token weights, list splitting,
                 compare + winnerIndex (DOM-free, 42 tests)
app.js         — textarea → (a,b,c) chips + token breakdown, live

specificity.js is DOM-free, so all 42 tests run under node --test. Inline styles and !important live outside selector specificity (a separate layer that wins before the comparison even happens), so they're deliberately out of scope.

Try it

Demo: https://sen.ltd/portfolio/css-specificity-calculator/
GitHub: https://github.com/sen-ltd/css-specificity-calculator

Paste :is(#x) a and :where(#x) a on two lines and watch two visually identical selectors split into 1,0,1 and 0,0,1 — the clearest way to feel what :where() throws away.

Takeaways

Specificity is (a, b, c), compared left to right; a higher bucket wins outright (1,0,0 > 0,99,99).
* and combinators are zero.
The hinge: :is() / :not() / :has() weigh as the max of their arguments; :where() is always 0. The :name adds nothing itself.
:nth-child(... of S) is one pseudo-class plus the max of S.
Split on top-level commas only; scan [...] / (...) as balanced, quote-aware tokens.
Inline styles and !important are outside specificity, so they're out of scope.

This is OSS portfolio entry #273 from SEN LLC. https://sen.ltd/portfolio/

A Shortest-Path CLI in Rust — Making a Min-Heap from a Max-Heap, Path Reconstruction, and Rejecting Negative Weights

SEN LLC — Wed, 24 Jun 2026 02:07:24 +0000

A CLI that finds shortest paths in a weighted graph, in Rust, with Dijkstra's algorithm. Three implementation hinges: (1) Dijkstra needs a min-priority-queue to pull the closest unfinalized node, but Rust's BinaryHeap is a max-heap — so you reverse the Ord, (2) record predecessors to reconstruct the path, and (3) Dijkstra is wrong for negative weights, so reject them at parse time.

📦 GitHub: https://github.com/sen-ltd/dijkstra-cli

(It's a CLI — no live demo. Run with cargo run or Docker.)

Input format

Edge list, one per line: FROM TO WEIGHT. # comments and blanks ignored. --undirected mirrors every edge.

A B 7
A C 9
C F 2
F E 9

Hinge 1: a min-heap from a max-heap

Dijkstra repeatedly takes the node closest to the source — a min-priority-queue. But Rust's std::collections::BinaryHeap is a max-heap (largest on top).

The fix is to reverse the Ord of the State you push, so popping yields the minimum distance:

#[derive(Copy, Clone, Eq, PartialEq)]
struct State { dist: u64, idx: usize }

impl Ord for State {
    fn cmp(&self, other: &Self) -> Ordering {
        // reverse both keys: smallest dist pops first; on a tie, smaller idx
        other.dist.cmp(&self.dist).then_with(|| other.idx.cmp(&self.idx))
    }
}
impl PartialOrd for State {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> { Some(self.cmp(other)) }
}

other.dist.cmp(&self.dist) flips the comparison, using the max-heap as a min-heap — the canonical Rust idiom (the std-doc Dijkstra example does this too).

Reversing the secondary key (idx) too makes ties deterministic. Without it, equal-distance nodes pop in an arbitrary order and the reconstructed path wobbles between runs. Pinned by a test:

#[test]
fn deterministic_path_on_ties() {
    // A->B->D and A->C->D cost the same; predecessor is the smaller, B
    let sp = dijkstra(&g("A B 1\nA C 1\nB D 1\nC D 1\n"), "A");
    assert_eq!(sp.path_to("D").unwrap(), vec!["A", "B", "D"]);
}

I actually wrote this test first without reversing idx — it returned A->C->D and failed. Testing determinism caught the bug in my own Ord.

Hinge 2: discard stale heap entries

You want "found a shorter distance? update the queue," but BinaryHeap has no decrease-key. The fix: push duplicates and skip stale pops (lazy deletion):

while let Some(State { dist, idx }) = heap.pop() {
    if dist > best[idx] {
        continue; // a shorter distance was already finalized — stale entry
    }
    // ... relax neighbors ...
}

If dist > best[idx], a shorter path was found after this entry was pushed, so ignore it. Simpler than a hand-rolled indexed heap, and still O((V+E) log V).

#[test]
fn stale_heap_entries_ignored() {
    // direct B is 10 but via C it's 2
    let sp = dijkstra(&g("A B 10\nA C 1\nC B 1\n"), "A");
    assert_eq!(sp.dist["B"], 2);
    assert_eq!(sp.path_to("B").unwrap(), vec!["A", "C", "B"]);
}

Hinge 3: path reconstruction & negative weights

You want the path, not just the distance. Each relaxation records "who updated this node" in a prev map; path_to walks it back from the target and reverses.

And Dijkstra is incorrect for negative weights — the assumption that a finalized node can't later be improved breaks. Reject them at parse time:

if w < 0 {
    return Err(GraphError::NegativeWeight(line, w));
}

The error tells you to use Bellman-Ford instead of silently returning a wrong answer:

$ echo "A B -3" | dijkstra A
error: line 1: negative weight -3 — Dijkstra requires non-negative weights

CLI

match &cli.target {
    Some(target) => { /* print the single path */ }
    None => { /* table of shortest distances to all reachable nodes */ }
}

With a target, one path; without, all distances + paths. stdin supported.

$ dijkstra A E --file examples/graph.txt
A -> C -> F -> E  (distance 20)

A test pins the classic Wikipedia Dijkstra graph: A→E is A->C->F->E = 9+2+9 = 20.

Architecture

src/graph.rs — edge-list parse, Dijkstra (BinaryHeap), path reconstruction
src/main.rs  — clap CLI: single path or all-distances table, file/stdin

Single clap dependency; 10 inline tests in graph.rs. Docker: rust:1.85-alpine → alpine, non-root. House style (committed Cargo.lock, opt-level="z" + LTO).

Run it

cargo test
cargo run -- A E --file examples/graph.txt
docker build -t dijkstra . && docker run --rm -i dijkstra A E < examples/graph.txt

GitHub: https://github.com/sen-ltd/dijkstra-cli

Takeaways

Rust's BinaryHeap is a max-heap; reverse State's Ord to use it as the min-heap Dijkstra needs.
Reverse the secondary key too for deterministic ties — stable path reconstruction (a test caught this).
Skip stale entries on pop instead of decrease-key (lazy deletion); still O((V+E) log V).
Reconstruct the path from a prev predecessor map.
Reject negative weights — Dijkstra's invariant breaks, so error instead of returning garbage.

This is OSS portfolio #272 from SEN LLC (Tokyo). https://sen.ltd/portfolio/

Building a WCAG Contrast Checker — Relative Luminance, sRGB Gamma, and the Step Most Implementations Skip

SEN LLC — Mon, 22 Jun 2026 22:54:17 +0000

A tool that computes the WCAG contrast ratio between a text color and a background and reports AA / AAA pass-fail. It looks like "the ratio of brightnesses," but contrast is computed from relative luminance — not raw RGB, not a channel average — and getting relative luminance right requires undoing the sRGB gamma curve on each channel. Skip that step and your checker reports the wrong ratio for mid-grays. The hinges are that formula and the fact that the pass threshold differs by text size. Fully in-browser.

🌐 Demo: https://sen.ltd/portfolio/color-contrast-checker/
📦 GitHub: https://github.com/sen-ltd/color-contrast-checker

Why a plain RGB ratio is wrong

"White (255) over gray (128) is 255/128 ≈ 2" — wrong, for two reasons:

Displays apply an sRGB gamma. Pixel value 128 is not 50% physical brightness — it's about 21%. You must undo the gamma to get perceived brightness.
The eye's sensitivity differs per channel — most sensitive to green, least to blue. So it's a weighted sum, not a plain average.

WCAG defines this precisely as relative luminance.

The hinge: computing relative luminance

Four steps:

// 1 + 2. normalize to 0..1 and undo the sRGB gamma (linearize)
export function linearizeChannel(c255) {
  const c = c255 / 255;
  return c <= 0.03928 ? c / 12.92 : Math.pow((c + 0.055) / 1.055, 2.4);
}

// 3. relative luminance — green has the largest weight (eye most sensitive to green)
export function relativeLuminance({ r, g, b }) {
  return 0.2126 * linearizeChannel(r)
       + 0.7152 * linearizeChannel(g)
       + 0.0722 * linearizeChannel(b);
}

// 4. contrast ratio
export function contrastRatio(c1, c2) {
  const l1 = relativeLuminance(c1), l2 = relativeLuminance(c2);
  return (Math.max(l1, l2) + 0.05) / (Math.min(l1, l2) + 0.05);
}

Point by point:

The linearization branch c <= 0.03928 ? c/12.92 : ((c+0.055)/1.055)^2.4 is the inverse sRGB transfer function — linear in the dark region, a power curve above it. Skip undoing this curve and mid-gray luminance comes out badly off.

The weights 0.2126 / 0.7152 / 0.0722 encode the human luminosity function — green dominates:

test("green is brightest channel", () => {
  const g = relativeLuminance({ r: 0, g: 255, b: 0 }); // ≈ 0.7152
  const r = relativeLuminance({ r: 255, g: 0, b: 0 }); // ≈ 0.2126
  const b = relativeLuminance({ r: 0, g: 0, b: 255 }); // ≈ 0.0722
  assert.ok(g > r && r > b);
});

The +0.05 models ambient screen flare. It's what makes pure black (L=0) over pure white (L=1) come out to exactly (1+0.05)/(0+0.05) = 21 — the origin of the 21:1 cap:

test("black on white = 21", () => {
  approx(contrastRatio({r:0,g:0,b:0}, {r:255,g:255,b:255}), 21, 1e-2);
});

The difference shows up in mid-grays

The gap between a "good enough" implementation and a correct one is widest at mid-gray. #777777 on white:

correct: 4.48:1 → just below the normal-text AA threshold (4.5)
without linearization: the ratio drifts and may falsely pass AA

#777 on white being a "just fails AA" gray is a well-known case, so it's a test:

test("known pair: #777 on white ≈ 4.48", () => {
  approx(contrastRatio(parseColor("#777"), parseColor("#fff")), 4.48, 0.05);
});

A 0.02 difference decides AA pass/fail, which is exactly why accuracy matters.

Thresholds depend on text size

WCAG has more than one line:

context	AA	AAA
normal text	4.5	7
large text (≥18pt, or ≥14pt bold)	3	4.5
UI components / graphics	3	—

export function wcagLevels(ratio) {
  return {
    normalAA: ratio >= 4.5, normalAAA: ratio >= 7,
    largeAA: ratio >= 3,    largeAAA: ratio >= 4.5,
    uiAA: ratio >= 3,
  };
}

test("4.5 is the normal-AA / large-AAA boundary", () => {
  const l = wcagLevels(4.5);
  assert.ok(l.normalAA && l.largeAAA && !l.normalAAA);
});

The same 4.5 is the boundary for both normal-AA and large-AAA. The demo shows all five verdicts as pass/fail badges.

Color parsing

Accepts #rgb, #rrggbb, and rgb(r,g,b):

export function parseColor(input) {
  let s = input.trim().toLowerCase();
  const m = /^rgba?\(\s*(\d+)\s*,\s*(\d+)\s*,\s*(\d+)/.exec(s);
  if (m) { /* rgb() form */ }
  if (s.startsWith("#")) s = s.slice(1);
  if (/^[0-9a-f]{3}$/.test(s)) { /* expand #rgb → #rrggbb */ }
  if (/^[0-9a-f]{6}$/.test(s)) { /* #rrggbb */ }
  return null; // invalid
}

#f80 → {r:255, g:136, b:0} shorthand expansion included; invalid colors return null for a UI error.

Architecture

contrast.js — parse, sRGB linearization, luminance, ratio, WCAG levels (DOM-free, 32 tests)
app.js      — live preview + pass/fail table

contrast.js is DOM-free, so all 32 tests run in Node. The UI syncs the native color picker with the text input and reflects fg/bg into a live preview.

Try it

Demo: https://sen.ltd/portfolio/color-contrast-checker/
GitHub: https://github.com/sen-ltd/color-contrast-checker

Set #777 text on white: 4.48, "fails normal AA but passes for large text." Darken it gradually to find the moment it crosses 4.5 and you'll build intuition for accessible palettes.

Takeaways

Contrast is computed from relative luminance, not raw RGB or channel averages.
Relative luminance requires undoing the sRGB gamma (linearization) — skip it and mid-grays misjudge.
Weights are 0.2126 / 0.7152 / 0.0722 (green dominant), encoding human sensitivity.
The +0.05 flare term models ambient light and caps the ratio at 21:1.
Thresholds vary by text size (normal AA 4.5 / large AA 3); the same 4.5 bounds normal-AA and large-AAA.
#777 on white = 4.48 — the classic "just fails AA" gray. Test it to protect accuracy.

This is OSS portfolio #271 from SEN LLC (Tokyo). https://sen.ltd/portfolio/

Implementing Huffman Coding in Go — Merging the Two Rarest Nodes Builds the Optimal Prefix-Free Code

SEN LLC — Sun, 21 Jun 2026 23:03:00 +0000

A CLI that compresses text with Huffman coding and reports the ratio, in Go. The essence of Huffman coding: give frequent symbols short bit strings, rare ones long ones, and make the code prefix-free — no code is a prefix of another — so a concatenated bit stream decodes unambiguously with no separators. The hinge: a greedy construction that just merges the two lowest-frequency nodes repeatedly produces the optimal code tree — and pinning that with property tests.

📦 GitHub: https://github.com/sen-ltd/huffman-cli

(It's a CLI — no live demo. Run with go run or Docker.)

What "prefix-free" buys you

Fixed-width codes (8-bit ASCII) decode without separators. Go variable-length and "where does one symbol end?" becomes the problem: with a=0, b=01, the stream 001 is ambiguous.

Prefix-free removes the ambiguity. Since no code is a prefix of another, you read the bit stream left to right, walk the code tree, and the moment you hit a leaf you've finished exactly one symbol. Unique decoding, zero separators.

The hinge: merge the two rarest nodes

The tree construction is a surprisingly simple greedy algorithm:

Make each symbol a leaf weighted by its frequency.
Put them all in a min-heap.
Pop the two lowest-frequency nodes, merge them under a parent (frequency = sum), push it back.
Repeat until one node remains.

for q.Len() > 1 {
    a := heap.Pop(q).(*node)   // lowest
    b := heap.Pop(q).(*node)   // next lowest
    heap.Push(q, &node{freq: a.freq + b.freq, left: a, right: b})
}

Left edge adds 0, right adds 1; each leaf's root-to-leaf path is its code:

var walk func(n *node, prefix string)
walk = func(n *node, prefix string) {
    if n.leaf { codes[n.sym] = prefix; return }
    walk(n.left, prefix+"0")
    walk(n.right, prefix+"1")
}

Why it's optimal: merging the two rarest nodes first pushes them to the deepest positions (longest codes), while frequent symbols, merged late, stay shallow (short codes). "Rarer ⇒ deeper" is achieved greedily, minimizing average code length (approaching the Shannon entropy).

Pin the properties with tests

Huffman correctness is best guarded by properties, not specific output values.

1. Prefix-free

For every pair, neither is a prefix of the other:

func TestPrefixFree(t *testing.T) {
    codes := BuildCodes(Frequencies("abracadabra"))
    for i := range list {
        for j := range list {
            if i != j && hasPrefix(list[i], list[j]) {
                t.Errorf("%q is a prefix of %q — not prefix-free", list[j], list[i])
            }
        }
    }
}

2. Frequent ⇒ shorter

A higher-frequency symbol never gets a longer code than a rarer one:

freq := map[rune]int{'a': 5, 'b': 2, 'c': 1}
codes := BuildCodes(freq)
if len(codes['a']) > len(codes['b']) { t.Error(...) }  // 'a' must be shortest

3. Round-trip

decode(encode(text)) == text for ASCII, Unicode, and single-symbol input:

for _, text := range []string{"abracadabra", "mississippi", "日本語のテキストも符号化できる"} {
    codes := BuildCodes(Frequencies(text))
    bits, _ := Encode(text, codes)
    got, _ := Decode(bits, codes)
    if got != text { t.Errorf("round trip failed: %q -> %q", text, got) }
}

Frequencies are counted per rune, so Unicode works.

4. Deterministic

Identical input always yields an identical table. Ties (equal frequency) break on a stable insertion order:

func (p pq) Less(i, j int) bool {
    if p[i].freq != p[j].freq { return p[i].freq < p[j].freq }
    return p[i].order < p[j].order  // equal freq → deterministic by insertion
}

Without this, the merge order of equal-frequency symbols would depend on Go's map iteration order and wobble run to run.

Edge case: a single distinct symbol

"aaaa" has no branching tree — the one leaf is the root. Naively its code is the empty string, so encoding produces zero bits and can't be decoded. The fix: assign code "0" when there's only one symbol.

if root.leaf {
    codes[root.sym] = "0"  // single symbol → 1-bit code
    return codes
}

func TestSingleSymbol(t *testing.T) {
    codes := BuildCodes(Frequencies("aaaa"))
    if codes['a'] != "0" { t.Error(...) }   // and "aaaa" -> "0000" -> "aaaa"
}

Reporting the ratio

Analyze compares "original bytes × 8" to the Huffman bit count:

$ huff --table "mississippi"
symbols:       4
original:      88 bits (11 bytes x 8)
huffman:       21 bits
ratio:         0.239
space saved:   76.1%

mississippi is skewed (i and s appear 4× each), so it compresses 76%. The more skewed the distribution (lower entropy), the better Huffman does.

Architecture

huffman/huffman.go — tree build (heap), code assignment, encode/decode, stats
main.go            — CLI: stats, --table, --bits, stdin

Zero external dependencies. Built with golang:1.23-alpine → alpine runtime, non-root. Passes go test -race.

Run it

go test ./... -race
go run . --table "mississippi"
docker build -t huff . && docker run --rm huff --table "abracadabra"

GitHub: https://github.com/sen-ltd/huffman-cli

Takeaways

Huffman codes are prefix-free, so the bit stream decodes uniquely with no separators.
Construction is a greedy "merge the two rarest nodes" loop — that's what minimizes average code length.
Guard correctness with properties: prefix-free, frequent ⇒ shorter, round-trip, determinism.
Break heap ties on insertion order for a deterministic table.
A single symbol needs a "0" special case — an empty code can't be decoded.
Count frequencies per rune and Unicode just works.

This is OSS portfolio #270 from SEN LLC (Tokyo). https://sen.ltd/portfolio/

Building a Base Converter — BigInt for Unlimited Digits, and Detecting Repeating Fractions

SEN LLC — Sat, 20 Jun 2026 23:44:14 +0000

A converter between any radix from 2 to 36. "Isn't that just parseInt(s, 16)?" — done properly, there are two traps: (1) Number loses precision past 2^53, so large values need BigInt, and (2) a fraction that terminates in one base often repeats in another (decimal 0.1 is 0.0(0011) repeating in binary). How you detect and display that repetition is the real story. Fully in-browser, vanilla JS.

🌐 Demo: https://sen.ltd/portfolio/base-converter/
📦 GitHub: https://github.com/sen-ltd/base-converter

Hinge 1: BigInt integer part, no precision ceiling

parseInt("ff", 16) does return 255. But large values break:

Number.parseInt("ffffffffffffffff", 16)  // 18446744073709552000 (wrong!)
// correct: 18446744073709551615

Number is float64 — past 2^53 it can't represent integers exactly, which is fatal for a base converter. Use BigInt:

const DIGITS = "0123456789abcdefghijklmnopqrstuvwxyz";

export function parseIntPart(intStr, base) {     // string → BigInt
  const b = BigInt(base);
  let acc = 0n;
  for (const ch of intStr) acc = acc * b + BigInt(digitValue(ch));
  return acc;
}

export function renderIntPart(value, base) {     // BigInt → string
  if (value === 0n) return "0";
  const b = BigInt(base);
  let out = "", v = value;
  while (v > 0n) { out = DIGITS[Number(v % b)] + out; v = v / b; }
  return out;
}

The digit ceiling disappears:

test("200-bit number converts exactly", () => {
  const bin = "1" + "0".repeat(200);  // 2^200
  assert.equal(renderIntPart(parseIntPart(bin, 2), 10),
    "1606938044258990275541962092341162602522202993782792835301376");
});

v % b is Number()-cast for indexing, which is safe because b ≤ 36 so the remainder is always 0–35.

Hinge 2: detecting repeating fractions

The interesting part. A fraction that "terminates" in one base "repeats" in another.

decimal 0.1 = binary 0.0001100110011... (0011 repeats forever)
decimal 0.5 = binary 0.1 (terminates)

Why? 0.1 = 1/10. The denominator 10 = 2×5 has a factor of 5, but binary only terminates when the denominator is a power of 2. The leftover 5 makes it repeat.

Detection: remember the remainders

Fractional conversion is "multiply by the target base, take the integer part, repeat." When a remainder recurs, the digits since then repeat — the same trick as long division:

export function convertFraction(fracStr, fromBase, toBase, maxDigits = 64) {
  // hold the fraction exactly as num/den (BigInt)
  const fb = BigInt(fromBase);
  let num = 0n, den = 1n;
  for (const ch of fracStr) {
    num = num * fb + BigInt(digitValue(ch));
    den = den * fb;
  }
  const g = gcd(num, den);            // reduce → canonical remainders
  if (g > 0n) { num /= g; den /= g; }

  const tb = BigInt(toBase);
  const digits = [];
  const seen = new Map();             // remainder → digit index
  let rem = num, repeatStart = -1;

  while (rem !== 0n && digits.length < maxDigits) {
    if (seen.has(rem)) {              // seen before = cycle starts
      repeatStart = seen.get(rem);
      break;
    }
    seen.set(rem, digits.length);
    rem *= tb;
    digits.push(DIGITS[Number(rem / den)]);  // next digit
    rem %= den;
  }
  return { digits: digits.join(""), repeatStart };
}

The key is holding the fraction as an exact num/den over BigInt. Float arithmetic would introduce drift and break the cycle detection; exact BigInt remainders match precisely, so the repetend is found reliably.

test("0.1 dec → repeating binary, wrapped in parens", () => {
  assert.deepEqual(convert("0.1", 10, 2), { value: "0.0(0011)", repeating: true });
});

In the demo, decimal 0.1 shows as binary 0.0(0011), octal 0.0(6314), hex 0.1(9) — each base repeats differently, visible at a glance.

Why reduce the fraction first

The gcd reduction at the top canonicalizes the remainders. Without it, the same value can appear as 2/20 and 1/10, and remainder-based cycle detection can misfire. Reduce to lowest terms first and each remainder is unique to its value.

Input validation

In base N the valid digits are 0 through the (N-1)th character. A 2 in a binary number is invalid:

export function isValidForBase(str, base) {
  const body = str.startsWith("-") ? str.slice(1) : str;
  if (body === "" || body === ".") return false;
  let seenDot = false;
  for (const ch of body) {
    if (ch === ".") { if (seenDot) return false; seenDot = true; continue; }
    const v = digitValue(ch);
    if (v < 0 || v >= base) return false;
  }
  return true;
}

The UI reports the exact allowed digits on error.

Architecture

convert.js — parse/render (BigInt), fraction conversion + cycle detection (DOM-free, 38 tests)
app.js     — UI glue, common-base comparison table

Bases 2–36 (0-9a-z), negatives, fractions. convert.js is DOM-free, so all 38 tests run in Node.

Try it

Demo: https://sen.ltd/portfolio/base-converter/
GitHub: https://github.com/sen-ltd/base-converter

Enter 0.1 and switch the output base between 2 / 8 / 16 — every base repeats, with a different repetend. Enter a 2^100-scale integer and watch the precision hold.

Takeaways

Do the integer part in BigInt — Number corrupts past 2^53. Only the v % base index is safe to Number() (base ≤ 36).
A fraction that terminates in one base can repeat in another — when the denominator keeps a prime factor the target base lacks.
Detect repetition via recurring remainders in a Map — the long-division trick.
Hold the fraction as an exact num/den BigInt so there's no float drift in cycle detection.
gcd-reduce first to canonicalize remainders and keep detection stable.

This is OSS portfolio #269 from SEN LLC (Tokyo). https://sen.ltd/portfolio/

A Topological-Sort CLI in Python — Kahn's Algorithm and a DFS That Names the Cycle

SEN LLC — Sat, 20 Jun 2026 01:18:29 +0000

make targets, npm dependencies, task ordering — "do B and C before A" is a dependency graph, and putting it in a valid order is topological sorting. I built a CLI for it. Two implementation hinges: (1) Kahn's algorithm (in-degrees + a queue) with stable, lexicographic output, and (2) when there's a cycle, don't just say "cycle detected" — use DFS to name exactly which nodes form it, as auth -> cache -> db -> auth. The last two entries were Rust and Go, so this one's a Python CLI.

📦 GitHub: https://github.com/sen-ltd/topo-sort-cli

(It's a CLI — no live demo. Run with python3 main.py or Docker.)

Input format

One declaration per line. A: B C means A depends on B and C (B and C come first). # comments and blanks are ignored:

deploy: build test
build: compile
test: compile
compile:

Internally each dependency is stored as a "prerequisite → dependent" edge (A: B → edge B -> A), so a prerequisites-first topological sort is directly a build order.

Hinge 1: Kahn's algorithm with stable output

Topological sort comes in a DFS flavor and a Kahn flavor. Kahn's is intuitive: repeatedly take nodes whose in-degree (number of prerequisites) is zero:

Count every node's in-degree.
Queue the zero-in-degree nodes (no prerequisites → can go first).
Pop one, emit it, decrement its dependents' in-degrees.
Newly-zero nodes join the queue. Repeat.

A naive queue pops in arbitrary order, so the output wobbles run to run. A min-heap of ready nodes always takes the lexicographically smallest, making output deterministic:

import heapq

def topo_sort(g):
    indeg = g.indegrees()
    ready = [n for n, d in indeg.items() if d == 0]
    heapq.heapify(ready)                       # ready set as a min-heap

    order = []
    while ready:
        n = heapq.heappop(ready)               # smallest ready node → stable
        order.append(n)
        for v in sorted(g.adj[n]):
            indeg[v] -= 1
            if indeg[v] == 0:
                heapq.heappush(ready, v)

    if len(order) == len(g.nodes):
        return SortResult(order=order, cycle=None)
    return SortResult(order=None, cycle=_find_cycle(g))  # leftovers = cycle

That final len(order) != len(g.nodes) is the cycle test: if some node's in-degree never hits zero, it's in a cycle. Determinism is pinned by a test:

def test_deterministic_tiebreak():
    # three independent nodes → lexicographic order
    assert order_of("b:\na:\nc:\n") == ["a", "b", "c"]

Hinge 2: name the cycle

Kahn's tells you a cycle exists, not where. Lots of tools stop at error: cycle detected, leaving you to stare at the graph. A second pass — DFS with white/gray/black coloring — extracts one concrete cycle:

white = unvisited, gray = on the current recursion stack, black = finished
reaching a gray node during DFS = a back-edge = a cycle
the recursion stack from that node onward is the cycle

def _find_cycle(g):
    WHITE, GRAY, BLACK = 0, 1, 2
    color = {n: WHITE for n in g.nodes}
    stack = []

    def dfs(u):
        color[u] = GRAY
        stack.append(u)
        for v in sorted(g.adj[u]):
            if color[v] == GRAY:               # back-edge → cycle
                idx = stack.index(v)
                return stack[idx:] + [v]       # stack slice + return node
            if color[v] == WHITE:
                found = dfs(v)
                if found is not None:
                    return found
        stack.pop()
        color[u] = BLACK
        return None

    for n in sorted(g.nodes):
        if color[n] == WHITE:
            found = dfs(n)
            if found is not None:
                return found
    return []

So instead of "there is a cycle" you get:

error: graph has a cycle:
  auth -> cache -> db -> auth

— the actual path, plus exit code 1 so shell scripts can detect it. The user fixes those three edges and moves on.

Cycles hidden behind innocent branches still get found

DFS starts from every node, so a cycle survives even when an unrelated acyclic subgraph is present:

def test_cycle_with_innocent_tail():
    # x -> y is fine; a <-> b is the cycle. Must still be detected.
    res = topo_sort(parse_graph("x: y\ny:\na: b\nb: a\n"))
    assert res.order is None
    assert set(res.cycle) <= {"a", "b"}
    assert res.cycle[0] == res.cycle[-1]   # path returns to its start

Self-loops (a: a), 2-node and 3-node cycles each get their own test too.

CLI

text = open(args.file).read() if args.file else sys.stdin.read()
graph = parse_graph(text)
result = topo_sort(graph)
if result.cycle is not None:
    print("error: graph has a cycle:", file=sys.stderr)
    print("  " + " -> ".join(result.cycle), file=sys.stderr)
    return 1
for node in (reversed(result.order) if args.reverse else result.order):
    print(node)
return 0

--reverse for dependents-first, --numbered for positions, and stdin support so cat deps.txt | toposort works.

Architecture

src/graph.py — parse + Kahn's sort + DFS cycle extraction (stdlib only)
src/cli.py   — argparse, file/stdin, exit codes
main.py      — entry point

Zero dependencies. 21 pytest tests: parsing, ordering validity, deterministic tie-breaking, self-loops, 2- and 3-node cycles, and cycles hidden behind acyclic tails. Docker: python:3.12-alpine build → alpine runtime, non-root.

Run it

python3 main.py examples/build.deps
python3 -m pytest          # 21 tests
docker build -t toposort . && docker run --rm -i toposort < examples/build.deps

GitHub: https://github.com/sen-ltd/topo-sort-cli

Takeaways

Kahn's algorithm: emit zero-in-degree nodes; a min-heap makes the output stable.
len(order) != node_count is the cycle test — no separate check needed.
Don't stop at "cycle detected" — DFS gray-node revisit extracts the actual path (auth -> cache -> db -> auth).
DFS from every node finds cycles hidden behind unrelated branches.
Split exit codes (0 ok / 1 cycle) so the tool composes in shell.

This is OSS portfolio #268 from SEN LLC (Tokyo). https://sen.ltd/portfolio/

A Fuzzy-Finder CLI in Go — Two-Row Edit Distance, Unicode Correctness, and Mutex-Free Concurrency by Index

SEN LLC — Fri, 19 Jun 2026 00:55:54 +0000

lev kitten sitting mitten prints each candidate's Levenshtein edit distance and similarity, ranked — a tiny fuzzy finder, written in Go. Three implementation hinges: (1) fold the DP table to two rows for O(min(m,n)) memory, (2) operate on runes, not bytes, so "café"↔"cafe" is 1 and CJK/emoji are counted correctly, and (3) make the goroutine fan-out race-free without a mutex by partitioning the result slice by index. This is SEN's first Go entry (the previous one was Rust — two non-JS in a row).

📦 GitHub: https://github.com/sen-ltd/levenshtein-cli

(It's a CLI — no live demo. Run with go run or Docker.)

Edit distance

Levenshtein distance is "the minimum number of single-character insertions, deletions, or substitutions to turn one string into the other." kitten → sitting is 3 (substitute k→s, e→i, append g). It's the basis of spell correction and fuzzy search.

Hinge 1: two-row DP → O(min(m,n)) memory

Textbook Levenshtein fills an (m+1)×(n+1) matrix. But each cell depends only on the one above, the one to the left, and the diagonal — so you keep two rows and roll them. Make the inner row the shorter string and memory is O(min(m,n)), not O(m·n):

func Distance(a, b string) int {
    ra, rb := []rune(a), []rune(b)
    if len(ra) < len(rb) { ra, rb = rb, ra } // shorter string drives row width
    if len(rb) == 0 { return len(ra) }

    prev := make([]int, len(rb)+1)
    curr := make([]int, len(rb)+1)
    for j := range prev { prev[j] = j }

    for i := 1; i <= len(ra); i++ {
        curr[0] = i
        for j := 1; j <= len(rb); j++ {
            cost := 1
            if ra[i-1] == rb[j-1] { cost = 0 }
            curr[j] = min3(
                prev[j]+1,      // deletion
                curr[j-1]+1,    // insertion
                prev[j-1]+cost, // substitution / match
            )
        }
        prev, curr = curr, prev // O(1) swap, buffer reused
    }
    return prev[len(rb)]
}

The prev, curr = curr, prev swap reuses the allocated buffers as it advances. Even for long strings, memory scales only with the shorter one.

Hinge 2: runes, not bytes

This one quietly matters. é is two bytes in UTF-8. A byte-based distance says café → cafe is 2 (counting the two bytes of é separately); the correct answer is 1. Converting to []rune fixes it and makes CJK and emoji work:

ra, rb := []rune(a), []rune(b) // Unicode code points, not bytes

func TestUnicodeAware(t *testing.T) {
    if d := Distance("café", "cafe"); d != 1 { ... }        // 1, not 2
    if d := Distance("こんにちは", "こんばんは"); d != 2 { ... }  // 2 substitutions
    if d := Distance("a🎉b", "ab"); d != 1 { ... }           // emoji = 1 rune
}

Range a Go string as []byte and you see UTF-8 bytes; convert to []rune and you see characters. Edit distance is about character operations a human sees, so runes are correct.

Hinge 3: mutex-free concurrency by index partitioning

With many candidates, fan the distance computations out across goroutines — the idiomatic Go bit. Multiple goroutines writing one slice sounds like a data race, but if each worker writes only to results[i] for the index it pulled off the channel, no mutex is needed: distinct indices are distinct memory.

func Rank(target string, candidates []string, workers int) []Scored {
    results := make([]Scored, len(candidates))
    jobs := make(chan int)
    var wg sync.WaitGroup
    for w := 0; w < workers; w++ {
        wg.Add(1)
        go func() {
            defer wg.Done()
            for i := range jobs {
                results[i] = Scored{                 // writes only results[i]
                    Candidate:  candidates[i],
                    Distance:   Distance(target, candidates[i]),
                    Similarity: Similarity(target, candidates[i]),
                }
            }
        }()
    }
    for i := range candidates { jobs <- i }
    close(jobs)
    wg.Wait()
    sort.SliceStable(results, func(i, j int) bool { /* distance asc, ties A-Z */ })
    return results
}

Pin correctness with "worker-count invariant" + `-race`

The most effective test for concurrent code asserts the result is identical for any worker count:

func TestRankIsWorkerCountInvariant(t *testing.T) {
    base := Rank("apple", cands, 1)
    for _, w := range []int{2, 3, 8, 100, runtime.NumCPU()} {
        got := Rank("apple", cands, w)
        for i := range base {
            if got[i] != base[i] { t.Errorf("workers=%d differs at %d", w, i) }
        }
    }
}

One worker vs. a hundred — if a single field differs, it fails. Run it under go test -race and the race detector catches memory-level races on top of logical mismatches. Both green means the concurrency is correct.

Note: -race requires cgo, so when building with the Alpine golang image, apk add build-base for gcc and set CGO_ENABLED=1.

CLI: args or stdin

target := args[0]
candidates := args[1:]
if len(candidates) == 0 {
    sc := bufio.NewScanner(os.Stdin) // no inline candidates → read stdin
    for sc.Scan() { /* append non-empty lines */ }
}
ranked := levenshtein.Rank(target, candidates, *workers)

Two usage modes:

lev kitten sitting mitten        # candidates as args
cat words.txt | lev --top 5 needle   # rank every line, best 5

--top N caps results, --json for machine output, --workers N for parallelism.

Architecture

levenshtein/levenshtein.go  — Distance / Similarity / Rank (stdlib only)
main.go                     — CLI (args or stdin), table / JSON output

Zero external dependencies. Built with golang:1.23-alpine, runs on alpine, non-root.

Run it

go test ./... -race
go run . kitten sitting       # 1
docker build -t lev . && docker run --rm lev kitten sitting mitten

GitHub: https://github.com/sen-ltd/levenshtein-cli

Takeaways

Levenshtein DP folds to two rows. Make the inner row the shorter string for O(min(m,n)) memory; prev, curr = curr, prev reuses buffers.
Compute distance over runes, not bytes, or café↔cafe is 2. CJK and emoji need runes too.
Goroutine fan-out is race-free without a mutex if you partition the output slice by index — distinct index, distinct memory.
Guard concurrent code with a worker-count-invariant test and go test -race.
-race needs cgo — apk add build-base on Alpine.

This is OSS portfolio #267 from SEN LLC (Tokyo) — and our first Go entry. https://sen.ltd/portfolio/

DEV Community: SEN LLC

Building a Cuckoo Filter CLI in Rust — the Deletion a Bloom Filter Can't Do, Partial-Key Cuckoo Hashing, and a High Load Factor via Relocation

What a Cuckoo filter is

Hinge 1: partial-key cuckoo hashing

Hinge 2: relocation buys a high load factor

The signature property: delete

Persistence

Takeaway

Building a t-digest CLI in Go — Stream p50/p99/p99.9 in a Few KB, a Scale Function That Keeps Tails Sharp, Exact min/max, and Mergeable Digests

What a t-digest is

Hinge 1: a scale function that keeps the tails sharp

Hinge 2: exact min/max, interpolated middle

The signature property: merge

Persistence

Takeaway

Building a Count-Min Sketch CLI in Rust — Sizing from a Target Error, d Counters from Two Hashes, No Underestimates, and Mergeable Sketches

What a Count-Min sketch is

Hinge 1: sizing from a target error and confidence

Hinge 2: d counters from two hashes (Kirsch–Mitzenmacher)

274's Bloom filter.

Hinge 3: take the minimum — and why it can't underestimate

The signature property: merge

Persistence

Takeaway

Building a HyperLogLog CLI in Go — One Billion Distinct in 16 KB, a Harmonic Mean, a Hash Finalizer, and Mergeable Sketches

What HyperLogLog is

The idea: rare hash patterns leak scale

Hinge 1: a harmonic mean over m buckets

Hinge 2: why the hash needs a finalizer

The signature property: merge

Persistence

Takeaway

Building a Bloom Filter CLI in Rust — Sizing from a Target FP Rate, k Hashes from Two, and Guaranteed No False Negatives

What a Bloom filter is

Hinge 1: sizing from a target false-positive rate

Hinge 2: k hashes from two (Kirsch–Mitzenmacher)

Hinge 3: no false negatives — guaranteed

Counting distinct items honestly

Persistence

Architecture

Try it

Takeaways

Building a CSS Specificity Calculator — Counting (a,b,c) and the :is() / :where() Trap Most Implementations Fall Into

What specificity is

The hinge: functional pseudo-classes

A small :nth-child(... of S) trap

The unglamorous part: commas and brackets

Picking the winner

Architecture

Try it

Takeaways

A Shortest-Path CLI in Rust — Making a Min-Heap from a Max-Heap, Path Reconstruction, and Rejecting Negative Weights

Input format

Hinge 1: a min-heap from a max-heap

Hinge 2: discard stale heap entries

Hinge 3: path reconstruction & negative weights

CLI

Architecture

Run it

Takeaways

Building a WCAG Contrast Checker — Relative Luminance, sRGB Gamma, and the Step Most Implementations Skip

Why a plain RGB ratio is wrong

The hinge: computing relative luminance

The difference shows up in mid-grays

Thresholds depend on text size

Color parsing

Architecture

Try it

Takeaways

Implementing Huffman Coding in Go — Merging the Two Rarest Nodes Builds the Optimal Prefix-Free Code

What "prefix-free" buys you

The hinge: merge the two rarest nodes

Pin the properties with tests

1. Prefix-free

2. Frequent ⇒ shorter

3. Round-trip

4. Deterministic

Edge case: a single distinct symbol

Reporting the ratio

Architecture

A small `:nth-child(... of S)` trap

Pin correctness with "worker-count invariant" + `-race`