Tugas membandingkan string serupa sering dijumpai dalam praktiknya: Saya pribadi baru-baru ini menjumpainya ketika mencoba mengimpor alamat surat dari satu program ke program lain.
Misalnya, satu alamat mungkin terlihat seperti "Tverskaya oblast, Kashin g, Sovetskaya ul, 1, 5", dan lainnya - seperti "Tver oblast; kota Kashin; Jalan Sovetskaya; rumah 1; apartemen 5 ". Apakah garis-garis ini serupa dan berapa? Tentu mirip. Dan dengan "mata telanjang" struktur mereka terlihat: wilayah - pemukiman - jalan - rumah - apartemen. Adalah logis bahwa untuk mengatasi gangguan garis menjadi kelompok adalah penting; yaitu, kita tidak harus membandingkan "dua sereal" dari kata-kata yang serupa (di mana satu "bubur" terdiri dari kata-kata dari baris pertama, dan yang kedua dari kata-kata dari baris kedua), melainkan, melakukan perbandingan "grup" kata-kata dari baris pertama dengan kata-kata dari baris kedua. Kriteria untuk pemisahan menjadi kelompok-kelompok juga diperiksa: pada baris pertama, pemisah kelompok adalah ",", dan pada yang kedua - "; ".
Pada saat yang sama, ada garis di mana tidak ada pengelompokan eksplisit terlihat. Misalnya, ambil "klasik": "Ketika tidak ada kesepakatan dalam kawan-kawan, pekerjaan mereka tidak akan berjalan lancar, dan itu tidak akan berhasil - hanya tepung." Dan baris kedua: "Monyet Prankish, Donkey, Goat, dan kaki pekuk beruang Teddy mulai memainkan kuartet." Jelas garis-garisnya berbeda (dan bahkan moral dari dongeng ini berbeda, walaupun paralelnya dapat ditemukan).
Tugas yang dimaksud bukanlah hal baru. Ada algoritma (terkadang sangat kompleks) yang mencoba menyelesaikannya, dan bahkan terkadang berhasil menyelesaikannya. Saya mengusulkan satu kotak algoritma lagi. Ketika mengkompilasinya, saya melanjutkan dari prinsip-prinsip berikut:
- kesederhanaan memanggil fungsi perbandingan;
- kemudahan implementasi;
- fleksibilitas yang cukup.
Selain itu, algoritma ini diterapkan pada VBA Excel, oleh karena itu sangat "demokratis" dan dapat digunakan di mana-mana: Excel tidak hanya ada di antara perangkat lunak berbagai komputer "dengan sendirinya", tetapi juga data dari semua jenis DBMS dan aplikasi yang diekspor ke sana.
Jadi mari kita mulai.
Fungsi perbandingan disebut StrCompare. Ini akan memiliki 4 argumen, dua di antaranya adalah opsional: str1 baris pertama, str2 baris kedua, pemisah grup dari div1 baris pertama dan pemisah grup dari div2 baris kedua. Jika div1 atau div2 dihilangkan, maka pemisah default adalah "|". "|" dipilih karena tidak mungkin terjadi pada garis "rata-rata", dan karenanya dapat digunakan untuk membandingkan garis monolitik (tidak dapat dikelompokkan). Garis monolitik semacam itu juga dapat dianggap sebagai garis yang terdiri dari satu kelompok. Yaitu, tajuk fungsi perbandingan terlihat seperti ini:
Public Function StrCompare(str1 As String, str2 As String, Optional div1 As String = "|", Optional div2 As String = "|") As Single
Tunggal - karena hasil dari fungsi akan menjadi angka yang menunjukkan tingkat kesamaan string yang dibandingkan.
Semua grup baris 1 secara berurutan dibandingkan dengan semua grup baris 2 kata demi kata, dan jumlah kata yang cocok di setiap pasangan grup dipertimbangkan. Untuk setiap grup dari baris 1, “grup terbaik” dari baris 2 akhirnya dipilih (yaitu, grup yang paling cocok). Kecocokan untuk setiap pasangan kata diperiksa untuk kata dengan panjang minimum: yaitu, "street = street", dan "g = city". Aturan ini tidak berlaku untuk angka: mis. 200 <> 20. Saat memilih kata, semua "karakter tidak penting" dalam grup hanyalah pemisah kata, tetapi mereka sendiri diabaikan, yaitu, kata-kata hanya dapat terdiri dari karakter WordSymbols = "0123456789ABBGDEJEZLKLMNOPRSTUFKHCHSHCHYSYEYABCDEFGHIJKLM Dapat dipahami bahwa kasus tidak diperhitungkan.
Untuk mencari kata yang cocok dalam grup saat ini dari baris kedua, metode pembagian setengah cepat digunakan (tetapi sedikit dimodernisasi dibandingkan dengan yang "klasik", karena pertandingan diperiksa dengan metode di atas). Dan karena operasi metode setengah divisi memerlukan array yang diurutkan, algoritma pengurutan cepat juga digunakan.
Hasil dari fungsi StrCompare adalah hasil dari membagi jumlah kata yang cocok dengan total jumlah kata dalam baris 1 dan 2:
StrCompare = (da * 2) / ((kon1_2 - nach1_2 + 1) * (kon1_1 - nach1_1 + 1) + (kon2_2 - nach2_2 + 1) * (kon2_1 - nach2_1 + 1))
Di sini, misalnya, kon1_2 adalah batas akhir array 1 (array kata yang terkandung dalam kelompok-kelompok dari baris pertama) sesuai dengan dimensi ke-2 (dimensi 1 adalah jumlah grup, dan ke-2 adalah jumlah kata dalam grup).
Saatnya memperkenalkan kode:
' "" . : '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
Tidak ada gunanya berkomentar semuanya, saya pikir: Anda dapat menavigasi dengan kode. Hanya menganalisis operasi fungsi perbandingan pada beberapa baris yang berbeda sifatnya.
- str1 = "Wilayah Tver., Kashin g, jalan Sovetskaya, 1, 5" str2 = "Wilayah Tver; kota Kashin; Jalan Sovetskaya; rumah 1; apartemen 5 ".
Pertama, bandingkan garis tidak termasuk grup:
StrCompare (str1, str2) memberikan hasil 0,8888889.
Dan sekarang mempertimbangkan:
StrCompare (str1, str2, ",", ";") - hasilnya adalah 0,8.
Seperti yang Anda lihat, kelompok lebih erat terkait dengan perbandingan; dalam hal ini, penting bagi mereka bahwa "rumah adalah rumah, dan apartemen adalah apartemen". Saat mengabaikan grup, ini tidak berperan. - str1 = "Nenek saya tinggal kambing abu-abu" str2 = "Nenek tinggal kambing abu-abu"
StrCompare (str1, str2) -> 0.6666667 - str1 = ”Ivanov Ivan Ivanovich m. Kaluga 1950 ”str2 =” Ivanov I.I. 01/20/1950 ”
StrCompare (str1, str2) -> 0.6153846 - str1 = "Ketika tidak ada kesepakatan dalam kawan-kawan, pekerjaan mereka tidak akan berhasil dengan baik, dan itu tidak akan berhasil - hanya tepung." str2 = "Monyet prank, Keledai, Kambing dan kaki pengekek beruang Teddy mulai memainkan kuartet."
StrCompare (str1, str2) -> 0 - str1 = ”Sesuai dengan paragraf 1 Seni. 540 dari Kode Sipil Federasi Rusia dalam hal ketika pelanggan berdasarkan perjanjian pasokan listrik adalah warga negara yang menggunakan energi untuk konsumsi dalam negeri, kontrak dianggap selesai sejak pelanggan benar-benar terhubung ke jaringan. Menurut Bagian 1 dari Pasal 153 Kode Perumahan Federasi Rusia, warga negara wajib membayar tepat waktu dan sepenuhnya membayar biaya perumahan dan utilitas. | Pada periode dari "____" _________ 2017 hingga "____" __________ 2017, pemasok Penjamin mensuplai listrik kepada Anda dalam jumlah ______________________. Sehubungan dengan pelanggaran kewajiban Anda untuk membayar energi listrik, yang mengarah pada pembentukan utang konsumen kepada pemasok penjaminan dalam jumlah lebih dari 2 periode penyelesaian, tindakan telah diambil untuk membatasi tempat tinggal Konsumen dengan mengorbankan pemasok Jaminan / dimulainya kembali penyediaan layanan utilitas untuk pasokan listrik. | Sesuai dengan ayat 121 (1) Peraturan untuk penyediaan layanan utilitas untuk pemilik dan pengguna bangunan di gedung multi-apartemen x dan perumahan bangunan, disetujui dengan Keputusan Pemerintah 06.05.2011g. No. 354, biaya kontraktor terkait dengan pengenalan pembatasan, penangguhan, dan dimulainya kembali penyediaan layanan utilitas kepada konsumen-debitur diganti dengan biaya konsumen sehubungan dengan tindakan yang diambil. jumlah pemasok ______________________________________________. | Berdasarkan hal tersebut di atas, FE TverAtomEnergoSbyt meminta Anda membayar utang untuk tindakan pembatasan / perpanjangan layanan kota untuk listrik dalam jumlah _____________________ rubel. pada detail berikut dengan nomor akun pribadi dan tujuan pembayaran: "
str2 = ”“ ____ ”__________ 2017 antara JSC AtomEnergoSbyt - Penyedia Jaminan dan _____________________ - Konsumen menyimpulkan perjanjian pasokan energi No. ___________________, berlaku selama _________________ tahun, dengan ketentuan perpanjangan lebih lanjut (klausul 8.1 perjanjian, pasal 540 dari Kode Sipil Federasi Rusia) ), sesuai dengan paragraf 1.1. yang dilakukan oleh pemasok penjamin untuk menjual energi listrik (daya), serta secara mandiri atau melalui pihak ketiga untuk menyediakan layanan dan layanan transmisi tenaga listrik, yang ketentuannya merupakan bagian integral dari proses penyediaan energi listrik kepada konsumen, dan Pembeli berkewajiban untuk membayar energi listrik yang dibeli (daya) . Berkaitan dengan pelanggaran oleh Konsumen atas kewajibannya untuk membayar energi listrik (klausul 5.2. Dari perjanjian pasokan listrik No. __________________ dari ___________), yang menyebabkan pembentukan utang konsumen kepada pemasok penjamin dalam jumlah lebih dari satu periode tagihan terkait dengan fasilitas jaringan listrik konsumen. -_________________ tindakan diambil untuk membatasi / melanjutkan rezim konsumsi energi sesuai dengan Aturan untuk pembatasan penuh dan (atau) sebagian rezim konsumsi listrik, disetujui oleh Keputusan Pemerintah Federasi Rusia tanggal 04.05.2012 No. 442 (selanjutnya - Peraturan). Menurut paragraf 24 Peraturan, konsumen berkewajiban untuk memberikan kompensasi kepada kontraktor atas biaya tindakan untuk memperkenalkan pembatasan dan pemulihan rezim konsumsi energi listrik berikutnya. | Biaya pengeluaran pemasok Jaminan untuk pembayaran tindakan untuk memperkenalkan pembatasan dan pemulihan rezim konsumsi energi listrik selanjutnya adalah ______________________________________. | dari hal tersebut di atas, OP "TverAtomEnergoSbyt" meminta Anda untuk membayar biaya pemasok Penjamin untuk tindakan terbatas pada Modus w / melanjutkan konsumsi daya listrik dalam jumlah _______________ rubel. untuk perincian berikut dengan jumlah kontrak dan tujuan pembayaran: | Tujuan pembayaran: pembayaran pembatasan / dimulainya kembali rezim konsumsi energi listrik berdasarkan kontrak No. ____________ ”
Di sini str1 dan str2 adalah fragmen dari dokumen yang sangat mirip (perjanjian pasokan energi untuk individu dan badan hukum, masing-masing). Untuk "penilaian kasar" kesamaan dokumen, Anda dapat menggunakan perbandingan tanpa grup StrCompare (str1, str2, "*", "*") (karakter "|" tidak cocok dalam kasus ini, karena digunakan dalam baris asli untuk memecahnya. kelompok), yang menunjukkan kemiripan yang layak yaitu 0,75 (mis., dokumen jelas memiliki sifat yang sama!). Dan untuk konkretisasi kesamaan, kami menggunakan pengelompokan: StrCompare (str1, str2, "|", "|") (atau hanya StrCompare (str1, str2)). Hasil: 0,3790227.
Dan sekarang, mungkin contoh yang paling menarik. Plot dongeng tentang gagak dan rubah telah dikenal sejak zaman Aesop. Menggunakan StrCompare, bandingkan dua dongeng: versi klasik oleh I.A. Krylova dan kurang dikenal dari A.P. Sumarokova:
str1 = ”Berapa kali mereka mengulangi dunia, pujian itu jahat, berbahaya; tetapi tidak untuk masa depan, Dan di dalam hati seorang penyanjung akan selalu menemukan sudut. Di suatu tempat ke Vorone, Tuhan mengirim sepotong keju; Menumpuk di Spruce Crow, Sarapan sudah cukup, Ya, bijaksana, dan aku menyimpan keju di mulutku. Untuk kemalangan itu, si Rubah berlari mendekat; Tiba-tiba, roh jahat Lisa berhenti: rubah melihat keju, rubah menangkap keju. Jinjit ke pohon berjinjit; Dia memelintir ekornya, tidak mengalihkan pandangannya dari Gagak, dan berbicara dengan sangat manis, bernapas sedikit: “Ya ampun, betapa bagus! Sungguh leher, sungguh mata! Terus terang dong dong! Apa pearshki! apa kaus kaki! Dan, benar, malaikat itu harus bersuara! Bernyanyilah, ringan, jangan malu! Bagaimana, jika, Saudari, Dengan keindahan seperti itu, Anda adalah pengrajin wanita yang bernyanyi, - Lagipula, jika kita memiliki burung raja! ” Kepala Veschunya berputar-putar dengan pujian, Dengan sukacita, nafasnya mereda, - Dan bagi Lisitsyna yang ramah, kata-kata sang Raven melemparkan ke seluruh tenggorokannya: Keju jatuh - seperti kecurangan dengannya. "
str2 = ”Dan burung-burung memegang kerajinan manusia. Seekor burung gagak membawa keju ke cous dan duduk di pohon oak. Ya, hanya belum makan sedikit. Rubah melihat sepotong di mulutnya, dan dia berpikir: "Aku akan memberikan jus gagak! Meskipun saya tidak akan sampai di sana, saya akan mendapatkan bagian ini, Oak tidak peduli seberapa tinggi. " "Luar biasa," kata Fox, "Teman, Saluran, bernama saudara perempuan!" Kamu adalah burung yang cantik! Gunting macam apa, kaus kaki apa, dan kau bisa memberitahumu tanpa kemunafikan, Apa yang lebih penting darimu, cahaya kecilku, bagus! Dan burung beo itu tidak ada apa-apanya di hadapan Anda, jiwa, Lebih dari seratus kali lebih indah adalah bulu merak Anda! ” (Pujian yang menyenangkan tidak menyanjung). "Oh, jika kamu masih tahu cara bernyanyi, Jadi tidak akan ada bagimu seperti burung di dunia!" Burung gagak membuka lehernya lebih lebar menjadi burung bulbul, "Dan untuk keju," pikirnya, "dan setelah itu aku akan makan." Saat ini saya tidak berbicara tentang pesta! " Aku membuka mulut dan menunggu puasa. Dia hanya melihat ujung ekor Lisitsyn. Saya ingin bernyanyi, saya tidak bernyanyi, saya ingin makan, saya tidak makan.
Alasannya, keju sudah tidak ada lagi. Keju jatuh dari perusahaan, - Fox untuk makan siang. "
StrCompare (str1, str2) memberikan hasil 0,5590062 - jadi ada kesamaan plot!