Algoritmos de similitud de cadenas?

Question

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

Por ejemplo. buscar "perro" volvería

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

Ej. la búsqueda de "crack" se volvería

1. grieta
2. chiste
3. estante
4. jack
5. charlatán

me he encontrado:

• QuickSilver
• LiquidMetal

¿Conoce alguna algoritmos más similitud de cadenas?

Answer 1

Parece que necesita algún tipo de combinación difusa. Aquí está la implementación de Java de algún conjunto de métricas 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, esto depende de cuán difusa y cuán rápida debe ser su implementación.

Answer 2

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

Answer 3

Usted puede hacer esto:

 
ForeachstringinhaystackDo 
    offset := -1; 
    matchedCharacters := 0; 
    ForeachcharinneedleDo 
     offset := PositionInString(string, char, offset+1); 
     Ifoffset = -1 Then 
      Break; 
     End; 
     matchedCharacters := matchedCharacters + 1; 
    End; 
    IfmatchedCharacters > 0 Then 
     // (partial) match found 
    End; 
End; 

Con matchedCharacters se puede determinar el “grado” del partido. Si es igual a la longitud de aguja, todos los caracteres en 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 restando el desplazamiento del primer carácter coincidente del desplazamiento del último carácter coincidente offset; cuanto menor es la diferencia, más densa es la combinación.

Answer 4

Si la atención se centra en el rendimiento, que implementaría un algoritmo basado en una estructura trie
(funciona bien para encontrar las palabras en un texto, o para ayudar a corregir una palabra, pero en su caso para encontrar rápidamente todas las palabras que contiene una palabra dada o todas menos una letra, por ejemplo).

Siga primero el enlace de la wikipedia arriba.Tries son las palabras más rápido método de clasificación (n palabras, la búsqueda s, O (n) para crear el trie, O (1) para buscar s (o si se prefiere, si un es el longitud promedio, O (y) para el trie y O (s) para la búsqueda)).

Una aplicación rápida y fácil (para ser optimizado) de su problema (palabras similares) se compone de

• Hacer el trie con la lista de palabras, que tiene todas las cartas en un índice frontal y posterior (ver el siguiente ejemplo)
• para buscar s, iterar desde s [0] para encontrar la palabra en el trie, entonces s [1], etc ...
• En el trie, si el número de letras encontradas es len (s) - k aparece la palabra, donde k es la tolerancia (falta 1 letra, 2 ...).
• El algoritmo se puede extender a las palabras en la lista (ver más abajo)

ejemplo, con las palabras car, vars.

Construyendo el trie (una letra grande significa una palabra termina aquí, mientras que otra puede continuar). El > es post-index (seguir adelante) y < es pre-index (ir hacia atrás). En otro ejemplo, es posible que tengamos que indicar también la letra inicial, que no se presenta aquí para mayor claridad.
La < y > en C++, por ejemplo, sería Mystruct *previous,*next, el significado de a > c < r, puede ir directamente a-c, y en sentido inverso, también 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 

buscando estrictamente para coche el trie le da acceso a 1., y usted se encuentra coche (que habría encontrado también todo lo que empieza con coche, sino también nada con el coche en el interior - que es no en el ejemplo, pero vicar por ejemplo se habría encontrado en c > i > v < a < R).

Para buscar permitiendo al mismo tiempo 1-letra equivocada tolerancia/faltante, iterar por cada letra del s y, contar el número de consecutivo - o saltándose 1 letra - las cartas que recibe de s en el trie .

buscando car,

• c: buscar el trie para c < a y c < r (letra que falta 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 saltar sobre letras, lo que hace que el trie sea complejo y codicioso con respecto a la memoria.
• a, entonces r: igual que el anterior, pero buscando hacia atrás, así

Esto es sólo para dar una idea sobre el principio - el ejemplo anterior puede tener algunos problemas técnicos (Voy a comprobar de nuevo mañana).

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 ("Stackoverflow","StuckOverflow")); 
Console.ReadKey(); 
} 
}