Obtener la coincidencia de cadena más cercana

Se me presentó este problema hace aproximadamente un año cuando se trataba de buscar información del usuario ingresada sobre una plataforma petrolera en una base de datos de información diversa. El objetivo era hacer algún tipo de búsqueda de cadenas difusas que pudiera identificar la entrada de la base de datos con los elementos más comunes.

Parte de la investigación consistió en implementar el algoritmo Levenshtein distance , que determina cuántos cambios se deben hacer a una cadena o frase para convertirla en otra cadena o frase. frase.

La implementación que se me ocurrió fue relativamente simple, e implicó una comparación ponderada de la longitud de las dos frases, el número de cambios entre cada frase, y si cada palabra se podía encontrar en la entrada de destino.

El artículo está en un sitio privado, así que haré todo lo posible para agregar los contenidos relevantes aquí:

La coincidencia de cadenas difusas es el proceso de realizar una estimación similar a la humana de la similitud de dos palabras o frases. En muchos casos, implica identificar palabras o frases que son más similares entre sí. Este artículo describe una solución interna al problema de coincidencia de cadenas difusas y su utilidad para resolver una variedad de problemas que nos pueden permitir automatizar tareas que anteriormente requerían la tediosa participación del usuario.

Introducción

La necesidad de hacer coincidencias de cadenas difusas surgió originalmente durante el desarrollo de la herramienta Validador del Golfo de México. Lo que existía era una base de datos de plataformas y plataformas petroleras del golfo de México, y la gente que compraba seguros nos daba información mal escrita sobre sus activos y teníamos que cotejarla con la base de datos de plataformas conocidas. Cuando había muy poca información dada, lo mejor que podíamos hacer es confiar en un asegurador para "reconocer" a la que se referían y llamar a la información adecuada. Aquí es donde esta solución automatizada es útil.

Pasé un día investigando métodos de coincidencia de cadenas difusas, y finalmente se topó con el muy útil algoritmo de distancia de Levenshtein en Wikipedia.

Aplicación

Después de leer sobre la teoría detrás de ella, implementé y encontré formas de optimizarla. Así es como se ve mi código en VBA:

'Calculate the Levenshtein Distance between two strings (the number of insertions,
'deletions, and substitutions needed to transform the first string into the second)
Public Function LevenshteinDistance(ByRef S1 As String, ByVal S2 As String) As Long
    Dim L1 As Long, L2 As Long, D() As Long 'Length of input strings and distance matrix
    Dim i As Long, j As Long, cost As Long 'loop counters and cost of substitution for current letter
    Dim cI As Long, cD As Long, cS As Long 'cost of next Insertion, Deletion and Substitution
    L1 = Len(S1): L2 = Len(S2)
    ReDim D(0 To L1, 0 To L2)
    For i = 0 To L1: D(i, 0) = i: Next i
    For j = 0 To L2: D(0, j) = j: Next j

    For j = 1 To L2
        For i = 1 To L1
            cost = Abs(StrComp(Mid$(S1, i, 1), Mid$(S2, j, 1), vbTextCompare))
            cI = D(i - 1, j) + 1
            cD = D(i, j - 1) + 1
            cS = D(i - 1, j - 1) + cost
            If cI <= cD Then 'Insertion or Substitution
                If cI <= cS Then D(i, j) = cI Else D(i, j) = cS
            Else 'Deletion or Substitution
                If cD <= cS Then D(i, j) = cD Else D(i, j) = cS
            End If
        Next i
    Next j
    LevenshteinDistance = D(L1, L2)
End Function

Simple, rápido y una métrica muy útil. Usando esto, creé dos métricas separadas para evaluar la similitud de dos cadenas. A una la llamo "Valuefrase" y a otra la llamo "valueWords". Valuefrase es solo el Levenshtein distancia entre las dos frases, y valueWords divide la cadena en palabras individuales, basado en delimitadores como espacios, guiones y cualquier otra cosa que desee, y compara cada palabra entre sí, resumiendo la distancia más corta de Levenshtein que conecta dos palabras cualesquiera. Esencialmente, mide si la información en una "frase" está realmente contenida en otra, al igual que una permutación en cuanto a palabras. Pasé unos días como proyecto paralelo ideando la forma más eficiente posible de dividir una cadena basada en delimitadores.

ValueWords, Valuefrase y función Dividida:

Public Function valuePhrase#(ByRef S1$, ByRef S2$)
    valuePhrase = LevenshteinDistance(S1, S2)
End Function

Public Function valueWords#(ByRef S1$, ByRef S2$)
    Dim wordsS1$(), wordsS2$()
    wordsS1 = SplitMultiDelims(S1, " _-")
    wordsS2 = SplitMultiDelims(S2, " _-")
    Dim word1%, word2%, thisD#, wordbest#
    Dim wordsTotal#
    For word1 = LBound(wordsS1) To UBound(wordsS1)
        wordbest = Len(S2)
        For word2 = LBound(wordsS2) To UBound(wordsS2)
            thisD = LevenshteinDistance(wordsS1(word1), wordsS2(word2))
            If thisD < wordbest Then wordbest = thisD
            If thisD = 0 Then GoTo foundbest
        Next word2
foundbest:
        wordsTotal = wordsTotal + wordbest
    Next word1
    valueWords = wordsTotal
End Function

''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
' SplitMultiDelims
' This function splits Text into an array of substrings, each substring
' delimited by any character in DelimChars. Only a single character
' may be a delimiter between two substrings, but DelimChars may
' contain any number of delimiter characters. It returns a single element
' array containing all of text if DelimChars is empty, or a 1 or greater
' element array if the Text is successfully split into substrings.
' If IgnoreConsecutiveDelimiters is true, empty array elements will not occur.
' If Limit greater than 0, the function will only split Text into 'Limit'
' array elements or less. The last element will contain the rest of Text.
''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
Function SplitMultiDelims(ByRef Text As String, ByRef DelimChars As String, _
        Optional ByVal IgnoreConsecutiveDelimiters As Boolean = False, _
        Optional ByVal Limit As Long = -1) As String()
    Dim ElemStart As Long, N As Long, M As Long, Elements As Long
    Dim lDelims As Long, lText As Long
    Dim Arr() As String

    lText = Len(Text)
    lDelims = Len(DelimChars)
    If lDelims = 0 Or lText = 0 Or Limit = 1 Then
        ReDim Arr(0 To 0)
        Arr(0) = Text
        SplitMultiDelims = Arr
        Exit Function
    End If
    ReDim Arr(0 To IIf(Limit = -1, lText - 1, Limit))

    Elements = 0: ElemStart = 1
    For N = 1 To lText
        If InStr(DelimChars, Mid(Text, N, 1)) Then
            Arr(Elements) = Mid(Text, ElemStart, N - ElemStart)
            If IgnoreConsecutiveDelimiters Then
                If Len(Arr(Elements)) > 0 Then Elements = Elements + 1
            Else
                Elements = Elements + 1
            End If
            ElemStart = N + 1
            If Elements + 1 = Limit Then Exit For
        End If
    Next N
    'Get the last token terminated by the end of the string into the array
    If ElemStart <= lText Then Arr(Elements) = Mid(Text, ElemStart)
    'Since the end of string counts as the terminating delimiter, if the last character
    'was also a delimiter, we treat the two as consecutive, and so ignore the last elemnent
    If IgnoreConsecutiveDelimiters Then If Len(Arr(Elements)) = 0 Then Elements = Elements - 1

    ReDim Preserve Arr(0 To Elements) 'Chop off unused array elements
    SplitMultiDelims = Arr
End Function

Medidas de Similitud

Usando estas dos métricas, y una tercera que simplemente calcula la distancia entre dos cadenas, tengo una serie de variables que puedo ejecutar un algoritmo de optimización para lograr el mayor número de coincidencias. La coincidencia de cadenas difusas es, en sí misma, una ciencia difusa, y por lo tanto mediante la creación de métricas linealmente independientes para medir cadenas similitud, y teniendo un conjunto conocido de cadenas que deseamos que coincidan entre sí, podemos encontrar los parámetros que, para nuestros estilos específicos de cadenas, dan los mejores resultados de coincidencia difusa.

Inicialmente, el objetivo de la métrica era tener un valor de búsqueda bajo para una coincidencia exacta, y aumentar los valores de búsqueda para medidas cada vez más permutadas. En un caso poco práctico, esto era bastante fácil de definir utilizando un conjunto de permutaciones bien definidas, y la ingeniería de la fórmula final de tal manera que tenían aumentar los resultados de los valores de búsqueda según se desee.

En la captura de pantalla anterior, ajusté mi heurística para llegar a algo que sentí que se ajustaba muy bien a mi diferencia percibida entre el término de búsqueda y el resultado. La heurística que utilicé para Value Phrase en la hoja de cálculo anterior fue =valuePhrase(A2,B2)-0.8*ABS(LEN(B2)-LEN(A2)). Estaba reduciendo efectivamente la penalización de la distancia de Levenstein en un 80% de la diferencia en la longitud de las dos "frases". De esta manera, las" frases " que tienen la misma longitud sufren el pleno pena, pero las "frases" que contienen "información adicional" (más larga) pero aparte de eso todavía comparten en su mayoría los mismos caracteres sufren una pena reducida. Usé la función Value Words tal como está, y luego mi heurística final SearchVal se definió como =MIN(D2,E2)*0.8+MAX(D2,E2)*0.2 - un promedio ponderado. Cualquiera de las dos puntuaciones fue menor obtuvo ponderación 80%, y 20% de la puntuación más alta. Esto era solo una heurística que se adaptaba a mi caso de uso para obtener una buena tasa de coincidencia. Estos pesos son algo que uno podría ajustar para obtener el mejor tasa de coincidencia con sus datos de prueba.

Como puede ver, las dos últimas métricas, que son métricas de coincidencia de cadenas difusas, ya tienen una tendencia natural a dar puntuaciones bajas a las cadenas que están destinadas a coincidir (en la diagonal). Esto es muy bueno.

Solicitud Para permitir la optimización de la coincidencia difusa, peso cada métrica. Como tal, cada aplicación de fuzzy string match puede ponderar los parámetros de manera diferente. La fórmula que define la puntuación final es una simple combinación de las métricas y sus pesos:

value = Min(phraseWeight*phraseValue, wordsWeight*wordsValue)*minWeight
      + Max(phraseWeight*phraseValue, wordsWeight*wordsValue)*maxWeight
      + lengthWeight*lengthValue

Usando un algoritmo de optimización (la red neuronal es mejor aquí porque es un problema discreto y multidimensional), el objetivo es ahora maximizar el número de coincidencias. He creado una función que detecta el número de coincidencias correctas de cada conjunto entre sí, como se puede ver en esta captura de pantalla final. Una columna o fila obtiene un punto si se asigna la puntuación más baja a la cadena que estaba destinada a ser emparejado, y los puntos parciales se dan si hay un empate para la puntuación más baja, y el partido correcto está entre las cadenas emparejadas empatadas. Luego lo optimicé. Puede ver que una celda verde es la columna que mejor coincide con la fila actual, y un cuadrado azul alrededor de la celda es la fila que mejor coincide con la columna actual. La puntuación en la esquina inferior es aproximadamente el número de coincidencias exitosas y esto es lo que le decimos a nuestro problema de optimización para maximizar.

El el algoritmo fue un éxito maravilloso, y los parámetros de la solución dicen mucho sobre este tipo de problema. Notarás que la puntuación optimizada fue de 44, y la mejor puntuación posible es de 48. Las 5 columnas al final son señuelos, y no tienen ninguna coincidencia con los valores de la fila. Cuantos más señuelos haya, más difícil será encontrar la mejor pareja.

En este caso particular de coincidencia, la longitud de las cadenas es irrelevante, porque esperamos abreviaturas que representen más tiempo palabras, por lo que el peso óptimo para la longitud es -0.3, lo que significa que no penalizamos las cuerdas que varían en longitud. Reducimos la puntuación en previsión de estas abreviaturas, dando más espacio para que las coincidencias parciales de palabras sustituyan a las coincidencias que no son de palabras que simplemente requieren menos sustituciones porque la cadena es más corta.

El peso de la palabra es 1.0 mientras que el peso de la frase es solo 0.5, lo que significa que penalizamos las palabras enteras que faltan en una cadena y valoramos más la frase entera intacta. Esto es útil porque muchas de estas cadenas tienen una palabra en común (el peligro) donde lo que realmente importa es si la combinación (región y peligro) se mantienen o no.

Finalmente, el peso mínimo se optimiza a 10 y el peso máximo a 1. Lo que esto significa es que si el mejor de los dos resultados (frase de valor y palabras de valor) no es muy bueno, el partido se penaliza en gran medida, pero no penalizamos en gran medida el peor de los dos resultados. Esencialmente, esto pone énfasis en requerir ya sea la valueWord o Valuefrase para tener una buena puntuación, pero no ambas. Una especie de mentalidad de "tomar lo que podemos conseguir".

Es realmente fascinante lo que el valor optimizado de estos 5 pesos dicen sobre el tipo de coincidencia de cadena difusa que tiene lugar. Para casos prácticos completamente diferentes de coincidencia de cadenas difusas, estos parámetros son muy diferentes. Lo he usado para 3 aplicaciones separadas hasta ahora.

Mientras que no se utilizó en la optimización final, una hoja de referencia fue establecido que coincide con las columnas a sí mismos para todos los resultados perfectos en la diagonal, y permite al usuario cambiar los parámetros para controlar la velocidad a la que las puntuaciones divergen de 0, y nota similitudes innatas entre las frases de búsqueda (que en teoría podría ser utilizado para compensar los falsos positivos en los resultados)

Otras solicitudes

Esta solución tiene potencial para ser utilizada en cualquier lugar donde el usuario desee que un sistema informático identifique una cadena conjunto de cuerdas donde no hay coincidencia perfecta. (Como un vlookup de coincidencia aproximada para cadenas).

Entonces, lo que debes tomar de esto, es que probablemente quieras usar una combinación de heurística de alto nivel (encontrar palabras de una frase en la otra frase, longitud de ambas frases, etc.) junto con la implementación del algoritmo de distancia de Levenshtein. Porque decidir cuál es el "mejor" partido es una determinación heurística (difusa) - usted tendrá que llegar a un conjunto de pesos para cualquier métrica que se le ocurra para determinar la similitud.

Con el conjunto apropiado de heurísticas y pesos, tendrá su programa de comparación tomando rápidamente las decisiones que habría tomado.