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

Question

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

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

Answer 1

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

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

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

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

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

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

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

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

EDIT2: Если вы не хотите копаться в SSIS и все еще боретесь с производительностью алгоритма Levensthein Distance, вы можете попробовать этот алгоритм , который выглядит менее сложным.

Answer 2

Для всех пользователей Google, которые сталкиваются с этим вопросом, хотя он уже помечен как ответный, я решил поделиться некоторым кодом, чтобы помочь с этим.Если вы можете выполнять пользовательские функции 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

Answer 3

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

Answer 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

надеюсьэто помогает.

Answer 5

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

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

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

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

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