使用T-SQL进行模糊匹配

Question

我有一个表的人与personaldata等.有很多专栏,但这里曾经感兴趣的是:addressindex,lastname以及firstname在addressindex公寓门口钻一个独特的地址.因此,如果我"喜欢下面"两个人和lastname一个人firstnames相同,他们很可能是重复的.

我需要一种方法来列出这些重复项.

tabledata:

personid     1
firstname    "Carl"
lastname     "Anderson"
addressindex 1

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

我知道如果我要在所有列上完全匹配,但是我需要模糊匹配来完成这个技巧(来自上面的例子),结果如下:

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

关于如何以一种好的方式解决这个问题的任何提示？

Answer 1

我发现SQL Server让你做模糊匹配的东西非常笨重.我使用Levenshtein距离算法和一些加权对我自己的CLR函数运气很好.使用该算法,我制作了一个名为GetSimilarityScore的UDF,它接受两个字符串并返回0.0到1.0之间的分数.匹配越接近1.0越好.然后,查询阈值> = 0.8左右以获得最可能的匹配.像这样的东西:

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

只是不要用非常大的表来做.这是一个缓慢的过程.

这是CLR UDF:

''' <summary>
''' Compute the distance between two strings.
''' </summary>
''' <param name="s1">The first of the two strings.</param>
''' <param name="s2">The second of the two strings.</param>
''' <returns>The Levenshtein cost.</returns>
<Microsoft.SqlServer.Server.SqlFunction()> _
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

''' <summary>
''' 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.
''' </summary>
<Microsoft.SqlServer.Server.SqlFunction()> _
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

''' <summary>
''' Sorts all the alpha numeric characters in the string in alphabetical order
''' and removes everything else.
''' </summary>
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

''' <summary>
''' Removes all non-alpha numeric characters and then sorts
''' the words in alphabetical order.
''' </summary>
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

Answer 2

除了这里的其他好信息,你可能还想考虑使用Double Metaphone语音算法,它通常被认为比SOUNDEX更好.

Tim Pfeiffer在他的文章Double Metaphone Sounds Great C++ Double Metaphone算法转换为T-SQL(最初在SQL Mag中然后在SQL Server Pro中)中详细介绍了SQL中的实现.

这将有助于匹配名称与轻微的拼写错误,例如,卡尔与卡尔.

更新:实际的可下载代码似乎已经消失了,但是这里是一个在github repo上找到的实现,似乎克隆了原始代码

Answer 3

我会使用SQL Server全文索引,这将允许您进行搜索并返回不仅包含单词而且可能有拼写错误的内容.

Answer 4

自Master Data Services首次发布以来,您可以访问比SOUNDEX实现的更先进的模糊逻辑算法.因此,如果您已安装MDS,您将能够在mdq架构(MDS数据库)中找到名为Similarity()的函数.

有关其工作原理的更多信息:http://blog.hoegaerden.be/2011/02/05/finding-similar-strings-with-fuzzy-logic-functions-built-into-mds/

Answer 5

我个人使用Jaro-Winkler算法的 CLR 实现，该算法似乎工作得很好 - 它在处理长度超过 15 个字符的字符串时有点困难，并且不喜欢匹配电子邮件地址，但在其他方面相当不错 - 完整的实现指南可以在在这里找到

\n

这是 t-sql 中的示例

\n

SELECT * \nFROM myTable1 as t1 \nINNER JOIN myTable2 as t2 \nON dbo.StringDistance(t1.MyField, t2.MyField) > 0.85\n

\n

与 soundex 相比，这种方法的一个优点是可以更轻松地处理拼写错误，因为如果拼写错误产生不同的声音，那么 SOUNDEX 将无法正确匹配它。

\n

例如，如果您输入 \xe2\x80\x9cytpe\xe2\x80\x9d 而不是 \xe2\x80\x9ctype\xe2\x80\x9d，那么 SOUNDEX 将不会为您提供正确的匹配项。SOUNDEX(\xe2\x80\x98ytpe\xe2\x80\x99) 和 SOUNDEX(\xe2\x80\x98type\xe2\x80\x99) 返回的代码如下：

\n

ytpe Y310

\n

T100型

\n

如果我使用 Jaro-Winkler StringDistance(\xe2\x80\x98ytpe\xe2\x80\x99,\xe2\x80\x99type\xe2\x80\x99) 这是我得到的 0.91(6)，这意味着它是一个很好的匹配。请记住 1 \xe2\x80\x93 是完全匹配的，因此 0.91 非常接近它。

\n

如果您出于某种原因无法使用 CLR 函数，也许您可​​以尝试通过 SSIS 包运行数据（使用模糊转换查找） - 详细信息请参见此处

\n