Author Dennis Sweeney
Recipients BTaskaya, Dennis Sweeney, aroberge, james, pablogsal, serhiy.storchaka, vstinner, xtreak, yselivanov
Date 2021-05-01.10:10:05
SpamBayes Score -1.0
Marked as misclassified Yes
Message-id <1619863806.25.0.758600181114.issue38530@roundup.psfhosted.org>
In-reply-to
Content
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.
History
Date User Action Args
2021-05-01 10:10:06Dennis Sweeneysetrecipients: + Dennis Sweeney, vstinner, aroberge, serhiy.storchaka, yselivanov, james, pablogsal, xtreak, BTaskaya
2021-05-01 10:10:06Dennis Sweeneysetmessageid: <1619863806.25.0.758600181114.issue38530@roundup.psfhosted.org>
2021-05-01 10:10:06Dennis Sweeneylinkissue38530 messages
2021-05-01 10:10:05Dennis Sweeneycreate