Работая над обработкой сравнения документа с присланной версией печатной формы заказа в xls, столкнулся с необходимостью сообщать не только сам факт отличия в названиях товаров, но и информации о том, что конкретно отличается. Беглое знакомство с материалами Инфостарта не помогло — не нашел подходящего решения. Пришлось самому придумывать алгоритм. Получившийся инструмент показался мне полезным — потому решил поделиться ним.
Алгоритм: находим наибольшую общую подстроку двух строк (с помощью суффиксных автоматов http://e-maxx.ru/algo/suffix_automata) — получается что каждая строка разбита на 3 части: левая (еще не обработанная), средняя (это наибольшая общая подстрока) и правая (не обработанная). Левую и правую части обрабатываем таким же образом до тех пор, пока не сможем получить общую подстроку — в таком случае подстроки различны. В итоге получаем чередование совпадающих и не совпадающих подстрок.
Алгоритм выполнен без рекурсии — т.е. подходит для обработки больших строк.
Дополнительно для увеличения наглядности добавил вывод в html.
PS: если снова изобрел велосипед — прошу прощения за невнимательность.
Related Posts
Получение логина и пароля техподдержки 1С из базы
Класс для вывода отчета в Excel
Счет-фактура для УПП
Библиотека классов для создания внешней компоненты 1С на C#- Акт об оказании услуг (со скидками) — внешняя печатная форма для Управление торговлей 11.1.10.86
Прайс-лист с артикулом в отдельной колонке
Очень интересно!
И построение суффиксного автомата на 1С запрограммировано. А это действительно сложный и нужный алгоритм. Его реализация и без обертки внешнего алгоритма имеет самостоятельное значение. — Замечательно!
А быстродействие замеряли? — Как насчет действительно больших строк (например, миллион символов)?
Можно ли применять для сравнения текстов модулей до и после изменений?
В чем отличие от алгоритма (наибольшая общая подпоследовательность)?
Нет ли проблем неоднозначности (если одновременно нашлись в разных местах две наибольших совпадающих последовательности одинаковой длины)?
(1) ildarovich, быстродействие не замерял. Теоретически, отличия от алгоритма Diff в асимптотическом время работы алгоритма: Diff — O(n1*n2), суффиксные автоматы — O(n1+n2). Однако многое зависит от реализации.
С трудом могу себе представить, где может быть использовано сравнение строк в цикле — это скорее разовая задача, хотя я могу ошибаться, поэтому существенной оптимизации и работы по поиску наиболее быстрого алгоритма не проводил. Остановился на алгоритме с хорошей зависимостью времени выполнения от объема данных. На протяжении полугода использования нареканий по скорости не было.
Алгоритм хорошо себя показывает на родственных строках, в которых внесен небольшой шум.
Проблема неоднозначности в общем случае присутствует, однако для конкретного применения — проблема редко встречается. Для текстов модулей проблема неоднозначности становится слишком серьезной — сравнение получается некрасивым. Возможно внесение дополнительных эвристик сделает этот алгоритм вполне конкурентоспособным и для сравнения модулей.
(2) Ну таких задач много, навскидку базы всяких рефератов, статей и т.д.
Круто!!!
Отдельно спасибо за ссылку на суффиксные автоматы
Зачетно!
Пригодится на досуге.
какой там велосипед?! -))
очень здорово.
Мир этому дому!
Отлично! Будет время, обязательно для себя разберусь с алгоритмом и теорией суффиксных автоматов. Автору большое спасибо!
На мой взгляд правильнее выделять отдельные слова в отличии нежели отдельные части. К примеру, для 2,1 и 1,6 необходимо показать отличие целиком в числах нежели выделять отдельные цифры 2 и 6.
Для таких вещей в принципе достаточно использовать метод шинглов. Работает он быстрее и проще, к тому же есть возможность настраивать уровень сравнения (шаг шингла). Единственная проблема, скорее проблема 1С, а не алгоритма — это отсутствие метода получения значения hash, md5.
(8) ivanov660, изначально этот алгоритм разрабатывался для сравнения названий номенклатуры. В целевой базе наименования довольно длинные и очень разнообразные — выделение различных слов приводит с сокращению размерности задачи — сравнению не всего названия, а нескольких слов, однако это все еще затруднительно делать глазами.
Хорошей идеей будет совместить Ваше предложение — выделение отличных слов — с моим алгоритмом — в каждой паре различных слов выделить отличные символы.
Однако и здесь возникает масса вопросов, например — если в исходной строке одно слово а на его месте в другой строке три слова, как быть?
А какие отличия от 1С встроенного СравнениеФайлов ?
Кроме настроек которые есть в 1С
1. Игнорировать пустое пространство
2. Учитывать регистр
3. Учитывать различия в разделителях строк
(10) kiruha, можно сказать, что в СравнениеФайлов единица сравнения — абзац, здесь — символ.
Если бы СравнениеФайлов детализировала отличия до символа — не имело бы смысла делать эту обработку.
Здесь все-таки основная задача сравнить 2 строки и показать конкретные различия, а не столько сам факт различия.
(11)
Ок, спасибо, понятно — то же хорошо бы в публикации объяснить
(8) ivanov660, в 8.3+ появилась возможность на уровне платформы получать разнообразные хеши…
Велосипед, но зачетный. Автору, в любом случае, спасибо. Как дополнительная опция к стандартным — подойдет.
Замечена не очень корректная работа обработки (((
При
1 >Строка1 = «Оттмеченные»
2 >Строка2 = «Отмеченые»
Результат
1 >Отмеченыеные
2 >Отмеченые
Если поменять строки местами, все вроде работает.
Лучшая подстрока = «Отмечен» не существует в первой строке.
Вышеуказанный алгоритм находит не наибольшую общую подстроку двух строк, а наибольшую последовательность символов.
Я тут имел смелость (наглость?) дополнить авторскую обработку для решения этой задачи. Если найденная последовательность не является подстрокой, вызывается другой (не столь эффективный) алгоритм.