mixle.enumeration.algorithms module

Back-compat facade for the smart-enumeration machinery.

The implementation was split by concern (it had grown into one ~1100-line module mixing three distinct things):

  • generic stream primitives -> mixle.enumeration.streams

  • best-first / product search -> mixle.enumeration.best_first

  • the quantized seek / unrank index -> mixle.enumeration.quantization.seek

This module re-exports them so from mixle.enumeration.algorithms import X keeps working unchanged. New code can import from the modules above directly. See mixle.stats.compute.pdist.DistributionEnumerator for the enumeration contract.

class BufferedStream(it)[source]

Bases: object

Random access by rank into a lazy stream of (value, log_prob) pairs.

get(i) extends an internal buffer as needed and returns the i-th item, or None if the stream has fewer than i+1 items. The underlying stream is consumed at most once regardless of how many consumers share this object.

Parameters:

it (Iterator[tuple[Any, float]])

get(i)[source]

Return buffered item i, pulling from the stream if needed.

i is an absolute, 0-based rank – not a Python sequence index – so it must be an exact, non-negative integer. This is checked before the buffer is touched at all, regardless of how much has been buffered so far: without this check, get(-1) would return the last currently buffered item via ordinary Python negative indexing once anything has been pulled, but raise an incidental IndexError from indexing an empty list otherwise – making a negative rank’s observable behavior depend on prior access history instead of always meaning “invalid.” bool is rejected too despite being an int subclass, and a whole-valued float such as 2.0 is rejected as well: a rank is always exactly integral, never merely numerically equal to one.

Parameters:

i (int)

Return type:

tuple[Any, float] | None

freeze(x)[source]

Return a canonical hashable key for x, for de-duplicating support values.

Lists/tuples freeze element-wise to tuples, dicts to frozensets of (key, value) pairs, sets to frozensets, numpy arrays to (shape, dtype string, bytes), numpy scalars to their python equivalents, and NaN to a shared sentinel (so nan == nan for dedup purposes). Raises TypeError for values that cannot be canonicalized.

Cross-type equality policy (deliberate, not incidental): type is part of a value’s identity for dedup purposes, so this never falls back to Python’s native cross-type equality/hashing.

  • ndarrays are keyed by (shape, dtype.str, bytes). Bytes alone are ambiguous – e.g. an int8 array holding -56 and a uint8 array holding 200 have identical tobytes() output but represent different numbers – so omitting dtype would silently merge genuinely distinct support values.

  • Every other value is keyed by (type(x), x) rather than bare x, after numpy scalars are unwrapped to their python equivalent via .item(). Plain x would let Python’s own cross-type equality collide unrelated values that happen to compare equal – True == 1, False == 0, 1 == 1.0 – even though a typed distribution’s support can legitimately contain both a bool and an int (or an int and a float) as distinct outcomes. Note .item() collapses numpy integer width (int8/uint8/int64 all become python int), which is safe because .item() – unlike an array’s raw .tobytes() – already applies each dtype’s own signed/unsigned interpretation, so equal post-.item() values really are the same number.

  • The one exception: every NaN float collapses to a single shared sentinel regardless of which NaN produced it, since IEEE 754 nan != nan would otherwise make each NaN a unique, never-deduplicated key.

Parameters:

x (Any)

Return type:

Hashable

merge_enumerators(streams, offsets)[source]

Lazy k-way merge of sorted (value, log_prob) streams with per-stream offsets.

Stream k’s log probs are shifted by offsets[k]. Correct only when the streams have pairwise disjoint supports (no de-duplication or re-scoring is performed).

Validated eagerly at call time, before any stream is touched: offsets must have exactly one entry per stream, and every offset must be finite or exactly -inf – the sentinel for “this stream contributes nothing” (e.g. a zero-weight mixture component), which excludes that stream entirely without ever opening its iterator. NaN and +inf offsets are rejected outright, since neither has a sensible reading as a log-probability shift. This function is a thin eager-validation wrapper; the actual merge runs in the generator it returns, so a malformed call raises immediately instead of on first iteration.

Each stream’s own items are validated lazily – one pull at a time, as they are actually consumed, so this is safe for infinite streams and never reads ahead: a non-finite log_prob (including -inf – a properly-formed descending stream should already exclude impossible/zero-probability items, matching the convention used elsewhere in this package, e.g. best_first.py’s if lp > -np.inf guards) raises immediately, and so does a log_prob that exceeds the previous log_prob pulled from that SAME stream – i.e. the stream failing the k-way merge’s fundamental precondition of actually being sorted descending.

Parameters:
Return type:

Iterator[tuple[Any, float]]

supports_enumeration(dist)[source]

Return True if dist.enumerator() can be constructed.

Return type:

bool

class ProductEnumerator(streams, combine=tuple, offset=0.0)[source]

Bases: object

Best-first enumeration of the Cartesian product of sorted child streams.

Yields (combine(values), log_prob) with log_prob = offset + sum of child log probs, in non-increasing order. Standard k-best lattice search: a max-heap over index tuples, with successors advancing one coordinate; correctness follows from each child stream being sorted (coordinate-wise monotonicity).

Duplicate-free successor rule: each heap entry carries the lowest coordinate it is allowed to advance, and a node only spawns successors for coordinates at or above that index. Every tuple is then reached by exactly one path – the one that increments coordinates in non-decreasing index order – so no visited set (and no O(n) per-successor tuple hashing) is needed. Best-first order is preserved because each successor’s score is <= its generating node’s (a sorted coordinate only decreases when advanced), so canonical edges are score-monotone.

Parameters:
class LengthFrontierMerge(len_stream, make_stream)[source]

Bases: object

Merge per-length sorted streams, instantiating lengths lazily from a sorted length stream.

len_stream yields (length, log_prob_of_length) in descending order. make_stream(length, lp_len) returns a sorted iterator of (value, log_prob) whose log probs already include lp_len and never exceed it (true whenever per-element contributions are log probs <= 0). The next un-instantiated length’s lp_len is then a valid upper bound on anything its stream could produce, so lengths are instantiated only when they can beat the best instantiated head. Supports of distinct lengths must be disjoint (no de-duplication).

Parameters:
frontier_merge(outer_stream, make_stream)[source]

Merge per-outer-key inner streams, instantiating outer keys lazily from a sorted outer stream.

The general form of LengthFrontierMerge for arbitrary (not necessarily integer) outer keys: outer_stream yields (key, lp_key) in descending lp_key order, and make_stream(key, lp_key) returns a sorted (value, log_prob) iterator whose log-probs are <= lp_key (true whenever the inner contribution is <= 0 and lp_key is folded in as an offset). The next un-instantiated key’s lp_key is then an upper bound on anything its stream could produce, so keys are instantiated only when they can beat the best instantiated head. Supports of distinct keys must be disjoint (no de-duplication). Used for conditional products where the inner distribution depends on the outer value (e.g. hidden-association S2 given S1).

Parameters:
Return type:

Iterator[tuple[Any, float]]

best_first_union(streams, log_offsets, exact_log_density, tol=1.0e-10)[source]

Enumerate the union of sorted streams with overlapping supports.

Candidate values are pulled from the streams (stream k shifted by log_offsets[k]), de-duplicated via freeze, re-scored exactly with exact_log_density, and buffered until their exact score is at least the upper bound on any not-yet-seen value: logsumexp_k(log_offsets[k] + head_lp_k). This is the mixture algorithm: any unseen x satisfies p_k(x) <= head_k for every k, hence sum_k w_k p_k(x) <= exp(bound).

Parameters:
Return type:

Iterator[tuple[Any, float]]

best_first_union_max(streams, log_offsets, exact_log_density, tol=1.0e-10)[source]

Like best_first_union, but for a max-scored union (bound = max over heads).

Used to enumerate a deduped symbol pool ordered by max-over-states emission probability for markov/HMM enumerators.

Parameters:
Return type:

Iterator[tuple[Any, float]]

bounded_best_first_union_index(streams, log_offsets, exact_log_density, max_bits, bin_width_bits=1.0, tol=1.0e-10, component_log_density=None)[source]

Build a quantized index from a globally bounded best-first union.

This is the index-building counterpart of best_first_union. It is useful for mixtures: if each stream head bounds one component contribution, then the log-sum of live heads bounds every unseen value. Once that global frontier is below the requested probability threshold, all remaining qualifying values must already be in the exact-score buffer, so the index can stop without enumerating a looser per-component candidate prefix.

Parameters:
Return type:

QuantizedEnumerationIndex

sound_top_k(dist, k, start=0, budget_bits=40.0, oversample=8, bin_width_bits=1.0, max_budget_bits=512.0, total_mass=1.0, tol=1.0e-12)[source]

Exact true-descending observations ranked [start, start+k) for ANY normalized model.

Mass-threshold certificate, correct regardless of the seek stream’s ordering (so it holds for deep/nested mixtures and HMMs where the tropical order is badly displaced): pull distinct (value, log_prob) from the count-budget index, accumulate probability mass with a provable (never-overstated) lower bound, and keep the best start+k by probability. Since every unpulled item’s probability is at most the remaining mass total_mass - accumulated, once a sound upper bound on remaining drops below the (start+k)-th best probability the heap is exactly the true top start+k; return sorted_desc[start:start+k].

Running out of the in-budget stream is NOT by itself proof the support is exhausted: only a non-truncated index has genuinely covered the entire support, so seeing fewer than start + k distinct values THERE means that many is honestly all there is. A TRUNCATED index only proves “nothing more is visible to this bounded build” – running out of one deepens the budget (doubling up to max_budget_bits) instead of returning the partial prefix as the answer. If even max_budget_bits cannot certify or exhaust, the call fails closed: the returned status is "incomplete" and marked as such rather than silently shaped like a proof (see SoundTopKResult – this is why the return type is a structured result, not a plain list).

total_mass (default 1.0) may be a known upper bound for sub-normalized models; it is trusted as a valid bound on the model’s TRUE total probability mass (this function cannot re-derive a model’s own normalization) but is validated for basic sanity – finite and positive – before use, so a NaN/inf/non-positive caller bug cannot silently corrupt the certificate.

Cost is O(number pulled) – small for peaked distributions, large for flat ones, so for top-k from rank 0 dist.enumerator() is usually leaner; this adds the soundness certificate and the arbitrary start offset the sequential enumerator lacks.

Parameters:
Return type:

SoundTopKResult

class SoundTopKResult(items, status, budget_bits, remaining_mass_bound)[source]

Bases: object

Outcome of sound_top_k(): the found items plus an explicit soundness certificate.

sound_top_k is named and documented as SOUND, so callers must be able to tell a mathematically-certified top-k apart from a best-effort guess it gave up on – unlike a plain list, this always carries the status that earned items.

Parameters:
items

the (value, log_prob) pairs ranked [start, start+k), in descending log_prob order. Fewer than k items only when status == "exhausted" and the distribution’s true support genuinely has fewer than start + k distinct values.

Type:

list[tuple[Any, float]]

status

how items was established.

  • "certified" – the mass certificate proved no unseen value can outrank the worst kept item: the accumulated seen mass leaves less than the worst kept item’s own probability unaccounted for. Sound regardless of the count-budget index’s internal seek order (deep/nested mixtures and HMMs included).

  • "exhausted" – the count-budget index was NOT truncated, i.e. it covers the distribution’s entire true support, so items is exact by construction: nothing was left unseen for the certificate to reason about.

  • "incomplete" – max_budget_bits was reached before either certificate above could be established. items is a best-effort prefix of whatever the search had found – NOT proven to be the true top-k. Callers that require soundness must treat this as a failure (retry with a larger max_budget_bits, or fall back to exact enumeration) rather than silently trusting items.

Type:

Literal[‘certified’, ‘exhausted’, ‘incomplete’]

budget_bits

the final (possibly doubled) count-budget-index budget used to produce items.

Type:

float

remaining_mass_bound

a conservative upper bound on the probability mass of every value not in items – never smaller than the truth, even accounting for floating-point rounding (see _fold_mass_lower_bound()). Certifies "certified" results (strictly less than the worst kept item’s probability); left at total_mass (a trivial but valid bound) when the heap never reached start + k items.

Type:

float

property sound: bool

True when items is a proven-correct top-k (status is not "incomplete").

class QuantizedEnumerationIndex(bins, bin_width_bits, max_bits, truncated)[source]

Bases: object

Bounded, indexable view of an exact probability-ordered enumeration.

Items are grouped into log-probability bins measured in bits:

bits(x) = -log2(p(x)) bin(x) = floor(bits(x) / bin_width_bits)

Only items whose bit cost is at most max_bits are indexed. The returned (value, log_prob) pairs always carry the original exact log probability; the quantized bins are used only for counting and rank lookup.

The generic implementation can build from an exact enumerator stream, so it works for every currently enumerable discrete stats model. Simple distributions may also build directly from scored support items, and distribution-specific dynamic programs can produce the same bin layout without relying on an exact global stream.

Parameters:
static bin_for_log_prob(log_prob, bin_width_bits=1.0)[source]

Return the quantized bit bin for a log probability.

Parameters:
Return type:

int

classmethod from_enumerator(enum, max_bits, bin_width_bits=1.0)[source]

Build an index from an exact non-increasing-probability enumerator.

Parameters:

  • enum (Iterator[tuple[Any, float]]) – Iterator yielding (value, log_prob) pairs in exact descending order.

  • max_bits (float) – Include only values with -log2(p) <= max_bits.

  • bin_width_bits (float) – Width of each quantized probability bin in bits.

Returns:

QuantizedEnumerationIndex over the bounded prefix/domain slice.

Return type:

QuantizedEnumerationIndex

classmethod from_items(items, max_bits, bin_width_bits=1.0, sorted_items=False, truncated=None)[source]

Build an index from known support items and exact log probabilities.

Parameters:

  • items (Sequence[tuple[Any, float]]) – Finite collection of (value, log_prob) pairs. Zero-probability items with log_prob == -inf are ignored.

  • max_bits (float) – Include only values with -log2(p) <= max_bits.

  • bin_width_bits (float) – Width of each quantized probability bin in bits.

  • sorted_items (bool) – If True, preserve the input order. Otherwise, stable-sort included items by descending log probability.

  • truncated (bool | None) – Optional explicit truncation flag. If omitted, it is True when any finite-probability item was outside the bit bound.

Returns:

QuantizedEnumerationIndex over the bounded finite item set.

Return type:

QuantizedEnumerationIndex

bin_for_index(index)[source]

Return (bin_id, offset_within_bin) for a bounded quantized rank.

Parameters:

index (int)

Return type:

tuple[int, int]

get(index)[source]

Return the indexed (value, exact_log_prob) pair.

Parameters:

index (int)

Return type:

tuple[Any, float]

slice(start, k)[source]

Return up to k indexed pairs starting at start.

Parameters:
Return type:

list[tuple[Any, float]]

iter_from(start=0)[source]

Iterate indexed pairs from start to the end of the bounded index.

Parameters:

start (int)

Return type:

Iterator[tuple[Any, float]]

bin_items(bin_id)[source]

Return all indexed items in a quantized probability bin.

Parameters:

bin_id (int)

Return type:

list[tuple[Any, float]]

summary()[source]

Return a compact description of the bounded index.

Return type:

dict[str, Any]

class LazyQuantizedEnumerationIndex(counts, bin_width_bits, max_bits, truncated, getter)[source]

Bases: QuantizedEnumerationIndex

Quantized index whose bin counts are precomputed but items are unranked lazily.

This supports compositional distributions where a dynamic program can count how many values fall in each quantized log-density bin without materializing every Cartesian-product value. The getter receives a bin id and offset within that bin and returns the exact (value, log_prob) pair for that quantized rank.

Parameters:
bin_for_index(index)[source]

Return (bin_id, offset_within_bin) for a bounded quantized rank.

Parameters:

index (int)

Return type:

tuple[int, int]

get(index)[source]

Return the indexed (value, exact_log_prob) pair.

Parameters:

index (int)

Return type:

tuple[Any, float]

iter_from(start=0)[source]

Iterate indexed pairs from start to the end of the bounded index.

Parameters:

start (int)

Return type:

Iterator[tuple[Any, float]]

bin_items(bin_id)[source]

Return all indexed items in a quantized probability bin.

Parameters:

bin_id (int)

Return type:

list[tuple[Any, float]]

class QuantizedCrossIndex(items, max_bits, bin_width_bits, truncated=False)[source]

Bases: object

Aligned support rows for multiple distributions under quantized bit bounds.

Each row is (value, log_probs), where log_probs[j] is the exact log-density of value under component j, or -inf when that component assigns zero mass. Rows are included when any component’s bit cost is within its requested bound. The joint bin counts expose the cross-bin alignment that mixtures need and marginal bin counts cannot provide.

Parameters:
static bits_for_log_prob(log_prob)[source]

Return -log2(p), using inf for zero probability.

Parameters:

log_prob (float)

Return type:

float

classmethod from_items(items, max_bits, bin_width_bits=1.0, truncated=False)[source]

Build a cross index from exact aligned support rows.

Parameters:
Return type:

QuantizedCrossIndex

iter_items()[source]

Iterate aligned support rows.

Return type:

Iterator[tuple[Any, tuple[float, …]]]

summary()[source]

Return a compact description of the cross index.

Return type:

dict[str, Any]

quantized_index(enum, max_bits, bin_width_bits=1.0)[source]

Convenience wrapper for QuantizedEnumerationIndex.from_enumerator.

Parameters:
Return type:

QuantizedEnumerationIndex