Fuzzy Sequence Matcher
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.
Free software: MIT license
Documentation: https://fuzzy-sequence-matcher.readthedocs.io.
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.
Metadata
Release files for fuzzy-sequence-matcher 0.1.1
For a detailed explanation of source distributions (sdists) and built distributions (wheels), please see the package formats documentation.
Source distribution (sdist)
| File | Size | Uploaded | Provenance | Actions |
|---|---|---|---|---|
| fuzzy_sequence_matcher-0.1.1.tar.gz | 13.7 kB | Without provenance | Details for fuzzy_sequence_matcher-0.1.1.tar.gz |
Built distribution (wheel)
| File | Interpreter | ABI | Platform | Actions Reset |
|---|---|---|---|---|
| fuzzy_sequence_matcher-0.1.1-py2.py3-none-any.whl | Python 2, Python 3 | none | any | Details for fuzzy_sequence_matcher-0.1.1-py2.py3-none-any.whl |
Total release size: 20.1 kB
Release files / fuzzy_sequence_matcher-0.1.1.tar.gz
| Download URL | fuzzy_sequence_matcher-0.1.1.tar.gz |
|---|---|
| Size | 13.7 kB |
| Tags | Source |
|
SHA-256 checksum How to use checksums |
c386a12999d98448acd5e8bf4b9632d4f15bba9419fca842cc4189b7a562674b
|
|
BLAKE2b-256 checksum How to use checksums |
67da753340e647b460adcdd3e4e721386ef32f64a0a9d1f9c2c2e93034296348
|
| Upload date | |
|
Uploaded using Trusted Publishing? What is trusted publishing? |
No |
| Uploaded via |
twine/3.1.1 pkginfo/1.5.0.1 requests/2.22.0 setuptools/41.2.0 requests-toolbelt/0.9.1 tqdm/4.40.2 CPython/3.8.0
|
Release files / fuzzy_sequence_matcher-0.1.1-py2.py3-none-any.whl
| Download URL | fuzzy_sequence_matcher-0.1.1-py2.py3-none-any.whl |
|---|---|
| Size | 6.5 kB |
| Tags | Python 2 Python 3 |
|
SHA-256 checksum How to use checksums |
c425b44e54fec2f6abae3acbbcae11bb7fc27361a1f183d4515b4c67411900a5
|
|
BLAKE2b-256 checksum How to use checksums |
00ed14f1224684296db00ac309330c98c76f73fe920c6c6bb8356e44bdd7c470
|
| Upload date | |
|
Uploaded using Trusted Publishing? What is trusted publishing? |
No |
| Uploaded via |
twine/3.1.1 pkginfo/1.5.0.1 requests/2.22.0 setuptools/41.2.0 requests-toolbelt/0.9.1 tqdm/4.40.2 CPython/3.8.0
|
Security for fuzzy-sequence-matcher 0.1.1
Provenance
Provenance describes where a file came from. On PyPI, provenance is shared via attestations, which provide a verifiable record of the build or publishing details. View details, limitations and caveats.
No provenance found
None of the files in this release were uploaded with provenance metadata.
A note on package security
PyPI is a repository for distributing packages, not a service for auditing them. While third-party security researchers and our staff do their best to detect and remove malicious packages, PyPI cannot guarantee the quality, security or suitability of any given package.
To learn more about protecting yourself from malicious actors, visit our package security documentation.