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

Откуда: Minsk
Сообщений: 59
Приветствую!

Задача в следующем
требуется сравнить две таблицы с именами и адресами компаний на предмет наибольшей похожести, то есть для компаний в ТАБЛИЦА1 поставить в соответствие наиболее похожую по написанию и присутствующим словам компанию из ТАБЛИЦА2.
Более того, нужно вывести некую метрику соответствия, например процент соответствия, чтобы в первую очередь рассматривать наиболее похожие результаты.

Объем таблиц:
ТАБЛИЦА1 40 000 записей
ТАБЛИЦА2 100 000 записей

Хочу применить возможности полнотекстового поиска MS SQL server (любой версии).

Вопрос:
можно ли в дополнительном столбце вывести процент соответствия при полнотекстовом поиске?
ну и может лучше как-то по-другому решить данную задачу, например сторонними библиотеками?
4 май 12, 13:25    [12507592]     Ответить | Цитировать Сообщить модератору
 Re: Процент совпадения при полнотекстовом поиске  [new]
invm
Member

Откуда: Москва
Сообщений: 9836
FTS вам слабо поможет.
https://www.sql.ru/forum/actualthread.aspx?bid=1&tid=928728&hl=
4 май 12, 13:27    [12507617]     Ответить | Цитировать Сообщить модератору
 Re: Процент совпадения при полнотекстовом поиске  [new]
MSSQL_USER
Member

Откуда: Minsk
Сообщений: 59
invm,

Ну я хочу задействовать полнотекстовый поиск для получения для каждой строки ТАБЛИЦА1 наиболее совпадающую строку из ТАБЛИЦА2, так как думаю мозговитые программеры SQL Server эти сравнения NxM выполнять быстрее - они же по FT-индексу поиск ведут + на низком уровне, на Сишнике, а то и на Асме.
Далее нужно расставить только метрики, как говорится - сравнить сравненное.
Вот надыбал алгоритм Левенштейна, буду прикручивать, отпишусь, если получится.

Может еще мысли какие, опыт? - спасибо.
4 май 12, 15:48    [12508961]     Ответить | Цитировать Сообщить модератору
 Re: Процент совпадения при полнотекстовом поиске  [new]
Andrey1306
Member

Откуда: Киев
Сообщений: 2611
Пришлось недавно таким же заниматься.
Алгоритм Левенштейна сразу применять сложно было (слишком долго сравнивается)

Поэтому сначала использовал метод Метод N-грамм http://habrahabr.ru/post/114997/.

и уже на более менее похожие названия натравливал Алгоритм Левенштейна.

Может не совсем правильно но ...
+

CREATE FUNCTION [dbo].[SplitNGramm](@Str nvarchar(4000), @Len int)
RETURNS @Results 
TABLE (Items nvarchar(4000))
AS BEGIN
	DECLARE @Counter int
	DECLARE @Slice nvarchar(4000)
	SELECT @Counter = 1
		IF @Str IS NULL RETURN
		SELECT @Str = REPLACE(@Str,' ', '')
		SELECT @Str = REPLACE(@Str,'-', '')
		SELECT @Str = REPLACE(@Str,'_', '')
		SELECT @Str = REPLACE(@Str,'+', '')
		IF LEN(@Str) < @Len
			INSERT INTO @Results(Items) VALUES(@Str)
		ELSE
			WHILE @Counter != 0
			BEGIN
				IF @Counter !=0
					SELECT @Slice = LEFT(@Str,@Len)
					ELSE
					SELECT @Slice = @Str
					
					INSERT INTO @Results(Items) VALUES(@Slice)
					SELECT @Str = RIGHT(@Str,LEN(@Str) - 1)
					SET @Counter = @Counter + 1
			IF LEN(@Str) = @Len-1 BREAK
			END
RETURN
END 




CREATE FUNCTION [dbo].[fnLevenshteinDistance]
(
	@string1 varchar(4000),
	@string2 varchar(4000)
	
)
RETURNS 
@Table  TABLE 
(
	-- Add the column definitions for the TABLE variable here
	Column_1 varchar(4000),
	Column_2 varchar(4000),
	Column_3 int
)
AS
BEGIN
	-- Fill the table variable with the rows for your result set
	
	
/***********************/

    declare @diff int
        declare @len1 int
        declare @len2 int
 
        set @len1 = len(@string1)
        set @len2 = len(@string2)
 
        declare @m table (i int, j int, val int)
 
        declare @i int, @j int
 
        set @i = 0
        while (@i <= @len1) 
        begin
                delete @m where i=@i and j=0
 
                insert into @m (i, j, val)
                values (@i, 0, @i)
                set @i = @i + 1
        end
 
        set @j = 0
        while (@j <= @len2)
        begin
                delete @m where i=0 and j=@j
 
                insert into @m (i, j, val)
                values (0, @j, @j)
                set @j = @j + 1
        end
 
 
        set @i = 1
        while (@i <= @len1) begin
                set @j = 1
                while (@j <= @len2) begin
 
                        if (substring(@string1, @i, 1) = substring(@string2, @j, 1))
                                set @diff = 0
                        else
                                set @diff = 1
 
 
                        declare @minval int
 
                        select @minval = min(val) 
                        from (
                                        select isnull(val, 0) + 1 as val
                                        from @m
                                        where i = @i-1 and j = @j
 
                                        union 
 
                                        select isnull(val, 0) + 1 as val
                                        from @m
                                        where i = @i and j = @j-1
 
                                        union
 
                                        select isnull(val, 0) + @diff as val
                                        from @m
                                        where i = @i-1 and j = @j-1
                                ) t
 
                        delete @m where i=@i and j=@j
 
                        insert into @m (i, j, val)
                        values (@i, @j, isnull(@minval, 0))
 
                        set @j = @j + 1                 
                end
                set @i = @i + 1
        end
 
        declare @retval int
        select @retval = isnull(val, 0) 
        from @m 
        where i = @len1 and j = @len2

/***********************/
	
	INSERT INTo @Table
		(Column_1, Column_2, Column_3)
	Values
		(@string1,@string2,@retval)
	RETURN 
END	 

4 май 12, 16:21    [12509265]     Ответить | Цитировать Сообщить модератору
 Re: Процент совпадения при полнотекстовом поиске  [new]
MSSQL_USER
Member

Откуда: Minsk
Сообщений: 59
Andrey1306, - СУПЕР !!! ТО, ЧТО НАДО !!!

Вот оптимизированную дистанцию Левенштейна нашел, быстрая, 100% работает, может кому надо:

CREATE FUNCTION uf_distance(@s1 nvarchar(3999), @s2 nvarchar(3999))
RETURNS int
AS
BEGIN
  DECLARE @s1_len int, @s2_len int, @i int, @j int, @s1_char nchar, @c int, @c_temp int,
    @cv0 varbinary(8000), @cv1 varbinary(8000)
  SELECT @s1_len = LEN(@s1), @s2_len = LEN(@s2), @cv1 = 0x0000, @j = 1, @i = 1, @c = 0
  WHILE @j <= @s2_len
    SELECT @cv1 = @cv1 + CAST(@j AS binary(2)), @j = @j + 1
  WHILE @i <= @s1_len
  BEGIN
    SELECT @s1_char = SUBSTRING(@s1, @i, 1), @c = @i, @cv0 = CAST(@i AS binary(2)), @j = 1
    WHILE @j <= @s2_len
    BEGIN
      SET @c = @c + 1
      SET @c_temp = CAST(SUBSTRING(@cv1, @j+@j-1, 2) AS int) +
        CASE WHEN @s1_char = SUBSTRING(@s2, @j, 1) THEN 0 ELSE 1 END
      IF @c > @c_temp SET @c = @c_temp
      SET @c_temp = CAST(SUBSTRING(@cv1, @j+@j+1, 2) AS int)+1
      IF @c > @c_temp SET @c = @c_temp
      SELECT @cv0 = @cv0 + CAST(@c AS binary(2)), @j = @j + 1
    END
    SELECT @cv1 = @cv0, @i = @i + 1
  END

  RETURN @c
END
4 май 12, 20:39    [12510647]     Ответить | Цитировать Сообщить модератору
Все форумы / Microsoft SQL Server Ответить