Поиск дублей по полям ключей шапки, табличных частей (используем hash функцию)

08.07.24

Разработка - Математика и алгоритмы

Рассмотрим быстрый алгоритм поиска дублей с использованием hash функции по набору полей шапки и табличных частей.

Достаточно часто встречаются задачи поиска одинаковых элементов справочников и других объектов данных - поиск дублей данных. Обычно критерии поиска достаточно простые - содержат один или несколько полей из "шапки" элемента метаданных. Но иногда условия бывают сложными - выполнить поиск с учетом совпадения полей в табличных частях, например, найти одинаковые ресурсные спецификации, у которых номенклатура в рецептуре совпадает.

Когда данных у нас тысячи или сотни тысяч, то алгоритм поиска в лоб путем перебора будет достаточно длительной операцией. И в этом случае требуется более производительный механизм, особенно, когда хочется искать дубли практически онлайн. Возникает вопрос: "А как можно решить подобную задачу?".

И в этой статье я хочу рассказать об одном таком алгоритме, который использует хеширование данных для поиска в прикладных задачах на языке 1С. 

 

Структура статьи:

  • стандартный алгоритм поиска
  • алгоритм с использование хеширования
  • замечания к алгоритму хеширования
  • еще один вариант использования 
  • заключение

 

Стандартный алгоритм поиска - простая задача

 

Сначала рассмотрим простую задачу нахождения одинаковых элементов данных справочников номенклатуры при заведении новой карточки элемента. У нас есть критерий поиска соответствия по равенству артикула, тогда мы можем написать достаточно простой запрос для поиска наличия дублей в алгоритме перед записью:

 
 Алгоритм поиска дублей по артикулу

 

//...

Запрос = Новый Запрос();
Запрос.Текст = "ВЫБРАТЬ
|	Номенклатура.Ссылка КАК Ссылка
|ИЗ
|	Справочник.Номенклатура КАК Номенклатура
|ГДЕ
|	Номенклатура.Артикул = &Артикул
|	И НЕ Номенклатура.ПометкаУдаления";

Запрос.УстановитьПараметр("Артикул",Артикул);

РезультатЗапроса = Запрос.Выполнить();    

Отказ = НЕ РезультатЗапроса.Пустой();

//...

 

 

Усложненная задача - алгоритм с использованием хеширования (hash функции)

 

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

 

Рис. Пример задачи поиска дублей по справочнику ресурсные спецификации

 

Теперь при попытке написать запрос, то мы должны будем решить достаточно сложную задачу - мы должны будем сравнить табличную часть без учета порядка строк по равенству сырья и равенству количества. Писать подобный запрос мы не будем, а будем использовать механизм сравнения хешированием.

С одним из примеров использования подобного алгоритма можно ознакомиться, если почитать про работу оператора соединения хешированием - hash_join в различных СУБД.

Для реализации этого алгоритма под задачи нахождения дублей нам потребуется выполнить следующие вещи:

  1. Добавить новый строковый реквизит и назвать его hash_ключ (не забываем его проиндексировать)
  2. Создать функцию для вычисления этого ключа перед записью
  3. При поиске дублей мы получим hash_ключ создаваемого элемента и выполним запрос поиска в таблице спецификаций

Думаю, что с задачей добавления нового реквизита и его индексирования мы справимся без проблем, поэтому опустим этот момент.

Функцию создания ключа при записи элемента можно описать следующим образом:

 
Процедура ПередЗаписью(Отказ)

	// ...
	hash_Ключ = ПолучитьHashКлюч(ЭтотОбъект);
	// ...

КонецПроцедуры


Функция ПолучитьHashКлюч(Источник,СортировкаСтрок=Истина)
	
	КлючевыеПоляШапки="ОсновноеИзделиеНоменклатура,ОсновноеИзделиеХарактеристика";
	КлючевыеПоляТабличнойЧастиМатериалы = "Номенклатура,Характеристика,КоличествоУпаковок";
	
	// 1. Формируем описание объекта поиска
	МассивСтруктур = Новый Массив;
	
	// по шапке
	ПолучитьМассивСтруктурОбъекта(Источник,МассивСтруктур,СтрРазделить(КлючевыеПоляШапки,","));
	
	// по материалам
	МассивЧастей = СтрРазделить(КлючевыеПоляТабличнойЧастиМатериалы,",");
	
	Если СортировкаСтрок=Истина Тогда      
		ТаблицаТЧ = Источник.МатериалыИУслуги.Выгрузить();
		ТаблицаТЧ.Сортировать(КлючевыеПоляТабличнойЧастиМатериалы);
	Иначе
		ТаблицаТЧ = Источник.МатериалыИУслуги;
	КонецЕсли;
	
	Для Каждого стр из ТаблицаТЧ Цикл
		ПолучитьМассивСтруктурОбъекта(стр,МассивСтруктур,МассивЧастей);	
	КонецЦикла;                    
	
	// 2. Преобразуем в XML
	ЗаписьXML = Новый ЗаписьXML;
	ЗаписьXML.УстановитьСтроку();
	СериализаторXDTO.ЗаписатьXML(ЗаписьXML,МассивСтруктур);
	
	// 3. Формируем хеш
	Хешировавние  = Новый ХешированиеДанных(ХешФункция.SHA512);
	Хешировавние.Добавить(ЗаписьXML.Закрыть());	
	
	Возврат Хешировавние.ХешСумма;
	
КонецФункции      


Процедура ПолучитьМассивСтруктурОбъекта(Источник,ТаблицаСравнения,МассивЧастей)
	
	Для каждого рек из МассивЧастей Цикл
		ТаблицаСравнения.Добавить(Новый Структура("Реквизит,Значение",рек,Источник[рек]));
	КонецЦикла;	
	
КонецПроцедуры

 

 

Рассмотрим кратко логику работы алгоритма:

  1. Сначала мы получаем данные по ключам, которые будем использовать для сравнения. Эти данные сохраняются в массиве структур.
    Обратите внимание! Мы используем опцию сортировки строк табличной части, благодаря этому достигается независимость алгоритма от положения строк.
  2. Следующим шагом мы преобразуем полученную таблицу в xml текст
  3. И от этого текста мы получаем hash значение, которое в дальнейшем используется как ключ сравнения.

 

Рис. Порядок строк может меняться

 

Функция проверки на дубли получится такой-же простой, как и вариант выше:

 
 Поиск дублей по hash-ключу

 

//...

Запрос = Новый Запрос();
Запрос.Текст = "ВЫБРАТЬ
|	РС.Ссылка КАК Ссылка
|ИЗ
|	Справочник.РесурсныеСпецификации КАК РС
|ГДЕ
|	РС.hash_ключ = &hash_ключ
|	И НЕ РС.ПометкаУдаления";   

Запрос.УстановитьПараметр("hash_ключ",ПолучитьHashКлюч(ЭтотОбъект));

РезультатЗапроса = Запрос.Выполнить();    

Отказ = НЕ РезультатЗапроса.Пустой();

//...

 

 

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

 

Рис. Пример использования алгоритма - обработка сравнения

 

Замечания к алгоритму 

 

Ограничения применения. Данный алгоритм работает по равенству, иными словами вы можете искать только при условии равно. Если у вас встречаются комбинации с условием "ИЛИ", тогда вам придется бить алгоритм на части. А вот при условии больше или меньше он не умеет работать совсем.

Также обращаю ваше внимание, что алгоритм "жесткий", а не вероятностный, т.е. дает ответ на вопрос соответствия - только да или нет.

Быстродействие. За счет того что новый реквизит проиндексирован и он один, поиск будет работать очень быстро. А вот при использовании типового алгоритма вам потребуется написать достаточно сложный запрос (вероятно пакет запросов) и для вероятной быстрой работы проиндексировать большинство полей при использовании, что не всегда является возможным (особенно если мы не хотим снимать с поддержки типовую конфигурацию) и рациональным (наличие большого количества индексов не только приносит пользу, но и вред) и не всегда помогает.

Коллизии. При использования алгоритма существует небольшая вероятность создания одинакового hash-ключа для двух разных элементов, поэтому после определения потенциальных дублей, рекомендуется провести дополнительную проверку на совпадение данных сопоставлением элементов вручную. Поэтому можно добавить небольшое дополнение - функцию сравнения массивов структур совпавших элементов.

 

Еще один алгоритм

 

Рассмотрим еще один алгоритм хеширования, когда выполняется неявное преобразование для разработчика самой платформой 1С. Возможно вы уже догадались что речь идет про один из видов универсальных коллекций значений - Соответствие.

Давайте рассмотрим некоторую простую, но показательную задачу. Пусть нам требуется создать некоторый список с дублями контрагентов. Мы хотим найти контрагентов с одинаковыми ИНН+КПП.

Замечание! Такой алгоритм мы достаточно часто используем при загрузке сырых данных из внешних источников, таких как например Excel.

Алгоритм действий следующий:

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

 

Процедура НайтиДублиКонтрагентовНаСервере()
	
	// 1. Формируем новую коллекцию
	ДублиКонтрагентов = Новый Соответствие;
	
	// 2. Получим данные
	Запрос = Новый Запрос;
	Запрос.Текст = "ВЫБРАТЬ
	|	Контрагенты.ИНН КАК ИНН,
	|	Контрагенты.КПП КАК КПП,
	|	Контрагенты.Ссылка КАК Ссылка
	|ИЗ
	|	Справочник.Контрагенты КАК Контрагенты";
	
	Выборка = Запрос.Выполнить().Выбрать();
	
	// 3. Ищем дубли	
	Пока Выборка.Следующий() Цикл
		Ключ = Выборка.ИНН+"/"+Выборка.КПП;
		МассивДублей = ДублиКонтрагентов.Получить(Ключ);
		Если МассивДублей=Неопределено Тогда
			МассивДублей = Новый Массив();
			ДублиКонтрагентов.Вставить(Ключ,МассивДублей);
		КонецЕсли;                     
		МассивДублей.Добавить(Выборка.Ссылка);
	КонецЦикла;                        
	
	// 4. Обработка (загружаем в таблицу с колонками - Ключ, Количество и СписокЗначений)
	ТаблицаДублейКонтрагентов.Очистить();
	Для каждого эл из ДублиКонтрагентов Цикл
		стр_н = ТаблицаДублейКонтрагентов.Добавить();
		стр_н.Ключ = эл.Ключ;
		стр_н.Количество = эл.Значение.Количество();
		стр_н.СписокЗначений.ЗагрузитьЗначения(эл.Значение);
	КонецЦикла;  	
	
КонецПроцедуры

 

 

Рис. Пример обработки поиска дублей с помощью универсальной коллекции - соответствие

 

Заключение

 

Мы рассмотрели основную идею и подход, практическое использование остается за Вами и зависит от конкретной ситуации. Вариации же рассмотренного алгоритма довольно успешно применяется на практике. Фактически рассмотренный подход достаточно быстрый и простой для реализации, подходит для тех случаев, когда использование альтернативных решений не целесообразно.

поиск дубли хеширование hash

См. также

Инструментарий разработчика Роли и права Запросы СКД Программист Платформа 1С v8.3 Управляемые формы Запросы Система компоновки данных Конфигурации 1cv8 Платные (руб)

Набор инструментов программиста и специалиста 1С для всех конфигураций на управляемых формах. В состав входят инструменты: Консоль запросов, Консоль СКД, Консоль кода, Редактор объекта, Анализ прав доступа, Метаданные, Поиск ссылок, Сравнение объектов, Все функции, Подписки на события и др. Редактор запросов и кода с раскраской и контекстной подсказкой. Доработанный конструктор запросов тонкого клиента. Продукт хорошо оптимизирован и обладает самым широким функционалом среди всех инструментов, представленных на рынке.

10000 руб.

02.09.2020    139558    765    391    

800

HighLoad оптимизация Запросы

Очень немногие из тех, кто занимается поддержкой MS SQL, работают с хранилищем запросов. А ведь хранилище запросов – это очень удобный, мощный и, главное, бесплатный инструмент, позволяющий быстро найти и локализовать проблему производительности и потребления ресурсов запросами. В статье расскажем о том, как использовать хранилище запросов в MS SQL и какие плюсы и минусы у него есть.

11.10.2023    17705    skovpin_sa    14    

102

Запросы HighLoad оптимизация Программист Запросы Бесплатно (free)

Многие знают, что для ускорения работы запроса нужно «изучить план». При этом сам план обычно обескураживает: куча разноцветных иконок и стрелочек; ничего не понятно, но очень интересно! Аналитик производительности Александр Денисов на конференции Infostart Event 2021 Moscow Premiere рассказал, как выполняется план запроса и что нужно сделать, чтобы с его помощью находить проблемы производительности.

20.06.2023    20590    Филин    37    

118

Запросы Инструментарий разработчика Программист Бесплатно (free)

Список всех популярных обработок.

17.03.2023    44752    kuzyara    87    

187

Запросы Механизмы платформы 1С Программист Платформа 1С v8.3 Запросы Бесплатно (free)

В платформе 8.3.22 появилась возможность получать идентификатор в запросе. Лично я ждал этого давно, но по итогу ждал большего. Что не так?

12.01.2023    49624    dsdred    26    

103

Механизмы платформы 1С Запросы Программист Платформа 1С v8.3 Запросы Конфигурации 1cv8 Бесплатно (free)

В предлагаемой статье решил привести примеры применения новых возможностей языка запросов 1С, начиная с версии платформы 8.3.20.

21.11.2022    25432    quazare    36    

125
Комментарии
Подписаться на ответы Инфостарт бот Сортировка: Древо развёрнутое
Свернуть все
1. user1950534 09.07.24 09:36 Сейчас в теме
Ну задача точного совпадения табличных частей на практике мне не попадалась ни разу)) А вот задача проверить, например, что больше половины строк совпадает, или какой-то условный процент, попадается регулярно. Решаю я ее внутренним соединением по равенству нужных мне реквизитов с подсчетом количества. Работает быстро, проблем нет. Хеш-методикой такую задачу не решить. Впрочем, можно замутить хеш на каждую строку, да, по нужным реквизитам. Возможно это облегчило бы такую задачу, в другой раз попробую

Точно так же, совпадение контрагентов по названию и ИНН прекрасно решается запросом с Количество(*) СГРУППИРОВАТЬ ПО ИНН, Наименование. Вместо того, чтобы в цикле перебирать запрос и всё такое. С другой стороны, ну сколько там может быть контрагентов? Всего юр.лиц у нас миллионов 5 в стране, с учетом дублей ну пусть хорошо 50млн. На таких объемах в принципе любой алгоритм сработает относительно быстро.

В 7.7 нельзя было искать сразу по двум полям в таблице значений. Вот там, помню, спасались хешами....
ALmighty; +1 Ответить
2. ivanov660 4540 09.07.24 10:23 Сейчас в теме
(1)
1. Предположу, что вам не часто приходилось решать задачи, когда требуется применять данный подход. Но на самом деле их достаточно много, когда требуется использовать преимущества hash таблиц.
2. Быстро у вас запрос отработает по ИНН, потому что обычно поле это проиндексировано в типовых конфигурациях. Если же задача будет стоять поиск дублей по полному наименованию и т.п., то запрос уже будет не такой шустрый. И относительно быстро для одного пользователя, будет выглядеть уже не так весело, когда их 1000.
3. user612295_death4321 09.07.24 15:37 Сейчас в теме
Главное не пробовать применять данный алгоритм в комбинации с ЗначениеВСтрокуВнутр.

Я когда-то проигнорировал примечание:
Используется для сохранения функциональной совместимости с 1С:Предприятием 7.7. Использовать для других целей не рекомендуется.

и долго ломал голову, почему на одних и тех же отсортированных данных разный хеш.
4. siamagic 09.07.24 22:01 Сейчас в теме
Просто сортируешь тч, сериализуешь.
5. ALmighty 10.07.24 14:32 Сейчас в теме
лучше использовать SHA256
у этого метода есть процессорная аппаратная поддержка
6. Serg2000mr 428 11.07.24 13:26 Сейчас в теме
Можно использовать обертку в виде функции ОбщегоНазначения.КонтрольнаяСуммаСтрокой
7. Casey1984 3 12.07.24 15:50 Сейчас в теме
Делал похожее при миграции с УПП на ERP. Нужно было из номенклатурной каши собрать удобную структуру, группируя по не помню каким признакам ;-)
Оставьте свое сообщение