Club Delphi  
    FTP   CCD     Buscar   Trucos   Trabajo   Foros

Retroceder   Foros Club Delphi > Otros temas > Trucos
Registrarse FAQ Miembros Calendario Guía de estilo Temas de Hoy

Los mejores trucos

Respuesta
 
Herramientas Buscar en Tema Desplegado
  #1  
Antiguo 26-07-2007
Avatar de Héctor Randolph
[Héctor Randolph] Héctor Randolph is offline
Miembro Premium
 
Registrado: dic 2004
Posts: 882
Poder: 20
Héctor Randolph Va por buen camino
Distancia entre palabras (Algoritmo de Levenshtein)

Se le llama Distancia de Levenshtein o distancia de edición al número mínimo de operaciones requeridas para transformar una cadena de caracteres en otra.

Es útil en programas que determinan cuán similares son dos cadenas de caracteres, como es el caso de los correctores de ortografía.

Por ejemplo, la distancia de Levenshtein entre "kitten" y "sitting" es de 3 porque se necesitan al menos tres ediciones elementales para cambiar uno en el otro.

1. kitten ? sitten (sustitución de 'k' por 's')
2. sitten ? sittin (sustitución de 'e' por 'i')
3. sittin ? sitting (inserción de 'g' al final)


Código Delphi [-]
function DistanciaLevenshtein(Str1, Str2: String): Integer;
var
  d : array of array of Integer;
  Len1, Len2 : Integer;
  i, j, cost: Integer;
begin
  Len1:=Length(Str1);
  Len2:=Length(Str2);
  SetLength(d,Len1+1);
  for i := Low(d) to High(d) do
    SetLength(d[i],Len2+1);

  for i := 0 to Len1 do
    d[i,0]:=i;

  for j := 0 to Len2 do
    d[0,j]:=j;

  for i:= 1 to Len1 do
    for j:= 1 to Len2 do
    begin
      if Str1[i]=Str2[j] then
        cost:=0
      else
        cost:=1;
      d[i,j]:= Min(d[i-1, j] + 1,     // costo de borrar,
                   Min(d[i, j-1] + 1, // costo de insertar
                       d[i-1, j-1] + cost));   // costo de sustituir                            
    end;
  Result:=d[Len1,Len2];
end;

Ejemplo de uso:
Código Delphi [-]
  ShowMessageFmt('La distancia entre kitten y sitting es : %d',[DistanciaLevenshtein('kitten','sitting')]);
Responder Con Cita
  #2  
Antiguo 27-07-2007
Avatar de Delphius
[Delphius] Delphius is offline
Miembro Premium
 
Registrado: jul 2004
Ubicación: Salta, Argentina
Posts: 5.582
Poder: 26
Delphius Va camino a la fama
Hola Hector.
De curioso pasé por aquí para ver de que se trata, y veo que es un algoritmo relativamente sencillo... he notado que te basaste en el contenido de wikipedia.
¿Por casualidad no sabes si es válido para cualquier idioma?¿O sólo funciona para el inglés?
Responder Con Cita
  #3  
Antiguo 27-07-2007
Avatar de roman
roman roman is offline
Moderador
 
Registrado: may 2003
Ubicación: Ciudad de México
Posts: 20.269
Poder: 10
roman Es un diamante en brutoroman Es un diamante en brutoroman Es un diamante en bruto
No creo que dependa del idioma porque, como explica Héctor, el algoritmo sólo mide cuántas transformaciones hay que hacer para pasar de una cadena a otra, y las transformaciones son meras operaciones entre caracteres, tal como se indica en el código: borrar, insertar, sustituir.

Muy bonita esta función. Por cierto, la nomenclatura "distancia" es realmente adecuada, ya que la función cumple las tres propiedades básicas de una métrica:

1. Reflexividad: d(S, T) = 0 si y sólo si S = T
2. Simetría: d(S, T) = d(T, S)
3. Desigualdad del triángulo: d(A, B) <= d(A, C) + d(C, B)
Responder Con Cita
  #4  
Antiguo 27-07-2007
Avatar de Héctor Randolph
[Héctor Randolph] Héctor Randolph is offline
Miembro Premium
 
Registrado: dic 2004
Posts: 882
Poder: 20
Héctor Randolph Va por buen camino
Hola Delphius, efectivamente el texto es extraído de Wikipedia, de hecho, lo que hice fue agregar en la Wikipedia el código en Delphi ya que no existía y después lo publiqué acá.
Responder Con Cita
  #5  
Antiguo 27-07-2007
Avatar de Delphius
[Delphius] Delphius is offline
Miembro Premium
 
Registrado: jul 2004
Ubicación: Salta, Argentina
Posts: 5.582
Poder: 26
Delphius Va camino a la fama
Gracias por las aclaraciones roman y hector.
Buscando un poco y leyendo me doy conque lo que hace es algo similar al algoritmo Huggman (o algo así), que lo que permite es calcular la cantidad de bits que varían entre un conjunto y otro. Tengo entendido que se usa (Huggman)(o mejor dicho se usaba) para calcular y determinar si se producían errores en la transmisión de información en las redes.
Me mareaba el hecho de que la palabra usada en el ejemplo no sea castellana...
Responder Con Cita
Respuesta



Normas de Publicación
no Puedes crear nuevos temas
no Puedes responder a temas
no Puedes adjuntar archivos
no Puedes editar tus mensajes

El código vB está habilitado
Las caritas están habilitado
Código [IMG] está habilitado
Código HTML está deshabilitado
Saltar a Foro


La franja horaria es GMT +2. Ahora son las 01:20:39.


Powered by vBulletin® Version 3.6.8
Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
Traducción al castellano por el equipo de moderadores del Club Delphi
Copyright 1996-2007 Club Delphi