La tarea de comparar cadenas similares a menudo se encuentra en la práctica: personalmente la encontré recientemente al intentar importar direcciones de correo de un programa a otro.
Por ejemplo, una dirección puede verse como "Tverskaya oblast, Kashin g, Sovetskaya ul, 1, 5" y otra, como "Tver oblast; la ciudad de Kashin; Calle Sovetskaya; casa 1; apartamento de 5 ". ¿Son similares estas líneas y cuánto? Claro, similar. Y a simple vista su estructura es visible: región - asentamiento - calle - casa - apartamento. Es lógico que para las direcciones este desglose de líneas en grupos sea importante; es decir, no debemos comparar "dos cereales" de palabras similares (donde una "papilla" consiste en las palabras de la primera línea y la segunda de las palabras de la segunda), sino más bien, realizar una comparación "grupal" de las palabras de la primera línea con las palabras de la segunda. También se examina el criterio para dividir en grupos: en la primera línea, el separador de los grupos es ",", y en la segunda - "; ".
Al mismo tiempo, hay líneas donde no hay agrupación explícita visible. Por ejemplo, tome los "clásicos": "Cuando no hay acuerdo en los camaradas, su trabajo no funcionará sin problemas, y no funcionará, solo la harina". Y la segunda línea: "El mono franco, el burro, la cabra y el oso de peluche del pie zambo comenzaron a tocar un cuarteto". Obviamente las líneas son diferentes (e incluso la moraleja de estas fábulas es diferente, aunque se pueden encontrar paralelos).
La tarea en cuestión no es nueva. Hay algoritmos (a veces muy complejos) que intentan resolverlo, e incluso a veces lo resuelven con éxito. Propongo un cuadro de algoritmo más. Al compilarlo, procedí de los siguientes principios:
- simplicidad de llamar a la función de comparación;
- facilidad de implementación;
- suficiente versatilidad
Además, el algoritmo se implementa en VBA Excel, por lo tanto, es muy "democrático" y se puede usar en todas partes: Excel no solo existe entre el software de varias computadoras "por sí mismo", sino que también se exportan datos de todo tipo de DBMS y aplicaciones.
Entonces comencemos.
La función de comparación se llama StrCompare. Tendrá 4 argumentos, dos de los cuales son opcionales: la primera línea str1, la segunda línea str2, el separador de grupo de la primera línea div1 y el separador de grupo de la segunda línea div2. Si se omiten div1 o div2, el separador predeterminado es "|". "|" elegido porque es poco probable que ocurra en la línea "promedio" y, por lo tanto, puede usarse para comparar líneas monolíticas (no agrupables). Tales cadenas monolíticas también pueden considerarse cadenas que consisten en un grupo. Es decir, el encabezado de la función de comparación se ve así:
Public Function StrCompare(str1 As String, str2 As String, Optional div1 As String = "|", Optional div2 As String = "|") As Single
Single: porque el resultado de la función será un número que muestra el grado de similitud de las cadenas comparadas.
Todos los grupos de la línea 1 se comparan secuencialmente con todos los grupos de la línea 2 palabra por palabra, y se considera el número de coincidencias de palabras en cada par de grupos. Para cada grupo de la línea 1, finalmente se selecciona el "mejor grupo" de la línea 2 (es decir, el grupo con más coincidencias). Las coincidencias para cada par de palabras se verifican para una palabra con una longitud mínima: es decir, "calle = calle" y "g = ciudad". Esta regla no se aplica a los números: es decir, 200 <> 20. Al seleccionar palabras, todos los "caracteres insignificantes" dentro de los grupos son solo separadores de palabras, pero ellos mismos se ignoran, es decir, las palabras pueden consistir solo en caracteres WordSymbols = "0123456789ABBGDEJEZLKLMNOPRSTUFKHCHSHCHYSYEYABCDEFGHIJKLMNOPYRXUVXWVX. Se entiende que el caso no se tiene en cuenta.
Para buscar una palabra coincidente en el grupo actual de la segunda línea, se utiliza el método de división rápida (pero ligeramente modernizado en comparación con el "clásico", ya que las coincidencias se verifican con el método anterior). Y dado que la operación del método de media división requiere matrices ordenadas, también se utiliza el algoritmo de clasificación rápida.
El resultado de la función StrCompare será el resultado de dividir el número de palabras coincidentes por el número total de palabras en las líneas 1 y 2:
StrCompare = (da * 2) / ((kon1_2 - nach1_2 + 1) * (kon1_1 - nach1_1 + 1) + (kon2_2 - nach2_2 + 1) * (kon2_1 - nach2_1 + 1))
Aquí, por ejemplo, kon1_2 es el límite final de la matriz 1 (una matriz de palabras contenidas en los grupos de la primera fila) de acuerdo con la segunda dimensión (la primera dimensión es el número de grupos y la segunda es el número de palabras en el grupo).
Es hora de introducir el código:
' "" . : '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
No tiene sentido comentar todo, creo: puedes navegar por el código. Simplemente analice el funcionamiento de la función de comparación en varias líneas de diferente naturaleza.
- str1 = ”región de Tver., Kashin g, calle Sovetskaya, 1, 5” str2 = ”región de Tver; la ciudad de Kashin; Calle Sovetskaya; casa 1; apartamento de 5 ".
Primero, compare las líneas excluyendo grupos:
StrCompare (str1, str2) da el resultado 0.8888889.
Y ahora considerando:
StrCompare (str1, str2, ”,“, ”;“) - el resultado es 0.8.
Como puede ver, los grupos están más estrictamente relacionados con la comparación; en este caso, es importante para ellos que "la casa es la casa y el departamento es el departamento". Al ignorar grupos, esto no juega un papel. - str1 = "Mi abuela vivía una cabra gris" str2 = "La abuela vivía una cabra gris"
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 = "Cuando no hay acuerdo en los camaradas, su trabajo no funcionará bien, y no funcionará a partir de eso, solo harina". str2 = "Prankish monkey, Donkey, Goat y clubfoot Teddy bear comenzaron a tocar un cuarteto".
StrCompare (str1, str2) -> 0 - str1 = ”De conformidad con el párrafo 1 del art. 540 del Código Civil de la Federación de Rusia en el caso de que un suscriptor bajo un acuerdo de suministro de energía sea un ciudadano que usa energía para consumo doméstico, el contrato se considera concluido desde el momento en que el suscriptor realmente se conecta a la red. De acuerdo con la Parte 1 del Artículo 153 del Código de Vivienda de la Federación Rusa, los ciudadanos están obligados a pagar a tiempo y por completo las tarifas de vivienda y servicios públicos. El | En el período comprendido entre "____" _________ 2017 y "____" __________ 2017, el proveedor de Garantía le suministró electricidad por un monto de ______________________. | En relación con su incumplimiento de sus obligaciones de pagar la energía eléctrica, lo que condujo a la formación de la deuda del consumidor con el proveedor que garantiza en la cantidad de más de 2 períodos de liquidación, se tomaron medidas para limitar la vivienda del Consumidor a expensas del proveedor de la Garantía / la reanudación de la prestación de servicios públicos para el suministro de electricidad. De conformidad con el párrafo 121 (1) de las Reglas para la prestación de servicios públicos a los propietarios y usuarios de locales en edificios de apartamentos múltiples x residenciales y edificios, aprobado por el Decreto del Gobierno 06.05.2011g. No. 354, los gastos del contratista relacionados con la introducción de la restricción, suspensión y reanudación de la prestación de servicios públicos al consumidor-deudor se reembolsan a expensas del consumidor respecto del cual se tomaron las medidas indicadas. el monto del proveedor ______________________________________________. | Basado en lo anterior, FE TverAtomEnergoSbyt le pide que pague la deuda por acciones de restricción / renovación de los servicios municipales de electricidad en la cantidad de _____________________ rublos. en los siguientes detalles con el número de cuenta personal y el propósito del pago: "
str2 = ”“ ____ ”__________ 2017 entre JSC AtomEnergoSbyt - el Proveedor de Garantía y _____________________ - El Consumidor concluyó un acuerdo de suministro de energía No. ___________________, válido por _________________ años, con la condición de su extensión adicional (cláusula 8.1 del acuerdo, artículo 540 del Código Civil de la Federación Rusa ), de conformidad con el apartado 1.1. que el proveedor de garantía se comprometió a vender energía eléctrica (energía), así como de manera independiente o a través de terceros para proporcionar servicios y servicios de transmisión de energía eléctrica, cuya provisión es una parte integral del proceso de suministro de energía eléctrica al consumidor, y el Comprador se compromete a pagar la energía (energía) comprada . En relación con la violación por parte del Consumidor de sus obligaciones de pagar por la energía eléctrica (cláusula 5.2. Del acuerdo de suministro de energía No. __________________ de ___________), que llevó a la formación de la deuda del consumidor con el proveedor garantizador por más de un período de facturación en relación con la instalación de la red eléctrica del consumidor -_________________ se tomaron medidas para limitar / reanudar el régimen de consumo de energía de conformidad con las Reglas para la limitación total y (o) parcial del régimen de consumo de electricidad, aprobado por Decreto del Gobierno de la Federación de Rusia de fecha 04.05.2012 No. 442 (en adelante, las Reglas). | Según el párrafo 24 de las Reglas, el consumidor está obligado a compensar al contratista por el costo de las acciones para introducir una restricción y la restauración posterior del régimen de consumo de energía eléctrica. | El costo de los gastos del proveedor de Garantía por el pago de acciones para introducir una restricción y la restauración posterior del régimen de consumo de energía eléctrica es ______________________________________________. de lo anterior, el OP "TverAtomEnergoSbyt" le pide que pague los costos del proveedor que garantiza las acciones limitadas a modo de w / reanudar el consumo de energía eléctrica en la cantidad de _______________ rublos. para los siguientes detalles con el número del contrato y el propósito del pago: | Propósito del pago: pago de la restricción / reanudación del régimen de consumo de energía eléctrica bajo el contrato No. ____________ ”
Aquí str1 y str2 son fragmentos de documentos muy similares (acuerdos de suministro de energía para personas físicas y jurídicas, respectivamente). Para una "evaluación aproximada" de la similitud de documentos, puede usar una comparación sin los grupos StrCompare (str1, str2, "*", "*") (el carácter "|" no es adecuado en este caso, porque se usa en las líneas originales para separarlos grupos), lo que revela un parecido decente de 0,75 (es decir, ¡los documentos son claramente de la misma naturaleza!). Y para la concreción de similitudes, utilizamos la agrupación: StrCompare (str1, str2, ”|”, ”|”) (o simplemente StrCompare (str1, str2)). Resultado: 0.3790227.
Y ahora, quizás el ejemplo más interesante. La trama de la fábula sobre el cuervo y el zorro se conoce desde los tiempos de Esopo. Usando StrCompare, compare dos fábulas: una versión clásica de I.A. Krylova y menos conocido de A.P. Sumarokova:
str1 = "¿Cuántas veces le han repetido al mundo, que los halagos son viles, dañinos; pero no para el futuro, y en el corazón un adulador siempre encontrará un rincón. En algún lugar a Vorone, Dios envió un trozo de queso; Acomodándose en el Spruce Crow, el desayuno estaba bastante listo, sí, pensativo, y mantuve el queso en la boca. Para esa desgracia, el zorro corrió cerca; De repente, el espíritu cursi de Lisa se detuvo: el zorro ve el queso, el zorro capturó el queso. De puntillas al árbol es de puntillas; Gira la cola, no quita los ojos del cuervo y habla con dulzura, respirando un poco: “¡Querido, qué bueno! ¡Qué cuello, qué ojo! A decir, entonces, bien, cuentos de hadas! ¡Qué pearshki! ¡Qué calcetín! Y, cierto, ¡el ángel debe tener voz! ¡Canta, luz, no te avergüences! Qué, si, hermana, con tanta belleza, eres una artesana para cantar, - ¡Después de todo, si tuviéramos un pájaro real! ” La cabeza de Veschunya daba vueltas de alabanza. Con alegría, su aliento se hundió. Y a la amigable Lisitsyna, las palabras del Cuervo le arrojaron por toda la garganta: se le cayó el queso, tal fue el engaño con él ".
str2 = "Y los pájaros se aferran a la artesanía de los hombres. Un cuervo una vez llevó un queso a un cous y se sentó en un roble. Sí, simplemente no he comido un poquito. El zorro vio un pedazo en su boca y ella piensa: “¡Le daré jugo al cuervo! Aunque no llegaré allí, obtendré esta pieza, Oak, no importa cuán alto ". "Es genial", dice Fox, "¡Amiga, Funnel, llamada hermana!" Eres un pájaro hermoso! Qué tipo de tijeras, qué calcetín, Y puedes decirte sin hipocresía, ¿Qué eres más que nada, mi pequeña luz, bien! Y el loro no es nada ante ti, alma, ¡Más de cien veces más hermosas son tus plumas de pavo real! (Las alabanzas agradables no son halagadoras). "¡Oh, si todavía supieras cantar, entonces no habría para ti un pájaro así en el mundo!" El cuervo abrió más el cuello para ser un ruiseñor, "Y al queso", piensa, "y después de eso comeré". ¡En este momento no estoy hablando de una fiesta! " Abrí la boca y esperé el ayuno. Solo ve el final de la cola de Lisitsyn. Quería cantar, no cantaba, quería comer, no comía.
La razón es que el queso ya no está allí. El queso se cayó de la compañía. Fox para el almuerzo.
StrCompare (str1, str2) da el resultado 0.5590062, ¡así que hay una similitud de trama!