An Interest In:
Web News this Week
- April 27, 2024
- April 26, 2024
- April 25, 2024
- April 24, 2024
- April 23, 2024
- April 22, 2024
- April 21, 2024
Levenshtein Distance - An Algorithm that gets you caught in your online exams
When I had to do similarity check between two strings in a project that I was working on, I came across this algorithm. My senior dev explained me this algorithm in very simple terms,
Levenshtein distance between two strings is nothing but the number of single-character edits the first string is away from becoming the second
Named after the soviet mathematician Vladimir Levenshtein, Levenshtein distance (a.k.a edit distance) can been seen in modern applications such as
- Spell checking
- DNA analysis
- Speech recognition
- Plagiarism detection
Yes, this guy is the reason you got caught when you copied something from your friend's assignment. An algorithm developed in the 1960's during the soviet era, is still in a way is being used in your google keyboard, smart devices and smart classroom frameworks.
Now enough of the details, here's the mathematical notation of the algorithm
To the better understanding for all the coders out there, let's define this as a python function, shall we?
import numpy as npdef levi_dist(a,b): ''' takes two strings as arguments, need not be of same length - a,b returns the levenshtein distance between the two strings ''' # Initializing a matrix of zeros rows = len(a) + 1 cols = len(b) + 1 arr = np.zeros((rows,cols),dtype=int) # Initializing the first row and first column with string indices for i in range(rows): for j in range(cols): arr[i][0] = i arr[0][j] = j # Iterating over the elements of the matrix except index column and row for i in range(1,rows): for j in range(1,cols): if a[i-1] == b[j-1]: cost = 0 else: cost = 1 arr[i][j] = min(arr[i-1][j] + 1, # deletion arr[i][j-1] + 1, # insertion arr[i-1][j-1] + cost) # replacement return f'Levenshtein Distance between string A and string B is {arr[len(a)][len(b)]}'
Great! now that we've defined our function, We would need two strings to test this, Here in my case I'll take monty as string A and python as string B. You can choose any two strings of your choice.
calling the function with our strings, we get
> levi_dist('monty','python') Levenshtein Distance between string A and string B is 6
This means that monty is 6 single-character edits away from becoming python.
and here's how the matrix would look like
There we go, we accomplished our task. Now, If you are lazy like me and you don't want to write the algorithm on your own, you can just leverage some of the functions in text transformation modules like jellyfish, enchant etc.. which also does the same thing.
> from jellyfish import levenshtein_distance > levenshtein_distance('monty','python') 6
Cheers! will see you in the next post.
Original Link: https://dev.to/iamadhee/levenshtein-distance-an-algorithm-that-gets-you-caught-in-your-online-exams-3ldd
Dev To
An online community for sharing and discovering great ideas, having debates, and making friendsMore About this Source Visit Dev To