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

16.05.2017 15 Comments

Практика программирования, Разработка

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

Понадобилось мне 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);

 

Related Posts

15 Comments

  1. YuraLu

    Спасибо. Только недавно была нужна подобная фишка. Обз… прикручу!

    Reply ↓
  2. ildarovich

    Чересчур громоздкое решение. Вот мой вариант без дихотомии (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));
Возврат Ответ
КонецФункции

    Показать

    Reply ↓
  3. ildarovich

    Может быть, данный пример заставит Вас изменить свое мнение по вопросу комментария?

    Reply ↓
  4. Yashazz

    (2) Ну, вариант с посимвольным — неинтересно, а вот дихотомия да, изящна. Вы, часом, на Perl’е не работали? 🙂

    По времени наши варианты практически одинаковы, замерено; в среднем, Ваш чуть-чуть быстрее.

    Мнение насчёт комментария — нет, не изменит. Код должен быть читабелен и управляем. Компактность — лютое эстетство, отнюдь не всегда нужное.

    Так что меряться количеством строк кода — дело бесползеное. Можно вообще всё в одну строку вытянуть, верно? Только вот пониманию и отладке это не способствует.

    Reply ↓
  5. bulpi

    Варианты (2) не только компактней, но и понятней. А также доставляют эстетическое удовольствие, что немаловажно в нашем унылом мире 🙂

    Reply ↓
  6. ildarovich

    (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 символа — очень много. Это несколько анекдотов типа «повторение — мать заикания».

    В первом варианте имена создаваемых колонок рядом, как на самом деле в таблице, не нужно тратить воображение на транспонирование ее шапки.

    Извините за занудство, это была еще одна попытка перетащить Вас в свой лагерь любителей краткости.

    Reply ↓
  7. Yashazz

    (6) Короче, ага. Только вот тогда ещё и эта функция нужна всюду.

    Вообще, я хорошо понимаю, что такое эстетика кода, лаконичность и прочее, иногда трачу изрядное время лишь на сокращение и «вылизывание» решения, просто у нас с Вами разные взгляды на конкретно такие вещи. Вот, например, с запросами замыканием я целиком согласен, сам нечто подобное делал и Вашими идеями пользуюсь, но насчёт создания таблицы значений мы расходимся. Ну вот не нравится мне такое. Массив так объявить ещё куда ни шло, а объявления типов, заголовки, ширины? Мне бывает надо; тогда вызов Вашей функции или недостаточен, или распухает в не менее уродливые переносы на несколько строк.

    А что моё решение не самое красивое, а ваше — более стильное, не спорю; хорошо, что спровоцировал такие находки.

    Reply ↓
  8. maloi_a

    В ветку «разницы вообще нет» добавьте:

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

    Иначе значение реквизит «ЕстьРазница» неопределено.

    Reply ↓
  9. vnagapov

    А что такое дихотомический обход?

    Reply ↓
  10. ildarovich

    Кстати, вызванные данной статьей размышления над этой задачей и ее решением привели к мысли использовать тот же метод уже не для сравнения строк, а для сравнения движений документов в двух базах. В результате получился вот такой очень быстрый и полезный на практике отчет Компаратор оборотов в информационных базах.За это еще одно спасибо.

    Reply ↓
  11. meier8th

    что за дихотомия? о.О

    Reply ↓
  12. ildarovich

    (12) PiccaHut001, результат сравнения здесь показывает не просто «равно-не равно», а где равно, а где не равно, то есть показывает, например, все интервалы позиций равенства символов в двух строках. Например, кто-то что-то изменил в длинной строке, как найти место изменений. Посимвольное сравнение — долгое, а если сравнивать большие куски строк, то будет быстрее.

    Reply ↓
  13. PiccaHut001

    (13) ildarovich, Всё равно не понятно, как в 1С эту функцию можно использовать.

    Reply ↓
  14. ildarovich

    (14) PiccaHut001, ну это лучше у автора спрашивать. Ну а меня это натолкнуло на идею быстро сравнивать таким образом обороты по счетам или регистрам в двух разных базах(отчет «Компаратор оборотов в информационных базах»). Впрочем, я об этом уже говорил в комментарии (10).

    Reply ↓
  15. Yashazz

    (16) Ivon, ага, такое завышенное самомнение у человека, который в каждой третьей публикации вообще сомневается, стоило ли выкладывать… Который про одну свою недавнюю публично написал «пардон, баян». Почитайте мои высказывания, ага: http://infostart.ru/public/447333/ Всем бы такое завышенное)))

    Reply ↓

Leave a Comment

Ваш адрес email не будет опубликован. Обязательные поля помечены *