distance - Rango de porcentaje de coincidencias usando Levenshtein Distancia coincidente

percentage ranking

Question

Estoy intentando hacer coincidir un solo término de búsqueda con un diccionario de posibles coincidencias utilizando un algoritmo de distancia Levenshtein. El algoritmo devuelve una distancia expresada como el número de operaciones necesarias para convertir la cadena de búsqueda en la cadena coincidente. Quiero presentar los resultados en la lista de porcentajes clasificados de las mejores coincidencias de "N" (por ejemplo, 10).

Dado que la cadena de búsqueda puede ser más larga o más corta que las cadenas de diccionario individuales, lo que sería una lógica apropiada para expresar la distancia como un porcentaje, lo que refutaría cualitativamente qué tan cerca "como porcentaje" es cada resultado de la cadena de consulta, con 100 % que indica una coincidencia exacta.

Consideré las siguientes opciones:

Q = query string
M = matched string
PM = Percentage Match
Option 1. PMi = (1 - Lev_distance(Q, Mi)/Strlen(Q)) * 100
Option 2. PMi = (1 - Lev_distance(Q, Mi)/max(Strlen(Q), strlen(Mi))) * 100

La opción 1 tiene la posibilidad de porcentajes negativos en caso de que la distancia sea mayor que la longitud de la cadena de búsqueda, donde la cadena de coincidencia es larga. Por ejemplo, la consulta "ABC" coincide con "ABC Corp." daría como resultado un porcentaje de coincidencia negativo.

La opción 2 no parece dar un porcentaje consistente a través de un conjunto de Mi, ya que cada cálculo posiblemente usaría un denominador diferente y, por lo tanto, los valores porcentuales resultantes no se normalizarían.

Solo otra forma en la que puedo pensar es abandonar la comparación de lev_distance a cualquiera de las longitudes de las cuerdas, pero en su lugar presentar las distancias comparativas de las coincidencias "N" superiores como un rango de percentil inverso (rango de 100 percentiles).

¿Alguna idea? ¿Hay mejores enfoques? Debo estar perdiendo algo, ya que la distancia Levenshtein es probablemente el algoritmo más común para las coincidencias difusas y este debe ser un problema muy común.

Answer 1

¿Qué pasa con este?

100 - ( ((2*Lev_distance(Q, Mi)) / (Q.length + Mi.length)) * 100 )

Da la misma distancia en (Q, M1) y (Q,M2)

Answer 2

El número máximo de distancia de levenshtein es [l1, l2].max . Yo pienso que es verdad. Pero no deberíamos dividirnos por ello.

gem install levenshtein diff-lcs

Diff::LCS.lcs "abc", "qwer"
=> []
Levenshtein.distance("abc", "qwer").to_f / [3, 4].max
=> 1.0

Diff::LCS.lcs "abc", "cdef"
=> ["c"]
Levenshtein.distance("abc", "cdef").to_f / [3, 4].max
=> 1.0

Diff::LCS.lcs "1234", "34567890"
=> ["3", "4"]
Levenshtein.distance("1234", "34567890").to_f / [4, 8].max
=> 1.0

Levenshtein no parece una manera confiable de comparar cadenas en porcentajes . No quiero tratar cadenas similares como 100% diferentes .

Puedo recomendar solo analizar la diferencia entre cada secuencia y LCS.

def get_similarity(sequence_1, sequence_2)
  lcs_length = Diff::LCS::Internals.lcs(sequence_1, sequence_2).compact.length
  lcs_length.to_f * 2 / (sequence_1.length + sequence_2.length)
end

Answer 3

Esta es esencialmente la opción 2 mencionada en mi pregunta. Sin embargo, déjame demostrar un problema con ese enfoque.

Q = "ABC Corp" (len = 8)
M1 = "ABC"
M2 = "ABC Corporati"
M3 = "ABC Corp"

He elegido M1 y M2 de modo que sus distancias Lev son iguales (5 cada uno). Usando la opción 2, los porcentajes de coincidencia serían

M1 = (1 - 5/8)*100  = 37.5%
M2 = (1 - 5/13)*100 = 61.5%
M3 = 100%

Como puedes ver si presento las coincidencias en ese orden, hay una gran diferencia de rango entre M1 y M2, a pesar de que tienen exactamente la misma distancia de leva. ¿Ves el problema?

Answer 4

Mi enfoque a este problema fue mediante el cálculo de las operaciones máximas permitidas, que es la distancia de Levenshtein. La fórmula que utilicé es:

percent = 0.75; // at least 75% of string must match
maxOperationsFirst = s1.length() - s1.length() * percent;
maxOperationsSecond = s2.length() - s2.length() * percent;
maxOperations = round(min(maxOperationsFirst, maxOperationsSecond));

Calcula el máximo de operaciones para cada cadena, creo que el cálculo es fácil de entender. Utilizo el valor mínimo de ambos resultados y lo redondeo al número entero más cercano. Puede omitir esta parte y usar solo el valor de las operaciones max de cualquiera de las cadenas, realmente depende de sus datos.

Una vez que tenga la cantidad máxima de operaciones, puede compararla con el resultado de levenshtein y determinar si la cadena es aceptable. De esta manera, puede usar cualquier método de levenshtein extendido, por ejemplo , la distancia Damerau-Levenshtein , que cuenta las faltas de ortografía, p . Ej. Test -> tset , solo como 1 operación, lo cual es muy útil cuando se verifica la entrada del usuario donde esas faltas de ortografía ocurren con mucha frecuencia.

Espero que esto te ayude a tener una idea de cómo resolver este problema.

Answer 5

Tuve un problema similar y este hilo me ayudó a encontrar una solución. Espero que pueda ayudar a otros también.

int levDis = Lev_distance(Q, Mi)
int bigger = max(strlen(Q), strlen(Mi))
double pct = (bigger - levDis) / bigger

Debería devolver el 100% si ambas cadenas son exactamente iguales y el 0% si son totalmente diferentes.

(perdon si mi ingles no es tan bueno)

Answer 6

(1 - (levNum / Math.max(s.length,t.length) ) ) *100

debe ser correcto