A tarefa de comparar sequências semelhantes é frequentemente encontrada na prática: eu a encontrei recentemente ao tentar importar endereços de email de um programa para outro.
Por exemplo, um endereço pode se parecer com “Tverskaya oblast, Kashin g, Sovetskaya ul, 1, 5” e outro - como “Tver oblast; a cidade de Kashin; Rua Sovetskaya; casa 1; apartamento 5 ". Essas linhas são semelhantes e quanto? Claro, semelhante. E com o "olho nu" sua estrutura é visível: região - povoado - rua - casa - apartamento. É lógico que, para endereços, essa divisão de linhas em grupos seja importante; isto é, não devemos comparar "dois cereais" de palavras semelhantes (em que um "mingau" consiste nas palavras da primeira linha e a segunda das palavras da segunda), mas sim realizar uma comparação "de grupo" das palavras da primeira linha com as palavras da segunda. O critério para dividir em grupos também é examinado: na primeira linha, o separador de grupos é “,” e na segunda - “; "
Ao mesmo tempo, existem linhas em que nenhum agrupamento explícito é visível. Por exemplo, considere os "clássicos": "Quando não há acordo entre os camaradas, o trabalho deles não será tranquilo e não dará certo - apenas farinha". E a segunda linha: "Macaco brincalhão, burro, cabra e ursinho começaram a tocar um quarteto". Obviamente as linhas são diferentes (e até a moral dessas fábulas é diferente, embora paralelos possam ser encontrados).
A tarefa em questão não é nova. Existem algoritmos (às vezes muito complexos) que tentam resolvê-lo e, às vezes, resolvê-lo com sucesso. Proponho mais uma caixa de algoritmos. Ao compilá-lo, procedi dos seguintes princípios:
- simplicidade de chamar a função de comparação;
- facilidade de implementação;
- versatilidade suficiente.
Além disso, o algoritmo é implementado no VBA Excel, portanto, é muito "democrático" e pode ser usado em qualquer lugar: o Excel não existe apenas entre os softwares de vários computadores "por si só", mas também são exportados para ele dados de todos os tipos de DBMSs e aplicativos.
Então, vamos começar.
A função de comparação é chamada StrCompare. Ele terá 4 argumentos, dois dos quais são opcionais: a primeira linha str1, a segunda linha str2, o separador de grupo da primeira linha div1 e o separador de grupo da segunda linha div2. Se div1 ou div2 forem omitidos, o separador padrão será "|". "|" escolhido porque é improvável que seja encontrado na linha "média" e, portanto, pode ser usado para comparar linhas monolíticas (não agrupáveis). Tais linhas monolíticas também podem ser consideradas linhas consistindo em um grupo. Ou seja, o cabeçalho da função de comparação fica assim:
Public Function StrCompare(str1 As String, str2 As String, Optional div1 As String = "|", Optional div2 As String = "|") As Single
Único - porque o resultado da função será um número que mostra o grau de similaridade das seqüências comparadas.
Todos os grupos da linha 1 são comparados sequencialmente com todos os grupos da linha 2, palavra por palavra, e o número de correspondências de palavras em cada par de grupos é considerado. Para cada grupo da linha 1, o “melhor grupo” é finalmente selecionado na linha 2 (ou seja, o grupo com mais correspondências). As correspondências para cada par de palavras são verificadas quanto a uma palavra com tamanho mínimo: ou seja, "rua = rua" e "g = cidade". Esta regra não se aplica a números: ou seja, 200 <> 20. Ao selecionar palavras, todos os “caracteres insignificantes” nos grupos são apenas separadores de palavras, mas eles mesmos são ignorados, ou seja, as palavras podem consistir apenas em caracteres WordSymbols = "0123456789ABBGDEJEZLKLMNOPRSTUFKHCHSHCHYSYEYABCDEFGHIJKLMNOPYRXUVXWWXX. Entende-se que o caso não é levado em consideração.
Para procurar uma palavra correspondente no grupo atual da segunda linha, é usado o método de meia divisão rápida (mas ligeiramente modernizado em comparação com o "clássico", pois as correspondências são verificadas usando o método acima). E como a operação do método de meia divisão exige matrizes classificadas, o algoritmo de classificação rápida também é usado.
O resultado da função StrCompare será o resultado da divisão do número de palavras correspondentes pelo número total de palavras nas linhas 1 e 2:
StrCompare = (da * 2) / ((kon1_2 - nach1_2 + 1) * (kon1_1 - nach1_1 + 1) + (kon2_2 - nach2_2 + 1) * (kon2_1 - nach2_1 + 1))
Aqui, por exemplo, kon1_2 é o limite final da matriz 1 (uma matriz de palavras contidas nos grupos da primeira linha) de acordo com a 2ª dimensão (a 1ª dimensão é o número de grupos e a 2ª é o número de palavras no grupo).
É hora de introduzir o 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
Não adianta comentar tudo, eu acho: você pode navegar pelo código. Basta analisar a operação da função de comparação em várias linhas de natureza diferente.
- str1 = ”região de Tver., Kashin g, rua Sovetskaya, 1, 5” str2 = ”região de Tver; a cidade de Kashin; Rua Sovetskaya; casa 1; apartamento 5 ".
Primeiro, compare as linhas excluindo grupos:
StrCompare (str1, str2) fornece o resultado 0,8888889.
E agora considerando:
StrCompare (str1, str2, ”,“, ”;“) - o resultado é 0,8.
Como você pode ver, os grupos estão mais estritamente relacionados à comparação; neste caso, é importante para eles que “a casa é a casa e o apartamento é o apartamento”. Ao ignorar grupos, isso não desempenha um papel. - str1 = ”Minha avó viveu uma cabra cinza” str2 = ”Minha avó viveu uma cabra cinza”
StrCompare (str1, str2) -> 0,66666667 - str1 = ”Ivanov Ivan Ivanovich m. Kaluga 1950 "str2 =" Ivanov I.I. 20/01/1950 ”
StrCompare (str1, str2) -> 0,6153846 - str1 = "Quando não há acordo entre os camaradas, o trabalho deles não vai dar certo e não vai dar certo - apenas farinha." str2 = "Macaco brincalhão, burro, cabra e ursinho começaram a tocar um quarteto."
StrCompare (str1, str2) -> 0 - str1 = ”De acordo com o parágrafo 1 do art. 540 do Código Civil da Federação Russa, no caso de um assinante de um contrato de fornecimento de energia ser um cidadão que utiliza energia para consumo doméstico, o contrato é considerado concluído a partir do momento em que o assinante realmente se conecta à rede. | De acordo com a Parte 1 do Artigo 153 do Código da Habitação da Federação Russa, os cidadãos são obrigados a pagar oportuna e totalmente as taxas pela habitação e serviços públicos. | No período de "____" _________ 2017 a "____" __________ 2017, o fornecedor Garantidor forneceu a você eletricidade no valor de ______________________. | Em conexão com a violação de suas obrigações de pagar por energia elétrica, o que levou à formação de dívida do consumidor com o fornecedor garantidor no valor de mais de 2 períodos de liquidação, foram tomadas ações para limitar a habitação do Consumidor às custas do fornecedor / a retomada da prestação de serviços de utilidade pública para o fornecimento de eletricidade. | De acordo com o parágrafo 121 (1) das Regras para a prestação de serviços de utilidade pública aos proprietários e usuários de instalações em edifícios com vários apartamentos. x e residenciais edifícios, aprovado pelo Decreto do Governo 06.05.2011g. No. 354, os custos do contratado relacionados à introdução da restrição, suspensão e retomada da prestação de serviços de utilidade pública ao consumidor devedor são reembolsados às custas do consumidor em relação aos quais as ações indicadas foram tomadas. | O custo do pagamento das ações para introduzir a restrição e a subsequente restauração do fornecimento de energia é para a Garantia o valor do fornecedor ______________________________________________. | Com base no exposto, a FE TverAtomEnergoSbyt solicita que você pague a dívida por ações de restrição / renovação de serviços municipais de electricidade na quantidade de _____________________ rublos. nos seguintes detalhes com o número da conta pessoal e a finalidade do pagamento: "
str2 = ”“ ____ ”__________ 2017 entre JSC AtomEnergoSbyt - Fornecedor Garantidor e _____________________ - O Consumidor celebrou um contrato de fornecimento de energia nº ___________________, válido por _________________ anos, com a condição de sua extensão adicional (cláusula 8.1 do contrato, artigo 540 do Código Civil da Federação Russa ), em conformidade com o ponto 1.1. que o fornecedor garante comprometeu-se a vender energia elétrica (energia), bem como de forma independente ou terceirizada, para fornecer serviços e serviços de transmissão de energia elétrica, cuja provisão é parte integrante do processo de fornecimento de energia elétrica ao consumidor, e o Comprador se compromete a pagar pela energia elétrica comprada (energia) . | Em conexão com a violação pelo Consumidor de suas obrigações de pagar por energia elétrica (cláusula 5.2. Do contrato de fornecimento de energia nº __________________ de ___________), o que levou à formação de dívida do consumidor com o fornecedor garante no valor de mais de um período de cobrança em relação à instalação de rede elétrica do consumidor -_________________ foram tomadas medidas para limitar / retomar o regime de consumo de energia, de acordo com as Regras para a limitação total e (ou) parcial do regime de consumo de eletricidade, aprovado pelo Decreto do Governo da Federação Russa de 05.04.2012, n. 442 (doravante - o Regulamento). | De acordo com o parágrafo 24 das Regras, o consumidor é obrigado a compensar o contratado pelo custo das ações para introduzir uma restrição e a subsequente restauração do regime de consumo de energia elétrica. | O custo das despesas do fornecedor de Garantia pelo pagamento de ações para introduzir uma restrição e a subsequente restauração do regime de consumo de energia elétrica é ______________________________________________. | Baseado em do exposto, a OP TverAtomEnergoSbyt solicita que você pague os custos do fornecedor garante por ações limitadas a Modo w / retomar o consumo de energia eléctrica no valor de _______________ rublos. pelos seguintes detalhes, com o número do contrato e a finalidade do pagamento: | Objetivo do pagamento: pagamento da restrição / retomada do regime de consumo de energia elétrica nos termos do contrato ____________ ”
Aqui str1 e str2 são fragmentos de documentos muito semelhantes (contratos de fornecimento de energia para indivíduos e entidades legais, respectivamente). Para uma "avaliação aproximada" da semelhança do documento, você pode usar uma comparação sem os grupos StrCompare (str1, str2, "*", "*") (o caractere "|" não é adequado nesse caso, porque é usado nas linhas originais para quebrá-los grupos), o que revela uma semelhança decente de 0,75 (ou seja, documentos são claramente da mesma natureza!). E para concretizar semelhanças, usamos o agrupamento: StrCompare (str1, str2, ”|”, ”|”) (ou apenas StrCompare (str1, str2)). Resultado: 0,3790227.
E agora, talvez o exemplo mais interessante. A trama da fábula sobre o corvo e a raposa é conhecida desde a época de Esopo. Usando o StrCompare, compare duas fábulas: uma versão clássica da I.A. Krylova e menos conhecido de A.P. Sumarokova:
str1 = ”Quantas vezes eles repetiram ao mundo, que a bajulação é vil, prejudicial; mas não para o futuro, e no coração um bajulador sempre encontrará um canto. Em algum lugar para Vorone, Deus enviou um pedaço de queijo; Empilhando sobre o Spruce Crow, o café da manhã estava bastante pronto, sim, atencioso, e eu mantive o queijo na boca. Para esse infortúnio, a Fox chegou perto; De repente, o espírito brega de Lisa parou: a raposa vê o queijo, a raposa captura o queijo. A ponta dos pés na árvore está na ponta dos pés; Ele torce o rabo, não tira os olhos do Corvo e fala tão docemente, respirando um pouco: “Querido, que bom! Que pescoço, que olho! Para contar, então, certo, contos de fadas! Que pearshki! que meia! E, verdade, o anjo deve ter uma voz! Cante, leve, não tenha vergonha! E se irmã, com tanta beleza, você é uma artesã para cantar: - Afinal, se tivéssemos um pássaro-rei! A cabeça de Veschunya girava com louvor. Com alegria, sua respiração afundou. E para a amiga Lisitsyna, as palavras do Corvo jogaram em sua garganta inteira: queijo caiu - esse foi o truque dele.
str2 = ”E os pássaros seguram o ofício dos homens. Um corvo uma vez levou um queijo a um cuscuz E sentou-se em um carvalho. Sim, só não comi nem um pouquinho. A raposa viu um pedaço na boca e pensa: “Vou dar o suco de corvo! Embora eu não chegue lá, vou pegar esse pedaço, Oak, não importa quão alto seja. " "É ótimo", diz Fox, "Amigo, Funil, chamado irmã!" Você é um lindo pássaro! Que tipo de tesoura, que meia, E você pode dizer sem hipocrisia, O que você é mais do que qualquer outra coisa, minha pequena luz, que bom! E o papagaio não é nada diante de você, alma. Mais de cem vezes mais belas são suas penas de pavão! (Louvores agradáveis não são lisonjeiros). "Ah, se você ainda soubesse cantar, não haveria um pássaro para você no mundo!" O corvo abriu ainda mais o pescoço para ser um rouxinol: "E para o queijo", ele pensa, "e depois comerei". Neste minuto não estou falando de um banquete! Abri a boca e esperei o jejum. Ele só vê o fim da cauda de Lisitsyn. Eu queria cantar, não cantei, queria comer, não comi.
A razão é que o queijo não está mais lá. O queijo caiu fora da empresa, Fox para o almoço.
StrCompare (str1, str2) fornece o resultado 0,5590062 - portanto, há uma semelhança na plotagem!