gifts2017

Сравнение строк с выводом различий

Опубликовал bah bah (bahbah) в раздел Программирование - Универсальные функции

Обработка созданная с целью представить реализованный мной алгоритм сравнения строк. Реализована на 1С 8.1, однако будет работать и на более поздних версиях.

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

Алгоритм: находим наибольшую общую подстроку двух строк (с помощью суффиксных автоматов http://e-maxx.ru/algo/suffix_automata) - получается что каждая строка разбита на 3 части: левая (еще не обработанная), средняя (это наибольшая общая подстрока) и правая (не обработанная). Левую и правую части обрабатываем таким же образом до тех пор, пока не сможем получить общую подстроку - в таком случае подстроки различны. В итоге получаем чередование совпадающих и не совпадающих подстрок.
Алгоритм выполнен без рекурсии - т.е. подходит для обработки больших строк.

Дополнительно для увеличения наглядности добавил вывод в html.

PS: если снова изобрел велосипед - прошу прощения за невнимательность.

Скачать файлы

Наименование Файл Версия Размер
СравнениеСтрок.epf 62
.epf 10,66Kb
14.05.14
62
.epf 10,66Kb Скачать

См. также

Подписаться Добавить вознаграждение
Комментарии
1. Сергей (ildarovich) 17.05.14 00:49
Очень интересно!
И построение суффиксного автомата на 1С запрограммировано. А это действительно сложный и нужный алгоритм. Его реализация и без обертки внешнего алгоритма имеет самостоятельное значение. - Замечательно!

А быстродействие замеряли? - Как насчет действительно больших строк (например, миллион символов)?

Можно ли применять для сравнения текстов модулей до и после изменений?

В чем отличие от алгоритма Diff(наибольшая общая подпоследовательность)?

Нет ли проблем неоднозначности (если одновременно нашлись в разных местах две наибольших совпадающих последовательности одинаковой длины)?
2. bah bah (bahbah) 19.05.14 15:07
(1) ildarovich, быстродействие не замерял. Теоретически, отличия от алгоритма Diff в асимптотическом время работы алгоритма: Diff - O(n1*n2), суффиксные автоматы - O(n1+n2). Однако многое зависит от реализации.
С трудом могу себе представить, где может быть использовано сравнение строк в цикле - это скорее разовая задача, хотя я могу ошибаться, поэтому существенной оптимизации и работы по поиску наиболее быстрого алгоритма не проводил. Остановился на алгоритме с хорошей зависимостью времени выполнения от объема данных. На протяжении полугода использования нареканий по скорости не было.
Алгоритм хорошо себя показывает на родственных строках, в которых внесен небольшой шум.
Проблема неоднозначности в общем случае присутствует, однако для конкретного применения - проблема редко встречается. Для текстов модулей проблема неоднозначности становится слишком серьезной - сравнение получается некрасивым. Возможно внесение дополнительных эвристик сделает этот алгоритм вполне конкурентоспособным и для сравнения модулей.
3. Virikus 21.05.14 09:38
(2) bahbah, Ну таких задач много, навскидку базы всяких рефератов, статей и т.д.
4. pallid *** (white_sochi) 22.05.14 23:30
Круто!!!
Отдельно спасибо за ссылку на суффиксные автоматы
5. Епрст (Ёпрст) 23.05.14 12:38
Зачетно!
Пригодится на досуге.
6. Максим Кузнецов (Makushimo) 26.05.14 12:33
какой там велосипед?! -))
очень здорово.
7. Сергей Маслов (LexSeIch) 28.05.14 13:00
Мир этому дому!
Отлично! Будет время, обязательно для себя разберусь с алгоритмом и теорией суффиксных автоматов. Автору большое спасибо!
8. ivanov660 ivanov660 (ivanov660) 10.06.14 11:02
На мой взгляд правильнее выделять отдельные слова в отличии нежели отдельные части. К примеру, для 2,1 и 1,6 необходимо показать отличие целиком в числах нежели выделять отдельные цифры 2 и 6.
Для таких вещей в принципе достаточно использовать метод шинглов. Работает он быстрее и проще, к тому же есть возможность настраивать уровень сравнения (шаг шингла). Единственная проблема, скорее проблема 1С, а не алгоритма - это отсутствие метода получения значения hash, md5.
9. bah bah (bahbah) 10.06.14 11:16
(8) ivanov660, изначально этот алгоритм разрабатывался для сравнения названий номенклатуры. В целевой базе наименования довольно длинные и очень разнообразные - выделение различных слов приводит с сокращению размерности задачи - сравнению не всего названия, а нескольких слов, однако это все еще затруднительно делать глазами.
Хорошей идеей будет совместить Ваше предложение - выделение отличных слов - с моим алгоритмом - в каждой паре различных слов выделить отличные символы.
Однако и здесь возникает масса вопросов, например - если в исходной строке одно слово а на его месте в другой строке три слова, как быть?
10. kiruha Дронов (kiruha) 10.06.14 12:03
А какие отличия от 1С встроенного СравнениеФайлов ?

Кроме настроек которые есть в 1С
1. Игнорировать пустое пространство
2. Учитывать регистр
3. Учитывать различия в разделителях строк
11. bah bah (bahbah) 10.06.14 12:16
(10) kiruha, можно сказать, что в СравнениеФайлов единица сравнения - абзац, здесь - символ.
Если бы СравнениеФайлов детализировала отличия до символа - не имело бы смысла делать эту обработку.
Здесь все-таки основная задача сравнить 2 строки и показать конкретные различия, а не столько сам факт различия.
12. kiruha Дронов (kiruha) 10.06.14 16:55
(11)
Ок, спасибо, понятно - то же хорошо бы в публикации объяснить
13. Сергей Лямин (bydk) 12.06.14 04:54
(8) ivanov660, в 8.3+ появилась возможность на уровне платформы получать разнообразные хеши...
	ХешMD5 = Новый ХешированиеДанных(ХешФункция.MD5);
	ХешMD5.Добавить("Строка");
	Результат = ХешMD5.ХешСумма;
14. Юрий Лу (yura1960) 21.06.14 17:02
Велосипед, но зачетный. Автору, в любом случае, спасибо. Как дополнительная опция к стандартным - подойдет.