Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Microsoft SQL Server Новый топик    Ответить
 Корреляция двух текстовых строк. Как сосчитать?  [new]
MOXHATOE
Guest
Коллеги, необходима функция оценивающая похожесть двух строк.
Формально описть ее сложно, но думаю, что необходимо сравнивать две строки как два символьных массива и считать коэф. взаимной корреляции этих массивов.
Мне видится это как аналог экселевской функции =коррел(массив1;массив2).

То есть при входе ("корреляция" и "корреляция") на выходе должно быть 1,
при входе ("корреляция" и "корреляцию") на выходе должно быть где-то 0,95,
при входе ("корреляция" и "157ывф34") на выходе должно быть около 0,
а при входе ("корреляция" и "яицялеррок") на выходе должно быть -1.

Никто такими вещами не заморачивался?
А может уже и что-то подобное есть и я зря голову ломаю?
23 сен 05, 11:18    [1904410]     Ответить | Цитировать Сообщить модератору
 Re: Корреляция двух текстовых строк. Как сосчитать?  [new]
Stupindo
Member

Откуда:
Сообщений: 143
Я когда-то писал похожую штучку, правда на PL/SQL.
Задача состояла в поиске слов в тексте с учётом "похожести".
В результате получался коэффициент от 0 до 1.
Случаи, как у тебя, с -1 не обрабатывались, но насколько я помню.
В принципе всё работало более менее сносно и при том что усилий было потрачено не так много - простенько и эффективно.
23 сен 05, 12:16    [1904771]     Ответить | Цитировать Сообщить модератору
 Re: Корреляция двух текстовых строк. Как сосчитать?  [new]
Taffy
Member

Откуда:
Сообщений: 20501
Ага, тебе ответишь, а ты обсмеешь...
Хотя, если слова недлинные, то делается функция. Оба слова преобразуется в таблицы - id (номер позиции в слове), буква.
Потом связываем по id и букве. Количество строк в полученной делим на сумму количества букв в заданных / 2 . Получаем коэффициент.
23 сен 05, 12:30    [1904852]     Ответить | Цитировать Сообщить модератору
 Re: Корреляция двух текстовых строк. Как сосчитать?  [new]
Bug69
Member

Откуда: Москва, Чертаново
Сообщений: 229
Попробуй посмотреть в сторону шинглов
23 сен 05, 12:36    [1904896]     Ответить | Цитировать Сообщить модератору
 Re: Корреляция двух текстовых строк. Как сосчитать?  [new]
MOXHATOE
Guest
Taffy
Ага, тебе ответишь, а ты обсмеешь...

Ну вот, кажется я попал в черный список :)
Теперь век не забудут :)

Taffy
Оба слова преобразуется в таблицы...

Идея очень хорошая... Главное - просто реализовать...
Попробую и прогоню по реальной базе...
О результатах сообщу!

Спасибо, Taffy!

Bug69
Попробуй посмотреть в сторону шинглов

Шо цэ таке???
Первый раз слышу!
Можно поподробнее?
23 сен 05, 12:45    [1904960]     Ответить | Цитировать Сообщить модератору
 Re: Корреляция двух текстовых строк. Как сосчитать?  [new]
msdatabaseru
Guest
не корелляция, не вычисление схожести
но получение критерия для сортировки по похожести для слова / фразы

конечно делалось с вполне конкретной целью избежать дубликатов при вводе новых позиций в справочники, и, возможно, не совсем то что вам нужно:

http://www.msdatabase.ru/index.php?programs.htm
23 сен 05, 15:48    [1906025]     Ответить | Цитировать Сообщить модератору
 Re: Корреляция двух текстовых строк. Как сосчитать?  [new]
aleks2
Guest
CREATE FUNCTION "CorrelationOfTwoStrings"(@s1 nvarchar(4000), @s2 nvarchar(4000))
RETURNS float
AS
BEGIN
declare @l int
set @l=LEN(@s1)
if @l>LEN(@s2) set @l=LEN(@s2)

declare @i int, @m1 bigint, @m2 bigint, @m12  bigint,  @m11 bigint, @m22  bigint
declare @c1 smallint, @c2 smallint


set @i=@l
select  @m1=0, @m2=0, @m12=0,  @m11=0,  @m22=0

while @i>0 begin
   select  @c1=cast(SUBSTRING(@s1,@i,1) as smallint), @c2=cast(SUBSTRING(@s2,@i,1) as smallint)
   select  @m1=@m1+@c1, @m2=@m2+@c2, @m12=@m12+@c1*@c2,  @m11=@m11+@c1*@c1,  @m22=@m22+@c2*@c2
   set @i=@i-1
end

select  @m1=cast(@m1 as float)/@l, @m2=cast(@m2 as float)/@l, @m12=cast(@m12 as float)/@l,  @m11=cast(@m11 as float)/@l,  @m22=cast(@m22 as float)/@l


RETURN (@m12-@m1*@m2)/SQRT ((@m11-@m1*@m1)*(@m22-@m2*@m2))
END

Насчет declare @m1 bigint я не уверен, возможно и int сойдет.
23 сен 05, 16:05    [1906110]     Ответить | Цитировать Сообщить модератору
 Re: Корреляция двух текстовых строк. Как сосчитать?  [new]
aleks2
Guest
поправка

declare @i int, @m1 bigint, @m2 bigint, @m12  bigint,  @m11 bigint, @m22  bigint

следует читать

declare @i int, @m1 float, ...
23 сен 05, 16:08    [1906129]     Ответить | Цитировать Сообщить модератору
 Re: Корреляция двух текстовых строк. Как сосчитать?  [new]
Bug69
Member

Откуда: Москва, Чертаново
Сообщений: 229
MOXHATOE
Taffy
Ага, тебе ответишь, а ты обсмеешь...

Ну вот, кажется я попал в черный список :)
Теперь век не забудут :)

Taffy
Оба слова преобразуется в таблицы...

Идея очень хорошая... Главное - просто реализовать...
Попробую и прогоню по реальной базе...
О результатах сообщу!

Спасибо, Taffy!

Bug69
Попробуй посмотреть в сторону шинглов

Шо цэ таке???
Первый раз слышу!
Можно поподробнее?

Долго объяснять. попробуй поискать в Гугле. В общем, то, что предлагает Taffy, является сильно упрощенным частным случаем шинглов. Однако это вполне пригодно для сравнения небольшого числа коротких слов. Если надо искать похожие поля text(ntext) в таблице с числом записей > 1000000, то придется изучать более быстрые алгоритмы.
23 сен 05, 16:14    [1906167]     Ответить | Цитировать Сообщить модератору
 Re: Корреляция двух текстовых строк. Как сосчитать?  [new]
Амимопроходил
Guest
алгоритм конечно несовершенный но похожие слова выделяет

alter function dbo.str_like(@str1 varchar(128), @str2 varchar(128), @match_case bit ) RETURNS float as
begin
declare @sa varchar(128), @sb varchar(128)
declare @ta table (token varchar(128) COLLATE Cyrillic_General_BIN ) 
declare @tb table (token varchar(128) COLLATE Cyrillic_General_BIN)
declare @la int, @lb int, @mt float, @i int, @ia int, @ib int, @na int, @nb int
 
select @sa = case @match_case when 1 then @str1 else UPPER(@str1) end, 
		 @sb = case @match_case when 1 then @str2 else UPPER(@str2) end

if @sa = reverse(@sb) return -1
--максимальное  количество токенов
select  @lb = len(@sb),  @la = len(@sa)
select @ib = @lb , @ia =@la

set @mt = (len(@sa)*(len(@sa)+1))/2+(len(@sb)*(len(@sb)+1))/2

while @ia >0
	begin
	set @i =1 
	while @i <= @la-@ia+1
		begin
		insert into @ta(token) values(substring(@sa,@i,@ia))
     	set @i = @i+1
		end 	
	set @ia = @ia-1
	end

while @ib >0
	begin
	set @i =1 
	while @i <= @lb-@ib+1
		begin
		insert into @tb(token) values(substring(@sb,@i,@ib))
     	set @i = @i+1
		end 	
	set @ib = @ib-1
	end



select @na = count(*) from @ta where charindex(token,@sb, 1) > 0 

select @nb = count(*) from @tb where charindex(token,@sa, 1) > 0

select @mt = sqrt((@na+@nb)/@mt)
return @mt
end

select  dbo.str_like ('корреляция' ,'корреляция',0) as correlation
union all
select  dbo.str_like ('корреляция' ,'корреляцию',0)
union all
select  dbo.str_like ('корреляция' ,'157ывф34',0)
union all
select  dbo.str_like ('корреляция' ,'яицялеррок',0)


Value
1.0
0.90954534096587358
0.0
-1.0
23 сен 05, 16:21    [1906203]     Ответить | Цитировать Сообщить модератору
 Re: Корреляция двух текстовых строк. Как сосчитать?  [new]
MOXHATOE
Guest
Повозился с алгоритмами...
Вывод: учитывать по позиции символов нет смысла, т.к. при этом строки например "вася" и " вася" будут считаться абсолютно разными из-за того, что лидирующий пробел смещает все символы на один.
В итоге отказался от такого метода и решил просто сравнивать вхождение символов одной строки в другую.
Для моей задачи (а надо было оценить наличие дублей в БД с учетом ошибок при записи) метод подошел как нельзя лучше.

Текст функции:
CREATE FUNCTION dbo.strCor(
	@str1 nvarchar(4000)
,	@str2 nvarchar(4000)
)
RETURNS real
BEGIN
declare @i int
declare @cor real
declare @str3 nvarchar(4000)
if len(@str1) < len(@str2) begin
	set @str3 = @str2
	set @str2 = @str1
	set @str1 = @str3
end
set @cor = 0
set @i = 1
while @i <= len(@str2) begin
	if charindex(substring(@str2, @i, 1), @str1, 1) > 0 set @cor = @cor + 1 
	set @i = @i + 1
end
RETURN @cor * 2 / (len(@str1) + len(@str2))
END

На выходе имеем число от 0 до 1 оценивающее схожесть набора букв в двух словах.
Пример использования:
create table #t (name nvarchar(1000))
insert #t values('ЗАО Инфотел')
insert #t values('Инфотелл, ЗАО')
insert #t values('Инфотелл ЗАО')
insert #t values('ШОКОЛАД (ООО)')
insert #t values('ШОКОЛАД, ООО')
insert #t values('альфа софт')
insert #t values('оо балтавто логистика')
insert #t values('энергопром')
--select * from #t
select *, dbo.strCor(a.name, b.name) from #t a, #t b
where dbo.strCor(a.name, b.name) > 0.8
and a.name <> b.name
На выходе получим пары названий с коэф. схожести более 0,8, как показала практика работает это достаточно точно:
Инфотелл, ЗАО	ЗАО Инфотел	0.91666669
Инфотелл ЗАО	ЗАО Инфотел	0.95652175
ЗАО Инфотел	Инфотелл, ЗАО	0.91666669
Инфотелл ЗАО	Инфотелл, ЗАО	0.95999998
ЗАО Инфотел	Инфотелл ЗАО	0.95652175
Инфотелл, ЗАО	Инфотелл ЗАО	0.95999998
ШОКОЛАД, ООО	ШОКОЛАД (ООО)	0.88
ШОКОЛАД (ООО)	ШОКОЛАД, ООО	0.88

Особенность данного алгоритма: чем длиннее исходные строки, тем выше точность.
Есть дыры (некогда было думать, сделал по-быстрому), например при использовании искуственных конструкции вида:
select dbo.strCor('вася', 'аааа')
select dbo.strCor('вася', 'сява')
получим однозначное совпадение - рузультат 1.0 - из-за того, что все буквы второго слова являются подмножеством букв первого слова ,а длина строк совпадает.

Будет время переделаю чтобы все было корректно с точки зрения математики, и считалась действительно корреляцию двух массивов, но пока и так нормально справляется...
23 сен 05, 17:22    [1906463]     Ответить | Цитировать Сообщить модератору
 Re: Корреляция двух текстовых строк. Как сосчитать?  [new]
*alex++
Member

Откуда:
Сообщений: 80
MOXHATOE

Текст функции:
CREATE FUNCTION dbo.strCor(
	@str1 nvarchar(4000)
,	@str2 nvarchar(4000)
)
RETURNS real
BEGIN
declare @i int
declare @cor real
declare @str3 nvarchar(4000)
if len(@str1) < len(@str2) begin
	set @str3 = @str2
	set @str2 = @str1
	set @str1 = @str3
end
set @cor = 0
set @i = 1
while @i <= len(@str2) begin
	if charindex(substring(@str2, @i, 1), @str1, 1) > 0 set @cor = @cor + 1 
	set @i = @i + 1
end
RETURN @cor * 2 / (len(@str1) + len(@str2))
END




Попробовал эту функцию на своей базе :)
Одна фигня получилась
Сметанина Елена Александровна	Исполком Горсовета г.Дзержинск	0.98305082
Райгосадминистрация г.Первомайск	Петровский Кондитерский Дом ООО 	0.98412699
23 сен 05, 17:56    [1906614]     Ответить | Цитировать Сообщить модератору
 Re: Корреляция двух текстовых строк. Как сосчитать?  [new]
баззззлайтер
Guest
SELECT DIFFERENCE('smithers', 'smothers')

а русские слова в транслит переводить - функцию напишите
28 сен 05, 00:11    [1916173]     Ответить | Цитировать Сообщить модератору
 Re: Корреляция двух текстовых строк. Как сосчитать?  [new]
LexusR
Member

Откуда: Novosibirsk
Сообщений: 1887
MetaPhoneRu
28 сен 05, 06:03    [1916363]     Ответить | Цитировать Сообщить модератору
 Re: Корреляция двух текстовых строк. Как сосчитать?  [new]
OVEL28
Member

Откуда: г. Обнинск
Сообщений: 20
Попробуйте ссылочку:
http://delphi.mtu-net.ru/zip/compare.zip
и мыльте (в профиле есть) - отправлю файля для sql:
fuzzycomparestring.rar (14 128) - не могу "пришпилить"

Мне помогло, но тормоза...
28 сен 05, 21:16    [1920417]     Ответить | Цитировать Сообщить модератору
 Re: Корреляция двух текстовых строк. Как сосчитать?  [new]
Lepsik
Member

Откуда: glubinka
Сообщений: 4256
MOXHATOE
Коллеги, необходима функция оценивающая похожесть двух строк.


https://www.sql.ru/forum/actualthread.aspx?bid=1&tid=88787&pg=-1&hl=md5
29 сен 05, 01:15    [1920685]     Ответить | Цитировать Сообщить модератору
Между сообщениями интервал более 1 года.
 Re: Корреляция двух текстовых строк. Как сосчитать?  [new]
dvvarna
Member

Откуда: Белгород -> Москва
Сообщений: 50
Тема хоть и старая, но.
Предложу вариант псевдошинглов, для коротких текстов без получения хешей и без идеальной канонизации

Делал для ASE
DECLARE @str1 varchar(255), 
        @str2 varchar(255),
        @str1a varchar(255), 
        @str2a varchar(255),
        @str1a2a varchar(255),
        @shingl_size integer,
        @shingl_step integer,
        @l1a integer,
        @l2a integer,
        @l1a2a integer,
        @i integer,    
        @n1 integer,
        @n2 integer
        
SELECT @str1 = 'Офтальмологическая когерентная томография зрительного нерва с применением аппарата "OPTOVUE"',
       @str2 = 'Офтальмологическая когерентная томография сетчатки глаза с применением аппарата "OPTOVUE"',
       @shingl_size = 3,
       @shingl_step = 1

       
--  канонизация текста

SELECT @str1a = str_replace(lower(@str1), " в ", NULL),
       @str2a = str_replace(lower(@str2), " в ", NULL) 
SELECT @str1a = str_replace(@str1a, " и ", NULL),
       @str2a = str_replace(@str2a, " и ", NULL) 
SELECT @str1a = str_replace(@str1a, " на ", NULL),
       @str2a = str_replace(@str2a, " на ", NULL) 
SELECT @str1a = str_replace(@str1a, " по ", NULL),
       @str2a = str_replace(@str2a, " по ", NULL) 
SELECT @str1a = str_replace(@str1a, " для ", NULL),
       @str2a = str_replace(@str2a, " для ", NULL)
SELECT @str1a = str_replace(@str1a, " или ", NULL),
       @str2a = str_replace(@str2a, " или ", NULL)
SELECT @str1a = str_replace(@str1a, " как ", NULL),
       @str2a = str_replace(@str2a, " как ", NULL) 
SELECT @str1a = str_replace(@str1a, " а ", NULL),
       @str2a = str_replace(@str2a, " а ", NULL) 
SELECT @str1a = str_replace(@str1a, " к ", NULL),
       @str2a = str_replace(@str2a, " к ", NULL) 
SELECT @str1a = str_replace(@str1a, " в ", NULL),
       @str2a = str_replace(@str2a, " в ", NULL) 
SELECT @str1a = str_replace(@str1a, " до ", NULL),
       @str2a = str_replace(@str2a, " до ", NULL) 
SELECT @str1a = str_replace(@str1a, " с ", NULL),
       @str2a = str_replace(@str2a, " с ", NULL) 
SELECT @str1a = str_replace(@str1a, " у ", NULL),
       @str2a = str_replace(@str2a, " у ", NULL) 
SELECT @str1a = str_replace(@str1a, " к ", NULL),
       @str2a = str_replace(@str2a, " к ", NULL) 
       

SELECT @str1a = str_replace(@str1a, " ", NULL),
       @str2a = str_replace(@str2a, " ", NULL) 

SELECT @str1a = str_replace(@str1a, ".", NULL),
       @str2a = str_replace(@str2a, ".", NULL) 
SELECT @str1a = str_replace(@str1a, ",", NULL),
       @str2a = str_replace(@str2a, ",", NULL) 
SELECT @str1a = str_replace(@str1a, ":", NULL),
       @str2a = str_replace(@str2a, ":", NULL) 
SELECT @str1a = str_replace(@str1a, ";", NULL),
       @str2a = str_replace(@str2a, ";", NULL) 
SELECT @str1a = str_replace(@str1a, "!", NULL),
       @str2a = str_replace(@str2a, "!", NULL) 
SELECT @str1a = str_replace(@str1a, "?", NULL),
       @str2a = str_replace(@str2a, "?", NULL) 

SELECT @str1a = str_replace(@str1a, "ё", 'е'),
       @str2a = str_replace(@str2a, "ё", 'е') 
       
SELECT @l1a = len(@str1a),
       @l2a = len(@str2a)
       
-- Добавим в конец текстов символы из начала текста для того что бы шингл всегда был полноразмерным      
SELECT @str1a = @str1a + Left(@str1a, @shingl_size - 1 ),
       @str2a = @str2a + Left(@str2a, @shingl_size - 1 )


IF @l1a > @l2a
   -- Делаем второй элемент больше первого 
   BEGIN
    SELECT @str1a2a = @str2a, @l1a2a = @l2a 
    SELECT @str2a = @str1a, @l2a = @l1a  
    SELECT @str1a = @str1a2a, @l1a = @l1a2a    
   END

 
CREATE TABLE #ts_1 (shingl varchar(255) NULL)   
CREATE TABLE #ts_2 (shingl varchar(255) NULL)
 
SELECT @i = 1  
WHILE @i <= @l1a
    -- заполняем шинглы первой строки
    BEGIN
    
        INSERT INTO #ts_1 (shingl)
        SELECT substring(@str1a, @i, @shingl_size)
        
        
        SELECT @i = @i + @shingl_step
    END


SELECT @i = 1  
WHILE @i <= @l2a
    -- заполняем штнглы второй строки
    BEGIN
    
        INSERT INTO #ts_2 (shingl)
        SELECT substring(@str2a, @i, @shingl_size)
        
        
        SELECT @i = @i + @shingl_step
    END




-- Считаем кол-во одинаковых шинглов из первой строки, которые повторяются во второй
SELECT @n1 = COUNT(#ts_1.shingl) 
FROM #ts_1
WHERE exists (SELECT 1 FROM #ts_2 WHERE #ts_2.shingl = #ts_1.shingl)


-- Считаем кол-во одинаковых шинглов из второй строки, которые повторяются в первой
SELECT @n2 = COUNT(#ts_2.shingl) 
FROM #ts_2
WHERE exists (SELECT 1 FROM #ts_1 WHERE #ts_1.shingl = #ts_2.shingl)

SELECT @str1,
       @str2,
       CAST((@n1 + @n2) as float)/CAST((@l1a + @l2a) as float)  

       
--SELECT * FROM #ts_1
--SELECT * FROM #ts_2
       
DROP TABLE #ts_1
DROP TABLE #ts_2
19 дек 16, 09:54    [20020077]     Ответить | Цитировать Сообщить модератору
 Re: Корреляция двух текстовых строк. Как сосчитать?  [new]
aleks2
Guest
О якая древность то...

Упрощенная функция, считающая
(среднюю длину точно совпадающих последовательностей двух строк @s1, @s2) / (максимальная длина строки).
@minLen - минимальная учитываемая длина совпадения.

ALTER FUNCTION "SimilarityOfTwoStrings"(@s1 nvarchar(4000), @s2 nvarchar(4000), @minLen int = 2 )
RETURNS float
AS
begin

  declare @c1 As Table( n int, c nchar(1) );
  declare @c2 As Table( n int, c nchar(1) );
  declare @x float;

  -- Две исходные таблицы предложений
  insert @c1 select n, substring( @s1, n, 1 ) from dbo.N where n between 1  and len(@s1);
  insert @c2 select n, substring( @s2, n, 1 ) from dbo.N where n between 1  and len(@s2);

  -- это для осознания тривиальности
  with x as ( select c1.c, id = c1.n - c2.n, c1.n from @c1 as c1 inner join @c2 as c2 on c1.c = c2.c )
     , y as ( select id, cnt = count(*) from x group by id having count(*) > iif( @minLen >= 2, @minLen, 2 ) )
     , z as ( select l = max(l) from ( values (len(@s1)), (len(@s2)) ) as z(l) )
     select @x = avg(cnt)/cast( ( select l from z ) as float) from y;
  
  return isnull( @x, 0);

end; 
19 дек 16, 13:40    [20021635]     Ответить | Цитировать Сообщить модератору
Все форумы / Microsoft SQL Server Ответить