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

15.05.14

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

Скачать файл

ВНИМАНИЕ: Файлы из Базы знаний - это исходный код разработки. Это примеры решения задач, шаблоны, заготовки, "строительные материалы" для учетной системы. Файлы ориентированы на специалистов 1С, которые могут разобраться в коде и оптимизировать программу для запуска в базе данных. Гарантии работоспособности нет. Возврата нет. Технической поддержки нет.

Наименование		По подписке [?]	Купить один файл
СравнениеСтрок.epf .epf 10,66Kb 80	80	Скачать (1 SM)	Купить за 1 850 руб.

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

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

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

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

Сравнение строк

+64 –

См. также

Загрузка табличного документа в таблицу значений. Пять строк кода, которые изменили мир

Универсальные функции Программист Платформа 1С v8.3 1C:Бухгалтерия Бесплатно (free)

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

21.05.2024 31335 dimanich70 83

152

Вставляем картинку из буфера обмена (платформа 1С 8.3.24)

Универсальные функции Программист Платформа 1С v8.3 1C:Бухгалтерия Абонемент ($m)

Задача: вставить картинку из буфера обмена на форму средствами платформы 1С.

1 стартмани

18.03.2024 5042 6 John_d 11

GUID в 1С 8.3

Универсальные функции Программист Стажер Платформа 1С v8.3 1C:Бухгалтерия Бесплатно (free)

Пришлось помучиться с GUID-ами немного, решил поделиться опытом, мало ли кому пригодится.

12.02.2024 35429 atdonya 29

Переоткрытие внешних обработок

Универсальные функции Программист Платформа 1С v8.3 Бесплатно (free)

На заключительных этапах, когда идет отладка или доработка интерфейса, необходимо много раз переоткрыть внешний объект. Вот один из способов автоматизации этого.

30.11.2023 6659 ke.92@mail.ru 17

Генерация штрихкода и QR, разбор настроек и примеры

БСП (Библиотека стандартных подсистем) Сканер штрих-кода Универсальные функции Этикетки, ценники Программист Бизнес-аналитик 1C:Бухгалтерия Бесплатно (free)

Разберем на примерах использование компоненты из БСП для генерации штрихкода и матричных кодов.

15.09.2023 27118 YA_418728146 10

123

Валидация JSON через XDTO (включая массивы)

WEB-интеграция Универсальные функции Механизмы платформы 1С Программист Платформа 1С v8.3 1C:Бухгалтерия Бесплатно (free)

При работе с интеграциями рано или поздно придется столкнуться с получением JSON файлов. И, конечно же, жизнь заставит проверять файлы перед тем, как записывать данные в БД.

28.08.2023 18291 YA_418728146 8

172

Печать непроведенных документов для УТ, КА, ERP. Настройка печати по пользователям, документам и печатным формам

Пакетная печать Печатные формы Адаптация типовых решений Универсальные функции Платформа 1С v8.3 1С:ERP Управление предприятием 2 1С:Управление торговлей 11 1С:Комплексная автоматизация 2.х Россия Абонемент ($m)

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

2 стартмани

22.08.2023 4890 80 progmaster 11

Расширение: Быстрые отборы через буфер [Alt+C] Копировать список, [Alt+V] Вставить список, [Ctrl+C] Копировать из файлов

Инструментарий разработчика Универсальные функции Платформа 1С v8.3 1C:Бухгалтерия 1С:Розница 2 1С:ERP Управление предприятием 2 1С:Бухгалтерия 3.0 1С:Управление торговлей 11 1С:Комплексная автоматизация 2.х 1С:Зарплата и Управление Персоналом 3.x Абонемент ($m)

Копирует в буфер значения из списков, из ячеек отчетов, таблиц, настроек списков, других отборов и вставляет в выбранную настройку отбора. Работает с Объект не найден. Работает как в одной так и между разными базами 1С. Использует комбинации [Alt+C] Копировать список, [Alt+V] Вставить список. Также для копирования данных используется стандартная [Ctrl+C] (например из открытого xls, mxl, doc и т.п. файла скопировать список наименований)

1 стартмани

13.10.2022 19968 191 sapervodichka 113

137

Комментарии

Подписаться на ответы Инфостарт бот

Свернуть все

1. ildarovich 7958 17.05.14 00:49 Сейчас в теме

Очень интересно!
И построение суффиксного автомата на 1С запрограммировано. А это действительно сложный и нужный алгоритм. Его реализация и без обертки внешнего алгоритма имеет самостоятельное значение. - Замечательно!

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

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

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

Нет ли проблем неоднозначности (если одновременно нашлись в разных местах две наибольших совпадающих последовательности одинаковой длины)?

2. bahbah 153 19.05.14 15:07 Сейчас в теме

(1) ildarovich, быстродействие не замерял. Теоретически, отличия от алгоритма Diff в асимптотическом время работы алгоритма: Diff - O(n1*n2), суффиксные автоматы - O(n1+n2). Однако многое зависит от реализации.
С трудом могу себе представить, где может быть использовано сравнение строк в цикле - это скорее разовая задача, хотя я могу ошибаться, поэтому существенной оптимизации и работы по поиску наиболее быстрого алгоритма не проводил. Остановился на алгоритме с хорошей зависимостью времени выполнения от объема данных. На протяжении полугода использования нареканий по скорости не было.
Алгоритм хорошо себя показывает на родственных строках, в которых внесен небольшой шум.
Проблема неоднозначности в общем случае присутствует, однако для конкретного применения - проблема редко встречается. Для текстов модулей проблема неоднозначности становится слишком серьезной - сравнение получается некрасивым. Возможно внесение дополнительных эвристик сделает этот алгоритм вполне конкурентоспособным и для сравнения модулей.

3. Virikus 64 21.05.14 09:38 Сейчас в теме

(2) Ну таких задач много, навскидку базы всяких рефератов, статей и т.д.

4. pallid 274 22.05.14 23:30 Сейчас в теме

Круто!!!
Отдельно спасибо за ссылку на суффиксные автоматы

5. Ёпрст 1067 23.05.14 12:38 Сейчас в теме

Зачетно!
Пригодится на досуге.

6. Makushimo 160 26.05.14 12:33 Сейчас в теме

какой там велосипед?! -))
очень здорово.

7. LexSeIch 212 28.05.14 13:00 Сейчас в теме

Мир этому дому!
Отлично! Будет время, обязательно для себя разберусь с алгоритмом и теорией суффиксных автоматов. Автору большое спасибо!

8. ivanov660 4729 10.06.14 11:02 Сейчас в теме

На мой взгляд правильнее выделять отдельные слова в отличии нежели отдельные части. К примеру, для 2,1 и 1,6 необходимо показать отличие целиком в числах нежели выделять отдельные цифры 2 и 6.
Для таких вещей в принципе достаточно использовать метод шинглов. Работает он быстрее и проще, к тому же есть возможность настраивать уровень сравнения (шаг шингла). Единственная проблема, скорее проблема 1С, а не алгоритма - это отсутствие метода получения значения hash, md5.

9. bahbah 153 10.06.14 11:16 Сейчас в теме

(8) ivanov660, изначально этот алгоритм разрабатывался для сравнения названий номенклатуры. В целевой базе наименования довольно длинные и очень разнообразные - выделение различных слов приводит с сокращению размерности задачи - сравнению не всего названия, а нескольких слов, однако это все еще затруднительно делать глазами.
Хорошей идеей будет совместить Ваше предложение - выделение отличных слов - с моим алгоритмом - в каждой паре различных слов выделить отличные символы.
Однако и здесь возникает масса вопросов, например - если в исходной строке одно слово а на его месте в другой строке три слова, как быть?

13. bydk 12.06.14 04:54 Сейчас в теме

(8) ivanov660, в 8.3+ появилась возможность на уровне платформы получать разнообразные хеши...

	ХешMD5 = Новый ХешированиеДанных(ХешФункция.MD5);
	ХешMD5.Добавить("Строка");
	Результат = ХешMD5.ХешСумма;

10. kiruha 388 10.06.14 12:03 Сейчас в теме

А какие отличия от 1С встроенного СравнениеФайлов ?

Кроме настроек которые есть в 1С
1. Игнорировать пустое пространство
2. Учитывать регистр
3. Учитывать различия в разделителях строк

11. bahbah 153 10.06.14 12:16 Сейчас в теме

(10) kiruha, можно сказать, что в СравнениеФайлов единица сравнения - абзац, здесь - символ.
Если бы СравнениеФайлов детализировала отличия до символа - не имело бы смысла делать эту обработку.
Здесь все-таки основная задача сравнить 2 строки и показать конкретные различия, а не столько сам факт различия.

12. kiruha 388 10.06.14 16:55 Сейчас в теме

(11)
Ок, спасибо, понятно - то же хорошо бы в публикации объяснить

14. yura1960 21.06.14 17:02 Сейчас в теме

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

15. user840225 14.05.18 19:44 Сейчас в теме

Замечена не очень корректная работа обработки (((
При
1 >Строка1 = "Оттмеченные"
2 >Строка2 = "Отмеченые"

Результат
1 >Отмеченыеные
2 >Отмеченые

Если поменять строки местами, все вроде работает.
Лучшая подстрока = "Отмечен" не существует в первой строке.

16. user840225 15.05.18 16:17 Сейчас в теме

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

Прикрепленные файлы:

СравнениеСтрок2.epf