Skip to main content

Finds best pairings of elements between two sequences

Project description

Fuzzy Sequence Matcher

https://img.shields.io/pypi/v/fuzzy_sequence_matcher.svg https://img.shields.io/travis/catherinedevlin/fuzzy_sequence_matcher.svg Documentation Status

Purpose

Finds best pairings of elements between two sequences.

Each element can only be used at most once, and the order of elements is preserved. That is, if X1 -> Y2, then X2 cannot match to Y1 or Y2; it must match to Y3 or later. This is appropriate for sequences where Y is a garbled or mutated copy of X.

Example

>>> from fuzzy_sequence_matcher.fuzzy_sequence_matcher import best_matches
>>> from jellyfish import jaro_distance
>>> declaration = "We hold these truths to be self evident".split()
>>> degradation = ("I guess wee hold them tooths and stuff "
...     "for being sort of evidence, y'know?").split()
>>> best_matches(declaration, degradation, scorer=jaro_distance)
[('We', 'wee'), ('hold', 'hold'), ('these', 'them'), ('truths', 'tooths'), ('to', 'for'), ('be', 'being'), ('self', 'sort'), ('evident', 'evidence,')]

Features

  • Match any objects you can write a scoring function for
  • No dependencies outside standard library

Scoring function

The matching is done with a scoring function you specify. It should look something like:

def score(element_from_seq1: Any, element_from_seq2: Any) -> float

with high scores indicating better matches.

For comparing strings, you might use jellyfish.jaro_distance. For comparing numbers, -abs(n1 - n2) works.

threshold

By default, fuzzy_sequence_matcher finds the combination that maximizes the sum scores of all the pairings. However, when one sequence is much longer than the other, the number of possible combinations grows impractically large to try them all. The itertools documentation gives the number of combinations as

len(Y)! / len(X)! / (len(Y) - len(X))!

when len(Y) >= len(X).

This function is exposed as fuzzy_sequence_matcher.n_combinations.

If the number of possible combinations exceeds a threshold - by default, 1_000_000, which happens when the long seq is ~ 15 or more elements longer than the short - then elements from the longer sequence will be dropped from consideration entirely, starting with those whose best match to the shorter sequence is worst, until n_combinations is under the threshold. This could conceivably give a result that is not the ideal-scoring set of matches.

Credits

This package was created with Cookiecutter and the audreyr/cookiecutter-pypackage project template.

Thanks to Dayton Dynamic Languages for advice and brainstorming

History

0.1.0 (2019-12-14)

  • First release on PyPI.

0.1.1 (2019-12-26)

  • Allow scorers that handle the arguments differently.

Project details


Download files

Download the file for your platform. If you're not sure which to choose, learn more about installing packages.

Files for fuzzy-sequence-matcher, version 0.1.1
Filename, size File type Python version Upload date Hashes
Filename, size fuzzy_sequence_matcher-0.1.1-py2.py3-none-any.whl (6.5 kB) File type Wheel Python version py2.py3 Upload date Hashes View hashes
Filename, size fuzzy_sequence_matcher-0.1.1.tar.gz (13.7 kB) File type Source Python version None Upload date Hashes View hashes

Supported by

Elastic Elastic Search Pingdom Pingdom Monitoring Google Google BigQuery Sentry Sentry Error logging AWS AWS Cloud computing DataDog DataDog Monitoring Fastly Fastly CDN DigiCert DigiCert EV certificate StatusPage StatusPage Status page