PDA

Visualizza la versione completa : Distanza di Levenshtein


devil89
17-08-2006, 15:14
Ho conosciuto per caso questa "legge" dello scenziato russo.

Qualcuno mi potrebbe fare vedere un semplice algoritmo scritto in C di applicazione di questa distanza di Levenshtein, per il calcolo del minor numero di modifiche per trasformare una stringa A in un'altra B?

Grazie

U-bahn
17-08-2006, 16:50
cioè ti interessa solo sapere il numero minimo di modifiche ?
o queste modifiche devono essere applicate ?

nel primo caso:


int editd(const char *s1, const char *s2)
{
int ed = 0;

if (strcmp(s1, s2) == 0)
return 0;

while (*s1 != '\0') {
if ((*s1 - *s2) != 0)
++ed;
if (*s2 != '\0')
++s2;
++s1;
}
while (*s2 != '\0')
++ed, ++s2;

return ed;
}

alka
18-08-2006, 09:51
Se ti interessa l'algoritmo nel linguaggio C++, perché mettere OT? :zizi:
Correggo il prefisso.

Ciao! :ciauz:

devil89
18-08-2006, 15:28
Mi interessavano entrambe le cose: l'algoritmo per il calcolo del numero minimo di modifiche e anche l'applicazione delle modifiche a scelta (solo un esempio).

Loading