Levenshtein Distance in C

Da Bioingegneria Elettronica e Informatica.

Versione del 30 nov 2019 alle 14:01 di Profbevilacqua (Discussione | contributi)

(diff) ← Versione meno recente | Versione attuale (diff) | Versione più recente → (diff)

Vai a: navigazione, ricerca

Nicola Altini nicola.altini@poliba.it

Vitoantonio Bevilacqua vitoantonio.bevilacqua@poliba.it

Levenshtein Distance in C

Including Libraries

```
#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/>
```

Estratto da "http://www.vitoantoniobevilacqua.it/wiki/index.php?title=Levenshtein_Distance_in_C&oldid=1137"