Znajdź słowa w długim strumieniu znaków. Automatycznie tokenizuj

Question

Jak znaleźć właściwe słowa w długim strumieniu znaków?

Wejście:

"The revised report onthesyntactictheoriesofsequentialcontrolandstate" 

Google'a wyjściowa:

"The revised report on syntactic theories sequential controlandstate" 

(który jest na tyle blisko, biorąc pod uwagę czas, który wytwarzany one wyjście)

Jak sądzisz Google to robi? Jak zwiększyć dokładność?

Answer 1

chciałbym spróbować rekurencyjnego algorytmu takiego:

• Spróbuj wstawić spację w każdej pozycji. Jeśli lewa część jest słowem, powróć ponownie do prawej części.
• Policz liczbę poprawnych słów/liczb wszystkich słów we wszystkich końcowych wynikach. Ten z najlepszym stosunkiem jest prawdopodobnie Twoją odpowiedzią.

Na przykład, nadając mu "thesentenceisgood" by uruchomić:

thesentenceisgood 
the sentenceisgood 
    sent enceisgood 
     enceisgood: OUT1: the sent enceisgood, 2/3 
    sentence isgood 
      is good 
       go od: OUT2: the sentence is go od, 4/5 
      is good: OUT3: the sentence is good, 4/4 
    sentenceisgood: OUT4: the sentenceisgood, 1/2 
these ntenceisgood 
     ntenceisgood: OUT5: these ntenceisgood, 1/2 

Więc byś wybrał OUT3 jako odpowiedź.

Answer 2

Sprawdź algorytm korekty pisowni. Oto link do artykułu na temat algorytmu użytego w google - http://www.norvig.com/spell-correct.html. Tutaj znajdziesz a scientific paper on this topic from google.

Answer 3

Oto kod w Mathematica Zacząłem rozwijać najnowszy kodowany golf.
Jest to algorytm rekursywny o minimalnym dopasowaniu, nie chciwy. Oznacza to, że zdanie „pióro jest mighter niż miecz” (bez spacji) zwraca { "pióro jest potęga er niż miecz} :)

findAll[s_] := 
    Module[{a = s, b = "", c, sy = "="}, 
    While[ 
    StringLength[a] != 0, 
    j = ""; 
    While[(c = findFirst[a]) == {} && StringLength[a] != 0, 
    j = j <> StringTake[a, 1]; 
    sy = "~"; 
    a = StringDrop[a, 1]; 
    ]; 
    b = b <> " " <> j ; 
    If[c != {}, 
    b = b <> " " <> c[[1]]; 
    a = StringDrop[a, StringLength[c[[1]]]]; 
    ]; 
    ]; 
    Return[{StringTrim[StringReplace[b, " " -> " "]], sy}]; 
] 

findFirst[s_] := 
    If[s != "" && (c = DictionaryLookup[s]) == {}, 
    findFirst[StringDrop[s, -1]], Return[c]]; 

Wejście Próbka

ss = {"twodreamstop", 
     "onebackstop", 
     "butterfingers", 
     "dependentrelationship", 
     "payperiodmatchcode", 
     "labordistributioncodedesc", 
     "benefitcalcrulecodedesc", 
     "psaddresstype", 
     "ageconrolnoticeperiod", 
     "month05", 
     "as_benefits", 
     "fname"} 

Wyjście

twodreamstop    = two dreams top 
onebackstop    = one backstop 
butterfingers    = butterfingers 
dependentrelationship  = dependent relationship 
payperiodmatchcode  = pay period match code 
labordistributioncodedesc ~ labor distribution coded es c 
benefitcalcrulecodedesc ~ benefit c a lc rule coded es c 
psaddresstype    ~ p sad dress type 
ageconrolnoticeperiod  ~ age con rol notice period 
month05     ~ month 05 
as_benefits    ~ as _ benefits 
fname      ~ f name 

HTH

Answer 4

Spróbuj stochastyczny regularną gramatykę (odpowiednik ukrytych modeli Markowa) o następujących zasadach:

for every word in a dictionary: 
stream -> word_i stream with probability p_w 
word_i -> letter_i1 ...letter_in` with probability q_w (this is the spelling of word_i) 
stream -> letter stream with prob p (for any letter) 
stream -> epsilon with prob 1 

Prawdopodobieństwa mogłyby pochodzić ze zbioru treningowego, ale patrz poniższa dyskusja. Najbardziej prawdopodobny analizator jest obliczany przy użyciu algorytmu Viterbiego, który ma złożoność czasu kwadratowego w liczbie ukrytych stanów, w tym przypadku słownictwa, dzięki czemu można napotkać problemy z szybkością w przypadku dużych słowników. Ale co, jeśli ustawisz wszystkie p_w = 1, q_w = 1 p = 0,5. To oznacza, że ​​są to prawdopodobieństwa w sztucznym modelu językowym, w którym wszystkie słowa są równie prawdopodobne, a wszystkie nie-słowa są równie mało prawdopodobne. Oczywiście możesz lepiej posegmentować, jeśli nie używałeś tego uproszczenia, ale złożoność algorytmu znacznie się zmniejszyła. Jeśli spojrzysz na relację powtarzalności w wikipedia entry, możesz spróbować i uprościć ją w tym szczególnym przypadku.Prawdopodobieństwo parsowania viterbi do pozycji k można uprościć do VP(k) = max_l(VP(k-l) * (1 if text[k-l:k] is a word else .5^l) Możesz związać l maksymalną długością słowa i znaleźć, jeśli l litery tworzą słowo z hash. Złożoność tego jest niezależna od wielkości słownika i jest O(<text length> <max l>). Przepraszam, to nie jest dowód, tylko szkic, ale powinienem pójść. Kolejna potencjalna optymalizacja, jeśli utworzysz słownik słownika, możesz sprawdzić, czy podłańcuch jest prefiksem dowolnego poprawnego słowa. Kiedy więc wyszukujesz tekst [k-l: k] i dostajesz negatywną odpowiedź, wiesz już, że to samo dotyczy tekstu [k-l: k + d] dla dowolnego d. Aby to wykorzystać, musiałbyś znacznie zmienić rekursję, więc nie jestem pewien, czy można to w pełni wykorzystać (może zobaczyć komentarz).

Answer 5

Po wykonaniu podziału rekursywnego i wyszukiwania słownika, w celu zwiększenia jakości par słów w Twojej frazie, być może zainteresuje Cię stosowanie wzajemnych informacji o parach słów.

Zasadniczo chodzi o zestaw treningowy i znalezienie M.I. wartości par słów, które mówią ci, że Albert Simpson jest mniej prawdopodobny niż Albert Einstein :)

Możesz wypróbować wyszukiwanie Science Direct dla artykułów naukowych w tym temacie. Aby uzyskać podstawowe informacje na temat wzajemnej informacji, zobacz http://en.wikipedia.org/wiki/Mutual_information

W zeszłym roku brałem udział w frazie wyszukiwania projektu wyszukiwarki, w której próbowałem przeanalizować zbiór danych wikipedia i uszeregować każdą parę słów. Mam kod w C++, jeśli chcesz go udostępnić, jeśli możesz go znaleźć. Analizuje on wikimedia i dla każdej pary słów znajduje wzajemne informacje.