Trova le parole in un lungo flusso di caratteri. Auto-tokenize

Question

Come troveresti le parole corrette in un lungo flusso di caratteri?

ingresso:

"The revised report onthesyntactictheoriesofsequentialcontrolandstate" 

uscita di Google:

"The revised report on syntactic theories sequential controlandstate" 

(che è abbastanza vicino considerando il tempo che hanno prodotto l'uscita)

Come pensi che Google lo fa? Come aumenteresti la precisione?

Answer 1

vorrei provare un algoritmo ricorsivo come questo:

• Provare a inserire uno spazio in ogni posizione. Se la parte sinistra è una parola, si ripresenta sulla parte destra.
• Contare il numero di parole valide/numero di parole totali in tutte le uscite finali. Quella con il miglior rapporto è probabilmente la tua risposta.

Per esempio, dandogli "thesentenceisgood" correrebbe:

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 

Così si sarebbe scegliere OUT3 come la risposta.

Answer 2

Controllare l'algoritmo di correzione ortografica. Ecco un link a un articolo sull'algoritmo utilizzato in google - http://www.norvig.com/spell-correct.html. Qui troverete a scientific paper on this topic from google.

Answer 3

Ecco un codice in Mathematica che ho iniziato a sviluppare per un recente codice golf.
È un algoritmo ricorsivo di corrispondenza minima, non avido. Ciò significa che la frase "la penna è mighter della spada" (senza spazi) restituisce { "la penna è er forza della spada} :)

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]]; 

Esempio Ingresso

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

uscita

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

Prova una grammatica regolare stocastico (equivalente a modelli di Markov nascosti) con le seguenti regole:

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 

Le probabilità potrebbero essere derivati ​​da un insieme di addestramento, ma vedere il seguente discussione. L'analisi più probabile viene calcolata utilizzando l'algoritmo di Viterbi, che ha una complessità quadratica nel numero di stati nascosti, in questo caso il tuo vocabolario, in modo da poter affrontare problemi di velocità con ampi vocabolari. Ma cosa succede se imposti tutti i p_w = 1, q_w = 1 p = .5 Il che significa che queste sono probabilità in un modello di linguaggio artificiale in cui tutte le parole sono ugualmente probabili e tutte le non parole sono ugualmente improbabili. Ovviamente potresti segmentare meglio se non usassi questa semplificazione, ma la complessità dell'algoritmo diminuisce di un bel po '. Se si osserva la relazione di ricorrenza nel wikipedia entry, è possibile provare e semplificarlo per questo caso speciale.La probabilità viterbi parsing fino alla posizione k può essere semplificata in VP(k) = max_l(VP(k-l) * (1 if text[k-l:k] is a word else .5^l) È possibile associare l alla lunghezza massima di una parola e trovare se le lettere l formano una parola con una ricerca hash. La complessità di questo è indipendente dalla dimensione del vocabolario ed è O(<text length> <max l>). Spiacente, questa non è una prova, solo uno schizzo, ma dovrebbe farti andare. Un'altra potenziale ottimizzazione, se si crea un trie del dizionario, è possibile verificare se una sottostringa è un prefisso di una parola corretta. Quindi, quando interrogate il testo [k-l: k] e ottenete una risposta negativa, già sapete che lo stesso vale per il testo [k-l: k + d] per ogni d. Per trarne vantaggio dovresti riorganizzare la ricorsione in modo significativo, quindi non sono sicuro che questo possa essere sfruttato appieno (può vedere un commento).

Answer 5

Dopo aver eseguito la suddivisione ricorsiva e la ricerca nel dizionario, per aumentare la qualità delle coppie di parole nella frase utilizzata potrebbe essere interessato a utilizzare le informazioni sulle coppie di parole.

Questo essenzialmente sta andando attraverso un set di allenamento e scoprendo M.I. valori di coppie di parole che ti dicono che Albert Simpson è meno probabile di Albert Einstein :)

Puoi provare a cercare Science Direct per gli articoli accademici in questo tema. Per informazioni di base sull'informazione reciproca vedi http://en.wikipedia.org/wiki/Mutual_information

L'anno scorso ero stato coinvolto nella parte di ricerca frase di un progetto di motore di ricerca in cui stavo cercando di analizzare il set di dati wikipedia e classificare ogni coppia di parole. Ho il codice in C++ se ti interessa poterlo condividere con te se riesci a trovarne un uso. Analizza wikimedia e per ogni coppia di parole scopre l'informazione reciproca.