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

15.05.14

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

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

Файлы

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

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

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

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

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

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

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

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

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

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

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

+64 –

См. также

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

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

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

30.10.2025    4551    Abysswalker    11    

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

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

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

14.05.2025    8431    DeerCven    15    

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

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

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

22.07.2024    10438    256    ixijixi    10    

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

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

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

21.05.2024    55974    dimanich70    84    

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

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

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

1 стартмани

18.03.2024    7910    7    John_d    13    

59
GUID в 1С 8.3

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

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

12.02.2024    70402    atdonya    31    

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

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

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

30.11.2023    9901    ke.92@mail.ru    17    

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

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

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

15.09.2023    45727    YA_418728146    16    

129
Комментарии
Подписаться на ответы Инфостарт бот Сортировка: Древо развёрнутое
Свернуть все
1. ildarovich 8054 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 4964 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
+ – Ответить
Для отправки сообщения требуется регистрация/авторизация