查找包含相似字符串的sql记录

Question

我有一个包含2列的表格: ID和Title，其中包含超过500.000条记录。例如：

ID  Title
--  ------------------------
1   Aliens
2   Aliens (1986)
3   Aliens vs Predator
4   Aliens 2
5   The making of "Aliens"

我需要找到非常相似的记录，我的意思是它们有3-6个字母的差异，通常这种差异是在标题的末尾。因此，我必须设计一个查询来返回1、2和4号记录。我已经查看了levenstein距离，但我不知道如何应用它。此外，由于记录的数量，查询不应该花费整个晚上。

感谢您的任何想法或建议

Answer 1

如果你真的想用你在问题中描述的精确方式来定义相似度，那么就像你所说的那样，你必须实现Levensthein距离计算。在由DataReader检索的每一行上计算的代码中，或作为SQL Server函数。

所述的问题实际上比乍看起来更棘手，因为您不能假设知道两个字符串之间相互共享的元素可能是什么。

因此，除了Levensthein距离之外，您可能还希望指定实际必须匹配的连续字符的最小数量(以便得出足够的相似性结论)。

总而言之:这听起来像是一个过于复杂和耗时/缓慢的方法。

有趣的是，在SQL Server2008中，您可以使用DIFFERENCE函数来做类似的事情。

它计算两个字符串的拼音值并计算其差值。我不确定您是否能让它正确地处理多个单词的表达式，比如电影标题，因为它不能很好地处理空格或数字，并且过于强调字符串的开头，但它仍然是一个值得注意的有趣谓词。

如果您实际上试图描述的是某种搜索功能，那么您应该研究一下SQL Server2008的Full Text Search功能。它提供了内置的Thesaurus support、花哨的SQL predicates和“最佳匹配”的排名机制。

编辑:如果你想消除重复，也许你可以看看SSIS Fuzzy Lookup and Fuzzy Group Transformation。我自己还没有试过，但它看起来是一个很有前途的线索。

EDIT2:如果您不想深入研究algorithm，并且仍然为Levensthein距离算法的性能而苦苦挣扎，那么您也许可以尝试一下这个SSIS，它看起来不那么复杂。

Answer 2

对于所有遇到这个问题的谷歌人来说，尽管它已经被标记为已回答，但我想我应该分享一些代码来帮助解决这个问题。如果您能够在SQL Server上执行CLR用户定义函数，则可以实现自己的Levensthein距离算法，然后在此基础上创建一个名为dbo.GetSimilarityScore()的“相似性分数”函数。我的评分不区分大小写，没有太多考虑混乱的词序和非字母数字字符的权重。您可以根据需要调整评分算法，但这是一个很好的开始。感谢this code project link帮我入门。

Option Explicit On
Option Strict On
Option Compare Binary
Option Infer On

Imports System
Imports System.Collections.Generic
Imports System.Data
Imports System.Data.SqlClient
Imports System.Data.SqlTypes
Imports System.Text
Imports System.Text.RegularExpressions
Imports Microsoft.SqlServer.Server

Partial Public Class UserDefinedFunctions

    Private Const Xms As RegexOptions = RegexOptions.IgnorePatternWhitespace Or RegexOptions.Multiline Or RegexOptions.Singleline
    Private Const Xmsi As RegexOptions = Xms Or RegexOptions.IgnoreCase

    ''' <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 score1 As SqlDouble = InternalGetSimilarityScore(s1, s2)
        If score1.IsNull Then Return SqlDouble.Null

        Dim mod1 As String = GetSimilarityString(s1)
        Dim mod2 As String = GetSimilarityString(s2)
        Dim score2 As SqlDouble = InternalGetSimilarityScore(mod1, mod2)
        If score2.IsNull Then Return SqlDouble.Null

        If score1 = 1.0F AndAlso score2 = 1.0F Then Return 1.0F
        If score1 = 0.0F AndAlso score2 = 0.0F Then Return 0.0F
        ' Return weighted result
        Return (score1 * 0.2F) + (score2 * 0.8F)
    End Function

    Private Shared Function InternalGetSimilarityScore(s1 As String, s2 As String) As SqlDouble
        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>
    ''' Removes all non-alpha numeric characters and then sorts
    ''' the words in alphabetical order.
    ''' </summary>
    Private Shared Function GetSimilarityString(s1 As String) As String
        Dim normString = Regex.Replace(If(s1, ""), "\W|_", " ", Xms)
        normString = Regex.Replace(normString, "\s+", " ", Xms).Trim()
        Dim words As New List(Of String)(normString.Split(" "c))
        words.Sort()
        Return String.Join(" ", words.ToArray())
    End Function

End Class

Answer 3

select id, title
from my_table
where 
    title like 'Aliens%' 
    and 
    len(rtrim(title)) < len('Aliens') + 7