[c++]Implementare algorithm Levenshtein

[nedo]

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.

Edited September 20, 2011 by nedo

[em]

Poate unii se intreaba. Bine, bine, dar la ce foloseste? Pai, google foloseste asta tot timpul sa va corecteze greselile.

public class Corector {
   static int tempAbat[]=new int[65];
   static int tempFrecv[]=new int[65];
   static String tempString[]=new String[65];
   public static void dist(String st1, final int len1,String st2, final int len2,final int frecventa)
   {
       /* M-am folosit de distanta Levenshtein (wiki)
        * Am optimizat ca sa imi calculeze nu doar pentru cuvant, ci si pentru
        * toate sufixele unui cuvant (folosind niste variabile statice)
       */
   int[][] d=new int[len1+1][len2+1];
   int i,j;
   for(i=0;i<=len1;i++)
   {
       d[i][0]=i;
   }
   for(i=0;i<=len2;i++)
   {
       d[0][i]=i;
   }
            for(i=1;i<=len1;i++)
            {
                if(i>=18) {tempAbat[i-1]=i; continue;} // Nu are rost sa calc.
                for(j=1;j<=len2;j++)
                {
                d[i][j]=Math.min(Math.min(d[i-1][j]+1,d[i][j-1]+1),d[i-1][j-1]+((st1.charAt(i-1)==st2.charAt(j-1))?0:1));
                }
                if(d[i][len2]<tempAbat[i-1] || // Are abaterea mai mica?
                 ((d[i][len2])==tempAbat[i-1] && tempFrecv[i-1]<frecventa)) // Daca o are egala, are frecventa mai mica?
                {
                    tempAbat[i-1]=d[i][len2];
                    tempFrecv[i-1]=frecventa;
                    tempString[i-1]=st2;
                }
            }
    }
   public static void corecteazaUnCuvant(String st1, final int len1,String []cuvinte,int[] frec)
   {

       for(int i=0;i<cuvinte.length;i++)
               dist(st1,len1,cuvinte[i],cuvinte[i].length(),frec[i]);
   }

    public static void main(String[] args) throws java.io.FileNotFoundException, java.io.IOException 
    {
        // Citirea de la tastatura + dictionar
        java.util.Scanner cit=new java.util.Scanner(System.in);
        String decorectat=cit.nextLine();  
        String[] cuvinte=new String[8000];
        int[] frec=new int[8000]; 
        int i=0;
        java.io.BufferedReader reader = new java.io.BufferedReader(new java.io.FileReader("dict.txt"));
        String text=null;
        while ((text = reader.readLine()) != null)
        {
            String[] tokens=text.split(" ");
            cuvinte[i]=tokens[0];
            frec[i]=Integer.parseInt(tokens[1]);
            i++;
        }
        decorectat=decorectat.replace(" ", ""); // Scot spatiile
        java.util.Arrays.fill(tempAbat, 63);    // Abateri partiale (cuvinte)
        java.util.Arrays.fill(tempFrecv, -1);   // Frecvente partiale
        int lungimeSir=decorectat.length();
        // Imi construiesc 3 matrici (abateri, frecvente, stringuri)
        // Ex: matriceAbateri[j][i] = Abaterea fata de dictionar a cuvantului
        // citit de la tastatura (de la poz i la j)
        int[][] matriceAbateri=new int[lungimeSir+1][lungimeSir+1];
        int[][] matriceFrecvente=new int[lungimeSir+1][lungimeSir+1];
        String[][] matriceStringuri=new String[65][65];
        int j;
        int t=0;
        for(i=0;i<lungimeSir;i++)
        {
            corecteazaUnCuvant(decorectat.substring(i,lungimeSir),lungimeSir-i,cuvinte,frec);
            t=0;
            for(int k=i;k<=lungimeSir;k++)
            {
                matriceAbateri[k][i]=tempAbat[t];
                matriceFrecvente[k][i]=tempFrecv[t];
                matriceStringuri[k][i]=tempString[t];
                tempFrecv[t]=-1;
                tempAbat[t++]=63;
            }
        }
        /** 
         * Functia distanta (Levenshtein optimizat) imi calculeza distanta nu
         * doar pentru un cuvant, ci si pentru tot sufixul lui
         * Ex: Levi(proiectare, dictionar) => proiectare, roiectare, oiectar etc
         * corectate, cu distante calculate si cu frecvente calculate.
         */
        String stringOptim[]=new String[64];
        int abatOptima[]=new int[64];
        int frecvOptima[]=new int[64];
        int nrCuvinte[]=new int[64];

        stringOptim[0]=matriceStringuri[0][0];
        abatOptima[0]=matriceAbateri[0][0];
        frecvOptima[0]=matriceFrecvente[0][0];
        nrCuvinte[0]=1;
        String temporaryString="";
        // Ma folosesc din plin de rezultatele anterioare
        for(i=1;i<lungimeSir;i++)
        {
            stringOptim[i]=matriceStringuri[i][0];
            frecvOptima[i]=matriceFrecvente[i][0];
            nrCuvinte[i]=1;
            abatOptima[i]=matriceAbateri[i][0];
            for(j=0;j<i;j++)
            {
                if(abatOptima[j]<=abatOptima[i]) // Pot optimiza solutia precedenta?
                {
                    temporaryString=stringOptim[j]+" "+matriceStringuri[i][j+1];
                    if(matriceAbateri[i][j+1]+abatOptima[j]<abatOptima[i] || // Are abaterea mai mica?
                     ((matriceAbateri[i][j+1]+abatOptima[j]==abatOptima[i])&&(nrCuvinte[j]+1<nrCuvinte[i])) || // Daca nu, are mai putine cuvinte?
                     ((matriceAbateri[i][j+1]+abatOptima[j]==abatOptima[i])&&(nrCuvinte[j]+1==nrCuvinte[i])&&
                            (frecvOptima[i]<matriceFrecvente[i][j+1]+frecvOptima[j])) || // Daca nu,are frecventa totala maxima?
                     ((matriceAbateri[i][j+1]+abatOptima[j]==abatOptima[i])&&(nrCuvinte[j]+1==nrCuvinte[i])&&
                            (frecvOptima[i]==matriceFrecvente[i][j+1]+frecvOptima[j])&& stringOptim[i].compareTo(temporaryString)>0)) // Daca nu,lexicografic e mai optim?
                    {
                        // Se poate optimiza!
                        abatOptima[i]=abatOptima[j]+matriceAbateri[i][j+1];
                        stringOptim[i]=temporaryString;
                        frecvOptima[i]=frecvOptima[j]+matriceFrecvente[i][j+1];
                        nrCuvinte[i]=nrCuvinte[j]+1;
                    }
                }
            }
        }
        System.out.print(stringOptim[lungimeSir-1]);
    }
}

Download aici. Parola

helloworld

Exemplu de folosire

java Corector
error free text
error free text

java Corector
schaprobl mcanbe easilisolved 
such a problem can be easily solved

[cmiN]

O simpla dinamica in 2 doua dimensiuni, oricum googleul mai foloseste si arbori de prefixe din care se extrag posibili candidati pentru levenshtein.

[nedo]

O astfel de implementare simpla nici nu ar fi utila la un asa nivel, totusi pentru programele simple spre exemplu ,cautarea unor localitati intr-un fisier, o astfel de implementare este cat de cat suficienta.

Le:

Ca tot suntem la capitolul asta poate aveti vreo idee mai buna decat mine.

Sa zicem ca avem o linie de genul:

data nume telefon1 telefon2 adresa(judet, sat, comuna, strada, numar)

Voi cum ati extrage de aici comuna, satul si strada si numarul, avand in vedere ca toate astea sunt in ordine intamplatoare?

Eu m-am gandit sa fac o lista cu toate satele/comunele dintr-un judet si sa caut cu ajutorul functiei care am postat-o satul si comuna, dar tot raman cu strada numarul si eventual ce mai poate veni la o adresa.

Edited September 20, 2011 by nedo

[cmiN]

Nu prea inteleg cerinta ... despre ce functie vorbesti ? Daca datele din linie sunt corecte pur si simplu dai split in tokens dupa separatoare ca virgula si spatiu sau ce ai acolo, asta intre 2 idexi ai parantezelor.

[nedo]

Chestia asta o fac si pentru a mai invata ceva dar si sa imi usurez munca la servici. In mod normal eu trebuie sa le introduc de mana intr-o baza de date access.

Spre exemplu, am un fisier de genul urmator

2011-07-06 15:12:46 nume1 tel1 tel2 cnp jud.GORJ TG.JIU sat BALTENI-COCORENI nr.85 custodie standard   
2011-07-06 15:16:10 nume2 tel1 tel2 cnp STR CAINENI, NR 5, LOC RAMNICU SARAT, CART. ZIDARI JUD BUZAU custodie standard   
2011-07-06 16:05:44 nume2 tel1 tel2 cnp jud.TIMIS loc.TEREMA MARE nr.150 custodie standard  
2011-07-06 16:10:17 nume4  tel1 cnp ORAS CORABIA, SAT VARTOPU, ,NR 17, JUD OLT custodie standard   
2011-07-06 16:39:09 nume5 tel1 tel2 cnp JUD OLT ORAS CARACAL STR CORABII  custodie standard  ULTIMA UNITATE MILITARA 
2011-07-06 16:43:17 nume6 tel1 tel2 cnp JUD. BACAU COM. TAMAS SAT CHETRIS NR.247 custodie 
2011-07-06 17:05:17 nume7 tel1 tel2 cnp BUCURESTI, STR VINTILA MIHAILESCU, NR 20, BL 64, AP 73 
2011-07-06 17:16:38 nume8  tel1 cnp SOS BUCURESTI-CIOROGARLA,LOC CIOROGARLA, JUD ILFOV custodie standard 

Dintr-un fisier de genul asta eu pot extrage numele, data, telefoanele, cnp-ul, si ultimele 2 cuvinte care reprezinta o oferta. Problema mea este cum sa extrag eu satul si comuna pe de o parte si strada nr bl ce o mai fi, pentru ca eu trebuie sa introduc satul si comuna intr-un camp, si strada si celelalte in alt camp, si judetul in un alt camp. Judetul iar il gasesc usor.

Dupa cum se observa, satele, comunele, nu sunt mereu in acelasi loc si uneori nici nu sunt scrise corect sa le caut pur si simplu dintr-un fisier cu sate.(de asta m-am gandit sa folosesc functia asta postata de mine mai sus pentru a cauta satele si comunele)

[Birkoff]

Distanta Levenstein algoritmul de editare in php exista functie deja implementata

singura problema e ca algoritmul ocupa multe resurse deci trebuie gandit doar daca aveti un hosting care sa permita asa ceva...