The Essence of Levenshtein Edit Distance: A Mathematical Lens
The Birth of the Concept
The Levenshtein edit distance algorithm was introduced by Vladimir Levenshtein in 1965. It's a mathematical formula that calculates the least number of single-character edits needed to change one string into another.
The Intimidating Equation
Upon first glance, the formula for Levenshtein Distance may seem complex:
Breaking Down the Formula
The Min Function
The min function is key to understanding the formula. What we're doing is considering three options at each step:
- Insertion: This is represented by
- Deletion: This is represented by
- Substitution: This is represented by
We take the minimum of these three options because we want to find the least number of edits needed.
The Cost Factor
The "cost" is either 0 or 1, depending on whether the current characters in the strings a and b are equal or not. If they are equal, the cost is 0; otherwise, it's 1.
A More Intuitive View
Think of this as a journey where you start at one corner of a grid. Your destination is the opposite corner. The grid cells represent the characters in the strings you're comparing. Each move from one cell to another corresponds to an edit operation:
- Moving horizontally represents insertion.
- Moving vertically represents deletion.
- Moving diagonally represents substitution.
You're trying to find the shortest path from one corner to another, making the least number of moves (edits). That's your Levenshtein Distance.
xxxxxxxxxx console.log('PASSED: ' + "getEditDistance('busa', 'ebcar') should return 4");var assert = require('assert');function getEditDistance(a, b) { return '';}class Graph { constructor() { this.adjacencyList = new Map(); this.verticesCount = 0; } addVertex(nodeVal) { this.adjacencyList.set(nodeVal, []); this.verticesCount++; } addEdge(src, dest) { this.adjacencyList.get(src).push(dest); this.adjacencyList.get(dest).push(src); // push to both adjacency lists } removeVertex(val) { if (this.adjacencyList.get(val)) { this.adjacencyList.delete(val); }