Fuzzy testo (frasi/titoli) corrispondenza in C#

Question

Ehi, sto utilizzando Levenshteins algoritmo per ottenere la distanza tra l'origine e la stringa di destinazione.

anche io ho un metodo che restituisce un valore da 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;
}

ma questo per me non è sufficiente.Perché ho bisogno di più complesso modo di corrispondere due frasi.

Per esempio voglio taggare automaticamente un po ' di musica, ho originale il nome della song, e ho canzoni con cestino, come super, qualità, anni come 2007, 2008, ecc..ecc..inoltre, alcuni file sono appena http://trash..thash..song_name_mp3.mp3, altri sono normali.Voglio creare un algoritmo che funziona di più perfetto di mia ora..Forse qualcuno mi può aiutare?

ecco la mia attuale 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;
}

Questo funziona normalmente ma solo in alcuni casi, un sacco di titoli che devono corrispondere, non corrisponde...Penso che ho bisogno di un qualche tipo di formula si gioca con i pesi e ecc, ma non riesco a pensare a uno..

Idee?Suggerimenti?Algos?

dal modo in cui so già di questo argomento (il Mio collega già postato ma non riusciamo a venire con una soluzione adeguata a questo problema.):Approssimativo stringa di algoritmi per il matching

Answer 1

Il tuo problema potrebbe essere distinguere tra il rumore di parole e dati utili:

• Rolling_Stones.Best_of_2003.Wild_Horses.mp3
• Super.Qualità.Wild_Horses.mp3
• Tori_Amos.Wild_Horses.mp3

Potrebbe essere necessario produrre un dizionario di parole rumore di ignorare.Che sembra goffo, ma non sono sicuro che c'è un algoritmo in grado di distinguere tra le band/i nomi degli album e rumore.

Answer 2

È un po ' vecchio, ma potrebbe essere utile per i futuri visitatori.Se si sta già utilizzando l'algoritmo di Levenshtein e hai bisogno di andare un po ' meglio, ho descritto alcuni molto efficace euristica in questa soluzione:

Ottenere il più vicino corrispondenza della stringa

La chiave è che si arriva con 3 o 4 (o più metodi per misurare la somiglianza tra le frasi (distanza di Levenshtein è solo un metodo) e poi usando esempi reali di stringhe che si desidera partita simile, si regolano i coefficienti di ponderazione e combinazioni di questi euristica fino a quando si ottiene qualcosa che massimizza il numero di positivi partite.Quindi, utilizzare questa formula per tutte le future partite e si dovrebbe vedere grandi risultati.

Se un utente è coinvolto in un processo, e ' anche meglio se si fornisce un'interfaccia che permette all'utente di vedere ulteriori corrispondenze che una posizione elevata in una somiglianza in caso di disaccordo con la prima scelta.

Ecco un estratto dal collegato risposta.Se si vuole utilizzare questo codice come è, mi scuso in anticipo per aver per la conversione di VBA in C#.

---

Semplice, veloce e molto utile metrica.Usando questo, ho creato due distinte le metriche per la valutazione della somiglianza tra i due stringhe.La chiamo "valuePhrase" e la chiamo "valueWords".valuePhrase è solo la distanza di Levenshtein tra le due frasi, e valueWords divide la stringa in singole parole, basato su delimitatori come spazi, trattini, e quant'altro si desideri, e il confronto di ogni parola di ogni altra parola, che riassume la più breve distanza di Levenshtein il collegamento di due parole.In sostanza, misure se le informazioni in una 'frase' è realmente contenuto in un altro, come una parola-saggio di permutazione.Ho trascorso un paio di giorni come un side-project venire con il modo più efficiente possibile, di dividere una stringa in base delimitatori.

valueWords, valuePhrase, e la funzione 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

Le misure di Similarità

Utilizzando queste due metriche, e un terzo, che calcola la distanza tra due stringhe, ho una serie di variabili che sono in grado di eseguire un algoritmo di ottimizzazione per ottenere il maggior numero di partite.Fuzzy corrispondenza della stringa è, di per sé, un fuzzy scienza, e la creazione linearmente indipendenti metriche per la misura della stringa somiglianza, e avendo conosciuto un insieme di stringhe vogliamo corrisponde a vicenda, siamo in grado di trovare i parametri, per i nostri specifici stili di stringhe, dare il meglio di corrispondenza fuzzy risultati.

Inizialmente, l'obiettivo della metrica era quello di avere un basso valore di ricerca per una corrispondenza esatta, e la sempre maggiore ricerca di valori sempre più permutata misure.In un caso pratico, questo era abbastanza facile definire l'utilizzo di un set ben definito di permutazioni, di ingegneria e la formula finale in modo tale che essi avevano sempre maggiore ricerca di valori, come desiderato.

Come si può vedere, gli ultimi due parametri, che sono fuzzy stringa corrispondente metriche, già hanno una naturale tendenza a dare punteggi bassi per le stringhe che sono destinati a partita (giù la diagonale).Questo è molto buono.

Applicazione Per consentire l'ottimizzazione della corrispondenza fuzzy, mi peso ogni metrica.Come tale, ogni applicazione di fuzzy corrispondenza della stringa può peso i parametri in modo diverso.La formula che definisce il punteggio finale è semplicemente una combinazione di metriche e i loro pesi:

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

Utilizzando un algoritmo di ottimizzazione (rete neurale è meglio qui, perché è un discreto, multi-dimensionali problema), l'obiettivo è ora quello di massimizzare il numero di partite.Ho creato una funzione che rileva il numero di abbinamenti di ogni set all'altro, come può essere visto in questa ultima schermata.Una colonna o una riga ottiene un punto se il punteggio più basso è assegnata la stringa che è stato pensato per essere abbinato, e parziale vengono assegnati punti se c'è un pareggio per il punteggio più basso, e la corretta corrispondenza tra il legato stringhe corrispondenti.Poi ho ottimizzato.Si può vedere che una cella verde è la colonna che meglio corrisponde alla riga corrente e un quadrato blu intorno alla cella è la riga che corrisponde meglio alla colonna corrente.Il punteggio ottenuto in un angolo in basso, è di circa il numero di partite e questo è quello che ci dicono le nostre problema di ottimizzazione per massimizzare.

Answer 3

Sembra che ciò che si desidera può essere più lunga sottostringa partita.Che è, nel tuo esempio, due file come

trash..thash..song_name_mp3.mp3 e spazzatura..spotch..song_name_mp3.mp3

finirebbe guardando lo stesso.

Avete bisogno di alcune euristiche c'è, naturalmente.Una cosa che potresti provare è mettere la stringa attraverso un soundex converter.Soundex è il codec usato per vedere se le cose "suono" lo stesso (come si potrebbe dire di un operatore telefonico).E ' più o meno ruvido, fonetica e storpiatura semi-prova di traslitterazione.È sicuramente più povero di modificare a distanza, ma molto, molto più economico.(L'uso ufficiale è per i nomi, e utilizza solo tre caratteri.Non c'è motivo di fermarsi, basta usare la mappatura per ogni carattere della stringa.Vedere wikipedia per i dettagli)

Quindi il mio suggerimento sarebbe quello di soundex tue corde, tagliare ognuno in un paio di lunghezza tranche (diciamo 5, 10, 20) e poi basta guardare i cluster.All'interno del cluster, è possibile utilizzare qualcosa di più costoso come modificare la distanza o max sottostringa.

Answer 4

C'è un sacco di lavoro fatto in qualche modo correlati a problema di allineamento di sequenza del DNA (ricerca per "locale allineamento di sequenza") - classico algoritmo essere "Needleman-Wunsch" e più complessi di quelli moderni anche facile da trovare.L'idea è simile a Greg risposta - invece di individuare e confrontare le parole chiave di provare a trovare la più lunga vagamente sottostringhe corrispondenti all'interno di stringhe lunghe.

Che tristezza, se l'unico obiettivo è l'ordinamento di musica, una serie di espressioni regolari per la copertura di eventuali schemi di denominazione probabilmente potrebbe funzionare meglio di qualsiasi algoritmo generico.

Answer 5

C'è un Repo GitHub implementazione di metodi diversi.