Fuzzy-text (Sätze/Titel) matching in C#

Question

Hey, ich bin mit Levenshteins Algorithmus, um die Entfernung zwischen Quell-und Ziel-string.

auch ich habe die Methode liefert den Wert von 0 bis 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;
}

aber das ist für mich nicht genug.Da brauche ich mehr komplexe Weise zu entsprechen zwei Sätzen.

Zum Beispiel möchte ich automatisch tag der Musik, ich habe ursprünglichen song-Namen, und ich habe songs mit Müll, wie super, Qualität, Jahren wie 2007, 2008, usw..usw..auch einige Dateien haben nur http://trash..thash..song_name_mp3.mp3, andere sind normal.Ich will, einen Algorithmus zu kreieren, die einfach nur vollkommener, als mir jetzt..Vielleicht jemand kann mir helfen?

hier ist meine aktuelle algo:

/// <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;
}

Dies funktioniert normalerweise, aber nur in einigen Fällen, eine Menge Titel, die sollte mit dem übereinstimmen, nicht übereinstimmen...Ich glaube, ich brauche eine Art von Formel zu spielen, mit gewichten und etc, aber ich kann nicht von einem denken..

Ideen?Anregungen?Algos?

durch die Art und Weise, die ich schon weiß, das Thema (Mein Kollege schon geschrieben, aber wir können nicht kommen mit eine richtige Lösung für dieses problem.):Ungefähre string-matching-algorithmen

Answer 1

Ihr problem hier kann die Unterscheidung zwischen Füllwörter und nützliche Daten:

• Rolling_Stones.Best_of_2003.Wild_Horses.mp3
• Super.Qualität.Wild_Horses.mp3
• Tori_Amos.Wild_Horses.mp3

Sie müssen möglicherweise produzieren Wörterbuch der Lärm Worte zu ignorieren.Das scheint umständlich, aber ich bin mir nicht sicher, es gibt einen Algorithmus, der unterscheiden kann zwischen band - /album-Namen und Lärm.

Answer 2

Art von alten, aber Es könnte nützlich sein, um zukünftige Besucher.Wenn Sie bereits mit dem Levenshtein-Algorithmus, und Sie benötigen, um ein wenig besser beschreibe ich einige sehr effektive Heuristiken in dieser Lösung:

Immer die nächstgelegene string match

Der Schlüssel ist, dass Sie kommen mit ein 3-oder 4 (oder mehr) Methoden der Messung der ähnlichkeit zwischen Ihre Sätze (Levenshtein-Distanz ist nur ein Weg) - und dann mit realen Beispielen von Zeichenfolgen, die Sie wollen, um anzupassen, wie ähnlich wird, passen Sie die Gewichtung und Kombinationen dieser Heuristiken, bis Sie etwas bekommen, das maximiert die Anzahl der positiven entspricht.Verwenden Sie dann die Formel für alle zukünftigen entspricht, und Sie sollten sehen, gute Ergebnisse.

Wenn ein Benutzer beteiligt ist, in den Prozess, es ist auch am besten, wenn Sie bieten eine Schnittstelle, die es ermöglicht die Benutzer, um zu sehen, zusätzliche Spiele, die mit einem hohen Ranking in der ähnlichkeit in Fall Sie nicht einverstanden mit die erste Wahl.

Hier ist ein Auszug aus der verknüpften Antwort.Wenn Sie am Ende wollen, verwenden Sie diesen code, wie es ist, ich entschuldige mich im Voraus für das umstellen von VBA zu C#.

---

Einfache, schnelle, und eine sehr nützliche Metrik.Mit diesem, ich habe zwei separate Metriken für die Bewertung der ähnlichkeit von zwei Zeichenfolgen.Die eine nenne ich "valuePhrase" und ich rufe: "valueWords".valuePhrase ist nur die Levenshtein-Distanz zwischen den zwei Phrasen, und valueWords spaltet den string in einzelne Wörter, basierend auf Trennzeichen wie Leerzeichen, Bindestriche, und alles, was Sie möchten, und vergleicht jedes Wort zu jedem anderen Wort, fasst die kürzeste Levenshtein-Distanz die Verbindung von zwei beliebigen Wörtern.Im wesentlichen, es misst, ob die Informationen in einem 'Satz' ist echt enthalten in einer anderen, nur als word-wise permutation.Ich verbrachte ein paar Tage als Nebenprojekt kommt mit möglichst effiziente Art und Weise der Teilung einer saite, basierend auf Trennzeichen.

valueWords, valuePhrase-und Split-Funktion:

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

Maßnahmen der Ähnlichkeit

Mit diesen beiden Metriken, und eine Dritte, die einfach berechnet die Entfernung zwischen zwei Saiten, ich habe eine Reihe von Variablen, die ich ausführen kann, um eine Optimierung Algorithmus zu erreichen die größte Anzahl von Treffern.Fuzzy-string-matching, selbst eine unscharfe Wissenschaft, und so durch die Schaffung von Linear unabhängige Metriken für die Messung der ähnlichkeit von Zeichenketten, und nach einem bekannten Satz von Saiten wir wünschen entsprechen zu jeder andere, den wir finden können die Parameter ein, für unsere styles von strings, die besten fuzzy-match Ergebnisse.

Zunächst ist das Ziel der Metrik wurde, um einen niedrigen Wert für die nach einer exakten übereinstimmung, und die zunehmende Suche Werte für zunehmend permuted Maßnahmen.In einem Fall unpraktisch, dies war relativ einfach zu definieren, mit einer Reihe von gut definierten Permutationen und engineering die endgültige Formel, so dass Sie hatte zunehmenden Suche nach Werten wie gewünscht.

Wie Sie sehen können, in den letzten zwei Metriken, die fuzzy-string-matching-Metriken, die bereits haben eine Natürliche Tendenz zu geben, die niedrige Werte auf strings, die sind gedacht, um entsprechen (nach unten der diagonalen).Das ist sehr gut.

Anwendung Zu ermöglichen die Optimierung von fuzzy-matching, ich Gewicht jeder Metrik.Als solche, jede Anwendung der fuzzy-Textsuche können Gewicht die Parameter anders.Die Formel, die bestimmt das Endergebnis ist einfach eine Kombination der Metriken und deren GEWICHTE:

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

Mithilfe eines Optimierungs-Algorithmus (neuronale Netzwerk ist am besten hier, weil es eine diskrete, multi-dimensionale problem) das Ziel ist jetzt der Maximierung der Anzahl der übereinstimmungen.Erstellt habe ich eine Funktion, die erkennt die Anzahl der korrekten Treffern von jedem Satz, jedem anderen, wie Sie sehen können in diesem letzten screenshot.Eine Spalte oder Zeile, bekommt einen Punkt, wenn die niedrigste Punktzahl zugeordnet, die die Zeichenfolge, die gemeint war zu werden abgestimmt, und teilweise Punkte sind gegeben, wenn es eine Krawatte für die niedrigste Punktzahl, und das richtige Wort unter die gebunden übereinstimmenden Zeichenfolgen.Ich habe dann optimiert es.Sie können sehen, dass eine grüne Zelle der Spalte, die am besten passt die aktuelle Zeile, und eine Blaue Quadrat, um die Zelle ist die Zeile, die besten Spiele der aktuellen Spalte.Die Kerbe in der unteren Ecke etwa, die Zahl der erfolgreichen matches und das ist, was wir sagen unsere Optimierungs-problem zu maximieren.

Answer 3

Es klingt wie das, was Sie wollen kann eine längste Teilstring.Das heißt, in deinem Beispiel zwei Dateien wie

trash..thash..song_name_mp3.mp3 und Müll..spotch..song_name_mp3.mp3

würde am Ende gleich aussieht.

Sie würde müssen einige Heuristiken gibt es, natürlich.Eine Sache, die Sie könnten versuchen, setzen die Schnur durch einen soundex-Konverter.Soundex ist der "codec" verwendet, um zu sehen, wenn die Dinge "sound" das gleiche (wie Sie vielleicht sagen, ein Telefon-operator).Es ist mehr oder weniger eine grobe phonetische und mispronunciation semi-Beweis transliteration.Es ist definitiv ärmer als edit-Distanz, aber viel, viel billiger.(Die offizielle Verwendung ist für den Namen, und verwendet nur drei Zeichen.Es gibt keinen Grund, es zu stoppen, obwohl, verwenden Sie einfach die Zuordnung für jedes Zeichen in der Zeichenfolge.Finden wikipedia für details)

Also mein Vorschlag wäre, soundex-Saiten, hacken jeweils in wenigen Länge Tranchen (sagen wir 5, 10, 20) und dann schaut einfach auf Clustern.Innerhalb der Cluster, die Sie verwenden können, etwas teurer wie edit-Distanz-oder max-Teilstring.

Answer 4

Es gibt eine Menge Arbeit auf etwas Verwandtes problem der DNA-Sequenz-alignment (Suche für "local sequence alignment") - klassisch-Algorithmus, "Needleman-Wunsch" und mehr komplexe moderne auch leicht zu finden.Die Idee ist - ähnlich wie Gregs Antwort - anstatt die Identifizierung und den Vergleich Schlüsselwörter versuchen, zu finden längsten lose übereinstimmende Teilstrings in langen Ketten.

Das wird traurig, wenn das einzige Ziel ist das Sortieren der Musik eine Reihe von regulären Ausdrücken zu decken möglich naming schemes würde wahrscheinlich besser funktionieren, als jeder von generischen algorithmen.

Answer 5

Es ist ein GitHub repo die Implementierung verschiedener Methoden.