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

Откуда:
Сообщений: 25
Здравствуйте,помогите пожалуйста советом!Необходимо сравнить две таблицы и найти в них совпадения включая опечатки.
Фамилии, которые нужно сравнить находятся в таблице zags(количество записей 1600).
Фамилии с которыми нужно сравнить находятся в таблице WM_PERSONAL_CARD (количество записей более 120000).
Функция uf_distance была найдена на данном форуме, далее к ней был дописан курсор для поиска совпадений.
Быстродействие данного курсора катастрофически мала,на поиски одного человека уходит 2 минуты.
Помогите люди добрые как оптимизировать данный алгоритм!)
Заранее спасибо!

--Функция расчета кол-ва несовпадения символов
CREATE FUNCTION [dbo].[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

--- Процедура сравнения

delete from KNN_KONTR_SIMWOL_ZAGS		-- таблица результатов
declare @nOuid	int,
		@nOuid1	int,
		@sFio	varchar(100),
		@sFio1	varchar(100),
		@sDtr	varchar(10),
		@sDtr1	varchar(10),
		@nKolSimw	int,
		@sStr1	varchar(255),
		@sStr2	varchar(255)
-- Идентификатор табл., ФИ, Дата рожд.		
select OUID_Z,rtrim(Family)+' '+rtrim(Name)+' '+convert(varchar(10),datr,104)   from zags  -- Список ЛД, которые надо сравнить (1600 чел)
where datr is not null
order by OUID_Z

OPEN curSpisLD1
FETCH NEXT FROM curSpisLD1  INTO @nOuid, @sStr1

WHILE @@fetch_status = 0 
BEGIN

DECLARE curSpisLD  INSENSITIVE CURSOR FOR

-- Идентификатор табл., ФИ, Дата рожд.		
SELECT WM_PERSONAL_CARD.ouid ,
rtrim(SPR_FIO_SURNAME.A_NAME)+' '+rtrim(SPR_FIO_NAME.A_NAME)+' '+convert(varchar(10),WM_PERSONAL_CARD.BIRTHDATE,104) -- Дата рождения
 from WM_PERSONAL_CARD  -- Список ЛД с которыми надо сравнить т(120000 чел.)
INNER JOIN SPR_FIO_SURNAME ON WM_PERSONAL_CARD.SURNAME= SPR_FIO_SURNAME.OUID -- фамилия
INNER JOIN SPR_FIO_NAME ON SPR_FIO_NAME.OUID = WM_PERSONAL_CARD.A_NAME   -- имя
where isnull(WM_PERSONAL_CARD.a_status,0) in (0,10)
and WM_PERSONAL_CARD.a_pcstatus=1
order by 2


OPEN curSpisLD
FETCH NEXT FROM curSpisLD  INTO @nOuid1, @sFio1

WHILE @@fetch_status = 0 
BEGIN

select @nKolSimw =dbo.uf_distance(@sStr1, @sFio1) -- кол-во несовпадающих символов

if @nKolSimw <5
insert into KNN_KONTR_SIMWOL_ZAGS (OUID_Z, OUID_LD, KOL_SIMW)
select @nOuid, @nOuid1, @nKolSimw

FETCH NEXT FROM curSpisLD  INTO @nOuid1, @sFio1

END
CLOSE  curSpisLD
DEALLOCATE curSpisLD

FETCH NEXT FROM curSpisLD1  INTO @nOuid, @sStr1
END
CLOSE  curSpisLD1
DEALLOCATE curSpisLD1
21 янв 13, 08:33    [13800462]     Ответить | Цитировать Сообщить модератору
 Re: Оптимизация алгоритма поиска Левенштейна  [new]
aleks2
Guest
Учись пользоваться поиском
https://www.sql.ru/forum/actualthread.aspx?tid=909855&hl=%f0%e0%f1%f1%f2%ee%ff%ed%e8%e5
21 янв 13, 08:43    [13800488]     Ответить | Цитировать Сообщить модератору
 Re: Оптимизация алгоритма поиска Левенштейна  [new]
Bahha_Omsk
Member

Откуда:
Сообщений: 25
Читал!Поиском пользоваться умею!aleks2,
21 янв 13, 08:47    [13800495]     Ответить | Цитировать Сообщить модератору
 Re: Оптимизация алгоритма поиска Левенштейна  [new]
aleks2
Guest
Bahha_Omsk
Читал!Поиском пользоваться умею!aleks2,

Сумневаюсь. Глядя на ваши WHILE не в жисть не поверю...
21 янв 13, 09:20    [13800577]     Ответить | Цитировать Сообщить модератору
 Re: Оптимизация алгоритма поиска Левенштейна  [new]
MasterZiv
Member

Откуда: Питер
Сообщений: 34705
Bahha_Omsk,

Как бы сравнивать видимо нужно каждую с каждой, это 1600 × 1200000, не сравниш до конца жизни.

Надо индексы применять хотябы для отсечения заведомо неподходящих записей.
21 янв 13, 11:36    [13801546]     Ответить | Цитировать Сообщить модератору
 Re: Оптимизация алгоритма поиска Левенштейна  [new]
MasterZiv
Member

Откуда: Питер
Сообщений: 34705
OPEN curSpisLD

Где курсор-то?
21 янв 13, 11:39    [13801586]     Ответить | Цитировать Сообщить модератору
 Re: Оптимизация алгоритма поиска Левенштейна  [new]
Гость333
Member

Откуда:
Сообщений: 3683
MasterZiv
OPEN curSpisLD

Где курсор-то?

Да тут он, парой строчек выше:

DECLARE curSpisLD  INSENSITIVE CURSOR FOR

-- Идентификатор табл., ФИ, Дата рожд.		
SELECT WM_PERSONAL_CARD.ouid ,
...
21 янв 13, 12:00    [13801812]     Ответить | Цитировать Сообщить модератору
 Re: Оптимизация алгоритма поиска Левенштейна  [new]
Bahha_Omsk
Member

Откуда:
Сообщений: 25
MasterZiv
Bahha_Omsk,

Как бы сравнивать видимо нужно каждую с каждой, это 1600 × 1200000, не сравниш до конца жизни.

Надо индексы применять хотябы для отсечения заведомо неподходящих записей.


По какому принципу отсеять заведомо не подходящие записи?
21 янв 13, 13:30    [13802658]     Ответить | Цитировать Сообщить модератору
 Re: Оптимизация алгоритма поиска Левенштейна  [new]
DenMak
Member

Откуда:
Сообщений: 53
Можно отсеивать записи в наборе, по длине строки например, исключать из сравнения строки в которых длины фамилий отличаются на заданную величину ( например в два раза).
Можно добавить еще ряд правил при которых будет исключаться собственно расчет расстояния (т.е. такие записи либо совпадают 100 % либо отличаются по некоторым параметрам настолько, что расчет расстояния заведомо не имеет смыла). Дополнительно, имеет смысл реализовать функцию расчета расстояния на CLR.
Вообще можно попробовать обойтись без курсора, просто джойнить строки на основе значения расстояния которое возвращает функция (ну конечно с критерием пожостче ;-) . Наборы для сравнения лучше подготовить заранее (во временных табличках к примеру)
21 янв 13, 14:44    [13803279]     Ответить | Цитировать Сообщить модератору
 Re: Оптимизация алгоритма поиска Левенштейна  [new]
HandKot
Member

Откуда: Sergiev Posad
Сообщений: 3058
а вот это смотрели Нечеткое сравнение строк / fuzzy matching ?
по словам автора
Ares_ekb
Размер словаря ~ 160 000 записей. 10 наиболее похожих записей находятся за ~ 1 секунду.
21 янв 13, 14:59    [13803389]     Ответить | Цитировать Сообщить модератору
 Re: Оптимизация алгоритма поиска Левенштейна  [new]
MasterZiv
Member

Откуда: Питер
Сообщений: 34705
Bahha_Omsk
MasterZiv
Bahha_Omsk,

Как бы сравнивать видимо нужно каждую с каждой, это 1600 × 1200000, не сравниш до конца жизни.

Надо индексы применять хотябы для отсечения заведомо неподходящих записей.


По какому принципу отсеять заведомо не подходящие записи?


Я не знаю, это тебе решать.
21 янв 13, 15:19    [13803569]     Ответить | Цитировать Сообщить модератору
 Re: Оптимизация алгоритма поиска Левенштейна  [new]
MasterZiv
Member

Откуда: Питер
Сообщений: 34705
Как бы главное:
Пока ты не уйдёшь от почти 2-миллиардной размерности задачи тебе это делать в коде бесполезно.
21 янв 13, 15:27    [13803651]     Ответить | Цитировать Сообщить модератору
 Re: Оптимизация алгоритма поиска Левенштейна  [new]
Кот Матроскин
Member

Откуда: Москва
Сообщений: 8933
Bahha_Omsk,

можно сделать N проходов алгоритма
1 проход сравниваем только те фамилии, у которых совпали 1-е символы.
2 проход - сравниваем те фамилии, у которых первые символы не совпали, но совпали вторые.
...
N. сравниваем те, у которых не совпали первые N-1, но совпали N-e.


храня лидирующие N символов отдельно и строя индексы по ним

учитывая, что каждый проход будет быстрее в среднем раз в 15 (за счет того что проверяем только фамилии с конкретной буквой в позиции N), а потребуется вряд ли больше 3 проходов- выигрыш налицо.
21 янв 13, 16:07    [13804147]     Ответить | Цитировать Сообщить модератору
 Re: Оптимизация алгоритма поиска Левенштейна  [new]
MasterZiv
Member

Откуда: Питер
Сообщений: 34705
Кот Матроскин,

Только естественно надо иметь соответствующие индексы и их использовать.

Само такое разбиение сложность задачи никак не уменьшает.
21 янв 13, 18:42    [13805348]     Ответить | Цитировать Сообщить модератору
 Re: Оптимизация алгоритма поиска Левенштейна  [new]
Владимир Затуливетер
Member

Откуда:
Сообщений: 427
Bahha_Omsk
(количество записей 1600).
(количество записей более 120000).


Данных не очень много, CLR хорошо справиться с этой задачей и ничего городить не надо.
Поиск в 120 тыс. строк будет занимать пару секунд с учетом того что сканируемая таблица/индекс в памяти.
21 янв 13, 20:51    [13805724]     Ответить | Цитировать Сообщить модератору
 Re: Оптимизация алгоритма поиска Левенштейна  [new]
Кот Матроскин
Member

Откуда: Москва
Сообщений: 8933
MasterZiv,
Про индексы я упомянул
храня лидирующие N символов отдельно и строя индексы по ним
.

Но учитывая что у автора курсор - даже без индексов будет выигрыш, хоть и поменьше, просто за счет уменьшения числа вызовов функции.
21 янв 13, 22:32    [13806000]     Ответить | Цитировать Сообщить модератору
Все форумы / Microsoft SQL Server Ответить