Задача сравнения похожих строк встречается на практике довольно часто: лично я недавно столкнулся с ней при попытке импорта почтовых адресов из одной программы в другую.
Например, один адрес может выглядеть как «Тверская обл., Кашин г, Советская ул, 1, 5», а другой – как «Тверская область; город Кашин; улица Советская; дом 1; квартира 5». Похожи ли эти строки и насколько? Несомненно, похожи. И «невооруженным глазом» видна их структура: область – населенный пункт – улица – дом – квартира. Логично, что для адресов важно такое разбиение строк на группы; то есть сравнивать мы должны не «две каши» из сходных слов (где одна «каша» состоит из слов первой строки, а вторая – из слов второй), а именно осуществлять «погруппное» сравнение слов из первой строки со словами из второй. Просматривается и критерий разбиения на группы: в первой строке разделителем групп является «, », а во второй – «; ».
В то же время есть строки, где никакого явного разбиения на группы не просматривается. Например, возьмем «классику»: «Когда в товарищах согласья нет, на лад их дело не пойдет, и выйдет из него не дело — только мука.» И вторая строка: «Проказница мартышка, Осел, Козел да косолапый Мишка затеяли сыграть квартет.» Явно строки разные (и даже мораль у этих басен разная, хотя параллели и можно найти ).
Рассматриваемая задача не нова. Существуют алгоритмы (порой весьма сложные), которые пытаются решить ее, и даже иногда успешно решают. Я предлагаю в копилку алгоритмов еще один. При его составлении я исходил из следующих принципов:
- простота вызова функции сравнения;
- простота реализации;
- достаточная универсальность.
Кроме того, алгоритм реализован на VBA Excel, поэтому он очень «демократичный», и его можно применять повсеместно: Excel не только существует среди программного обеспечения самых разных компьютеров «сам по себе», но и в него экспортируются данные из всевозможных СУБД и приложений.
Итак, начнем.
Функцию сравнения назовем StrCompare. У нее будет 4 аргумента, два из которых необязательные: первая строка str1, вторая строка str2, разделитель групп первой строки div1 и разделитель групп второй строки div2. Если div1 либо div2 пропущены, то по умолчанию подразумевается разделитель “|”. “|” выбран потому, что он вряд ли встретится в «среднестатистической» строке, и поэтому может использоваться для сравнения монолитных (не разбиваемых на группы) строк. Подобные монолитные строки можно также считать строками, состоящими из одной группы. То есть заголовок функции сравнения выглядит так:
Public Function StrCompare(str1 As String, str2 As String, Optional div1 As String = "|", Optional div2 As String = "|") As SingleSingle – потому что результатом функции будет число, показывающее степень сходства сравниваемых строк.
Все группы строки 1 последовательно сравниваются со всеми группами строки 2 пословно, и считается количество совпадений слов в каждой паре групп. Для каждой группы строки 1 в итоге выбирается «лучшая группа» из строки 2 (то есть группа с наибольшим количеством совпадений). Совпадения для каждой пары слов проверяются по слову с минимальной длиной: то есть «улица = ул», а «г = город». Это правило не относится к числам: то есть 200<>20. При выделении слов все «незначащие символы» внутри групп как раз и являются разделителями слов, но сами они при этом игнорируются, то есть слова могут состоять только из символов WordSymbols = «0123456789АБВГДЕЁЖЗИЙКЛМНОПРСТУФХЦЧШЩЪЫЬЭЮЯABCDEFGHIJKLMNOPQRSTUVWXYZ». Понятно, что регистр символов во внимание не принимается.
Для поиска совпадающего слова в текущей группе второй строки используется быстрый метод половинного деления (но немного модернизированный по сравнению с «классическим», так как совпадения проверяются по вышеописанному способу). А поскольку для работы метода половинного деления требуются отсортированные массивы, то применяется еще и алгоритм быстрой сортировки.
Итогом работы функции StrCompare будет результат деления количества совпадающих слов на общее количество слов в строках 1 и 2:
StrCompare = (da * 2) / ((kon1_2 - nach1_2 + 1) * (kon1_1 - nach1_1 + 1) + (kon2_2 - nach2_2 + 1) * (kon2_1 - nach2_1 + 1))Здесь, например, kon1_2 – конечная граница массива 1 (массив слов, содержащихся в группах первой строки) по 2-му измерению (1-е измерение – это количество групп, а 2-е – количество слов в группе).
Настало время представить код:
'Функция "интеллектуального" сравнения двух строк. Аргументы:
'строка1, строка2, разделители1, разделители2
Public Function StrChange(str1 As String, str2 As String, Optional div1 As String = "|", Optional div2 As String = "|") As Single
WordSymbols = "0123456789АБВГДЕЁЖЗИЙКЛМНОПРСТУФХЦЧШЩЪЫЬЭЮЯABCDEFGHIJKLMNOPQRSTUVWXYZ"
Dim massiv1() As String, massiv2() As String, mass1() As String, mass2() As String, m1() As Variant, m2() As Variant 'одномерные массивы групп и двумерные массивы слов
Dim mm1() As String, mm2() As String
Dim nach1_1 As Integer, kon1_1 As Integer, nach1_2 As Integer, kon1_2 As Integer, nach2_1 As Integer, kon2_1 As Integer, nach2_2 As Integer, kon2_2 As Integer
Dim item As String, itemnumber As Integer
Dim yes As Integer, maxyes As Integer, da As Integer
Dim counter As Integer 'счетчик noname
str1 = UCase(str1): str2 = UCase(str2)
massiv1 = Split(str1, div1)
ReDim mass1(LBound(massiv1) To UBound(massiv1), 0 To 1000)
maxk = 0
counter = 0
For i = LBound(massiv1) To UBound(massiv1)
item = massiv1(i)
dlina = Len(item)
slovo = ""
NewWord = False
k = 0 'второй индекс для массива слов
For j = 1 To dlina
bukva = mid(item, j, 1)
If (InStr(1, WordSymbols, bukva) > 0) And Not NewWord Then
NewWord = True
slovo = slovo + bukva
Else
If InStr(1, WordSymbols, bukva) > 0 Then
slovo = slovo + bukva
Else
If (InStr(1, WordSymbols, bukva) = 0) And NewWord Then
NewWord = False
mass1(i, k) = slovo
If k > maxk Then maxk = k
k = k + 1
slovo = ""
End If
End If
End If
Next j
If NewWord Then
mass1(i, k) = slovo
If k > maxk Then maxk = k
End If
Next i
ReDim Preserve mass1(LBound(massiv1) To UBound(massiv1), 0 To maxk)
'*************************************************************'
massiv2 = Split(str2, div2)
ReDim mass2(LBound(massiv2) To UBound(massiv2), 0 To 1000)
maxk = 0
For i = LBound(massiv2) To UBound(massiv2)
item = massiv2(i)
dlina = Len(item)
slovo = ""
NewWord = False
k = 0 'второй индекс для массива слов
For j = 1 To dlina
bukva = mid(item, j, 1)
If (InStr(1, WordSymbols, bukva) > 0) And Not NewWord Then
NewWord = True
slovo = slovo + bukva
Else
If InStr(1, WordSymbols, bukva) > 0 Then
slovo = slovo + bukva
Else
If (InStr(1, WordSymbols, bukva) = 0) And NewWord Then
NewWord = False
mass2(i, k) = slovo
If k > maxk Then maxk = k
k = k + 1
slovo = ""
End If
End If
End If
Next j
If NewWord Then
mass2(i, k) = slovo
If k > maxk Then maxk = k
End If
Next i
ReDim Preserve mass2(LBound(massiv2) To UBound(massiv2), 0 To maxk)
' а теперь непосредственно "гибкое" сравнение строк; пример: kon1_2 - конечная граница массива 1 по 2-му измерению
nach1_1 = LBound(mass1, 1)
kon1_1 = UBound(mass1, 1)
nach1_2 = LBound(mass1, 2)
kon1_2 = UBound(mass1, 2)
nach2_1 = LBound(mass2, 1)
kon2_1 = UBound(mass2, 1)
nach2_2 = LBound(mass2, 2)
kon2_2 = UBound(mass2, 2)
For i = nach1_1 To kon1_1
For j = nach1_2 To kon1_2
If mass1(i, j) = "" Then
counter = counter + 1
mass1(i, j) = "noname" + Trim(Str(counter))
End If
'MsgBox ("mass1(" + Trim(Str(i)) + "," + Trim(Str(j)) + ")=" + mass1(i, j))
Next j
Next i
For i = nach2_1 To kon2_1
For j = nach2_2 To kon2_2
If mass2(i, j) = "" Then
counter = counter + 1
mass2(i, j) = "noname" + Trim(Str(counter))
End If
'MsgBox ("mass2(" + Trim(Str(i)) + "," + Trim(Str(j)) + ")=" + mass2(i, j))
Next j
Next i
'сортировка "внутренних массивов-групп"
ReDim m2(nach2_2 To kon2_2) As Variant
For i = nach2_1 To kon2_1
For j = nach2_2 To kon2_2
m2(j) = mass2(i, j)
Next j
Call QuickSort(m2, nach2_2, kon2_2)
For j = nach2_2 To kon2_2
mass2(i, j) = m2(j)
Next j
Next i
'а теперь непосредственно само сравнение: каждая группа строки1 сравнивается с каждой группой строки2 почленно
ReDim mm2(nach2_2 To kon2_2)
da = 0
For k = nach1_1 To kon1_1 'цикл по группам строки1
maxyes = 0
For i = nach2_1 To kon2_1 'цикл по группам строки2
yes = 0
For j = nach2_2 To kon2_2: mm2(j) = mass2(i, j): Next j 'цикл по членам конкретной группы строки2
For l = nach1_2 To kon1_2 'цикл по членам конкретной группы строки1
If BinarySearch(mm2, nach2_2, kon2_2, mass1(k, l)) <> -1 Then yes = yes + 1
Next l
If yes > maxyes Then maxyes = yes
Next i
da = da + maxyes
Next k
StrChange = (da * 2) / ((kon1_2 - nach1_2 + 1) * (kon1_1 - nach1_1 + 1) + (kon2_2 - nach2_2 + 1) * (kon2_1 - nach2_1 + 1))
'StrChange = da
End Function
Public Sub QuickSort(ByRef vArray() As Variant, inLow As Integer, inHi As Integer)
Dim pivot As Variant
Dim tmpSwap As Variant
Dim tmpLow As Integer
Dim tmpHi As Integer
tmpLow = inLow
tmpHi = inHi
pivot = vArray((inLow + inHi) 2)
While (tmpLow <= tmpHi)
While (vArray(tmpLow) < pivot And tmpLow < inHi)
tmpLow = tmpLow + 1
Wend
While (pivot < vArray(tmpHi) And tmpHi > inLow)
tmpHi = tmpHi - 1
Wend
If (tmpLow <= tmpHi) Then
tmpSwap = vArray(tmpLow)
vArray(tmpLow) = vArray(tmpHi)
vArray(tmpHi) = tmpSwap
tmpLow = tmpLow + 1
tmpHi = tmpHi - 1
End If
Wend
If (inLow < tmpHi) Then QuickSort vArray, inLow, tmpHi
If (tmpLow < inHi) Then QuickSort vArray, tmpLow, inHi
End Sub
Public Function BinarySearch(vArray() As String, inLow As Integer, inHi As Integer, key As String) As Integer
Dim lev As Integer, prav As Integer, mid As Integer
Dim key_ As String, arritem As String, arritem_ As String
Dim minlen As Integer, keylen As Integer, arritemlen As Integer
If key = Trim(Str(Val(key))) Then 'это число
lev = inLow: prav = inHi
While lev <= prav
mid = lev + (prav - lev) 2
arritem = vArray(mid)
If key < arritem Then
prav = mid - 1
ElseIf key > arritem Then
lev = mid + 1
Else
BinarySearch = mid
Exit Function
End If
Wend
Else
keylen = Len(key)
lev = inLow
prav = inHi
While lev <= prav
mid = lev + (prav - lev) 2
arritem = vArray(mid)
arritemlen = Len(arritem)
minlen = IIf(keylen < arritemlen, keylen, arritemlen)
key_ = left(key, minlen)
arritem_ = left(arritem, minlen)
If key_ < arritem_ Then
prav = mid - 1
ElseIf key_ > arritem_ Then
lev = mid + 1
Else
BinarySearch = mid
Exit Function
End If
Wend
End If
BinarySearch = -1
End FunctionКомментировать все подряд, я думаю, нет смысла: можно сориентироваться по коду. Просто проанализируем работу функции сравнения на нескольких строках разной природы.
- str1=”Тверская обл., Кашин г, Советская ул, 1, 5” str2=”Тверская область; город Кашин; улица Советская; дом 1; квартира 5”.
Сначала сравним строки без учета групп:
StrCompare(str1,str2) дает результат 0.8888889.
А теперь с учетом:
StrCompare(str1,str2,”, “,”; “) — результат 0.8.
Как видим, группы более строго относятся к сравнению; в данном случае для них важно, чтобы «дом был домом, а квартира – квартирой». При игнорировании групп это роли не играет. - str1=”Жил-был у бабушки серенький козлик” str2=”Жил-был у бабушки серый козел”
StrCompare(str1,str2) -> 0.6666667 - str1=”Иванов Иван Иванович м.р. Калуга 1950” str2=”Иванов И.И. 20.01.1950”
StrCompare(str1,str2) -> 0.6153846 - str1=”Когда в товарищах согласья нет, на лад их дело не пойдет, и выйдет из него не дело — только мука.” str2=”Проказница мартышка, Осел, Козел да косолапый Мишка затеяли сыграть квартет.”
StrCompare(str1,str2) -> 0 - str1=”В соответствии с пунктом 1 ст. 540 ГК РФ в случае, когда абонентом по договору энергоснабжения выступает гражданин, использующий энергию для бытового потребления, договор считается заключенным с момента фактического подключения абонента к сети. |Согласно части 1 статьи 153 Жилищного кодекса РФ граждане обязаны своевременно и полностью вносить плату за жилое помещение и коммунальные услуги. | В период с «____»_________2017 по «____»__________2017 Гарантирующий поставщик поставил Вам электроэнергию на сумму______________________. |В связи с нарушением Вами своих обязательств по оплате электрической энергии, что привело к образованию задолженности потребителя перед гарантирующим поставщиком в размере, более чем за 2 расчетных периода, в отношении жилого помещения Потребителя, за счет средств Гарантирующего поставщика, были произведены действия по ограничению/ возобновлению предоставления коммунальной услуги по электроснабжению.|В соответствии с пунктом 121(1) Правил предоставления коммунальных услуг собственникам и пользователям помещений в многоквартирных домах и жилых домов, утвержденных Постановлением Правительства от 06.05.2011г. №354, расходы исполнителя, связанные с введением ограничения, приостановлением и возобновлением предоставления коммунальной услуги потребителю-должнику, подлежат возмещению за счет потребителя, в отношении которого осуществлялись указанные действия.|Стоимость расходов на оплату действий по введению ограничения и последующему восстановлению электроснабжения составляет для Гарантирующего поставщика сумму ______________________________________________.|На основании вышеизложенного, ОП «ТверьАтомЭнергоСбыт» просит Вас оплатить задолженность за действия по ограничению/возобновлению предоставления коммунальной услуги по электроснабжению в размере _____________________ руб. по следующим реквизитам с указанием номера лицевого счета и назначением платежа:”
str2=”«____» __________ 2017 г. между АО «АтомЭнергоСбыт» — Гарантирующим поставщиком и _____________________ — Потребителем заключен договор энергоснабжения №___________________, сроком действия с _________________ года, с условием его дальнейшей пролонгации (пункт 8.1 договора, статья 540 Гражданского кодекса Российской Федерации), согласно пункту 1.1. которого гарантирующий поставщик обязался осуществлять продажу электрической энергии (мощности), а также самостоятельно или через привлеченных третьих лиц оказывать услуги по передаче электрической энергии и услуги, оказание которых является неотъемлемой частью процесса поставки электрической энергии потребителю, а Покупатель обязался оплачивать приобретаемую электрическую энергию (мощность). |В связи с нарушением Потребителем своих обязательств по оплате электрической энергии (п.5.2. договора энергоснабжения №__________________ от ___________), что привело к образованию задолженности потребителя перед гарантирующим поставщиком в размере, более чем за один расчетный период, в отношении объекта электросетевого хозяйства потребителя -_________________ были произведены действия по ограничению/возобновлению режима потребления энергоснабжения в соответствии с Правилами полного и (или) частичного ограничения режима потребления электрической энергии, утвержденными Постановлением Правительства РФ от 04.05.2012 г. №442 (далее – Правила). |Согласно пункту 24 Правил, потребитель обязан компенсировать исполнителю расходы на оплату действий по введению ограничения и последующему восстановлению режима потребления электрической энергии.|Стоимость расходов Гарантирующего поставщика на оплату действий по введению ограничения и последующему восстановлению режима потребления электрической энергии составляет сумму ______________________________________________.|На основании вышеизложенного, ОП «ТверьАтомЭнергоСбыт» просит Вас оплатить расходы Гарантирующего поставщика за действия по ограничению/возобновлению режима потребления электрической энергии в размере _______________ руб. по следующим реквизитам с указанием номера договора и назначением платежа:|Назначение платежа: оплата ограничения / возобновления режима потребления электрической энергии по договору №____________”
Здесь str1 и str2 – фрагменты очень схожих документов (Договоров энергоснабжения для физических и юридических лиц соответственно). Для «грубой оценки» сходства документов можно применить сравнение без групп StrCompare(str1,str2,”*”,”*”) (символ «|» в данном случае не годится, т.к. в исходных строках именно он применяется для разбиения их на группы), которое обнаруживает приличное сходство 0.75 (т.е. документы явно одной природы!). А для конкретизации сходства применяем разбиение на группы: StrCompare(str1,str2,”|”,”|”) (или просто StrCompare(str1,str2)). Результат: 0.3790227.
И теперь, возможно, самый интересный пример. Сюжет басни про ворону и лисицу был известен еще со времен Эзопа. Сравним с помощью StrCompare две басни: классический вариант от И.А. Крылова и менее известный от А.П. Сумарокова:
str1=”Уж сколько раз твердили миру, Что лесть гнусна, вредна; но только все не впрок, И в сердце льстец всегда отыщет уголок. Вороне где-то бог послал кусочек сыру; На ель Ворона взгромоздясь, Позавтракать было совсем уж собралась, Да призадумалась, а сыр во рту держала. На ту беду Лиса близехонько бежала; Вдруг сырный дух Лису остановил: Лисица видит сыр, Лисицу сыр пленил. Плутовка к дереву на цыпочках подходит; Вертит хвостом, с Вороны глаз не сводит И говорит так сладко, чуть дыша: «Голубушка, как хороша! Ну что за шейка, что за глазки! Рассказывать, так, право, сказки! Какие перушки! какой носок! И, верно, ангельский быть должен голосок! Спой, светик, не стыдись! Что, ежели, сестрица, При красоте такой и петь ты мастерица,- Ведь ты б у нас была царь-птица!» Вещуньина с похвал вскружилась голова, От радости в зобу дыханье сперло,- И на приветливы Лисицыны слова Ворона каркнула во все воронье горло: Сыр выпал — с ним была плутовка такова.”
str2=”И птицы держатся людского ремесла. Ворона сыру кус когда-то унесла И на дуб села. Да только лишь еще ни крошечки не ела. Увидела Лиса во рту у ней кусок И думает она: «Я дам Вороне сок! Хотя туда не вспряну, Кусочек этот я достану, Дуб сколько ни высок». «Здорово, — говорит Лисица, — Дружок, Воронушка, названая сестрица! Прекрасная ты птица! Какие ноженьки, какой носок, И можно то сказать тебе без лицемерья, Что паче всех ты мер, мой светик, хороша! И попугай ничто перед тобой, душа, Прекраснее стократ твои павлиньих перья!» (Нелестны похвалы приятно нам терпеть). «О, если бы еще умела ты и петь, Так не было б тебе подобной птицы в мире!» Ворона горлышко разинула пошире, Чтоб быти соловьем, «А сыру, — думает, — и после я поем. В сию минуту мне здесь дело не о пире!» Разинула уста И дождалась поста. Чуть видит лишь конец Лисицына хвоста. Хотела петь, не пела, Хотела есть, не ела.
Причина та тому, что сыру больше нет. Сыр выпал из роту, — Лисице на обед.”
StrCompare(str1,str2) дает результат 0.5590062 – так что сходство сюжета налицо!
Автор: ALANGAL
