Visualizza sorgente di Levenshtein Distance in C

'''Nicola Altini''' [mailto:nicola.altini@poliba.it nicola.altini@poliba.it]

'''Vitoantonio Bevilacqua''' [mailto:vitoantonio.bevilacqua@poliba.it vitoantonio.bevilacqua@poliba.it]

[http://www.vitoantoniobevilacqua.it/wiki/images/7/7a/BLAST_LD.pdf Slides]

== Levenshtein Distance in C ==
=== Including Libraries ===
<syntaxhighlight lang="c" line>
#include <stdlib.h>
#include <stdio.h>  
#include <string.h>
<syntaxhighlight/>

=== Macros ===
<syntaxhighlight lang="c" line>
#define MAXNCHARS 50
#define VERBOSE 1
#define VERSION 1
<syntaxhighlight/>

=== Declaration of  Functions ===
<syntaxhighlight lang="c" line>
void print_matrix(int **, int, int);
int Levenshtein_distance(char *, char *);
int Levenshtein_distance_v2(char *, char *);
int minimum(int, int, int);
<syntaxhighlight/>

=== Main ===
<syntaxhighlight lang="c" line>
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;
}
<syntaxhighlight/>

=== Definition of Functions ===
<syntaxhighlight lang="c" line>
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;
}
<syntaxhighlight/>