Найти записи sql, содержащие похожие строки

У меня есть следующая таблица с двумя столбцами: 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. Я уже смотрел на расстояние левенштайн, но я не знаю, как его применять. Также из-за количества записей запрос не должен длиться всю ночь.

Спасибо за любую идею или предложение

Ответы

Ответ 1

Если вы действительно хотите определить сходство в точности так, как вы сформулировали его в своем вопросе, то вам, как вы говорите, придется выполнить вычисление расстояния Левенштейна. Либо в коде, рассчитанном для каждой строки, извлекаемой DataReader, либо в качестве функции SQL Server.

Указанная проблема на самом деле более сложна, чем может показаться на первый взгляд, потому что вы не можете предположить, что знаете, какие могут быть общие элементы между двумя строками.

Таким образом, в дополнение к Levensthein Distance вы, вероятно, также захотите указать минимальное количество последовательных символов, которые фактически должны совпадать (для того, чтобы можно было заключить достаточное сходство).

В итоге: это звучит как слишком сложный и трудоемкий/медленный подход.

Интересно, что в SQL Server 2008 у вас есть функция DIFFERENCE, которая может использоваться для чего-то подобного.

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

Если то, что вы на самом деле пытаетесь описать, - это какая-то функция поиска, то вам следует изучить возможности полнотекстового поиска в SQL Server 2008. Он предоставляет встроенную поддержку тезауруса, причудливые предикаты SQL и механизм ранжирования для "наилучших совпадений".

РЕДАКТИРОВАТЬ: Если вы хотите устранить дубликаты, может быть, вы могли бы взглянуть на SSIS Fuzzy Lookup и Fuzzy Group Transformation. Я не пробовал это сам, но это выглядит многообещающим лидерством.

РЕДАКТИРОВАТЬ 2: Если вы не хотите копаться в SSIS и все еще боретесь с производительностью алгоритма Levensthein Distance, вы можете попробовать этот алгоритм, который выглядит менее сложным.

Ответ 2

Для всех гуглеров, которые сталкиваются с этим вопросом, хотя он уже был отмечен как ответ, я решил, что поделился бы некоторым кодом, чтобы помочь с этим. Если вы можете выполнять определенные пользователем функции CLR на вашем SQL Server, вы можете реализовать свой собственный алгоритм Levensthein Distance, а затем создать функцию, которая дает вам "оценку подобия" под названием dbo.GetSimilarityScore(). Я основывал свою оценку нечувствительности к регистру, без особого веса, чтобы перепутать порядок слов и не буквенно-цифровые символы. Вы можете настроить свой алгоритм подсчета по мере необходимости, но это хороший старт. Подпишитесь на эту ссылку на проект кода, чтобы начать меня.

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

Ответ 3

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

Ответ 4

Из того, что вы спросили, я полагаю, что различия, которые вы ищете, не должны быть более одного слова в конце исходного названия. Вот почему возвращаются 1,2 и 4?

В любом случае я сделал запрос, который проверяет разницу в конце, состоит из одного слова без пробелов.

declare @title varchar(20)
set @title = 'Aliens'
select id, title
from movies with (nolock)
where ltrim(title) like @title + '%'
and Charindex(' ', ltrim(right(title, len(title) - len(@title)))) = 0
and len(ltrim(right(title, len(title) - len(@title)))) < 7

надеюсь, что это поможет.

Ответ 5

если вы используете SQL Server 2008, вы сможете использовать функциональность FULLTEXT.

Основные шаги:

1) Создайте полный текст по столбцу. Это будет означать каждую строку (stremmers, splitters и т.д.) И позволит вам искать строки "LIKE THIS".

Отказ от ответственности состоит в том, что мне никогда не приходилось его использовать, но я думаю, что он может делать то, что вы хотите.

Начните читать здесь: http://msdn.microsoft.com/en-us/library/ms142571.aspx