fuzzy_search.match package

Submodules

fuzzy_search.match.candidate_match module

Candidate match objects and the skipgram-based logic used to build, grow and validate fuzzy match candidates between a text and a phrase.

class fuzzy_search.match.candidate_match.Candidate(phrase: Phrase, match_start_offset: int, match_end_offset: int, match_string: str, skipgram_overlap: float = 0.0)

Bases: object

A finalized candidate match between a phrase and a span of text, with the matching string, its offsets, and the skipgram overlap score.

__init__(phrase: Phrase, match_start_offset: int, match_end_offset: int, match_string: str, skipgram_overlap: float = 0.0)

Create a Candidate for a matched phrase.

Parameters:

• phrase (Phrase) – the phrase that this candidate is a match for

• match_start_offset (int) – the start offset of the match in the text

• match_end_offset (int) – the end offset of the match in the text

• match_string (str) – the matching text string

• skipgram_overlap (float) – the skipgram overlap score between phrase and match string

class fuzzy_search.match.candidate_match.CandidatePartial(phrase: Phrase, max_length_variance: int = 1, ignorecase: bool = False, debug: int = 0)

Bases: object

A partially built candidate match for a phrase, accumulating matching skipgrams found in the text as they are encountered. Used while scanning text for skipgram matches, before a final Candidate is produced.

__init__(phrase: Phrase, max_length_variance: int = 1, ignorecase: bool = False, debug: int = 0)

Create a Candidate instance for a given Phrase object.

Parameters:

• phrase (Phrase) – a phrase object

• ignorecase (bool) – whether to ignore case when matching skip grams

• debug (int) – level to show debugging info

fuzzy_search.match.candidate_match.add_skip_match(candidate: CandidatePartial, skipgram: SkipGram) → None

Add a skipgram match between a text and a phrase to the candidate, updating its offsets and skipgram counts. If adding the skipgram makes the candidate’s matched span longer than the phrase allows, or its start no longer lies in the phrase’s early skipgram index, the earliest skipgrams are dropped from the front until the candidate is valid again.

Parameters:

• candidate (CandidatePartial) – the candidate to add the skipgram to

• skipgram (SkipGram) – a matching skipgram

fuzzy_search.match.candidate_match.candidate_from_partial(candidate_partial: CandidatePartial, text: Dict[str, any]) → Candidate

Create a finalized Candidate instance from a CandidatePartial object.

Parameters:

• candidate_partial (CandidatePartial) – a partially built candidate match

• text (Dict[str, any]) – the text object that the candidate match string is taken from

Returns:

a finalized Candidate

Return type:

Candidate

fuzzy_search.match.candidate_match.get_match_start_offset(candidate: CandidatePartial) → None | int

Calculate the start offset of the match in the text, based on the candidate’s first skipgram and that skipgram’s offset within the phrase.

Parameters:

candidate (CandidatePartial) – the candidate to compute the start offset for

Returns:

the match start offset, or None if the candidate has no skipgrams

Return type:

Union[None, int]

fuzzy_search.match.candidate_match.get_match_string(candidate: CandidatePartial, text: Dict[str, any]) → str | None

Find the matching string of a candidate fuzzy match by slicing the text between the candidate’s start and end offsets.

Parameters:

• candidate (CandidatePartial) – the candidate whose match string to extract

• text (Dict[str, any]) – the text object containing the candidate’s match string

Returns:

the matching text string

Return type:

Union[str, None]

fuzzy_search.match.candidate_match.get_skip_count_overlap(candidate: CandidatePartial) → float

Calculate deviation of candidate skipgrams from phrase skipgrams.

Parameters:

candidate (CandidatePartial) – the candidate to score

Returns:

the skipgram overlap (-inf, 1.0]

Return type:

float

fuzzy_search.match.candidate_match.get_skip_match_length(candidate: CandidatePartial) → int

Return the length of the matching string spanned by the candidate’s current offsets.

Parameters:

candidate (CandidatePartial) – the candidate to measure

Returns:

the length of the candidate’s matching span

Return type:

int

fuzzy_search.match.candidate_match.get_skip_set_overlap(candidate: CandidatePartial) → float

Calculate the skipgram set overlap between the candidate and its phrase (fraction of the phrase’s distinct skipgrams that are present in the candidate), store it on the candidate, and return it.

Parameters:

candidate (CandidatePartial) – the candidate to score

Returns:

the skipgram set overlap

Return type:

float

fuzzy_search.match.candidate_match.is_match(candidate: CandidatePartial, skipgram_threshold: float) → bool

Check if the candidate is a likely match for its corresponding phrase, based on its length relative to the phrase, whether its first/last skipgrams are in the phrase’s early/late skipgram indexes, and whether its skipgram set overlap meets the given threshold.

Parameters:

• candidate (CandidatePartial) – the candidate to validate

• skipgram_threshold (float) – the minimum required skipgram set overlap

Returns:

whether the candidate is a likely match

Return type:

bool

fuzzy_search.match.candidate_match.remove_first_skip(candidate: CandidatePartial) → None

Remove the first matching skipgram from the candidate’s list and update its skipgram count and set accordingly.

Parameters:

candidate (CandidatePartial) – the candidate to remove the first skipgram from

fuzzy_search.match.candidate_match.same_candidate(candidate1: CandidatePartial | Candidate, candidate2: CandidatePartial | Candidate)

Check if this candidate has the same start and end offsets as another candidate.

Parameters:

• candidate1 (Candidate) – first candidate .

• candidate2 (Candidate) – second candidate.

Returns:

this candidate match has the same offsets as the other candidate

Return type:

bool

fuzzy_search.match.candidate_match.shift_start_skip(candidate: CandidatePartial) → bool

Check if a later skipgram in the candidate would make a better starting point than the current first skipgram (i.e. it shortens an overly long match without losing the best start), and if so, shift the candidate’s start to that skipgram.

Parameters:

candidate (CandidatePartial) – a candidate match to check and potentially shift

Returns:

whether the start was shifted

Return type:

bool

fuzzy_search.match.exact_match module

Functions for finding exact (non-fuzzy) matches of phrases in text, with or without requiring word boundaries.

fuzzy_search.match.exact_match.add_exact_match_score(match: PhraseMatch) → PhraseMatch

Set perfect (1.0) similarity scores on a match, since it is an exact match.

Parameters:

match (PhraseMatch) – the exact phrase match to score

Returns:

the same match, with scores set

Return type:

PhraseMatch

fuzzy_search.match.exact_match.get_exact_match_ranges(exact_matches: List[PhraseMatch]) → List[dict]

Merge a list of exact phrase matches into contiguous, possibly overlapping, character ranges, each annotated with the set of phrases that matched within that range.

Parameters:

exact_matches (List[PhraseMatch]) – a list of exact phrase matches

Returns:

a list of match range dictionaries with ‘s’ (start), ‘e’ (end) and ‘phrases’ keys

Return type:

List[dict]

fuzzy_search.match.exact_match.get_known_word_offsets(match_ranges: List[Dict[str, any]], text_doc: Dict[str, str]) → Dict[int, dict]

Index the individual words within a list of match ranges by their text offset.

Parameters:

• match_ranges (List[Dict[str, any]]) – a list of match range dictionaries with ‘s’ (start), ‘e’ (end) and ‘phrases’ keys

• text_doc (Dict[str, str]) – the text document the match ranges were found in

Returns:

a dictionary mapping word start offset to word info

Return type:

Dict[int, dict]

fuzzy_search.match.exact_match.index_known_word_offsets(exact_matches: List[PhraseMatch]) → Dict[int, Dict[str, any]]

Index the individual words of a list of exact phrase matches by their text offset.

Parameters:

exact_matches (List[PhraseMatch]) – a list of exact phrase matches

Returns:

a dictionary mapping word start offset to word info (word, start, end, matching phrases)

Return type:

Dict[int, Dict[str, any]]

fuzzy_search.match.exact_match.search_exact(phrase: Phrase, text: Dict[str, str], ignorecase: bool = False, use_word_boundaries: bool = True)

Search for all exact occurrences of a single phrase in a text.

Parameters:

• phrase (Phrase) – the phrase to search for

• text (Dict[str, str]) – the text object to search, with at least a ‘text’ key

• ignorecase (bool) – whether to ignore case when matching

• use_word_boundaries (bool) – whether matches must be on word boundaries

Returns:

an iterator of regex match objects

fuzzy_search.match.exact_match.search_exact_phrases(phrase_model: PhraseModel, text: Dict[str, str], ignorecase: bool = False, use_word_boundaries: bool = True, include_variants: bool = False, debug: int = 0)

Search for exact occurrences of phrases from a phrase model in a text, dispatching to word-boundary-aware or plain substring search depending on use_word_boundaries.

Parameters:

• phrase_model (PhraseModel) – the phrase model containing phrases to search for

• text (Dict[str, str]) – the text object to search, with at least ‘text’ and ‘id’ keys

• ignorecase (bool) – whether to ignore case when matching

• use_word_boundaries (bool) – whether matches must be on word boundaries

• include_variants (bool) – whether to also search for registered phrase variants

• debug (int) – level to show debug information

Returns:

a generator of exact phrase matches

fuzzy_search.match.exact_match.search_exact_phrases_with_word_boundaries(phrase_model: PhraseModel, text: Dict[str, str], ignorecase: bool = False, include_variants: bool = False, debug: int = 0)

Search for exact phrase matches in text, requiring matches to start and end on word boundaries. For each word in the text that is the first word of a known phrase, check whether the full phrase string matches the text starting at that word.

Parameters:

• phrase_model (PhraseModel) – the phrase model containing phrases to search for

• text (Dict[str, str]) – the text object to search, with at least ‘text’ and ‘id’ keys

• ignorecase (bool) – whether to ignore case when matching

• include_variants (bool) – whether to also search for registered phrase variants

• debug (int) – level to show debug information

Returns:

a generator of exact phrase matches

fuzzy_search.match.exact_match.search_exact_phrases_without_word_boundaries(phrase_model: PhraseModel, text: Dict[str, str], ignorecase: bool = False, include_variants: bool = False, debug: int = 0)

Search for exact phrase matches in text as plain substring matches, without requiring matches to be on word boundaries.

Parameters:

• phrase_model (PhraseModel) – the phrase model containing phrases to search for

• text (Dict[str, str]) – the text object to search, with at least ‘text’ and ‘id’ keys

• ignorecase (bool) – whether to ignore case when matching

• include_variants (bool) – whether to also search for registered phrase variants

• debug (int) – level to show debug information

Returns:

a generator of exact phrase matches

fuzzy_search.match.match_offsets module

Algorithms for building PhraseMatch objects from candidate matches, validating their properties, and adjusting their start/end offsets to align with word boundaries.

fuzzy_search.match.match_offsets.adjust_match_end_offset(phrase_string: str, candidate_string: str, text: Dict[str, any], end_offset: int, punctuation: str, debug: int = 0) → int | None

Adjust the end offset if it is not at a word boundary.

Parameters:

• phrase_string (str) – the phrase string

• candidate_string (str) – the candidate match string

• text (Dict[str, any]) – the text object that contains the candidate match string

• end_offset (int) – the text offset of the candidate match string

• punctuation (str) – the set of characters to treat as punctuation

• debug (int) – level to show debug information

Returns:

the adjusted offset or None if the required adjustment is too big

Return type:

Union[int, None]

fuzzy_search.match.match_offsets.adjust_match_offsets(phrase_string: str, candidate_string: str, text: Dict[str, any], candidate_start_offset: int, candidate_end_offset: int, punctuation: str = '!"#$%&\'()*+,-./:;<=>?@[\\]^_`{|}~', debug: int = 0) → Dict[str, str | int] | None

Adjust the end offset if it is not at a word boundary.

Parameters:

• phrase_string (str) – the phrase string

• candidate_string (str) – the candidate match string

• text (Dict[str, any]) – the text object that contains the candidate match string

• candidate_start_offset (int) – the text offset of the start of the candidate match string

• candidate_end_offset (int) – the text offset of the end of the candidate match string

• punctuation (str) – the set of characters to treat as punctuation (defaults to string.punctuation)

• debug (int) – level to show debug information

Returns:

the adjusted offset or None if the required adjustment is too big

Return type:

Union[int, None]

fuzzy_search.match.match_offsets.adjust_match_start_offset(text: Dict[str, any], match_string: str, match_offset: int) → int | None

Adjust the start offset if it is not at a word boundary.

Parameters:

• text (Dict[str, any]) – the text object that contains the candidate match string

• match_string (str) – the candidate match string

• match_offset (int) – the text offset of the candidate match string

Returns:

the adjusted offset or None if the required adjustment is too big

Return type:

Union[int, None]

fuzzy_search.match.match_offsets.calculate_end_shift(phrase_end: str, match_end: str, text_suffix: str, end_offset: int)

Determine whether and how much to shift the end offset, based on trailing whitespace for either the phrase or the match or both.

fuzzy_search.match.match_offsets.candidates_to_matches(candidates: List[Candidate], text: dict, phrase_model: PhraseModel, ignorecase: bool = False) → List[PhraseMatch]

Convert a list of fuzzy match candidates into PhraseMatch objects, resolving variant candidates to their corresponding main phrase and computing similarity scores.

Parameters:

• candidates (List[Candidate]) – a list of candidate matches

• text (dict) – the text object the candidates were found in

• phrase_model (PhraseModel) – the phrase model containing the phrases and their variants

• ignorecase (bool) – whether to ignore case when scoring matches

Returns:

a list of phrase matches

Return type:

List[PhraseMatch]

fuzzy_search.match.match_offsets.filter_matches_by_overlap(filtered_matches: List[PhraseMatch], first_best: bool = False, debug: int = 0) → List[PhraseMatch]

Filter matches by overlapping match string offsets. When there are multiple phrases matching with the same character range in the input text, only pick the matches with the highest similarity scores. By default, all matches with the highest similarity score are returned. Use ‘first_best=True’ to return only the first best scoring match.

fuzzy_search.match.match_offsets.map_string(affix_string: str, punctuation: str, whitespace_only: bool = False, debug: int = 0) → str

Turn affix string into type char representation. Types are ‘w’ for non-whitespace char, and ‘s’ for whitespace char.

Parameters:

• affix_string – a string

• punctuation (str) – the set of characters to treat as punctuation

• whitespace_only (bool) – whether to treat only whitespace as word boundary or also include (some) punctuation

• debug (int) – level to show debug information

Type:

str

Returns:

the type char representation

Return type:

str

fuzzy_search.match.match_offsets.validate_match_props(match_phrase: Phrase, match_variant: Phrase, match_string: str, match_offset: int) → None

Validate match properties.

Parameters:

• match_phrase (Phrase) – the phrase that has been matched

• match_variant (Phrase) – the variant of the phrase that the match is based on

• match_string (str) – the text string that matches the variant phrase

• match_offset (int) – the offset of the match string in the text

Returns:

None

Return type:

None

fuzzy_search.match.phrase_match module

PhraseMatch and related classes that represent a fuzzy match between a phrase (or a part of it) and a span of text, along with their JSON (de)serialization.

Algorithms for building and adjusting the offsets of matches live in fuzzy_search.match.match_offsets; this module only defines the match data models themselves.

class fuzzy_search.match.phrase_match.MatchType(*values)

Bases: Enum

Enumerates how a token match relates a text token to a phrase token: no match, a partial match within a phrase token, a full match, or a partial match within a text token.

FULL = 1

NONE = 0

PARTIAL_OF_PHRASE_TOKEN = 0.5

PARTIAL_OF_TEXT_TOKEN = 1.5

class fuzzy_search.match.phrase_match.PhraseMatch(match_phrase: Phrase, match_variant: Phrase, match_string: str, match_offset: int, ignorecase: bool = False, text_id: None | str = None, match_scores: dict = None, match_label: str | List[str] = None, match_id: str = None, levenshtein_similarity: float = None)

Bases: object

A fuzzy match between a phrase (and a specific spelling variant of it) and a string found in a text, with its offsets, label(s) and similarity scores.

__init__(match_phrase: Phrase, match_variant: Phrase, match_string: str, match_offset: int, ignorecase: bool = False, text_id: None | str = None, match_scores: dict = None, match_label: str | List[str] = None, match_id: str = None, levenshtein_similarity: float = None)

Create a PhraseMatch.

Parameters:

• match_phrase – a phrase object for which a matching string is found in the text

• match_variant – a phrase object for the variant that matches the string in the text

• match_string – the matching string found in the text

• match_offset – the offset of the matching string in the text

• ignorecase – boolean flag whether to ignore case differences

• text_id – the identifier of the text in which the match is found

• match_scores – the similarity scores of the match

• match_label – one or more labels to attach to the match

• match_id – an optional identifier to use for the match

• levenshtein_similarity – an optional precomputed levenshtein similarity score

add_scores(skipgram_overlap: None | float = None) → None

Compute overlap and similarity scores between the match variant and the match string and add these to the match object.

Parameters:

skipgram_overlap (Union[float, None]) – the overlap in skipgrams between match string and match variant

Returns:

None

Return type:

None

as_web_anno() → Dict[str, any]

Turn match object into a W3C Web Annotation representation.

Returns:

a W3C Web Annotation dictionary

Return type:

Dict[str, any]

character_overlap: None | float

static from_json(match_json)

Reconstruct a PhraseMatch from its JSON dictionary representation.

Parameters:

match_json – a JSON dictionary as produced by json()

Returns:

the reconstructed phrase match

Return type:

PhraseMatch

has_label(label: str)

Check whether this match has the given label.

Parameters:

label (str) – a label string

Returns:

whether the match has this label

Return type:

bool

json() → dict

Return a JSON-serializable dictionary representation of the match.

property label_list: List[str]

Return the match’s label(s) as a list, regardless of whether it is stored as a single string, a list, or None.

levenshtein_similarity: None | float

ngram_overlap: None | float

overlaps(other: PhraseMatch) → bool

Check if the match string of this match object overlaps with the match string of another match object.

Parameters:

other (PhraseMatch) – another match object

Returns:

a boolean indicating whether the match_strings of the two objects overlap in the source text

Return type:

bool

score_character_overlap()

Return the character overlap between the variant phrase_string and the match_string

Returns:

the character overlap as proportion of the variant phrase string

Return type:

float

score_levenshtein_similarity()

Return the levenshtein similarity between the variant phrase_string and the match_string

Returns:

the levenshtein similarity as proportion of the variant phrase string

Return type:

float

score_ngram_overlap() → float

Return the ngram overlap between the variant phrase_string and the match_string

Returns:

the ngram overlap as proportion of the variant phrase string

Return type:

float

skipgram_overlap: None | float

class fuzzy_search.match.phrase_match.PhraseMatchInContext(match: PhraseMatch, text: str | dict = None, context: str = None, context_start: int = None, context_end: int = None, prefix_size: int = 20, suffix_size: int = 20)

Bases: PhraseMatch

A PhraseMatch extended with a window of surrounding text (prefix and suffix context) taken from the source document.

as_web_anno() → Dict[str, any]

Turn match object into a W3C Web Annotation representation, including a TextQuoteSelector with the prefix/exact/suffix context.

json()

Return a JSON-serializable dictionary representation including the context.

fuzzy_search.match.phrase_match.phrase_match_from_json(match_json: dict) → PhraseMatch

Reconstruct a PhraseMatch (or PhraseMatchInContext, if context info is present) from its JSON dictionary representation.

Parameters:

match_json (dict) – a JSON dictionary representation of a phrase match

Returns:

the reconstructed phrase match

Return type:

PhraseMatch

fuzzy_search.match.phrase_match.validate_match_props(match_phrase: Phrase, match_variant: Phrase, match_string: str, match_offset: int) → None

Validate match properties.

Parameters:

• match_phrase (Phrase) – the phrase that has been matched

• match_variant (Phrase) – the variant of the phrase that the match is based on

• match_string (str) – the text string that matches the variant phrase

• match_offset (int) – the offset of the match string in the text

Returns:

None

Return type:

None

fuzzy_search.match.skip_match module

Skipgram-based matching: tracking which phrase skipgrams are found in a text (SkipMatches), and turning those skipgram matches into candidate matches per phrase.

class fuzzy_search.match.skip_match.SkipMatches(ngram_size: int, skip_size: int)

Bases: object

Tracks, for a set of phrases, which of their skipgrams are found in a text, along with the text offsets where each match occurs. Used as an intermediate structure to build candidate matches per phrase.

__init__(ngram_size: int, skip_size: int)

Create an empty SkipMatches tracker.

Parameters:

• ngram_size (int) – the ngram size used to compute skipgrams

• skip_size (int) – the maximum number of characters skipped between ngram parts

add_skip_match(skipgram: SkipGram, phrase: Phrase | Token) → None

Add a skipgram from a text that matches a phrase.

Parameters:

• skipgram (SkipGram) – a skipgram from a text

• phrase (Phrase) – a phrase object that matches the skipgram

remove_phrase(phrase: Phrase | Token)

Remove all tracked skipgram match data for a given phrase.

Parameters:

phrase (Union[Phrase, Token]) – the phrase to remove from the tracker

fuzzy_search.match.skip_match.filter_overlapping_phrase_candidates(phrase_candidates: List[Candidate], debug: int = 0) → List[Candidate]

Filter a list of candidate matches for a phrase so that overlapping candidates are reduced to the single best one (by Levenshtein similarity, then by match length).

Parameters:

• phrase_candidates (List[Candidate]) – a list of candidate matches for the same phrase

• debug (int) – level to show debug information

Returns:

a list of non-overlapping candidate matches

Return type:

List[Candidate]

fuzzy_search.match.skip_match.filter_skipgram_threshold(skip_matches: SkipMatches, skip_threshold: float) → List[Phrase]

Filter the skipgram matches based on the skipgram overlap threshold.

Parameters:

• skip_matches (SkipMatches) – the phrases that matches the text

• skip_threshold (float) – the threshold for the skipgram overlap between a text and a phrase

Returns:

the list of phrases with a skipgram overlap that meets the threshold

Return type:

List[Phrase]

fuzzy_search.match.skip_match.get_skipmatch_candidates(text: Dict[str, any], skip_matches: SkipMatches, skipgram_threshold: float, phrase_model: PhraseModel, max_length_variance: int = 1, ignorecase: bool = False, debug: int = 0) → Dict[str, List[Candidate]]

Find all candidate matches for the phrases in a SkipMatches object.

Parameters:

• text (Dict[str, any]) – the text object to match with phrases

• skip_matches (SkipMatches) – a SkipMatches object with matches between a text and a list of phrases

• skipgram_threshold (float) – a threshold for how many skipgrams should match between a phrase and a candidate

• phrase_model (PhraseModel) – a phrase model, either as dictionary or as PhraseModel object

• max_length_variance (int) – the maximum difference in length between candidate and phrase

• ignorecase (bool) – whether to ignore case when matching skip grams

• debug (int) – level to show debug information

Returns:

a list of candidate matches

Return type:

Dict[str, List[Candidate]]

fuzzy_search.match.skip_match.get_skipmatch_phrase_candidates(text: Dict[str, any], phrase: Phrase, skip_matches: SkipMatches, skipgram_threshold: float, max_length_variance: int = 1, ignorecase: bool = False, debug: int = 0) → List[Candidate]

Find all candidate matches for a given phrase and SkipMatches object.

Parameters:

• text (Dict[str, any]) – the text object to match with phrases

• phrase (Phrase) – a phrase to find candidate matches for

• skip_matches (SkipMatches) – a Skipmatches object with matches between a text and a list of phrases

• skipgram_threshold (float) – a threshold for how many skipgrams should match between a phrase and a candidate

• max_length_variance (int) – the maximum difference in length between candidate and phrase

• ignorecase (bool) – whether to ignore case when matching skip grams

• debug (int) – level to show debug information

Returns:

a list of candidate matches

Return type:

List[Candidate]

fuzzy_search.match.skip_match.get_skipset_overlap(phrase: Phrase, skip_matches: SkipMatches) → float

Calculate the overlap between the set of skipgrams of a text and the skipgrams of a phrase.

Parameters:

• phrase (Phrase) – a phrase object that has been matched against a text

• skip_matches (SkipMatches) – a SkipMatches object containing the skipgram matches between a text and a list of phrases

Returns:

the fraction of skipgrams in the phrase that overlaps with the text

Return type:

float

Module contents

Classes and functions for matching phrases against text, including exact, skipgram-based, and candidate match logic, and the resulting phrase match objects.