Separazione di parole in una stringa

Question

Separazione di parole in una stringa

#1 da (6 voti)
#2 da (1 voti)

3

Come separo le parole in una stringa?

Di seguito ho un campione casuale di parole in una stringa estratta da un file di testo con oltre un milione di parole.

Ecco la stringa: "intervengono Tasche Gerusalemme e tessuti potenti giorni gadget tasso invenzione riscaldata Stewartis trova lotti di lavoro comunali interni Hanno causato rumore goand grandi salti perdono galassie Tutti Mall nascita mondo mondo rotazione ucciso prodotto grande centro Non fingere soluzione Africa tempi cursore buona notte problema professionale rifugiati parlare"

Come puoi vedere, la terza parola è "Jerusalemand". Il mio obiettivo è quello di separare "Gerusalemme" e "e", e fare la stessa cosa per qualsiasi altra parola che si blocca insieme.

L'unica cosa a cui potrei pensare fin d'ora è di confrontare ogni parola della stringa con un dizionario (forse SCOWL?), e se un segmento della parola corrisponde a una parola nel dizionario, dovrò dividere le parole per renderle indipendenti.

Ad esempio, per "Jerusalemand" farò un loop di ogni personaggio fino a quando non trovi una corrispondenza nel dizionario per "Jerusalem", quindi posso separarla da "and," a sua volta completando la separazione.

Non dovrebbe esserci un modo migliore per farlo?

machine-learning natural-language-processing text-processing dynamic-programming

posta Ji Park 12.07.2012 - 05:48

fonte

2 risposte

Leggi altre domande sui tag machine-learning natural-language-processing text-processing dynamic-programming

Il puntatore Head (inizio) dell'elenco Doubly Linked punta in precedenza al nodo (ultimo) della coda Esiste un caso d'uso valido per l'utilizzo della direttiva namespace?

score 6 · Answer 1

Le soluzioni a questo problema sono spesso ambigue e talvolta è difficile decidere una soluzione ottimale, anche per un umano.

Se hai bisogno di una sola soluzione in cui tutte le parole esistono in un dizionario, allora un approccio ingenuo fallirà non appena incontrerai una parola il cui prefisso è anche una voce di dizionario valida.

Ad esempio, se la stringa di input era:

tryingtomessitup

A meno che non torni indietro, il tuo algoritmo verrebbe probabilmente in mente:

try in gtomessitup

invece di

trying to mess it up

La soluzione corretta a questo problema deve essere eseguita utilizzando la programmazione dinamica o anche un algoritmo ricorsivo di forza bruta che può decidere se un prefisso conduce effettivamente alla soluzione ottimale.

Un esempio DP è menzionato in questo thread StackOverflow . Questa risposta la spiega in modo ancora più approfondito (e conduce a questo articolo: Separare le parole unite in una singola stringa (composto-separatore) ).

score 1 · Answer 2

Non riesco a pensare ad alcuna ragionevole alternativa all'approccio generale che descrivi. Probabilmente vorresti focalizzare la tua attenzione su esattamente quali passi utilizzerai per (provare a) trasformare una potenziale parola in una o più parole verificate.

Una cosa che potresti sicuramente fare per velocizzare le cose è controllare prima tutta la parola, e solo controllare sottostringhe se quella ricerca fallisce. Ciò presuppone che la maggior parte delle parole potenziali siano parole valide, come sembra essere il caso nel tuo esempio.

Alcune cose da considerare, in nessun ordine particolare:

Ci saranno mai più di 2 parole inceppate?
Assicurati che la ricerca del dizionario sia veloce!
Una lettera maiuscola nel mezzo della parola potrebbe essere una buona indicazione di dove iniziare a provare a dividere una parola.
Una divisione è valida solo se entrambe le parti sono parole valide?
Che cosa vuoi fare se c'è una parola potenziale che non puoi dividere in 2 (o più) parole valide?
Se ti interessa davvero l'efficienza, potresti scoprire che è più veloce provare a suddividere le potenziali parole a metà, piuttosto che iniziare con il primo personaggio e andare da lì. Le divisioni valide tenderanno ad essere vicino al centro di potenziali parole, piuttosto che all'inizio o alla fine. Ciò renderebbe il codice responsabile per provare tutte le potenziali divisioni un po 'più complesse però.