嘿，我正在使用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;
}

但这对我来说还不够。因为我需要更复杂的方式来匹配两个句子。

例如，我想自动标记一些音乐，我拥有原始的歌曲名称，并且我有带有垃圾邮件的歌曲，例如super，quality，诸如2007、2008等年份。 .thash..song_name_mp3.mp3，其他都是正常的。我想创建一种算法，该算法现在比我的算法更完美。.也许有人可以帮助我吗？

这是我目前的算法：

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

这正常工作，但是在某些情况下，很多标题应该匹配，不匹配...我想我需要某种公式来处理权重等，但是我想不出一个。

有想法吗？有什么建议吗？阿尔戈斯？

顺便说一句，我已经知道了这个主题(我的同事已经发布了这个主题，但是我们不能为这个问题提供适当的解决方案。)：
近似字符串匹配算法

解决方案

回答

听起来我们想要的可能是最长的子字符串匹配。也就是说，在示例中，两个文件

垃圾桶..thash..song_name_mp3.mp3
和
垃圾..spotch..song_name_mp3.mp3

最终看起来会一样。

当然，我们在那里需要一些启发式方法。我们可能要尝试的一件事是将字符串通过soundex转换器。 Soundex是用于查看事物"听起来"是否相同的"编解码器"(就像我们可能告诉电话接线员一样)。它或者多或者少是一种粗糙的语音和发音错误的半证明音译。它肯定比编辑距离差，但便宜得多。 (官方使用的是名称，仅使用三个字符。不过，没有必要在此停下脚步，只需对字符串中的每个字符都使用映射。有关详细信息，请参阅Wikipedia。)

因此，我的建议是将琴弦进行声音处理，将每个琴弦切成几小段(例如5、10、20)，然后再看一下音簇。在群集中，我们可以使用更昂贵的东西，例如编辑距离或者最大子字符串。

回答

问题可能是区分干扰词和有用数据：

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

我们可能需要制作一个干扰词字典来忽略。这似乎很笨拙，但是我不确定是否有一种算法可以区分乐队/专辑名称和噪声。

回答

关于DNA序列比对(搜索"局部序列比对")的一些相关问题，有很多工作要做，经典算法是" Needleman-Wunsch"，更容易找到更现代的算法。这个想法类似于Greg的答案，而不是识别和比较关键字以尝试在长字符串中找到最长的松散匹配子字符串。

令人遗憾的是，如果唯一的目标是对音乐进行排序，那么覆盖所有可能命名方案的许多正则表达式可能比任何通用算法都更好。