gifts2017

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

Опубликовал Яков Коган (Yashazz) в раздел Программирование - Практика программирования

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

Понадобилось мне 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. Yura Yura (YuraLu) 20.02.13 06:13
Спасибо. Только недавно была нужна подобная фишка. Обз... прикручу!
2. Сергей (ildarovich) 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
alevnev; unichkin; miller-adm; andrey-prog; yandextesting; bulpi; +6 Ответить 2
3. Сергей (ildarovich) 20.02.13 13:50
Может быть, данный пример заставит Вас изменить свое мнение по вопросу комментария?
4. Яков Коган (Yashazz) 20.02.13 14:25
(2) Ну, вариант с посимвольным - неинтересно, а вот дихотомия да, изящна. Вы, часом, на Perl'е не работали? :)
По времени наши варианты практически одинаковы, замерено; в среднем, Ваш чуть-чуть быстрее.

Мнение насчёт комментария - нет, не изменит. Код должен быть читабелен и управляем. Компактность - лютое эстетство, отнюдь не всегда нужное.
Так что меряться количеством строк кода - дело бесползеное. Можно вообще всё в одну строку вытянуть, верно? Только вот пониманию и отладке это не способствует.
5. bulpi bulpi (bulpi) 20.02.13 17:10
Варианты (2) не только компактней, но и понятней. А также доставляют эстетическое удовольствие, что немаловажно в нашем унылом мире :)
6. Сергей (ildarovich) 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) 20.02.13 21:21
(6) Короче, ага. Только вот тогда ещё и эта функция нужна всюду.
Вообще, я хорошо понимаю, что такое эстетика кода, лаконичность и прочее, иногда трачу изрядное время лишь на сокращение и "вылизывание" решения, просто у нас с Вами разные взгляды на конкретно такие вещи. Вот, например, с запросами замыканием я целиком согласен, сам нечто подобное делал и Вашими идеями пользуюсь, но насчёт создания таблицы значений мы расходимся. Ну вот не нравится мне такое. Массив так объявить ещё куда ни шло, а объявления типов, заголовки, ширины? Мне бывает надо; тогда вызов Вашей функции или недостаточен, или распухает в не менее уродливые переносы на несколько строк.
А что моё решение не самое красивое, а ваше - более стильное, не спорю; хорошо, что спровоцировал такие находки.
8. Alexandr (maloi_a) 26.06.13 09:26
В ветку "разницы вообще нет" добавьте:

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

Иначе значение реквизит "ЕстьРазница" неопределено.
9. vn agapov (vnagapov) 26.06.13 10:01
А что такое дихотомический обход?
10. Сергей (ildarovich) 05.05.14 13:25
Кстати, вызванные данной статьей размышления над этой задачей и ее решением привели к мысли использовать тот же метод уже не для сравнения строк, а для сравнения движений документов в двух базах. В результате получился вот такой очень быстрый и полезный на практике отчет Компаратор оборотов в информационных базах.За это еще одно спасибо.
11. Олег Мэйер (meier8th) 05.05.14 13:43
12. John Smith (PiccaHut001) 07.10.14 18:50
(0) Тоже не понял, зачем так извращаться. Булевого Строка1=Строка2 достаточно. самый изящный код
13. Сергей (ildarovich) 07.10.14 22:17
(12) PiccaHut001, результат сравнения здесь показывает не просто "равно-не равно", а где равно, а где не равно, то есть показывает, например, все интервалы позиций равенства символов в двух строках. Например, кто-то что-то изменил в длинной строке, как найти место изменений. Посимвольное сравнение - долгое, а если сравнивать большие куски строк, то будет быстрее.
14. John Smith (PiccaHut001) 08.10.14 10:35
(13) ildarovich, Всё равно не понятно, как в 1С эту функцию можно использовать.
15. Сергей (ildarovich) 08.10.14 10:57
(14) PiccaHut001, ну это лучше у автора спрашивать. Ну а меня это натолкнуло на идею быстро сравнивать таким образом обороты по счетам или регистрам в двух разных базах(отчет "Компаратор оборотов в информационных базах"). Впрочем, я об этом уже говорил в комментарии (10).
16. Ivon (Ivon) 15.03.16 12:01
(3) ildarovich, Не надейтесь. У Yashazz явно завышенное самомнение при знаниях чуть выше среднего. Зато ... в комментариях - это у него просто талант. Кстати, читабельностью, в чем вас упрекнул сей автор, код автора так же не блещет, судя по тому, что я видел в его публикациях.
17. Яков Коган (Yashazz) 17.03.16 00:50
(16) Ivon, ага, такое завышенное самомнение у человека, который в каждой третьей публикации вообще сомневается, стоило ли выкладывать... Который про одну свою недавнюю публично написал "пардон, баян". Почитайте мои высказывания, ага: http://infostart.ru/public/447333/ Всем бы такое завышенное)))
Для написания сообщения необходимо авторизоваться
Прикрепить файл
Дополнительные параметры ответа