Skip to main content

Edit Distance ↔ metric to quantify string similarity via # bitwise ops

aka ED

Levenshtein distance​

Algo to compute ED by # single char ins/sub/del ops to transform string to another

Damerau-Levenshtein distance​

Algo extends Levenshtein distance but include transpose as valid op

Longest common subsequence (LCS)​

Algo to compute ED via single char ins/del ops only

Bitap Algo​

Algo to Fuzzy Search by transform string to Bitmask & compute # Bitwise Ops for Levenshtein distance

References​

  1. Levenshtein distance ↔ Algo to compute ED by # single char ins/sub/del ops to transform string to another

  2. Longest common subsequence (LCS) ↔ Algo to compute ED via single char ins/del ops only

  3. Fuzzy Search ↔ Typo Tolerance for Search to allow approx match to string via Edit Distance Algo