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

Опубликовал 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);

 

См. также

Лучшие комментарии

2. ildarovich 20.02.2013 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));
	Возврат Ответ
КонецФункции
...Показать Скрыть
Ответили: (4) (5)
# Ответить
3. ildarovich 20.02.2013 13:50
Может быть, данный пример заставит Вас изменить свое мнение по вопросу комментария?
Ответили: (16)
+ 1 [ Ivon; ]
# Ответить

Комментарии

1. YuraLu 20.02.2013 06:13
Спасибо. Только недавно была нужна подобная фишка. Обз... прикручу!
# Ответить
2. ildarovich 20.02.2013 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));
	Возврат Ответ
КонецФункции
...Показать Скрыть
Ответили: (4) (5)

Прикрепленные файлы:

СравнениеСтрок.erf
# Ответить
3. ildarovich 20.02.2013 13:50
Может быть, данный пример заставит Вас изменить свое мнение по вопросу комментария?
Ответили: (16)
+ 1 [ Ivon; ]
# Ответить
4. Yashazz 20.02.2013 14:25
(2) Ну, вариант с посимвольным - неинтересно, а вот дихотомия да, изящна. Вы, часом, на Perl'е не работали? :)
По времени наши варианты практически одинаковы, замерено; в среднем, Ваш чуть-чуть быстрее.

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

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

Иначе значение реквизит "ЕстьРазница" неопределено.
# Ответить
9. vnagapov 26.06.2013 10:01
А что такое дихотомический обход?
# Ответить
10. ildarovich 05.05.2014 13:25
Кстати, вызванные данной статьей размышления над этой задачей и ее решением привели к мысли использовать тот же метод уже не для сравнения строк, а для сравнения движений документов в двух базах. В результате получился вот такой очень быстрый и полезный на практике отчет Компаратор оборотов в информационных базах.За это еще одно спасибо.
Ответили: (15)
# Ответить
11. meier8th 05.05.2014 13:43
что за дихотомия? о.О
# Ответить
12. PiccaHut001 07.10.2014 18:50
(0) Тоже не понял, зачем так извращаться. Булевого Строка1=Строка2 достаточно. самый изящный код
Ответили: (13)
− 1 [ MaxDavid; ]
# Ответить
13. ildarovich 07.10.2014 22:17
(12) PiccaHut001, результат сравнения здесь показывает не просто "равно-не равно", а где равно, а где не равно, то есть показывает, например, все интервалы позиций равенства символов в двух строках. Например, кто-то что-то изменил в длинной строке, как найти место изменений. Посимвольное сравнение - долгое, а если сравнивать большие куски строк, то будет быстрее.
Ответили: (14)
# Ответить
14. PiccaHut001 08.10.2014 10:35
(13) ildarovich, Всё равно не понятно, как в 1С эту функцию можно использовать.
Ответили: (15)
# Ответить
15. ildarovich 08.10.2014 10:57
(14) PiccaHut001, ну это лучше у автора спрашивать. Ну а меня это натолкнуло на идею быстро сравнивать таким образом обороты по счетам или регистрам в двух разных базах(отчет "Компаратор оборотов в информационных базах"). Впрочем, я об этом уже говорил в комментарии (10).
# Ответить
16. Ivon 15.03.2016 12:01
(3) ildarovich, Не надейтесь. У Yashazz явно завышенное самомнение при знаниях чуть выше среднего. Зато ... в комментариях - это у него просто талант. Кстати, читабельностью, в чем вас упрекнул сей автор, код автора так же не блещет, судя по тому, что я видел в его публикациях.
Ответили: (17)
# Ответить
17. Yashazz 17.03.2016 00:50
(16) Ivon, ага, такое завышенное самомнение у человека, который в каждой третьей публикации вообще сомневается, стоило ли выкладывать... Который про одну свою недавнюю публично написал "пардон, баян". Почитайте мои высказывания, ага: http://infostart.ru/public/447333/ Всем бы такое завышенное)))
# Ответить
Внимание! За постинг в данном форуме $m не начисляются.
Внимание! Для написания сообщения необходимо авторизоваться
Текст сообщения*
Прикрепить файл