Texto difuso (frases/títulos) correspondente em C#
https://stackoverflow.com/questions/53480
-
09-06-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPergunta
Ei, estou usando Levenshteins algoritmo para obter a distância entre a string de origem e de destino.
também tenho um método que retorna valor de 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;
}
mas isso para mim não é suficiente.Porque preciso de uma maneira mais complexa de combinar duas frases.
Por exemplo, quero marcar automaticamente algumas músicas, tenho nomes de músicas originais e tenho músicas com lixo, como super, qualidade, anos como 2007, 2008, etc etc..também alguns arquivos acabaram de http://trash..thash..song_name_mp3.mp3, outros são normais.Quero criar um algoritmo que funcione de forma mais perfeita que o meu agora.Talvez alguém possa me ajudar?
aqui está meu algoritmo atual:
/// <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;
}
Isso funciona normalmente, mas apenas em alguns casos, muitos títulos que deveriam corresponder, não coincidem...Acho que preciso de algum tipo de fórmula para brincar com pesos e etc, mas não consigo pensar em nenhuma..
Ideias?Sugestões?Algos?
aliás, eu já conheço esse tópico (meu colega já postou, mas não conseguimos encontrar uma solução adequada para esse problema.):Algoritmos aproximados de correspondência de strings
Solução
Seu problema aqui pode ser distinguir entre palavras barulhentas e dados úteis:
- Rolling_Stones.Best_of_2003.Wild_Horses.mp3
- Super.Qualidade.Cavalos_selvagens.mp3
- Tori_Amos.Wild_Horses.mp3
Pode ser necessário produzir um dicionário de palavras ruidosas para ignorar.Isso parece desajeitado, mas não tenho certeza se existe um algoritmo que possa distinguir entre nomes de bandas/álbuns e ruído.
Outras dicas
Meio antigo, mas pode ser útil para futuros visitantes.Se você já está usando o algoritmo Levenshtein e precisa melhorar um pouco, descrevo algumas heurísticas muito eficazes nesta solução:
Obtendo a correspondência de string mais próxima
A chave é que você chegue a 3 ou 4 (ou mais) métodos para avaliar a semelhança entre suas frases (a distância de Levenshtein é apenas um método) - e então, usando exemplos reais de strings que você deseja igualar como semelhantes, você ajusta os pesos e combinações dessas heurísticas até obter algo que maximize o número de correspondências positivas.Então você usa essa fórmula para todas as partidas futuras e verá ótimos resultados.
Se um usuário estiver envolvido no processo, também é melhor fornecer uma interface que permita ao usuário ver correspondências adicionais com alta classificação em similaridade, caso discordem da primeira escolha.
Aqui está um trecho da resposta vinculada.Se você quiser usar algum código como está, peço desculpas antecipadamente por ter que converter VBA em C#.
Uma métrica simples, rápida e muito útil.Usando isso, criei duas métricas separadas para avaliar a semelhança de duas strings.Um eu chamo de "valuePhrase" e outro eu chamo de "valueWords".valuePhrase é apenas a distância de Levenshtein entre as duas frases, e valueWords divide a string em palavras individuais, com base em delimitadores como espaços, travessões e qualquer outra coisa que você desejar, e compara cada palavra entre si, resumindo o mais curto Distância de Levenshtein conectando duas palavras quaisquer.Essencialmente, mede se a informação contida numa “frase” está realmente contida noutra, tal como uma permutação palavra-a-palavra.Passei alguns dias como um projeto paralelo, descobrindo a maneira mais eficiente possível de dividir uma string com base em delimitadores.
função valueWords, valuePhrase e 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
Medidas de Similaridade
Usando essas duas métricas, e uma terceira que simplesmente calcula a distância entre duas strings, tenho uma série de variáveis nas quais posso executar um algoritmo de otimização para obter o maior número de correspondências.A correspondência difusa de strings é, em si, uma ciência difusa e, portanto, ao criar métricas linearmente independentes para medir a similaridade de strings e ter um conjunto conhecido de strings que desejamos combinar entre si, podemos encontrar os parâmetros que, para nossos estilos específicos de strings, fornecem os melhores resultados de correspondência difusa.
Inicialmente, o objetivo da métrica era ter um valor de pesquisa baixo para uma correspondência exata e aumentar os valores de pesquisa para medidas cada vez mais permutadas.Em um caso impraticável, isso foi bastante fácil de definir usando um conjunto de permutações bem definidas e projetando a fórmula final de forma que eles tivessem resultados de valores de pesquisa crescentes conforme desejado.
Como você pode ver, as duas últimas métricas, que são métricas de correspondência difusa de strings, já têm uma tendência natural de atribuir pontuações baixas a strings que deveriam corresponder (na diagonal).Isso é muito bom.
AplicativoPara permitir a otimização da correspondência difusa, pondero cada métrica.Como tal, cada aplicação de correspondência difusa de strings pode ponderar os parâmetros de maneira diferente.A fórmula que define a pontuação final é uma simples combinação das métricas e seus pesos:
value = Min(phraseWeight*phraseValue, wordsWeight*wordsValue)*minWeight +
Max(phraseWeight*phraseValue, wordsWeight*wordsValue)*maxWeight + lengthWeight*lengthValue
Usando um algoritmo de otimização (a rede neural é melhor aqui porque é um problema discreto e multidimensional), o objetivo agora é maximizar o número de correspondências.Criei uma função que detecta o número de correspondências corretas de cada conjunto entre si, como pode ser visto nesta imagem final.Uma coluna ou linha recebe um ponto se a pontuação mais baixa for atribuída à sequência que deveria ser correspondida, e pontos parciais serão dados se houver empate para a pontuação mais baixa e a correspondência correta estiver entre as sequências empatadas.Eu então otimizei.Você pode ver que uma célula verde é a coluna que melhor corresponde à linha atual e um quadrado azul ao redor da célula é a linha que melhor corresponde à coluna atual.A pontuação no canto inferior é aproximadamente o número de partidas bem-sucedidas e é isso que dizemos ao nosso problema de otimização para maximizar.
Parece que o que você deseja pode ser uma correspondência de substring mais longa.Ou seja, no seu exemplo, dois arquivos como
Trash..Thash..Song_Name_mp3.mp3 e Garbage..spotch..Song_Name_Mp3.mp3
acabaria parecendo o mesmo.
Você precisaria de algumas heurísticas, é claro.Uma coisa que você pode tentar é colocar a corda em um conversor soundex.Soundex é o “codec” usado para ver se as coisas “soam” iguais (como você diria a uma operadora de telefonia).É mais ou menos uma transliteração semi-prova de fonética grosseira e de pronúncia incorreta.É definitivamente mais pobre que a distância de edição, mas muito, muito mais barato.(O uso oficial é para nomes e utiliza apenas três caracteres.Não há razão para parar por aí, basta usar o mapeamento para cada caractere da string.Ver Wikipédia para detalhes)
Então, minha sugestão seria soar suas cordas, cortar cada uma delas em algumas tranches de comprimento (digamos 5, 10, 20) e então apenas observar os clusters.Dentro dos clusters, você pode usar algo mais caro, como distância de edição ou substring máxima.
Há muito trabalho feito em problemas relacionados de alinhamento de sequência de DNA (pesquisa por "alinhamento de sequência local") - o algoritmo clássico é "Needleman-Wunsch" e os modernos mais complexos também são fáceis de encontrar.A idéia é - semelhante à resposta de Greg - em vez de identificar e comparar palavras-chave, tentar encontrar as substrings mais vagamente correspondentes em seqüências longas.
Sendo triste, se o único objetivo for classificar músicas, uma série de expressões regulares para cobrir possíveis esquemas de nomenclatura provavelmente funcionariam melhor do que qualquer algoritmo genérico.
Existe um Repositório GitHub implementação de vários métodos.
