mixle.enumeration.best_first module

Best-first / A*-style search over sorted enumeration streams.

The k-best engines used by the combinator distributions: ProductEnumerator (best-first over a Cartesian product of child streams), LengthFrontierMerge / frontier_merge (length-indexed frontier merge), and the best_first_union family (union of overlapping-support streams, re-scored exactly and emitted in provably correct descending-probability order). See mixle.stats.compute.pdist.DistributionEnumerator for the enumeration contract.

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]]

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

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]]

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 exact probability mass, and keep the best start+k by probability. Since every unpulled item’s probability is at most the remaining mass total_mass - accumulated, once remaining drops below the (start+k)-th best probability the heap is exactly the true top start+k; return sorted_desc[start:start+k]. If the in-budget stream is exhausted first, the budget is doubled (up to max_budget_bits). total_mass (default 1.0) may be a known upper bound for sub-normalized models.

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:

list[tuple[Any, float]]