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

Question

[bearpaw]

Здравствуйте!
Есть некоторая таблица с наименованиями номенклатур . Около 70К записей.
Необходимо что бы каждая вновь вносимая номенклатура проверялась на уникальность.
Иногда сотрудники пишут вместо русской х (с) латинскую х (c).
Пробовали сходство Джаро — Винклера , расстояние Дамерау-Левенштейна (в виде функций на MS SQL Server). Это все работает и даже идеально работает. Кроме одного - время. Необходимо что бы на операцию уходило 10-20 секунд, а данные алгоритмы работаю от 2-3 минуты до 10-15. Причем время возрастает логарифмически в зависимости от длины нового слова, т.к. вычисляется параметр для каждой строки. Нормализация строки поиска (убираем пробелы, запяты, точки и т.п.) дает выигрыш 3-4 секунды.
Может кто-то знает или видел быстрые алгоритмы поиска сходства? Например на основе NGram, или использовании хэшей. В принципе длина строки имеет фиксированный размер не более 150 символов. Может как то разложить существующие записи так что бы по ним осуществлялся быстрый поиск

Comments

[Артём Каретников]

Стесняюсь спросить, но если заведомо известно, что буква должна быть русской, почему нельзя тупо до ввода ее в базу делать replace?

[bearpaw]

Артём Каретников, нормализация делается . но если человек выбросит букву из слова или поменяет местами (такое тоже бывает), то найти 100% соответствия не возможно.

Answer 1

[Александр Таратин]

Наверное читали уже, но вдруг нет
https://habrahabr.ru/post/342434/

Comments

[bearpaw]

Да смотрел. На хабре есть несколько статей. Некоторые проверяли , но существующее время не входит в разумные границы.

[Александр Таратин]

bearpaw, В статье таблица на 2 ляма. У вас 70к. Думаю стоит попробовать самый быстрый способ из статьи.

[Александр Таратин]

bearpaw, Иначе переводим все в транслит и используем sphinxsearch.com с включенным soundex или metaphone

Answer 2

[Евгений]

логирование добавления записей и неминуемое наказание для самый отъявленных рукожуев к вашим услугам.
Но нужно будет реализовать отчёт который раз в день/неделю/месяц будет шерстить наименования на дубляжи

Comments

[bearpaw]

Да это прекрасный вариант. Но практически мгновенно созданная номенклатура используется в проектировании, закупках, обсчете себестоимости. Желательно намекнуть пользователю на моменте создания что данная номенклатура может (с вероятностью > 90%) является дублем.

Answer 3

[d-stream]

В момент создания одиночной позиции - вполне реально потратить некоторое время на проверку.
То есть поискать в 100500 записях похожие на дубликаты записи - это может занять часы, а вот при создании карточки товара - что собственно редкая и ответственная операция (доступная не каждому) - подождать 3-5-10 сек проверки - вполне приемлемо.

Comments

[bearpaw]

3-5-10-20 секунд это приемлемо.
не приемлемо до получаса держать.

[d-stream]

bearpaw, то есть поиск похожих на ОДИН образец занимает столько времени??????

[bearpaw]

d-stream, для каждой новой записи , необходимо провести проверку со всеми существующими записями и получить похожую ~ 90% соответствия, ну либо не получить.
Т.е. каждый раз выполняется расчет по новой.

Answer 4

[basrach]

Как вариант. Можно привести сначала строки к какому-то "нормализованному виду". Например, удалить всё кроме букв, удалить места с наиболее вероятными ошибками (буквы а, о), заменить всю кириллицу на латиницу и т.п. и затем положить это всё в в словарь, где каждому такому "хэшу" будет соответствовать 5-10 похожих наименований. При добавлении новой записи сначала вычислять "хэш", затем по соответствующим ему 5-10-15ти записям пройтись нормальной функцией поиска соответствия. Идея в том, чтобы не шерстить все 70к каждый раз, более 90% из них очевидно даже близко не похожи. Собственно нужно просто подобрать способ как отфильтровать эти 90+% заранее.