Come faccio a determinare se una stringa casuale di suoni come l'inglese?

Question

Ho un algoritmo che genera le stringhe sulla base di un elenco di parole di ingresso.Come faccio a separare solo le corde che suona come parole in inglese?ie.scartare RDLO mantenendo SIGNORE.

EDIT: Per chiarire, non è necessario essere le parole nel dizionario.Hanno solo bisogno di un sound inglese.Per esempio KEAL sarebbe stato accettato.

Answer 1

Si può costruire una catena di markov di un grande testo in inglese.

Poi si può nutrire parole in catena di markov e verificare quanto sia alta la probabilità è che la parola è inglese.

Vedi qui: http://en.wikipedia.org/wiki/Markov_chain

In fondo alla pagina potete vedere il markov generatore di testo.Quello che vuoi è esattamente il contrario di essa.

In breve:La catena di markov negozi per ogni personaggio la probabilità che il prossimo personaggio da seguire.È possibile estendere questa idea di due o tre caratteri, se si dispone di memoria sufficiente.

Answer 2

Il modo più semplice con filtri Bayesiani (Python esempio da http://sebsauvage.net/python/snyppets/#bayesian)

from reverend.thomas import Bayes
guesser = Bayes()
guesser.train('french','La souris est rentrée dans son trou.')
guesser.train('english','my tailor is rich.')
guesser.train('french','Je ne sais pas si je viendrai demain.')
guesser.train('english','I do not plan to update my website soon.')

>>> print guesser.guess('Jumping out of cliffs it not a good idea.')
[('english', 0.99990000000000001), ('french', 9.9999999999988987e-005)]

>>> print guesser.guess('Demain il fera très probablement chaud.')
[('french', 0.99990000000000001), ('english', 9.9999999999988987e-005)]

Answer 3

Si potrebbe avvicinarsi a questo con la creazione di token una stringa di candidati in bigrams—coppie di adjascent lettere—e controllando ogni bigram con una tabella di inglese bigram frequenze.

• Semplice:se qualsiasi bigram è sufficientemente basso sulla tabella di frequenze (o addirittura assenti), rifiuta la corda come plausibile.(Stringa contiene un "QZ" bigram?Rifiutare!)
• Meno semplice:calcolare il generale plausibilità di tutta la stringa in termini di, diciamo, un prodotto delle frequenze di ogni bigram diviso per la frequenza media di un valido inglese stringa di lunghezza.Questo consentirebbe ad entrambi (a) accettare una stringa con uno strano bassa frequenza bigram tra altrimenti ad alta frequenza bigrams, e (b) rifiutare una stringa con diversi singoli basso-ma-non-abbastanza-sotto-la-soglia bigrams.

Uno di quelli che richiedono una messa a punto di soglia(s), la seconda tecnica è di più della prima.

Fare la stessa cosa con trigrammi probabilmente sarebbe più robusto, se sarà anche probabilmente portare un po ' più rigida serie di "valido" stringhe.Che si tratti di una vittoria o non dipende dalla vostra applicazione.

Bigram e trigramma tabelle di base di ricerca esistenti corpora possono essere disponibili gratuitamente o acquistare (non ho trovato nessuna liberamente disponibile, ma solo fatto un rapido google finora), ma si può calcolare un bigram o trigramma tavolo da se stessi da qualsiasi di buone dimensioni con il corpus del testo inglese.Appena manovella attraverso ogni parola come un token e tally up ogni bigram—si potrebbe gestire questo come un hash con un dato bigram come chiave e un numero intero incrementato il contatore come valore.

Inglese morfologia e fonetica inglese sono (famoso!) a meno di isometrica, in modo che questa tecnica potrebbe generare stringhe che "guarda" in inglese, ma presente fastidioso prounciations.Questo è un altro argomento per trigrammi, piuttosto che bigrams—le stranezze di prodotto mediante l'analisi dei suoni che utilizzano diverse lettere in sequenza per produrre un determinato fonema viene ridotta se l'n-gram si estende su tutto il suono.(Penso a "aratro" o "tsunami", per esempio.)

Answer 4

È abbastanza facile per generare inglese altisonanti parole utilizzando una catena di Markov.Andando a ritroso è più di una sfida, tuttavia.Che cosa è accettabile margine di errore per i risultati?Si potrebbe sempre avere un elenco di coppie di lettere, triple, ecc, e il grado in base a che.

Answer 5

Si dovrebbe ricerca "pronunciabile" generatori di password, dal momento che si sta tentando di eseguire la stessa operazione.

Perl soluzione sarebbe Cripta::PassGen, che si può allenare con un dizionario (così si potrebbe formare in diverse lingue, se è necessario).Passeggiate attraverso il dizionario e raccoglie statistiche su 1, 2, e 3-lettera sequenze, quindi, crea nuove "parole" sulla base di frequenze relative.

Answer 6

Metaphone e Doppio Metaphone sono simili a SOUNDEX, con l'eccezione che può essere sintonizzata più verso il vostro obiettivo di SOUNDEX.Sono progettati per "hash" parole in base ai loro fonetica "suono", e sono bravi a fare questo per la lingua inglese (ma non così tanto altre lingue e i nomi propri).

Una cosa da tenere a mente con tutti e tre gli algoritmi è che sono estremamente sensibili alla prima lettera della parola.Per esempio, se si sta cercando di capire se KEAL è inglese dal suono, non trova una corrispondenza per REALE perché le lettere iniziali sono diverse.

Answer 7

Sarei tentato di eseguire il soundex algoritmo su un dizionario della lingua inglese parole e cache i risultati, quindi soundex il candidato stringa e la partita contro la cache.

A seconda dei requisiti di prestazioni, si potrebbe lavorare fuori a distanza di algoritmo per soundex codici e accettare stringhe all'interno di una certa tolleranza.

Soundex è molto facile da implementare - vedere Wikipedia per una descrizione dell'algoritmo.

Un esempio di implementazione di quello che vuoi fare sarebbe:

def soundex(name, len=4):
    digits = '01230120022455012623010202'
    sndx = ''
    fc = ''

    for c in name.upper():
        if c.isalpha():
            if not fc: fc = c
            d = digits[ord(c)-ord('A')]
            if not sndx or (d != sndx[-1]):
                sndx += d

    sndx = fc + sndx[1:]
    sndx = sndx.replace('0','')
    return (sndx + (len * '0'))[:len]

real_words = load_english_dictionary()
soundex_cache = [ soundex(word) for word in real_words ]

if soundex(candidate) in soundex_cache:
    print "keep"
else:
    print "discard"

Ovviamente avrete bisogno di fornire un'implementazione di read_english_dictionary.

MODIFICA:Il tuo esempio di "KEAL" va bene, dato che ha lo stesso codice soundex (K400) come "CHIGLIA".Potrebbe essere necessario accedere respinto parole e verificare manualmente se vuoi avere un'idea del tasso di guasto.

Answer 8

Non devono essere reale inglese parole o solo le stringhe che osservano come potrebbero essere parole in inglese?

Se hanno solo bisogno di guardare come possibile Inglese parole si potrebbe fare qualche analisi statistica di alcuni veri testi in inglese e scoprire quali sono le combinazioni delle lettere che si verificano di frequente.Una volta fatto questo, si può buttare fuori le stringhe che sono troppo improbabile, anche se alcuni di loro possono essere parole reali.

Oppure si può semplicemente utilizzare un dizionario e rifiutare parole che non sono in esso (con alcune indennità per i plurali e altre varianti).

Answer 9

Si potrebbe paragonare a loro un dizionario (liberamente disponibile su internet), ma che può essere costoso in termini di utilizzo della CPU.Oltre a questo, non so di qualsiasi altro modo programmatico per farlo.

Answer 10

Che suona come un bel coinvolti compito!Fuori della parte superiore della mia testa, una consonante fonema esigenze di una vocale prima o dopo di esso.Determinare ciò che un fonema è sarà molto difficile però!Avrete probabilmente bisogno di scrivere manualmente una lista di loro.Per esempio, "TR" è ok, ma non "TD", etc.

Answer 11

Io probabilmente valutare ogni parola con una SOUNDEX algoritmo contro un database di parole in inglese.Se stai facendo questo su un SQL-server dovrebbe essere abbastanza facile per l'installazione di un database contenente un elenco di parole in inglese (utilizzando liberamente disponibile dizionario), e MSSQL server ha SOUNDEX implementato come una ricerca-algoritmo.

Ovviamente è possibile implementare questo a voi stessi, se si desidera, in qualsiasi lingua, ma potrebbe essere piuttosto un compito.

In questo modo si otterrebbe una valutazione di quanto ogni parola suona come un esistente parola inglese, se qualsiasi, e si potrebbe installazione di alcuni limiti per quanto in basso si desidera accettare i risultati.Si sarebbe probabilmente desidera considerare come combinare i risultati per più termini, e si sarebbe probabilmente modificare l'accettazione-limiti basata sulle prove.

Answer 12

Vorrei suggerire di guardare il phi test e indice di coincidenza. http://www.threaded.com/cryptography2.htm

Answer 13

Vorrei suggerire un paio di semplici regole e standard coppie e triplette sarebbe buono.

Per esempio, l'inglese altisonanti parole tendono a seguire il modello della vocale-consonante-vocale, oltre che da alcuni dipthongs e standard consonante coppie (es.th, ie e ie, oo, tr).Con un sistema del genere si dovrebbe eliminare quasi tutte le parole che non suonano come potrebbero essere l'inglese.Ci si aspetterebbe di trovare su controllo più ravvicinato che probabilmente strip out un sacco di parole che fanno rumore come di inglese, ma si può quindi iniziare l'aggiunta di norme che consentano una più ampia gamma di parole e 'in treno' il tuo algoritmo manualmente.

Non rimuovere tutti i falsi negativi (ad es.Non credo che si possa riuscire a venire con una regola per includere il 'ritmo' senza codifica esplicitamente che il ritmo è una parola), ma fornirà un metodo di filtraggio.

Anche io sto supponendo che si desidera di stringhe che possono essere inglese parole (sembrano ragionevoli quando pronuncia), piuttosto che con le stringhe che sono sicuramente parole con un significato inglese.