• Acasă
  • Despre noi
  • Autori
  • Mărturii
  • Arhivă
  • Trimite Articol
  • Contact

WORLDIT

Lumea în 1 și 0.

  • Știri
    • Tehnologie
    • Tehnologie mobilă
    • Securitate
    • Developers
    • Știință
    • Benzi desenate
    • Jocuri
    • Intern
  • Tehnic
    • Browser
    • C#
    • C/C++
    • Challenge
    • HTML/CSS
    • Javascript, Ajax, jQuery
    • Open Source
    • PHP
    • Python
    • Securitate IT
    • Socializare
    • WordPress
    • Altele
  • Recenzii
  • Interviuri
  • Evenimente

Distanta Levenstein – algoritmul de editare

2
  • Publicat de Andrei Avădănei
  • în Fără categorie
  • — 14 mart., 2010 at 1:55 pm

Cu totii ne confruntam in viata de zi cu zi cu aplicatii informatice ce detin o cantitate uriasa de informatie si resurse. Pentru a multumi utilizatorul intr-un timp foarte scurt aceste aplicatii au dezvoltat diverse sisteme pentru a facilita accesul la informatiile detinute. Este foarte comod sa cautam pe Google (sau in oricare alt motor de cautare) ce dorim in loc sa luam o lista de cateva trilioane de site-uri pentru a face aceeasi operatie.

Una din problemele majore cu care se confrunta motoarele de cautare este neatentia end-userilor. Nu de putine ori se intampla sa scriem un cuvant gresit. Motorul de cautare Google, spre exemplu, are un sistem de sugestii ce ofera alternative la cuvintele scrise de tine, optiune ce se dovedeste una dintre cele mai utile din intreg ansamblu de facilitati ale engine-ului. Spre exemplu, daca vom scrie „prgramator” ar fi foarte util ca un sistem sa detecteze eroarea si sa ne corecteze oferindu-ne si varianta „programator”.

Ce este distanta de editare sau distanta Levenstein?

Distanta Levenstein este un algoritm ce poate ajuta la determinarea similaritatii intre expresii sau cuvinte utilizate in cautari. Functia poate fi folosita pentru a compara diverse deosebiri intre doua cuvinte. Prin distanta Levenstein se intelege numarul de caractere ce trebuie inlocuite, inserate, eliminate din prima expresie pentru a obtine a doua expresie.

Aplicabilitate

• Motoarea de cautare
• Inteligenta artificiala primitiva
• Dictionare sinonime, antonime etc.
• Cea mai lunga subsecventa comuna
• Distanta Damerau–Levenshtein
• Distanta Hamming

Probleme

1. Problema siruri2 de pe campion.
Distanta Levenshtein dintre doua siruri de caractere este egala cu numarul minim de operatii necesare pentru a transforma primul sir in celalalt. Operatiile permise sunt inserarea unui caracter, stergerea unui caracter sau inlocuirea unui caracter cu un alt caracter.

Cerinta

Cunoscand cele doua siruri de caractere, sa se determine care este numarul minim de operatii necesare pentru a transforma primul sir in cel de-al doilea sir.

Solutie

Evident, aceasta problema se rezolva prin aplicarea algoritmului clasic al distantei Levenstein. Solutia se bazeaza pe programare dinamica. De remarcat este faptul ca nu trebuie sa se faca diferenta intre majuscule si restul caracterelor.

2. Problema cuvinte1 de pe campion
Balaurul Arhirel se decide sa invete biologie, asa ca doreste sa cumpere manualul de clasa a X-a. Din pacate, acesta nu se mai gaseste pe piata, dar Balaurul reuseste sa gaseasca o copie la un prieten. Dupa ce incepe sa citeasca, Balaurul Arhirel observa ca exista greseli in copia prietenului, iar intr-un impuls de energie, se hotaraste sa corecteze manualul. El are la dispozitie un dictionar de M cuvinte dintre care trebuie sa extraga variante pentru cuvantul gresit. Asupra cuvantului gresit balaurul poate sa faca urmatoarele schimbari in asa fel incat acesta sa ajunga la o varianta din dictionar:
– poate sterge o litera ;
– poate insera o litera ;
– poate schimba o litera in alta litera.
Totusi, Balaurul Arhirel este lenes, asa ca nu doreste sa opereze mai mult de K schimbari in cuvantul gresit pentru a-l aduce la o forma corecta (existenta in dictionar).

Cerinta

Ajutati-l pe Balaurul Arhirel sa afle care dintre cuvintele din dictionar ar putea fi variante ale cuvantului gresit.

Solutie

Observam ca o complexitate ca in cazul primei solutii nu va duce la o rezolvare de 100 de puncte. Algoritmul clasic pentru determinarea distantei Levenstein, este O(n*m), unde n si m reprezinta lungimea celor doua cuvinte comparate. Asadar, O(n*m*k) va iesi cu siguranta din timpul de executie. Pentru asta, trebuie observat faptul ca noi nu suntem interesati decat de diagonala principala si (cu elementele din jurul ei) si doar de primii k pasi (avem nevoie de minim k incrementari pentru a decide daca putem sau nu transforma cuvantul in maxim k pasi). Si aceasta solutie foloseste algoritmul de editare Levenstein, implicit programare dinamica.

Imbunatatiri

• Observam ca avem nevoie de memorie O(m*n), dar dinamica necesita doar pastrarea ultimilor doua linii din matrice asa ca se poate reduce doar la O(2*n).
• Putem memora operatiile de stergere, editare, inserare separat.
• Daca suntem interesati doar de determinarea distantelor de editare ce sunt mai mici decat o valoare k, vom folosi o complexitate similara cu cea a problemei 2 din acest articol.
• Putem normaliza rezultatele in intervalul [0,1]

double _levenshtein(char* s1, char* s2) 
{
    return 1-levenshtein(s1, s2)/max(strlen(s1), strlen(s2));
}

• Putem da diverse valori de penalitate pentru inserare, inlocuire, stergere.

Completari

Puteti arunca o privire pe functia Levenstein din PHP.
Levenstein Distance pe Wikipedia.

Daca acest articol contine o greseala, selecteaza cuvintele sau fraza gresita si tasteaza combinatia de taste Shift + Enter sau apasa click aici pentru a o raporta. Multumim!

— Andrei Avădănei a scris 1246 articole

Andrei scrie pe worldit.info din vara lui 2011. Este fondatorul Asociatiei Centrul de Cercetare in Securitate Informatica din Romania - CCSIR si coordoneaza DefCamp, cea mai importanta conferinta de securitate informatica & hacking din Europa Centrala si de Est. Andrei ofera in cadrul Bit Sentinel servicii de securitate informatica, penetration testing, security management, recuperarea de pe urma unui atac cibernetic, training-uri si workshop-uri.

  • Articolul anterior Paris in toata splendoarea lui la 26 de gigapixeli
  • Articolul următor 25 de ani de la primul domeniu .com

2 Comentarii

  1. accesinterzis spune:
    martie 14, 2010 la 3:34 pm

    Tare articolul.

  2. Peste 20 de articole din 2010 ce merita citite de un programator web | WorldIT spune:
    decembrie 29, 2010 la 1:16 pm

    […] feed-urile RSS? Procesarea directoarelor eficient in PHP Numara cate linii de cod are proiectul tau Distanta Levenstein – algoritmul de editare Afla cand cineva ti-a citit mailul Introducere in Design Patterns – MVC (1, 2 si 3) Cum sa […]


  • Facebook

    WorldIT.info
  • Ultimele Atacuri Cibernetice din Romania – RO Hacked

    • imacoolat-curat.ro
      | Published: februarie 3, 2020 - 2:00 am
    • hotel-palace.ro
      | Published: februarie 2, 2020 - 2:00 am
    • www.tahometru.ro
      | Published: februarie 1, 2020 - 2:00 am
    • alexisart.ro
      | Published: ianuarie 30, 2020 - 2:00 am
    • justshop.ro
      | Published: ianuarie 29, 2020 - 2:00 am
    RO Hacked este registrul atacurilor cibernetice din România.
  • Caută

  • Articole Recomandate

    • Recent Posts
    • Tags
    • Număr record de participanți la DefCamp 2015, cel mai important eveniment dedicat securității cibernetice din Europe Centrala si de Estdecembrie 2, 2015
    • La DefCamp 2015 vei afla prin ce tehnici pot fi evitate măsurile de securitate ale sistemelor informatice criticeoctombrie 16, 2015
    • Ultima sansa sa rezervi bilete de tip Early Bird la DefCamp 2015septembrie 1, 2015
    • 15 sfaturi despre cum poti deveni un programator bun venite de la specialisti romaniaugust 4, 2015
    • algoritmica Android antivirus Apple Avadanei Andrei benzi desenate BitDefender blog browser C++ Chrome concurs eveniment Facebook Firefox Google google chrome hacking html5 infografic informatica internet Internet Explorer IT javascript linux Microsoft Mozilla Firefox online PHP programare retea sociala review Romania securitate Tehnologie Twitter web Windows Windows 7 Wordpress WorldIT worldit.info Yahoo! YouTube
  • ianuarie 2021
    L Ma Mi J V S D
    « dec.    
     123
    45678910
    11121314151617
    18192021222324
    25262728293031
  • Link-uri Sponsorizate

    • laptop second hand

    • Calculatoare Second Hand

    • cod voucher pc garage

  • Home
  • Distanta Levenstein – algoritmul de editare
  • Important

    • Bit Sentinel
    • Centrul de Cercetare în Securitate Informatică din România
    • DefCamp
  • Prieteni

    • BetiT.ro
    • bijuterii handmade
    • Computerica | Resurse gratuite PC
    • Descopera.org
    • Gadgeturi si IT – Giz.ro
  • Prieteni

    • PC – Config
    • RO Hacked
    • Stiri IT

Copyright © 2009-2014 WORLDIT. Toate drepturile Rezervate.
Termeni și condiții | Contact | Licența Creative Commons

Multumim foarte mult ca ne-ai raportat greseala! O vom remedia in cel mai scurt timp posibil.