Die Aufgabe, ähnliche Zeichenfolgen zu vergleichen, tritt in der Praxis häufig auf: Ich persönlich bin kürzlich darauf gestoßen, als ich versucht habe, E-Mail-Adressen von einem Programm in ein anderes zu importieren.
Beispielsweise kann eine Adresse wie "Tverskaya-Gebiet, Kashing, Sovetskaya ul, 1, 5" und eine andere wie "Tver-Gebiet; die Stadt Kashin; Sovetskaya Straße; Haus 1; Wohnung 5 ". Sind diese Zeilen ähnlich und wie viel? Klar, ähnlich. Und mit dem "bloßen Auge" ist ihre Struktur sichtbar: Region - Siedlung - Straße - Haus - Wohnung. Es ist logisch, dass für Adressen eine solche Aufteilung der Zeilen in Gruppen wichtig ist; Das heißt, wir sollten nicht "zwei Getreide" ähnlicher Wörter vergleichen (wobei ein "Brei" aus den Wörtern der ersten Zeile und das zweite der Wörter der zweiten Zeile besteht), sondern einen "Gruppen" -Vergleich von Wörtern aus der ersten Zeile mit Wörtern aus der zweiten Zeile durchführen. Das Kriterium für die Aufteilung in Gruppen wird ebenfalls untersucht: In der ersten Zeile ist das Trennzeichen der Gruppen "," und in der zweiten - "; ".
Gleichzeitig gibt es Zeilen, in denen keine explizite Gruppierung sichtbar ist. Nehmen wir zum Beispiel die „Klassiker“: „Wenn die Genossen keine Einigung erzielen, wird ihre Arbeit nicht reibungslos verlaufen und es wird nicht funktionieren - nur Mehl.“ Und die zweite Zeile: "Prankish Monkey, Donkey, Goat und Clubfoot Teddybär haben angefangen, ein Quartett zu spielen." Offensichtlich sind die Linien unterschiedlich (und sogar die Moral dieser Fabeln ist unterschiedlich, obwohl Parallelen gefunden werden können).
Die betreffende Aufgabe ist nicht neu. Es gibt Algorithmen (manchmal sehr komplex), die versuchen, es zu lösen, und manchmal sogar erfolgreich. Ich schlage eine weitere Algorithmusbox vor. Beim Kompilieren ging ich von folgenden Prinzipien aus:
- Einfachheit des Aufrufs der Vergleichsfunktion;
- einfache Implementierung;
- ausreichende Vielseitigkeit.
Darüber hinaus ist der Algorithmus in VBA Excel implementiert, daher sehr „demokratisch“ und kann überall verwendet werden: Excel existiert nicht nur in der Software verschiedener Computer „von selbst“, sondern es werden auch Daten aus allen Arten von DBMS und Anwendungen in dieses exportiert.
Also fangen wir an.
Die Vergleichsfunktion heißt StrCompare. Es gibt 4 Argumente, von denen zwei optional sind: die erste Zeile str1, die zweite Zeile str2, das Gruppentrennzeichen der ersten Zeile div1 und das Gruppentrennzeichen der zweiten Zeile div2. Wenn div1 oder div2 weggelassen werden, lautet das Standardtrennzeichen "|". "|" gewählt, weil es unwahrscheinlich ist, dass es in der "durchschnittlichen" Linie gefunden wird, und daher verwendet werden kann, um monolithische (nicht gruppierbare) Linien zu vergleichen. Solche monolithischen Strings können auch als Strings betrachtet werden, die aus einer Gruppe bestehen. Das heißt, der Header der Vergleichsfunktion sieht folgendermaßen aus:
Public Function StrCompare(str1 As String, str2 As String, Optional div1 As String = "|", Optional div2 As String = "|") As Single
Single - weil das Ergebnis der Funktion eine Zahl ist, die den Ähnlichkeitsgrad der verglichenen Zeichenfolgen angibt.
Alle Gruppen von Zeile 1 werden nacheinander Wort für Wort mit allen Gruppen von Zeile 2 verglichen, und die Anzahl der Wortübereinstimmungen in jedem Gruppenpaar wird berücksichtigt. Für jede Gruppe von Zeile 1 wird schließlich die „beste Gruppe“ aus Zeile 2 ausgewählt (dh die Gruppe mit den meisten Übereinstimmungen). Übereinstimmungen für jedes Wortpaar werden auf ein Wort mit einer Mindestlänge überprüft: "Straße = Straße" und "g = Stadt". Diese Regel gilt nicht für Zahlen: d. H. 200 <> 20. Bei der Auswahl von Wörtern sind alle „unbedeutenden Zeichen“ innerhalb der Gruppen nur Worttrennzeichen, sie werden jedoch selbst ignoriert, dh Wörter können nur aus Zeichen bestehen. WordSymbols = "0123456789ABBGDEJEZLKLMNOPRSTUFKHCHSHCHYSYEYABCDEFGHIJKLMNOPYRXUVXWX. Es versteht sich, dass der Fall nicht berücksichtigt wird.
Um in der aktuellen Gruppe der zweiten Zeile nach einem passenden Wort zu suchen, wird die schnelle Halbteilungsmethode verwendet (jedoch im Vergleich zur „klassischen“ Methode leicht modernisiert, da Übereinstimmungen mit der obigen Methode überprüft werden). Und da die Operation der Halbteilungsmethode sortierte Arrays erfordert, wird auch der schnelle Sortieralgorithmus verwendet.
Das Ergebnis der StrCompare-Funktion ist das Ergebnis der Division der Anzahl übereinstimmender Wörter durch die Gesamtzahl der Wörter in den Zeilen 1 und 2:
StrCompare = (da * 2) / ((kon1_2 - nach1_2 + 1) * (kon1_1 - nach1_1 + 1) + (kon2_2 - nach2_2 + 1) * (kon2_1 - nach2_1 + 1))
Hier ist kon1_2 beispielsweise die letzte Grenze von Array 1 (ein Array von Wörtern, die in den Gruppen der ersten Zeile enthalten sind) gemäß der 2. Dimension (die 1. Dimension ist die Anzahl der Gruppen und die 2. Dimension ist die Anzahl der Wörter in der Gruppe).
Es ist Zeit, den Code einzuführen:
' "" . : '1, 2, 1, 2 Public Function StrCompare(str1 As String, str2 As String, Optional div1 As String = "|", Optional div2 As String = "|") As Single WordSymbols = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ" 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
Es macht keinen Sinn, alles zu kommentieren, denke ich: Sie können anhand des Codes navigieren. Analysieren Sie einfach die Funktionsweise der Vergleichsfunktion in mehreren Zeilen unterschiedlicher Art.
- str1 = "Tver Region., Kashin g, Sovetskaya Straße, 1, 5" str2 = "Tver Region; die Stadt Kashin; Sovetskaya Straße; Haus 1; Wohnung 5 ".
Vergleichen Sie zunächst die Zeilen ohne Gruppen:
StrCompare (str1, str2) ergibt das Ergebnis 0,8888889.
Und jetzt überlegen wir:
StrCompare (str1, str2, ”,“, ”;“) - das Ergebnis ist 0,8.
Wie Sie sehen können, sind Gruppen enger mit dem Vergleich verbunden. In diesem Fall ist es für sie wichtig, dass „das Haus das Haus ist und die Wohnung die Wohnung“. Beim Ignorieren von Gruppen spielt dies keine Rolle. - str1 = "Meine Großmutter lebte eine graue Ziege" str2 = "Großmutter lebte eine graue Ziege"
StrCompare (str1, str2) -> 0,6666667 - str1 = ”Ivanov Ivan Ivanovich m. Kaluga 1950 ”str2 =” Ivanov I.I. 20.01.1950 ”
StrCompare (str1, str2) -> 0,6153846 - str1 = "Wenn es keine Einigung zwischen den Genossen gibt, wird ihre Arbeit nicht gut funktionieren und es wird nicht gut funktionieren - nur Mehl." str2 = "Prankish Monkey, Donkey, Goat und Clubfoot Teddybär haben angefangen, ein Quartett zu spielen."
StrCompare (str1, str2) -> 0 - str1 = ”In Übereinstimmung mit Absatz 1 der Kunst. 540 des Bürgerlichen Gesetzbuchs der Russischen Föderation gilt der Vertrag ab dem Zeitpunkt, an dem der Teilnehmer tatsächlich eine Verbindung zum Netz herstellt, als abgeschlossen, wenn ein Teilnehmer im Rahmen eines Stromversorgungsvertrags ein Bürger ist, der Energie für den Inlandsverbrauch verwendet. Gemäß Artikel 153 Teil 1 des Wohnungsgesetzbuchs der Russischen Föderation sind die Bürger verpflichtet, die Gebühren für Wohnen und Versorgung rechtzeitig und vollständig zu zahlen. | Im Zeitraum von "____" _________ 2017 bis "____" __________ 2017 hat Sie der Garantielieferant mit Strom in Höhe von ______________________ versorgt. Im Zusammenhang mit Ihrer Verletzung Ihrer Zahlungsverpflichtungen für elektrische Energie, die zur Bildung von Verbraucherschulden gegenüber dem garantierenden Lieferanten in Höhe von mehr als zwei Abrechnungsperioden führte, wurden Maßnahmen ergriffen, um die Wohnung des Verbrauchers auf Kosten des Lieferanten der Garantie zu begrenzen. die Wiederaufnahme der Erbringung von Versorgungsleistungen für die Stromversorgung. | Gemäß Paragraph 121 (1) der Regeln für die Erbringung von Versorgungsleistungen für Eigentümer und Nutzer von Räumlichkeiten in Mehrfamilienhäusern x und Wohngebäude, genehmigt durch Regierungsdekret 06.05.2011g. Nr. 354 werden die Kosten des Auftragnehmers im Zusammenhang mit der Einführung der Beschränkung, Aussetzung und Wiederaufnahme der Erbringung von Versorgungsleistungen für den Verbraucherschuldner auf Kosten des Verbrauchers erstattet, für den die angegebenen Maßnahmen ergriffen wurden. | Die Kosten für die Zahlung der Maßnahmen zur Einführung der Beschränkung und der anschließenden Wiederherstellung der Stromversorgung gehen zu Lasten der Garantie der Betrag des Lieferanten ______________________________________________. | Auf der Grundlage des Vorstehenden fordert FE TverAtomEnergoSbyt Sie auf, die Schulden für Maßnahmen zu bezahlen die Beschränkung / Erneuerung der kommunalen Dienstleistungen für Strom in Höhe von _____________________ Rubel. zu folgenden Angaben mit der persönlichen Kontonummer und dem Zahlungszweck: “
str2 = ”“ ____ ”__________ 2017 zwischen JSC AtomEnergoSbyt - dem Garantieanbieter und _____________________ - Der Verbraucher hat unter der Bedingung seiner weiteren Verlängerung einen für _________________ Jahre gültigen Energieversorgungsvertrag Nr. ___________________ geschlossen (Ziffer 8.1 des Vertrages, Artikel 540 des Bürgerlichen Gesetzbuchs der Russischen Föderation ) gemäß Absatz 1.1. Der garantierende Anbieter hat sich verpflichtet, elektrische Energie (Strom) sowie unabhängig oder über Dritte zu verkaufen, um Stromübertragungsdienste und -dienste bereitzustellen, deren Bereitstellung ein wesentlicher Bestandteil des Prozesses der Lieferung elektrischer Energie an den Verbraucher ist, und der Käufer verpflichtet sich, die gekaufte elektrische Energie (Strom) zu bezahlen. . | Im Zusammenhang mit der Verletzung seiner Verpflichtungen zur Zahlung elektrischer Energie durch den Verbraucher (Ziffer 5.2. Des Stromversorgungsvertrags Nr. __________________ von ___________), die zur Bildung einer Verbraucherschuld gegenüber dem garantierenden Lieferanten in Höhe von mehr als einer Abrechnungsperiode in Bezug auf die Stromnetzanlage des Verbrauchers führte -_________________ Es wurden Maßnahmen ergriffen, um das Energieverbrauchsregime gemäß den Regeln für die vollständige und (oder) teilweise Begrenzung des Stromverbrauchsregimes zu begrenzen / wieder aufzunehmen. genehmigt durch Dekret der Regierung der Russischen Föderation vom 04.05.2012 Nr. 442 (im Folgenden - die Regeln). | Gemäß Paragraph 24 der Regeln ist der Verbraucher verpflichtet, den Auftragnehmer für die Kosten der Maßnahmen zur Einführung einer Beschränkung und der anschließenden Wiederherstellung des Regimes des Stromverbrauchs zu entschädigen. | Die Kosten für die Kosten des Garantielieferanten für die Zahlung von Maßnahmen zur Einführung einer Beschränkung und die anschließende Wiederherstellung des Regimes des Stromverbrauchs betragen ______________________________________________ OP „TverAtomEnergoSbyt“ fordert Sie auf, die Kosten des Garantielieferanten für Maßnahmen zu zahlen, die auf Folgendes beschränkt sind w / Fortsetzungsmodus der elektrische Stromverbrauch in der Höhe von _______________ Rubel. für die folgenden Einzelheiten mit der Vertragsnummer und dem Zahlungszweck: | Zahlungszweck: Zahlung der Beschränkung / Wiederaufnahme des Regimes des Stromverbrauchs gemäß Vertrag Nr. ____________ “
Hierbei sind str1 und str2 Fragmente sehr ähnlicher Dokumente (Energieversorgungsvereinbarungen für Einzelpersonen bzw. juristische Personen). Für eine „grobe Beurteilung“ der Dokumentähnlichkeit können Sie einen Vergleich ohne die StrCompare-Gruppen (str1, str2, ”*”, ”*”) verwenden (das Zeichen “|” ist in diesem Fall nicht geeignet, da es in den ursprünglichen Zeilen verwendet wird, um sie zu unterbrechen Gruppen), was eine anständige Ähnlichkeit von 0,75 zeigt (d. h. Dokumente sind eindeutig von gleicher Natur!). Und zur Konkretisierung von Ähnlichkeiten verwenden wir die Gruppierung: StrCompare (str1, str2, ”|”, ”|”) (oder einfach StrCompare (str1, str2)). Ergebnis: 0,3790227.
Und jetzt vielleicht das interessanteste Beispiel. Die Handlung der Fabel über die Krähe und den Fuchs ist seit Aesops Zeit bekannt. Vergleichen Sie mit StrCompare zwei Fabeln: eine klassische Version von I.A. Krylova und weniger bekannt von A.P. Sumarokova:
str1 = ”Wie oft haben sie der Welt wiederholt: Diese Schmeichelei ist gemein, schädlich; aber nur nicht für die Zukunft, und im Herzen wird ein Schmeichler immer eine Ecke finden. Irgendwo nach Vorone sandte Gott ein Stück Käse; Das Frühstück war ziemlich fertig, ja, nachdenklich, und ich hielt den Käse in meinem Mund. Zu diesem Unglück rannte der Fuchs nahe heran; Plötzlich hörte der käsige Geist von Lisa auf: Der Fuchs sieht den Käse, Der Fuchs hat den Käse gefangen. Die Zehenspitzen zum Baum gehen auf Zehenspitzen; Er dreht seinen Schwanz, lässt die Krähe nicht aus den Augen und spricht so süß und atmet ein wenig: „Liebes, wie gut! Was für ein Hals, was für ein Auge! Also, richtig, Märchen! Was für ein Pearshki! Was für eine Socke! Und wahr, der Engel muss eine Stimme haben! Singe, Licht, schäme dich nicht! Was, wenn, Schwester, mit solch einer Schönheit bist du eine Handwerkerin zum Singen? - Immerhin, wenn wir einen Königsvogel hätten! “ Veschunyas Kopf drehte sich vor Lob, vor Freude sank sein Atem - und zu der freundlichen Lisitsyna warfen die Worte des Raben in ihren ganzen Hals: Käse fiel heraus - so war der Betrug bei ihm. "
str2 = ”Und die Vögel halten am Handwerk der Menschen fest. Eine Krähe trug einmal einen Käse zu einem Cous und setzte sich auf eine Eiche. Ja, habe nur kein kleines bisschen gegessen. Der Fuchs sah ein Stück in ihrem Mund und sie denkt: „Ich werde den Raben-Saft geben! Obwohl ich nicht dort ankomme, bekomme ich dieses Stück, Oak, egal wie groß. " "Es ist großartig", sagt Fox, "Freund, Trichter, benannte Schwester!" Du bist ein wunderschöner Vogel! Was für eine Schere, was für eine Socke, und du kannst dir ohne Heuchelei sagen, was bist du mehr als alles andere, mein kleines Licht, gut! Und der Papagei ist nichts vor dir, Seele. Mehr als hundertmal schöner sind deine Pfauenfedern! “ (Angenehmes Lob ist nicht schmeichelhaft). "Oh, wenn du noch singen könntest, gäbe es für dich keinen solchen Vogel auf der Welt!" Die Krähe öffnete ihren Hals weiter, um eine Nachtigall zu sein. "Und zum Käse", denkt er, "und danach werde ich essen." In dieser Minute spreche ich nicht von einem Fest! " Ich öffnete meinen Mund und wartete auf das Fasten. Er sieht nur das Ende des Lisitsyn-Schwanzes. Ich wollte singen, ich habe nicht gesungen, ich wollte essen, ich habe nicht gegessen.
Der Grund ist, dass Käse nicht mehr da ist. Der Käse fiel aus der Firma, - Fox zum Mittagessen. “
StrCompare (str1, str2) ergibt das Ergebnis 0,5590062 - es gibt also eine Plotähnlichkeit!