A simple C program to calculate Levenshtein distance
Levenshtein distance is a metric for measuring the amount of difference between two sequence. The sequences will be strings in most of the real life cases.
More information is available at Wikipedia: http://en.wikipedia.org/wiki/Levenshtein_distance
Its a simple program to implement it.
/******************************************************
* A simple program to calculate Levenshtein distance *
* *
* http://en.wikipedia.org/wiki/Levenshtein_distance *
* *
******************************************************/
#include<stdio.h>
#include<string.h>
int levenshtein_compare(const char *s1, const char *s2)
{
int l1 = strlen(s1);
int l2 = strlen(s2);
return l1 != l2 ? l1 - l2 : strcmp(s1, s2);
}
int main()
{
const char *str1 = "strong";
const char *str2 = "string";
printf("Levenshtein Distance is %d \n", levenshtein_compare(str1, str2));
return 0;
}
If you want to think of it in Python, here it goes:
# Python program for simple lavenshtein distance calculation
def levenshtein_compare(s1, s2):
len1 = len(s1)
len2 = len(s2)
if (len1 != len2):
ret_val = len1 – len2
else:
ret_val = cmp(s2,s1) #(s1 > s2) – (s1 < s2)
return ret_val
if __name__ == “__main__”:
print “Distance is:”, levenshtein_compare(“paintt”, “past”)