Edit Distance Algorithm

Data analyst daily algorithm

Photo by Soledad Lorieto on Unsplash

As a data analyst, a part of my job is to solve some novel data science questions. One project that I was working on these days was creating a program that could match strings for two tables. We used the fuzzywuzzy package Python. (I am still working on this project and will share my outcome one day)

After digging into this package, I found that it used the concept of edit distance. Therefore, this article will explain the methodology of the edit distance algorithm.

What is Edit Distance?

Purpose

Edit distance usually is used for comparing the similarity of strings. For example, “horses” and “horse” has only one edit distance, and “horses” and “cow” has four edit distance. We can say the word“horse” is more similar to “horses” than “cow.”

Concept

The concept of edit distance is simple. We want to find the minimal step that requires changing two strings to the same. For example, we need at least three actions to change the word “horse” and “ros” to the same.