Levenshtein Distance in C
Da Bioingegneria Elettronica e Informatica.
Nicola Altini nicola.altini@poliba.it
Vitoantonio Bevilacqua vitoantonio.bevilacqua@poliba.it
Indice
Levenshtein Distance in C
Including Libraries
#include <stdlib.h>#include <stdio.h>#include <string.h>
Macros
#define MAXNCHARS 50#define VERBOSE 1#define VERSION 1
Declaration of Functions
void print_matrix(int **, int, int);
int Levenshtein_distance(char *, char *);
int Levenshtein_distance_v2(char *, char *);
int minimum(int, int, int);
Main
int main(void) {
FILE *query, *db;
char str1[MAXNCHARS], str2[MAXNCHARS];
int d;
printf("VERSION: %d\n", VERSION);
printf("VERBOSE: %d\n", VERBOSE);
query = fopen("query.fa","r");
if (query == NULL) {
printf("It is not possible to open query.fa!\n");
scanf ("%[^\n]%*c", str1);
} else {
fscanf (query, "%[^\n]%*c", str1);
}db = fopen("db.fna", "r");
if (db == NULL) {
printf("It is not possible to open db.fna!\n");
scanf ("%[^\n]%*c", str2);
} else {
fscanf (db, "%[^\n]%*c", str2);
}printf("Query:\n'%s'\n", str1);
printf("Database:\n'%s'\n", str2);
if (VERSION == 1) {
d = Levenshtein_distance(str1,str2);
} else if (VERSION == 2) {
d = Levenshtein_distance_v2(str1,str2);
}printf("La distanza di Levenshtein e': %d", d);
return 0;
}
Definition of Functions
int Levenshtein_distance(char *x, char *y) {
int m = strlen(x);
int n = strlen(y);
printf("m = %d , n = %d\n", m, n);
int i, j;
int distance;
int **d = malloc((m + 1) * sizeof(int*));
for(i = 0; i <= m; i++)
d[i] = malloc((n + 1) * sizeof(int));
for(i = 0; i <= m; i++)
d[i][0] = i;
for(j = 1; j <= n; j++)
d[0][j] = j;
if (VERBOSE) print_matrix(d, m, n);
for(i = 1; i <= m; i++) {
for(j = 1; j <= n; j++) {
if(x[i - 1] != y[j - 1]) {
int k = minimum(
d[i][j - 1],
d[i - 1][j],
d[i - 1][j - 1]
);
d[i][j] = k + 1;
} else {
d[i][j] = d[i - 1][j - 1];
}if (VERBOSE) print_matrix(d, m, n);
}}distance = d[m][n];
for(i = 0; i <= m; i++)
free(d[i]);
free(d);
return distance;
}void print_matrix(int **matrix, int m, int n) {
int i, j;
for (i = 0; i <= m; i++) {
for (j = 0; j <= n; j++) {
printf("%d ", matrix[i][j]);
}printf("\n");
}printf("\n\n");
}int Levenshtein_distance_v2(char *x, char *y) {
int m = strlen(x);
int n = strlen(y);
int i, j;
int distance;
int *prev = malloc((n + 1) * sizeof(int));
int *curr = malloc((n + 1) * sizeof(int));
int *tmp = 0;
for(i = 0; i <= n; i++)
prev[i] = i;
for(i = 1; i <= m; i++) {
curr[0] = i;
for(j = 1; j <= n; j++) {
if(x[i - 1] != y[j - 1]) {
int k = minimum(curr[j - 1], prev[j - 1], prev[j]);
curr[j] = k + 1;
} else {
curr[j] = prev[j - 1];
}}tmp = prev;
prev = curr;
curr = tmp;
memset((void*) curr, 0, sizeof(int) * (n + 1));
}distance = prev[n];
free(curr);
free(prev);
return distance;
}int minimum(int a, int b, int c) {
/* funzione che calcola il minimo di 3 valori */int min = a;
if (b < min) min = b;
if (c < min) min = c;
return min;
}
