Kaip apskaičiuoti 2 linijų atstumo panašumo matą?

Turiu apskaičiuoti panašumą tarp dviejų eilučių. Taigi, ką tiksliai turiu galvoje? Leiskite paaiškinti pavyzdžiu:

  • Dabartinis žodis: hospital
  • haspita žodis: haspita

Dabar mano tikslas yra nustatyti, kiek simbolių reikia keisti klaidingą žodį, kad gautumėte tikrąjį žodį. Šiame pavyzdyje turiu keisti dvi raides. Taigi, kokie procentai? Aš visada paimsiu tikrojo žodžio ilgį. Taigi jis tampa 2/8 = 25%, todėl šios dvi DSM linijos yra 75%.

Kaip tai pasiekti, nes našumas yra pagrindinis?

46
26 февр. MonsterMMORPG nustatė vasario 26 d 2012-02-26 17:05 '12, 5:05 val. 2012-02-26 17:05
@ 7 atsakymai

Tai, ko ieškote, vadinamas redagavimo atstumu arba Levenshteino atstumu . Vikipedijos straipsnyje paaiškinama, kaip jis apskaičiuojamas, ir toliau pateikiamas gražus pseudo kodo gabalas, padedantis lengvai koduoti šį algoritmą C #.

Čia pateikiamas įgyvendinimas iš pirmos svetainės, susietos toliau:

 private static int CalcLevenshteinDistance(string a, string b) { if (String.IsNullOrEmpty(a) || String.IsNullOrEmpty(b)) return 0; int lengthA = a.Length; int lengthB = b.Length; var distances = new int[lengthA + 1, lengthB + 1]; for (int i = 0; i <= lengthA; distances[i, 0] = i++); for (int j = 0; j <= lengthB; distances[0, j] = j++); for (int i = 1; i <= lengthA; i++) for (int j = 1; j <= lengthB; j++) { int cost = b[j - 1] == a[i - 1] ? 0 : 1; distances[i, j] = Math.Min ( Math.Min(distances[i - 1, j] + 1, distances[i, j - 1] + 1), distances[i - 1, j - 1] + cost ); } return distances[lengthA, lengthB]; } 
36
26 февр. atsakymas dasblinkenlight 26 vasaris 2012-02-26 17:10 '12, 17:10, 2012-02-26 17:10

Prieš keletą savaičių šią problemą aptariau. Kai kas nors dabar klausia, pasidalinsiu kodu. Išsamiuose bandymuose mano kodas yra maždaug 10 kartų greitesnis už C # pavyzdį Wikipedijoje, net jei nėra maksimalaus atstumo. Kai nurodytas maksimalus atstumas, šis našumas padidėja iki 30x - 100x +. Atkreipkite dėmesį į keletą pagrindinių veiklos taškų:

  • Jei jums reikia palyginti tuos pačius žodžius vėl ir vėl, pirmiausia konvertuokite žodžius sveikųjų skaičių matricomis. Damerau-Levenshtein algoritme yra daug>, <, == palyginimų ir ints palyginti daug greičiau nei chars .
  • Ji apima trumpojo jungimo mechanizmą išėjimui, jei atstumas viršija nurodytą maksimalų dydį
  • Naudokite besisukančią trijų matricų rinkinį, o ne masinę matricą, kaip ir visose kitur matytose realizacijose.
  • Įsitikinkite, kad matricos yra supjaustytos trumpesniu žodžiu.

Kodas (jis veikia taip pat, jei pakeisite int[] su String parametro deklaracijose:

border=0
 /// <summary> /// Computes the Damerau-Levenshtein Distance between two strings, represented as arrays of /// integers, where each integer represents the code point of a character in the source string. /// Includes an optional threshhold which can be used to indicate the maximum allowable distance. /// </summary> /// <param name="source">An array of the code points of the first string</param> /// <param name="target">An array of the code points of the second string</param> /// <param name="threshold">Maximum allowable distance</param> /// <returns>Int.MaxValue if threshhold exceeded; otherwise the Damerau-Leveshteim distance between the strings</returns> public static int DamerauLevenshteinDistance(int[] source, int[] target, int threshold) { int length1 = source.Length; int length2 = target.Length; // Return trivial case - difference in string lengths exceeds threshhold if (Math.Abs(length1 - length2) > threshold) { return int.MaxValue; } // Ensure arrays [i] / length1 use shorter length if (length1 > length2) { Swap(ref target, ref source); Swap(ref length1, ref length2); } int maxi = length1; int maxj = length2; int[] dCurrent = new int[maxi + 1]; int[] dMinus1 = new int[maxi + 1]; int[] dMinus2 = new int[maxi + 1]; int[] dSwap; for (int i = 0; i <= maxi; i++) { dCurrent[i] = i; } int jm1 = 0, im1 = 0, im2 = -1; for (int j = 1; j <= maxj; j++) { // Rotate dSwap = dMinus2; dMinus2 = dMinus1; dMinus1 = dCurrent; dCurrent = dSwap; // Initialize int minDistance = int.MaxValue; dCurrent[0] = j; im1 = 0; im2 = -1; for (int i = 1; i <= maxi; i++) { int cost = source[im1] == target[jm1] ? 0 : 1; int del = dCurrent[im1] + 1; int ins = dMinus1[i] + 1; int sub = dMinus1[im1] + cost; //Fastest execution for min value of 3 integers int min = (del > ins) ? (ins > sub ? sub : ins) : (del > sub ? sub : del); if (i > 1  j > 1  source[im2] == target[jm1]  source[im1] == target[j - 2]) min = Math.Min(min, dMinus2[im2] + cost); dCurrent[i] = min; if (min < minDistance) { minDistance = min; } im1++; im2++; } jm1++; if (minDistance > threshold) { return int.MaxValue; } } int result = dCurrent[maxi]; return (result > threshold) ? int.MaxValue : result; } 

Kur Swap :

 static void Swap<T>(ref T arg1,ref T arg2) { T temp = arg1; arg1 = arg2; arg2 = temp; } 
56
26 февр. Atsakymą pateikė Joshua Honig 26 vasaris. 2012-02-26 17:45 '12, 17:45, 2012-02-26 17:45

Yra daug nuotolio algoritmų, pagrįstų naudojamų linijų panašumu. Kai kurie iš čia išvardytų (bet ne išsamiai išvardytų):

Biblioteka, kurioje yra visų jų įgyvendinimas, vadinama „ SimMetrics“, kuri turi ir „Java“, ir „C #“.

31
26 февр. atsakymą pateikė Anastasiosyal , vasario 26 d. 2012-02-26 17:26 '12 at 17:26 pm 2012-02-26 17:26

Radau, kad Levenshtein ir Jaro Winkler puikiai tinka mažiems skirtumams tarp linijų, pavyzdžiui:

  • Rašybos klaidos; arba
  • person vietoj o o asmens vardu.

Tačiau lyginant kažką panašaus į antraštes, kuriose prasmingi teksto fragmentai būtų tokie patys, bet „triukšmas“ aplink kraštus, Smith-Waterman-Gotoh buvo fantastiškas:

Palyginkite šias 2 antraštes (kurios yra tos pačios, tačiau suformuluotos skirtingai nei skirtingi šaltiniai):

„Escherichia coli“ endonukleazės, kuri įveda vieną polinukleotido grandinės sutrikimą ultravioletinėje spinduliuotėje

Endonukleazė III: Escherichia coli Endonukleazė, kuri ultravioletinėje spinduliuotėje DNR įveda vieną polinukleotidinę grandinę

Ši svetainė, kurioje pateikiami algoritmų palyginimai , rodo:

  • Lowenstein: 81
  • Smith-Waterman Gotoh 94
  • Yaro Winkler 78

Jaro Winkleris ir Levenshteinas nėra tokie kompetentingi kaip Smith Waterman Gotoh, ieškodami panašumų. Jei lyginame dvi antraštes, kurios nėra to paties straipsnio, tačiau turi atitinkamą tekstą:

Riebalų apykaita aukštesnėse augaluose. . Aciltioesterazės funkcija acil-koenzimų A ir acil-acilo nešiklių baltymų metabolizme

Riebalų medžiagų apykaita aukštuose augaluose. Acilo acilo nešiklio baltymo ir <strong> acil-koenzimo A nustatymas kompleksiniame lipidų mišinyje

Yaro Winkler pateikia klaidingą rezultatą, tačiau Smith Waterman Goto:

  • Lowenstein: 54
  • Smith-Waterman Gotoh 49
  • Yaro Winkler 89

Kaip pažymėjo Anastasiosyal , SimMetrics turi šių algoritmų Java kodą. Turėjau sėkmės naudojant „ Java SmithWatermanGotoh“ kodą iš „SimMetrics“ .

10
07 июля '16 в 2:55 2016-07-07 02:55 Atsakymą davė joshweir liepos 16 d . 16:55 2016-07-07 02:55

Čia yra alternatyvus metodas:

Per ilgai komentuoti.

Tipiškas panašumų paieškos būdas yra Levenshteino atstumas ir, be abejo, biblioteka su turimu kodu.

Deja, tam reikia palyginti kiekvieną eilutę. Trumpojo jungimo skaičiavimui gali tekti parašyti specializuotą kodo versiją, jei atstumas yra didesnis už tam tikrą ribą, vis tiek turite atlikti visus palyginimus.

Kita idėja yra naudoti kai kuriuos trigramų arba n-gramų variantus. Tai yra n simbolių sekos (arba n žodžiai, arba n genominės sekos arba n nepriklausomai). Išsaugokite trigramo žemėlapius eilutėse ir pasirinkite tuos, kurie labiausiai sutampa. Tipiškas pasirinkimas n yra „3“, taigi ir pavadinimas.

Pavyzdžiui, anglų kalba turėtų šiuos trigrams:

  • Eng
  • Ngl
  • ciklooksigenazė
  • lapė
  • ish

Ir Anglijoje būtų:

  • Eng
  • Ngl
  • GLA
  • LAN
  • ir

Na, 2 iš 7 (arba 4 iš 10) yra vienodi. Jei tai tinka jums ir galite indeksuoti trigrams / eilučių lentelę ir gauti greitesnę paiešką.

Taip pat galite sujungti šią funkciją su „Levenshtein“, kad sumažintumėte bendrą palyginimą su tais, kurie turi minimalų skaičių n-gramų.

4
07 дек. Gordon Linoff atsakymas, pateiktas gruodžio 7 d 2014-12-07 02:31 '14, 2:31 am 2014-12-07 02:31

Štai mano „Damerau Levenshtein Distance“ įgyvendinimas, kuris grąžina ne tik panašumo koeficientą, bet ir grąžina klaidų vietas pataisytame tekste (ši funkcija gali būti naudojama teksto redaktoriuose). Taip pat mano įgyvendinimas palaiko įvairius klaidų svorius (pakeitimą, ištrynimą, įterpimą, perkėlimą).

 public static List<Mistake> OptimalStringAlignmentDistance( string word, string correctedWord, bool transposition = true, int substitutionCost = 1, int insertionCost = 1, int deletionCost = 1, int transpositionCost = 1) { int w_length = word.Length; int cw_length = correctedWord.Length; var d = new KeyValuePair<int, CharMistakeType>[w_length + 1, cw_length + 1]; var result = new List<Mistake>(Math.Max(w_length, cw_length)); if (w_length == 0) { for (int i = 0; i < cw_length; i++) result.Add(new Mistake(i, CharMistakeType.Insertion)); return result; } for (int i = 0; i <= w_length; i++) d[i, 0] = new KeyValuePair<int, CharMistakeType>(i, CharMistakeType.None); for (int j = 0; j <= cw_length; j++) d[0, j] = new KeyValuePair<int, CharMistakeType>(j, CharMistakeType.None); for (int i = 1; i <= w_length; i++) { for (int j = 1; j <= cw_length; j++) { bool equal = correctedWord[j - 1] == word[i - 1]; int delCost = d[i - 1, j].Key + deletionCost; int insCost = d[i, j - 1].Key + insertionCost; int subCost = d[i - 1, j - 1].Key; if (!equal) subCost += substitutionCost; int transCost = int.MaxValue; if (transposition  i > 1  j > 1  word[i - 1] == correctedWord[j - 2]  word[i - 2] == correctedWord[j - 1]) { transCost = d[i - 2, j - 2].Key; if (!equal) transCost += transpositionCost; } int min = delCost; CharMistakeType mistakeType = CharMistakeType.Deletion; if (insCost < min) { min = insCost; mistakeType = CharMistakeType.Insertion; } if (subCost < min) { min = subCost; mistakeType = equal ? CharMistakeType.None : CharMistakeType.Substitution; } if (transCost < min) { min = transCost; mistakeType = CharMistakeType.Transposition; } d[i, j] = new KeyValuePair<int, CharMistakeType>(min, mistakeType); } } int w_ind = w_length; int cw_ind = cw_length; while (w_ind >= 0  cw_ind >= 0) { switch (d[w_ind, cw_ind].Value) { case CharMistakeType.None: w_ind--; cw_ind--; break; case CharMistakeType.Substitution: result.Add(new Mistake(cw_ind - 1, CharMistakeType.Substitution)); w_ind--; cw_ind--; break; case CharMistakeType.Deletion: result.Add(new Mistake(cw_ind, CharMistakeType.Deletion)); w_ind--; break; case CharMistakeType.Insertion: result.Add(new Mistake(cw_ind - 1, CharMistakeType.Insertion)); cw_ind--; break; case CharMistakeType.Transposition: result.Add(new Mistake(cw_ind - 2, CharMistakeType.Transposition)); w_ind -= 2; cw_ind -= 2; break; } } if (d[w_length, cw_length].Key > result.Count) { int delMistakesCount = d[w_length, cw_length].Key - result.Count; for (int i = 0; i < delMistakesCount; i++) result.Add(new Mistake(0, CharMistakeType.Deletion)); } result.Reverse(); return result; } public struct Mistake { public int Position; public CharMistakeType Type; public Mistake(int position, CharMistakeType type) { Position = position; Type = type; } public override string ToString() { return Position + ", " + Type; } } public enum CharMistakeType { None, Substitution, Insertion, Deletion, Transposition } 

Šis kodas yra mano projekto dalis: „ Yandex-Linguistics.NET“ .

Aš parašiau keletą bandymų , ir man atrodo, kad šis metodas veikia.

Tačiau komentarai ir komentarai yra sveikintini.

3
18 февр. Ivan Kochurkin atsakymas vasario 18 d. 2015-02-18 17:13 '15, 17:13 2015-02-18 17:13

Štai VB.net diegimas:

 Public Shared Function LevenshteinDistance(ByVal v1 As String, ByVal v2 As String) As Integer Dim cost(v1.Length, v2.Length) As Integer If v1.Length = 0 Then Return v2.Length 'if string 1 is empty, the number of edits will be the insertion of all characters in string 2 ElseIf v2.Length = 0 Then Return v1.Length 'if string 2 is empty, the number of edits will be the insertion of all characters in string 1 Else 'setup the base costs for inserting the correct characters For v1Count As Integer = 0 To v1.Length cost(v1Count, 0) = v1Count Next v1Count For v2Count As Integer = 0 To v2.Length cost(0, v2Count) = v2Count Next v2Count 'now work out the cheapest route to having the correct characters For v1Count As Integer = 1 To v1.Length For v2Count As Integer = 1 To v2.Length 'the first min term is the cost of editing the character in place (which will be the cost-to-date or the cost-to-date + 1 (depending on whether a change is required) 'the second min term is the cost of inserting the correct character into string 1 (cost-to-date + 1), 'the third min term is the cost of inserting the correct character into string 2 (cost-to-date + 1) and cost(v1Count, v2Count) = Math.Min( cost(v1Count - 1, v2Count - 1) + If(v1.Chars(v1Count - 1) = v2.Chars(v2Count - 1), 0, 1), Math.Min( cost(v1Count - 1, v2Count) + 1, cost(v1Count, v2Count - 1) + 1 ) ) Next v2Count Next v1Count 'the final result is the cheapest cost to get the two strings to match, which is the bottom right cell in the matrix 'in the event of strings being equal, this will be the result of zipping diagonally down the matrix (which will be square as the strings are the same length) Return cost(v1.Length, v2.Length) End If End Function 
0
13 апр. atsakymą pateikė GHC balandžio 13 d 2016-04-13 10:30 '16 at 10:30 2016-04-13 10:30

Kiti klausimai apie žymes arba Užduoti klausimą