Uzyskiwanie najbliższego dopasowania strun

Problem ten pojawił się jakiś rok temu, gdy chodziło o wyszukanie w bazie danych różnych informacji wprowadzonych przez użytkownika informacji o platformie wiertniczej. Celem było wykonanie pewnego rodzaju rozmytego wyszukiwania ciągów, które mogłoby zidentyfikować wpis bazy danych z najczęstszymi elementami.

Część badań dotyczyła implementacji algorytmu Levenshtein distance , który określa, ile zmian należy wprowadzić do Ciągu lub frazy, aby przekształcić go w inny ciąg lub fraza.

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źć w docelowym wpisie.

Artykuł znajduje się na prywatnej stronie, więc Dołożę wszelkich starań, aby dołączyć odpowiednią treść tutaj:

Fuzzy String Matching jest procesem wykonywania ludzkiej oceny podobieństwa dwóch słów lub fraz. W wielu przypadkach, polega na identyfikacji słów lub zwrotów, które są do siebie najbardziej podobne. W tym artykule opisano wewnętrzne rozwiązanie problemu fuzzy string matching i jego przydatność w rozwiązywaniu różnych problemów, które mogą pozwolić nam zautomatyzować zadania, które wcześniej wymagały żmudnego zaangażowania użytkownika.

Wprowadzenie

Potrzeba wykonania fuzzy string matching pierwotnie powstała podczas opracowywania narzędzia walidatora Zatoki Meksykańskiej. Istniała baza znanych platformy i platformy w Zatoce Meksykańskiej, a ludzie kupujący ubezpieczenia daliby nam źle wpisane informacje o ich aktywach i musieliśmy dopasować je do bazy znanych platform. Kiedy było bardzo mało informacji podanych, najlepsze, co mogliśmy zrobić, to polegać na ubezpieczycielu, aby "rozpoznać" tego, do którego się odnosili i wywołać odpowiednie informacje. Tutaj właśnie przydaje się to zautomatyzowane rozwiązanie.

Spędziłem dzień badając metody fuzzy string matching, i w końcu natknąłem się na bardzo przydatny algorytm odległości Levenshteina na Wikipedii.

Realizacja

Po przeczytaniu o teorii stojącej za tym, wdrożyłem i znalazłem sposoby, aby go zoptymalizować. 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 metryk. Korzystając z tego, stworzyłem dwie osobne metryki do oceny podobieństwa dwóch łańcuchów. Jeden nazywam "valuePhrase" i jeden nazywam "valueWords". valuePhrase to tylko Odległość Levenshteina między tymi dwoma frazami i wartościami dzieli ciąg znaków na poszczególne słowa, na podstawie ograniczników, takich jak spacje, myślniki i cokolwiek innego, i porównuje każde słowo ze sobą, podsumowując najkrótszą odległość Levenshteina łączącą dowolne dwa słowa. Zasadniczo mierzy, czy informacje zawarte w jednym "zdaniu" są rzeczywiście zawarte w innym, tak jak permutacja słowna. Spędziłem kilka dni jako projekt poboczny wymyślając najbardziej efektywny sposób możliwe rozdzielenie ciągu znaków na podstawie ograniczników.

ValueWords, valuePhrase i funkcja Split:

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

Używając tych dwóch metryk i trzeciej, która po prostu oblicza odległość między dwoma ciągami, mam szereg zmiennych, które mogę uruchomić algorytm optymalizacji, aby osiągnąć największą liczbę dopasowań. Fuzzy string matching jest samo w sobie nauką rozmytą, a więc tworząc liniowo niezależne metryki do pomiaru ciągu podobieństwo i mając znany zestaw ciągów, które chcemy dopasować do siebie, możemy znaleźć parametry, które dla naszych konkretnych stylów ciągów dają najlepsze wyniki dopasowania rozmytego.

Początkowo celem metryki 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ą zbioru dobrze zdefiniowanych permutacji i skonstruowania ostatecznej formuły tak, że miały zwiększanie wyników wyszukiwania według potrzeb.

Na powyższym zrzucie ekranu poprawiłem swoją heurystykę, aby wymyślić coś, co czułem, że jest ładnie skalowane do mojej postrzeganej różnicy między wyszukiwanym terminem a wynikiem. Heurystyka, której użyłem dla Value Phrase w powyższym arkuszu kalkulacyjnym, to =valuePhrase(A2,B2)-0.8*ABS(LEN(B2)-LEN(A2)). Skutecznie zmniejszył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 cierpią w pełni kary, ale "frazy", które zawierają "dodatkowe informacje" (dłuższe), ale poza tym nadal w większości mają te same znaki, podlegają obniżonej karze. Użyłem funkcji Value Words tak jak jest, a następnie moja końcowa heurystyka SearchVal została zdefiniowana jako =MIN(D2,E2)*0.8+MAX(D2,E2)*0.2 - średnia ważona. Każdy z dwóch punktów był niższy ważony 80%, a 20% wyższy wynik. To była tylko heurystyka, która pasowała do mojego przypadku użycia, Aby uzyskać dobry wskaźnik dopasowania. Te wagi są coś, co można następnie dostosować, aby uzyskać najlepsze dopasuj szybkość z ich danymi testowymi.

Jak widać, dwie ostatnie metryki, które są fuzzy string matching metrics, mają już naturalną tendencję do dawania niskich wyników ciągom, które są przeznaczone do dopasowania (po przekątnej). To jest bardzo dobre.

Zastosowanie Aby umożliwić optymalizację dopasowania rozmytego, ważę każdą metrykę. W związku z tym każda aplikacja fuzzy string match może ważyć parametry inaczej. Wzór, który określa wynik końcowy jest po prostu kombinacją metryk i ich wagi:

value = Min(phraseWeight*phraseValue, wordsWeight*wordsValue)*minWeight
      + Max(phraseWeight*phraseValue, wordsWeight*wordsValue)*maxWeight
      + lengthWeight*lengthValue

Używając algorytmu optymalizacji (sieć neuronowa jest tutaj najlepsza, ponieważ jest to dyskretny, wielowymiarowy problem), celem jest teraz zmaksymalizowanie liczby meczów. Stworzyłem funkcję, która wykrywa liczbę poprawnych dopasowań każdego zestawu do siebie, co widać na tym ostatnim zrzucie ekranu. Kolumna lub wiersz otrzymuje punkt, jeśli najniższy wynik jest przypisany ciąg, który miał być dopasowane, a częściowe punkty są przyznawane, jeśli jest remis za najniższy wynik, a prawidłowy mecz jest wśród remisów dopasowanych ciągów. Następnie go zoptymalizowałem. Widać, że zielona komórka jest kolumną, która najlepiej pasuje do bieżącego wiersza, a niebieski kwadrat wokół komórki jest wierszem, który najlepiej pasuje do bieżącej kolumny. Wynik w dolnym rogu to mniej więcej liczba udanych meczów i to właśnie mówimy naszemu problemowi optymalizacji, aby zmaksymalizować.

The algorytm okazał się wspaniałym sukcesem, a parametry rozwiązania mówią wiele o tego typu problemie. Zauważysz, że zoptymalizowany wynik wynosił 44, a najlepszy możliwy wynik to 48. 5 kolumn na końcu są wabikami i nie mają żadnego dopasowania do wartości wiersza. Im więcej wabików, tym trudniej będzie znaleźć najlepsze dopasowanie.

W tym konkretnym przypadku, 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 karamy strun, które różnią się 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 nie-słowne, które po prostu wymagają mniej podstawień, ponieważ ciąg jest krótszy.

Waga słowa wynosi 1,0, podczas gdy waga frazy wynosi tylko 0,5, co oznacza, że karamy całe słowa brakujące w jednym ciągu i cenimy bardziej całe wyrażenie jest nienaruszone. Jest to przydatne, ponieważ wiele z tych ciągów ma jedno słowo wspólne (the peril), gdzie naprawdę ważne jest to, czy kombinacja (region i peril) są utrzymywane.

Wreszcie, minimalna waga jest zoptymalizowana przy 10, a maksymalna waga przy 1. Oznacza to, że jeśli najlepszy z dwóch wyników (fraza wartości i słowa wartości) nie jest bardzo dobry, mecz jest znacznie karane, ale nie znacznie karane najgorsze z dwóch wyników. Zasadniczo kładzie to nacisk na konieczność albo valueWord lub valuePhrase, aby mieć dobry wynik, ale nie oba. Coś w rodzaju mentalności "weź to, co możemy dostać".

To naprawdę fascynujące, co zoptymalizowana wartość tych 5 wag mówi o rodzaju dopasowania rozmytego ciągu. Dla zupełnie różnych praktycznych przypadków dopasowania rozmytego ciągu parametry te są bardzo różne. Używałem go do 3 oddzielnych aplikacji do tej pory.

Podczas gdy nieużywany w ostatecznej optymalizacji, arkusz porównawczy był ustalono, który dopasowuje kolumny do siebie, aby uzyskać wszystkie doskonałe wyniki 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 frazami wyszukiwania (które teoretycznie mogą być używane do kompensowania fałszywych alarmów w wynikach) {]}

Dalsze Aplikacje

To rozwiązanie może być stosowane wszędzie tam, gdzie użytkownik chce mieć system komputerowy identyfikujący ciąg znaków w zestaw strun, w których nie ma idealnego dopasowania. (Jak przybliżony vlookup dopasowania dla ciągów).

Więc co powinieneś z tego wyciągnąć, to to, że prawdopodobnie chcesz użyć kombinacji 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ż decyzja, która jest "najlepsza" jest heurystyczną (rozmytą) determinacją - będziesz musiał wymyślić zestaw wag dla wszelkich metryk, które wymyślisz, aby określić podobieństwo.

Z odpowiednim zestawem heurystyki i wag, będziesz miał swój program porównawczy szybko podejmując decyzje, które byś podjął.