غامض النص (الجمل/عناوين) مطابقة في C#

Question

مرحبا, أنا باستخدام Levenshteins خوارزمية للحصول على المسافة بين المصدر والهدف السلسلة.

أيضا لدي الأسلوب الذي ترجع القيمة من 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;
}

لكن هذا بالنسبة لي لا يكفي.لأنني بحاجة أكثر تعقيدا الطريق إلى المباراة جملتين.

على سبيل المثال أريد تلقائيا الوسم بعض الموسيقى لدي الأغنية الأصلية أسماء لدي الأغاني مع القمامة ، مثل سوبر والجودة ، سنوات مثل 2007, 2008, الخ..الخ..أيضا بعض الملفات فقط http://trash..thash..song_name_mp3.mp3, الأخرى طبيعية.أريد إنشاء خوارزمية والتي سوف تعمل فقط أكثر كمالا من الألغام الآن..ربما أي شخص يمكن أن تساعدني ؟

هنا هو بلدي الحالي 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;
}

هذا يعمل بشكل طبيعي ولكن فقط في بعض الحالات الكثير من العناوين التي يجب أن المباراة لا تتناسب مع...أعتقد أنني في حاجة إلى نوع من صيغة للعب مع الأوزان وغيرها, ولكن لا أستطيع التفكير في أحد..

أفكار ؟ اقتراحات ؟ ألجوس?

بالمناسبة أنا أعرف بالفعل هذا الموضوع (زميلي نشرت بالفعل ولكن نحن لا يمكن أن تأتي مع الحل المناسب لهذه المشكلة.):التقريبية سلسلة خوارزميات مطابقة

Answer 1

المشكلة هنا يمكن التمييز بين الضوضاء الكلمات و البيانات المفيدة:

• Rolling_Stones.Best_of_2003.Wild_Horses.mp3
• السوبر.الجودة.Wild_Horses.mp3
• Tori_Amos.Wild_Horses.mp3

قد تحتاج إلى إنتاج قاموس كلمات الضجيج إلى تجاهل.يبدو عالي الكعب ، ولكن لست متأكدا من أن هناك خوارزمية يمكن أن تميز بين الفرقة/ألبوم أسماء والضوضاء.

Answer 2

نوع من العمر ، ولكن قد يكون من المفيد في المستقبل الزوار.إذا كنت بالفعل باستخدام Levenshtein الخوارزمية تحتاج إلى الذهاب من أفضل قليلا, لقد وصف بعض فعالة جدا الاستدلال في هذا الحل:

الحصول على أقرب السلسلة المباراة

المفتاح هو أن تأتي مع 3 أو 4 (أو المزيد) أساليب قياس تشابه بين العبارات الخاصة بك (Levenshtein المسافة هو أسلوب واحد فقط) - ثم باستخدام أمثلة حقيقية من سلاسل كنت ترغب في مباراة مماثلة ، يمكنك ضبط الأوزان ومجموعات من تلك الاستدلال حتى تحصل على شيء يزيد عدد إيجابية في المباريات.ثم يمكنك استخدام هذه الصيغة لجميع المباريات المقبلة ويجب أن نرى نتائج عظيمة.

إذا كان المستخدم هو المشاركة في العملية ، كما أنها أفضل إذا توفر واجهة التي تسمح للمستخدم لمعرفة إضافية المباريات التي تحتل مرتبة عالية في تشابه في حال اختلف مع الخيار الأول.

وهنا مقتطفات من ربط الجواب.إذا كنت في نهاية المطاف الرغبة في استخدام أي من هذا القانون كما هو ، أعتذر مقدما عن الحاجة إلى تحويل VBA في C#.

---

بسيطة, سريعة و مفيدة جدا متري.باستخدام هذا, أنا خلقت منفصلة اثنين مقاييس تقييم التشابه من سلسلتين.أطلق عليها "valuePhrase" واحد أسميه "valueWords".valuePhrase هو مجرد Levenshtein المسافة بين العبارتين ، valueWords تقسيم السلسلة إلى كلمات فردية ، بناء على المحددات مثل مسافات وأي شيء آخر كنت ترغب في ذلك ، ثم يقارن كل كلمة كل كلمة أخرى ، تلخيص أقصر Levenshtein المسافة توصيل أي كلمتين.أساسا, فهو يقيس ما إذا كانت المعلومات في 'عبارة' هو في الحقيقة الواردة في أخرى ، تماما كما أن كلمة الحكمة التقليب.قضيت بضعة أيام كمشروع جانبي الخروج مع الطريقة الأكثر فعالية ممكنة من تقسيم سلسلة بناء على المحددات.

valueWords, valuePhrase و تقسيم الوظيفة:

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

تدابير من التشابه

باستخدام هذين المقياسين ، الثالثة والتي ببساطة يحسب المسافة بين اثنين من سلاسل, لدي مجموعة من المتغيرات التي لا يمكن تشغيل خوارزمية الأمثل لتحقيق أكبر عدد من المباريات.غامض مطابقة السلسلة هي نفسها غامض العلم ، وذلك عن طريق إنشاء مستقلة خطيا مقاييس لقياس تشابه السلسلة ، وجود مجموعة معروفة من سلاسل نود أن تتطابق مع بعضها البعض ، يمكننا العثور على المعلمات أن لدينا أنماط محددة من السلاسل ، تعطي أفضل غامض نتائج المباريات.

في البداية الهدف من المقياس كان لديهم انخفاض قيمة البحث عن تطابق تام ، وزيادة البحث القيم على نحو متزايد متبدل الترتيب permuted التدابير.في عملي الحالة ، هذا كان من السهل إلى حد ما لتحديد باستخدام مجموعة محددة جيدا التباديل و الهندسة النهائي الصيغة هذه أن لديهم زيادة البحث القيم النتائج على النحو المطلوب.

كما يمكنك أن ترى من خلال المقاييس التي غامض سلسلة مطابقة المقاييس بالفعل لديهم ميل طبيعي إلى إعطاء درجات منخفضة إلى السلاسل التي تهدف إلى مباراة (أسفل قطري).هذا هو جيد جدا.

التطبيق للسماح الأمثل من مطابقة غامض, لا وزن لكل معيار.على هذا النحو, كل تطبيق من غامض السلسلة مباراة يمكن أن الوزن المعلمات بشكل مختلف.الصيغة التي تحدد النتيجة النهائية هي ببساطة مجموعة من المقاييس و الأوزان:

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

باستخدام خوارزمية الأمثل (الشبكة العصبية هو أفضل هنا لأنها منفصلة متعددة-dimentional المشكلة) ، والهدف هو الآن لزيادة عدد المباريات.أنا خلقت وظيفة بالكشف عن عدد من مباريات الصحيح من كل مجموعة إلى بعضها البعض ، كما يمكن أن يرى في هذه الصورة النهائية.عمود أو صف يحصل على نقطة إذا أدنى درجة تعيين السلسلة التي كان من المفترض أن تكون مطابقة جزئية يتم إعطاء نقاط إذا كان هناك التعادل على أقل درجة ، و الصحيح تطابق بين وتعادل مطابقة السلاسل.ثم الأمثل.يمكنك أن ترى أن الأخضر خلية العمود الذي يطابق أفضل الصف الحالي ، مربع اللون الأزرق حول الخلية هو الصف الذي يطابق أفضل العمود الحالي.النتيجة في أسفل الزاوية تقريبا عدد مباريات ناجحة و هذا هو ما نقول الأمثل المشكلة إلى أقصى حد.

Answer 3

يبدو أن ما تريده قد يكون أطول فرعية المباراة.الذي هو في المثال الخاص بك ، ملفين مثل

المهملات..thash..song_name_mp3.mp3 و القمامة..spotch..song_name_mp3.mp3

في نهاية المطاف يبحث عن نفسه.

كنت بحاجة إلى الاستدلال هناك ، بالطبع.شيء واحد كنت قد تحاول وضع السلسلة من خلال soundex محول.Soundex هو "الترميز" اعتدنا أن نرى إذا كانت الأمور "الصوت" نفسه (كما قد أخبر مشغل الهاتف).أنها أكثر أو أقل الخام لفظي خطأ لفظي شبه دليل على الحروف.هو بالتأكيد أكثر فقرا من تحرير المسافة ولكن أرخص بكثير.(للاستعمال الرسمي هو الأسماء فقط يستخدم ثلاثة أحرف.لا يوجد سبب لوقف هناك ، على الرغم من مجرد استخدام الخرائط لكل حرف في السلسلة.انظر ويكيبيديا لمزيد من التفاصيل)

اقتراحي أن soundex سلاسل الخاص بك ، ختم كل واحد في عدد قليل من طول الشرائح (5, 10, 20) ثم مجرد إلقاء نظرة على المجموعات.ضمن مجموعات يمكنك استخدام شيء أكثر تكلفة مثل تحرير المسافة أو ماكس فرعية.

Answer 4

هناك الكثير من العمل القيام به على حد ما مشكلة تتعلق الحمض النووي تسلسل المحاذاة (البحث عن "المحلية تسلسل المحاذاة") - خوارزمية الكلاسيكية كونها "نيدلمان-ونش" وأكثر تعقيدا الحديثة منها أيضا من السهل العثور على.الفكرة هي - على غرار جريج الجواب - بدلا من تحديد ومقارنة الكلمات الرئيسية في محاولة للعثور على أطول فضفاضة مطابقة سلاسل فرعية داخل سلاسل طويلة.

أن يجري حزين, إذا كان الهدف الوحيد هو الفرز الموسيقى عدد من التعبيرات العادية لتغطية الممكن تسمية مخططات المحتمل أن يعمل أفضل من أي عام الخوارزمية.

Answer 5

هناك جيثب الريبو تنفيذ عدة طرق.