Distancia de Levenshtein

[leandro]

Hola buenas tardes para todos, en este momento tenemos la necesidad de comparar un listado de nombres de productos, con la cadena de un nombre de producto, el problema es que la cadena no viene exacta, la idea es que se pueda sugerir la mas cercana posible.

Estuve consultando con ChatGTP y me sugirió que lo podemos hacer utilizando el algoritmo de Levenshtein, incluso nos dio un ejemplo para usarlo con PHP y Python. Le pregunte si lo podíamos hacer con xharbour/harbour y me dice que no hay una librería que lo tenga, pero que podemos hacer el algoritmo en C++, ya que xharbour esta basado en clipper, que a su vez esta basado en c++.

Buscando en Google encontré el mencionado algoritmo escrito en C++.

Code: Select all  Expand view  RUN

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int levenshtein(const string &s1, const string &s2)
{
   int N1 = s1.size();
   int N2 = s2.size();
   int i, j;
   vector<int> T(N2+1);

   for ( i = 0; i <= N2; i++ )
      T[i] = i;

   for ( i = 0; i < N1; i++ )
   {
      T[0] = i+1;
      int corner = i;
      for ( j = 0; j < N2; j++ )
      {
         int upper = T[j+1];
         if ( s1[i] == s2[j] )
            T[j+1] = corner;
         else
            T[j+1] = min(T[j], min(upper, corner)) + 1;
         corner = upper;
      }
   }
   return T[N2];
}
 

https://es.wikipedia.org/wiki/Distancia_de_Levenshtein

De casualidad alguno de los master, nos puede ayudar a traducir ese algoritmo para xharbour/harbour?

ChatGTP nos sugirió este código para hacerlo. Pero salen varios errores.

Code: Select all  Expand view  RUN

//Algoritmo de Levenshtein
FUNCTION LevenshteinDistance(s1, s2)
    LOCAL m, n, matriz, i, j, coste

    m := Len(s1)
    n := Len(s2)
    matriz := Array(m+1, n+1)

    FOR i := 0 TO m
        matriz[i][0] := i
    NEXT

    FOR j := 0 TO n
        matriz[0][j] := j
    NEXT

    FOR i := 1 TO m
        FOR j := 1 TO n
            IF s1[i] <> s2[j]
                coste := 1
            ELSE
                coste := 0
            ENDIF
            matriz[i][j] := Min(matriz[i-1][j] + 1, matriz[i][j-1] + 1, matriz[i-1][j-1] + coste)
        NEXT j
    NEXT i

 RETURN matriz[m][n]

 

Error E0021 Incorrect number of arguments: MIN

De antemano gracias

[groiss]

Buenos días:
Prueba a hacer esta modificación:

Code: Select all  Expand view  RUN

matriz[i][j] := Min(matriz[i-1][j] + 1,Min( matriz[i][j-1] + 1, matriz[i-1][j-1] + coste))

Por otra parte, no estoy seguro pero veo que

Code: Select all  Expand view  RUN

  FOR i := 0 TO m
        matriz[i][0] := i
    NEXT

    FOR j := 0 TO n
        matriz[0][j] := j
    NEXT
 

Y si no recuerdo mal en Harbour el primer elemento de la matriz o array es el 1
Un saludo
José Luis

[leandro]

José Luis, gracias por las sugerencias, fueron realmente útiles. Dejo la función funcionando jejejeje, por si alguien le interesa.

Code: Select all  Expand view  RUN

//Algoritmo de Levenshtein
FUNCTION LevenshteinDistance(s1, s2)
    LOCAL m, n, matriz, i, j, coste, jCn, iCn

    m := Len(s1)
    n := Len(s2)
    matriz := Array(m+1, n+1)

    iCn := 0
    FOR i := 1 TO m+1
        matriz[i][1] := iCn
        iCn++
    NEXT

    jCn := 0
    FOR j := 1 TO n+1
        matriz[1][j] := jCn
        jCn++
    NEXT

    FOR i := 2 TO m+1
        FOR j := 2 TO n+1
            IF substr(s1,i-1,1) != substr(s2,j-1,1)
                coste := 1
            ELSE
                coste := 0
            ENDIF
            matriz[i][j] := Min(matriz[i-1][j] + 1,Min( matriz[i][j-1] + 1, matriz[i-1][j-1] + coste))
        NEXT j
    NEXT i
   
RETURN matriz[m+1][n+1]
 

[George]

Leandro,
la funcion StrDiff(), en xHarbour, te calcula la funcion Levenshtein.

[nageswaragunupudi]

Leandro,
la funcion StrDiff(), en xHarbour, te calcula la funcion Levenshtein.

Yes.
This is the documentation of the function

StrDiff()
Calculates the similarity of two strings.
Syntax
StrDiff( <cString1> , ;
<cString2> , ;
[<nReplace>], ;
[<nDelete>] , ;
[<nInsert>] ) --> nSimilarity

Arguments
<cString1> and <cString2>
Thes are two character strings being compared for their similarity.
<nReplace>
The weighing factor for Replace operations defaults to 3. It can be changed to a numeric value between 0 and 255.
<nDelete>
The weighing factor for Delete operations defaults to 6. It can be changed to a numeric value between 0 and 255. Delete operations are considered the most expensive ones.
<nInsert>
The weighing factor for Insert operations defaults to 1. It can be changed to a numeric value between 0 and 255. Return
The function returns a numeric value indicating the similarity of two character strings.
Description
The function calculates the Levenshtein distance which indicates the similarity of two character strings. The algorithm weighs Delete, Insert and Replace operations required to transform <cString1> into <cString2>. The weighing factors of each operation influence the result. It is assumed that two strings are more similar the smaller the result is.

https://en.wikipedia.org/wiki/Levenshtein_distance

[leandro]

Excelente Mr.Nages

Muchas gracias por la información