Comment déterminer si une chaîne aléatoire sonne comme l'anglais?

StackOverflow https://stackoverflow.com/questions/92006

  •  01-07-2019
  •  | 
  •  

Question

J'ai un algorithme qui génère des chaînes en fonction d'une liste de mots d'entrée. Comment séparer uniquement les chaînes qui ressemblent à des mots anglais? c'est à dire. éliminez RDLO en conservant LORD .

MODIFIER: Pour préciser, il n'est pas nécessaire que ce soit des mots réels dans le dictionnaire. Ils ont juste besoin de sonner comme l'anglais. Par exemple, KEAL serait accepté.

Était-ce utile?

La solution

Vous pouvez construire une chaîne de markov d'un énorme texte anglais.

Ensuite, vous pouvez insérer des mots dans la chaîne de markov et vérifier quelle est la probabilité que le mot soit anglais.

Voir ici: http://en.wikipedia.org/wiki/Markov_chain

Au bas de la page, vous pouvez voir le générateur de texte Markov. Ce que vous voulez, c'est exactement le contraire.

En résumé: la chaîne de markov stocke pour chaque caractère les probabilités dont le prochain caractère suivra. Vous pouvez étendre cette idée à deux ou trois caractères si vous avez assez de mémoire.

Autres conseils

La solution de facilité avec les filtres bayésiens (exemple Python tiré de 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)]

Pour résoudre ce problème, vous pouvez créer une chaîne candidate en séparant bigrams & # 8212; lettres adjacentes et vérification de chaque bigramme par rapport à un tableau de fréquences anglaises de bigrammes.

  • Simple: si un bigramme est suffisamment bas sur la table de fréquences (ou carrément absent), rejetez la chaîne comme étant non plausible. (La chaîne contient un "QZ" bigram? Reject!)
  • Moins simple: calculez la vraisemblance globale de toute la chaîne en termes de, disons, un produit des fréquences de chaque bigramme divisé par la fréquence moyenne d’une chaîne anglaise valide de cette longueur. Cela vous permettrait à la fois (a) d'accepter une chaîne avec un bigram étrange basse fréquence parmi les bigrammes autrement haute fréquence, et (b) de rejeter une chaîne avec plusieurs bigrams individuels bas mais pas tout à fait en dessous du seuil .

L'une ou l'autre de ces solutions nécessiterait un réglage du (des) seuil (s), la deuxième technique plus que la première.

Faire la même chose avec les trigrammes serait probablement plus robuste, bien que cela conduira probablement à un ensemble un peu plus strict de "valide" des cordes. Que cela soit gagnant ou non dépend de votre application.

Des tables de Bigram et de trigrammes basées sur des corpus de recherche existants peuvent être disponibles gratuitement ou achetées (je n’en ai trouvé aucune disponible gratuitement, mais seulement une recherche rapide sur Google), mais vous pouvez calculer une table bigram ou trigram à partir de vous-même. tout corpus de bonne taille de texte anglais. Parcourez chaque mot en tant que jeton et compilez chaque bigramme. Vous pouvez le traiter comme un hachage avec un bigram donné comme clé et un compteur d’entiers incrémenté comme valeur.

La morphologie anglaise et la phonétique anglaise sont (notoirement!) inférieures à l'isométrie. Cette technique peut donc générer des chaînes qui "ressemblent" à "look". Anglais mais présente prounciations gênantes. C’est un autre argument en faveur des trigrammes plutôt que des bigrammes; l’étrangeté produite par l’analyse de sons utilisant plusieurs lettres en séquence pour produire un phonème donné sera réduite si le n-gramme couvre tout le son. (Pensez par exemple à "labourer" ou à "tsunami").

Il est assez facile de générer des mots à l’anglais avec une chaîne de Markov. Revenir en arrière est plus difficile, cependant. Quelle est la marge d'erreur acceptable pour les résultats? Vous pouvez toujours avoir une liste de paires de lettres communes, de triples, etc., et les noter en fonction de cela.

Vous devez rechercher " prononçable " générateurs de mots de passe, car ils essaient d'accomplir la même tâche.

Une solution Perl serait Crypt :: PassGen , que vous pouvez former avec un dictionnaire (vous pouvez donc le former en plusieurs langues si vous en avez besoin) Il parcourt le dictionnaire et collecte des statistiques sur les séquences de 1, 2 et 3 lettres, puis crée de nouveaux "mots". basé sur les fréquences relatives.

Metaphone et Double Metaphone sont similaires à SOUNDEX, mais ils peuvent être davantage adaptés à votre objectif que SOUNDEX . Ils sont conçus pour "hachage". mots basés sur leur "son" phonétique phonétique, et sont bons pour le faire pour la langue anglaise (mais pas tellement d'autres langues et noms propres).

Une chose à garder à l’esprit avec les trois algorithmes est qu’ils sont extrêmement sensibles à la première lettre de votre mot. Par exemple, si vous essayez de savoir si KEAL sonne en anglais, vous ne trouverez aucune correspondance avec REAL car les lettres initiales sont différentes.

Je serais tenté d'exécuter l'algorithme soundex sur un dictionnaire de mots anglais et de mettre en cache les résultats, puis soundex votre chaîne candidate et d'établir une correspondance avec le cache.

En fonction des exigences de performances, vous pouvez élaborer un algorithme de distance pour les codes soundex et accepter les chaînes dans une certaine tolérance.

Soundex est très facile à mettre en œuvre - voir Wikipedia pour une description. de l'algorithme.

Un exemple d'implémentation de ce que vous voulez faire serait: 

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"

Vous devrez évidemment fournir une implémentation de read_english_dictionary.

MODIFIER : votre exemple de " KEAL " ça ira, car il a le même code soundex (K400) que "KEEL". Vous devrez peut-être enregistrer les mots rejetés et les vérifier manuellement si vous souhaitez avoir une idée du taux d'échec.

Doivent-ils être de vrais mots anglais ou juste des chaînes qui ressemblent à des mots anglais?

S'ils ont juste besoin de ressembler à des mots anglais possibles , vous pouvez effectuer des analyses statistiques sur des textes anglais réels et déterminer les combinaisons de lettres les plus fréquentes. Une fois que vous avez fait cela, vous pouvez jeter des chaînes trop improbables, bien que certaines d’entre elles puissent être de vrais mots.

Vous pouvez également utiliser un dictionnaire et rejeter les mots qui n'y figurent pas (avec quelques tolérances sur les pluriels et autres variantes).

Vous pouvez les comparer à un dictionnaire (disponible gratuitement sur Internet), mais cela peut être coûteux en termes d’utilisation du processeur. À part cela, je ne connais aucune autre façon programmatique de le faire.

Cela semble être une tâche compliquée! Hors de ma tête, un phonème consonne a besoin d'une voyelle avant ou après. Déterminer ce qu'est un phonème sera assez difficile cependant! Vous devrez probablement écrire manuellement une liste d'entre eux. Par exemple, " TR " est ok mais pas "TD", etc.

J'évaluerais probablement chaque mot en utilisant un algorithme SOUNDEX par rapport à une base de données de mots anglais. Si vous faites cela sur un serveur SQL, il devrait être assez facile de configurer une base de données contenant une liste de la plupart des mots anglais (en utilisant un dictionnaire disponible gratuitement), et le serveur MSSQL a SOUNDEX implémenté comme algorithme de recherche disponible.

Évidemment, vous pouvez l’implémenter vous-même si vous le souhaitez, dans n’importe quelle langue - mais cela peut être une tâche ardue.

De cette façon, vous obtiendrez une évaluation de la mesure dans laquelle chaque mot ressemble à un mot anglais existant, le cas échéant, et vous pouvez définir des limites pour le niveau minimal d'acceptation des résultats. Vous voudrez probablement réfléchir à la manière de combiner les résultats de plusieurs mots, et vous voudrez probablement ajuster les limites d'acceptation en fonction des tests.

Je suggérerais de regarder le test de phi et l'indice de coïncidence. http://www.threaded.com/cryptography2.htm

Je suggérerais quelques règles simples et des paires et triplets standards serait bien.

Par exemple, les mots à consonance anglaise ont tendance à suivre le modèle voyelle-consonne-voyelle, mis à part certains diphtongues et paires de consonnes standard (par exemple, th, ie et ei, oo, tr). Avec un système comme celui-ci, vous devriez éliminer presque tous les mots qui ne sonnent pas comme s'ils pouvaient être anglais. En y regardant de plus près, vous constaterez probablement que vous supprimerez beaucoup de mots qui sonnent bien en anglais, mais vous pouvez ensuite ajouter des règles permettant un plus grand nombre de mots et "entraîner" votre algorithme manuellement.

Vous ne supprimerez pas tous les faux négatifs (par exemple, je ne pense pas que vous puissiez arriver à définir une règle pour inclure le «rythme» sans coder explicitement dans ce rythme est un mot), mais cela fournira une méthode de filtrage. .

Je suppose également que vous voulez des chaînes qui pourraient être des mots anglais (elles sonnent bien lorsqu'elles sont prononcées) plutôt que des chaînes qui sont définitivement des mots avec une signification anglaise.

Licencié sous: CC-BY-SA avec attribution
Non affilié à StackOverflow
scroll top