Porcentaje de coincidencia de coincidencia con Levenshtein Coincidencia de distancia

Estoy intentando hacer coincidir un único término de búsqueda con un diccionario de posibles coincidencias utilizando un algoritmo de distancia de Levenshtein. El algoritmo devuelve una distancia expresada como el número de operaciones requeridas para convertir la cadena de búsqueda en la cadena coincidente. Quiero presentar los resultados en la lista porcentual clasificada de las mejores "N" (digamos 10) coincidencias.Porcentaje de coincidencia de coincidencia con Levenshtein Coincidencia de distancia

Dado que la cadena de búsqueda puede ser más larga o más corta que las cadenas de diccionario individuales, ¿cuál sería una lógica apropiada para expresar la distancia como un porcentaje, lo que reflotaría cualitativamente la cercanía "en porcentaje" de cada resultado cuerda, con 100% que indica una coincidencia exacta.

que considera 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

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

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

Otra manera en que puedo pensar es abandonar la comparación de lev_distance con cualquiera de las longitudes de las cuerdas, pero en su lugar presenta las distancias comparativas de las principales "N" como un rango percentil inverso (rango de 100 percentiles).

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

Fuente

2012-05-01 user1368587

Qué pasa con su primera opción, pero cuando el el resultado es negativo, entonces simplemente devuelve 0? PD: He publicado un problema también aquí http://math.stackexchange.com/questions/1776860/convert-levenshtein-distance-to-percents –

No entendí cuál es el problema con Option2 ya que he implementado exactamente el la misma lógica que describe y parece funcionar correctamente. ¿Puedes por favor explicarlo mejor? – Roberto14

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

debe ser correcta

Fuente

2013-01-09 14:51:50

La pregunta inicial ya tiene esta solución como la "Opción 2". Él está buscando una solución alternativa al problema. –

Esta es esencialmente la opción 2 se ha mencionado en mi pregunta. Sin embargo, permítanme 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 de Lev sean las mismas (5 cada una). El uso de la opción 2, los porcentajes de los partidos serían

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

Como se puede ver si presento los partidos en ese orden, hay una enorme diferencia de rangos entre M1 y M2, a pesar de que tienen exactamente la misma distancia lev. ¿Ves el problema?

Fuente

2013-01-11 01:01:45

Después de un tiempo, supongo que este es el enfoque correcto. Supongamos que tiene cadenas muy cortas cuya LevDisstance es 5. Supongamos que tiene cadenas muy largas cuyo LevDist también es 5. Entonces, es correcto decir que las cadenas más cortas son menos similares que las más largas. –

Tbh, no veo ningún problema allí porque, como dijo @Wan Tanka, la misma distancia a una cadena más larga significa que hay más caracteres que coinciden entre ellos. Por lo tanto, no hay problema y Option2 es una opción válida. – Roberto14

Mi enfoque para este problema fue calculando las operaciones máximas permitidas, que es la distancia Levenshtein. La fórmula que utiliza 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));

Se calcula operaciones máximas para cada cuerda, 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 el valor justo de las operaciones máximas de cualquiera de las cadenas, realmente depende de sus datos.

Una vez que haya obtenido el número máximo de operaciones, puede compararlo con el resultado levenshtein y determinar si la cadena es aceptable. De esta forma puede usar cualquier método levenshtein extendido, por ejemplo Damerau–Levenshtein distance, que cuenta errores ortográficos, p.test -> tset, solo como 1 operación, que es bastante útil cuando se comprueba la entrada del usuario donde esos errores de ortografía ocurren muy a menudo.

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

Fuente

2013-08-14 23:11:45

me parece bien. – tonix

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

Debe devolver 100% si ambas cadenas son exactamente iguales y 0% si son totalmente diferentes.

(lo siento si mi Inglés no es tan bueno)

Fuente

2014-02-11 14:49:52

Esto no es correcto porque da diferentes resultados para '(" ABC Corp "," ABC ")' y '(" ABC Corp "," ABC Corporati ")' –

esto es una respuesta incorrecta. –

¿Qué pasa con éste:

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

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

Fuente

2016-05-08 09:06:52

Porcentaje de coincidencia de coincidencia con Levenshtein Coincidencia de distancia

Respuesta

Cuestiones relacionadas