Como faço para determinar se um aleatórias sons de cordas como o Inglês?

Question

Eu tenho um algoritmo que gera seqüências com base em uma lista de palavras de entrada. Como faço para separar somente as cordas que soa como palavras inglesas? ie. descarte RDLO , mantendo Senhor .

EDIT: Para esclarecer, eles não precisam ser verdadeiras palavras no dicionário. Eles só precisam de som como o Inglês. Por exemplo Keal seria aceito.

Answer 1

Você pode construir uma cadeia de Markov de um texto enorme Inglês.

Depois, você pode alimentar palavras na cadeia de Markov e verificar como alta a probabilidade é que a palavra é Inglês.

Veja aqui: http://en.wikipedia.org/wiki/Markov_chain

Na parte inferior da página você pode ver o gerador do texto Markov. O que você quer é exatamente o inverso disso.

Em poucas palavras: As lojas de cadeia de Markov para cada personagem as probabilidades de que no próximo personagem vai seguir. Você pode estender essa idéia para dois ou três caracteres se você tem memória suficiente.

Answer 2

A forma mais fácil com Bayesian filtra (exemplo Python de http://sebsauvage.net/python/snyppets / # bayesiana )

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

Você poderia abordar este por tokenizing uma corda candidato em bigramas -pairs de adjascent cartas- e verificando cada bigram contra uma tabela de Inglês freqüências bigrama.

• Simples: se houver bigram é suficientemente baixo na tabela de freqüência (ou totalmente ausente), rejeitar a string como implausível. (String contém um bigram "QZ"? Rejeitar!)
• Menos simples: calcular a plausibilidade geral de toda a corda em termos de, digamos, um produto das freqüências de cada bigram dividida pela frequência média de uma seqüência de Inglês válida do que o comprimento. Isso permitiria que você tanto (a) aceitar uma string com um bigram baixa frequência estranho entre outra forma bigramas de alta frequência, e (b) rejeitar uma corda com vários bigramas individuais baixo-mas-não-muito-abaixo-the-limite .

De qualquer daqueles exigiria algum ajuste do limiar (s), a segunda técnica mais do que o primeiro.

Fazer a mesma coisa com trigramas provavelmente seria mais robusto, embora ele também vai provavelmente levar a um conjunto um pouco mais rigorosa das cordas "válido". Se isso é uma vitória ou não depende da sua aplicação.

bigrama e trigram tabelas com base em corpora pesquisas existentes podem estar disponíveis gratuitamente ou compra (eu não havia nenhuma disponível livremente, mas só fez um google superficial até agora), mas você pode calcular um bigram ou trigrama tabela a partir-se de qualquer bom tamanho corpus de texto em Inglês. Apenas manivela através de cada palavra como um símbolo e coaduna-se cada bigram-que você pode lidar com isso como um hash com um determinado bigram como a chave e um contador inteiro incrementado conforme o valor.

morfologia Inglês e fonética inglesa são (famosa!) Inferior a isométrica, assim que esta técnica pode muito bem gerar seqüências que "olhar" Inglês, mas presentes prounciations problemáticos. Isto é um outro argumento para trigramas, em vez de bigramas-a estranheza produzidos por análise de sons que utiliza várias letras em sequência para produzir um dado fonema será reduzido se o n-grama vãos todo o som. (Pense "arado" ou "tsunami", por exemplo.)

Answer 4

É muito fácil para gerar Inglês palavras sonoras usando uma cadeia de Markov. Indo para trás é mais um desafio, no entanto. Qual é a margem de erro aceitável para os resultados? Você pode sempre ter uma lista de pares de letras comuns, triplos, etc, e classificá-los com base nisso.

Answer 5

Você deve pesquisar geradores de senha "pronunciável", uma vez que eles estão tentando realizar a mesma tarefa.

solução A Perl seria Crypt :: PassGen , que você pode treinar com um dicionário (para que você possa treiná-lo para várias línguas, se você precisa). Ele caminha através do dicionário e recolhe estatísticas sobre 1, seqüências 2 e 3 letras, em seguida, constrói novas "palavras" com base em frequências relativas.

Answer 6

Metaphone e Duplo Metaphone são semelhantes aos SOUNDEX, exceto que eles podem ser ajustados mais em direção a sua meta de SOUNDEX . Eles são projetados para palavras "de hash" com base em seu "som" fonética, e são bons em fazer isso para o idioma Inglês (mas não tanto outras línguas e nomes próprios).

Uma coisa a ter em mente com todos os três algoritmos é que eles são extremamente sensíveis à primeira letra de sua palavra. Por exemplo, se você está tentando descobrir se Keal é o Inglês-som, você não vai encontrar uma correspondência para real porque as letras iniciais são diferentes.

Answer 7

eu estaria tentado a correr o algoritmo soundex mais de um dicionário de palavras em inglês e armazenar em cache os resultados, então Soundex sua seqüência candidato e combinar contra o cache.

Dependendo dos requisitos de desempenho, você poderia trabalhar para fora um algoritmo de distância para códigos soundex e aceito cordas dentro de uma certa tolerância.

Soundex é muito fácil de implementar - veja Wikipedia para uma descrição do algoritmo.

Um exemplo de implementação do que você quer fazer seria:

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"

Obviamente, você precisará fornecer uma implementação de read_english_dictionary.

Editar : O seu exemplo de "Keal" vai ficar bem, uma vez que tem o mesmo código soundex (K400) como "KEEL". Você pode precisar fazer logon palavras rejeitados e manualmente verificar-los se você quiser ter uma idéia da taxa de insucesso.

Answer 8

Será que eles têm que ser palavras inglesas reais, ou apenas cordas que se parecem com eles poderiam ser palavras inglesas?

Se eles só precisam de olhar como possível palavras em inglês que você poderia fazer alguma análise estatística em alguns textos ingleses reais e trabalho fora que combinações de letras ocorrem com freqüência. Uma vez feito isso você pode jogar fora cordas que são muito improvável, embora alguns deles podem ser palavras reais.

Ou você pode simplesmente usar um dicionário e rejeitar as palavras que não estão nele (com alguns subsídios para plurais e outras variações).

Answer 9

Você poderia compará-los com um dicionário (disponível gratuitamente na internet), mas que pode ser dispendiosa em termos de uso da CPU. Fora isso, eu não sei de qualquer outra forma de programação para fazê-lo.

Answer 10

Isso soa como uma tarefa bastante envolvido! Em cima da minha cabeça, um fonema consonantal precisa de uma vogal antes ou depois dela. Determinar o que um fonema é vai ser muito difícil embora! Você provavelmente vai precisar de escrever manualmente uma lista deles. Por exemplo, "TR" é ok, mas não "TD", etc.

Answer 11

Eu provavelmente avaliar cada palavra usando um algoritmo de SOUNDEX contra um banco de dados de palavras em inglês. Se você estiver fazendo isso em um servidor SQL que deve ser bastante fácil de configurar um banco de dados contendo uma lista da maioria das palavras inglesas (usando um dicionário livremente disponível) e servidor MSSQL tem SOUNDEX implementado como uma pesquisa de algoritmo disponível.

Obviamente, você pode implementar esse mesmo, se quiser, em qualquer idioma - mas pode ser uma tarefa bastante.

Desta forma, você deseja obter uma avaliação de quanto cada palavra soa como uma palavra Inglês existente, se houver, e você poderia configurar alguns limites para o quão baixo você gostaria de aceitar os resultados. Você provavelmente considerar como combinar resultados de várias palavras, e você provavelmente ajustar a aceitação dos limites com base em testes.

Answer 12

Eu sugiro olhar o teste phi e o índice de coincidência. http://www.threaded.com/cryptography2.htm

Answer 13

Eu sugiro algumas regras simples e pares padrão e trigêmeos seria bom.

Por exemplo, palavras-sonda inglês tendem a seguir o padrão de vogal-consoante-vogal, para além de algumas diphthongs e pares de consoantes padrão (por exemplo, po, ou seja, e ei, oo, tr). Com um sistema como o que você deve retirar quase todas as palavras que não soam como eles poderiam ser Inglês. Você encontraria em uma inspeção mais próxima que você provavelmente irá retirar um monte de palavras que soam como Inglês, bem como, mas você pode então começar a adicionar regras que permitem uma ampla gama de palavras e 'treinar' seu algoritmo manualmente.

Você não irá remover todos os falsos negativos (por exemplo, eu não acho que você poderia conseguir chegar a uma regra para incluir 'ritmo' sem codificação explicitamente nesse ritmo é uma palavra), mas que irá fornecer um método de filtragem .

Eu também estou supondo que você quer cordas que poderiam ser palavras inglesas (eles som razoável quando pronunciado) em vez de strings que são definitivamente palavras com um significado Inglês.