Сравнение двух строк. Функция

19.02.13

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

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

Понадобилось мне 2 строки сравнить и определить, какие в них фрагменты совпадают, а какие различаются. Для удобства привёл строки к одной длине. Впрочем, при желании любые 2 строки можно порубать так, чтобы сравнивать как имеющие одинаковую длину. Ну и ничего, кроме хитрых регулярных выражений да посимвольного перебора не нашёл. RegExp не удалось припахать к выдаче результата в нужном мне виде (возможно, мои руки кривы), а посимвольно обходить длинные строки не хотелось. В итоге сделал эту, авось кому пригодится.




Функция ПолучитьРазличияДвухСтрок(Знач стро1,Знач стро2,тф=Неопределено,Знач рДельта=0)

    Если
тф=Неопределено Тогда

       
// это первая итерация, инициализируемся

       
рМаксДлина=0;

       
// результаты вернём в таблице значений, фиксирующей фрагменты: № начсим, № консим, ЕстьРазница (булево)

       
тф=Новый ТаблицаЗначений;

       
тф.Колонки.Добавить("Начало");

       
тф.Колонки.Добавить("Конец");

       
тф.Колонки.Добавить("ЕстьРазница");

        Если
стро1=стро2 Тогда // разницы вообще нет

           
стротф=тф.Добавить();

           
стротф.Начало=1;

           
стротф.Конец=СтрДлина(стро2);

            Возврат
тф;

        Иначе

           
рДлина1=СтрДлина(стро1);

           
рДлина2=СтрДлина(стро2);

            Если
рДлина1<>рДлина2 Тогда // можно обрезать под одну длину, можно и отказаться

               
рМинДлина=Мин(рДлина1,рДлина2);

               
рМаксДлина=Макс(рДлина1,рДлина2);

                Если
рМинДлина=рДлина1 Тогда стро2=Лев(стро2,рМинДлина) КонецЕсли;

                Если
рМинДлина=рДлина2 Тогда стро1=Лев(стро1,рМинДлина) КонецЕсли;

            КонецЕсли;

        КонецЕсли;

       
// заполним дихотомически

       
ПолучитьРазличияДвухСтрок(стро1,стро2,тф);

       
// дообработаем разницу длин, если она была, дописав "хвост" более длинной строки

       
Если рМаксДлина<>0 Тогда

           
стротф=тф.Добавить();

           
стротф.Начало=рМинДлина+1;

           
стротф.Конец=рМаксДлина;

           
стротф.ЕстьРазница=Истина; // априорно

       
КонецЕсли;

       
// грубо свернём (такая таблица никогда не будет очень большой, поэтому можно не изощряться)

       
тф2=тф.СкопироватьКолонки(); старЕР=Неопределено; старНачало=0; старКонец=0;

        Для каждого
стротф Из тф Цикл

            Если
старЕР<>стротф.ЕстьРазница Тогда

                Если
старЕР<>Неопределено Тогда // закончим предыдущую

                   
стротф2=тф2.Добавить();

                   
стротф2.Начало=старНачало;

                   
стротф2.Конец=старКонец;

                   
стротф2.ЕстьРазница=старЕР;

                КонецЕсли;

               
старЕР=стротф.ЕстьРазница;

               
старНачало=стротф.Начало;

            КонецЕсли;

           
старКонец=стротф.Конец;

        КонецЦикла;

        Если
старЕР<>Неопределено Тогда // закончим предыдущую

           
стротф2=тф2.Добавить();

           
стротф2.Начало=старНачало;

           
стротф2.Конец=старКонец;

           
стротф2.ЕстьРазница=старЕР;

        КонецЕсли;

        Возврат
тф2;

    Иначе

       
// собственно рекурсивное сравнение строк

       
этстро=стро1; // строка-эталон

       
обрстро=стро2; // обрабатываемая строка

       
пози=Цел(СтрДлина(обрстро)/2);

        Если
пози=0 Тогда Возврат "" КонецЕсли; // ненормальная ситуация

       
кусэт1=Лев(этстро,пози);

       
кусэт2=Сред(этстро,пози+1);

       
кусобр1=Лев(обрстро,пози);

       
кусобр2=Сред(обрстро,пози+1);

       
изм1=(кусэт1<>кусобр1);

       
изм2=(кусэт2<>кусобр2);

       
// смотрим первый кусок

       
Если не изм1 Тогда

           
стротф=тф.Добавить();

           
стротф.Начало=?(рДельта=0,1,рДельта);

           
стротф.Конец=стротф.Начало+СтрДлина(кусобр1)-1;

           
стротф.ЕстьРазница=Ложь;

        Иначе
// эта часть различна, идём дальше, обрабатывая её как отдельную строку

           
рНачало=?(рДельта=0,1,рДельта);

           
рКонец=рНачало+СтрДлина(кусобр1)-1;

            Если
рНачало=рКонец Тогда // финальная фаза, 1 символ разницы

               
стротф=тф.Добавить();

               
стротф.Начало=рНачало;

               
стротф.Конец=рКонец;

               
стротф.ЕстьРазница=Истина;

            Иначе

               
ПолучитьРазличияДвухСтрок(кусэт1,кусобр1,тф,рДельта);

            КонецЕсли;

        КонецЕсли;

       
// смотрим второй кусок

       
рДельта=(пози+1)+рДельта-?(рДельта=0,0,1);

        Если не
изм2 Тогда

           
стротф=тф.Добавить();

           
стротф.Начало=рДельта;

           
стротф.Конец=стротф.Начало+СтрДлина(кусобр2)-1;

           
стротф.ЕстьРазница=Ложь;

        Иначе
// эта часть различна, идём дальше, обрабатывая её как отдельную строку

           
рНачало=рДельта;

           
рКонец=рНачало+СтрДлина(кусобр2)-1;

            Если
рНачало=рКонец Тогда // финальная фаза, 1 символ разницы

               
стротф=тф.Добавить();

               
стротф.Начало=рНачало;

               
стротф.Конец=рКонец;

               
стротф.ЕстьРазница=Истина;

            Иначе

               
ПолучитьРазличияДвухСтрок(кусэт2,кусобр2,тф,рДельта);

            КонецЕсли;

        КонецЕсли;

       
// ничего не возвращаем, результат не важен

   
КонецЕсли;

КонецФункции




Пример вызова:
тф=ПолучитьРазличияДвухСтрок(строка1,строка2);

 

См. также

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

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

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

1 стартмани

18.03.2024    2669    0    John_d    8    

54

GUID в 1С 8.3 - как с ними быть

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

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

12.02.2024    4604    atdonya    22    

45

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

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

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

30.11.2023    3960    ke.92@mail.ru    16    

61

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

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

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

28.08.2023    8816    YA_418728146    6    

141

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

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

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

2 стартмани

22.08.2023    2071    21    progmaster    7    

3

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

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

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

1 стартмани

13.10.2022    16143    133    sapervodichka    112    

129

Система контроля ведения учета [БСП]

Универсальные функции Механизмы типовых конфигураций БСП (Библиотека стандартных подсистем) Платформа 1С v8.3 Конфигурации 1cv8 Бесплатно (free)

В данном материале рассмотрим типовой алгоритм подсистемы контроля учета БСП в конфигурациях на примерах.

18.07.2022    7243    quazare    8    

109
Комментарии
В избранное Подписаться на ответы Сортировка: Древо развёрнутое
Свернуть все
1. YuraLu 20.02.13 06:13 Сейчас в теме
Спасибо. Только недавно была нужна подобная фишка. Обз... прикручу!
2. ildarovich 7850 20.02.13 13:30 Сейчас в теме
Чересчур громоздкое решение. Вот мой вариант без дихотомии (15 строк):
Функция ТаблицаСравненияСтрок_(С1, С2) Экспорт
	Ответ = Новый ТаблицаЗначений; //Ответ = НоваяТаблицаЗначений("От, До, ОК");
	Ответ.Колонки.Добавить("От");
	Ответ.Колонки.Добавить("До"); 
	Ответ.Колонки.Добавить("ОК");  
	ЗаполнитьЗначенияСвойств(Ответ.Добавить(), Новый Структура("От, ОК", 1, Сред(С1, 1, 1) = Сред(С2, 1, 1)));
	Для ё = 2 По Макс(СтрДлина(С1), СтрДлина(С2)) Цикл
		Если Ответ[0].ОК <> (Сред(С1, ё, 1) = Сред(С2, ё, 1)) Тогда
			ЗаполнитьЗначенияСвойств(Ответ.Вставить(0), Новый Структура("От, ОК", ё, НЕ Ответ[1].ОК));                            
			Ответ[1].До = ё - 1
		КонецЕсли		
	КонецЦикла;
	Ответ[0].До = Макс(СтрДлина(С1), СтрДлина(С2));
	Возврат Ответ
КонецФункции
Показать

Вот мой вариант с рекурсией и дихотомией (19 строк)
Процедура РазДва(Ответ, С1, С2, От, До)
	Если От + 2 > До И (Сред(С1, От, 1) = Сред(С2, От, 1)) <> (Сред(С1, До, 1) = Сред(С2, До, 1)) Тогда
		ЗаполнитьЗначенияСвойств(Ответ.Вставить(0), Новый Структура("От, ОК", До, НЕ Ответ[1].ОК));
		Ответ[1].До = От
	ИначеЕсли  От + 1 < До И Сред(С1, От, До - От + 1) <> Сред(С2, От, До - От + 1) Тогда
		РазДва(Ответ, С1, С2, От, Цел((От + До) / 2));
		РазДва(Ответ, С1, С2, Цел((От + До) / 2), До)	
	КонецЕсли
КонецПроцедуры
Функция ТаблицаСравненияСтрок(С1, С2) Экспорт
	Ответ = Новый ТаблицаЗначений;
	Ответ.Колонки.Добавить("От");
	Ответ.Колонки.Добавить("До");
	Ответ.Колонки.Добавить("ОК");
	ЗаполнитьЗначенияСвойств(Ответ.Добавить(), Новый Структура("От, ОК", 1, Сред(С1, 1, 1) = Сред(С2, 1, 1)));
	РазДва(Ответ, С1, С2, 1, Макс(СтрДлина(С1), СтрДлина(С2)));
	Ответ[0].До = Макс(СтрДлина(С1), СтрДлина(С2));
	Возврат Ответ
КонецФункции
Показать
Прикрепленные файлы:
СравнениеСтрок.erf
jaroslav.h; alevnev; unichkin; miller-adm; andrey-prog; yandextesting; bulpi; +7 Ответить
4. Yashazz 4709 20.02.13 14:25 Сейчас в теме
(2) Ну, вариант с посимвольным - неинтересно, а вот дихотомия да, изящна. Вы, часом, на Perl'е не работали? :)
По времени наши варианты практически одинаковы, замерено; в среднем, Ваш чуть-чуть быстрее.

Мнение насчёт комментария - нет, не изменит. Код должен быть читабелен и управляем. Компактность - лютое эстетство, отнюдь не всегда нужное.
Так что меряться количеством строк кода - дело бесползеное. Можно вообще всё в одну строку вытянуть, верно? Только вот пониманию и отладке это не способствует.
6. ildarovich 7850 20.02.13 18:34 Сейчас в теме
(4) На примере Вашей же задачи (кстати, спасибо за нее) применение функции НоваяТаблицаЗначений дает экономию три строки. Число строк в решении тогда становится волшебным (для программистов) числом 16. Вторая функция при этом будет выглядеть так
Функция ТаблицаСравненияСтрок(С1, С2) Экспорт
    Ответ = НоваяТаблицаЗначений("От, До, ОК");
    ЗаполнитьЗначенияСвойств(Ответ.Добавить(), Новый Структура("От, ОК", 1, Сред(С1, 1, 1) = Сред(С2, 1, 1)));
    РазДва(Ответ, С1, С2, 1, Макс(СтрДлина(С1), СтрДлина(С2)));
    Ответ[0].До = Макс(СтрДлина(С1), СтрДлина(С2));
    Возврат Ответ
КонецФункции
Неужели Вы считаете более понятным, наглядным, упрощающим отладку вариант
Функция ТаблицаСравненияСтрок(С1, С2) Экспорт
    Ответ = Новый ТаблицаЗначений;
    Ответ.Колонки.Добавить("От");
    Ответ.Колонки.Добавить("До");
    Ответ.Колонки.Добавить("ОК");
    ЗаполнитьЗначенияСвойств(Ответ.Добавить(), Новый Структура("От, ОК", 1, Сред(С1, 1, 1) = Сред(С2, 1, 1)));
    РазДва(Ответ, С1, С2, 1, Макс(СтрДлина(С1), СтрДлина(С2)));
    Ответ[0].До = Макс(СтрДлина(С1), СтрДлина(С2));
    Возврат Ответ
КонецФункции
Показать
В нем полно воды! Три совершенно не информативных, избыточных строчки, 72 символа, которые отнимают Ваше внимание, на которые Вы никогда не поставите точки останова в отладчике. Как я уже говорил в комментариях в той статье, 72 символа - очень много. Это несколько анекдотов типа "повторение - мать заикания".
В первом варианте имена создаваемых колонок рядом, как на самом деле в таблице, не нужно тратить воображение на транспонирование ее шапки.
Извините за занудство, это была еще одна попытка перетащить Вас в свой лагерь любителей краткости.
7. Yashazz 4709 20.02.13 21:21 Сейчас в теме
(6) Короче, ага. Только вот тогда ещё и эта функция нужна всюду.
Вообще, я хорошо понимаю, что такое эстетика кода, лаконичность и прочее, иногда трачу изрядное время лишь на сокращение и "вылизывание" решения, просто у нас с Вами разные взгляды на конкретно такие вещи. Вот, например, с запросами замыканием я целиком согласен, сам нечто подобное делал и Вашими идеями пользуюсь, но насчёт создания таблицы значений мы расходимся. Ну вот не нравится мне такое. Массив так объявить ещё куда ни шло, а объявления типов, заголовки, ширины? Мне бывает надо; тогда вызов Вашей функции или недостаточен, или распухает в не менее уродливые переносы на несколько строк.
А что моё решение не самое красивое, а ваше - более стильное, не спорю; хорошо, что спровоцировал такие находки.
5. bulpi 215 20.02.13 17:10 Сейчас в теме
Варианты (2) не только компактней, но и понятней. А также доставляют эстетическое удовольствие, что немаловажно в нашем унылом мире :)
3. ildarovich 7850 20.02.13 13:50 Сейчас в теме
Может быть, данный пример заставит Вас изменить свое мнение по вопросу комментария?
16. Ivon 673 15.03.16 12:01 Сейчас в теме
(3) ildarovich, Не надейтесь. У Yashazz явно завышенное самомнение при знаниях чуть выше среднего. Зато ... в комментариях - это у него просто талант. Кстати, читабельностью, в чем вас упрекнул сей автор, код автора так же не блещет, судя по тому, что я видел в его публикациях.
17. Yashazz 4709 17.03.16 00:50 Сейчас в теме
(16) Ivon, ага, такое завышенное самомнение у человека, который в каждой третьей публикации вообще сомневается, стоило ли выкладывать... Который про одну свою недавнюю публично написал "пардон, баян". Почитайте мои высказывания, ага: http://infostart.ru/public/447333/ Всем бы такое завышенное)))
8. maloi_a 26.06.13 09:26 Сейчас в теме
В ветку "разницы вообще нет" добавьте:

стротф.ЕстьРазница=Ложь;

Иначе значение реквизит "ЕстьРазница" неопределено.
9. vnagapov 26.06.13 10:01 Сейчас в теме
А что такое дихотомический обход?
10. ildarovich 7850 05.05.14 13:25 Сейчас в теме
Кстати, вызванные данной статьей размышления над этой задачей и ее решением привели к мысли использовать тот же метод уже не для сравнения строк, а для сравнения движений документов в двух базах. В результате получился вот такой очень быстрый и полезный на практике отчет Компаратор оборотов в информационных базах.За это еще одно спасибо.
11. meier8th 05.05.14 13:43 Сейчас в теме
12. PiccaHut001 07.10.14 18:50 Сейчас в теме
(0) Тоже не понял, зачем так извращаться. Булевого Строка1=Строка2 достаточно. самый изящный код
13. ildarovich 7850 07.10.14 22:17 Сейчас в теме
(12) PiccaHut001, результат сравнения здесь показывает не просто "равно-не равно", а где равно, а где не равно, то есть показывает, например, все интервалы позиций равенства символов в двух строках. Например, кто-то что-то изменил в длинной строке, как найти место изменений. Посимвольное сравнение - долгое, а если сравнивать большие куски строк, то будет быстрее.
14. PiccaHut001 08.10.14 10:35 Сейчас в теме
(13) ildarovich, Всё равно не понятно, как в 1С эту функцию можно использовать.
15. ildarovich 7850 08.10.14 10:57 Сейчас в теме
(14) PiccaHut001, ну это лучше у автора спрашивать. Ну а меня это натолкнуло на идею быстро сравнивать таким образом обороты по счетам или регистрам в двух разных базах(отчет "Компаратор оборотов в информационных базах"). Впрочем, я об этом уже говорил в комментарии (10).
18. webstep 9 16.09.21 15:29 Сейчас в теме
Код некорректен. "Степанов" и "Степнов" дает ошибку на все буквы после "Степ", хотя разница состоит всего в одной пропущенной букве.
Оставьте свое сообщение