مقارنة سلاسل مماثلة

غالبًا ما تتم مواجهة مهمة مقارنة السلاسل المتشابهة في الممارسة: لقد واجهتها شخصيًا مؤخرًا عند محاولة استيراد عناوين البريد من برنامج إلى آخر.

على سبيل المثال ، قد يبدو أحد العناوين مثل "تفرسكايا أوبلاست ، كاشين جي ، سوفيتسكايا ماي ، 1 ، 5" ، وآخر - مثل "تفير أوبلاست" ؛ مدينة كاشين شارع سوفيتسكايا منزل 1 ؛ شقة 5 ". هل هذه الخطوط متشابهة وكم؟ بالتأكيد ، مماثلة. ومع "العين المجردة" هيكلها واضح: المنطقة - تسوية - شارع - منزل - شقة. من المنطقي أن يكون تقسيم الخطوط إلى مجموعات أمرًا مهمًا ؛ بمعنى أنه لا ينبغي لنا مقارنة "حبيبتان" بكلمات متشابهة (حيث يتكون "عصيدة" واحدة من كلمات السطر الأول والثاني لكلمات السطر الثاني) ، بل يجب إجراء مقارنة "جماعية" للكلمات من السطر الأول مع كلمات من الثاني. يتم أيضًا فحص معيار الانقسام إلى مجموعات: في السطر الأول ، يكون فاصل المجموعات هو "،" ، وفي السطر الثاني - "؛ ".

في الوقت نفسه ، هناك خطوط لا يوجد فيها تجميع واضح للعيان. على سبيل المثال ، خذ "الكلاسيكيات": "عندما لا يكون هناك اتفاق في الرفاق ، فإن عملهم لن يسير بسلاسة ولن ينجح في ذلك - إنه مجرد دقيق". والسطر الثاني: "بدأ القرد المزعج ، حمار ، عنزة ، وتيدي بير كلوب لعب الرباعية". من الواضح أن الخطوط مختلفة (وحتى أخلاقيات هذه الخرافات مختلفة ، على الرغم من وجود أوجه تشابه).

المهمة في السؤال ليست جديدة. هناك خوارزميات (في بعض الأحيان معقدة للغاية) تحاول حلها ، وحتى في بعض الأحيان حلها بنجاح. أقترح مربع واحد أكثر الخوارزمية. عند تجميعها ، انتقلت من المبادئ التالية:

• بساطة استدعاء وظيفة المقارنة ؛
• سهولة التنفيذ ؛
• براعة كافية.

بالإضافة إلى ذلك ، يتم تنفيذ الخوارزمية على VBA Excel ، وبالتالي فهي "ديمقراطية" للغاية ويمكن استخدامها في كل مكان: لا يوجد Excel فقط بين برامج أجهزة الكمبيوتر المختلفة "في حد ذاته" ، ولكن يتم أيضًا تصدير البيانات من قواعد البيانات والتطبيقات المختلفة.

لذلك دعونا نبدأ.

تسمى وظيفة المقارنة StrCompare. ستتضمن 4 وسيطات ، اثنتان منها اختياريتان: السطر الأول str1 ، السطر الثاني str2 ، فاصل المجموعة في السطر الأول div1 وفاصل المجموعة في السطر الثاني div2. إذا تم حذف div1 أو div2 ، فسيكون الفاصل الافتراضي هو "|". "|" تم اختياره لأنه من غير المحتمل العثور عليه في السطر "المتوسط" ، وبالتالي يمكن استخدامه لمقارنة الخطوط المتجانسة (غير القابلة للتجميع). ويمكن اعتبار هذه السلاسل المتجانسة أيضًا سلاسل تتكون من مجموعة واحدة. بمعنى أن رأس دالة المقارنة يشبه هذا:

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 = "0123456789ABBGDEJEZLKLMNOPRSTUFKHCHSHCHYSYEYABABEFEFGHIJKLMX ومن المعلوم أن القضية لا تؤخذ بعين الاعتبار.

للبحث عن كلمة مطابقة في المجموعة الحالية من السطر الثاني ، يتم استخدام طريقة تقسيم النصف السريع (ولكن تم تحديثها قليلاً مقارنة بالطريقة "الكلاسيكية" ، حيث يتم التحقق من التطابقات باستخدام الطريقة أعلاه). ونظرًا لأن تشغيل طريقة القسمة النصفية يتطلب مصفوفات مرتبة ، يتم أيضًا استخدام خوارزمية الفرز السريع.

ستكون نتيجة الدالة 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 هو الحد النهائي للمصفوفة 1 (مجموعة من الكلمات الموجودة في مجموعات الصف الأول) وفقًا للبعد الثاني (البعد الأول هو عدد المجموعات ، والثاني هو عدد الكلمات في المجموعة).

حان الوقت لإدخال الرمز:

 ' ""   . : '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 = "إيفانوف إيفان إيفانوفيتش م. Kaluga 1950 "str2 =" Ivanov I.I. 01/20/1950 "
   StrCompare (str1 ، str2) -> 0.6153846
4. str1 = "عندما لا يكون هناك اتفاق في الرفاق ، فإن عملهم لن ينجح بشكل جيد ، ولن ينجح في ذلك - إنه دقيق فقط." str2 = "بدأ القرد المزعج ، والحمير ، والماعز ، والألعاب الرياضية تيدي بير باللعب الرباعي".
   StrCompare (str1 ، str2) -> 0
5. str1 = "وفقًا للفقرة 1 من الفن. 540 من القانون المدني للاتحاد الروسي في حالة ما إذا كان المشترك بموجب اتفاق إمدادات الطاقة هو مواطن يستخدم الطاقة للاستهلاك المحلي ، يعتبر العقد مبرمًا منذ اللحظة التي يتصل فيها المشترك بالشبكة فعليًا. وفقًا للجزء 1 من المادة 153 من قانون الإسكان في الاتحاد الروسي ، يتعين على المواطنين دفع رسوم السكن والمرافق في الوقت المناسب بالكامل. | في الفترة من "____" _________ 2017 إلى "____" __________ 2017 ، زودك المورد الضام بالكهرباء بمبلغ ______________________. فيما يتعلق بانتهاك التزاماتك بالدفع مقابل الطاقة الكهربائية ، مما أدى إلى تكوين دين مستهلك للمورد الضامن بمبلغ يزيد عن فترتي تسوية ، تم اتخاذ إجراءات للحد من مسكن المستهلك على حساب مورد الضمان / استئناف تقديم خدمات المرافق لإمدادات الكهرباء. | وفقًا للفقرة 121 (1) من قواعد توفير خدمات المرافق لأصحاب ومستخدمي المباني في المباني متعددة الشقق س و المباني السكنية، التي وافقت عليها المرسوم الحكومي 06.05.2011g. رقم 354 ، يتم تعويض مصاريف المقاول المتعلقة بإدخال التقييد وتعليق واستئناف تقديم خدمات المرافق إلى المستهلك - المدين على حساب المستهلك الذي اتخذت الإجراءات المشار إليها بشأنه. مبلغ المورد ______________________________________________. | بناءً على ما تقدم ، يطلب منك OP "TverAtomEnergoSbyt" سداد الدين عن الإجراءات تقييد / تجديد الخدمات البلدية للكهرباء في كمية _____________________ روبل. على التفاصيل التالية مع رقم الحساب الشخصي والغرض من الدفع: "
   str2 = "" ____ "__________ 2017 بين JSC AtomEnergoSbyt - مقدم الضمان و _____________________ - أبرم المستهلك اتفاقية إمدادات الطاقة رقم ___________________ ، صالحة لمدة _________________ سنة ، بشرط تمديدها (المادة 8.1 من الاتفاقية ، المادة 540 من القانون المدني للاتحاد الروسي ) ، وفقا للفقرة 1.1. تعهد المورد الضامن ببيع الطاقة الكهربائية (الطاقة) ، وكذلك بشكل مستقل أو من خلال أطراف ثالثة لتوفير خدمات وخدمات نقل الطاقة الكهربائية ، والتي يعد توفيرها جزءًا لا يتجزأ من عملية توفير الطاقة الكهربائية للمستهلك ، ويتعهد المشتري بدفع ثمن الطاقة الكهربائية المشتراة (الطاقة) . فيما يتعلق بانتهاك المستهلك لالتزاماته بالدفع مقابل الطاقة الكهربائية (البند 5.2 من اتفاقية تزويد الطاقة رقم __________________ بتاريخ ___________) ، والتي أدت إلى تكوين ديون المستهلك للمورد الضامن بمبلغ أكثر من فترة إعداد فواتير فيما يتعلق بمرفق الشبكة الكهربائية للمستهلك - تم اتخاذ إجراءات للحد من / استئناف نظام استهلاك الطاقة وفقًا للقواعد الخاصة بالحد الكامل و (أو) من نظام استهلاك الكهرباء ، تمت الموافقة بموجب مرسوم من حكومة الاتحاد الروسي بتاريخ 04.05.2012 رقم 442 (يشار إليه فيما بعد - القواعد). | وفقًا للفقرة 24 من القواعد ، يلتزم المستهلك بتعويض المقاول عن تكلفة الإجراءات اللازمة لإدخال قيود والاستعادة اللاحقة لنظام استهلاك الطاقة الكهربائية. | تكلفة مصاريف مورد الضمان مقابل دفع الإجراءات لإدخال قيود والاستعادة اللاحقة لنظام استهلاك الطاقة الكهربائية هي ___________________________________________________________________________ لما تقدم ، فإن OP "TverAtomEnergoSbyt" يطلب منك دفع تكاليف مورد الضمان عن الإجراءات التي تقتصر على ث / استئناف وضع استهلاك الطاقة الكهربائية في كمية _______________ روبل. للحصول على التفاصيل التالية مع رقم العقد والغرض من الدفع: | الغرض من الدفع: دفع قيود / استئناف نظام استهلاك الطاقة الكهربائية بموجب العقد رقم ____________ "
   هنا str1 و str2 هي شظايا من وثائق مشابهة جدا (اتفاقيات امدادات الطاقة للأفراد والكيانات القانونية ، على التوالي). من أجل "تقييم تقريبي" لتشابه الوثيقة ، يمكنك استخدام مقارنة بدون مجموعات StrCompare (str1 ، str2 ، "*" ، "*") (الحرف "|" غير مناسب في هذه الحالة ، لأنه يستخدم في الأسطر الأصلية لكسرها مجموعات) ، والتي تكشف عن تشابه لائق من 0.75 (أي ، الوثائق هي بوضوح من نفس الطبيعة!). وللتطابق في أوجه التشابه ، نستخدم المجموعة: StrCompare (str1 ، str2 ، "|" ، "|") (أو مجرد StrCompare (str1 ، str2)). النتيجة: 0.3790227.

والآن ، ربما المثال الأكثر إثارة للاهتمام. كانت حكاية الخرافة حول الغراب والثعلب معروفة منذ زمن إيسوب. باستخدام StrCompare ، قارن بين اثنين من الخرافات: نسخة كلاسيكية من قبل I.A. كريلوفا وأقل شهرة من A.P. Sumarokova:
str1 = "كم مرة كرروا للعالم ، أن الإطراء حقير ، ضار ؛ ولكن ليس فقط من أجل المستقبل ، وفي قلب المكان ستجد دائمًا زاوية. في مكان ما إلى فورون ، أرسل الله قطعة من الجبن. تتراكم على Spruce Crow ، كان الإفطار جاهزًا تمامًا ، نعم ، مدروس ، واحتفظت بالجبن في فمي. إلى تلك المحنة ، ركض الثعلب ؛ فجأة ، توقفت روح ليزا الجبن: الثعلب يرى الجبن ، الثعلب يلتقط الجبن. رؤوس الأصابع إلى الشجرة هي أطراف أصابعها ؛ يلف ذيله ولا يرفع عينيه عن الغراب ويتحدث بلطف شديد ويتنفس قليلاً: "عزيزي ، كم هو جيد! يا له من رقبة ، يا لها من عين! لقول ، لذلك ، حكايات خرافية! ما pearshki! يا له من جورب! وصحيح ، يجب أن يكون للملاك صوت! الغناء ، الضوء ، لا تخجل! ماذا ، إذا ، أخت ، مع هذا الجمال ، أنت حنكة تغني ، - بعد كل شيء ، إذا كان لدينا طائر ملكي! " كان رأس فيشونيا يدور مع الثناء ، وبفرح ، غرق أنفاسه - ولسيسينا الودية ، ألقيت كلمات الغراب في حنجرتها بالكامل: سقط الجبن - كان مثل هذا الغش معه. "
str2 = "وتمسك الطيور بحرفة الرجال. غراب حمل مرة جبنًا إلى عجينة وجلس على بلوط. نعم ، فقط لم تأكل قليلا. رأى الثعلب قطعة في فمها ، وهي تعتقد: "سأقدم عصير الغراب! على الرغم من أنني لن أصل إلى هناك ، إلا أنني سأحصل على هذه القطعة ، يا أوك بغض النظر عن طول القامة ". "إنها رائعة" ، كما يقول فوكس ، "صديق ، قمع ، اسمه أخت!" أنت طائر جميل! أي نوع من المقص ، يا له من جورب ، ويمكنك إخبارك دون نفاق ، ما أنت أكثر من أي شيء آخر ، يا ضوءي الصغير ، جيد! والببغاء ليس أمامك يا روح ، أكثر من مائة مرة أجمل ريش الطاووس! " (المديح لطيف لا الاغراء). "أوه ، إذا كنت لا تزال تعرف كيف تغني ، فلن يكون لك مثل هذا الطائر في العالم!" لقد فتح الغراب رقبته على نطاق أوسع ليكون عندليبًا ، "كما يعتقد ،" وبعد ذلك سوف آكل ". هذه اللحظة لا أتحدث عن وليمة! " فتحت فمي وانتظرت الصيام. يرى فقط نهاية ذيل Lisitsyn. كنت أرغب في الغناء ، لم أغني ، أردت أن آكل ، لم أكن آكل.
والسبب هو أن الجبن لم يعد هناك. سقط الجبن من الشركة ، - فوكس لتناول طعام الغداء. "

StrCompare (str1 ، str2) تعطي النتيجة 0.5590062 - لذلك هناك تشابه قطعة!