Реализация сравнения текстовых файлов

27.01.17

Разработка - Инструментарий разработчика

Понадобилось мне для одного моего проекта сравнивать файлы. После недолгого гугления оказалось, что сравнение файлов это весело! А еще 1С, оказывается, поддерживает многомерные массивы. В статье будет рассмотрена общая задача нахождения наибольшей общей подпоследовательности и немного отсебятины. PS.: про существование kdiff3 знаю

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

Наименование Файл Версия Размер
Пример обработки сравнения файлов
.epf 10,49Kb
10
.epf 10,49Kb 10 Скачать

Подпоследовательности

Пусть у нас есть последовательности АБВГДЕЖЗ и АВБГДЖ. Общая подпоследовательность это например АГЖ, она есть в обеих последовательностях: АБВГДЕЖЗ и АВБГДЖ. При этом АБВ не входит в АВБГДЖ - не тот порядок букв, и поэтому АБВ не общая подпоследовательность для АБВГДЕЖЗ и АВБГДЖ. Общих подпоследовательностей много, среди них есть самые длинные - наибольшие.

Когда мы смотрим на сравнение двух текстов, фактически мы смотрим на наибольшую общую подпоследовательность строк (сопоставленные строки), а добавленные/удаленные - это те что не вошли в неё. 

Алгоритмы и понятия я почерпнул из http://foxford.ru/wiki/informatika/naibolshaya-obschaya-podposledovatelnost

Подготовка

Перед тем как сравнить тексты, их разбивают на строки и хешируют. За функцию хеша спасибо //infostart.ru/public/100845/, возможно встроенная в платформу SHA256 была бы быстрее, но в этой публикации использование очевидное, а узкое место в быстродействии всей обработки не здесь.

Потом строится таблица длин подпоследовательностей такого вида:

 

А

В

Б

Г

Д

Ж

 

0

0

0

0

0

0

0

А

0

0

1

1

1

1

1

Б

0

1

1

2

2

2

2

В

0

1

2

2

2

2

2

Г

0

1

2

2

3

3

3

Д

0

1

2

2

3

4

4

Е

0

1

2

2

3

4

4

Ж

0

1

2

2

3

4

5

З

0

1

2

2

3

4

5

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

 

Обратите внимание, что на пересечении Б и В получилась развилка - выбор зависит от того, как написан алгоритм. Дав возможность менять выбор пути при построении дерева можно сделать удобнее сравнение модулей*

*Сейчас пример построить не смог, но раньше встречал - когда добавленный код перемешивался с типовым т.к. встречались одинаковые куски.

Реализация всего этого в приложенной обработке. Надеюсь, вам было также интересно узнать всё это, как и мне.

Быстродействие

Конечно, использовать 1с в качестве числодробилки - не самая лучшая идея и быстродействие ожидаемо проигрывает существующим утилитам, но некоторая оптимизация была проведена. Во первых оказалось плохой идеей использовать для хранения таблицы таблицу значений и обращаться к колонкам по имени - после замены её на двумерный массив всё ускорилось. Во вторых - запись циклов одной строкой дала ещё двойное ускорение. Сейчас файлы длинной 1000 строк сравниваются у меня примерно за 3 секунды. Вероятно, можно улучшать этот показатель, но для моих дальнейших задач этого хватает. Для файлов большей длины используйте её с осторожностью.

См. также

SALE! 20%

Infostart Toolkit: Инструменты разработчика 1С 8.3 на управляемых формах

Инструментарий разработчика Роли и права Запросы СКД Платформа 1С v8.3 Управляемые формы Запросы Система компоновки данных Конфигурации 1cv8 Платные (руб)

Набор инструментов программиста и специалиста 1С для всех конфигураций на управляемых формах. В состав входят инструменты: Консоль запросов, Консоль СКД, Консоль кода, Редактор объекта, Анализ прав доступа, Метаданные, Поиск ссылок, Сравнение объектов, Все функции, Подписки на события и др. Редактор запросов и кода с раскраской и контекстной подсказкой. Доработанный конструктор запросов тонкого клиента. Продукт хорошо оптимизирован и обладает самым широким функционалом среди всех инструментов, представленных на рынке.

13000 10400 руб.

02.09.2020    122176    670    389    

714

SALE! 25%

Infostart PrintWizard

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

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

18000 15300 руб.

06.10.2023    7296    21    6    

39

SALE! 20%

Infostart УДиФ: Управление данными и формами

Инструменты администратора БД Инструментарий разработчика Роли и права Платформа 1С v8.3 Конфигурации 1cv8 Россия Платные (руб)

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

10000 8000 руб.

10.11.2023    3543    11    1    

34

SALE! 30%

PowerTools

Инструментарий разработчика Инструменты администратора БД Платформа 1С v8.3 Управляемые формы Конфигурации 1cv8 Россия Платные (руб)

Универсальный инструмент программиста для администрирования конфигураций. Сборник наиболее часто используемых обработок под единым интерфейсом.

3600 2520 руб.

14.01.2013    177757    1073    0    

849

Многопоточность. Универсальный «Менеджер потоков» 2.1

Инструментарий разработчика Платформа 1С v8.3 Конфигурации 1cv8 Россия Платные (руб)

Восстановление партий или взаиморасчетов, расчет зарплаты, пакетное формирование документов или отчетов - теперь все это стало доступнее. * Есть желание повысить скорость работы медленных алгоритмов! Но... * Нет времени думать о реализации многопоточности? * о запуске и остановке потоков? * о поддержании потоков в рабочем состоянии? * о передаче данных в потоки и как получить ответ из потока? * об организации последовательности? Тогда ЭТО - то что надо!!!

5000 руб.

07.02.2018    99348    239    97    

296

[ЕХТ] Фреймворк для Расширений 1С

Инструментарий разработчика Платформа 1С v8.3 Управляемые формы Платные (руб)

"Фреймворк для Расширений 1С" это универсальное и многофункциональное решение, упрощающее разработку и поддержку создаваемых Расширений. Поставляется в виде комплекта из нескольких Расширений с открытым исходным кодом. Работает в любых Конфигурациях в режиме Управляемого приложения с режимом совместимости 8.3.12 и выше без необходимости внесения изменений в Конфигурацию.

3000 руб.

27.08.2019    18116    6    8    

39

1С HTML Шаблоны / HTML Templates

Инструментарий разработчика Платформа 1С v8.3 Конфигурации 1cv8 Платные (руб)

Быстрая и удобная обработка для работы с шаблонами HTML. Позволяет легко и быстро формировать код HTML.

2040 руб.

27.12.2017    28110    3    10    

15

Выполнение произвольного кода или запроса с параметрами через Web-сервис (замена COM-подключений)

Инструментарий разработчика Обмен между базами 1C Платформа 1С v8.3 Платные (руб)

В процессе работы в 1С часто возникает потребность получить данные из другой базы.  Обычно это делается через COM-соединение, и время выполнения запроса при этом оставляет желать лучшего. В данной публикации представлено универсальное решение, позволяющее практически моментально выполнить произвольный код или запрос с параметрами в другой информационной базе через Web-сервис.

2400 руб.

24.09.2019    23604    15    15    

32
Комментарии
В избранное Подписаться на ответы Сортировка: Древо развёрнутое
Свернуть все
1. tormozit 7136 27.01.17 14:10 Сейчас в теме
Опечатка "Бастродействие"
2. ildarovich 7850 28.01.17 11:33 Сейчас в теме
"Перед тем как сравнить тексты, их разбивают на строки и хешируют" - в данном случае в этом нет необходимости. Строки достаточно "пронумеровать". То есть, просматривая строки вниз по тексту, каждой новой (не встречающейся ранее) найденной строке присваивать новый номер. Это можно сделать при помощи такой структуры как соответствие.
Посмотрите как это сделано, например, в обработке http://infostart.ru/public/294285/ .
3. pumbaE 28.01.17 13:27 Сейчас в теме
(2) а какие можете посоветовать алгоритмы для diff xml деревьев и для последующего merge? Если для объектов метаданных xml доволно таки простой и достаточно искать соответствия по имени или по uuid, то для форм не так просто сделать определить правильный порядок, т.к. вложенность элементов может быть большая.
4. ildarovich 7850 28.01.17 15:11 Сейчас в теме
(3) тема diff tree algorithm очень специфичная, напрямую сталкиваться не приходилось, могу только посоветовать посмотреть вот эти статьи, чтобы понять, что вообще в этой области происходит:
https://www.deltaxml.com/support/documents/articles-and-papers/is2004.pdf
http://treepatch.sourceforge.net/report.pdf
а также вот эту ссылку:
http://stackoverflow.com/questions/5894879/detect-differences-between-tree-structures .
Оставьте свое сообщение