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

Откуда:
Сообщений: 1148
Есть таблица личных данных после ручного ввода: Фио и адрес (необязатеьно российский)

Некая функция часто обращается к таблице и просит найти дубликаты для некой персоны.
В том числе те, которые имеют отличия в написании.
И желательно быстро.

По этой причине использование Дамерау-Левенштайна, по крайней мере в лоб, видится проблематично.

Есть ли оправдавшие себя подходы к проблеме или советы?
13 янв 21, 12:20    [22262553]     Ответить | Цитировать Сообщить модератору
 Re: Нечёткий поиск  [new]
env
Member

Откуда: Россия, Москва
Сообщений: 6977
Alexander Us
и просит найти дубликаты для некой персоны

Функция тоже получает значение из ручного ввода или оперирует одним из значений этой таблицы?
13 янв 21, 12:52    [22262575]     Ответить | Цитировать Сообщить модератору
 Re: Нечёткий поиск  [new]
ptr128
Member

Откуда: Moscow
Сообщений: 865
Alexander Us,

а если использовать хеширование по сигнатуре?
13 янв 21, 13:21    [22262600]     Ответить | Цитировать Сообщить модератору
 Re: Нечёткий поиск  [new]
Alexander Us
Member

Откуда:
Сообщений: 1148
env
Функция тоже получает значение из ручного ввода или оперирует одним из значений этой таблицы?

Могут быть оба варианта.
13 янв 21, 13:35    [22262609]     Ответить | Цитировать Сообщить модератору
 Re: Нечёткий поиск  [new]
Alexander Us
Member

Откуда:
Сообщений: 1148
ptr128
а если использовать хеширование по сигнатуре?

Извините, что не понял Вашу идею.
Могли бы Вы чуть подробнее объяснить?
13 янв 21, 13:49    [22262626]     Ответить | Цитировать Сообщить модератору
 Re: Нечёткий поиск  [new]
invm
Member

Откуда: Москва
Сообщений: 9587
Alexander Us,

Какая-нибудь внешняя поисковая система с возможностью нечеткого поиска (например Elastic Search) плюс интеграция с ней через SQL CLR
13 янв 21, 14:12    [22262642]     Ответить | Цитировать Сообщить модератору
 Re: Нечёткий поиск  [new]
Alexander Us
Member

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

Спасибо, попробую.
А эта штука платная?
13 янв 21, 14:18    [22262647]     Ответить | Цитировать Сообщить модератору
 Re: Нечёткий поиск  [new]
felix_ff
Member

Откуда: Moscow
Сообщений: 1636
Alexander Us,

погуглите. ES распостраняется по лицензии apache. можно свитать что бесплатно
13 янв 21, 14:19    [22262648]     Ответить | Цитировать Сообщить модератору
 Re: Нечёткий поиск  [new]
Владислав Колосов
Member

Откуда:
Сообщений: 8165
Alexander Us,

SSIS имеет средство нечеткого сравнения. Данные можно периодически обрабатывать таким образом с формированием "отсева".
13 янв 21, 14:44    [22262667]     Ответить | Цитировать Сообщить модератору
 Re: Нечёткий поиск  [new]
Alexander Us
Member

Откуда:
Сообщений: 1148
Владислав Колосов,

Тогда придётся вызывать исполнение SSIS пакета по каждому запросу на поиск.
Ведь данные в таблице могут обновляться: идут вставки, иногда удаления.
Мне кажется, это не совсем то, что я бы хотел.
13 янв 21, 15:17    [22262713]     Ответить | Цитировать Сообщить модератору
 Re: Нечёткий поиск  [new]
aleks222
Member

Откуда:
Сообщений: 1169
Alexander Us
И желательно быстро.

По этой причине использование Дамерау-Левенштайна, по крайней мере в лоб, видится проблематично.

Есть ли оправдавшие себя подходы к проблеме или советы?


invm
Alexander Us,
Какая-нибудь внешняя поисковая система с возможностью нечеткого поиска (например Elastic Search) плюс интеграция с ней через SQL CLR


А чо, внешняя система способна быстро искать в какой-то базе, без передачи данных в эту систему?
13 янв 21, 15:20    [22262715]     Ответить | Цитировать Сообщить модератору
 Re: Нечёткий поиск  [new]
invm
Member

Откуда: Москва
Сообщений: 9587
aleks222
А чо, внешняя система способна быстро искать в какой-то базе, без передачи данных в эту систему?
Не задавай глупых вопросов :)
Само-собой, данные придется туда передавать.
13 янв 21, 15:36    [22262732]     Ответить | Цитировать Сообщить модератору
 Re: Нечёткий поиск  [new]
invm
Member

Откуда: Москва
Сообщений: 9587
Alexander Us,

Можете поиграться со штатным FTS и containstable с запросом ISABOUT.
Примерно так
+
use master;
create database TestDB;
alter database TestDB set recovery simple;
go

use TestDB;
set ansi_nulls, quoted_identifier, xact_abort on;
go

create table dbo.t
(
 id int identity constraint PK_t primary key,
 s varchar(8000) not null
);

insert into dbo.t
 (s)
 values
  ('Иванов Петр Васильевич, Москва, ул. Пряничная, д. 7'),
  ('Иванов Петр Васильевич, Моска, Пряничная - 7'),
  ('Москва, ул. Пряничная, д. 7, Иванов Петр Васильевич'),
  ('Иванов П. В., Москва, Пряничная, 7'),
  ('Иванов Петр Васильевич, Москва, ул. Пряничная, д. 7'),
  ('Петр Васильевич Иванов, Москва, ул. Пряничная, д. 7'),
  ('Гришин Петр Александрович, Ижевск, ул. Пряничная, д. 19'),
  ('Иванов Пётр Восильевич, Москва, Пряничная - 7');
go

create fulltext catalog Test;
go

create fulltext index on dbo.t (s language 0) key index PK_t on Test with (stoplist = off, change_tracking = auto);
go

alter fulltext index on dbo.t start full population;
go

while fulltextcatalogproperty('Test', 'PopulateStatus') <> 0
 waitfor delay '00:00:01';
go

declare @s varchar(8000) = 'ISABOUT(Иванов, Петр, Васильевич, Москва, ул., Пряничная, д., 7)';

select
 b.*, a.[RANK]
from
 containstable(dbo.t, s, @s, language 0, 10) a join
 dbo.t b on b.id = a.[KEY]
order by
 a.[RANK] desc
go

use master;
alter database TestDB set single_user with rollback immediate;
drop database TestDB;
go
13 янв 21, 15:42    [22262738]     Ответить | Цитировать Сообщить модератору
 Re: Нечёткий поиск  [new]
Alexander Us
Member

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

Спасибо, обязательно попробую.
13 янв 21, 15:50    [22262747]     Ответить | Цитировать Сообщить модератору
 Re: Нечёткий поиск  [new]
ptr128
Member

Откуда: Moscow
Сообщений: 865
Alexander Us
Могли бы Вы чуть подробнее объяснить?

Я про это
13 янв 21, 15:57    [22262758]     Ответить | Цитировать Сообщить модератору
 Re: Нечёткий поиск  [new]
Alexander Us
Member

Откуда:
Сообщений: 1148
ptr128
Alexander Us
Могли бы Вы чуть подробнее объяснить?

Я про это


Спасибо за ссылку.
Сейчас нет времени всё обстоятельно прочитать, но такую или похожую штуку я уже делал для ускорения поиска Дамерау-Левенштайном в отдельном приложении: если сформировать битовый хэш для двух строк, и, два хэша отличаются, скажем на 4 бита, то можно сказать, что две строки отличаются как минимум на 4 символа.
Так можно не сравнивать Дамерау-Левенштайном строки, которые имеют слишком много отличий.

Это хорошо (приемлимо) работает в отдельном приложении, но мне сейчвс надо SQL.
13 янв 21, 16:40    [22262786]     Ответить | Цитировать Сообщить модератору
 Re: Нечёткий поиск  [new]
ptr128
Member

Откуда: Moscow
Сообщений: 865
Alexander Us,

Количество хешей может быть существенно меньшим, чем количество слов, да и сравнивать хеши намного быстрее. Сканирование отдельной таблицы хешей позволит на первом этапе существенно ограничить список строк из основной таблиц, по которым уже производится сравнение Дамерау-Левенштайном.
13 янв 21, 16:53    [22262799]     Ответить | Цитировать Сообщить модератору
 Re: Нечёткий поиск  [new]
Alexander Us
Member

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

да, конечно, это я уже реализовал в приложении.
Но этот способ, как мне кажется, не очень хорошо подходит для SQL сервера.
13 янв 21, 17:12    [22262815]     Ответить | Цитировать Сообщить модератору
 Re: Нечёткий поиск  [new]
Ролг Хупин
Member

Откуда: Чебаркуль
Сообщений: 3870
Alexander Us
ptr128
пропущено...

Я про это


Спасибо за ссылку.
Сейчас нет времени всё обстоятельно прочитать, но такую или похожую штуку я уже делал для ускорения поиска Дамерау-Левенштайном в отдельном приложении: если сформировать битовый хэш для двух строк, и, два хэша отличаются, скажем на 4 бита, то можно сказать, что две строки отличаются как минимум на 4 символа.
Так можно не сравнивать Дамерау-Левенштайном строки, которые имеют слишком много отличий.

Это хорошо (приемлимо) работает в отдельном приложении, но мне сейчвс надо SQL.



По-моему расстояние Левентшайна означает количество преобразований исходной строки в целевую, это к слову.

Можно ничего не делать, а взять SOUNDEX ( character_expression )

Если делать, то в ы можете взять алгоритм Питера Норвига, простейший прообраз гугловского "Did you mean"
https://norvig.com/spell-correct.html

Там в конце есть список языков, на которых реализован поиск.
Можно дописать на SQL, но я делал SQL CLR функцию+таблицу с английскими словами.

Сообщение было отредактировано: 13 янв 21, 17:15
13 янв 21, 17:19    [22262820]     Ответить | Цитировать Сообщить модератору
 Re: Нечёткий поиск  [new]
Alexander Us
Member

Откуда:
Сообщений: 1148
Ролг Хупин,

Спасибо за ссылку. Интересно.
13 янв 21, 17:35    [22262829]     Ответить | Цитировать Сообщить модератору
 Re: Нечёткий поиск  [new]
Владислав Колосов
Member

Откуда:
Сообщений: 8165
Alexander Us,

а зачем это делать на лету? Вопросы приведения базы в порядок можно решать при регулярном обслуживании. Стремление выполнять какие-то преобразования синхронно со вставкой не всегда оправданы.
13 янв 21, 19:03    [22262871]     Ответить | Цитировать Сообщить модератору
 Re: Нечёткий поиск  [new]
Alexander Us
Member

Откуда:
Сообщений: 1148
Владислав Колосов,

Да, но не в этом случае.
Скажем, в таблицу вносятся персоны, и тут же приходит запрос на определение дубликатов.
Было бы нежелательно заставлять пользователя ждать, пока исполнится пакет и приведет всё "в порядок".
К тому же, задача по нечёткой группировке списков уже решена в отдельном приложении (0,5 млн группируются ~за 5 мин).
В данном случае нужен поиск дубликатов "на лету".
14 янв 21, 11:28    [22263117]     Ответить | Цитировать Сообщить модератору
 Re: Нечёткий поиск  [new]
Владислав Колосов
Member

Откуда:
Сообщений: 8165
Alexander Us,

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