Floue texte (phrases/titres) correspondant en C#

Question

Hey, je suis en utilisant Levenshteins algorithme pour obtenir la distance entre la source et la cible de la chaîne.

j'ai aussi la méthode qui retourne la valeur de 0 à 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;
}

mais moi ce n'est pas suffisant.Parce que j'ai besoin de plus complexe pour s'aligner deux phrases.

Par exemple je veux associer automatiquement de la musique, j'ai d'origine noms de la chanson, et j'ai des chansons avec de la poubelle, comme super, la qualité,la ans comme 2007, 2008, etc..etc..en outre, certains fichiers ont juste http://trash..thash..song_name_mp3.mp3, d'autres sont normaux.Je veux créer un algorithme qui fonctionneront plus parfait que le mien maintenant..Peut-être que quelqu'un peut m'aider?

ici est mon 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;
}

Cela fonctionne normalement, mais seulement dans certains cas, beaucoup de titres qui devraient correspondre aux, ne correspond pas...Je pense que j'ai besoin d'une sorte de formule de jouer avec des poids et etc, mais je ne peux pas penser à un..

Des idées?Des Suggestions?Algos?

par la façon dont je sais déjà ce sujet (Mon collègue l'a déjà posté, mais on ne peut pas venir avec une solution appropriée à ce problème.):L'appariement approximatif de chaînes algorithmes

Answer 1

Votre problème peut être la distinction entre le bruit des mots et des données utiles:

• Rolling_Stones.Best_of_2003.Wild_Horses.mp3
• Super.La qualité de l'.Wild_Horses.mp3
• Tori_Amos.Wild_Horses.mp3

Vous devrez peut-être produire un dictionnaire de bruit de mots à ignorer.Qui semble maladroit, mais je ne suis pas sûr qu'il y a un algorithme qui permet de distinguer entre la bande/noms d'album et le bruit.

Answer 2

Genre de vieux, mais Il pourrait être utile pour les futurs visiteurs.Si vous êtes déjà à l'aide de l'algorithme de Levenshtein et vous avez besoin d'aller un peu mieux, je décris quelques très efficace heuristiques dans cette solution:

D'obtenir le plus proche de la chaîne de match

La clé est que vous venez avec 3 ou 4 (ou plus méthodes de mesure de la similarité entre vos phrases (Levenshtein est juste une méthode) - puis à l'aide d'exemples réels de chaînes que vous souhaitez en fonction similaire, vous pouvez régler les coefficients de pondération et des combinaisons de ces heuristiques jusqu'à ce que vous obtenez quelque chose qui maximise le nombre de positif correspond.Puis vous utilisez cette formule pour tous les matches à l'avenir et vous devriez voir de grands résultats.

Si un utilisateur est impliqué dans le processus, il est également préférable si vous fournissez une interface qui permet à l'utilisateur de voir les autres matches de rang très similitude dans le cas où ils sont en désaccord avec le premier choix.

Voici un extrait de la liés réponse.Si vous avez envie d'utiliser ce code en l'état, je m'en excuse à l'avance pour avoir à les convertir VBA en C#.

---

Simple, rapide, et très utile métrique.En utilisant cela, j'ai créé deux métriques pour l'évaluation de la similarité de deux chaînes de caractères.Celui que j'appelle "valuePhrase" et celui que j'appelle "valueWords".valuePhrase est juste la distance de Levenshtein entre les deux phrases, et valueWords divise la corde en deux mots, basé sur les séparateurs tels que des espaces, des tirets, et autre chose que vous aimeriez, et compare chaque mot de chaque autre mot, résumant la plus courte distance de Levenshtein connecter tous les deux mots.Essentiellement, il évalue si les informations 'phrase' est vraiment dans un autre, tout comme un mot de permutation.J'ai passé quelques jours comme un projet parallèle à venir avec la manière la plus efficace possible de scinder une chaîne basée sur des délimiteurs.

valueWords, valuePhrase, et la fonction de répartition:

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

Les mesures de Similarité

À l'aide de ces deux mesures, et d'un troisième qui, tout simplement, calcule la distance entre deux chaînes de caractères, j'ai une série de variables qui je peux exécuter un algorithme d'optimisation pour atteindre le plus grand nombre de matchs.Floue correspondance de chaîne est, en soi, un flou de la science, et donc par la création d'indépendance linéaire des métriques pour mesurer la similarité de chaînes, et d'avoir un ensemble de chaînes de caractères nous souhaitons correspondre les uns aux autres, nous pouvons trouver les paramètres qui, pour nos styles spécifiques de cordes, de donner le meilleur de correspondance floue résultats.

Initialement, le but de cette mesure est d'avoir une faible valeur de recherche pour une correspondance exacte, et l'augmentation des valeurs de recherche de plus en plus permutées mesures.Dans irréaliste cas, c'était assez facile à définir à l'aide d'un ensemble bien défini de permutations, et le génie de la formule finale, tels qu'ils ont plus de valeurs de recherche les résultats souhaités.

Comme vous pouvez le voir, les deux dernières mesures, qui sont floues correspondance de chaîne métriques, ont déjà une tendance naturelle à donner de faibles scores aux chaînes qui sont destinés à faire correspondre (en bas de la diagonale).C'est très bien.

Application Pour permettre l'optimisation de la correspondance floue, j'ai le poids de chacune des mesures.En tant que tel, chaque application de flou de chaîne de match peut de poids les paramètres différemment.La formule qui définit le score final est tout simplement une combinaison de ces critères et leur poids:

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

À l'aide d'un algorithme d'optimisation (réseau de neurones est mieux ici, car il est discret, multi-dimensions problème), l'objectif est de maximiser le nombre de matchs.J'ai créé une fonction qui détecte le nombre de corriger les matches de chaque série les uns aux autres, comme on peut le voir dans cette dernière capture d'écran.Une colonne ou une ligne obtient un point si le score le plus bas est affecté à la chaîne qui était censé être adapté, et partielle des points sont attribués si il y a égalité pour le score le plus bas, et que le match est parmi les attachés chaînes mises en correspondance.J'ai ensuite optimisé.Vous pouvez voir qu'une cellule en vert est la colonne qui correspond le mieux à la ligne actuelle, et un carré bleu autour de la cellule est la ligne qui correspond le mieux à la colonne en cours.Le score dans le coin en bas est à peu près le nombre de matchs et c'est ce que nous disons à notre problème d'optimisation pour maximiser.

Answer 3

Il semble que vous vous voulez peut-être une plus longue correspondance de sous-chaîne.C'est, dans votre exemple, deux fichiers comme

corbeille..thash..song_name_mp3.mp3 et poubelle..spotch..song_name_mp3.mp3

ce serait la fin de l'air tout de même.

Vous auriez besoin de quelques heuristiques là, bien sûr.Une chose que vous pouvez essayer est de mettre la chaîne à travers un soundex convertisseur.Soundex est le "codec" pour voir si les choses "son" de la même (comme vous pouvez vous en dire un opérateur téléphonique).C'est plus ou moins un accidenté de la phonétique et de la mauvaise prononciation semi-preuve de la translittération.Il est certainement plus pauvre que la distance d'édition, mais beaucoup, beaucoup moins cher.(L'usage officiel est pour les noms, et n'utilise que trois personnages.Il n'y a pas de raison de s'arrêter là, bien, il suffit d'utiliser la cartographie pour chaque caractère dans la chaîne.Voir wikipédia pour plus de détails)

Donc, ma suggestion serait de soundex vos chaînes, les couper chacun en quelques longueur tranches (par exemple, 5, 10, 20) et puis il suffit de regarder les clusters.À l'intérieur des clusters, vous pouvez utiliser quelque chose de plus cher comme la distance d'édition ou max de sous-chaîne.

Answer 4

Il y a beaucoup de travail de fait sur un peu problème lié à l'alignement de la séquence de l'ADN (de la recherche pour "local de l'alignement de la séquence") - algorithme classique étant "Needleman-Wunsch" et plus complexes les plus modernes aussi facile à trouver.L'idée est similaire à la réponse de Greg - au lieu d'identifier et de comparer des mots-clés essayer de trouver le plus long vaguement les chaînes de correspondance au sein des chaînes longues.

Que le fait d'être triste, si le seul but est de trier la musique, un certain nombre d'expressions régulières pour couvrir d'éventuels schémas de nommage serait probablement plus efficace que n'importe quel algorithme générique.

Answer 5

Il y a un Dépôt GitHub la mise en œuvre de plusieurs méthodes.