c++ - sort - string reverse c#
Algoritmo de cadena similar (9)
Estoy buscando un algoritmo, o al menos una teoría de operación sobre cómo encontrarías texto similar en dos o más cadenas diferentes ...
Al igual que la pregunta planteada aquí: Algoritmo para encontrar artículos con texto similar , con la diferencia de que mis cadenas de texto solo serán un puñado de palabras.
Como decir que tengo una cuerda: "En el cielo azul claro" y estoy haciendo una comparación con las dos cadenas siguientes: "El color es azul cielo" y "En el cielo azul claro"
Estoy buscando un algoritmo que pueda usarse para hacer coincidir el texto en los dos, y decidir qué tan cerca coinciden. En mi caso, la ortografía y la puntuación serán importantes. No quiero que afecten la capacidad de descubrir el texto real. En el ejemplo anterior, si la referencia de color se almacena como "azul celeste", quiero que aún pueda coincidir. Sin embargo, la tercera cadena de la lista debe ser una MEJOR coincidencia con la segunda, etc.
Estoy seguro de que lugares como Google probablemente utilicen algo similar con la función "Quisiste decir:" ...
* EDIT *
Al hablar con un amigo, trabajó con un tipo que escribió un artículo sobre este tema. Pensé que podría compartirlo con todos leyendo esto, ya que hay algunos métodos y procesos realmente buenos descritos en él ...
Aquí está el enlace a su artículo , espero que sea útil para quienes leen esta pregunta, y sobre el tema de algoritmos de cadenas similares.
Es posible que desee buscar en los algoritmos utilizados por los biólogos para comparar las secuencias de ADN, ya que tienen que hacer frente a muchas de las mismas cosas (pueden faltar trozos, o se han insertado, o simplemente se han movido a una posición diferente en la cadena.
El algoritmo de Smith-Waterman sería un ejemplo que probablemente funcionaría bastante bien, aunque podría ser demasiado lento para sus usos. Aunque podría darte un punto de partida.
La dificultad sería hacer coincidir las cadenas semánticamente.
Podría generar algún tipo de valor basado en las propiedades léxicas de la cadena. por ejemplo, bot tienen azul, y cielo, y están en la misma oración, etc., etc. Pero no manejará los casos donde "el jean de Sky es azul", o alguna otra construcción inglesa de bola extraña que usa las mismas palabras, pero necesitarías analizar la gramática inglesa ...
Para hacer algo más allá de la similitud léxica, necesitarías ver el procesamiento del lenguaje natural, y no va a haber un solo algoritmo que pueda resolver tu problema.
Posible enfoque:
Construya un diccionario con una clave de cadena de "palabra1 | palabra2" para todas las combinaciones de palabras en la cadena de referencia . Una combinación única puede suceder varias veces, por lo que el valor del diccionario debe ser una lista de números, cada uno representando la distancia entre las palabras en la cadena de referencia.
Cuando haga esto, habrá duplicación aquí: para cada entrada del diccionario "word1 | word2", habrá una entrada "word2 | word1" con la misma lista de valores de distancia, pero negada.
Para cada combinación de palabras en la cadena de comparación (palabras 1 y 2, palabras 1 y 3, palabras 2 y 3, etc.), verifique las dos claves (palabra1 | palabra2 y palabra2 | palabra1) en la cadena de referencia y encuentre la más cercana valor a la distancia en la cadena actual. Agregue el valor absoluto de la diferencia entre la distancia actual y la distancia más cercana a un contador.
Si la distancia de referencia más cercana entre las palabras es en la dirección opuesta (palabra2 | palabra1) como la cadena de comparación, es posible que desee ponderarla más pequeña que si el valor más cercano estuviera en la misma dirección en ambas cadenas.
Cuando hayas terminado, divide la suma por el cuadrado de la cantidad de palabras en la cadena de comparación.
Esto debería proporcionar algún valor decimal que represente qué tan cerca cada palabra / frase coincide con alguna palabra / frase en la cadena original.
Por supuesto, si la cadena original es más larga, no dará cuenta de eso, por lo que puede ser necesario calcular ambas direcciones (utilizando una como referencia, luego la otra) y promediarlas.
No tengo absolutamente ningún código para esto, y probablemente reinventé una rueda muy tosca. YMMV.
Una forma (aunque quizás sea más adecuado un algoritmo de tipo de revisión ortográfica) es la "distancia de edición", es decir, calcular cuántas ediciones se necesitan para transformar una cadena en otra. Una técnica común se encuentra aquí:
Una forma de determinar una medida de "similitud general sin respeto al orden" es utilizar algún tipo de distancia basada en la compresión . Básicamente, la forma en que funcionan la mayoría de los algoritmos de compresión (por ejemplo, gzip ) es escanear a lo largo de una cadena buscando segmentos de cuerda que aparecieron antes; cada vez que se encuentra un segmento, se reemplaza por un par (desplazamiento, longitud) que identifica segmento para usar. Puede usar medidas de cómo se comprimen dos cadenas para detectar similitudes entre ellas.
Supongamos que tiene una función string comp(string s) que devuelve una versión comprimida de s . A continuación, puede usar la siguiente expresión como "puntuación de similitud" entre dos cadenas s y t :
len(comp(s)) + len(comp(t)) - len(comp(s . t))
donde . se toma como una concatenación. La idea es que estés midiendo cuánto más puedes comprimir mirando primero. Si s == t , entonces len(comp(s . t)) apenas será más grande que len(comp(s)) y obtendrás un puntaje alto, mientras que si son completamente diferentes, len(comp(s . t)) estará muy cerca de len(comp(s) + comp(t)) y obtendrá un puntaje cercano a cero. Los niveles intermedios de similitud producen puntajes intermedios.
En realidad, la siguiente fórmula es aún mejor ya que es simétrica (es decir, la puntuación no cambia dependiendo de qué cadena es s y cuál es t ):
2 * (len(comp(s)) + len(comp(t))) - len(comp(s . t)) - len(comp(t . s))
Esta técnica tiene sus raíces en la teoría de la información.
Ventajas: buenos algoritmos de compresión ya están disponibles, por lo que no es necesario hacer mucha codificación, y se ejecutan en tiempo lineal (o casi) para que sean rápidos. Por el contrario, las soluciones que involucran todas las permutaciones de palabras crecen súper exponencialmente en el número de palabras (aunque es cierto que eso puede no ser un problema en su caso ya que usted dice que sabe que solo habrá un puñado de palabras).
La distancia de Levenshtein no funcionará completamente, porque quiere permitir reajustes. Creo que tu mejor opción será encontrar la mejor reorganización con distancia levenstein como costo para cada palabra.
Para encontrar el costo de la reorganización, un poco como el problema de clasificación de panqueques . Por lo tanto, puede permutar todas las combinaciones de palabras (filtrando las coincidencias exactas), con cada combinación de otras cadenas, tratando de minimizar una combinación de distancia permuta y distancia Levenshtein en cada par de palabras.
editar: Ahora que tengo un segundo, puedo publicar un ejemplo rápido (todas las ''mejores'' conjeturas están en inspección y no ejecutando realmente los algoritmos):
original strings | best rearrangement w/ lev distance per word
Into the clear blue sky | Into the c_lear blue sky
The color is sky blue | is__ the colo_r blue sky
R_dist = dist( 3 1 2 5 4 ) --> 3 1 2 *4 5* --> *2 1 3* 4 5 --> *1 2* 3 4 5 = 3
L_dist = (2D+S) + (I+D+S) (Total Subsitutions: 2, deletions: 3, insertion: 1)
(Observe que todos los volteos incluyen todos los elementos en el rango, y uso rangos donde Xi - Xj = +/- 1)
Otro ejemplo
original strings | best rearrangement w/ lev distance per word
Into the clear blue sky | Into the clear blue sky
In the blue clear sky | In__ the clear blue sky
R_dist = dist( 1 2 4 3 5 ) --> 1 2 *3 4* 5 = 1
L_dist = (2D) (Total Subsitutions: 0, deletions: 2, insertion: 0)
Y para mostrar todas las combinaciones posibles de los tres ...
The color is sky blue | The colo_r is sky blue
In the blue clear sky | the c_lear in sky blue
R_dist = dist( 2 4 1 3 5 ) --> *2 3 1 4* 5 --> *1 3 2* 4 5 --> 1 *2 3* 4 5 = 3
L_dist = (D+I+S) + (S) (Total Subsitutions: 2, deletions: 1, insertion: 1)
De todas formas, si hace que la función de costo sea la segunda opción, tendrá el costo más bajo, ¡que es lo que esperaba!
Tenía un problema similar, necesitaba obtener el porcentaje de caracteres en una cadena que era similar. necesitaba secuencias exactas, por lo que, por ejemplo, "hola señor" y "señor hola", cuando se comparaban, era necesario darme cinco caracteres iguales, en este caso serían los dos "hola". luego tomaría la longitud de las dos cadenas más largas y me daría un porcentaje de lo similares que eran. este es el código que se me ocurrió
int compare(string a, string b){
return(a.size() > b.size() ? bigger(a,b) : bigger(b,a));
}
int bigger(string a, string b){
int maxcount = 0, currentcount = 0;//used to see which set of concurrent characters were biggest
for(int i = 0; i < a.size(); ++i){
for(int j = 0; j < b.size(); ++j){
if(a[i+j] == b[j]){
++currentcount;
}
else{
if(currentcount > maxcount){
maxcount = currentcount;
}//end if
currentcount = 0;
}//end else
}//end inner for loop
}//end outer for loop
return ((int)(((float)maxcount/((float)a.size()))*100));
}
Hay otra manera. Reconocimiento de patrones usando convolución. La imagen A se ejecuta a través de una transformada de Fourier. Imagen B también. Ahora superponiendo F (A) sobre F (B) y luego transformando esta parte posterior, obtendrá una imagen negra con algunos puntos blancos. Esos puntos indican dónde A coincide con B fuertemente. La suma total de puntos indicaría una similitud general. No estoy seguro de cómo ejecutaría una FFT en cadenas, pero estoy bastante seguro de que funcionaría.
No puedo marcar dos respuestas aquí, así que voy a responder y marcar la mía. La distancia de Levenshtein parece ser el método correcto en la mayoría de los casos para esto. Pero, vale la pena mencionar la respuesta de j_random_hackers también. He utilizado una implementación de LZMA para probar su teoría, y demuestra ser una solución de sonido. En mi pregunta original estaba buscando un método para cadenas cortas (de 2 a 200 caracteres), donde funcionará el algoritmo Levenshtein Distance. Pero no se mencionó en la pregunta la necesidad de comparar dos cadenas (más grandes) (en este caso, archivos de texto de tamaño moderado) y realizar una comprobación rápida para ver qué tan similares son las dos. Creo que esta técnica de compresión funcionará bien, pero aún no la he estudiado para determinar en qué punto uno se vuelve mejor que el otro, en términos del tamaño de los datos de muestra y la velocidad / costo de la operación en cuestión. Creo que muchas de las respuestas dadas a esta pregunta son valiosas, y vale la pena mencionarlas, para cualquiera que busque resolver una cadena de ordenes similar a la que estoy haciendo aquí. Gracias a todos por sus excelentes respuestas, y espero que puedan ser utilizadas para servir a los demás también.