Нечеткое сопоставление с использованием T-SQL

Ответ 1

Я обнаружил, что материал, который SQL Server дает вам, делает нечеткое соответствие довольно неуклюжим. Мне очень повезло с моими собственными функциями CLR, используя алгоритм расстояния Левенштейна и некоторый вес. Используя этот алгоритм, я сделал UDF под названием GetSimilarityScore, который берет две строки и возвращает результат между 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 UDFs:

''' <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

Ответ 2

В дополнение к другой полезной информации здесь вы можете рассмотреть использование фонетического алгоритма Double Metaphone, который намного превосходит SOUNDEX. Существует Transact-SQL версия (ссылка на код здесь).

Это поможет совместить имена с небольшими орфографическими ошибками, например, Карлом и Карлом.

Ответ 3

Я бы использовал SQL Server Full Text Indexing, который позволит вам выполнять поиск и возвращать вещи, которые не только содержат слово, но также могут иметь орфографическую ошибку.

Ответ 4

С момента первого выпуска Master Data Services у вас есть доступ к более совершенным алгоритмам с нечеткой логикой, чем реализуется SOUNDEX. Таким образом, при условии, что у вас установлен MDS, вы сможете найти функцию Сходство() в схеме mdq (база данных MDS).

Дополнительная информация о том, как это работает: http://blog.hoegaerden.be/2011/02/05/finding-similar-strings-with-fuzzy-logic-functions-built-into-mds/

Ответ 5

Я лично использую реализацию CLR алгоритма Jaro-Winkler, который, кажется, работает очень хорошо - он немного борется со строками дольше, чем примерно 15 символов и не нравится сопоставление адресов электронной почты, но в остальном это неплохо - полное руководство по реализации можно найти здесь

Если вы не можете использовать функции CLR по каким-либо причинам, возможно, вы можете попробовать запустить данные через пакет SSIS (используя поиск нечеткого преобразования) - подробный здесь

Ответ 6

Что касается дедублирования вещей, то ваша раскол и совпадение строк великолепны. Если известны данные о данных, которые могут быть использованы для уменьшения рабочей нагрузки и/или получения лучших результатов, всегда полезно воспользоваться ими. Имейте в виду, что часто для устранения дублирования невозможно полностью исключить ручную работу, хотя вы можете сделать это намного проще, поймав столько, сколько сможете, и затем создайте отчеты о своих "случаях неопределенности".

Что касается соответствия имени: SOUNDEX ужасен для качества соответствия и особенно плохого для типа работы, которую вы пытаетесь сделать, поскольку это будет соответствовать вещам, которые слишком далеки от цели. Лучше использовать комбинацию двойных результатов метафонов и расстояние Левенштейна для выполнения сопоставления имен. При соответствующем смещении это работает очень хорошо и, вероятно, может быть использовано для второго прохода после выполнения очистки ваших известных.

Вы также можете рассмотреть возможность использования пакета SSIS и поиск преобразований нечеткого поиска и группировки (http://msdn.microsoft.com/en-us/library/ms345128(SQL.90).aspx).

Использование полнотекстового поиска SQL (http://msdn.microsoft.com/en-us/library/cc879300.aspx) также возможно, но, вероятно, не подходит для вашего конкретного проблемного домена.

Ответ 7

Вы можете использовать SOUNDEX и соответствующую функцию DIFFERENCE в SQL Server, чтобы найти похожие имена. Ссылка на MSDN здесь.

Ответ 8

сделайте это так

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

а затем создать триггер

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

теперь, что я могу сделать, я могу создать процедуру, которая выглядит примерно так:

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

это вернет вам все имена, которые почти совпадают с именами, предоставленными для определенного лица