Search the Community

Aceasta este o implementare simpla in c++ a algoritmului lui Levenshtein pentru a masura diferentele intre 2 cuvinte. Implementarea are la baza pseudo codul de pe pagina wiki de aici M-am gandit sa postez aceasta implementare deoarece din cautarile mele alte implementari erau un pic mai complicate. Implementarea este o copie stricta dupa acel pseudo cod, singura adaugire este ca in loc sa returneze numarul de modificari necesare, el returneaza un "procent" de similaritate intre 100% si 0 %; Daca doriti sa le folositi nu trebuie decat sa adaugati cele 2 fisiere de mai jos la proiectul vostru. dist.h #ifndef DIST_H_INCLUDED #define DIST_H_INCLUDED /////////////////////////////////////////////////////////////////////////// //Aceasta functie preia 2 stringuri si le compara la nivel sintactic. // //Returneaza o valoare de tip double intre 0 si 100 in functie de cat // //de asemanatoare sunt cuvintele. // //Aceasta are la baza algoritmul lui Levenstein, implementarea se face // //pe baza pseudocodului de la adresa urmatoare // //http://en.wikipedia.org/wiki/Levenshtein_distance // /////////////////////////////////////////////////////////////////////////// #include <iostream> #include <string> using std::string; using std::cout; using std::endl; using std::min; double dist(string s1, string s2); #endif // DIST_H_INCLUDED dist.cpp /////////////////////////////////////////////////////////////////////////// //Aceasta functie preia 2 stringuri si le compara la nivel sintactic. // //Returneaza o valoare de tip double intre 0 si 100 in functie de cat // //de asemanatoare sunt cuvintele. // //Aceasta are la baza algoritmul lui Levenstein, implementarea se face // //pe baza pseudocodului de la adresa urmatoare // //http://en.wikipedia.org/wiki/Levenshtein_distance // /////////////////////////////////////////////////////////////////////////// #include "dist.h" double dist(string s1, string s2) { int num1 = s1.size(); int num2 = s2.size(); double array[num1 + 1][num2 + 1]; if(num1 == 0) { cout << "Primul string e gol.\n"; cout << "Nu se poate face comparatia.\n"; cout << endl; } else if(num2 == 0) { cout << "Al doilea string e gol.\n"; cout << "Nu se poate face comparatia.\n"; cout << endl; } else { for(int i = 0; i <= num1; i++) { array[i][0] = i; } for(int j = 0; j <= num2; j++) { array[0][j] = j; } for(int i = 1; i <= num1; i++) { for(int j = 1; j <= num2; j++) { if(s1[i - 1] == s2[j - 1]) { array[i][j] = array[i - 1][j - 1]; } else { array[i][j] = min(((array[i - 1][j] + 1)), (min((array[i][j - 1] + 1), (array[i - 1][j - 1] + 1)))); } } } } return (1.0 - (array[num1][num2] / min(num1, num2))) * 100; } Daca aveti de adaugat ceva, postati va rog.