algorithm - para - Algoritmos de similitud de cadenas?

distancia de levenshtein java

Question

Necesito comparar 2 cadenas y calcular su similitud, para filtrar una lista de las cadenas más similares.

P.ej. buscar "perro" volvería

1. perro
2. doggone
3. pantano
4. niebla
5. brumoso

P.ej. buscar "crack" volvería

1. grieta
2. cuchufleta
3. estante
4. Jack
5. curandero

He encontrado:

• Azogue
• Metal liquido

¿Conoces algún otro algoritmo de similitud de cadenas?

Answer 1

Podrías hacer esto:

Foreach string in haystack Do offset := -1; matchedCharacters := 0; Foreach char in needle Do offset := PositionInString(string, char, offset+1); If offset = -1 Then Break; End; matchedCharacters := matchedCharacters + 1; End; If matchedCharacters > 0 Then // (partial) match found End; End;

Con los Caracteres coincidentes puede determinar el "grado" de la coincidencia. Si es igual a la longitud de la aguja , todos los caracteres de la aguja también están en cadena . Si también almacena el desplazamiento del primer carácter coincidente, también puede ordenar el resultado por la "densidad" de los caracteres coincidentes al restar el desplazamiento del primer carácter coincidente del desplazamiento del último desplazamiento del carácter coincidente; cuanto menor es la diferencia, más densa es la combinación.

Answer 2

Si el foco está en el rendimiento, implementaría un algoritmo basado en una estructura trie
(funciona bien para encontrar palabras en un texto, o para ayudar a corregir una palabra, pero en su caso puede encontrar rápidamente todas las palabras que contienen una palabra dada o todas menos una letra, por ejemplo).

Por favor, siga primero el enlace de Wikipedia arriba. Tries es el método de clasificación de palabras más rápido ( n palabras, búsqueda s , O ( n ) para crear el trie, O (1) para buscar s (o si lo prefiere, si a es la duración promedio, O ( an ) para el trie y O ( s ) para la búsqueda)).

Una implementación rápida y fácil (para ser optimizada) de su problema (palabras similares) consiste en

• Haga el trie con la lista de palabras, con todas las letras indexadas al frente y atrás (vea el ejemplo a continuación)
• Para buscar s , iterar desde s [0] para encontrar la palabra en el trie, luego s [1] etc ...
• En el trie, si el número de letras encontradas es len ( s ) - k se muestra la palabra, donde k es la tolerancia (falta 1 letra, 2 ...).
• El algoritmo puede extenderse a las palabras en la lista (ver a continuación)

Ejemplo, con las palabras car , vars .

Construyendo el trie (letra grande significa que una palabra termina aquí, mientras que otra puede continuar). El > es posterior al índice (avance) y < es preíndice (retrocede). En otro ejemplo, es posible que tengamos que indicar también la letra inicial, que no se presenta aquí para mayor claridad.
El < y > en C ++ por ejemplo sería Mystruct *previous,*next , que significa de a > c < r , puede ir directamente de a a c , y viceversa, también de a a R

  1.  c < a < R
  2.  a > c < R
  3.    > v < r < S
  4.  R > a > c
  5.        > v < S
  6.  v < a < r < S
  7.  S > r > a > v

Si busca estrictamente el automóvil, el trie le da acceso desde 1. y encuentra el automóvil (también podría haber encontrado todo desde el automóvil , pero también cualquier cosa con el automóvil adentro -no está en el ejemplo-, pero se habría encontrado vicario, por ejemplo). de c > i > v < a < R ).

Para buscar permitiendo la tolerancia errónea / faltante de 1 letra, itere de cada letra de sy cuente el número de letras consecutivas u omitiendo 1 letra que recibe de s en el trie.

buscando car ,

• c : buscando en trie para c < a y c < r (letra faltante en s ). Para aceptar una letra incorrecta en una palabra w , intente saltar en cada iteración la letra incorrecta para ver si ar está detrás, esto es O ( w ). Con dos letras, O ( w ²) etc ... pero se podría agregar otro nivel de índice al trie para tener en cuenta el salto sobre las letras, lo que hace que el trie sea complejo y codicioso con respecto a la memoria.
• a , luego r : lo mismo que arriba, pero buscando hacia atrás también

Esto es solo para dar una idea sobre el principio: el ejemplo anterior puede tener algunos fallos técnicos (lo verificaré de nuevo mañana).

Answer 3

Parece que necesitas algún tipo de combinación difusa. Aquí está la implementación de java de un conjunto de medidas de similitud http://www.dcs.shef.ac.uk/~sam/stringmetrics.html . Aquí hay una explicación más detallada de las métricas de cadena http://www.cs.cmu.edu/~wcohen/postscript/ijcai-ws-2003.pdf depende de cuán difusa y cuán rápida debe ser su implementación.

Answer 4

La distancia de Levenshtein es el algoritmo que recomendaría. Calcula el número mínimo de operaciones que debe hacer para cambiar 1 cadena por otra. Cuantos menos cambios significa que las cadenas son más similares ...

Answer 5

class Program
{ 

static 
 int ComputeLevenshteinDistance(string source, string target){
if ((source == null) || (target == null)) return 0;
if ((source.Length == 0) || (target.Length == 0)) return 0;
if (source == target) return source.Length;

int sourceWordCount = source.Length;
int targetWordCount = target.Length;

int[,] distance = new int[sourceWordCount + 1, targetWordCount + 1];

// Step 2
for (int i = 0; i <= sourceWordCount; distance[i, 0] = i++);
for (int j = 0; j <= targetWordCount; distance[0, j] = j++);

for (int i = 1; i <= sourceWordCount; i++)
{
    for (int j = 1; j <= targetWordCount; j++)
    {
        // Step 3
        int cost = (target[j - 1] == source[i - 1]) ? 0 : 1;

        // Step 4
        distance[i, j] = Math.Min(Math.Min(distance[i - 1, j] + 1, distance[i, j - 1] + 1), distance[i - 1, j - 1] + cost);
    }
}

return distance[sourceWordCount, targetWordCount]; 
}

 static void Main(string[] args){ Console.WriteLine(ComputeLevenshteinDistance ("","StuckOverflow"));
Console.ReadKey();
}
}