Python/strings/levenshtein_distance.py at master · manmita/Python · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
"""
This is a Python implementation of the levenshtein distance.
Levenshtein distance is a string metric for measuring the
difference between two sequences.

For doctests run following command:
python -m doctest -v levenshtein-distance.py
or
python3 -m doctest -v levenshtein-distance.py

For manual testing run:
python levenshtein-distance.py
"""


deflevenshtein_distance(first_word: str, second_word: str) ->int:
"""Implementation of the levenshtein distance in Python.
 :param first_word: the first word to measure the difference.
 :param second_word: the second word to measure the difference.
 :return: the levenshtein distance between the two words.
 Examples:
 >>> levenshtein_distance("planet", "planetary")
 3
 >>> levenshtein_distance("", "test")
 4
 >>> levenshtein_distance("book", "back")
 2
 >>> levenshtein_distance("book", "book")
 0
 >>> levenshtein_distance("test", "")
 4
 >>> levenshtein_distance("", "")
 0
 >>> levenshtein_distance("orchestration", "container")
 10
 """
# The longer word should come first
iflen(first_word) <len(second_word):
returnlevenshtein_distance(second_word, first_word)

iflen(second_word) ==0:
returnlen(first_word)

previous_row=list(range(len(second_word) +1))

fori, c1inenumerate(first_word):
current_row= [i+1]

forj, c2inenumerate(second_word):
# Calculate insertions, deletions and substitutions
insertions=previous_row[j+1] +1
deletions=current_row[j] +1
substitutions=previous_row[j] + (c1!=c2)

# Get the minimum to append to the current row
current_row.append(min(insertions, deletions, substitutions))

# Store the previous row
previous_row=current_row

# Returns the last element (distance)
returnprevious_row[-1]


if__name__=="__main__":
first_word=input("Enter the first word:\n").strip()
second_word=input("Enter the second word:\n").strip()

result=levenshtein_distance(first_word, second_word)
print(f"Levenshtein distance between {first_word} and {second_word} is {result}")
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
"""
This is a Python implementation of the levenshtein distance.
Levenshtein distance is a string metric for measuring the
difference between two sequences.

For doctests run following command:
python -m doctest -v levenshtein-distance.py
or
python3 -m doctest -v levenshtein-distance.py

For manual testing run:
python levenshtein-distance.py
"""


deflevenshtein_distance(first_word: str, second_word: str) ->int:
"""Implementation of the levenshtein distance in Python.
 :param first_word: the first word to measure the difference.
 :param second_word: the second word to measure the difference.
 :return: the levenshtein distance between the two words.
 Examples:
 >>> levenshtein_distance("planet", "planetary")
 3
 >>> levenshtein_distance("", "test")
 4
 >>> levenshtein_distance("book", "back")
 2
 >>> levenshtein_distance("book", "book")
 0
 >>> levenshtein_distance("test", "")
 4
 >>> levenshtein_distance("", "")
 0
 >>> levenshtein_distance("orchestration", "container")
 10
 """
# The longer word should come first
iflen(first_word) <len(second_word):
returnlevenshtein_distance(second_word, first_word)

iflen(second_word) ==0:
returnlen(first_word)

previous_row=list(range(len(second_word) +1))

fori, c1inenumerate(first_word):
current_row= [i+1]

forj, c2inenumerate(second_word):
# Calculate insertions, deletions and substitutions
insertions=previous_row[j+1] +1
deletions=current_row[j] +1
substitutions=previous_row[j] + (c1!=c2)

# Get the minimum to append to the current row
current_row.append(min(insertions, deletions, substitutions))

# Store the previous row
previous_row=current_row

# Returns the last element (distance)
returnprevious_row[-1]


if__name__=="__main__":
first_word=input("Enter the first word:\n").strip()
second_word=input("Enter the second word:\n").strip()

result=levenshtein_distance(first_word, second_word)
print(f"Levenshtein distance between {first_word} and {second_word} is {result}")
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
"""
This is a Python implementation of the levenshtein distance.
Levenshtein distance is a string metric for measuring the
difference between two sequences.

For doctests run following command:
python -m doctest -v levenshtein-distance.py
or
python3 -m doctest -v levenshtein-distance.py

For manual testing run:
python levenshtein-distance.py
"""


deflevenshtein_distance(first_word: str, second_word: str) ->int:
"""Implementation of the levenshtein distance in Python.
 :param first_word: the first word to measure the difference.
 :param second_word: the second word to measure the difference.
 :return: the levenshtein distance between the two words.
 Examples:
 >>> levenshtein_distance("planet", "planetary")
 3
 >>> levenshtein_distance("", "test")
 4
 >>> levenshtein_distance("book", "back")
 2
 >>> levenshtein_distance("book", "book")
 0
 >>> levenshtein_distance("test", "")
 4
 >>> levenshtein_distance("", "")
 0
 >>> levenshtein_distance("orchestration", "container")
 10
 """
# The longer word should come first
iflen(first_word) <len(second_word):
returnlevenshtein_distance(second_word, first_word)

iflen(second_word) ==0:
returnlen(first_word)

previous_row=list(range(len(second_word) +1))

fori, c1inenumerate(first_word):
current_row= [i+1]

forj, c2inenumerate(second_word):
# Calculate insertions, deletions and substitutions
insertions=previous_row[j+1] +1
deletions=current_row[j] +1
substitutions=previous_row[j] + (c1!=c2)

# Get the minimum to append to the current row
current_row.append(min(insertions, deletions, substitutions))

# Store the previous row
previous_row=current_row

# Returns the last element (distance)
returnprevious_row[-1]


if__name__=="__main__":
first_word=input("Enter the first word:\n").strip()
second_word=input("Enter the second word:\n").strip()

result=levenshtein_distance(first_word, second_word)
print(f"Levenshtein distance between {first_word} and {second_word} is {result}")
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
"""
This is a Python implementation of the levenshtein distance.
Levenshtein distance is a string metric for measuring the
difference between two sequences.

For doctests run following command:
python -m doctest -v levenshtein-distance.py
or
python3 -m doctest -v levenshtein-distance.py

For manual testing run:
python levenshtein-distance.py
"""


deflevenshtein_distance(first_word: str, second_word: str) ->int:
"""Implementation of the levenshtein distance in Python.
 :param first_word: the first word to measure the difference.
 :param second_word: the second word to measure the difference.
 :return: the levenshtein distance between the two words.
 Examples:
 >>> levenshtein_distance("planet", "planetary")
 3
 >>> levenshtein_distance("", "test")
 4
 >>> levenshtein_distance("book", "back")
 2
 >>> levenshtein_distance("book", "book")
 0
 >>> levenshtein_distance("test", "")
 4
 >>> levenshtein_distance("", "")
 0
 >>> levenshtein_distance("orchestration", "container")
 10
 """
# The longer word should come first
iflen(first_word) <len(second_word):
returnlevenshtein_distance(second_word, first_word)

iflen(second_word) ==0:
returnlen(first_word)

previous_row=list(range(len(second_word) +1))

fori, c1inenumerate(first_word):
current_row= [i+1]

forj, c2inenumerate(second_word):
# Calculate insertions, deletions and substitutions
insertions=previous_row[j+1] +1
deletions=current_row[j] +1
substitutions=previous_row[j] + (c1!=c2)

# Get the minimum to append to the current row
current_row.append(min(insertions, deletions, substitutions))

# Store the previous row
previous_row=current_row

# Returns the last element (distance)
returnprevious_row[-1]


if__name__=="__main__":
first_word=input("Enter the first word:\n").strip()
second_word=input("Enter the second word:\n").strip()

result=levenshtein_distance(first_word, second_word)
print(f"Levenshtein distance between {first_word} and {second_word} is {result}")
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
"""
This is a Python implementation of the levenshtein distance.
Levenshtein distance is a string metric for measuring the
difference between two sequences.

For doctests run following command:
python -m doctest -v levenshtein-distance.py
or
python3 -m doctest -v levenshtein-distance.py

For manual testing run:
python levenshtein-distance.py
"""


deflevenshtein_distance(first_word: str, second_word: str) ->int:
"""Implementation of the levenshtein distance in Python.
 :param first_word: the first word to measure the difference.
 :param second_word: the second word to measure the difference.
 :return: the levenshtein distance between the two words.
 Examples:
 >>> levenshtein_distance("planet", "planetary")
 3
 >>> levenshtein_distance("", "test")
 4
 >>> levenshtein_distance("book", "back")
 2
 >>> levenshtein_distance("book", "book")
 0
 >>> levenshtein_distance("test", "")
 4
 >>> levenshtein_distance("", "")
 0
 >>> levenshtein_distance("orchestration", "container")
 10
 """
# The longer word should come first
iflen(first_word) <len(second_word):
returnlevenshtein_distance(second_word, first_word)

iflen(second_word) ==0:
returnlen(first_word)

previous_row=list(range(len(second_word) +1))

fori, c1inenumerate(first_word):
current_row= [i+1]

forj, c2inenumerate(second_word):
# Calculate insertions, deletions and substitutions
insertions=previous_row[j+1] +1
deletions=current_row[j] +1
substitutions=previous_row[j] + (c1!=c2)

# Get the minimum to append to the current row
current_row.append(min(insertions, deletions, substitutions))

# Store the previous row
previous_row=current_row

# Returns the last element (distance)
returnprevious_row[-1]


if__name__=="__main__":
first_word=input("Enter the first word:\n").strip()
second_word=input("Enter the second word:\n").strip()

result=levenshtein_distance(first_word, second_word)
print(f"Levenshtein distance between {first_word} and {second_word} is {result}")
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
"""
This is a Python implementation of the levenshtein distance.
Levenshtein distance is a string metric for measuring the
difference between two sequences.

For doctests run following command:
python -m doctest -v levenshtein-distance.py
or
python3 -m doctest -v levenshtein-distance.py

For manual testing run:
python levenshtein-distance.py
"""


deflevenshtein_distance(first_word: str, second_word: str) ->int:
"""Implementation of the levenshtein distance in Python.
 :param first_word: the first word to measure the difference.
 :param second_word: the second word to measure the difference.
 :return: the levenshtein distance between the two words.
 Examples:
 >>> levenshtein_distance("planet", "planetary")
 3
 >>> levenshtein_distance("", "test")
 4
 >>> levenshtein_distance("book", "back")
 2
 >>> levenshtein_distance("book", "book")
 0
 >>> levenshtein_distance("test", "")
 4
 >>> levenshtein_distance("", "")
 0
 >>> levenshtein_distance("orchestration", "container")
 10
 """
# The longer word should come first
iflen(first_word) <len(second_word):
returnlevenshtein_distance(second_word, first_word)

iflen(second_word) ==0:
returnlen(first_word)

previous_row=list(range(len(second_word) +1))

fori, c1inenumerate(first_word):
current_row= [i+1]

forj, c2inenumerate(second_word):
# Calculate insertions, deletions and substitutions
insertions=previous_row[j+1] +1
deletions=current_row[j] +1
substitutions=previous_row[j] + (c1!=c2)

# Get the minimum to append to the current row
current_row.append(min(insertions, deletions, substitutions))

# Store the previous row
previous_row=current_row

# Returns the last element (distance)
returnprevious_row[-1]


if__name__=="__main__":
first_word=input("Enter the first word:\n").strip()
second_word=input("Enter the second word:\n").strip()

result=levenshtein_distance(first_word, second_word)
print(f"Levenshtein distance between {first_word} and {second_word} is {result}")
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
"""
This is a Python implementation of the levenshtein distance.
Levenshtein distance is a string metric for measuring the
difference between two sequences.

For doctests run following command:
python -m doctest -v levenshtein-distance.py
or
python3 -m doctest -v levenshtein-distance.py

For manual testing run:
python levenshtein-distance.py
"""


deflevenshtein_distance(first_word: str, second_word: str) ->int:
"""Implementation of the levenshtein distance in Python.
 :param first_word: the first word to measure the difference.
 :param second_word: the second word to measure the difference.
 :return: the levenshtein distance between the two words.
 Examples:
 >>> levenshtein_distance("planet", "planetary")
 3
 >>> levenshtein_distance("", "test")
 4
 >>> levenshtein_distance("book", "back")
 2
 >>> levenshtein_distance("book", "book")
 0
 >>> levenshtein_distance("test", "")
 4
 >>> levenshtein_distance("", "")
 0
 >>> levenshtein_distance("orchestration", "container")
 10
 """
# The longer word should come first
iflen(first_word) <len(second_word):
returnlevenshtein_distance(second_word, first_word)

iflen(second_word) ==0:
returnlen(first_word)

previous_row=list(range(len(second_word) +1))

fori, c1inenumerate(first_word):
current_row= [i+1]

forj, c2inenumerate(second_word):
# Calculate insertions, deletions and substitutions
insertions=previous_row[j+1] +1
deletions=current_row[j] +1
substitutions=previous_row[j] + (c1!=c2)

# Get the minimum to append to the current row
current_row.append(min(insertions, deletions, substitutions))

# Store the previous row
previous_row=current_row

# Returns the last element (distance)
returnprevious_row[-1]


if__name__=="__main__":
first_word=input("Enter the first word:\n").strip()
second_word=input("Enter the second word:\n").strip()

result=levenshtein_distance(first_word, second_word)
print(f"Levenshtein distance between {first_word} and {second_word} is {result}")
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
"""
This is a Python implementation of the levenshtein distance.
Levenshtein distance is a string metric for measuring the
difference between two sequences.

For doctests run following command:
python -m doctest -v levenshtein-distance.py
or
python3 -m doctest -v levenshtein-distance.py

For manual testing run:
python levenshtein-distance.py
"""


deflevenshtein_distance(first_word: str, second_word: str) ->int:
"""Implementation of the levenshtein distance in Python.
 :param first_word: the first word to measure the difference.
 :param second_word: the second word to measure the difference.
 :return: the levenshtein distance between the two words.
 Examples:
 >>> levenshtein_distance("planet", "planetary")
 3
 >>> levenshtein_distance("", "test")
 4
 >>> levenshtein_distance("book", "back")
 2
 >>> levenshtein_distance("book", "book")
 0
 >>> levenshtein_distance("test", "")
 4
 >>> levenshtein_distance("", "")
 0
 >>> levenshtein_distance("orchestration", "container")
 10
 """
# The longer word should come first
iflen(first_word) <len(second_word):
returnlevenshtein_distance(second_word, first_word)

iflen(second_word) ==0:
returnlen(first_word)

previous_row=list(range(len(second_word) +1))

fori, c1inenumerate(first_word):
current_row= [i+1]

forj, c2inenumerate(second_word):
# Calculate insertions, deletions and substitutions
insertions=previous_row[j+1] +1
deletions=current_row[j] +1
substitutions=previous_row[j] + (c1!=c2)

# Get the minimum to append to the current row
current_row.append(min(insertions, deletions, substitutions))

# Store the previous row
previous_row=current_row

# Returns the last element (distance)
returnprevious_row[-1]


if__name__=="__main__":
first_word=input("Enter the first word:\n").strip()
second_word=input("Enter the second word:\n").strip()

result=levenshtein_distance(first_word, second_word)
print(f"Levenshtein distance between {first_word} and {second_word} is {result}")