Ten problem został mi przedstawiony około rok temu, gdy chodziło o wyszukiwanie użytkowników wpisujących informacje o platformie wiertniczej w bazie danych różnych informacji. Celem było przeprowadzenie pewnego rodzaju wyszukiwania rozmytych ciągów znaków, które mogłyby zidentyfikować pozycję bazy danych za pomocą najczęściej występujących elementów.
Część badań obejmowała implementację algorytmu odległości Levenshteina , który określa, ile zmian należy wprowadzić w ciągu lub frazie, aby przekształcić go w inny ciąg lub frazę.
Implementacja, którą wymyśliłem, była stosunkowo prosta i obejmowała ważone porównanie długości dwóch fraz, liczby zmian między każdą frazą i tego, czy każde słowo można znaleźć we wpisie docelowym.
Artykuł jest na prywatnej stronie, więc dołożę wszelkich starań, aby dołączyć odpowiednią treść tutaj:
Fuzzy String Matching to proces dokonywania podobnej do ludzkiej oceny podobieństwa dwóch słów lub fraz. W wielu przypadkach wiąże się to z identyfikacją słów lub zwrotów, które są do siebie najbardziej podobne. W tym artykule opisano wewnętrzne rozwiązanie problemu dopasowywania rozmytych ciągów znaków oraz jego przydatność w rozwiązywaniu różnych problemów, które mogą pozwolić nam zautomatyzować zadania wymagające wcześniejszego zaangażowania użytkownika.
Wprowadzenie
Konieczność dopasowania rozmytych ciągów znaków pierwotnie pojawiła się podczas opracowywania narzędzia Zatoki Meksykańskiej Validator. Istniała baza danych znanej zatoki meksykańskich platform wiertniczych i platform, a ludzie kupujący ubezpieczenie podali nam źle wpisane informacje o ich aktywach i musieliśmy je dopasować do bazy danych znanych platform. Gdy podanych jest bardzo mało informacji, najlepsze, co możemy zrobić, to polegać na ubezpieczycielu, który „rozpoznaje” ten, do którego się odnosi, i przywołuje odpowiednie informacje. Tutaj przydaje się to zautomatyzowane rozwiązanie.
Spędziłem dzień badając metody dopasowywania rozmytych ciągów znaków i ostatecznie natknąłem się na bardzo przydatny algorytm odległości Levenshteina na Wikipedii.
Realizacja
Po przeczytaniu teorii leżącej u jej podstaw wdrożyłem i znalazłem sposoby jej optymalizacji. Tak wygląda mój kod w VBA:
'Calculate the Levenshtein Distance between two strings (the number of insertions,
'deletions, and substitutions needed to transform the first string into the second)
Public Function LevenshteinDistance(ByRef S1 As String, ByVal S2 As String) As Long
Dim L1 As Long, L2 As Long, D() As Long 'Length of input strings and distance matrix
Dim i As Long, j As Long, cost As Long 'loop counters and cost of substitution for current letter
Dim cI As Long, cD As Long, cS As Long 'cost of next Insertion, Deletion and Substitution
L1 = Len(S1): L2 = Len(S2)
ReDim D(0 To L1, 0 To L2)
For i = 0 To L1: D(i, 0) = i: Next i
For j = 0 To L2: D(0, j) = j: Next j
For j = 1 To L2
For i = 1 To L1
cost = Abs(StrComp(Mid$(S1, i, 1), Mid$(S2, j, 1), vbTextCompare))
cI = D(i - 1, j) + 1
cD = D(i, j - 1) + 1
cS = D(i - 1, j - 1) + cost
If cI <= cD Then 'Insertion or Substitution
If cI <= cS Then D(i, j) = cI Else D(i, j) = cS
Else 'Deletion or Substitution
If cD <= cS Then D(i, j) = cD Else D(i, j) = cS
End If
Next i
Next j
LevenshteinDistance = D(L1, L2)
End Function
Prosty, szybki i bardzo przydatny wskaźnik. Korzystając z tego, stworzyłem dwie osobne miary do oceny podobieństwa dwóch ciągów. Jeden nazywam „valuePhrase”, a drugi „valueWords”. valuePhrase to tylko odległość Levenshteina między dwiema frazami, a valueWords dzieli ciąg na pojedyncze słowa, w oparciu o ograniczniki, takie jak spacje, myślniki i wszystko, co chcesz, i porównuje każde słowo ze sobą, podsumowując najkrótsze Odległość Levenshteina łącząca dowolne dwa słowa. Zasadniczo mierzy, czy informacje w jednej „frazie” są rzeczywiście zawarte w innej, podobnie jak permutacja słowna. Spędziłem kilka dni jako projekt poboczny, wymyślając najskuteczniejszy możliwy sposób podziału łańcucha opartego na ogranicznikach.
funkcja wartości słowa, wartość frazy i funkcja podziału:
Public Function valuePhrase#(ByRef S1$, ByRef S2$)
valuePhrase = LevenshteinDistance(S1, S2)
End Function
Public Function valueWords#(ByRef S1$, ByRef S2$)
Dim wordsS1$(), wordsS2$()
wordsS1 = SplitMultiDelims(S1, " _-")
wordsS2 = SplitMultiDelims(S2, " _-")
Dim word1%, word2%, thisD#, wordbest#
Dim wordsTotal#
For word1 = LBound(wordsS1) To UBound(wordsS1)
wordbest = Len(S2)
For word2 = LBound(wordsS2) To UBound(wordsS2)
thisD = LevenshteinDistance(wordsS1(word1), wordsS2(word2))
If thisD < wordbest Then wordbest = thisD
If thisD = 0 Then GoTo foundbest
Next word2
foundbest:
wordsTotal = wordsTotal + wordbest
Next word1
valueWords = wordsTotal
End Function
''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
' SplitMultiDelims
' This function splits Text into an array of substrings, each substring
' delimited by any character in DelimChars. Only a single character
' may be a delimiter between two substrings, but DelimChars may
' contain any number of delimiter characters. It returns a single element
' array containing all of text if DelimChars is empty, or a 1 or greater
' element array if the Text is successfully split into substrings.
' If IgnoreConsecutiveDelimiters is true, empty array elements will not occur.
' If Limit greater than 0, the function will only split Text into 'Limit'
' array elements or less. The last element will contain the rest of Text.
''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
Function SplitMultiDelims(ByRef Text As String, ByRef DelimChars As String, _
Optional ByVal IgnoreConsecutiveDelimiters As Boolean = False, _
Optional ByVal Limit As Long = -1) As String()
Dim ElemStart As Long, N As Long, M As Long, Elements As Long
Dim lDelims As Long, lText As Long
Dim Arr() As String
lText = Len(Text)
lDelims = Len(DelimChars)
If lDelims = 0 Or lText = 0 Or Limit = 1 Then
ReDim Arr(0 To 0)
Arr(0) = Text
SplitMultiDelims = Arr
Exit Function
End If
ReDim Arr(0 To IIf(Limit = -1, lText - 1, Limit))
Elements = 0: ElemStart = 1
For N = 1 To lText
If InStr(DelimChars, Mid(Text, N, 1)) Then
Arr(Elements) = Mid(Text, ElemStart, N - ElemStart)
If IgnoreConsecutiveDelimiters Then
If Len(Arr(Elements)) > 0 Then Elements = Elements + 1
Else
Elements = Elements + 1
End If
ElemStart = N + 1
If Elements + 1 = Limit Then Exit For
End If
Next N
'Get the last token terminated by the end of the string into the array
If ElemStart <= lText Then Arr(Elements) = Mid(Text, ElemStart)
'Since the end of string counts as the terminating delimiter, if the last character
'was also a delimiter, we treat the two as consecutive, and so ignore the last elemnent
If IgnoreConsecutiveDelimiters Then If Len(Arr(Elements)) = 0 Then Elements = Elements - 1
ReDim Preserve Arr(0 To Elements) 'Chop off unused array elements
SplitMultiDelims = Arr
End Function
Miary podobieństwa
Korzystając z tych dwóch metryk i jednej trzeciej, która po prostu oblicza odległość między dwoma łańcuchami, mam szereg zmiennych, które mogę uruchomić algorytm optymalizacyjny, aby osiągnąć największą liczbę dopasowań. Dopasowywanie rozmytych ciągów jest samo w sobie nauką rozmytą, a zatem tworząc liniowo niezależne miary do pomiaru podobieństwa ciągów i dysponując znanym zestawem ciągów, które chcemy ze sobą dopasować, możemy znaleźć parametry, które dla naszych specyficznych stylów ciągi, dają najlepsze wyniki dopasowania rozmytego.
Początkowo celem pomiaru była niska wartość wyszukiwania dla dokładnego dopasowania i zwiększenie wartości wyszukiwania dla coraz bardziej permutowanych miar. W niepraktycznym przypadku było to dość łatwe do zdefiniowania za pomocą zestawu dobrze zdefiniowanych permutacji i zaprojektowania ostatecznej formuły, tak aby miały one pożądane zwiększenie wyników wyszukiwania.
Na powyższym zrzucie ekranu poprawiłem moją heurystykę, aby wymyślić coś, co według mnie dobrze pasuje do mojej postrzeganej różnicy między wyszukiwanym hasłem a wynikiem. Heurystyka, której użyłem Value Phrasew powyższym arkuszu kalkulacyjnym, była =valuePhrase(A2,B2)-0.8*ABS(LEN(B2)-LEN(A2)). Skutecznie zmniejszałem karę odległości Levensteina o 80% różnicy długości dwóch „fraz”. W ten sposób „zwroty” o tej samej długości ponoszą pełną karę, ale „zwroty”, które zawierają „dodatkowe informacje” (dłuższe), ale poza tym wciąż dzielą te same znaki, podlegają zmniejszonej karze. UżyłemValue Words funkcji obecnej postaci, a następnie moją ostateczną SearchValheurystykę zdefiniowano jako=MIN(D2,E2)*0.8+MAX(D2,E2)*0.2- średnia ważona. Niezależnie od tego, który z dwóch wyników był niższy, ważono 80%, a 20% wyższego wyniku. To była tylko heurystyka, która pasowała do mojego przypadku użycia, aby uzyskać dobry wskaźnik dopasowania. Wagi te można następnie dostosować, aby uzyskać najlepszy współczynnik dopasowania z danymi testowymi.
Jak widać, ostatnie dwa wskaźniki, które są rozmytymi wskaźnikami dopasowywania ciągów, mają już naturalną tendencję do dawania niskich wyników ciągom, które mają się zgadzać (w dół po przekątnej). To jest bardzo dobre.
Zastosowanie
Aby umożliwić optymalizację rozmytego dopasowania, ważę każdą metrykę. W związku z tym każda aplikacja dopasowania łańcucha rozmytego może ważyć parametry w różny sposób. Formuła, która określa końcowy wynik, jest po prostu kombinacją wskaźników i ich wag:
value = Min(phraseWeight*phraseValue, wordsWeight*wordsValue)*minWeight
+ Max(phraseWeight*phraseValue, wordsWeight*wordsValue)*maxWeight
+ lengthWeight*lengthValue
Wykorzystując algorytm optymalizacyjny (najlepiej tutaj sieć neuronowa, ponieważ jest to dyskretny, wielowymiarowy problem), celem jest teraz maksymalizacja liczby dopasowań. Stworzyłem funkcję, która wykrywa liczbę poprawnych dopasowań każdego zestawu do siebie, jak widać na ostatnim zrzucie ekranu. Kolumna lub rząd otrzymuje punkt, jeśli najniższy wynik jest przypisany ciągowi, który miał być dopasowany, a częściowe punkty są przyznawane, jeśli istnieje remis dla najniższego wyniku, a prawidłowe dopasowanie znajduje się wśród powiązanych pasujących ciągów. Następnie zoptymalizowałem to. Możesz zobaczyć, że zielona komórka to kolumna, która najlepiej pasuje do bieżącego wiersza, a niebieski kwadrat wokół komórki to wiersz, który najlepiej pasuje do bieżącej kolumny. Wynik w dolnym rogu to z grubsza liczba udanych dopasowań i to jest nasz maksymalizujący problem optymalizacji.
Algorytm był cudownym sukcesem, a parametry rozwiązania mówią wiele o tego rodzaju problemach. Zauważysz, że zoptymalizowany wynik to 44, a najlepszy możliwy wynik to 48. 5 kolumn na końcu to wabiki i nie mają żadnego dopasowania do wartości wierszy. Im więcej jest wabików, tym trudniej będzie znaleźć najlepsze dopasowanie.
W tym konkretnym przypadku dopasowania długość łańcuchów jest nieistotna, ponieważ oczekujemy skrótów, które reprezentują dłuższe słowa, więc optymalna waga dla długości wynosi -0,3, co oznacza, że nie penalizujemy łańcuchów o różnej długości. Zmniejszamy wynik w oczekiwaniu na te skróty, dając więcej miejsca na częściowe dopasowania słów, aby zastąpić dopasowania niebędące słowami, które po prostu wymagają mniejszej liczby podstawień, ponieważ łańcuch jest krótszy.
Waga słowa wynosi 1,0, podczas gdy waga frazy wynosi tylko 0,5, co oznacza, że karamy całe brakujące słowa w jednym ciągu i bardziej cenimy całą nienaruszoną frazę. Jest to przydatne, ponieważ wiele z tych ciągów ma jedno wspólne słowo (zagrożenie), a tak naprawdę liczy się to, czy zachowana jest kombinacja (region i zagrożenie).
Wreszcie, minimalna waga jest optymalizowana przy 10, a maksymalna przy 1. 1. Oznacza to, że jeśli najlepszy z dwóch wyników (wyrażenie wartości i słowa wartości) nie jest zbyt dobry, dopasowanie jest bardzo karane, ale nie to bardzo niekorzystnie wpływa na najgorszy z dwóch wyników. Zasadniczo kładzie to nacisk na wymaganie jednego z nich z valueWord lub valuePhrase mieć wynik dobry, ale nie jednocześnie. Coś w rodzaju mentalności „bierz, co możemy”.
To naprawdę fascynujące, co zoptymalizowana wartość tych 5 wag mówi o rodzaju rozmytego dopasowania łańcucha. W przypadku zupełnie różnych praktycznych przypadków dopasowywania rozmytych ciągów parametry te są bardzo różne. Do tej pory korzystałem z niego w 3 osobnych aplikacjach.
Chociaż nieużywany w końcowej optymalizacji, został utworzony arkusz porównawczy, który dopasowuje kolumny do siebie dla wszystkich doskonałych wyników w dół po przekątnej, i pozwala użytkownikowi zmieniać parametry, aby kontrolować szybkość, z jaką wyniki różnią się od 0, i zauważyć wrodzone podobieństwa między wyszukiwanymi hasłami ( które teoretycznie mogłyby być wykorzystane do zrekompensowania wyników fałszywie dodatnich)
Dalsze zastosowania
To rozwiązanie może być stosowane wszędzie tam, gdzie użytkownik chce, aby system komputerowy identyfikował ciąg w zestawie ciągów, w którym nie ma idealnego dopasowania. (Jak przybliżone dopasowanie podglądu dla ciągów).
Powinieneś więc wziąć pod uwagę, że prawdopodobnie chcesz zastosować kombinację heurystyki wysokiego poziomu (znajdowanie słów z jednej frazy w drugiej frazie, długość obu fraz itp.) Wraz z implementacją algorytmu odległości Levenshteina. Ponieważ podejmowanie decyzji, która opcja jest „najlepsza”, jest określeniem heurystycznym (rozmytym) - musisz wymyślić zestaw wag dla wszystkich wymyślonych przez ciebie wskaźników, aby określić podobieństwo.
Dzięki odpowiedniemu zestawowi heurystyk i wag będziesz mieć swój program porównawczy, który szybko podejmie decyzje.