allowing transpositions reduces the number of edits required with transpositions e g abc t cba d ca 2 steps without transpositions e g abc d ab d a i ca 3 steps note a substitioncost of higher than 2 doesn t make much sense as a deletion insertion is identical and always costs 2 transpositions don t always reduce the number of edits required with or without transpositions e g wants d wats d was i wasp 3 steps ought to have the same results with and without transpositions with or without transpositions e g rain s sain s shin i shine 3 steps but cost 5 if substitutioncost2 several potentially interesting typos with transpositions e g acbdef t abcdef 1 step without transpositions e g acbdef d abdef i abcdef 2 steps with transpositions e g lnaguaeg t languaeg t language 2 steps without transpositions e g lnaguaeg d laguaeg i languaeg d languag i language 4 steps with transpositions e g lnaugage t lanugage t language 2 steps without transpositions e g lnaugage s lnangage d langage i language 3 steps but one substitution so a cost of 4 if substitioncost 2 does require substitutions if no transpositions with transpositions e g lngauage t lnaguage t language 2 steps without transpositions e g lngauage i lanaguage d language 2 steps with or without transpositions e g wants s sants s swnts s swits s swims d swim 5 steps with substitutioncost2 and transpositions e g wants t santw d sntw d stw d sw i swi i swim 6 steps with substitutioncost2 and no transpositions e g wants i swants d swant d swan d swa d sw i swi i swim 7 steps with or without transpositions e g kitten s sitten s sittin i sitting 3 steps but cost 5 if substitutioncost2 duplicated letter e g duplicated d duplicated test editdistance between two strings given some substitutioncost and whether transpositions are allowed param str left first input string to editdistance param str right second input string to editdistance param int substitutioncost the cost of a substitution action in editdistance param tupleint int expecteds a tuple of expected outputs such that expecteds0 is the expected output with transpositionstrue and expecteds1 is the expected output with transpositionsfalse test the input strings in both orderings zip with true false to get the transpositions value allowing transpositions reduces the number of edits required with transpositions e g abc t cba d ca 2 steps without transpositions e g abc d ab d a i ca 3 steps doesn t require substitutions note a substition_cost of higher than 2 doesn t make much sense as a deletion insertion is identical and always costs 2 transpositions don t always reduce the number of edits required with or without transpositions e g wants d wats d was i wasp 3 steps doesn t require substitutions ought to have the same results with and without transpositions with or without transpositions e g rain s sain s shin i shine 3 steps but cost 5 if substitution_cost 2 does require substitutions several potentially interesting typos with transpositions e g acbdef t abcdef 1 step without transpositions e g acbdef d abdef i abcdef 2 steps doesn t require substitutions with transpositions e g lnaguaeg t languaeg t language 2 steps without transpositions e g lnaguaeg d laguaeg i languaeg d languag i language 4 steps doesn t require substitutions with transpositions e g lnaugage t lanugage t language 2 steps without transpositions e g lnaugage s lnangage d langage i language 3 steps but one substitution so a cost of 4 if substition_cost 2 does require substitutions if no transpositions with transpositions e g lngauage t lnaguage t language 2 steps without transpositions e g lngauage i lanaguage d language 2 steps doesn t require substitutions with or without transpositions e g wants s sants s swnts s swits s swims d swim 5 steps with substitution_cost 2 and transpositions e g wants t santw d sntw d stw d sw i swi i swim 6 steps with substitution_cost 2 and no transpositions e g wants i swants d swant d swan d swa d sw i swi i swim 7 steps with or without transpositions e g kitten s sitten s sittin i sitting 3 steps but cost 5 if substitution_cost 2 duplicated letter e g duplicated d duplicated test edit_distance between two strings given some substitution_cost and whether transpositions are allowed param str left first input string to edit_distance param str right second input string to edit_distance param int substitution_cost the cost of a substitution action in edit_distance param tuple int int expecteds a tuple of expected outputs such that expecteds 0 is the expected output with transpositions true and expecteds 1 is the expected output with transpositions false test the input strings in both orderings zip with true false to get the transpositions value
from typing import Tuple

import pytest

from nltk.metrics.distance import edit_distance


class TestEditDistance:
    @pytest.mark.parametrize(
        "left,right,substitution_cost,expecteds",
        [
            
            
            
            
            
            
            ("abc", "ca", 1, (2, 3)),
            ("abc", "ca", 5, (2, 3)),  
            
            
            
            
            
            
            
            
            ("wants", "wasp", 1, (3, 3)),
            ("wants", "wasp", 5, (3, 3)),  
            
            
            
            
            
            
            ("rain", "shine", 1, (3, 3)),
            ("rain", "shine", 2, (5, 5)),  
            
            
            
            
            
            
            
            
            ("acbdef", "abcdef", 1, (1, 2)),
            ("acbdef", "abcdef", 2, (1, 2)),  
            
            
            
            
            
            
            
            ("lnaguaeg", "language", 1, (2, 4)),
            ("lnaguaeg", "language", 2, (2, 4)),  
            
            
            
            
            
            
            
            
            ("lnaugage", "language", 1, (2, 3)),
            ("lnaugage", "language", 2, (2, 4)),
            
            
            
            
            
            
            
            ("lngauage", "language", 1, (2, 2)),
            ("lngauage", "language", 2, (2, 2)),  
            
            
            
            
            
            
            
            
            
            
            
            
            ("wants", "swim", 1, (5, 5)),
            ("wants", "swim", 2, (6, 7)),
            
            
            
            
            
            ("kitten", "sitting", 1, (3, 3)),
            ("kitten", "sitting", 2, (5, 5)),
            
            
            
            ("duplicated", "duuplicated", 1, (1, 1)),
            ("duplicated", "duuplicated", 2, (1, 1)),
            ("very duplicated", "very duuplicateed", 2, (2, 2)),
        ],
    )
    def test_with_transpositions(
        self, left: str, right: str, substitution_cost: int, expecteds: Tuple[int, int]
    ):
        
        
        for s1, s2 in ((left, right), (right, left)):
            
            for expected, transpositions in zip(expecteds, [True, False]):
                predicted = edit_distance(
                    s1,
                    s2,
                    substitution_cost=substitution_cost,
                    transpositions=transpositions,
                )
                assert predicted == expected