Cum se pot compara 2 texte ? Sunt convins ca se poate pune un "==" in orice limbaj si se va obtine un raspuns True sau False. Dar intrebarea este daca doua texte difera prin cateva propozitii sau cateva caractere cum putem sa stim daca sunt la fel. Nu vom incerca sa determinam daca 2 text sunt la fel ca si mesaj, ca si informatie transmisa (nu suntem Google), in schimb dorim sa aflam daca 2 texte sunt asemanatoare, similare. Obiectivul programului va dicta directia in care vom determina daca 2 text sunt similare. Mai jos am sa propun 3 situatii:
1. Text Field Autocomplete Sa spunem ca doresti sa implementezi o pagina web sau un UI de desktop si ai adaugat un text field in care utilizatorul trebuie sa introduca o valoare de cateva caractere (sa spunem pana in 50). Tu doresti sa faci un autocomplete frumos care in timp ce utilizatorul scrie intr-un drop down sa ii afisezi posibile valori. Utilizatorul va mai gresi litere va mai apasa pe taste gresite, nu te poti baza 100% pe caracterele introduse de utilizator pentru a putea cauta in ceva baza de date dupa posibile valori. In cazul asta un algorithm de similitudine intre 2 string-uri va putea sa iti spuna care dintre string-urile pe care tu le ai in baza de date sunt cele mai similare cu ce a introdus utilizatorul, pentru a putea crea un drop down cu posibile valori corecte.
2. Specificatii In multe industrii clienti ofera unui furnizor un set de specificatii scrise (texte, poze, diagrame). Astfel de specificatii de client de obicei implica schimbari in componente de mecanica, electronica si software. Specificatiile clientului se vor sparge (in industrie se spune ca se decompun) in alte specificatii specifice domeniului la care se refer (soft, hard, mecanica, etc). O practica corecta de decompunere de specificatii este sa se enunte un nou text care sa descrie dorinta clientului special pentru acel domeniu. Exemplu specificatie Client: "Vreau un buton care sa deschida usa" Dupa decompunere: - specificatie mecanica: "Trebui introdus in desen un buton de plastic." - specificatie hardware: "Trebuie utilizat un pin digital pentru buton." - specificatie software: "Trebuie implementata o functie care sa actioneze un pin digital cand se apasa butonul." Totul clar pana aici, insa daca va uitati atent la cele 3 specificatii decompuse veti vedea ca textul este foarte diferit fata de cel al clientului. Decompunerea implica o sparge a informatie originale (de la client) in subseturi de informatii (mai specifice), insa implica si o schimbare a textului specificatiei care ajunge la un domeniu. Acesta diferenta de text este un marker ca decompunerea fost facuta (la suprafata) corect. Daca cele 3 specificatii ale celor 3 domenii ar fi exact la fel ca si specificatia clientului am putea sa ne dam seama ca decompunerea nu a fost facut foarte atent.
3. Diferente Daca avem 2 fisiere text in memorie si dorim sa aflam precis care caractere sau care cuvinte difera intre ele. Desigur in ziua de azi exista nenumarate librarii si tool-uri care fac asta, dar sa spunem ca noi trebuie sa implementam un astfel de program. Algoritmi Dupa cautari pe internet dupa algoritmi de similitudine intre string-uri am gasit urmatorii : * Levenshtein * Hamming * Damerau-Levenshtein * Gotoh * Jaro * Jaro-Winkler * Needleman-Wunsch * Smith-Waterman * Strccmp95 * Tversky * Overlap * Monge-Elkan * Jaccard * Sorenson * Cosine In acelasi timp am gasit si un baiat cumsecade care a implementat toti algoritmii de mai sus plus cativa in plus intr-o librarie de python numita "textdistance". Implementarea este pur python folosind numpy. Va recomand sa cititi matematica din spatele algoritmilor. Nu este deloc complicata, si chiar interesanta. Algoritmi de similitudine se impart in 4 categorii: - edit based - detecteaza numarul de schimbari facute intre cele doua texte la nivel de caracter. - token based - detecteaza numarul de tokens schimbate - syntax based - detecteaza subseturile comune intre cele doua texte. - binary comparison - detecteaza redundanta binara. Sunt de obicei folositi la arhivare. Din cauza timpului mare de procesare pentru algoritmi syntax based si binary comparison, algoritmi de mai sus sunt din categoria edit based si token based. Si acum intrebarea este care algoritm il folosim? Am facut un script de python pentru a compara acesti algoritmi.
Codul se gaseste pe gitlab https://github.com/stefandragomir/string_similarity. Am ales 4 texte: - data_1_0 - textul original - data_1_1 - am schimbat cateva cuvinte din text, reformulare. - data_1_2 - text gol. Un control sa vedem daca algoritmul poate detecta diferenta totala. - data_1_3 - jumatate din textul original a fost inclocuit cu alt text Am rulat toti algoritmi pentru a compara toate cele 4 texte intre ele. In urma comparatiei am obtinut 4 parametrii: - distance - valoare returnata de algoritm. Este o valoare direct sau invers proportionala cu similitudinea textelor - similarity - am normalizat distance sa indice un procent intre 0%(complet diferite) si 100%(egale) ca valoare de similitudine intre cele doua texte - similar - alegand un threshold de 90% la similarity care din texte sunt similare (True sau False) - time - timpul necesar pentru calcul Pe langa tabelul cu valori am vrut sa vad cum variaza valoarea returnata la fiecare algoritm, daca schimb cate un caracter la fiecare iteratie. Am luat textul original am schimbat cate un caracter (pe rand) si am recalculat valoarea pentru fiecare algoritm. Statisticile se pot gasi aici: https://github.com/stefandragomir/string_similarity/raw/master/stats/stats.xlsx
In concluzie: Toti algoritmi au detectat foarte bine diferenta intre data_1_0(original) si data_1_1(cateva cuvinte schimbate). Doar o parte din algoritmi au detectat bine(similarity 50%) diferenta intre data_1_0(original) si data_1_3(jumatate din text schimbat). Ca si timp de procesare toti algoritmi sunt rapizi (mai putin Monge-Elkan care a durat aproape o secunda pentru un text de 236 de caractere). Eu as recomanda Levenshtein(cel mai rapid), Needleman-Wunsch sau Smith-Waterman. Distributia de python contine o librarie numita "difflib" pentru comparatie de texte. Foloseste algoritmul Levenshtein.
Comments