Fuzzy text (sentences/titles) matching in C#
嘿，我正在使用Levenshteins算法来获取源字符串和目标字符串之间的距离。
我也有方法返回值从0到1：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| /// <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等年份。等等。还有一些文件只有http：// trash。 .thash..song_name_mp3.mp3，其他都是正常的。我想创建一种算法，该算法现在比我的算法更完美。.也许有人可以帮助我吗？
这是我目前的算法：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
| /// <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;
} |
这正常工作，但在某些情况下，很多标题应该匹配，不匹配...我想我需要某种公式来处理权重等，但我想不到。
有想法吗？有什么建议吗？阿尔戈斯？
顺便说一句，我已经知道了这个主题(我的同事已经发布了这个主题，但是我们不能为这个问题提供适当的解决方案。)：
近似字符串匹配算法
有点陈旧，但对将来的访问者可能有用。如果您已经在使用Levenshtein算法，并且需要做得更好一些，我将在此解决方案中描述一些非常有效的启发式方法：
好。
获取最接近的字符串匹配
好。
关键是您想出3种或4种(或更多种)量度短语之间相似度的方法(Levenshtein距离只是一种方法)-然后使用要匹配的相似字符串的真实示例，调整权重以及这些试探法的组合，直到您获得最大程度地增加正匹配次数的东西。然后，将该公式用于将来的所有比赛，都应该会看到不错的结果。
好。
如果用户参与此过程，那么最好提供一个界面，该界面允许用户查看在相似性方面排名较高的其他匹配项，以防他们不同意第一选择。
好。
这是链接答案的摘录。如果您最终想按原样使用任何此代码，我必须为将VBA转换为C＃表示歉意。
好。
简单，快速且非常有用的指标。使用此方法，我创建了两个单独的指标来评估两个字符串的相似性。一个我称为" valuePhrase"，另一个我称为" valueWords"。 valuePhrase只是两个短语之间的Levenshtein距离，valueWords根据空格，破折号和其他所需的分隔符将字符串分成单个单词，并将每个单词与另一个单词进行比较，得出最短的总和Levenshtein距离连接任意两个词。本质上，它衡量一个"短语"中的信息是否真的包含在另一个"短语"中，就像逐字排列一样。我花了几天时间作为一个辅助项目，提出了基于定界符分割字符串的最有效方法。
好。
valueWords，valuePhrase和Split函数：
好。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
| 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 |
相似度
好。
使用这两个指标，第三个指标只是计算两个字符串之间的距离，我有一系列变量，可以运行优化算法以实现最大数量的匹配。模糊字符串匹配本身就是一门模糊科学，因此，通过创建线性独立的度量来测量字符串相似度，并拥有一组我们希望相互匹配的已知字符串，我们可以找到针对我们特定样式的参数字符串，给出最佳的模糊匹配结果。
好。
最初，该指标的目标是为精确匹配提供较低的搜索值，并为日益排列的度量提高搜索值。在不切实际的情况下，使用一组定义明确的排列来定义它非常容易，并对最终公式进行工程设计，使其具有所需的增加的搜索值结果。
好。
好。
如您所见，最后两个度量标准(即模糊字符串匹配度量标准)已经自然地倾向于为要匹配的字符串(对角线下方)赋予低分。这是非常好的。
好。
应用
为了优化模糊匹配，我对每个指标进行加权。这样，模糊字符串匹配的每种应用都可以对参数进行加权。定义最终分数的公式是指标及其权重的简单组合：
好。
1
2
| value = Min(phraseWeight*phraseValue, wordsWeight*wordsValue)*minWeight +
Max(phraseWeight*phraseValue, wordsWeight*wordsValue)*maxWeight + lengthWeight*lengthValue |
使用优化算法(神经网络在这里是最好的，因为它是一个离散的多维问题)，现在的目标是最大化匹配数。我创建了一个函数，用于检测每个集合彼此之间正确匹配的次数，如最终屏幕截图所示。如果将最低分数分配给了要匹配的字符串，则列或行将获得一个点；如果最低分数存在并列，则正确的匹配是在已绑定的匹配字符串中，则列或行将得到部分分数。然后，我对其进行了优化。您会看到绿色的单元格是与当前行最匹配的列，而单元格周围的蓝色正方形是与当前列最匹配的行。底角的得分大约是成功匹配的次数，这就是我们告诉优化问题最大化的原因。
好。
好。
好。
您的问题可能是区分干扰词和有用数据：
-
Rolling_Stones.Best_of_2003.Wild_Horses.mp3
-
Super.Quality.Wild_Horses.mp3
-
Tori_Amos.Wild_Horses.mp3
您可能需要制作一个干扰词字典来忽略。这似乎很笨拙，但是我不确定是否有一种算法可以区分乐队/专辑名称和噪声。
听起来您想要的可能是最长的子字符串匹配。也就是说，在您的示例中，两个文件
垃圾桶..thash..song_name_mp3.mp3
和
垃圾..spotch..song_name_mp3.mp3
最终看起来会一样。
当然，您需要在那里进行启发式操作。您可能要尝试的一件事是将字符串通过soundex转换器。 Soundex是用于查看事物"听起来"是否相同的"编解码器"(就像您可能告诉电话接线员一样)。它或多或少是一种粗糙的语音和发音错误的半证明音译。它肯定比编辑距离差，但便宜得多。 (正式使用是用于名称，仅使用三个字符。不过，没有理由在此停下来，只需对字符串中的每个字符使用映射。有关详细信息，请参阅Wikipedia。)
因此，我的建议是将您的琴弦进行声音处理，将每个琴弦切成几小段(例如5、10、20)，然后再看一下音簇。在群集中，您可以使用更昂贵的东西，例如编辑距离或最大子字符串。
关于DNA序列比对的一些相关问题(搜索"局部序列比对")，有很多工作要做-经典算法是" Needleman-Wunsch"，更复杂的现代算法也很容易找到。这个想法类似于Greg的回答，而不是识别和比较关键字，而是尝试在长字符串中找到最长的松散匹配子字符串。
令人遗憾的是，如果唯一的目标是对音乐进行排序，那么覆盖所有可能命名方案的许多正则表达式可能比任何通用算法都更好。
有一个GitHub仓库实现了几种方法。
|
