fuzzy_search.analysis package

Submodules

fuzzy_search.analysis.freq module

Token ngram frequency counting and probability estimation, plus log-likelihood-ratio keyword/word comparison statistics.

This module provides NgramFreq for counting word ngrams across a collection of documents and computing (optionally smoothed) ngram probabilities and conditional probabilities, along with functions for computing the log-likelihood ratio (LLR) and percentage-difference statistics that compare a word’s frequency between a target and reference corpus.

class fuzzy_search.analysis.freq.Ngram(tokens: List[str])[source]

Bases: object

Represents a word ngram, exposing both the full ngram and its head/tail parts.

tokens

The ngram’s token strings.

Type:: List[str]

size

The number of tokens in the ngram.

Type:: int

n

Alias of size.

Type:: int

string

The ngram tokens joined with spaces.

Type:: str

head_string

All tokens except the last, joined with spaces (the “history” used for conditional probability estimation).

Type:: str

tail_string

The last token in the ngram.

Type:: str

__init__(tokens: List[str])[source]

Initializes an Ngram from a list of token strings.

Parameters:: tokens (List[str]) – The tokens making up the ngram.

class fuzzy_search.analysis.freq.NgramFreq(max_ngram_size: int = 3)[source]

Bases: object

Counts word ngram frequencies (up to a maximum order) across a collection of documents and provides (smoothed) probability and conditional probability estimation.

ngram_freq

Maps ngram order -> Counter of ngram string -> frequency.

Type:: Dict[int, Counter]

max_ngram_size

The highest ngram order that is counted.

Type:: int

total_ngram_tokens

Maps ngram order -> total ngram token count.

Type:: Counter

total_ngram_types

Maps ngram order -> number of distinct ngram types.

Type:: Counter

num_docs

The number of documents counted so far.

Type:: int

start_tokens

The padded <s> boundary ngram strings, for each order.

Type:: Set[str]

end_tokens

The padded </s> boundary ngram strings, for each order.

Type:: Set[str]

__init__(max_ngram_size: int = 3)[source]

Initializes the NgramFreq counter.

Parameters:: max_ngram_size (int, optional) – The highest ngram order to count, e.g. 3 for unigrams, bigrams and trigrams. Defaults to 3.

count_ngrams(docs: List[Doc])[source]

Counts ngrams (of all orders up to max_ngram_size) across a list of documents, updating the running totals.

Parameters:: docs (List[Doc]) – The documents to count ngrams in.

has_conditional_prob(ngram_string: str, smoothing: str = None, lambdas: List[float] = None, k: float = 1.0)[source]

Computes the conditional probability of an ngram’s last token given its preceding tokens.

Parameters:

ngram_string (str) – The (space-joined) ngram string.
smoothing (str, optional) – One of None (unsmoothed), 'laplace' (add-k smoothing), or 'interpolation' (linear interpolation across orders).
lambdas (List[float], optional) – Interpolation weights, required when smoothing == 'interpolation'.
k (float, optional) – The add-k smoothing constant, used when smoothing == 'laplace'. Defaults to 1.0.

Returns:

The estimated conditional probability.

Return type:

float

Raises:

ValueError – If smoothing is not one of the supported values.

has_freq(term: str)[source]

Returns the frequency of an ngram string (without special-casing boundary tokens).

Parameters:: term (str) – The (space-joined) ngram string to look up.
Returns:: The ngram’s frequency, or 0 if unseen.
Return type:: int

has_prob(term: str, smoothing: str = None)[source]

Computes the (optionally Laplace-smoothed) probability of an ngram string.

Parameters:

term (str) – The (space-joined) ngram string.
smoothing (str, optional) – If 'laplace', apply add-one smoothing over the vocabulary; otherwise compute the unsmoothed maximum-likelihood probability.

Returns:

The estimated probability of the ngram.

Return type:

float

total_tokens(ngram_size: int = 1)[source]: Returns the total count of ngram tokens of a given order seen so far.

total_types(ngram_size: int = 1)[source]: Returns the number of distinct ngram types of a given order seen so far.

property vocab_size

The number of distinct unigram types (the vocabulary size).

Type:: int

fuzzy_search.analysis.freq.check_lambdas(lambdas: List[float], ngram_size: int)[source]

Validates interpolation lambda weights for ngram smoothing.

Parameters:

lambdas (List[float]) – The interpolation weights, one per ngram order from 1 up to ngram_size.
ngram_size (int) – The ngram order being smoothed.

Raises:

ValueError – If lambdas is missing, has the wrong length, or its values don’t sum to 1.0.
TypeError – If any value in lambdas is not a float.

fuzzy_search.analysis.freq.compute_expected(observed: array) → array[source]: Computes the contingency table of the expected values given a contingency table of the observed values.

fuzzy_search.analysis.freq.compute_llr(token: str, target_counter: Counter, target_total: int, reference_counter: Counter, reference_total: int, include_direction: bool = False) → Tuple[float, str][source]: Computes the log likelihood ratio for given a target token, and target and reference analysers and counters.

fuzzy_search.analysis.freq.compute_llr_from_observed(observed: array, include_direction: bool = False) → float | Tuple[float, str][source]

Computes the log-likelihood ratio (G2 statistic) from an observed 2x2 contingency table.

Parameters:

observed (np.array) – A 2x2 contingency table, as produced by get_observed_from_counter().
include_direction (bool, optional) – If True, also return whether the target count is higher (‘more’) or lower (‘less’) than expected under independence.

Returns:

The log-likelihood ratio, optionally paired with the direction string.

Return type:

Union[float, Tuple[float, str]]

fuzzy_search.analysis.freq.compute_percentage_diff(token, target_counter, target_total, reference_counter, reference_total)[source]

Computes the relative percentage difference in a token’s frequency fraction between a target and a reference corpus.

Parameters:

token – The token to compare.
target_counter (Counter) – Token frequencies in the target corpus.
target_total (int) – Total token count in the target corpus.
reference_counter (Counter) – Token frequencies in the reference corpus.
reference_total (int) – Total token count in the reference corpus.

Returns:

The percentage difference of the target fraction relative to the reference fraction, or float('inf') if the token does not occur in the reference corpus.

Return type:

float

fuzzy_search.analysis.freq.doc_to_string_tokens(doc: Doc | List[Token] | List[str])[source]

Normalizes a document representation into a plain list of normalised token strings.

Parameters:: doc (Union[Doc, List[Token], List[str]]) – A Doc, a list of Token objects, or a list of strings.
Returns:: The normalised token strings of the document.
Return type:: List[str]

fuzzy_search.analysis.freq.get_observed_from_counter(token: str, target_counter: Counter, target_total: int, reference_counter: Counter, reference_total: int)[source]: Computes the contingency table of the observed values given a target token, and target and reference analysers and counters.

fuzzy_search.analysis.freq.make_token_ngrams(doc: Doc | List[Token] | List[str], ngram_size: int)[source]

Generates word ngrams of a given size from a document, padded with start/end symbols.

The document’s tokens are padded with ngram_size - 1 <s> start symbols and </s> end symbols so that ngrams overlapping the document boundaries are also produced (e.g. for a trigram model, this yields ngrams like ['<s>', '<s>', tok1]).

Parameters:

doc (Union[Doc, List[Token], List[str]]) – The document to extract ngrams from.
ngram_size (int) – The number of tokens per ngram.

Yields:

List[str] – Each successive ngram (as a list of token strings) in the document.

fuzzy_search.analysis.similarity module

Term similarity utilities: Levenshtein-based begin/end similarity, term skip-cooccurrence counting, and an efficient skipgram-based cosine-similarity index for finding terms similar to a query term.

The centerpiece is SkipgramSimilarity, which indexes a vocabulary of terms by their character skipgram frequency vectors, bucketed by term length, and uses sparse matrix-vector products to retrieve the most similar indexed terms to a query term.

class fuzzy_search.analysis.similarity.KeywordList(keywords: List[str], max_length_diff: int)[source]

Bases: object

Indexes a list of keywords by length, to efficiently enumerate candidate pairs of keywords whose lengths are close enough to plausibly be near-duplicates.

len_keys

Maps keyword length to the keywords of that length.

Type:: Dict[int, List[str]]

max_length_diff

The default maximum length difference used when generating candidate pairs.

Type:: int

len_order

The distinct keyword lengths, sorted ascending.

Type:: List[int]

__init__(keywords: List[str], max_length_diff: int)[source]

Initializes the KeywordList by indexing keywords by their length.

Parameters:

keywords (List[str]) – The keywords to index.
max_length_diff (int) – The default maximum length difference allowed when comparing keyword pairs.

Raises:

ValueError – If any keyword is not a string.

find_close_distance_keywords(max_distance_ratio: float = 0.3, max_length_diff: int = 3, max_distance: int = 10, ignorecase: bool = False) → Dict[str, List[str]][source]: TODO: should we make the arguments into a config?

find_closer_terms(candidate: str, keyword: str, close_terms: List[str])[source]

Finds which of a keyword’s known close terms are even closer to a candidate string than the keyword itself.

Parameters:

candidate (str) – The string to compare distances against.
keyword (str) – The reference keyword.
close_terms (List[str]) – Terms previously identified as close to keyword.

Returns:

Maps each close term that is nearer to candidate than keyword is, to its Levenshtein distance from candidate.

Return type:

Dict[str, int]

iterate_candidate_pairs()[source]

Yields all candidate keyword pairs whose lengths differ by at most max_length_diff, without yielding the same unordered pair twice.

Yields:: Tuple[str, str] – Each candidate (kw1, kw2) pair.

class fuzzy_search.analysis.similarity.SkipCooccurrence(vocabulary: Vocabulary, skip_size: int = 1, sentences: Iterable[List[str]] = None)[source]

Bases: object

Counts the co-occurrence frequency of word skipgrams within sentences.

cooc_freq

Maps (term_id, term_id) co-occurrence pairs to their observed frequency.

Type:: Dict[Tuple[int, int], int]

vocabulary

Maps terms to identifiers used in cooc_freq.

Type:: Vocabulary

skip_size

The default maximum number of skips allowed between co-occurring terms.

Type:: int

__init__(vocabulary: Vocabulary, skip_size: int = 1, sentences: Iterable[List[str]] = None)[source]

Initializes the SkipCooccurrence counter.

Parameters:

vocabulary (Vocabulary) – The vocabulary used to map terms to identifiers.
skip_size (int, optional) – The maximum number of skips allowed between co-occurring terms. Defaults to 1.
sentences (Iterable[List[str]], optional) – If given, immediately count co-occurrences for these sentences.

calculate_skip_cooccurrences(sentences: Iterable[List[str]], skip_size: int = 0)[source]

Count the frequency of term (skip) co-occurrences for a given list of sentences.

Parameters:

sentences (Iterable[List[str]) – a list of sentences, where each sentence is itself a list of term tokens
skip_size (int) – the maximum number of skips to allow between co-occurring terms

get_term_coocs(term: str) → None | Generator[Tuple[str, str], None, None][source]

Yields all co-occurring term pairs and their frequency for a given term.

Parameters:: term (str) – The term to look up co-occurrences for.
Yields:: Tuple[Tuple[str, str], int] – Each (term pair, frequency) where term is one of the two terms in the pair.
Returns:: If term is not in the vocabulary.
Return type:: None

class fuzzy_search.analysis.similarity.SkipgramSimilarity(ngram_length: int = 3, skip_length: int = 0, terms: List[str] = None, max_length_diff: int = 2)[source]

Bases: object

Indexes terms by their character skipgram frequency vectors and finds similar indexed terms for a query term via cosine similarity.

Terms are bucketed by length (see max_length_diff) and, within each length bucket, represented as columns of a sparse skipgram-by-term matrix. This lets a query be compared against only the terms within the relevant length range using a handful of sparse matrix-vector products, rather than scanning the whole vocabulary.

ngram_length

The number of characters per skipgram.

Type:: int

skip_length

The maximum number of skipped characters per skipgram.

Type:: int

vocabulary

Maps indexed terms to term ids.

Type:: Vocabulary

skipgram_vocabulary

Maps observed skipgram strings to skipgram ids.

Type:: Vocabulary

max_length_diff

The maximum term-length difference considered when searching for similar terms.

Type:: int

__init__(ngram_length: int = 3, skip_length: int = 0, terms: List[str] = None, max_length_diff: int = 2)[source]

A class to index terms by their character skipgrams and to find similar terms for a given input term based on the cosine similarity of their skipgram overlap.

Parameters:

ngram_length (int) – the number of characters per ngram
skip_length (int) – the maximum number of characters to skip
terms (List[str]) – a list of terms
max_length_diff (int) – the maximum difference in length between a search term and a term in the index to be considered a match. This is an efficiency parameter to reduce the number of candidate similar terms to ones that are roughly similar in length to the search term.

index_terms(terms: List[str], reset_index: bool = True)[source]

Make a frequency index of the skip grams for a given list of terms. By default, indexing is cumulative, that is, everytime you call index_terms with a list of terms, they are added to the index. Use ‘reset_index=True’ to reset the index before indexing the given terms.

Parameters:

terms (List[str]) – a list of term to index
reset_index (bool) – whether to reset the index before indexing or to keep the existing index

rank_similar(term: str, top_n: int = 10, score_cutoff: float = 0.5)[source]

Return a ranked list of similar terms from the index for a given input term, based on their character skipgram cosine similarity.

Parameters:

term (str) – a term (any string) to match against the indexed terms
top_n (int (default 10)) – the number of highest ranked terms to return
score_cutoff (float) – the minimum similarity score after which to cutoff the ranking

Returns:

a ranked list of terms and their similarity scores

Return type:

List[Tuple[str, float]]

fuzzy_search.analysis.similarity.get_begin_sim(phrase1: str, phrase2: str, begin_length: int) → float[source]

Computes the Levenshtein-based similarity of the first begin_length characters of two phrases.

Parameters:

phrase1 (str) – The first phrase.
phrase2 (str) – The second phrase.
begin_length (int) – The number of leading characters to compare (clamped to the shorter phrase’s length).

Returns:

1 minus the normalised Levenshtein distance between the two prefixes.

Return type:

float

fuzzy_search.analysis.similarity.get_end_sim(phrase1: str, phrase2: str, end_length: int) → float[source]

Computes the Levenshtein-based similarity of the last end_length characters of two phrases.

Parameters:

phrase1 (str) – The first phrase.
phrase2 (str) – The second phrase.
end_length (int) – The number of trailing characters to compare (clamped to the shorter phrase’s length).

Returns:

1 minus the normalised Levenshtein distance between the two suffixes.

Return type:

float

fuzzy_search.analysis.similarity.get_min_length(phrase1: str, phrase2: str, begin_length: int) → int[source]: Returns the smallest of the two phrase lengths and a requested length.

fuzzy_search.analysis.similarity.get_skip_coocs(seq_ids: List[str], skip_size: int = 0) → Generator[Tuple[int, int], None, None][source]

Generates all (current, following) id pairs within a skip window of a sequence.

Parameters:

seq_ids (List[str]) – A sequence of (term) identifiers.
skip_size (int, optional) – The number of extra positions beyond the immediate neighbour to pair with each element. Defaults to 0 (only adjacent pairs).

Yields:

Tuple[int, int] – Each (current_id, following_id) co-occurrence pair.

fuzzy_search.analysis.similarity.is_close_distance_keyword_pair(keyword1: str, keyword2: str, max_distance_ratio: float, max_length_difference: int, max_distance: int) → bool[source]

Checks whether two keywords are close enough to be considered near-duplicates.

Two keywords are considered close if their length difference is within max_length_difference and their Levenshtein distance is both below max_distance and below max_distance_ratio relative to either keyword’s length.

Parameters:

keyword1 (str) – The first keyword.
keyword2 (str) – The second keyword.
max_distance_ratio (float) – The maximum allowed distance-to-length ratio.
max_length_difference (int) – The maximum allowed difference in keyword lengths.
max_distance (int) – The maximum allowed absolute Levenshtein distance.

Returns:

True if the keywords are considered a close-distance pair.

Return type:

bool

fuzzy_search.analysis.similarity.vector_length(skipgram_freq)[source]

Computes the Euclidean length of a skipgram frequency vector.

Parameters:: skipgram_freq – A mapping (e.g. dict or Counter) of skipgram -> frequency.
Returns:: The square root of the sum of squared frequencies.
Return type:: float

fuzzy_search.analysis.spelling_compare module

Compares word frequencies between two corpora to detect words that increase, decrease, emerge, disappear, or get replaced/shifted to a semantically similar word (via embeddings).

SpellingCompare computes, for each high-frequency word, how its relative frequency changed between two corpora, and uses an embedding model’s similarity to link a word that dropped in frequency in one corpus to a similar word that jumped in frequency in the other (e.g. detecting spelling variant shifts).

class fuzzy_search.analysis.spelling_compare.Change(decrease_word: str = None, decrease_type: str = None, increase_word: str = None, increase_type: str = None, sim_score: float = None)[source]

Bases: object

Represents a detected change between two corpora linking a decreasing word to an increasing word.

decrease_word

The word that decreased/disappeared.

Type:: str, optional

decrease_type

The type of decrease (‘decrease’ or ‘disappear’).

Type:: str, optional

increase_word

The word that increased/emerged.

Type:: str, optional

increase_type

The type of increase (‘increase’ or ‘emerge’).

Type:: str, optional

sim_score

The embedding similarity score between the two words.

Type:: float, optional

__init__(decrease_word: str = None, decrease_type: str = None, increase_word: str = None, increase_type: str = None, sim_score: float = None)[source]

Initializes a Change record.

Parameters:

decrease_word (str, optional) – The word that decreased/disappeared.
decrease_type (str, optional) – The type of decrease (‘decrease’ or ‘disappear’).
increase_word (str, optional) – The word that increased/emerged.
increase_type (str, optional) – The type of increase (‘increase’ or ‘emerge’).
sim_score (float, optional) – The embedding similarity score between the two words.

class fuzzy_search.analysis.spelling_compare.Diff(word, freq1, frac1, perc_diff1, freq2, frac2, perc_diff2, llr, direction)

Bases: tuple

direction: Alias for field number 8

frac1: Alias for field number 2

frac2: Alias for field number 5

freq1: Alias for field number 1

freq2: Alias for field number 4

llr: Alias for field number 7

perc_diff1: Alias for field number 3

perc_diff2: Alias for field number 6

word: Alias for field number 0

class fuzzy_search.analysis.spelling_compare.SpellingCompare(word_freq1: Counter, word_freq2: Counter, embeddings)[source]

Bases: object

Compares word frequencies between two corpora and links words that dropped in one corpus to similar words that rose in the other, using word embeddings.

word_freq1

Word frequencies in the first corpus.

Type:: Counter

word_freq2

Word frequencies in the second corpus.

Type:: Counter

embeddings: A word embedding model exposing wv.similarity(word1, word2) (e.g. a gensim Word2Vec-like model).

total1

The total token count of the first corpus.

Type:: int

total2

The total token count of the second corpus.

Type:: int

word_frac1

Relative frequency of each word in the first corpus.

Type:: Dict[str, float]

word_frac2

Relative frequency of each word in the second corpus.

Type:: Dict[str, float]

__init__(word_freq1: Counter, word_freq2: Counter, embeddings)[source]

Initializes the SpellingCompare with word frequencies from two corpora.

Parameters:

word_freq1 (Counter) – Word frequencies in the first corpus.
word_freq2 (Counter) – Word frequencies in the second corpus.
embeddings – A word embedding model exposing wv.similarity(word1, word2).

compute_percentage_diff(word: str)[source]

Computes the frequency and percentage-difference statistics for a word between the two corpora.

Parameters:: word (str) – The word to compute statistics for.
Returns:: A namedtuple with the word’s frequency, fraction and percentage difference in each corpus, plus the log-likelihood ratio and its direction.
Return type:: Diff

get_frequency_change_words(hf_words: List[str] | Set[str], increase_threshold: float = 0.5, emerge_threshold: float = 5.0, decrease_threshold: float = 0.5, disappear_threshold: float = 5.0, similarity_threshold: float = 0.6)[source]

Classifies frequency changes for a set of high-frequency words and links decreasing/disappearing words to similar increasing/emerging words.

Words are first sorted into ‘decrease’/’disappear’ (dropped from corpus 1 to 2) and ‘increase’/’emerge’ (rose from corpus 1 to 2) buckets based on the percentage difference thresholds (see sort_drop_jump()). Each dropped word is then compared via embedding similarity to every risen word; if the similarity exceeds similarity_threshold, the pair is recorded as a ‘replace’ (if the word disappeared) or ‘shift’ (if it merely decreased) change. Dropped or risen words with no matching counterpart are recorded as unlinked changes.

Parameters:

hf_words (Union[List[str], Set[str]]) – The high-frequency words to compare.
increase_threshold (float, optional) – Minimum percentage increase to count as ‘increase’. Defaults to 0.5.
emerge_threshold (float, optional) – Minimum percentage increase to count as ‘emerge’. Defaults to 5.0.
decrease_threshold (float, optional) – Minimum percentage decrease to count as ‘decrease’. Defaults to 0.5.
disappear_threshold (float, optional) – Minimum percentage decrease to count as ‘disappear’. Defaults to 5.0.
similarity_threshold (float, optional) – Minimum embedding similarity required to link a dropped word to a risen word. Defaults to 0.6.

Returns:

A list of (drop_diff, jump_diff, drop_level, jump_level, change_type) tuples describing each detected change (drop_diff/jump_diff or their levels may be None when a word has no linked counterpart).

Return type:

List[tuple]

get_high_frequency_words(min_freq: int = None, min_frac: float = None)[source]

Returns the union of words meeting a minimum frequency/fraction threshold in either corpus.

Parameters:

min_freq (int, optional) – Minimum absolute frequency in either corpus.
min_frac (float, optional) – Minimum relative frequency (fraction) in either corpus. Only used if min_freq is not given.

Returns:

The sorted list of words meeting the threshold in corpus 1 or corpus 2.

Return type:

List[str]

Raises:

ValueError – If neither min_freq nor min_frac is given.

fuzzy_search.analysis.spelling_compare.sort_drop_jump(hf_words: Set[str] | List[str], spelling_compare: SpellingCompare, increase_threshold: float = 0.5, emerge_threshold: float = 5.0, decrease_threshold: float = 0.5, disappear_threshold: float = 5.0)[source]

Sorts high-frequency words into ‘decrease’/’disappear’ and ‘increase’/’emerge’ buckets based on their percentage frequency difference between two corpora.

Parameters:

hf_words (Union[Set[str], List[str]]) – The high-frequency words to classify.
spelling_compare (SpellingCompare) – Provides per-word percentage-difference stats.
increase_threshold (float, optional) – Minimum percentage increase to count as ‘increase’. Defaults to 0.5.
emerge_threshold (float, optional) – Minimum percentage increase to count as ‘emerge’ (checked before ‘increase’). Defaults to 5.0.
decrease_threshold (float, optional) – Minimum percentage decrease to count as ‘decrease’. Defaults to 0.5.
disappear_threshold (float, optional) – Minimum percentage decrease to count as ‘disappear’ (checked before ‘decrease’). Defaults to 5.0.

Returns:

A pair of dicts (drop, jump), each mapping a change-level name (‘decrease’/’disappear’ or ‘emerge’/’increase’) to the list of Diff records at that level.

Return type:

Tuple[Dict[str, list], Dict[str, list]]

fuzzy_search.analysis.subtoken module

Byte Pair Encoding (BPE) subword tokenization utilities.

This module implements a simple BPE training algorithm operating on tokens split into characters (plus a trailing word-boundary marker). It builds a corpus of BPEToken objects, repeatedly finds the most frequent adjacent symbol pair using a FrequencyTracker index, merges that pair into a new symbol across all tokens, and updates the frequency index incrementally, producing a learned subword vocabulary.

class fuzzy_search.analysis.subtoken.BPEToken(token: str)[source]

Bases: object

A token represented as a mutable list of BPE symbols.

Initially each symbol is a single character of the token, with a trailing space symbol marking the end of the token. As BPE merges are applied, adjacent symbols get combined into longer symbols.

token

The original token string.

Type:: str

symbols

The current list of symbols representing the token.

Type:: List[str]

__init__(token: str)[source]

Initializes a BPEToken by splitting it into characters plus an end-of-word marker.

Parameters:: token (str) – The token string to represent.

property symbol_pairs

All adjacent pairs of symbols in the token.

Type:: List[Tuple[str, str]]

class fuzzy_search.analysis.subtoken.FrequencyTracker[source]

Bases: object

Tracks symbol-pair frequencies and supports fast lookup of the most frequent pair(s).

Frequencies are organized into buckets keyed first by frequency, then by the combined character length of the symbol pair, so that the most frequent pair (optionally the shortest among ties) can be retrieved without scanning all pairs.

freq_buckets

Maps frequency -> combined symbol length -> set of symbol pairs with that frequency and length.

Type:: Dict[int, Dict[int, Set[Tuple[str, str]]]]

symbol_pair_freq

Maps each symbol pair to its current frequency.

Type:: Dict[Tuple[str, str], int]

max_freq

The highest frequency currently present in freq_buckets.

Type:: int

all_with_max_frequency(length=None)[source]

Returns all symbol pairs that currently have the maximum frequency.

Parameters:: length (int, optional) – If given, restrict to symbol pairs whose combined character length equals this value.
Returns:: The set of symbol pairs at the maximum frequency.
Return type:: Set[Tuple[str, str]]

frequency_of(symbol_pair)[source]: Returns the current frequency of a symbol pair, or 0 if it is not tracked.

most_frequent(length=None)[source]

Returns one symbol pair with the current maximum frequency.

Parameters:: length (int, optional) – If given, restrict the search to symbol pairs whose combined character length equals this value.
Returns:: A tuple of (symbol_pair, frequency), or None if there is no pair (matching the length, if given).
Return type:: Optional[Tuple[Tuple[str, str], int]]

most_frequent_shortest()[source]

Return one symbol pair with the highest frequency and, among ties, the shortest combined string length.

Returns:: A tuple of (symbol_pair, frequency, length), or None if no symbol pairs are tracked.
Return type:: Optional[Tuple[Tuple[str, str], int, int]]

update(symbol_pair: Tuple[str, str], count: int)[source]

Adjusts the frequency of a symbol pair by count and updates the buckets.

Removes the pair from its old frequency/length bucket (if any) and re-inserts it into the bucket for its new frequency, also maintaining max_freq. If the new frequency is zero or below, the pair is removed entirely.

Parameters:

symbol_pair (Tuple[str, str]) – The symbol pair to update.
count (int) – The (positive or negative) amount to add to the pair’s frequency.

fuzzy_search.analysis.subtoken.compare_token_symbol_pairs(token1: List[str] | Tuple[str, ...], token2: List[str] | Tuple[str, ...]) → Tuple[Set[Tuple[str, str]], Set[Tuple[str, str]], Set[Tuple[str, str]]][source]

Compares the adjacent symbol pairs of two symbol sequences (e.g. a token before and after a merge).

Parameters:

token1 (Union[List[str], Tuple[str, ...]]) – The first symbol sequence.
token2 (Union[List[str], Tuple[str, ...]]) – The second symbol sequence.

Returns:

A tuple of (pairs present in both, pairs only in token1, pairs only in token2).

Return type:

Tuple[Set, Set, Set]

fuzzy_search.analysis.subtoken.find_new_symbol_pairs(merge_symbol: str, token: Tuple[str, ...])[source]

Finds the new adjacent symbol pairs introduced around each occurrence of a merged symbol.

Parameters:

merge_symbol (str) – The newly merged symbol to search for in token.
token (Tuple[str, ...]) – The token’s (already merged) symbol sequence.

Returns:

The new symbol pairs formed with merge_symbol’s neighbours.

Return type:

List[Tuple[str, str]]

fuzzy_search.analysis.subtoken.generate_corpus_symbol_pairs(corpus: Counter[BPEToken, int]) → Generator[Tuple[Tuple[str, str], BPEToken], None, None][source]: Iterate over all tokens in a corpus and return all tuples of two adjacent symbols together with their corresponding token

fuzzy_search.analysis.subtoken.generate_symbol_pairs(symbols: List[str] | Tuple[str, ...])[source]: Returns all adjacent pairs of symbols in a sequence.

fuzzy_search.analysis.subtoken.generate_vocab(corpus: Counter[BPEToken, int])[source]

Collects the set of all distinct symbols currently used across a corpus of BPETokens.

Parameters:: corpus (Counter[BPEToken, int]) – The tokens in the corpus.
Returns:: The set of distinct symbols in the corpus.
Return type:: Set[str]

fuzzy_search.analysis.subtoken.index_symbol_pair(corpus: Counter[BPEToken, int]) → Dict[Tuple[str, str], Set[BPEToken]][source]

Builds an index mapping each adjacent symbol pair to the set of tokens it occurs in.

Parameters:: corpus (Counter[BPEToken, int]) – The tokens in the corpus.
Returns:: Maps each symbol pair to the tokens containing it.
Return type:: Dict[Tuple[str, str], Set[BPEToken]]

fuzzy_search.analysis.subtoken.make_byte_pair_encoding(tokens: List[str], k: int)[source]

Trains a Byte Pair Encoding vocabulary from a list of token strings.

Iteratively merges the most frequent (and, among ties, shortest) adjacent symbol pair across the corpus for k iterations, growing the vocabulary by one merged symbol per iteration.

Parameters:

tokens (List[str]) – The token strings (e.g. words) to train the BPE model on.
k (int) – The number of merge iterations (and roughly the number of new subword symbols to learn).

Returns:

The learned vocabulary of symbols, including the original characters and the merged subword units.

Return type:

Set[str]

fuzzy_search.analysis.subtoken.make_symbol_pair_freq(corpus: Counter[BPEToken, int], symbol_pair_index: Dict[Tuple[str, str], Set[BPEToken]])[source]

Builds a FrequencyTracker of symbol-pair frequencies from a corpus and its symbol pair index.

Parameters:

corpus (Counter[BPEToken, int]) – Token frequencies in the corpus.
symbol_pair_index (Dict[Tuple[str, str], Set[BPEToken]]) – Maps each symbol pair to the set of tokens it occurs in.

Returns:

A tracker initialised with each symbol pair’s total frequency, summed over the tokens it occurs in.

Return type:

FrequencyTracker

fuzzy_search.analysis.subtoken.merge_symbols_in_token(merge_symbol: str, token: BPEToken)[source]

Returns a new symbol sequence for a token with every occurrence of an adjacent symbol pair merged into a single combined symbol.

Parameters:

merge_symbol (str) – The concatenated string of the symbol pair being merged (used to detect matching adjacent pairs in the token’s symbol list).
token (BPEToken) – The token whose symbols are being merged.

Returns:

The token’s new symbol sequence, with matching adjacent pairs replaced by the merged symbol.

Return type:

Tuple[str, …]

fuzzy_search.analysis.subtoken.merge_symbols_in_tokens(symbol_pair_index: Dict[Tuple[str, str], Set[BPEToken]], symbol_pair_freq: FrequencyTracker, corpus: Counter[BPEToken, int], merge_symbols: Tuple[str, str])[source]

Applies a BPE merge of merge_symbols to every token containing it, updating the symbol pair index and frequency tracker in place.

For each affected token, this computes which symbol pairs disappear and which new ones appear as a result of the merge (via compare_token_symbol_pairs()), removes the disappearing pairs from the index/frequencies, adds the new ones, and finally removes the now-fully-merged merge_symbols entry from the index.

Parameters:

symbol_pair_index (Dict[Tuple[str, str], Set[BPEToken]]) – The symbol pair to tokens index, updated in place.
symbol_pair_freq (FrequencyTracker) – The frequency tracker, updated in place.
corpus (Counter[BPEToken, int]) – Token frequencies in the corpus.
merge_symbols (Tuple[str, str]) – The symbol pair to merge.

fuzzy_search.analysis.subtoken.prune_symbol_pair_freq(symbol_pair_freq: Counter[Tuple[str, str], int])[source]: Removes symbol pairs with a frequency of zero from a symbol-pair frequency counter, in place.

fuzzy_search.analysis.subtoken.string_tokens_to_corpus(tokens: List[str]) → Counter[BPEToken, int][source]

Builds a BPE corpus from a list of token strings.

Parameters:: tokens (List[str]) – The token strings, e.g. words from a document collection.
Returns:: A counter mapping each unique token (wrapped as a BPEToken) to its frequency in tokens.
Return type:: Counter[BPEToken, int]

Module contents

Standalone corpus/vocabulary analysis tools that build on the tokenization layer but are not wired into the core fuzzy phrase-search engine: skipgram-based term similarity (similarity), ngram frequency and log-likelihood-ratio statistics (freq), and spelling-variant comparison (spelling_compare).