@bearpaw

Какой алгоритм поиска дублей посоветуете Sql server?

Здравствуйте!
Есть некоторая таблица с наименованиями номенклатур . Около 70К записей.
Необходимо что бы каждая вновь вносимая номенклатура проверялась на уникальность.
Иногда сотрудники пишут вместо русской х (с) латинскую х (c).
Пробовали сходство Джаро — Винклера , расстояние Дамерау-Левенштейна (в виде функций на MS SQL Server). Это все работает и даже идеально работает. Кроме одного - время. Необходимо что бы на операцию уходило 10-20 секунд, а данные алгоритмы работаю от 2-3 минуты до 10-15. Причем время возрастает логарифмически в зависимости от длины нового слова, т.к. вычисляется параметр для каждой строки. Нормализация строки поиска (убираем пробелы, запяты, точки и т.п.) дает выигрыш 3-4 секунды.
Может кто-то знает или видел быстрые алгоритмы поиска сходства? Например на основе NGram, или использовании хэшей. В принципе длина строки имеет фиксированный размер не более 150 символов. Может как то разложить существующие записи так что бы по ним осуществлялся быстрый поиск
  • Вопрос задан
  • 630 просмотров
Пригласить эксперта
Ответы на вопрос 4
Taraflex
@Taraflex
Ищу работу. Контакты в профиле.
Наверное читали уже, но вдруг нет
https://habrahabr.ru/post/342434/
Ответ написан
@klim76
android/java/sql
логирование добавления записей и неминуемое наказание для самый отъявленных рукожуев к вашим услугам.
Но нужно будет реализовать отчёт который раз в день/неделю/месяц будет шерстить наименования на дубляжи
Ответ написан
@d-stream
Готовые решения - не подаю, но...
В момент создания одиночной позиции - вполне реально потратить некоторое время на проверку.
То есть поискать в 100500 записях похожие на дубликаты записи - это может занять часы, а вот при создании карточки товара - что собственно редкая и ответственная операция (доступная не каждому) - подождать 3-5-10 сек проверки - вполне приемлемо.
Ответ написан
@basrach
Как вариант. Можно привести сначала строки к какому-то "нормализованному виду". Например, удалить всё кроме букв, удалить места с наиболее вероятными ошибками (буквы а, о), заменить всю кириллицу на латиницу и т.п. и затем положить это всё в в словарь, где каждому такому "хэшу" будет соответствовать 5-10 похожих наименований. При добавлении новой записи сначала вычислять "хэш", затем по соответствующим ему 5-10-15ти записям пройтись нормальной функцией поиска соответствия. Идея в том, чтобы не шерстить все 70к каждый раз, более 90% из них очевидно даже близко не похожи. Собственно нужно просто подобрать способ как отфильтровать эти 90+% заранее.
Ответ написан
Комментировать
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы