Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Microsoft SQL Server Новый топик    Ответить
 Сравнение результатов поиска  [new]
Santa89
Member

Откуда:
Сообщений: 1471
Всем привет!

Допустим в таблице есть такие значения:

DECLARE @T TABLE (Name varchar(20))

INSERT INTO @T
SELECT 'Михаил' UNION 
SELECT 'Михалыч' UNION
SELECT 'Михаинский' UNION
SELECT 'Михайловский' 


У меня есть строка для поиска - допустим "Михаил"
Какими средствами я могу получить данные которые бы показывали мне насколько каждая из строк в таблице @T соответствует моему поисковому слову?
Допустим первая строка это совпадение 6 символов из 6, во второй - только 4 из 6, в третьей - 5 из 6 и.т.д.

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

Как можно решать такие задачи?
Полнотекстовый индекс, подключение CLR - библиотек?
19 мар 18, 22:07    [21269714]     Ответить | Цитировать Сообщить модератору
 Re: Сравнение результатов поиска  [new]
alexeyvg
Member

Откуда: Moscow
Сообщений: 30786
Santa89
Как можно решать такие задачи?
Полнотекстовый индекс, подключение CLR - библиотек?
SOUNDEX, DIFFERENCE, полнотекстовый индекс, подключение CLR - библиотек
19 мар 18, 23:01    [21269843]     Ответить | Цитировать Сообщить модератору
 Re: Сравнение результатов поиска  [new]
uaggster
Member

Откуда:
Сообщений: 767
Santa89
подключение CLR - библиотек?

Я себе наваячил CLR сборку, и использую ее.
+

Imports System
Imports System.Collections.Generic
Imports System.Data
Imports System.Data.SqlClient
Imports System.Data.SqlTypes
Imports Microsoft.SqlServer.Server
Imports Microsoft.VisualBasic

Partial Public Class UserDefinedFunctions

    Private Structure RetCount
        Public lngSubRows As Integer
        Public lngCountLike As Integer
    End Structure

    'Нечеткое сравнение строк 
    'Аргументы: 
    '   lngMaxLen - максимальная длина сравниваемых подстрок (читайте описание алгоритма сравнения строк), 
    '   strStringMatching - первая строка,
    '   strStringStandart - вторая строка, 
    '   lngCase - тип сравнения (без учёта - 0, с учётом регистра - 1)
    'Назначение: Нечеткое сравнение двух строк 
    'Возвращает: Возвращает коэффициент совпадения строк от 0 до 100 
    '   (0 - строки не совпадают, 100 - полное совпадение)
    'Алгоритм сравнения строк Функция нечёткого сравнения использует в качестве аргументов две строки и параметр сравнения - максимальную длину
    'сравниваемых подстрок. Результатом работы функции является число, лежащее в пределах от 0 до 1. 0 соответствует полному 
    'несовпадению двух строк, а 1 - полной (в определённом ниже смысле) их идентичности. Сравнение строк происходит по следующей схеме. 
    'Пусть, например, в качестве аргументов заданы две строки "test" и "text" и некоторая максимальная длина подстрок, скажем, 4. 
    'Функция сравнения составляет все возможные комбинации подстрок с длиной вплоть до указанной и подсчитывает их совпадения в двух сравниваемых строках. 
    'Количество совпадений, разделённое на число вариантов, объявляется коэффициентом схожести строк и выдаётся в качестве результата работы функции. 

    <Microsoft.SqlServer.Server.SqlFunction()>
    Public Shared Function IndistinctMatching(MaxLen As SqlInt32, StringMatching As SqlString, StringStandart As SqlString, MatchingCase As SqlInt32) As SqlInt32
        Dim gret As RetCount
        Dim tret As RetCount
        Dim lngCurLen As Integer

        If MaxLen.IsNull Or MatchingCase.IsNull Or StringMatching.IsNull Or StringStandart.IsNull Then
            Return SqlInt32.Null
        End If

        If MaxLen = 0 Or CType(StringMatching, String).Length = 0 Or CType(StringStandart, String).Length = 0 Then
            IndistinctMatching = 0
            Exit Function
        End If

        Dim _CompareMethod As CompareMethod
        If MatchingCase = 0 Then _CompareMethod = CompareMethod.Text Else _CompareMethod = CompareMethod.Binary

        gret.lngCountLike = 0
        gret.lngSubRows = 0
        For lngCurLen = 1 To CType(MaxLen, Integer)
            tret = MatchingStrings(CType(StringMatching, String), CType(StringStandart, String), lngCurLen, _CompareMethod)
            gret.lngCountLike = gret.lngCountLike + tret.lngCountLike
            gret.lngSubRows = gret.lngSubRows + tret.lngSubRows
            tret = MatchingStrings(CType(StringStandart, String), CType(StringMatching, String), lngCurLen, _CompareMethod)
            gret.lngCountLike = gret.lngCountLike + tret.lngCountLike
            gret.lngSubRows = gret.lngSubRows + tret.lngSubRows
        Next lngCurLen
        If gret.lngSubRows = 0 Then
            Return 0
        End If
        Return CType((gret.lngCountLike / gret.lngSubRows) * 100, SqlInt32)
    End Function

    Private Shared Function MatchingStrings(strA As String, strB As String, lngLen As Integer, lngCase As CompareMethod) As RetCount
        Dim tret As RetCount
        Dim y As Integer, z As Integer
        Dim strta As String
        Dim strtb As String

        For z = 0 To strA.Length - lngLen
            strta = strA.Substring(z, lngLen)
            For y = 0 To strB.Length - lngLen
                strtb = strB.Substring(y, lngLen)
                If StrComp(strta, strtb, lngCase) = 0 Then
                    tret.lngCountLike = tret.lngCountLike + 1
                    Exit For
                End If
            Next y
            tret.lngSubRows = tret.lngSubRows + 1
        Next z
        MatchingStrings.lngCountLike = tret.lngCountLike
        MatchingStrings.lngSubRows = tret.lngSubRows
    End Function

    'Дистанция Левенштейна
    '"Наивный" алгоритм из Викиучебника
    'Сравнение без учета регистра
    <Microsoft.SqlServer.Server.SqlFunction()>
    Public Shared Function LevenshteinDistance(source As SqlString, target As SqlString) As SqlInt32

        'Если одна из строк неизвестна - результат неизвестен
        If source.IsNull Or target.IsNull Then
            Return SqlInt32.Null
        End If

        Dim l1 As Integer = CType(source, String).Length
        Dim l2 As Integer = CType(target, String).Length

        ' Если одна из строк пустая - результат - размер непустой строки
        If l1 = 0 Or l2 = 0 Then
            Return Math.Max(l1, l2)
        End If

        Dim m(l1, l2) As Integer
        Dim diff As Integer

        For i As Integer = 0 To l1
            m(i, 1) = i
        Next

        For j As Integer = 0 To l2
            m(1, j) = j
        Next

        For i As Integer = 1 To l1
            For j As Integer = 1 To l2
                If CType(source, String)(i - 1) = CType(target, String)(j - 1) Then diff = 0 Else diff = 1
                m(i, j) = Math.Min(Math.Min(m(i - 1, j) + 1, m(i, j - 1) + 1), m(i - 1, j - 1) + diff)
            Next
        Next

        Return m(l1, l2)
    End Function

    'Дистанция Дамерау-Левенштейна
    '"Наивный" алгоритм из Викиучебника
    'Сравнение без учета регистра
    <Microsoft.SqlServer.Server.SqlFunction()>
    Public Shared Function DamerauLevenshteinDistance(source As SqlString, target As SqlString) As SqlInt32

        'Если одна из строк неизвестна - результат неизвестен
        If source.IsNull Or target.IsNull Then
            Return SqlInt32.Null
        End If

        Dim l1 As Integer = CType(source, String).Length
        Dim l2 As Integer = CType(target, String).Length

        ' Если одна из строк пустая - результат - размер непустой строки
        If l1 = 0 Or l2 = 0 Then
            Return Math.Max(l1, l2)
        End If

        Dim h(l1 + 2, l2 + 2) As Integer
        Dim INF As Integer = l1 + l2

        h(0, 0) = INF

        For i As Integer = 0 To l1
            h(i + 1, 1) = i
            h(i + 1, 0) = INF
        Next

        For j As Integer = 0 To l2
            h(1, j + 1) = j
            h(0, j + 1) = INF
        Next

        Dim sd As New SortedDictionary(Of Char, Integer)
        For Each letter As Char In CType(source, String) & CType(target, String)
            If Not sd.ContainsKey(letter) Then sd.Add(letter, 0)
        Next

        For i As Integer = 1 To l1
            Dim DB As Integer = 0
            For j As Integer = 1 To l2
                Dim i1 As Integer = sd(CType(target, String)(j - 1))
                Dim j1 As Integer = DB
                If CType(source, String)(i - 1) = CType(target, String)(j - 1) Then
                    h(i + 1, j + 1) = h(i, j)
                    DB = j
                Else
                    h(i + 1, j + 1) = Math.Min(h(i, j), Math.Min(h(i + 1, j), h(i, j + 1))) + 1
                End If
                h(i + 1, j + 1) = Math.Min(h(i + 1, j + 1), h(i1, j1) + (i - i1 - 1) + 1 + (j - j1 - 1))
            Next
            sd(CType(source, String)(i - 1)) = i
        Next
        Return h(l1 + 1, l2 + 1)
    End Function

    'Инкапсулирует Regex.Replace
    <Microsoft.SqlServer.Server.SqlFunction()>
    Public Shared Function RegexReplace(source As SqlString, pattern As SqlString) As SqlString
        If source.IsNull Or pattern.IsNull Then
            Return SqlString.Null
        End If
        Return Text.RegularExpressions.Regex.Replace(source.ToString, pattern.ToString, String.Empty)
    End Function

End Class


Для эпизодических, не требовательных к производительности задач - вполне прокатывает.
20 мар 18, 10:57    [21270596]     Ответить | Цитировать Сообщить модератору
 Re: Сравнение результатов поиска  [new]
Minamoto
Member

Откуда: Москва
Сообщений: 1162
Santa89, это называется "Нечеткий поиск", один из алгоритмов, которые часто используется - это метод N-грам.
Я когда то сам реализовывал, но не публиковал нигде, ссылку не дам, но вот по поиску такой вариант находится:

https://social.technet.microsoft.com/wiki/contents/articles/33419.sql-server-implementation-of-n-gram-search-index.aspx
20 мар 18, 11:46    [21270806]     Ответить | Цитировать Сообщить модератору
 Re: Сравнение результатов поиска  [new]
aleksrov
Member

Откуда:
Сообщений: 948
Minamoto,

А я ссылку дам :) Хотя писал не я.
https://sqlperformance.com/2017/09/sql-performance/sql-server-trigram-wildcard-search
20 мар 18, 12:10    [21270913]     Ответить | Цитировать Сообщить модератору
 Re: Сравнение результатов поиска  [new]
Santa89
Member

Откуда:
Сообщений: 1471
Ребят, супер, спасибо!
Сейчас начну вникать...
20 мар 18, 17:15    [21272286]     Ответить | Цитировать Сообщить модератору
 Re: Сравнение результатов поиска  [new]
Santa89
Member

Откуда:
Сообщений: 1471
Нашел интересный коммент с Хабра:
Большой минус триграмм — на коротких словах (5 символов) они работают неадекватно при такой популярной опечатке, как перепутанные символы, например: 'table' % 'tbale' = 0.2. 
20 мар 18, 17:58    [21272425]     Ответить | Цитировать Сообщить модератору
 Re: Сравнение результатов поиска  [new]
Santa89
Member

Откуда:
Сообщений: 1471
uaggster,

а почему именно CLR? Ведь такой же алгоритм можно наваять на TSQL, даже на StackOverflow есть примеры, легче поддерживать было бы...
20 мар 18, 18:35    [21272493]     Ответить | Цитировать Сообщить модератору
 Re: Сравнение результатов поиска  [new]
Santa89
Member

Откуда:
Сообщений: 1471
aleksrow,

описанный метод плох тем, что он просто выводит результаты поиска в строку, но не ранжирует эти результаты по релевантности
22 мар 18, 15:41    [21278017]     Ответить | Цитировать Сообщить модератору
 Re: Сравнение результатов поиска  [new]
iap
Member

Откуда: Москва
Сообщений: 46953
Много было тут таких тем. Вот одна из них:
Расстояние между строками
22 мар 18, 15:53    [21278071]     Ответить | Цитировать Сообщить модератору
Все форумы / Microsoft SQL Server Ответить