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

15.05.14

Разработка - Универсальные функции

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

Файлы

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

Наименование Скачано Купить файл
СравнениеСтрок.epf
.epf 10,66Kb
80 2 500 руб. Купить

Подписка PRO — скачивайте любые файлы со скидкой до 85% из Базы знаний

Оформите подписку на компанию для решения рабочих задач

Оформить подписку и скачать решение со скидкой

Вы можете заказать платную доработку или адаптацию этой разработки под вашу конфигурацию на «Бирже заказов».

  • 0% комиссии — оплата напрямую исполнителю;
  • Исполнители любого масштаба — от отдельных специалистов до команд под проект;
  • Прямой обмен контактами между заказчиком и исполнителем;
  • Безопасная сделка — при необходимости;
  • Рейтинги, кейсы и прозрачная система откликов.

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

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

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

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

Вступайте в нашу телеграмм-группу Инфостарт

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

+64 –

См. также

ДО+ для 1С:Документооборот

Универсальные функции 1С 8.3 1С:Документооборот Россия Платные (руб)

ДО+ — расширение конфигурации, в котором собран постоянно пополняемый набор из 33 востребованных доработок для 1С:Документооборот КОРП 3.0: согласование задач прямо из мессенджеров MAX и Telegram, отзыв согласования и исполнения, гибкие повторные круги, эскалация с точностью до минут, контроль исполнительской дисциплины, выгрузка вложений в ZIP и склейка PDF, реестр документов в Excel, проверка дублей контрагентов и регистрационных номеров. Каждая возможность активируется отдельным флажком в режиме предприятия — включается только то, что нужно конкретной организации. Список функций расширяется с каждым релизом — текущая версия 2.1.0. Режим AddOn: типовая конфигурация не модифицируется, обновления ДО ставятся штатно, дополнительные лицензии и внешние компоненты не требуются. Внедрение силами администратора — около часа.

30000 руб.

09.07.2026    1426    1    0    

2
Заполнение формул в файлах Excel (кроссплатформенное решение)

Загрузка и выгрузка в Excel Универсальные функции Разработчик 1С:Предприятие 8 Россия Бесплатно (free)

Описанный ниже подход позволяет в три шага заполнять формулы в Excel файлы, вне зависимости от ОС сервера (MS Windows Server или Linux). Подход подразумевает отказ от работы с COM-объектом в пользу работы через "объектную модель документа" (DOM).

30.10.2025    8779    Abysswalker    11    

49
Отключение уведомления "Расширение конфигурации неактивно"

Универсальные функции Работа с интерфейсом Разработчик 1С:Предприятие 8 Бесплатно (free)

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

14.05.2025    14535    DeerCven    16    

66
В помощь разработчику: преобразование табличного документа в запрос

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

Внешняя обработка для создания запроса на основании табличных данных.

22.07.2024    11974    278    ixijixi    10    

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

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

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

21.05.2024    68825    dimanich70    87    

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

Универсальные функции Разработчик 1С:Предприятие 8 1C:Бухгалтерия Абонемент ($m)

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

1 стартмани

18.03.2024    9301    7    John_d    13    

59
GUID в 1С 8.3

Универсальные функции Разработчик Стажер 1С:Предприятие 8 1C:Бухгалтерия Бесплатно (free)

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

12.02.2024    85893    atdonya    31    

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

Универсальные функции Разработчик 1С:Предприятие 8 Бесплатно (free)

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

30.11.2023    13498    ke.92@mail.ru    18    

68
Комментарии
Подписаться на ответы Инфостарт бот Сортировка: Древо развёрнутое
Свернуть все
1. ildarovich 8066 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 277 22.05.14 23:30 Сейчас в теме
Круто!!!
Отдельно спасибо за ссылку на суффиксные автоматы
+ – Ответить
5. Ёпрст 1068 23.05.14 12:38 Сейчас в теме
Зачетно!
Пригодится на досуге.
+ – Ответить
6. Makushimo 160 26.05.14 12:33 Сейчас в теме
какой там велосипед?! -))
очень здорово.
+ – Ответить
7. LexSeIch 212 28.05.14 13:00 Сейчас в теме
Мир этому дому!
Отлично! Будет время, обязательно для себя разберусь с алгоритмом и теорией суффиксных автоматов. Автору большое спасибо!
+ – Ответить
8. ivanov660 4989 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 389 10.06.14 12:03 Сейчас в теме
А какие отличия от 1С встроенного СравнениеФайлов ?

Кроме настроек которые есть в 1С
1. Игнорировать пустое пространство
2. Учитывать регистр
3. Учитывать различия в разделителях строк
+ – Ответить
11. bahbah 153 10.06.14 12:16 Сейчас в теме
(10) kiruha, можно сказать, что в СравнениеФайлов единица сравнения - абзац, здесь - символ.
Если бы СравнениеФайлов детализировала отличия до символа - не имело бы смысла делать эту обработку.
Здесь все-таки основная задача сравнить 2 строки и показать конкретные различия, а не столько сам факт различия.
+ – Ответить
12. kiruha 389 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
+ – Ответить
Для отправки сообщения требуется регистрация/авторизация