Uzyskiwanie najbliższego ciągu pasującego

Potrzebuję sposobu na porównanie wielu ciągów do ciągu testowego i zwrócenie ciągu, który jest do niego podobny:

TEST STRING: THE BROWN FOX JUMPED OVER THE RED COW

CHOICE A   : THE RED COW JUMPED OVER THE GREEN CHICKEN
CHOICE B   : THE RED COW JUMPED OVER THE RED COW
CHOICE C   : THE RED FOX JUMPED OVER THE BROWN COW

(Jeśli zrobiłem to poprawnie) Najbliższym ciągiem do „TEST STRING” powinien być „CHOICE C”. Jak najłatwiej to zrobić?

Planuję zaimplementować to w wielu językach, w tym VB.net, Lua i JavaScript. W tym momencie pseudo kod jest akceptowalny. Jeśli możesz podać przykład dla określonego języka, to też jest to mile widziane!

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.

Ten problem pojawia się cały czas w bioinformatyce. Przyjęta powyżej odpowiedź (która była świetna) jest znana w bioinformatyce jako algorytm Needleman-Wunsch (porównaj dwa ciągi) i Smith-Waterman (znajdź przybliżony podciąg w dłuższym ciągu). Działają świetnie i od dziesięcioleci są końmi roboczymi.

Ale co jeśli masz milion ciągów do porównania? To biliony porównań parami, z których każde to O (n * m)! Nowoczesne sekwencery DNA z łatwością generują miliard krótkich sekwencji DNA, każda o długości około 200 „liter” DNA. Zazwyczaj chcemy znaleźć dla każdego takiego ciągu najlepsze dopasowanie do ludzkiego genomu (3 miliardy liter). Oczywiście algorytm Needlemana-Wunscha i jego krewni nie zadziałają.

Ten tak zwany „problem wyrównania” jest dziedziną aktywnych badań. Najpopularniejsze algorytmy są obecnie w stanie znaleźć niedokładne dopasowania między 1 miliardem krótkich łańcuchów a ludzkim genomem w ciągu kilku godzin na rozsądnym sprzęcie (powiedzmy, osiem rdzeni i 32 GB pamięci RAM).

Większość z tych algorytmów działa poprzez szybkie znajdowanie krótkich dopasowań ścisłych (nasion), a następnie rozszerzenie ich do pełnego ciągu przy użyciu wolniejszego algorytmu (na przykład Smith-Waterman). Powodem tego jest fakt, że naprawdę interesuje nas tylko kilka bliskich meczów, więc opłaca się pozbyć 99,9 ...% par, które nie mają ze sobą nic wspólnego.

W jaki sposób znalezienie dokładnych dopasowań pomaga znaleźć niedokładne dopasowania? Powiedzmy, że dopuszczamy tylko jedną różnicę między zapytaniem a celem. Łatwo zauważyć, że ta różnica musi występować w prawej lub lewej połowie zapytania, a więc druga połowa musi dokładnie pasować. Pomysł ten można rozszerzyć na wiele niedopasowań i jest on podstawą algorytmu ELAND powszechnie stosowanego w sekwencerach DNA Illumina.

Istnieje wiele bardzo dobrych algorytmów do dokładnego dopasowywania ciągów. Biorąc pod uwagę ciąg zapytania o długości 200 i ciąg docelowy o długości 3 miliardów (ludzki genom), chcemy znaleźć dowolne miejsce w celu, w którym istnieje podłańcuch o długości k, który dokładnie odpowiada podłańcuchowi zapytania. Prostym podejściem jest rozpoczęcie od indeksowania celu: weź wszystkie podciągi długości K, umieść je w tablicy i posortuj. Następnie weź każdy podciąg długości kw kwerendy i przeszukaj posortowany indeks. Sortowanie i wyszukiwanie można przeprowadzić w czasie O (log n).

Ale przechowywanie może stanowić problem. Indeks celu o wartości 3 miliardów liter musiałby zawierać 3 miliardy wskaźników i słowa o długości 3 miliardów K. Wydaje się, że trudno to zmieścić w mniej niż kilkudziesięciu gigabajtach pamięci RAM. Ale o dziwo możemy znacznie skompresować indeks, używając transformacji Burrowsa-Wheelera , i nadal będzie on wydajnie sprawdzany. Indeks ludzkiego genomu mieści się w mniej niż 4 GB pamięci RAM. Ten pomysł jest podstawą popularnych algorytmów wyrównujących sekwencje, takich jak Bowtie i BWA .

Alternatywnie możemy użyć tablicy sufiksów , która przechowuje tylko wskaźniki, ale reprezentuje jednoczesny indeks wszystkich sufiksów w ciągu docelowym (w zasadzie jednoczesny indeks dla wszystkich możliwych wartości k; to samo dotyczy transformacji Burrowsa-Wheelera ). Indeks tablicy sufiksów ludzkiego genomu zajmie 12 GB pamięci RAM, jeśli użyjemy wskaźników 32-bitowych.

Powyższe linki zawierają bogactwo informacji i linki do podstawowych artykułów naukowych. Łącze ELAND prowadzi do pliku PDF z przydatnymi rysunkami ilustrującymi związane z nim koncepcje i pokazuje, jak radzić sobie z wstawieniami i usunięciami.

Wreszcie, podczas gdy algorytmy te zasadniczo rozwiązały problem (ponownego) sekwencjonowania pojedynczych ludzkich genomów (miliard krótkich łańcuchów), technologia sekwencjonowania DNA poprawia się nawet szybciej niż prawo Moore'a, a my szybko zbliżamy się do zbiorów danych o wartości trylionów liter. Na przykład obecnie trwają projekty sekwencjonowania genomów 10 000 gatunków kręgowców , każdy o długości około miliarda liter. Oczywiście będziemy chcieli wykonać niedokładne dopasowanie par w danych ...

Podważam, że wybór B jest bliższy ciągowi testowemu, ponieważ to tylko 4 znaki (i 2 usuwa) z oryginalnego ciągu. Podczas gdy widzisz C jako bliżej, ponieważ obejmuje zarówno brązowy, jak i czerwony. Miałby jednak większą odległość edycji.

Istnieje algorytm o nazwie Levenshtein Distance, który mierzy odległość edycji między dwoma wejściami.

Oto narzędzie do tego algorytmu.

1. Wybór stawek A w odległości 15.
2. Wybór stawek B w odległości 6.
3. Wybór stawek C w odległości 9.

EDYCJA: Przepraszam, ciągle miksuję łańcuchy w narzędziu levenshtein. Zaktualizowano w celu poprawienia odpowiedzi.

Implementacja Lua, dla potomności:

function levenshtein_distance(str1, str2)
    local len1, len2 = #str1, #str2
    local char1, char2, distance = {}, {}, {}
    str1:gsub('.', function (c) table.insert(char1, c) end)
    str2:gsub('.', function (c) table.insert(char2, c) end)
    for i = 0, len1 do distance[i] = {} end
    for i = 0, len1 do distance[i][0] = i end
    for i = 0, len2 do distance[0][i] = i end
    for i = 1, len1 do
        for j = 1, len2 do
            distance[i][j] = math.min(
                distance[i-1][j  ] + 1,
                distance[i  ][j-1] + 1,
                distance[i-1][j-1] + (char1[i] == char2[j] and 0 or 1)
                )
        end
    end
    return distance[len1][len2]
end

Ten post może Cię zainteresować.

http://seatgeek.com/blog/dev/fuzzywuzzy-fuzzy-string-matching-in-python

Fuzzywuzzy to biblioteka Pythona, która zapewnia łatwe pomiary odległości, takie jak odległość Levenshteina do dopasowywania ciągów. Jest zbudowany na difflib w standardowej bibliotece i będzie korzystał z implementacji języka C Python-levenshtein, jeśli jest dostępny.

http://pypi.python.org/pypi/python-Levenshtein/

Ta biblioteka może być pomocna! http://code.google.com/p/google-diff-match-patch/

Jest obecnie dostępny w Javie, JavaScript, Dart, C ++, C #, Objective C, Lua i Python

Działa też całkiem dobrze. Używam go w kilku moich projektach Lua.

I nie sądzę, że przeniesienie go na inne języki byłoby zbyt trudne!

Jeśli robisz to w kontekście wyszukiwarki lub nakładki na bazę danych, możesz rozważyć użycie narzędzia takiego jak Apache Solr z wtyczką ComplexPhraseQueryParser . Ta kombinacja umożliwia wyszukiwanie według indeksu ciągów z wynikami posortowanymi według trafności, zgodnie z odległością Levenshteina.

Używaliśmy go w stosunku do dużej kolekcji artystów i tytułów piosenek, gdy nadchodzące zapytanie może zawierać jedną lub więcej literówek, i zadziałało całkiem nieźle (i niezwykle szybko, biorąc pod uwagę, że kolekcje są w milionach ciągów).

Dodatkowo za pomocą Solr możesz wyszukiwać na podstawie indeksu na żądanie za pomocą JSON, więc nie będziesz musiał wymyślać rozwiązania dla różnych języków, na które patrzysz.

Bardzo, bardzo dobrym zasobem dla tego rodzaju algorytmów jest Simmetrics: http://sourceforge.net/projects/simmetrics/

Niestety nie ma wspaniałej strony internetowej zawierającej dużo dokumentacji :( W przypadku ponownego uruchomienia jej poprzedni adres to: http://www.dcs.shef.ac.uk/~sam/simmetrics.html

Voila (dzięki uprzejmości „Wayback Machine”): http://web.archive.org/web/20081230184321/http://www.dcs.shef.ac.uk/~sam/simmetrics.html

Możesz przestudiować źródło kodu, istnieją dziesiątki algorytmów dla tego rodzaju porównań, każdy z innym kompromisem. Implementacje są w Javie.

Aby efektywnie przesłać zapytanie do dużego zestawu tekstu, możesz użyć koncepcji Edytuj odległość / Prefiks Edytuj odległość.

Edytuj odległość ED (x, y): minimalna liczba rygli, które można uzyskać od terminu x do terminu y

Ale obliczanie ED między każdym terminem a tekstem zapytania wymaga dużych nakładów i czasu. Dlatego zamiast obliczać ED dla każdego terminu w pierwszej kolejności, możemy wyodrębnić możliwe pasujące terminy przy użyciu techniki o nazwie Indeks Qgram. a następnie zastosuj obliczenia ED na tych wybranych warunkach.

Zaletą techniki indeksu Qgram jest obsługa wyszukiwania rozmytego.

Jednym z możliwych sposobów dostosowania indeksu QGram jest zbudowanie indeksu odwróconego za pomocą Qgrams. Tam przechowujemy wszystkie słowa, które składają się na konkretny Qgram, pod tym Qgramem (zamiast przechowywania pełnego łańcucha możesz użyć unikalnego identyfikatora dla każdego łańcucha). W tym celu można użyć struktury danych mapy drzewa w Javie. Poniżej znajduje się mały przykład przechowywania terminów

col: col mbia, col ombo, gan col a, ta col ama

Następnie, podczas zapytania, obliczamy liczbę wspólnych Qgramów między tekstem zapytania a dostępnymi terminami.

Example: x = HILLARY, y = HILARI(query term)
Qgrams
$$HILLARY$$ -> $$H, $HI, HIL, ILL, LLA, LAR, ARY, RY$, Y$$
$$HILARI$$ -> $$H, $HI, HIL, ILA, LAR, ARI, RI$, I$$
number of q-grams in common = 4

wspólna liczba q-gramów = 4.

W przypadku terminów o dużej liczbie typowych Qgramów obliczamy ED / PED względem terminu zapytania, a następnie sugerujemy to użytkownikowi końcowemu.

Implementację tej teorii można znaleźć w następującym projekcie (patrz „QGramIndex.java”). Możesz zadawać pytania. https://github.com/Bhashitha-Gamage/City_Search

Aby dowiedzieć się więcej o Edycji odległości, prefiksie Edycja odległości Indeks Qgram, obejrzyj następujący film prof. Dr Hannah Bast https://www.youtube.com/embed/6pUg2wmGJRo (Lekcja zaczyna się od 20:06)

Problem jest trudny do wdrożenia, jeśli dane wejściowe są zbyt duże (powiedzmy miliony ciągów). Użyłem elastycznego wyszukiwania, aby to rozwiązać.

Szybki start: https://www.elastic.co/guide/en/elasticsearch/client/net-api/6.x/elasticsearch-net.html

Wystarczy wstawić wszystkie dane wejściowe do DB, aby szybko wyszukać dowolny ciąg znaków na podstawie dowolnej odległości edycji. Oto fragment kodu C #, który daje listę wyników posortowanych według odległości edycji (od mniejszej do wyższej)

var res = client.Search<ClassName>(s => s
    .Query(q => q
    .Match(m => m
        .Field(f => f.VariableName)
        .Query("SAMPLE QUERY")
        .Fuzziness(Fuzziness.EditDistance(5))
    )
));

Tutaj możesz mieć Golang POC do obliczenia odległości między podanymi słowami. Możesz dostroić minDistancei differencedla innych zakresów.

Plac zabaw: https://play.golang.org/p/NtrBzLdC3rE

package main

import (
    "errors"
    "fmt"
    "log"
    "math"
    "strings"
)

var data string = `THE RED COW JUMPED OVER THE GREEN CHICKEN-THE RED COW JUMPED OVER THE RED COW-THE RED FOX JUMPED OVER THE BROWN COW`

const minDistance float64 = 2
const difference float64 = 1

type word struct {
    data    string
    letters map[rune]int
}

type words struct {
    words []word
}

// Print prettify the data present in word
func (w word) Print() {
    var (
        lenght int
        c      int
        i      int
        key    rune
    )
    fmt.Printf("Data: %s\n", w.data)
    lenght = len(w.letters) - 1
    c = 0
    for key, i = range w.letters {
        fmt.Printf("%s:%d", string(key), i)
        if c != lenght {
            fmt.Printf(" | ")
        }
        c++
    }
    fmt.Printf("\n")
}

func (ws words) fuzzySearch(data string) ([]word, error) {
    var (
        w      word
        err    error
        founds []word
    )
    w, err = initWord(data)
    if err != nil {
        log.Printf("Errors: %s\n", err.Error())
        return nil, err
    }
    // Iterating all the words
    for i := range ws.words {
        letters := ws.words[i].letters
        //
        var similar float64 = 0
        // Iterating the letters of the input data
        for key := range w.letters {
            if val, ok := letters[key]; ok {
                if math.Abs(float64(val-w.letters[key])) <= minDistance {
                    similar += float64(val)
                }
            }
        }

        lenSimilarity := math.Abs(similar - float64(len(data)-strings.Count(data, " ")))
        log.Printf("Comparing %s with %s i've found %f similar letter, with weight %f", data, ws.words[i].data, similar, lenSimilarity)
        if lenSimilarity <= difference {
            founds = append(founds, ws.words[i])
        }
    }

    if len(founds) == 0 {
        return nil, errors.New("no similar found for data: " + data)
    }

    return founds, nil
}

func initWords(data []string) []word {
    var (
        err   error
        words []word
        word  word
    )
    for i := range data {
        word, err = initWord(data[i])
        if err != nil {
            log.Printf("Error in index [%d] for data: %s", i, data[i])
        } else {
            words = append(words, word)
        }
    }
    return words

}

func initWord(data string) (word, error) {
    var word word

    word.data = data
    word.letters = make(map[rune]int)
    for _, r := range data {
        if r != 32 { // avoid to save the whitespace
            word.letters[r]++
        }

    }
    return word, nil
}
func main() {
    var ws words
    words := initWords(strings.Split(data, "-"))
    for i := range words {
        words[i].Print()
    }
    ws.words = words

    solution, _ := ws.fuzzySearch("THE BROWN FOX JUMPED OVER THE RED COW")
    fmt.Println("Possible solutions: ", solution)

}