# SPDX-License-Identifier: MIT # Copyright (C) 2022 Max Bachmann from __future__ import annotations from math import ceil from rapidfuzz._common_py import conv_sequences from rapidfuzz._utils import ScorerFlag, add_scorer_attrs, is_none, setupPandas from rapidfuzz.distance import ScoreAlignment from rapidfuzz.distance.Indel_py import ( _block_normalized_similarity as indel_block_normalized_similarity, distance as indel_distance, normalized_similarity as indel_normalized_similarity, ) def get_scorer_flags_fuzz(**_kwargs): return { "optimal_score": 100, "worst_score": 0, "flags": ScorerFlag.RESULT_F64 | ScorerFlag.SYMMETRIC, } fuzz_attribute = {"get_scorer_flags": get_scorer_flags_fuzz} def _norm_distance(dist, lensum, score_cutoff): score = (100 - 100 * dist / lensum) if lensum else 100 return score if score >= score_cutoff else 0 def _split_sequence(seq): if isinstance(seq, (str, bytes)): return seq.split() splitted_seq = [[]] for x in seq: ch = x if isinstance(x, str) else chr(x) if ch.isspace(): splitted_seq.append([]) else: splitted_seq[-1].append(x) return [tuple(x) for x in splitted_seq if x] def _join_splitted_sequence(seq_list): if not seq_list: return "" if isinstance(next(iter(seq_list)), str): return " ".join(seq_list) if isinstance(next(iter(seq_list)), bytes): return b" ".join(seq_list) joined = [] for seq in seq_list: joined += seq joined += [ord(" ")] return joined[:-1] def ratio( s1, s2, *, processor=None, score_cutoff=None, ): """ Calculates the normalized Indel similarity. Parameters ---------- s1 : Sequence[Hashable] First string to compare. s2 : Sequence[Hashable] Second string to compare. processor: callable, optional Optional callable that is used to preprocess the strings before comparing them. Default is None, which deactivates this behaviour. score_cutoff : float, optional Optional argument for a score threshold as a float between 0 and 100. For ratio < score_cutoff 0 is returned instead. Default is 0, which deactivates this behaviour. Returns ------- similarity : float similarity between s1 and s2 as a float between 0 and 100 See Also -------- rapidfuzz.distance.Indel.normalized_similarity : Normalized Indel similarity Notes ----- .. image:: img/ratio.svg Examples -------- >>> fuzz.ratio("this is a test", "this is a test!") 96.55171966552734 """ setupPandas() if is_none(s1) or is_none(s2): return 0 if score_cutoff is not None: score_cutoff /= 100 score = indel_normalized_similarity(s1, s2, processor=processor, score_cutoff=score_cutoff) return score * 100 def _partial_ratio_impl(s1, s2, score_cutoff): """ implementation of partial_ratio. This assumes len(s1) <= len(s2). """ s1_char_set = set(s1) len1 = len(s1) len2 = len(s2) res = ScoreAlignment(0, 0, len1, 0, len1) block = {} block_get = block.get x = 1 for ch1 in s1: block[ch1] = block_get(ch1, 0) | x x <<= 1 for i in range(1, len1): substr_last = s2[i - 1] if substr_last not in s1_char_set: continue # todo cache map ls_ratio = indel_block_normalized_similarity(block, s1, s2[:i], score_cutoff=score_cutoff) if ls_ratio > res.score: res.score = score_cutoff = ls_ratio res.dest_start = 0 res.dest_end = i if res.score == 1: res.score = 100 return res for i in range(len2 - len1): substr_last = s2[i + len1 - 1] if substr_last not in s1_char_set: continue # todo cache map ls_ratio = indel_block_normalized_similarity(block, s1, s2[i : i + len1], score_cutoff=score_cutoff) if ls_ratio > res.score: res.score = score_cutoff = ls_ratio res.dest_start = i res.dest_end = i + len1 if res.score == 1: res.score = 100 return res for i in range(len2 - len1, len2): substr_first = s2[i] if substr_first not in s1_char_set: continue # todo cache map ls_ratio = indel_block_normalized_similarity(block, s1, s2[i:], score_cutoff=score_cutoff) if ls_ratio > res.score: res.score = score_cutoff = ls_ratio res.dest_start = i res.dest_end = len2 if res.score == 1: res.score = 100 return res res.score *= 100 return res def partial_ratio( s1, s2, *, processor=None, score_cutoff=None, ): """ Searches for the optimal alignment of the shorter string in the longer string and returns the fuzz.ratio for this alignment. Parameters ---------- s1 : Sequence[Hashable] First string to compare. s2 : Sequence[Hashable] Second string to compare. processor: callable, optional Optional callable that is used to preprocess the strings before comparing them. Default is None, which deactivates this behaviour. score_cutoff : float, optional Optional argument for a score threshold as a float between 0 and 100. For ratio < score_cutoff 0 is returned instead. Default is 0, which deactivates this behaviour. Returns ------- similarity : float similarity between s1 and s2 as a float between 0 and 100 Notes ----- Depending on the length of the needle (shorter string) different implementations are used to improve the performance. short needle (length ≤ 64): When using a short needle length the fuzz.ratio is calculated for all alignments that could result in an optimal alignment. It is guaranteed to find the optimal alignment. For short needles this is very fast, since for them fuzz.ratio runs in ``O(N)`` time. This results in a worst case performance of ``O(NM)``. .. image:: img/partial_ratio_short_needle.svg long needle (length > 64): For long needles a similar implementation to FuzzyWuzzy is used. This implementation only considers alignments which start at one of the longest common substrings. This results in a worst case performance of ``O(N[N/64]M)``. However usually most of the alignments can be skipped. The following Python code shows the concept: .. code-block:: python blocks = SequenceMatcher(None, needle, longer, False).get_matching_blocks() score = 0 for block in blocks: long_start = block[1] - block[0] if (block[1] - block[0]) > 0 else 0 long_end = long_start + len(shorter) long_substr = longer[long_start:long_end] score = max(score, fuzz.ratio(needle, long_substr)) This is a lot faster than checking all possible alignments. However it only finds one of the best alignments and not necessarily the optimal one. .. image:: img/partial_ratio_long_needle.svg Examples -------- >>> fuzz.partial_ratio("this is a test", "this is a test!") 100.0 """ alignment = partial_ratio_alignment(s1, s2, processor=processor, score_cutoff=score_cutoff) if alignment is None: return 0 return alignment.score def partial_ratio_alignment( s1, s2, *, processor=None, score_cutoff=None, ): """ Searches for the optimal alignment of the shorter string in the longer string and returns the fuzz.ratio and the corresponding alignment. Parameters ---------- s1 : str | bytes First string to compare. s2 : str | bytes Second string to compare. processor: callable, optional Optional callable that is used to preprocess the strings before comparing them. Default is None, which deactivates this behaviour. score_cutoff : float, optional Optional argument for a score threshold as a float between 0 and 100. For ratio < score_cutoff None is returned instead. Default is 0, which deactivates this behaviour. Returns ------- alignment : ScoreAlignment, optional alignment between s1 and s2 with the score as a float between 0 and 100 Examples -------- >>> s1 = "a certain string" >>> s2 = "cetain" >>> res = fuzz.partial_ratio_alignment(s1, s2) >>> res ScoreAlignment(score=83.33333333333334, src_start=2, src_end=8, dest_start=0, dest_end=6) Using the alignment information it is possible to calculate the same fuzz.ratio >>> fuzz.ratio(s1[res.src_start:res.src_end], s2[res.dest_start:res.dest_end]) 83.33333333333334 """ setupPandas() if is_none(s1) or is_none(s2): return None if processor is not None: s1 = processor(s1) s2 = processor(s2) if score_cutoff is None: score_cutoff = 0 if not s1 and not s2: return ScoreAlignment(100.0, 0, 0, 0, 0) s1, s2 = conv_sequences(s1, s2) len1 = len(s1) len2 = len(s2) if len1 <= len2: shorter = s1 longer = s2 else: shorter = s2 longer = s1 res = _partial_ratio_impl(shorter, longer, score_cutoff / 100) if res.score != 100 and len1 == len2: score_cutoff = max(score_cutoff, res.score) res2 = _partial_ratio_impl(longer, shorter, score_cutoff / 100) if res2.score > res.score: res = ScoreAlignment(res2.score, res2.dest_start, res2.dest_end, res2.src_start, res2.src_end) if res.score < score_cutoff: return None if len1 <= len2: return res return ScoreAlignment(res.score, res.dest_start, res.dest_end, res.src_start, res.src_end) def token_sort_ratio( s1, s2, *, processor=None, score_cutoff=None, ): """ Sorts the words in the strings and calculates the fuzz.ratio between them Parameters ---------- s1 : str First string to compare. s2 : str Second string to compare. processor: callable, optional Optional callable that is used to preprocess the strings before comparing them. Default is None, which deactivates this behaviour. score_cutoff : float, optional Optional argument for a score threshold as a float between 0 and 100. For ratio < score_cutoff 0 is returned instead. Default is 0, which deactivates this behaviour. Returns ------- similarity : float similarity between s1 and s2 as a float between 0 and 100 Notes ----- .. image:: img/token_sort_ratio.svg Examples -------- >>> fuzz.token_sort_ratio("fuzzy wuzzy was a bear", "wuzzy fuzzy was a bear") 100.0 """ setupPandas() if is_none(s1) or is_none(s2): return 0 if processor is not None: s1 = processor(s1) s2 = processor(s2) s1, s2 = conv_sequences(s1, s2) sorted_s1 = _join_splitted_sequence(sorted(_split_sequence(s1))) sorted_s2 = _join_splitted_sequence(sorted(_split_sequence(s2))) return ratio(sorted_s1, sorted_s2, score_cutoff=score_cutoff) def token_set_ratio( s1, s2, *, processor=None, score_cutoff=None, ): """ Compares the words in the strings based on unique and common words between them using fuzz.ratio Parameters ---------- s1 : str First string to compare. s2 : str Second string to compare. processor: callable, optional Optional callable that is used to preprocess the strings before comparing them. Default is None, which deactivates this behaviour. score_cutoff : float, optional Optional argument for a score threshold as a float between 0 and 100. For ratio < score_cutoff 0 is returned instead. Default is 0, which deactivates this behaviour. Returns ------- similarity : float similarity between s1 and s2 as a float between 0 and 100 Notes ----- .. image:: img/token_set_ratio.svg Examples -------- >>> fuzz.token_sort_ratio("fuzzy was a bear", "fuzzy fuzzy was a bear") 83.8709716796875 >>> fuzz.token_set_ratio("fuzzy was a bear", "fuzzy fuzzy was a bear") 100.0 # Returns 100.0 if one string is a subset of the other, regardless of extra content in the longer string >>> fuzz.token_set_ratio("fuzzy was a bear but not a dog", "fuzzy was a bear") 100.0 # Score is reduced only when there is explicit disagreement in the two strings >>> fuzz.token_set_ratio("fuzzy was a bear but not a dog", "fuzzy was a bear but not a cat") 92.3076923076923 """ setupPandas() if is_none(s1) or is_none(s2): return 0 if processor is not None: s1 = processor(s1) s2 = processor(s2) if score_cutoff is None: score_cutoff = 0 s1, s2 = conv_sequences(s1, s2) tokens_a = set(_split_sequence(s1)) tokens_b = set(_split_sequence(s2)) # in FuzzyWuzzy this returns 0. For sake of compatibility return 0 here as well # see https://github.com/rapidfuzz/RapidFuzz/issues/110 if not tokens_a or not tokens_b: return 0 intersect = tokens_a.intersection(tokens_b) diff_ab = tokens_a.difference(tokens_b) diff_ba = tokens_b.difference(tokens_a) # one sentence is part of the other one if intersect and (not diff_ab or not diff_ba): return 100 diff_ab_joined = _join_splitted_sequence(sorted(diff_ab)) diff_ba_joined = _join_splitted_sequence(sorted(diff_ba)) ab_len = len(diff_ab_joined) ba_len = len(diff_ba_joined) # todo is length sum without joining faster? sect_len = len(_join_splitted_sequence(intersect)) # string length sect+ab <-> sect and sect+ba <-> sect sect_ab_len = sect_len + (sect_len != 0) + ab_len sect_ba_len = sect_len + (sect_len != 0) + ba_len result = 0.0 cutoff_distance = ceil((sect_ab_len + sect_ba_len) * (1 - score_cutoff / 100)) dist = indel_distance(diff_ab_joined, diff_ba_joined, score_cutoff=cutoff_distance) if dist <= cutoff_distance: result = _norm_distance(dist, sect_ab_len + sect_ba_len, score_cutoff) # exit early since the other ratios are 0 if not sect_len: return result # levenshtein distance sect+ab <-> sect and sect+ba <-> sect # since only sect is similar in them the distance can be calculated based on # the length difference sect_ab_dist = (sect_len != 0) + ab_len sect_ab_ratio = _norm_distance(sect_ab_dist, sect_len + sect_ab_len, score_cutoff) sect_ba_dist = (sect_len != 0) + ba_len sect_ba_ratio = _norm_distance(sect_ba_dist, sect_len + sect_ba_len, score_cutoff) return max(result, sect_ab_ratio, sect_ba_ratio) def token_ratio( s1, s2, *, processor=None, score_cutoff=None, ): """ Helper method that returns the maximum of fuzz.token_set_ratio and fuzz.token_sort_ratio (faster than manually executing the two functions) Parameters ---------- s1 : str First string to compare. s2 : str Second string to compare. processor: callable, optional Optional callable that is used to preprocess the strings before comparing them. Default is None, which deactivates this behaviour. score_cutoff : float, optional Optional argument for a score threshold as a float between 0 and 100. For ratio < score_cutoff 0 is returned instead. Default is 0, which deactivates this behaviour. Returns ------- similarity : float similarity between s1 and s2 as a float between 0 and 100 Notes ----- .. image:: img/token_ratio.svg """ setupPandas() if is_none(s1) or is_none(s2): return 0 if processor is not None: s1 = processor(s1) s2 = processor(s2) # todo write combined implementation return max( token_set_ratio(s1, s2, processor=None, score_cutoff=score_cutoff), token_sort_ratio(s1, s2, processor=None, score_cutoff=score_cutoff), ) def partial_token_sort_ratio( s1, s2, *, processor=None, score_cutoff=None, ): """ sorts the words in the strings and calculates the fuzz.partial_ratio between them Parameters ---------- s1 : str First string to compare. s2 : str Second string to compare. processor: callable, optional Optional callable that is used to preprocess the strings before comparing them. Default is None, which deactivates this behaviour. score_cutoff : float, optional Optional argument for a score threshold as a float between 0 and 100. For ratio < score_cutoff 0 is returned instead. Default is 0, which deactivates this behaviour. Returns ------- similarity : float similarity between s1 and s2 as a float between 0 and 100 Notes ----- .. image:: img/partial_token_sort_ratio.svg """ setupPandas() if is_none(s1) or is_none(s2): return 0 if processor is not None: s1 = processor(s1) s2 = processor(s2) s1, s2 = conv_sequences(s1, s2) sorted_s1 = _join_splitted_sequence(sorted(_split_sequence(s1))) sorted_s2 = _join_splitted_sequence(sorted(_split_sequence(s2))) return partial_ratio(sorted_s1, sorted_s2, score_cutoff=score_cutoff) def partial_token_set_ratio( s1, s2, *, processor=None, score_cutoff=None, ): """ Compares the words in the strings based on unique and common words between them using fuzz.partial_ratio Parameters ---------- s1 : str First string to compare. s2 : str Second string to compare. processor: callable, optional Optional callable that is used to preprocess the strings before comparing them. Default is None, which deactivates this behaviour. score_cutoff : float, optional Optional argument for a score threshold as a float between 0 and 100. For ratio < score_cutoff 0 is returned instead. Default is 0, which deactivates this behaviour. Returns ------- similarity : float similarity between s1 and s2 as a float between 0 and 100 Notes ----- .. image:: img/partial_token_set_ratio.svg """ setupPandas() if is_none(s1) or is_none(s2): return 0 if processor is not None: s1 = processor(s1) s2 = processor(s2) s1, s2 = conv_sequences(s1, s2) tokens_a = set(_split_sequence(s1)) tokens_b = set(_split_sequence(s2)) # in FuzzyWuzzy this returns 0. For sake of compatibility return 0 here as well # see https://github.com/rapidfuzz/RapidFuzz/issues/110 if not tokens_a or not tokens_b: return 0 # exit early when there is a common word in both sequences if tokens_a.intersection(tokens_b): return 100 diff_ab = _join_splitted_sequence(sorted(tokens_a.difference(tokens_b))) diff_ba = _join_splitted_sequence(sorted(tokens_b.difference(tokens_a))) return partial_ratio(diff_ab, diff_ba, score_cutoff=score_cutoff) def partial_token_ratio( s1, s2, *, processor=None, score_cutoff=None, ): """ Helper method that returns the maximum of fuzz.partial_token_set_ratio and fuzz.partial_token_sort_ratio (faster than manually executing the two functions) Parameters ---------- s1 : str First string to compare. s2 : str Second string to compare. processor: callable, optional Optional callable that is used to preprocess the strings before comparing them. Default is None, which deactivates this behaviour. score_cutoff : float, optional Optional argument for a score threshold as a float between 0 and 100. For ratio < score_cutoff 0 is returned instead. Default is 0, which deactivates this behaviour. Returns ------- similarity : float similarity between s1 and s2 as a float between 0 and 100 Notes ----- .. image:: img/partial_token_ratio.svg """ setupPandas() if is_none(s1) or is_none(s2): return 0 if processor is not None: s1 = processor(s1) s2 = processor(s2) if score_cutoff is None: score_cutoff = 0 s1, s2 = conv_sequences(s1, s2) tokens_split_a = _split_sequence(s1) tokens_split_b = _split_sequence(s2) tokens_a = set(tokens_split_a) tokens_b = set(tokens_split_b) # exit early when there is a common word in both sequences if tokens_a.intersection(tokens_b): return 100 diff_ab = tokens_a.difference(tokens_b) diff_ba = tokens_b.difference(tokens_a) result = partial_ratio( _join_splitted_sequence(sorted(tokens_split_a)), _join_splitted_sequence(sorted(tokens_split_b)), score_cutoff=score_cutoff, ) # do not calculate the same partial_ratio twice if len(tokens_split_a) == len(diff_ab) and len(tokens_split_b) == len(diff_ba): return result score_cutoff = max(score_cutoff, result) return max( result, partial_ratio( _join_splitted_sequence(sorted(diff_ab)), _join_splitted_sequence(sorted(diff_ba)), score_cutoff=score_cutoff, ), ) def WRatio( s1, s2, *, processor=None, score_cutoff=None, ): """ Calculates a weighted ratio based on the other ratio algorithms Parameters ---------- s1 : str First string to compare. s2 : str Second string to compare. processor: callable, optional Optional callable that is used to preprocess the strings before comparing them. Default is None, which deactivates this behaviour. score_cutoff : float, optional Optional argument for a score threshold as a float between 0 and 100. For ratio < score_cutoff 0 is returned instead. Default is 0, which deactivates this behaviour. Returns ------- similarity : float similarity between s1 and s2 as a float between 0 and 100 Notes ----- .. image:: img/WRatio.svg """ setupPandas() if is_none(s1) or is_none(s2): return 0 UNBASE_SCALE = 0.95 if processor is not None: s1 = processor(s1) s2 = processor(s2) # in FuzzyWuzzy this returns 0. For sake of compatibility return 0 here as well # see https://github.com/rapidfuzz/RapidFuzz/issues/110 if not s1 or not s2: return 0 if score_cutoff is None: score_cutoff = 0 len1 = len(s1) len2 = len(s2) len_ratio = len1 / len2 if len1 > len2 else len2 / len1 end_ratio = ratio(s1, s2, score_cutoff=score_cutoff) if len_ratio < 1.5: score_cutoff = max(score_cutoff, end_ratio) / UNBASE_SCALE return max( end_ratio, token_ratio(s1, s2, score_cutoff=score_cutoff, processor=None) * UNBASE_SCALE, ) PARTIAL_SCALE = 0.9 if len_ratio < 8.0 else 0.6 score_cutoff = max(score_cutoff, end_ratio) / PARTIAL_SCALE end_ratio = max(end_ratio, partial_ratio(s1, s2, score_cutoff=score_cutoff) * PARTIAL_SCALE) score_cutoff = max(score_cutoff, end_ratio) / UNBASE_SCALE return max( end_ratio, partial_token_ratio(s1, s2, score_cutoff=score_cutoff, processor=None) * UNBASE_SCALE * PARTIAL_SCALE, ) def QRatio( s1, s2, *, processor=None, score_cutoff=None, ): """ Calculates a quick ratio between two strings using fuzz.ratio. Since v3.0 this behaves similar to fuzz.ratio with the exception that this returns 0 when comparing two empty strings Parameters ---------- s1 : Sequence[Hashable] First string to compare. s2 : Sequence[Hashable] Second string to compare. processor: callable, optional Optional callable that is used to preprocess the strings before comparing them. Default is None, which deactivates this behaviour. score_cutoff : float, optional Optional argument for a score threshold as a float between 0 and 100. For ratio < score_cutoff 0 is returned instead. Default is 0, which deactivates this behaviour. Returns ------- similarity : float similarity between s1 and s2 as a float between 0 and 100 Examples -------- >>> fuzz.QRatio("this is a test", "this is a test!") 96.55171966552734 """ setupPandas() if is_none(s1) or is_none(s2): return 0 if processor is not None: s1 = processor(s1) s2 = processor(s2) # in FuzzyWuzzy this returns 0. For sake of compatibility return 0 here as well # see https://github.com/rapidfuzz/RapidFuzz/issues/110 if not s1 or not s2: return 0 return ratio(s1, s2, score_cutoff=score_cutoff) add_scorer_attrs(ratio, fuzz_attribute) add_scorer_attrs(partial_ratio, fuzz_attribute) add_scorer_attrs(token_sort_ratio, fuzz_attribute) add_scorer_attrs(token_set_ratio, fuzz_attribute) add_scorer_attrs(token_ratio, fuzz_attribute) add_scorer_attrs(partial_token_sort_ratio, fuzz_attribute) add_scorer_attrs(partial_token_set_ratio, fuzz_attribute) add_scorer_attrs(partial_token_ratio, fuzz_attribute) add_scorer_attrs(WRatio, fuzz_attribute) add_scorer_attrs(QRatio, fuzz_attribute)