Correspondência difusa usando T-SQL

Eu tenho uma tabela Pessoas com personaldata e assim por diante. Há muitas colunas, mas uma vez de interesse aqui são: addressindex , lastname e firstname onde addressindex é um endereço exclusivo perfurado até a porta do apartamento. Então, se eu tenho ‘como abaixo’ duas pessoas com o lastname e um o firstnames é o mesmo, provavelmente são duplicatas.

Eu preciso de uma maneira de listar essas duplicatas.

 tabledata: personid 1 firstname "Carl" lastname "Anderson" addressindex 1 personid 2 firstname "Carl Peter" lastname "Anderson" addressindex 1 

Eu sei como fazer isso se eu fosse corresponder exatamente em todas as colunas, mas eu preciso de correspondência difusa para fazer o truque com (a partir do exemplo acima) um resultado como:

 Row personid addressindex lastname firstname 1 2 1 Anderson Carl Peter 2 1 1 Anderson Carl ..... 

Alguma dica sobre como resolver isso de uma maneira boa?

Descobri que as coisas que o SQL Server lhe dá para fazer correspondências difusas são muito desajeitadas. Eu tive muita sorte com minhas próprias funções CLR usando o algoritmo de distância Levenshtein e algumas ponderações. Usando esse algoritmo, criei um UDF chamado GetSimilarityScore que usa duas strings e retorna uma pontuação entre 0.0 e 1.0. Quanto mais próximo de 1.0 for a partida, melhor. Em seguida, consulte um limite de> = 0,8 ou mais para obter as correspondências mais prováveis. Algo assim:

 if object_id('tempdb..#similar') is not null drop table #similar select a.id, ( select top 1 x.id from MyTable x where x.id <> a.id order by dbo.GetSimilarityScore(a.MyField, x.MyField) desc ) as MostSimilarId into #similar from MyTable a select *, dbo.GetSimilarityScore(a.MyField, c.MyField) from MyTable a join #similar b on a.id = b.id join MyTable c on b.MostSimilarId = c.id 

Apenas não faça isso com tabelas realmente grandes. É um processo lento.

Aqui estão os UDFs do CLR:

 '''  ''' Compute the distance between two strings. '''  ''' The first of the two strings. ''' The second of the two strings. ''' The Levenshtein cost.  _ Public Shared Function ComputeLevenstheinDistance(ByVal string1 As SqlString, ByVal string2 As SqlString) As SqlInt32 If string1.IsNull OrElse string2.IsNull Then Return SqlInt32.Null Dim s1 As String = string1.Value Dim s2 As String = string2.Value Dim n As Integer = s1.Length Dim m As Integer = s2.Length Dim d As Integer(,) = New Integer(n, m) {} ' Step 1 If n = 0 Then Return m If m = 0 Then Return n ' Step 2 For i As Integer = 0 To n d(i, 0) = i Next For j As Integer = 0 To m d(0, j) = j Next ' Step 3 For i As Integer = 1 To n 'Step 4 For j As Integer = 1 To m ' Step 5 Dim cost As Integer = If((s2(j - 1) = s1(i - 1)), 0, 1) ' Step 6 d(i, j) = Math.Min(Math.Min(d(i - 1, j) + 1, d(i, j - 1) + 1), d(i - 1, j - 1) + cost) Next Next ' Step 7 Return d(n, m) End Function '''  ''' Returns a score between 0.0-1.0 indicating how closely two strings match. 1.0 is a 100% ''' T-SQL equality match, and the score goes down from there towards 0.0 for less similar strings. '''   _ Public Shared Function GetSimilarityScore(string1 As SqlString, string2 As SqlString) As SqlDouble If string1.IsNull OrElse string2.IsNull Then Return SqlInt32.Null Dim s1 As String = string1.Value.ToUpper().TrimEnd(" "c) Dim s2 As String = string2.Value.ToUpper().TrimEnd(" "c) If s1 = s2 Then Return 1.0F ' At this point, T-SQL would consider them the same, so I will too Dim flatLevScore As Double = InternalGetSimilarityScore(s1, s2) Dim letterS1 As String = GetLetterSimilarityString(s1) Dim letterS2 As String = GetLetterSimilarityString(s2) Dim letterScore As Double = InternalGetSimilarityScore(letterS1, letterS2) 'Dim wordS1 As String = GetWordSimilarityString(s1) 'Dim wordS2 As String = GetWordSimilarityString(s2) 'Dim wordScore As Double = InternalGetSimilarityScore(wordS1, wordS2) If flatLevScore = 1.0F AndAlso letterScore = 1.0F Then Return 1.0F If flatLevScore = 0.0F AndAlso letterScore = 0.0F Then Return 0.0F ' Return weighted result Return (flatLevScore * 0.2F) + (letterScore * 0.8F) End Function Private Shared Function InternalGetSimilarityScore(s1 As String, s2 As String) As Double Dim dist As SqlInt32 = ComputeLevenstheinDistance(s1, s2) Dim maxLen As Integer = If(s1.Length > s2.Length, s1.Length, s2.Length) If maxLen = 0 Then Return 1.0F Return 1.0F - Convert.ToDouble(dist.Value) / Convert.ToDouble(maxLen) End Function '''  ''' Sorts all the alpha numeric characters in the string in alphabetical order ''' and removes everything else. '''  Private Shared Function GetLetterSimilarityString(s1 As String) As String Dim allChars = If(s1, "").ToUpper().ToCharArray() Array.Sort(allChars) Dim result As New StringBuilder() For Each ch As Char In allChars If Char.IsLetterOrDigit(ch) Then result.Append(ch) End If Next Return result.ToString() End Function '''  ''' Removes all non-alpha numeric characters and then sorts ''' the words in alphabetical order. '''  Private Shared Function GetWordSimilarityString(s1 As String) As String Dim words As New List(Of String)() Dim curWord As StringBuilder = Nothing For Each ch As Char In If(s1, "").ToUpper() If Char.IsLetterOrDigit(ch) Then If curWord Is Nothing Then curWord = New StringBuilder() End If curWord.Append(ch) Else If curWord IsNot Nothing Then words.Add(curWord.ToString()) curWord = Nothing End If End If Next If curWord IsNot Nothing Then words.Add(curWord.ToString()) End If words.Sort(StringComparer.OrdinalIgnoreCase) Return String.Join(" ", words.ToArray()) End Function 

Além das outras boas informações aqui, você pode considerar o uso do algoritmo fonético Double Metaphone , que geralmente é considerado melhor que SOUNDEX .

Tim Pfeiffer detalha uma implementação em SQL em seu artigo Double Metaphone Sounds Great Converta o algoritmo C ++ Double Metaphone em T-SQL (originalmente em SQL Mag e em SQL Server Pro ).

Isso ajudará na correspondência de nomes com ligeiros erros ortocharts, por exemplo, Carl vs. Karl .

Atualização : O código real para download parece ter desaparecido, mas aqui está uma implementação encontrada em um repository do github que parece ter clonado o código original

Eu usaria a Indexação de Texto Completo do SQL Server, que permitirá que você faça pesquisas e retorne coisas que não apenas contenham a palavra, mas também possam ter um erro de ortografia.

Desde o primeiro lançamento do Master Data Services, você tem access a algoritmos de lógica difusa mais avançados do que o SOUNDEX implementa. Assim, desde que você tenha o MDS instalado, você poderá encontrar uma function chamada Similarity () no esquema mdq (database MDS).

Mais informações sobre como funciona: http://blog.hoegaerden.be/2011/02/05/finding-similar-strings-with-fuzzy-logic-functions-built-into-mds/

Eu pessoalmente uso uma implementação CLR do algoritmo Jaro-Winkler que parece funcionar muito bem – ele se esforça um pouco com strings maiores que 15 caracteres e não gosta de endereços de e-mail correspondentes, mas é bastante bom – o guia de implementação completo pode ser encontrado Aqui

Se você não puder usar as funções do CLR por qualquer motivo, talvez possa tentar executar os dados por meio de um pacote do SSIS (usando a pesquisa de transformação difusa) – detalhado aqui

Em relação às coisas de duping, sua string dividida e combinada é ótima no primeiro corte. Se houver itens conhecidos sobre os dados que podem ser aproveitados para reduzir a carga de trabalho e / ou produzir melhores resultados, é sempre bom aproveitá-los. Tenha em mente que, muitas vezes, para a dedução, é impossível eliminar completamente o trabalho manual, embora seja muito mais fácil capturar o máximo possível automaticamente e gerar relatórios sobre os “casos de incerteza”.

Em relação à correspondência de nomes: SOUNDEX é horrível para a qualidade da correspondência e especialmente ruim para o tipo de trabalho que você está tentando fazer, pois ele irá corresponder a coisas que estão muito longe do alvo. É melhor usar uma combinação de resultados de metáfora dupla e a distância de Levenshtein para realizar a correspondência de nomes. Com um enviesamento apropriado, isso funciona muito bem e provavelmente poderia ser usado para uma segunda passagem depois de fazer uma limpeza em seus conhecidos.

Você também pode querer considerar o uso de um pacote SSIS e examinar transformações de pesquisa e agrupamento difusas (http://msdn.microsoft.com/en-us/library/ms345128(SQL.90).aspx).

Usar a pesquisa de texto completo do SQL (http://msdn.microsoft.com/en-us/library/cc879300.aspx) também é uma possibilidade, mas provavelmente não é apropriado ao seu domínio de problema específico.

Você pode usar a function SOUNDEX e DIFERENÇA relacionada no SQL Server para localizar nomes semelhantes. A referência no MSDN está aqui .

faça assim

  create table person( personid int identity(1,1) primary key, firstname varchar(20), lastname varchar(20), addressindex int, sound varchar(10) ) 

e depois criar um gatilho

  create trigger trigoninsert for dbo.person on insert as declare @personid int; select @personid=personid from inserted; update person set sound=soundex(firstname) where personid=@personid; 

agora o que eu posso fazer é que eu posso criar um procedimento que se parece com isso

  create procedure getfuzzi(@personid int) as declare @sound varchar(10); set @sound=(select sound from person where personid=@personid; select personid,firstname,lastname,addressindex from person where sound=@sound 

isso lhe devolverá todos os nomes que estão quase em conformidade com os nomes fornecidos por uma pessoa específica

    Intereting Posts