La tâche de comparer des chaînes similaires est souvent rencontrée dans la pratique: personnellement, je l'ai rencontrée récemment en essayant d'importer des adresses de messagerie d'un programme à un autre.
Par exemple, une adresse peut ressembler à «Tverskaya oblast, Kashin g, Sovetskaya ul, 1, 5», et une autre - comme «Tver oblast; la ville de Kashin; Rue Sovetskaya; maison 1; appartement 5 ". Ces lignes sont-elles similaires et combien? Bien sûr, similaire. Et à «l'œil nu», leur structure est visible: région - agglomération - rue - maison - appartement. Il est logique que pour les adresses, une telle répartition des lignes en groupes soit importante; c'est-à-dire que nous ne devons pas comparer «deux céréales» de mots similaires (où un «porridge» se compose des mots de la première ligne et du second des mots de la seconde), mais plutôt effectuer une comparaison «en groupe» des mots de la première ligne avec des mots de la seconde. Le critère de division en groupes est également examiné: dans la première ligne, le séparateur des groupes est «,» et dans la seconde - «; ".
Dans le même temps, il existe des lignes où aucun regroupement explicite n'est visible. Par exemple, prenons les «classiques»: «Quand il n'y a pas d'accord entre les camarades, leur travail ne se fera pas sans heurts, et cela ne fonctionnera pas - juste de la farine». Et la deuxième ligne: "Singe farceur, âne, chèvre et pied bot Teddy bear a commencé à jouer un quatuor." Évidemment, les lignes sont différentes (et même la morale de ces fables est différente, bien que des parallèles puissent être trouvés).
La tâche en question n'est pas nouvelle. Il existe des algorithmes (parfois très complexes) qui tentent de le résoudre, et parfois même de le résoudre avec succès. Je propose une autre boîte d'algorithme. Lors de sa compilation, je suis parti des principes suivants:
- simplicité d'appeler la fonction de comparaison;
- facilité de mise en œuvre;
- polyvalence suffisante.
De plus, l'algorithme est implémenté sur VBA Excel, il est donc très «démocratique» et peut être utilisé partout: Excel existe non seulement parmi les logiciels de différents ordinateurs «par lui-même», mais aussi les données de divers SGBD et applications y sont exportées.
Commençons donc.
La fonction de comparaison est appelée StrCompare. Il aura 4 arguments, dont deux sont facultatifs: la première ligne str1, la deuxième ligne str2, le séparateur de groupe de la première ligne div1 et le séparateur de groupe de la deuxième ligne div2. Si div1 ou div2 sont omis, le séparateur par défaut est «|». "|" choisi car il est peu probable qu'il se produise dans la ligne "moyenne", et peut donc être utilisé pour comparer des lignes monolithiques (non groupables). Ces chaînes monolithiques peuvent également être considérées comme des chaînes constituées d'un groupe. Autrement dit, l'en-tête de la fonction de comparaison ressemble à ceci:
Public Function StrCompare(str1 As String, str2 As String, Optional div1 As String = "|", Optional div2 As String = "|") As Single
Single - car le résultat de la fonction sera un nombre indiquant le degré de similitude des chaînes comparées.
Tous les groupes de la ligne 1 sont comparés séquentiellement avec tous les groupes de la ligne 2 mot par mot, et le nombre de correspondances de mots dans chaque paire de groupes est pris en compte. Pour chaque groupe de la ligne 1, le «meilleur groupe» de la ligne 2 est finalement sélectionné (c'est-à-dire le groupe avec le plus de correspondances). Les correspondances pour chaque paire de mots sont vérifiées pour un mot d'une longueur minimale: c'est-à-dire "rue = rue" et "g = ville". Cette règle ne s'applique pas aux nombres: soit 200 <> 20. Lors de la sélection de mots, tous les «caractères insignifiants» au sein des groupes ne sont que des séparateurs de mots, mais ils sont eux-mêmes ignorés, c'est-à-dire que les mots ne peuvent être composés que de caractères WordSymbols = "0123456789ABBGDEJEZLKLMNOPRSTUFKHCHSHCHYSYEYABCDEFGHIJKLMNOPYRXUVXWVX. Il est entendu que le cas n'est pas pris en compte.
Pour rechercher un mot correspondant dans le groupe actuel de la deuxième ligne, la méthode de demi-division rapide est utilisée (mais légèrement modernisée par rapport au mot «classique», car les correspondances sont vérifiées en utilisant la méthode ci-dessus). Et puisque le fonctionnement de la méthode de demi-division nécessite des tableaux triés, l'algorithme de tri rapide est également utilisé.
Le résultat de la fonction StrCompare sera le résultat de la division du nombre de mots correspondants par le nombre total de mots dans les lignes 1 et 2:
StrCompare = (da * 2) / ((kon1_2 - nach1_2 + 1) * (kon1_1 - nach1_1 + 1) + (kon2_2 - nach2_2 + 1) * (kon2_1 - nach2_1 + 1))
Ici, par exemple, kon1_2 est la limite finale du tableau 1 (un tableau de mots contenus dans les groupes de la première ligne) selon la 2e dimension (la 1re dimension est le nombre de groupes et la 2e est le nombre de mots du groupe).
Il est temps d'introduire le code:
' "" . : '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
Il ne sert à rien de tout commenter, je pense: vous pouvez naviguer par le code. Il suffit d'analyser le fonctionnement de la fonction de comparaison sur plusieurs lignes de nature différente.
- str1 = ”région de Tver., Kashin g, rue Sovetskaya, 1, 5” str2 = ”région de Tver; la ville de Kashin; Rue Sovetskaya; maison 1; appartement 5 ".
Tout d'abord, comparez les lignes hors groupes:
StrCompare (str1, str2) donne le résultat 0,8888889.
Et maintenant, considérant:
StrCompare (str1, str2, ”,“, ”;“) - le résultat est 0,8.
Comme vous pouvez le voir, les groupes sont plus strictement liés à la comparaison; dans ce cas, il est important pour eux que «la maison soit la maison et l'appartement soit l'appartement». Lorsque vous ignorez les groupes, cela ne joue aucun rôle. - str1 = "Ma grand-mère a vécu une chèvre grise" str2 = "Ma grand-mère a vécu une chèvre grise"
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 = "Quand il n'y a pas d'accord entre les camarades, leur travail ne fonctionnera pas bien, et cela ne fonctionnera pas - seulement de la farine." str2 = "Singe farceur, âne, chèvre et pied bot Teddy bear a commencé à jouer un quatuor."
StrCompare (str1, str2) -> 0 - str1 = ”Conformément au paragraphe 1 de l'art. 540 du Code civil de la Fédération de Russie dans le cas où un abonné dans le cadre d'un accord d'alimentation électrique est un citoyen utilisant de l'énergie pour la consommation domestique, le contrat est considéré comme conclu à partir du moment où l'abonné se connecte effectivement au réseau. | Conformément à l'article 153, partie 1, du Code du logement de la Fédération de Russie, les citoyens sont tenus de payer en temps voulu et intégralement les frais de logement et de services publics. | Dans la période du "____" _________ 2017 au "____" __________ 2017, le fournisseur garant vous a fourni de l'électricité pour un montant de ______________________. | Dans le cadre de votre violation de vos obligations de payer pour l'énergie électrique, qui a entraîné la formation d'une dette de consommation envers le fournisseur garant pour un montant de plus de 2 périodes de règlement, des mesures ont été prises pour limiter le logement du consommateur aux dépens du fournisseur de la garantie / renouvellement de la fourniture de services publics pour la fourniture d'électricité | Conformément au paragraphe 121, paragraphe 1, des règles pour la fourniture de services publics aux propriétaires et utilisateurs de locaux dans des immeubles à appartements multiples x et bâtiments résidentiels, approuvés par le décret gouvernemental 06.05.2011g. N ° 354, les frais de l'entrepreneur liés à l'introduction de la restriction, de la suspension et de la reprise de la fourniture de services publics au consommateur débiteur sont remboursés aux frais du consommateur à l'égard duquel les mesures indiquées ont été prises. | Le coût du paiement des mesures visant à introduire la restriction et la restauration ultérieure de l'alimentation en électricité est pour la garantie le montant du fournisseur ______________________________________________. | Sur la base de ce qui précède, le PO "TverAtomEnergoSbyt" vous demande de payer la dette pour les actions de restriction / renouvellement des services municipaux d'électricité à hauteur de _____________________ roubles. sur les informations suivantes avec le numéro de compte personnel et le but du paiement: "
str2 = ”“ ____ ”__________ 2017 entre JSC AtomEnergoSbyt - le fournisseur garant et _____________________ - le consommateur a conclu un accord de fourniture d'énergie n ° ___________________, valable pour _________________ ans, avec la condition de sa prolongation (clause 8.1 de l'accord, article 540 du Code civil de la Fédération de Russie ), conformément au point 1.1. que le fournisseur garant s'est engagé à vendre de l'énergie électrique (électricité), ainsi qu'indépendamment ou par l'intermédiaire de tiers pour fournir des services et des services de transmission d'énergie électrique, dont la fourniture fait partie intégrante du processus de fourniture d'énergie électrique au consommateur, et l'acheteur s'engage à payer pour l'énergie électrique achetée (énergie) . | Dans le cadre de la violation par le Consommateur de ses obligations de payer pour l'énergie électrique (clause 5.2. De l'accord de fourniture d'électricité n ° __________________ du ___________), qui a conduit à la formation d'une dette des consommateurs envers le fournisseur garant pour un montant de plus d'une période de facturation par rapport au réseau électrique du consommateur -_________________ des mesures ont été prises pour limiter / reprendre le régime de consommation d'énergie conformément aux règles de limitation intégrale et (ou) partielle du régime de consommation d'électricité, approuvé par décret du gouvernement de la Fédération de Russie en date du 04.05.2012 n ° 442 (ci-après - le règlement). | Conformément au paragraphe 24 des Règles, le consommateur est tenu d'indemniser le contractant pour le coût des actions visant à introduire une restriction et la restauration ultérieure du régime de consommation d'énergie électrique. | Le coût des dépenses du fournisseur de Garantie pour le paiement des actions visant à introduire une restriction et la restauration ultérieure du régime de consommation d'énergie électrique est ______________________________________________. | Basé sur de ce qui précède, l'OP «TverAtomEnergoSbyt» vous demande de payer les frais du fournisseur garant pour les actions limitées à w / mode de reprise consommation d'énergie électrique dans le montant de _______________ roubles. pour les informations suivantes avec le numéro du contrat et l'objet du paiement: | Objet du paiement: paiement de la restriction / reprise du régime de consommation d'énergie électrique dans le cadre du contrat n ° ____________ »
Ici str1 et str2 sont des fragments de documents très similaires (accords de fourniture d'énergie pour les particuliers et les entités juridiques, respectivement). Pour une "évaluation approximative" de la similitude des documents, vous pouvez utiliser une comparaison sans les groupes StrCompare (str1, str2, "*", "*") (le caractère "|" ne convient pas dans ce cas, car il est utilisé dans les lignes d'origine pour les casser). groupes), ce qui révèle une ressemblance décente de 0,75 (c'est-à-dire que les documents sont clairement de même nature!). Et pour concrétiser les similitudes, nous utilisons le regroupement: StrCompare (str1, str2, ”|”, ”|”) (ou simplement StrCompare (str1, str2)). Résultat: 0,3790227.
Et maintenant, peut-être l'exemple le plus intéressant. L'intrigue de la fable sur le corbeau et le renard est connue depuis l'époque d'Esope. À l'aide de StrCompare, comparez deux fables: une version classique par I.A. Krylova et moins connu de A.P. Sumarokova:
str1 = ”Combien de fois ont-ils répété au monde que la flatterie est vile, nuisible; mais juste pas pour l'avenir, Et dans le cœur un flatteur trouvera toujours un coin. Quelque part à Vorone, Dieu a envoyé un morceau de fromage; Empilant sur le Spruce Crow, le petit déjeuner était tout à fait prêt, oui, réfléchi, et j'ai gardé le fromage dans ma bouche. À ce malheur, le Fox a couru près; Soudain, l'esprit au fromage de Lisa s'arrêta: Le renard voit le fromage, Le renard a capturé le fromage. La pointe des pieds à l'arbre est la pointe des pieds; Il se tord la queue, ne quitte pas le Corbeau des yeux et parle si gentiment, respirant un peu: «Cher, comme c'est bon! Quel cou, quel œil! Pour dire, donc, à droite, les contes de fées! Quel pearshki! quelle chaussette! Et, c'est vrai, l'ange doit avoir une voix! Chante, léger, n'aie pas honte! Et si, sœur, avec une telle beauté, vous êtes une artisane à chanter, - Après tout, si nous avions un oiseau-roi! La tête de Veschunya tournait de louanges, Avec joie, son souffle a coulé, - Et à la sympathique Lisitsyna, les mots du Corbeau lui ont jeté dans la gorge: du fromage est tombé - telle était la triche avec lui. "
str2 = ”Et les oiseaux s'accrochent au métier d'hommes. Un corbeau a une fois emporté un fromage chez un cousin Et s'est assis sur un chêne. Oui, je n'ai tout simplement pas mangé un tout petit peu. Le renard a vu un morceau dans sa bouche et elle pense: «Je vais donner du jus de corbeau! Même si je n'y arriverai pas, j'obtiendrai cette pièce, Oak, peu importe sa taille. " "C'est génial", dit Fox, "Ami, entonnoir, soeur nommée!" Tu es un bel oiseau! Quel genre de ciseaux, quelle chaussette, Et tu peux te dire sans hypocrisie, Qu'est-ce que tu es plus que toute autre chose, ma petite lumière, bien! Et le perroquet n'est rien devant toi, âme, Plus de cent fois plus belles sont tes plumes de paon! (Les louanges agréables ne sont pas flatteuses). "Oh, si tu savais encore chanter, alors il n'y aurait pas pour toi un tel oiseau au monde!" Le corbeau a ouvert son cou plus large pour être un rossignol, "Et pour le fromage", pense-t-il, "et après cela je mangerai." Cette minute, je ne parle pas d'une fête! " J'ai ouvert la bouche et attendu le jeûne. Il ne voit que la fin de la queue Lisitsyn. Je voulais chanter, je ne chantais pas, je voulais manger, je ne mangeais pas.
La raison en est que le fromage n'est plus là. Le fromage est tombé de l'entreprise, - Fox pour le déjeuner. "
StrCompare (str1, str2) donne le résultat 0,5590062 - il y a donc une similitude de tracé!