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

15.05.14

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

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

Файлы

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

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

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

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

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

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

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

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

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

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

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

+64 –

См. также

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

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

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

21.05.2024    36800    dimanich70    83    

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

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

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

1 стартмани

18.03.2024    5545    6    John_d    11    

57
GUID в 1С 8.3

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

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

12.02.2024    43035    atdonya    29    

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

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

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

30.11.2023    7217    ke.92@mail.ru    17    

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

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

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

15.09.2023    31460    YA_418728146    10    

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

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

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

28.08.2023    19614    YA_418728146    8    

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

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

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

2 стартмани

22.08.2023    5391    86    progmaster    13    

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

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

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

1 стартмани

13.10.2022    21303    211    sapervodichka    117    

138
Комментарии
Подписаться на ответы Инфостарт бот Сортировка: Древо развёрнутое
Свернуть все
1. ildarovich 8018 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 275 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 4747 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
+ – Ответить
Оставьте свое сообщение