同様の文字列を比較する

同様の文字列を比較するタスクは、実際には頻繁に発生します。最近、あるプログラムから別のプログラムに電子メールアドレスをインポートしようとしたときに、私は個人的にそれに遭遇しました。



たとえば、1つの住所は「トヴェルスカヤ州、カシンg、ソヴェツカヤul、1、5」のように見え、別の住所は「トヴェルカ州、 カシン市。 ソヴェツカヤ通り; 家1; アパート5 "。 これらの行は似ていますか？ 確かに似ています。 そして、「裸の目」で彼らの構造が見える：地域-決済-通り-家-アパート。 アドレスの場合、行をグループに分割することは重要です。 つまり、類似した単語の「2つのポリッジ」を比較するべきではありません（1つの「ポリッジ」は最初の行の単語と2番目の単語の2番目の単語で構成されます）。 グループに分割するための基準も調べます。最初の行ではグループの区切り記号は「、」で、2番目の行では「-」です。 「。



同時に、明示的なグループ化が表示されない行があります。 たとえば、「クラシック」を考えてみましょう：「同志に合意がない場合、彼らの仕事はうまくいかず、うまくいきません-小麦粉だけです。」そして、2行目：「いたずらな猿、ロバ、ヤギ、不器用なクマがカルテットを演奏し始めました。 »明らかに、線は異なります（類似点はありますが、これらのf話のモラルさえ異なります）。



問題のタスクは新しいものではありません。 それを解決しようとするアルゴリズム（非常に複雑な場合もあります）があり、時にはそれをうまく解決することさえあります。 もう1つのアルゴリズムボックスを提案します。 それをコンパイルするとき、私は次の原則から進みました。

• 比較関数の呼び出しの単純さ。
• 実装の容易さ。
• 十分な汎用性。

さらに、アルゴリズムはVBA Excelに実装されているため、非常に「民主的」であり、どこでも使用できます。Excelはさまざまなコンピューターのソフトウェア間に「単独で」存在するだけでなく、さまざまなDBMSやアプリケーションからデータをエクスポートします。



それでは始めましょう。



比較関数はStrCompareと呼ばれます。 4つの引数があり、そのうち2つはオプションです。最初の行str1、2番目の行str2、最初の行div1のグループ区切り文字、2番目の行div2のグループ区切り文字。 div1またはdiv2が省略された場合、デフォルトの区切り文字は「|」です。 「|」が選択されたのは、「平均」行で発生する可能性が低いため、モノリシック（グループ化できない）行の比較に使用できるためです。 このようなモノリシック文字列は、1つのグループで構成される文字列と見なすこともできます。 つまり、比較関数のヘッダーは次のようになります。

Public Function StrCompare(str1 As String, str2 As String, Optional div1 As String = "|", Optional div2 As String = "|") As Single
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

単一-関数の結果は、比較される文字列の類似度を示す数値であるため。



行1のすべてのグループは、行2のすべてのグループと単語ごとに順次比較され、グループの各ペアで一致する単語の数が考慮されます。 行1の各グループに対して、行2の「最適なグループ」が最終的に選択されます（つまり、最も一致するグループ）。 単語の各ペアの一致は、最小の長さの単語（つまり、「street = street」および「g = city」）でチェックされます。 このルールは、数字には適用されません：200 <> 20。 単語を強調表示する場合、グループ内のすべての「重要でない文字」は単なる単語区切りですが、それら自体は無視されます。つまり、単語は文字WordSymbols = "0123456789ABBGDEJEZLKLMNOPRSTUFKHCHSHCHYSYEYABCDEFGHIJKLMNOPYRXUVXWVXXのみで構成できます。 ケースは考慮されないことが理解されます。



2行目の現在のグループで一致する単語を検索するには、高速半除算法が使用されます（ただし、上記の方法を使用して一致がチェックされるため、「クラシック」に比べてわずかに近代化されます）。 また、半除算法の操作にはソートされた配列が必要なため、高速ソートアルゴリズムも使用されます。



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は2次元の配列1（最初の行のグループに含まれる単語の配列）の最終境界です（1次元はグループの数、2次元はグループ内の単語の数です）。



コードを紹介するときです。

 ' ""   . : '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
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

すべてをコメントしても意味はありません。コードでナビゲートできます。 性質の異なる複数の行で比較関数の動作を分析するだけです。

1. str1 =” Tver region。、Kashin g、Sovetskaya street、1、5” str2 =” Tver region; カシン市。 ソヴェツカヤ通り; 家1; アパート5 "。
   
   最初に、グループを除く行を比較します。
   
   StrCompare（str1、str2）の結果は0.8888889です。
   
   そして今考慮します：
   
   StrCompare（str1、str2、”、”、”;”）-結果は0.8です。
   
   ご覧のとおり、グループはより厳密に比較に関連しています。 この場合、彼らにとって「家は家であり、アパートはアパートである」ことが重要です。 グループを無視する場合、これは役割を果たしません。
2. str1 =「昔、私の祖母は灰色のヤギに住んでいた」str2 =「昔、私の祖母は灰色のヤギに住んでいた」
   
   StrCompare（str1、str2）-> 0.6666667
3. str1 =” Ivanov Ivan Ivanovich m。 Kaluga 1950” str2 =” Ivanov I.I. 1950年1月20日 ''
   
   StrCompare（str1、str2）-> 0.6153846
4. str1 =「同志に合意がない場合、彼らの仕事はうまくいかず、うまくいきません。ただ小麦粉です。」str2 =「いたずらな猿、ロバ、ヤギ、内反足のクマがカルテットを始めました。」
   
   StrCompare（str1、str2）-> 0
5. str1 =”アートのパラグラフ1に従って。 ロシア連邦民法540条は、電力供給契約に基づく加入者が国内消費にエネルギーを使用する市民である場合、加入者が実際にネットワークに接続した瞬間から契約が成立したとみなされます。 |ロシア連邦住宅法第153条の第1部によると、市民は住宅と公共料金を全額支払う必要があります。 | 2017年の「____」_________から「____」の__________ 2017までの期間に、保証サプライヤから______________________の量の電力が供給されました。 |電気エネルギーを支払う義務の違反に関連して、消費者の施設に関連して、保証サプライヤーの費用で、保証サプライヤーに対する消費者の債務が2決済期間を超えて形成されることになり、電力供給のための公共サービスの提供の再開|アパートの建物の敷地の所有者および利用者への公共サービスの提供に関する規則の第121項（1）に従って 政府令06.05.2011gによって承認され、xおよび住宅、。 No. 354、制限の導入、消費者債務者へのユーティリティサービスの提供の一時停止および再開に関連する請負業者の費用は、示された措置が取られた消費者の費用で払い戻されるものとする。サプライヤの金額______________________________________________。|上記に基づいて、FE TverAtomEnergoSbytは、アクションに対して債務を支払うように求めます _____________________ルーブルの量の電気の自治体サービスの制限の/更新。 個人口座番号と支払いの目的に関する以下の詳細：”
   
   str2 =”“ ____” __________ 2017 JSC AtomEnergoSbyt-保証プロバイダーと_____________________-消費者は、エネルギー供給契約No. ___________________を締結し、_________________年間有効であり、その更なる延長の条件（契約の8.1条項、ロシア連邦民法540条） ）、1.1項に従います。 保証サプライヤが電気エネルギー（電力）を販売することを引き受けたほか、電力伝送サービスおよびサービスを提供するために独立してまたは第三者を通じて提供しました。 。 |消費者による電気エネルギーの支払い義務の違反に関連して（5.2。電力供給契約番号__________________の___________）、消費者の電気系統設備に関連する複数の請求期間の保証供給者への消費者延滞の形成につながった-_________________電力消費レジームの完全および（または）部分的制限に関する規則に従って、エネルギー消費レジームを制限/再開するための措置が取られました。 2012年5月4日付けのロシア連邦政府令第442号（以下-規則）により承認されました。 |規則の第24項によれば、消費者は、制限を導入するための行動のコストと電力消費のレジームの回復のために請負業者に補償する義務があります|制限を課すための行動の支払いと電力消費のレジームのその後の回復のための保証サプライヤーの費用のコストは______________________________________________。上記のうち、OP TverAtomEnergoSbytは、以下に限定されたアクションについて、保証サプライヤーの費用を支払うよう求めます。 _______________ルーブルの量のワット/再開モード消費電力。 契約の数と支払いの目的を示す以下の詳細について：|支払いの目的：制限の支払い/契約番号に基づく電気エネルギーの消費体制の再開____________”
   
   ここで、str1とstr2は非常によく似たドキュメントの断片です（それぞれ個人と法人のエネルギー供給契約）。 文書の類似性の「大まかな評価」のために、StrCompareグループ（str1、str2、” *”、” *”）なしで比較を使用できます（この場合、「|」文字は元の行で使用されるため適切ではありません）グループ）、0.75のまともな類似性が明らかになります（つまり、ドキュメントは明らかに同じ性質のものです！）。 また、類似性を具体化するために、グループ化を使用します：StrCompare（str1、str2、” |”、” |”）（または単にStrCompare（str1、str2））。 結果：0.3790227。

そして今、おそらく最も興味深い例です。 カラスとキツネに関するf話のプロットは、イソップの時代から知られています。 StrCompareを使用して、2つのf話を比較します：I.A.によるクラシックバージョン クリロバとA.P.からあまり知られていない スマロコバ：

str1 =”世界に何度も繰り返した。お世辞は卑劣で有害だ。 しかし、未来のためだけではありません。そして、心の中でお世辞は常にコーナーを見つけるでしょう。 ヴォーロンのどこかで、神はチーズを送りました。 スプルースカラスに積み上げて、朝食は準備ができていました。はい、思慮深く、口の中でチーズを保持しました。 その不幸なことに、フォックスはすぐに走りました。 突然、フォックスの安っぽい精神が止まりました。フォックスはチーズを見て、フォックスは魅了したチーズを見つけました。 ツリーへのつま先はつま先です。 彼は尻尾をひねり、カラスから目を離さず、とても優しく話し、少し呼吸をします。 なんて首、なんて目だ！ そう、そう、そう、おとぎ話！ なんてピアシキ！ なんと靴下！ そして、本当、天使には声がなければなりません！ 歌い、軽く、恥ずかしがらないでください！ 妹、こんな美しさで、あなたが歌う職人なら-あなたがキングバードだったら！」ヴェシュチュニーナは称賛から頭を向け、喜びで息を切らして、彼女はカラスを友好的なリシツィナに投げつけました。喉：チーズが落ちた-彼と一緒にそのようなチートだった。

str2 =”そして鳥は人間の技術を守ります。 カラスはかつてクスクスにチーズを運び去り、オークの上に座っていました。 はい、ほんの少し食べていません。 フォックスは彼女の口の中に一片を見ました。 そこまでは行きませんが、この作品は、オークがどんなに高くても手に入ります。」 「すごいよ」とフォックスは言います。「ボーイフレンド、ファンネル、妹という名前です！」 あなたは美しい鳥です！ どんな種類のはさみ、なんと靴下、そして偽善なくしてあなたに伝えることができます、何よりもあなたは何ですか、私の小さな光、良い！ そして、オウムはあなたの前に何もありません、魂、あなたの孔雀の羽は百倍以上美しいです！」（賞賛は私たちにとって楽しいものではありません）。 「ああ、もしあなたがまだ歌う方法を知っていたら、世界にあなたのような鳥はいないだろう！」カラスは首を広げてナイチンゲールになり、「そしてチーズに」と彼は思う。 この瞬間、それは私にとってここでのごmatter走の問題ではありません！」私は口を開けて断食を待ちました。 彼はLisitsynテールの終わりを見るだけです。 歌いたい、歌わなかった、食べたい、食べなかった。

その理由は、チーズがもう存在しないからです。 チーズは会社から落ちました-昼食にフォックス。」



StrCompare（str1、str2）は0.5590062の結果を返します-プロットの類似性があります！