Coincidencia de texto difuso (oraciones/títulos) en C#

Question

Oye, estoy usando Levenshteins Algoritmo para obtener la distancia entre la cadena de origen y la de destino.

También tengo un método que devuelve un valor de 0 a 1:

/// <summary>
/// Gets the similarity between two strings.
/// All relation scores are in the [0, 1] range, 
/// which means that if the score gets a maximum value (equal to 1) 
/// then the two string are absolutely similar
/// </summary>
/// <param name="string1">The string1.</param>
/// <param name="string2">The string2.</param>
/// <returns></returns>
public static float CalculateSimilarity(String s1, String s2)
{
    if ((s1 == null) || (s2 == null)) return 0.0f;

    float dis = LevenshteinDistance.Compute(s1, s2);
    float maxLen = s1.Length;
    if (maxLen < s2.Length)
        maxLen = s2.Length;
    if (maxLen == 0.0F)
        return 1.0F;
    else return 1.0F - dis / maxLen;
}

pero esto para mí no es suficiente.Porque necesito una forma más compleja de unir dos oraciones.

Por ejemplo, quiero etiquetar automáticamente algo de música, tengo nombres de canciones originales y tengo canciones con basura, como súper calidad, años como 2007, 2008, etcétera etcétera..También algunos archivos acaban de http://basura..thash..nombre_canción_mp3.mp3, otros son normales.Quiero crear un algoritmo que funcione de manera más perfecta que el mío ahora.¿Quizás alguien pueda ayudarme?

aquí está mi algo actual:

/// <summary>
/// if we need to ignore this target.
/// </summary>
/// <param name="targetString">The target string.</param>
/// <returns></returns>
private bool doIgnore(String targetString)
{
    if ((targetString != null) && (targetString != String.Empty))
    {
        for (int i = 0; i < ignoreWordsList.Length; ++i)
        {
            //* if we found ignore word or target string matching some some special cases like years (Regex).
            if (targetString == ignoreWordsList[i] || (isMatchInSpecialCases(targetString))) return true;
        }
    }

   return false;
}

/// <summary>
/// Removes the duplicates.
/// </summary>
/// <param name="list">The list.</param>
private void removeDuplicates(List<String> list)
{
    if ((list != null) && (list.Count > 0))
    {
        for (int i = 0; i < list.Count - 1; ++i)
        {
            if (list[i] == list[i + 1])
            {
                list.RemoveAt(i);
                --i;
            }
        }
    }
}

/// <summary>
/// Does the fuzzy match.
/// </summary>
/// <param name="targetTitle">The target title.</param>
/// <returns></returns>
private TitleMatchResult doFuzzyMatch(String targetTitle)
{
    TitleMatchResult matchResult = null;

   if (targetTitle != null && targetTitle != String.Empty)
   {
       try
       {
           //* change target title (string) to lower case.
           targetTitle = targetTitle.ToLower();

           //* scores, we will select higher score at the end.
           Dictionary<Title, float> scores = new Dictionary<Title, float>();

           //* do split special chars: '-', ' ', '.', ',', '?', '/', ':', ';', '%', '(', ')', '#', '\"', '\'', '!', '|', '^', '*', '[', ']', '{', '}', '=', '!', '+', '_'
           List<String> targetKeywords = new List<string>(targetTitle.Split(ignoreCharsList, StringSplitOptions.RemoveEmptyEntries));

          //* remove all trash from keywords, like super, quality, etc..
           targetKeywords.RemoveAll(delegate(String x) { return doIgnore(x); });
          //* sort keywords.
          targetKeywords.Sort();
        //* remove some duplicates.
        removeDuplicates(targetKeywords);

        //* go through all original titles.
        foreach (Title sourceTitle in titles)
        {
            float tempScore = 0f;
            //* split orig. title to keywords list.
            List<String> sourceKeywords = new List<string>(sourceTitle.Name.Split(ignoreCharsList, StringSplitOptions.RemoveEmptyEntries));
            sourceKeywords.Sort();
            removeDuplicates(sourceKeywords);

            //* go through all source ttl keywords.
            foreach (String keyw1 in sourceKeywords)
            {
                float max = float.MinValue;
                foreach (String keyw2 in targetKeywords)
                {
                    float currentScore = StringMatching.StringMatching.CalculateSimilarity(keyw1.ToLower(), keyw2);
                    if (currentScore > max)
                    {
                        max = currentScore;
                    }
                }
                tempScore += max;
            }

            //* calculate average score.
            float averageScore = (tempScore / Math.Max(targetKeywords.Count, sourceKeywords.Count)); 

            //* if average score is bigger than minimal score and target title is not in this source title ignore list.
            if (averageScore >= minimalScore && !sourceTitle.doIgnore(targetTitle))
            {
                //* add score.
                scores.Add(sourceTitle, averageScore);
            }
        }

        //* choose biggest score.
        float maxi = float.MinValue;
        foreach (KeyValuePair<Title, float> kvp in scores)
        {
            if (kvp.Value > maxi)
            {
                maxi = kvp.Value;
                matchResult = new TitleMatchResult(maxi, kvp.Key, MatchTechnique.FuzzyLogic);
            }
        }
    }
    catch { }
}
//* return result.
return matchResult;
}

Esto funciona normalmente, pero en algunos casos, muchos títulos que deberían coincidir no coinciden...Creo que necesito algún tipo de fórmula para jugar con pesas, etc., pero no se me ocurre ninguna.

¿Ideas?¿Sugerencias?¿Algo?

Por cierto, ya conozco este tema (mi colega ya lo publicó pero no podemos encontrar una solución adecuada para este problema):Algoritmos aproximados de coincidencia de cadenas

Answer 1

Su problema aquí puede ser distinguir entre palabras irrelevantes y datos útiles:

• Rolling_Stones.Lo mejor_de_2003.Wild_Horses.mp3
• Super.Calidad.Caballos_Salvajes.mp3
• Tori_Amos.Caballos_Salvajes.mp3

Es posible que necesites crear un diccionario de palabras irrelevantes para ignorar.Eso parece complicado, pero no estoy seguro de que exista un algoritmo que pueda distinguir entre nombres de bandas/álbumes y ruido.

Answer 2

Un poco antiguo, pero podría resultar útil para futuros visitantes.Si ya estás usando el algoritmo de Levenshtein y necesitas mejorar un poco, describo algunas heurísticas muy efectivas en esta solución:

Obtener la coincidencia de cadena más cercana

La clave es que se te ocurran 3 o 4 (o más) métodos para medir la similitud entre sus frases (la distancia de Levenshtein es solo un método) y luego, utilizando ejemplos reales de cadenas que desea hacer coincidir como similares, ajusta las ponderaciones y combinaciones de esas heurísticas hasta que obtenga algo que maximice el número de coincidencias positivas.Luego usas esa fórmula para todos los partidos futuros y deberías ver excelentes resultados.

Si un usuario está involucrado en el proceso, también es mejor si proporciona una interfaz que le permita ver coincidencias adicionales con un alto rango de similitud en caso de que no estén de acuerdo con la primera opción.

Aquí hay un extracto de la respuesta vinculada.Si finalmente desea utilizar parte de este código tal como está, le pido disculpas de antemano por tener que convertir VBA a C#.

---

Una métrica sencilla, rápida y muy útil.Usando esto, creé dos métricas separadas para evaluar la similitud de dos cadenas.A uno lo llamo "valuePhrase" y al otro lo llamo "valueWords".valuePhrase es solo la distancia de Levenshtein entre las dos frases, y valueWords divide la cadena en palabras individuales, basándose en delimitadores como espacios, guiones y cualquier otra cosa que desee, y compara cada palabra entre sí, resumiendo las más cortas. Distancia de Levenshtein que conecta dos palabras cualesquiera.Básicamente, mide si la información de una "frase" está realmente contenida en otra, como si fuera una permutación de palabras.Pasé unos días como proyecto paralelo ideando la forma más eficiente posible de dividir una cadena en función de delimitadores.

valueWords, valuePhrase y función Split:

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 con las que puedo ejecutar un algoritmo de optimización para lograr la mayor cantidad de coincidencias.La coincidencia difusa de cadenas es, en sí misma, una ciencia difusa, por lo que al crear métricas linealmente independientes para medir la similitud de cadenas y al tener un conjunto conocido de cadenas que deseamos hacer coincidir entre sí, podemos encontrar los parámetros que, para nuestros estilos específicos de cadenas, dan los mejores resultados de coincidencia aproximada.

Inicialmente, el objetivo de la métrica era tener un valor de búsqueda bajo para una coincidencia exacta y valores de búsqueda crecientes para medidas cada vez más permutadas.En un caso poco práctico, esto era bastante fácil de definir usando un conjunto de permutaciones bien definidas y diseñando la fórmula final de manera que tuvieran resultados de valores de búsqueda crecientes según se deseaba.

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

SolicitudPara permitir la optimización de la coincidencia difusa, pondero cada métrica.Como tal, cada aplicación de coincidencia difusa de cadenas 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 ponderaciones:

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

Utilizando un algoritmo de optimización (la red neuronal es mejor aquí porque es un problema discreto y multidimensional), el objetivo ahora es maximizar el número de coincidencias.Creé una función que detecta la cantidad 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 debía coincidir, y se otorgan puntos parciales si hay un empate en la puntuación más baja y la coincidencia correcta se encuentra entre las cadenas coincidentes 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 la cantidad de coincidencias exitosas y esto es lo que le decimos a nuestro problema de optimización que maximice.

Answer 3

Parece que lo que desea puede ser una coincidencia de subcadena más larga.Es decir, en su ejemplo, dos archivos como

Trash..Thash..Song_name_MP3.mp3 y basura..spotch..Song_name_mp3.mp3

terminaría luciendo igual.

Por supuesto, necesitarías algo de heurística allí.Una cosa que puedes intentar es pasar la cuerda por un convertidor Soundex.Soundex es el "códec" que se utiliza para ver si las cosas "suenan" igual (como le dirías a un operador telefónico).Es más o menos una transliteración a media prueba de fonética y mala pronunciación.Definitivamente es peor que la distancia de edición, pero mucho, mucho más barata.(El uso oficial es para nombres y sólo utiliza tres caracteres.Sin embargo, no hay razón para detenerse ahí, simplemente use el mapeo para cada carácter de la cadena.Ver Wikipedia para detalles)

Entonces, mi sugerencia sería sondear las cuerdas, cortar cada una en algunos tramos largos (digamos 5, 10, 20) y luego simplemente mirar los grupos.Dentro de los grupos, puede usar algo más costoso como editar la distancia o la subcadena máxima.

Answer 4

Se ha trabajado mucho sobre un problema algo relacionado con la alineación de la secuencia de ADN (busque "alineación de secuencia local"): el algoritmo clásico es "Needleman-Wunsch" y los modernos más complejos también son fáciles de encontrar.La idea es, similar a la respuesta de Greg, que en lugar de identificar y comparar palabras clave, intente encontrar subcadenas más largas que coincidan libremente dentro de cadenas largas.

Lamentablemente, si el único objetivo es ordenar la música, una serie de expresiones regulares para cubrir posibles esquemas de nombres probablemente funcionarían mejor que cualquier algoritmo genérico.

Answer 5

Hay un repositorio de GitHub implementando varios métodos.