Поиск в основном совпадающих символов [дубликат]

61
задан MrLore 18 September 2014 в 08:01
поделиться

8 ответов

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

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

4
ответ дан Dibstar 26 August 2018 в 11:37
поделиться

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

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

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

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

1
ответ дан James 26 August 2018 в 11:37
поделиться

В дополнение к другой полезной информации здесь вы можете рассмотреть использование фонетического алгоритма Double Metaphone , который обычно считается лучшим, чем SOUNDEX .

Тим Пфайфер подробно описывает реализацию в SQL в своей статье Двойной звук метафонов Великий Преобразование алгоритма двойного метафона C ++ в T-SQL (изначально в SQL Mag & amp; тогда в SQL Server Pro ).

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

Обновление: актуальная загружаемая код кажется ушел, но вот реализация, найденная в github repo , которая, похоже, клонировала исходный код

14
ответ дан KyleMit 26 August 2018 в 11:37
поделиться

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

0
ответ дан Matt Spradley 26 August 2018 в 11:37
поделиться

Я обнаружил, что материал 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

Просто не делайте этого с действительно большими таблицами. Это медленный процесс.

Вот CLF 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
17
ответ дан mattmc3 26 August 2018 в 11:37
поделиться

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

         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 personid=@personid;

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

         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

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

0
ответ дан Rakshith 26 August 2018 в 11:37
поделиться

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

7
ответ дан Russ Bradberry 26 August 2018 в 11:37
поделиться

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

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

7
ответ дан Valentino Vranken 26 August 2018 в 11:37
поделиться
Другие вопросы по тегам:

Похожие вопросы: