The implementation used by rapidfuzz has the following algorithms

• Jaro/JaroWinkler (fastest by a large margin)
• Hamming (slightly slower than python-Levenshtein)
• Levenshtein (similar fast to python-Levenshtein for very short strings and fastest for longer strings)

Additionally it supports any sequence of hashable types (e.g. lists of strings) and not only text

Here is the benchmark result:

# Faster than textdistance:

| algorithm          | library                 | function                     |        time |
|--------------------+-------------------------+------------------------------+-------------|
| DamerauLevenshtein | jellyfish               | damerau_levenshtein_distance | 0.0181046   |
| DamerauLevenshtein | pyxdameraulevenshtein   | damerau_levenshtein_distance | 0.030925    |
| Hamming            | Levenshtein             | hamming                      | 0.000351586 |
| Hamming            | rapidfuzz.string_metric | hamming                      | 0.00040442  |
| Hamming            | jellyfish               | hamming_distance             | 0.0143502   |
| Jaro               | rapidfuzz.string_metric | jaro_similarity              | 0.000749048 |
| Jaro               | jellyfish               | jaro_similarity              | 0.0152322   |
| JaroWinkler        | rapidfuzz.string_metric | jaro_winkler_similarity      | 0.000776006 |
| JaroWinkler        | jellyfish               | jaro_winkler_similarity      | 0.0157833   |
| Levenshtein        | rapidfuzz.string_metric | levenshtein                  | 0.0010058   |
| Levenshtein        | Levenshtein             | distance                     | 0.00103176  |
| Levenshtein        | jellyfish               | levenshtein_distance         | 0.0147382   |
| Levenshtein        | pylev                   | levenshtein                  | 0.14116     |
Total: 13 libs.

and the benchmark results when adding slightly longer strings:

STMT = """
func('text', 'test')
func('qwer', 'asdf')
func('a' * 15, 'b' * 15)
func('a' * 30, 'b' * 30)
"""

# Faster than textdistance:

| algorithm          | library                 | function                     |        time |
|--------------------+-------------------------+------------------------------+-------------|
| DamerauLevenshtein | jellyfish               | damerau_levenshtein_distance | 0.0323887   |
| DamerauLevenshtein | pyxdameraulevenshtein   | damerau_levenshtein_distance | 0.143235    |
| Hamming            | Levenshtein             | hamming                      | 0.000489837 |
| Hamming            | rapidfuzz.string_metric | hamming                      | 0.000517879 |
| Hamming            | jellyfish               | hamming_distance             | 0.0182341   |
| Jaro               | rapidfuzz.string_metric | jaro_similarity              | 0.00111363  |
| Jaro               | jellyfish               | jaro_similarity              | 0.0201971   |
| JaroWinkler        | rapidfuzz.string_metric | jaro_winkler_similarity      | 0.00105238  |
| JaroWinkler        | jellyfish               | jaro_winkler_similarity      | 0.0206678   |
| Levenshtein        | rapidfuzz.string_metric | levenshtein                  | 0.00138601  |
| Levenshtein        | Levenshtein             | distance                     | 0.0034889   |
| Levenshtein        | jellyfish               | levenshtein_distance         | 0.0232467   |
| Levenshtein        | pylev                   | levenshtein                  | 0.599603    |
Total: 13 libs.

There are two versions of the Damerau-Levenshtein distance, as described in this Debian bug report: https://bugs.debian.org/cgi-bin/bugreport.cgi?bug=1018933 Some of the external libraries implement one of them, others the other.

This PR splits introduces two different classes: DamerauLevenshteinRestricted and DamerauLevenshteinUnrestricted, with DamerauLevenshtein being the unrestricted version, so that it is clear what is intended.

Two particular tests have timings that differ wildly between successive runs on arm64 architectures. This might be because some libraries take a long time to load or something like that - I don't know. But this patch turns off hypothesis's timing checks for these two tests. I'm going to apply it to Debian's package; you might or might not want to apply it upstream.

Jellyfish has recently modified its JaroWinkler algorithm to allow for boosting even when one of the strings is shorter than 4 characters: https://github.com/jamesturk/jellyfish/commit/87f9679910eba0dad6a1f6019f03cbdffba28392. It is very unclear whether this is a good idea or not. But as it is, the tests now fail, as the internal and external algorithms give different results on a pair of strings such as ":" and ":0".

This patch replicates the change that jellyfish has made, which will then allow the external tests to pass once again. It also modifies the expected value of the comparison "fog" and "frog" to match this new algorithm behaviour.

If you do not wish to apply this patch, then the external tests will need modifying to exclude the case where either of the strings has length < 4.

Might be wrong about this, but think the code for the Monge-Elkan algorithm needs to be corrected.

If you look at the implementation in the py_stringmatching library on line 81 of https://github.com/anhaidgroup/py_stringmatching/blob/master/py_stringmatching/similarity_measure/monge_elkan.py sim = float(sum_of_maxes) / float(len(bag1)) which is essentially the mean max.

But in the implementation for textdistance, the score is given on line 222 of https://github.com/life4/textdistance/blob/master/textdistance/algorithms/token_based.py as
sum(maxes) / len(seq) / len(maxes)

I think the further division by len(maxes) isn't needed, and the line should just be sum(maxes) / len(seq)

The change in the code could mess up tests elsewhere, so I'm not changing anything else. But thought I should bring this to your attention.

Below is some code and differing scores I got in textdistance and py_stringmatching.

# score in textdistance
from textdistance import MongeElkan, levenshtein
ALG = MongeElkan
score = ALG(algorithm=levenshtein,qval=None,symmetric=False).similarity('Good Times!', "The Good Times and The Bad Ones")
score
# Got 2.25

#score in py_stringmatching
from py_stringmatching import MongeElkan
from py_stringmatching import Levenshtein as Levenshtein_2
ALG_2 = MongeElkan(sim_func=Levenshtein_2().get_raw_score)
source = 'Good Times!'
source_split = source.split()
target = "The Good Times and The Bad Ones"
target_split = target.split()
score2 = ALG_2.get_raw_score(source_split, target_split)
score2
# got 5.5

abydos has changed its interface for distance metrics quite significantly, and jellyfish has changed the names of the functions. This patch addresses both of these issues.

textdistance is currently failing its test-suite on arm64 machines with Python 3.10, which is causing me problems on Debian. I have managed to track down the first of these bugs (and there are at least two more to come): there are some algorithms that use upper() before comparing the strings. As noted in the code already, though these algorithms were designed for English (ASCII only), this can cause upper() to change the length of the string if using non-English characters. And hypothesis does this when testing. This can result in the normalised distance being greater than 1. This patch addresses this by ensuring that the distance returned from the relevant algorithms is no greater than self.maximum().

A second issue which arose when doing this was calculating the maximum distance for Editex(); the current function for calculating the maximum does not give the correct answer if match_cost > mismatch_cost, for example. But this would be a silly situation: why would we penalise matching characters more than mismatching ones? There are two ways of resolving this: the first is to calculate the maximum distance using max(match_cost, group_cost, mismatch_cost), the second is to force the inequalities match_cost <= group_cost <= mismatch_cost. I have gone for the latter option in this patch.

All being well, there will be more patches to come in the next few weeks as I get to the bottom of them!

update rapidfuzz to the latest version which provides a damerau levenshtein implementation. It is the fastest of the supported libraries:

| algorithm          | library                               | function                     |        time |
|--------------------+---------------------------------------+------------------------------+-------------|
| DamerauLevenshtein | rapidfuzz.distance.DamerauLevenshtein | distance                     | 0.00267046  |
| DamerauLevenshtein | jellyfish                             | damerau_levenshtein_distance | 0.022479    |
| DamerauLevenshtein | pyxdameraulevenshtein                 | damerau_levenshtein_distance | 0.0393475   |
| DamerauLevenshtein | **textdistance**                      | DamerauLevenshtein           | 0.589098    |

In addition it is the only implementation which only requires linear memory.

Basic types have been deprecated in numpy 1.20. Here are the full warnings:

DeprecationWarning: `np.int` is a deprecated alias for the builtin `int`. To silence this warning, use `int` by itself. Doing this will not modify any behavior and is safe. When replacing `np.int`, you may wish to use e.g. `np.int64` or `np.int32` to specify the precision. If you wish to review your current use, check the release note link for additional information.
  Deprecated in NumPy 1.20; for more details and guidance: https://numpy.org/devdocs/release/1.20.0-notes.html#deprecations

DeprecationWarning: `np.float` is a deprecated alias for the builtin `float`. To silence this warning, use `float` by itself. Doing this will not modify any behavior and is safe. If you specifically wanted the numpy scalar type, use `np.float64` here.
  Deprecated in NumPy 1.20; for more details and guidance: https://numpy.org/devdocs/release/1.20.0-notes.html#deprecations

I don’t know the code enough to assess if the specific numpy types are required though.

UserWarning: Usage of dash-separated 'description-file' will not be supported in future versions. Please use the underscore name 'description_file' instead

Hi,

Noticed that the Travis CI link was wrong. Then found a few more links that appear to reference an old repository.

This PR tries to correct the links by replacing orsinium by life4 in some URL's.

And thanks for the great project, Bruno