Fuzzy-Text (Sätze/Titel) passend in C#

Question

Hey, ich benutze Levenshteins Algorithmus, um den Abstand zwischen Quell- und Zielzeichenfolge zu erhalten.

auch habe ich die Methode Wert von 0 bis 1 zurück:

/// <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. Weil ich einen komplexeren Weg brauche, um zwei Sätze zu finden.

Zum Beispiel möchte ich automatisch etwas Musik Tag, ich habe Namen Original-Song, und ich habe Songs mit Müll, wie super, Qualität, Jahren wie 2007, 2008, etc..etc .. auch einige Dateien habe nur http://trash..thash..song_name_mp3.mp3, andere sind normal. Ich möchte einen Algorithmus erstellen, der jetzt perfekter funktioniert als meiner. Vielleicht kann mir jemand 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 in der Regel aber nur in einigen Fällen, die eine Menge Titel sollte nicht überein, passen ... Ich glaube, ich irgendeine Art von Formel müssen spielen mit Gewichten und etc, aber ich kann nicht an einen denken ..

Ideen? Vorschläge? Algos?

durch die Art, wie ich bereits zu diesem Thema weiß (Mein Kollege gepostet es bereits, aber wir können mit einer richtigen Lösung für dieses Problem nicht.): Approximate string matching algorithms

Answer 1

Ihr Problem hier kann zwischen Füllwörter und nützliche Daten werden zu unterscheiden:

• Rolling_Stones.Best_of_2003.Wild_Horses.mp3
• Super.Quality.Wild_Horses.mp3
• Tori_Amos.Wild_Horses.mp3

Möglicherweise müssen Sie ein Wörterbuch mit zu ignorierenden Geräuschwörtern erstellen. Das klingt klobig, aber ich bin mir nicht sicher, ob es einen Algorithmus gibt, der zwischen Band-/Albumnamen und Rauschen unterscheiden kann.

Answer 2

Es klingt wie das, was Sie wollen, ein längstes Teilzeichen Spiel sein kann . Das heißt, in der beispielsweise zwei Dateien wie

trash..thash..song_name_mp3.mp3 und garbage..spotch..song_name_mp3.mp3

würde am Ende das gleiche suchen.

Sie würden natürlich einige Heuristiken benötigen. Eine Sache, die Sie versuchen könnten, ist, die Zeichenfolge durch einen Soundex-Konverter zu setzen. Soundex ist der "Codec", der verwendet wird, um zu sehen, ob die Dinge "gleich klingen" (wie Sie vielleicht einem Telefonisten sagen). Es ist mehr oder weniger eine halbtransparente phonetische und falsch ausgesprochene Transliteration. Es ist definitiv ärmer als die Entfernung, aber viel, viel billiger. (Die offizielle Verwendung ist für Namen, und verwendet nur drei Zeichen. Es gibt keinen Grund, dort zu stoppen, verwenden Sie jedoch die Zuordnung für jedes Zeichen in der Zeichenfolge. Siehe wikipedia für Details)

Also mein Vorschlag wäre soundex Streichen Sie jede einzelne in ein paar Längen-Tranchen (sagen wir 5, 10, 20) und schauen Sie sich dann Cluster an. Innerhalb von Clustern können Sie etwas teureres verwenden, wie Editierdistanz oder Max-Teilzeichenfolge.

Answer 3

Es gibt eine Menge Arbeit an einem etwas verwandten Problem der DNA-Sequenzausrichtung (Suche nach "Local Sequence Alignment") - klassischer Algorithmus ist "Needleman-Wunsch" und komplexere moderne auch leicht zu finden. Die Idee ist - ähnlich wie bei Gregs Antwort - anstatt Keywords zu identifizieren und zu vergleichen, die am längsten locker passende Teilstrings innerhalb langer Strings finden.

Das ist traurig, wenn das einzige Ziel das Sortieren von Musik ist, würde eine Reihe von regulären Ausdrücken, die mögliche Namensschemata abdecken, wahrscheinlich besser funktionieren als jeder generische Algorithmus.

Answer 4

Art von alt, aber es könnte für zukünftige Besucher nützlich sein. Wenn Sie bereits den Levenshtein-Algorithmus und brauchen ein wenig besser zu gehen, beschreibe ich einige sehr effektive Heuristik in dieser Lösung:

Getting the closest string match

Der Schlüssel ist, dass Sie kommen mit 3 oder 4 (oder more) Methoden zur Messung der Ähnlichkeit zwischen Ihren Phrasen (Levenshtein Abstand ist nur eine Methode) - und dann echte Beispiele für Strings, die Sie als ähnlich übereinstimmen möchten, passen Sie die Gewichtungen und Kombinationen dieser Heuristiken, bis Sie etwas, das die Zahl maximiert von positiven Übereinstimmungen. Dann verwenden Sie diese Formel für alle zukünftigen Spiele und Sie sollten gute Ergebnisse sehen.

Wenn ein Benutzer in den Prozess einbezogen ist, ist es auch am besten, wenn Sie eine Schnittstelle zur Verfügung stellen, die dem Benutzer zusätzliche Übereinstimmungen anzeigt, die eine hohe Ähnlichkeit aufweisen, falls sie der ersten Wahl widersprechen.

Hier ist ein Auszug aus der verknüpften Antwort. Wenn Sie am Ende diesen Code verwenden möchten, entschuldige ich mich im Voraus, dass ich VBA in C# konvertieren muss.

---

Einfach, schnell und eine sehr nützliche Metrik. Mit diesem erstellt ich zwei separate Metriken für die Bewertung der Ähnlichkeit von zwei Strings. Eine, die ich "valuePhrase" nenne, und eine, die ich "valueWords" nenne. valuePhrase ist nur der Levenshtein-Abstand zwischen den beiden Phrasen, und valueWords teilt den String in einzelne Wörter auf, basierend auf Trennzeichen wie Leerzeichen, Bindestrichen und allem, was Sie möchten, und vergleicht jedes Wort mit jedem anderen Wort und addiert das kürzeste zusammen Levenshtein-Abstand, der zwei Wörter verbindet. Im Wesentlichen misst es, ob die Information in einer "Phrase" wirklich in einer anderen enthalten ist, genau wie eine wortweise Permutation. Ich verbrachte ein paar Tage als Nebenprojekt, um die effizienteste Möglichkeit zu finden, eine Zeichenfolge basierend auf Trennzeichen aufzuteilen.

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 

Ähnlichkeitsmaße

diese beiden Metriken und eine dritte, die einfach den Abstand zwischen zwei Strings berechnet, habe ich eine Reihe von Variablen, die ich einen Optimierungsalgorithmus ausführen kann, um die größte Anzahl von Übereinstimmungen zu erreichen. Fuzzy-String-Matching ist selbst eine Fuzzy-Wissenschaft, und indem wir linear unabhängige Metriken für die Messung von String-Ähnlichkeiten erstellen und eine bekannte Menge von Strings haben, die wir einander zuordnen wollen, können wir die Parameter finden, die für unsere spezifischen Styles von Strings, geben die besten Fuzzy-Match-Ergebnisse.

Ursprünglich bestand das Ziel der Metrik darin, einen niedrigen Suchwert für eine exakte Übereinstimmung zu verwenden und die Suchwerte für zunehmend permutierte Maße zu erhöhen. In einem unpraktischen Fall war dies ziemlich einfach zu definieren, indem eine Reihe von gut definierten Permutationen verwendet wurde, und die endgültige Formel so konstruiert wurde, dass sie nach Wunsch wachsende Suchwerte aufwies.

Wie Sie sehen können, sind die letzten zwei Metriken, die passende Metriken Fuzzy String sind, bereits eine natürliche Tendenz haben niedrige Werte in Strings zu geben, die (auf der Diagonale) übereinstimmen sollen. Das ist sehr gut.

Anwendung Um die Optimierung der Fuzzy-Anpassung zu ermöglichen, gewichte ich jede Metrik. Somit kann jede Anwendung der Fuzzy-String-Übereinstimmung die Parameter unterschiedlich gewichten. Die Formel, die das Endergebnis definiert ist einfach die Kombination der Metriken und ihre Gewichte:

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

Mit Hilfe eines Optimierungsalgorithmus (neuronales Netz ist hier am besten, weil es sich um eine diskrete ist, multi-dimensionales Problem), das Ziel ist jetzt, um die Anzahl der Übereinstimmungen zu maximieren. Ich habe eine Funktion erstellt, die die Anzahl der richtigen Übereinstimmungen jedes Satzes zueinander erkennt, wie in diesem letzten Screenshot zu sehen ist. Eine Spalte oder Zeile erhält einen Punkt, wenn die niedrigste Punktzahl der Zeichenfolge zugewiesen wird, die übereinstimmen sollte, und Teilpunkte werden angegeben, wenn für die niedrigste Punktzahl ein Gleichstand vorliegt und die richtige Übereinstimmung zwischen den verknüpften übereinstimmenden Zeichenfolgen besteht. Ich habe es dann optimiert. Sie können sehen, dass eine grüne Zelle die Spalte ist, die am besten zur aktuellen Zeile passt, und ein blaues Quadrat um die Zelle ist die Zeile, die am besten zur aktuellen Spalte passt. Der Punktestand in der unteren Ecke entspricht in etwa der Anzahl der erfolgreichen Übereinstimmungen und dies ist es, was wir unserem Optimierungsproblem zur Maximierung mitteilen.