411 votos

Llegar a la más cercana coincidencia con la cadena de

Necesito una manera de comparar varias cadenas a una cadena y devuelve la cadena que se asemeja a esto:

TEST STRING: THE BROWN FOX JUMPED OVER THE RED COW

CHOICE A   : THE RED COW JUMPED OVER THE GREEN CHICKEN
CHOICE B   : THE RED COW JUMPED OVER THE RED COW
CHOICE C   : THE RED FOX JUMPED OVER THE BROWN COW

(Si lo hice correctamente) El más cercano de la cadena a la "CADENA de PRUEBA" debe ser "OPCIÓN C". ¿Cuál es la forma más fácil de hacer esto?

I plan de aplicación de la presente en múltiples idiomas, incluyendo VB.net, Lua, y JavaScript. En este punto, pseudo código es aceptable. Si usted puede proporcionar un ejemplo para un idioma específico, esto es apreciado también!

Gracias si se puede!

978voto

Alain Puntos 10079

Se me presentó con este problema hace aproximadamente un año que cuando vinieron a buscar usuario haya introducido la información acerca de una plataforma petrolera en una base de datos de informaciones diversas. El objetivo era hacer una especie de difusa cadena de búsqueda que podría identificar la base de datos de entrada con los elementos más comunes.

Parte de la investigación supuso la implementación de la distancia de Levenshtein algoritmo, el cual determina cómo muchos de los cambios que deben hacerse a una cadena o una frase para convertirla en otra cadena o una frase.

La aplicación que se me ocurrió fue relativamente sencillo, y que participan de un promedio ponderado de la comparación de la longitud de las dos frases, el número de cambios entre cada frase, y si cada palabra puede ser encontrado en el blanco de la entrada.

El artículo está en un sitio privado así que voy a hacer mi mejor esfuerzo para anexar el correspondiente contenido aquí:


Fuzzy Cadena de adaptación es el proceso de realización de un ser humano como la estimación de la similitud de dos palabras o frases. En muchos casos, implica la identificación de palabras o frases que son más similares entre sí. En este artículo se describe una solución casera a la difusa cadena de problema de coincidencia y de su utilidad en la resolución de una variedad de problemas que nos pueden permitir automatizar tareas que antes requerían tediosa la participación de los usuarios.

Introducción

La necesidad de hacer difusa la cadena coincidente originalmente surgió durante el desarrollo del Golfo de México con la herramienta de validación. Lo que existía era una base de datos de sabe, en el golfo de México plataformas de petróleo y plataformas, y las personas que compran seguros nos daría algún mal escrito información sobre sus activos y tuvimos que coincidir con el de la base de datos de las conocidas plataformas. Cuando hay muy poca información dada, lo mejor que podemos hacer es confiar en una compañía de seguros para "reconocer" a la que se refiere y llamar a la correcta información. Aquí es donde esta solución automatizada viene muy bien.

Pasé un día los métodos de investigación de aproximada de la cadena de coincidencia, y, finalmente, se tropezó con la muy útil a la distancia de Levenshtein algoritmo en Wikipedia.

Aplicación

Después de leer sobre la teoría detrás de ella, he implementado y encontrar maneras de optimizar. Esta es la forma de 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

Sencilla, rápida, y muy útil métrica. Usando esto, he creado dos separar las métricas para la evaluación de la similitud de las dos cadenas. Uno de los que yo llamo "valuePhrase" y que yo llamo "valueWords". valuePhrase es sólo la distancia de Levenshtein entre las dos frases, y valueWords divide la cadena en palabras individuales, basado en los delimitadores, tales como espacios, guiones, y cualquier otra cosa que quisiera, y se compara cada palabra el uno al otro palabra, resumiendo el menor distancia de Levenshtein la conexión de cualquiera de las dos palabras. En esencia, se mide si la información en una 'frase' está realmente contenido en el otro, como una palabra sabia de permutación. Me pasé un par de días como un proyecto paralelo que viene con la forma más eficiente posible de separar una cadena de delimitadores.

valueWords, valuePhrase, y Dividir la función:

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

Las medidas de Similitud

El uso de estas dos métricas, y un tercero que simplemente calcula la distancia entre dos cadenas, tengo una serie de variables que puede ejecutar un algoritmo de optimización para conseguir el mayor número de partidos. Aproximada de la cadena de coincidencia es, en sí mismo, una difusa de la ciencia, y por tanto, por la creación linealmente independientes métricas para la medición de similitud de cadenas, y tener un conocido conjunto de cadenas deseamos partido a cada uno de los otros, podemos encontrar los parámetros que, para nuestros estilos específicos de las cadenas, dar la mejor coincidencia aproximada resultados.

Inicialmente, el objetivo de la métrica era tener un bajo valor de búsqueda de una coincidencia exacta, y el aumento de la búsqueda de valores para cada vez más permutada medidas. En un caso práctico, esto era bastante fácil de definir, mediante un conjunto de permutaciones, y la ingeniería de la final de la fórmula tal que tuvieron el aumento de valores de búsqueda de los resultados deseados.

Fuzzy String Matching Permutations

Fuzzy String Matching Value Phrase

Fuzzy String Matching Value Words

Como se puede ver, los dos últimos indicadores, que son difusos cadena de coincidencia de las métricas, ya tienen una tendencia natural a dar de baja de las puntuaciones para las cadenas que se deben igualar (abajo de la diagonal). Esto es muy bueno.

Aplicación Para permitir la optimización de la coincidencia aproximada, me peso cada métrica. Como tal, cada aplicación difusa de la cadena de coincidencia de peso de los parámetros de forma diferente. La fórmula que define el resultado final es una combinación de las métricas y sus pesos:

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

El uso de un algoritmo de optimización (red neuronal es la mejor porque es un discretos, multi-dimensional problema), el objetivo es maximizar el número de partidos. He creado una función que detecta el número de emparejamientos correctos de cada conjunto el uno al otro, como puede ser visto en este final de captura de pantalla. Una columna o fila recibe un punto si la puntuación más baja se asigna la cadena que estaba destinado a ser igualado, y parcial de puntos se dan si hay un empate en la puntuación más baja, y la coincidencia correcta entre el atado de cadenas coincidentes. Entonces me optimizado. Usted puede ver que una celda verde es la columna que mejor corresponda a la fila actual, y un cuadro azul alrededor de la célula es la fila que coincide mejor con la columna actual. La puntuación en la esquina inferior es aproximadamente el número de coincidencias con éxito y esto es lo que le decimos a nuestro problema de optimización para maximizar.

Fuzzy String Matching Optimized Metric

El algoritmo fue un éxito maravilloso, y la solución de los parámetros de decir mucho acerca de este tipo de problema. Notarás la optimización de la puntuación fue de 44, y la mejor puntuación posible es de 48. Las 5 columnas al final son trampas, y no tenga ninguna coincidencia en absoluto a los valores de la fila. Los señuelos más hay, más difícil será, naturalmente, para encontrar la mejor coincidencia.

En este particular caso similar, la longitud de las cadenas son irrelevantes, porque estamos a la espera de abreviaturas que representan las palabras largas, por lo que el peso óptimo para la longitud es de-0.3, lo que significa que no penalizan a las cadenas que varían en longitud. Podemos reducir la puntuación en previsión de estas abreviaturas, dando más espacio para el parcial palabra partidos para reemplazar de word no coincide con la que simplemente requieren menos sustituciones, porque la cadena es más corta.

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

Finalmente, el min peso está optimizado en 10 y el máximo de peso en 1. Lo que esto significa es que si la mejor de las dos puntuaciones (valor de la frase y el valor de las palabras) no es muy buena, el partido está muy penalizado, pero no mucho penalizar el peor de los dos puntajes. Esencialmente, esto pone el énfasis en exigir a [i] [/i] el valueWord o valuePhrase para tener un buen resultado, pero no tanto. Una especie de "tomar lo que podemos conseguir" mentalidad.

Es realmente fascinante lo que la optimización del valor de estos 5 pesos de decir acerca de la borrosos cadena coincidente teniendo lugar. Completamente diferentes casos prácticos de aproximada de la cadena de coincidencia, estos parámetros son muy diferentes. He usado por 3 aplicaciones separadas hasta el momento.

Mientras no utilizados en la final de la optimización, una evaluación comparativa de la hoja se estableció que los partidos de columnas a sí mismos para todas las resultados perfectos abajo de la diagonal, y permite al usuario cambiar los parámetros para el control de la velocidad a la que las puntuaciones divergen desde 0, y nota innata similitudes entre las frases de búsqueda (que en teoría podría ser utilizado para reducir los falsos positivos en los resultados)

Fuzzy String Matching Benchmark

Otras Aplicaciones

Esta solución tiene el potencial de ser utilizado en cualquier lugar donde el usuario desea disponer de un sistema informático de identificar una cadena en un conjunto de cadenas, donde no existe el partido perfecto. (Como una coincidencia aproximada buscarv para cadenas). Si alguien encontrar este artículo está buscando una funcionalidad similar, siéntase libre de contactar con el autor, para discutir los métodos de catering de la solución para su aplicación en particular.


Así que lo que debemos tomar de esto, es que usted probablemente querrá usar una combinación de alto nivel de la heurística (búsqueda de palabras de una frase en la otra frase, la longitud de ambas frases, etc) junto con la implementación de la distancia de Levenshtein algoritmo. Porque decidir cual es el "mejor" partido es un heurístico (aproximada) determinación - vas a tener que venir con un conjunto de ponderaciones para todas las métricas que pueda venir para determinar la similitud.

Con el conjunto de heurísticas y pesos, tendrá su programa de comparación rápidamente haciendo que las decisiones que usted hubiera hecho.

92voto

Sten L Puntos 1095

Este problema se vuelve todo el tiempo en la bioinformática. El aceptó respuesta anterior (que era genial, por cierto) es conocido en bioinformática como el Needleman-Wunsch (comparar dos cadenas de caracteres) y Smith-Waterman (encontrar un aproximado de subcadena en una cadena más larga) de los algoritmos. Que gran trabajo y han sido caballos de batalla durante décadas.

Pero ¿qué pasa si usted tiene un millón de cadenas a comparar? Eso es un billón de las comparaciones por pares, cada uno de los cuales es O(n*m)! Los modernos secuenciadores de ADN generar fácilmente un mil millones de secuencias cortas de ADN, cada uno de aproximadamente 200 ADN "cartas" de largo. Normalmente, queremos encontrar, para cada cadena, el mejor del partido contra el genoma humano (3 mil millones de letras). Claramente, la Needleman-Wunsch algoritmo y sus familiares no hacer.

Este así llamado "problema de alineación" es un campo activo de investigación. La mayoría de los algoritmos populares son actualmente capaces de encontrar inexacta a los partidos entre los 1 mil millones de cadenas cortas y el genoma humano en cuestión de horas razonables de hardware (es decir, ocho núcleos y 32 GB de RAM).

La mayoría de estos algoritmos funcionan por encontrar rápidamente a corto coincidencias exactas (semillas) y, a continuación, su extensión a la totalidad de la cadena utilizando un algoritmo más lento (por ejemplo, el de Smith-Waterman). La razón por la que esto funciona es que en realidad estamos sólo interesados en un par de cerrar los partidos, por lo que vale la pena deshacerse de la 99.9...% de las parejas que no tienen nada en común.

¿Cómo encontrar coincidencias exactas ayuda para encontrar inexacta partidos? Bien, decir que sólo permite a una sola diferencia entre la consulta y el destino. Es fácil ver que esta diferencia debe ocurrir, ya sea en la derecha o a la izquierda de la mitad de la consulta, y así la otra mitad debe coincidir exactamente. Esta idea puede extenderse a varios desajustes y es la base para el ELAND algoritmo que se utiliza normalmente con Illumina secuenciadores de ADN.

Hay muchos muy buenos algoritmos para hacer cadena exacta coincidencia. Dada una cadena de consulta de la longitud de 200, y una cadena de longitud 3 millones de euros (el genoma humano), queremos encontrar algún lugar en el destino donde hay una subcadena de longitud k que coincide con una subcadena de la consulta exactamente. Un método sencillo es empezar por la indexación de la meta: tomar todas las k-largo subcadenas, ponerlos en una matriz y ordenarlas. A continuación, tomar cada una de las k-largo de la cadena de la consulta y la búsqueda de la ordenada índice. Ordenación y búsqueda puede ser hecha en O(log n) tiempo.

Pero de almacenamiento puede ser un problema. Un índice de los 3 mil millones de carta de destino necesitaría tener 3 millones de punteros y 3 mil millones de k-palabras largas. Parece difícil de encajar esto en menos de varias decenas de gigabytes de memoria RAM. Pero sorprendentemente nos puede ser de gran comprimir el índice, usando el Burrows-Wheeler transformar, y será así que se puede consultar de manera eficiente. Un índice del genoma humano puede caber en menos de 4 GB de RAM. Esta idea es la base de la popular secuencia de alineadores tales como la Corbata de moño y BWA.

Alternativamente, se puede utilizar un sufijo de la matriz, que almacena sólo los punteros, sin embargo, representa simultánea de un índice de todos los sufijos en la cadena de destino (esencialmente, una simultánea del índice para todos los valores posibles de k; lo mismo es cierto de la Burrows-Wheeler transformar). Un sufijo índice de la matriz del genoma humano tendrá 12 GB de memoria RAM, si usamos punteros de 32 bits.

Los enlaces contienen una gran cantidad de información y enlaces a principal trabajos de investigación. El ELAND va el enlace a un PDF muy útil figuras que ilustran los conceptos involucrados, y muestra cómo tratar con las inserciones y eliminaciones.

Por último, aunque estos algoritmos tienen básicamente resuelto el problema de la (re), la secuenciación de una sola genomas humanos (un mil millones de cadenas cortas), tecnología de secuenciación de ADN mejora aún más rápido que la ley de Moore, y nos estamos acercando rápidamente billones de letras de conjuntos de datos. Por ejemplo, actualmente hay proyectos en marcha para la secuenciación de los genomas de 10,000 especies de vertebrados, cada una mil millones de letras de largo más o menos. Naturalmente, vamos a querer hacer parejas inexactitud de la cadena de coincidencia en los datos...

30voto

adorablepuppy Puntos 827

I concurso de que la opción B es la más cercana a la cadena de prueba, ya que sólo 4 de los personajes(y 2 eliminaciones) de la cadena original. Mientras que usted vea C como más cerca, ya que incluye tanto el marrón y el rojo. Sería, sin embargo, tiene una mayor distancia de edición.

Existe un algoritmo de Distancia de Levenshtein , que mide la distancia de edición entre dos entradas.

Aquí está una herramienta para que el algoritmo.

  1. Las tasas de elección como una distancia de 15.
  2. Las tasas de la opción B como una distancia de 6.
  3. Las tasas de elección C como una distancia de 9.

EDIT: lo Siento, sigo mezcla de cadenas en la levenshtein de la herramienta. Actualizado a las respuestas correctas.

19voto

Mud Puntos 12084

Lua aplicación, para la posteridad:

function levenshtein_distance(str1, str2)
    local len1, len2 = #str1, #str2
    local char1, char2, distance = {}, {}, {}
    str1:gsub('.', function (c) table.insert(char1, c) end)
    str2:gsub('.', function (c) table.insert(char2, c) end)
    for i = 0, len1 do distance[i] = {} end
    for i = 0, len1 do distance[i][0] = i end
    for i = 0, len2 do distance[0][i] = i end
    for i = 1, len1 do
        for j = 1, len2 do
            distance[i][j] = math.min(
                distance[i-1][j  ] + 1,
                distance[i  ][j-1] + 1,
                distance[i-1][j-1] + (char1[i] == char2[j] and 0 or 1)
                )
        end
    end
    return distance[len1][len2]
end

14voto

jseabold Puntos 2325

Usted podría estar interesado en este blog.

http://seatgeek.com/blog/dev/fuzzywuzzy-fuzzy-string-matching-in-python

Fuzzywuzzy es una biblioteca de Python que proporciona una fácil distancia a medidas tales como la distancia de Levenshtein para la cadena coincidente. Está construido en la parte superior de difflib en el estándar de la biblioteca y hacer uso de la implementación en C de Python-levenshtein si está disponible.

http://pypi.python.org/pypi/python-Levenshtein/

Iteramos.com

Iteramos es una comunidad de desarrolladores que busca expandir el conocimiento de la programación mas allá del inglés.
Tenemos una gran cantidad de contenido, y también puedes hacer tus propias preguntas o resolver las de los demás.

Powered by:

X