Dennis Sweeney <[email protected]> added the comment:
PR 25776 is a work in progress for what it might look like to do a few things:
- Make case-swaps half the cost of any other edit
- Refactor Levenshtein code to not use memory allocator, and to bail early on
no match.
- Add comments to Levenshtein distance code
- Add test cases for Levenshtein distance behind a debug macro
- Set threshold to (name_size + item_size + 3) * MOVE_COST / 6.
- Reasoning: similar to difflib.SequenceMatcher.ratio() >= 2/3:
"Multiset Jaccard similarity" >= 2/3
matching letters / total letters >= 2/3
(name_size - distance + item_size - distance) / (name_size + item_size)
>= 2/3
1 - (2*distance) / (name_size + item_size) >= 2/3
1/3 >= (2*distance) / (name_size + item_size)
(name_size + item_size) / 6 >= distance
With rounding:
(name_size + item_size + 3) // 6 >= distance
Re: Damerau-Levenshtein (transpositions as single edits), if that were to get
implemented, I don't see a way to do that without using a buffer of at least 3x
the size, storing the most recent 3 rows of the matrix.
----------
_______________________________________
Python tracker <[email protected]>
<https://bugs.python.org/issue38530>
_______________________________________
_______________________________________________
Python-bugs-list mailing list
Unsubscribe:
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
