Coincidencia difusa usando T-SQL

Tengo una tabla Personas con datos personales, etc. Hay muchas columnas, pero las que nos interesan aquí son: addressindex , lastname y firstname donde addressindex es una dirección única que se abre hacia la puerta del apartamento. Entonces, si tengo ‘como a continuación’ dos personas con el lastname y uno los firstnames son los mismos, lo más probable es que sean duplicados.

Necesito una forma de listar estos duplicados.

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

Sé cómo hacer esto si tuviera que coincidir exactamente en todas las columnas, pero necesito una coincidencia aproximada para hacer el truco con (del ejemplo anterior) un resultado como:

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

¿Alguna pista sobre cómo resolver esto de una buena manera?

Descubrí que las cosas que SQL Server te da para hacer coincidencias difusas son bastante torpes. He tenido muy buena suerte con mis propias funciones de CLR usando el algoritmo de distancia de Levenshtein y algunas ponderaciones. Usando ese algoritmo, hice una UDF llamada GetSimilarityScore que toma dos cadenas y devuelve una puntuación entre 0.0 y 1.0. Cuanto más cerca de 1.0 esté el partido, mejor. Luego, consulte con un umbral de> = 0.8 o más para obtener las coincidencias más probables. Algo como esto:

 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 

Simplemente no lo hagas con mesas realmente grandes. Es un proceso lento

Aquí están las UDF de 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 

Además de la otra buena información aquí, es posible que desee considerar el uso del algoritmo fonético Double Metaphone , que generalmente se considera mejor que SOUNDEX .

Tim Pfeiffer detalla una implementación en SQL en su artículo Double Metaphone Sounds Great Convierte el algoritmo C ++ Double Metaphone a T-SQL (originalmente en SQL Mag y luego en SQL Server Pro ).

Eso ayudará a emparejar los nombres con pequeños errores ortográficos, por ejemplo, Carl vs. Karl .

Actualización : Parece que el código descargable actual se ha ido, pero aquí hay una implementación encontrada en un repository de Github que parece haber clonado el código original

Utilizaría la indexación de texto completo de SQL Server, que le permitirá hacer búsquedas y devolver cosas que no solo contengan la palabra sino que también pueden tener un error de ortografía.

Desde el primer lanzamiento de Master Data Services, tiene acceso a algoritmos de lógica difusa más avanzados que lo que implementa SOUNDEX. Por lo tanto, siempre que tenga MDS instalado, podrá encontrar una función llamada Similitud () en el esquema mdq (base de datos MDS).

Más información sobre cómo funciona: http://blog.hoegaerden.be/2011/02/05/finding-similar-strings-with-fuzzy-logic-functions-built-into-mds/

Personalmente utilizo una implementación CLR del algoritmo Jaro-Winkler que parece funcionar bastante bien, tiene problemas con cadenas de más de 15 caracteres y no le gusta la coincidencia de direcciones de correo electrónico, pero es bastante buena. Se puede encontrar una guía de implementación completa. aquí

Si no puede usar las funciones de CLR por cualquier motivo, tal vez podría intentar ejecutar los datos a través de un paquete de SSIS (usando la búsqueda de transformación difusa) – detallado aquí

En lo que respecta a la eliminación de errores, su partición y coincidencia de cuerdas es excelente en el primer corte. Si hay elementos conocidos sobre los datos que pueden aprovecharse para reducir la carga de trabajo y / o producir mejores resultados, siempre es bueno aprovecharlos. Tenga en cuenta que, a menudo, para eliminar el duplicado, es imposible eliminar por completo el trabajo manual, aunque puede hacerlo mucho más fácil capturando tanto como puede de forma automática y luego generando informes de sus “casos de incertidumbre”.

En cuanto a la coincidencia de nombres: SOUNDEX es horrible para la calidad de la coincidencia y especialmente malo para el tipo de trabajo que estás tratando de hacer, ya que coincidirá con cosas que están demasiado lejos del objective. Es mejor usar una combinación de resultados de doble metafonía y la distancia de Levenshtein para realizar la coincidencia de nombres. Con un sesgo apropiado, esto funciona muy bien y probablemente podría usarse para un segundo pase después de hacer una limpieza en sus conocimientos.

También es posible que desee considerar el uso de un paquete SSIS y buscar en las transformaciones de búsqueda difusa y agrupamiento (http://msdn.microsoft.com/en-us/library/ms345128(SQL.90).aspx).

También es posible utilizar SQL Full-Text Search (http://msdn.microsoft.com/en-us/library/cc879300.aspx), pero es probable que no sea apropiado para su dominio de problema específico.

Puede usar SOUNDEX y la función DIFERENCIA relacionada en SQL Server para buscar nombres similares. La referencia en MSDN está aquí .

hacerlo de esta forma

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

y luego crea un disparador

  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; 

ahora lo que puedo hacer es crear un procedimiento que se parece a esto

  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 

esto le devolverá todos los nombres que coinciden con los nombres proporcionados por un personid particular

    Intereting Posts