Tous les * pangrammes parfaits de langlais

Un Le pangram anglais est une phrase qui contient les 26 lettres de lalphabet anglais. Le pangram anglais le plus connu est probablement « Le renard brun rapide saute sur le chien paresseux ». Mon pangram préféré est « Étonnamment peu de discothèques proposent des juke-box. »

Un pangramme parfait est un pangram où chacune des lettres napparaît quune seule fois. Jai trouvé des sources en ligne qui répertorient les pangrammes parfaits connus. Personne ne semble sêtre efforcé de les produire tous de manière exhaustive, alors je lai relevé comme un défi amusant. Cest ainsi que jai trouvé tous les pangrammes parfaits de langlais. Jexpliquerai lastérisque plus tard.

• Crwth vox zaps qi gym fjeld bunk. (Le son dun violon celtique frappe un centre de remise en forme axé sur les forces spirituelles orientales situé dans un plateau stérile de la Scandinavie.) Celui-ci est tous des mots juridiques de Scrabble!
• Squdgy kilp job zarf nth cwm vex. (Le varech mal formé achète un chauffe-tasse ornemental que lun des nombreux creux à flancs escarpés à demi ouverts à la tête dune vallée ou dun flanc de montagne a irrité.)
• Jock nymphs waqf drug vex blitz. (La dotation caritative a enivré les esprits de la forêt, qui ont frustré lathlète, qui se lance dans une attaque.)
• Hm, valse du fjord, cinq busk, pyx veg. (Voyons voir, une longue et étroite entrée profonde danse, les cinq sur les dés font de la musique dans la rue, et le petit récipient rond pour les malades et les incapables se repose.) Aussi Scrabble légal, mais a une interjection (Hm).

Malheureusement, ce sont quelques-unes des phrases les plus lisibles que jai pu trouver *. Tous les pangrammes parfaits générés à partir du tournoi officiel et de la liste de mots du club 3 (OWL3) pour le Scrabble sans interjections incluent le mot cwm ou crwth. Waqf est un tournoi de Scrabble légal en dehors de lAmérique du Nord.

Comment trouver tous les pangrammes parfaits

La méthode pour trouver les pangrammes parfaits se déroule en deux étapes. La première consiste à rechercher tous les ensembles de mots contenant une seule fois chaque lettre de lalphabet anglais. La deuxième étape consiste à voir lesquels de ces ensembles peuvent être réorganisés en phrases anglais valides.

Étape 1: Trouver des ensembles de mots pour le pangramme parfait

Pour commencer à trouver des ensembles de mots qui span lalphabet anglais nécessite une liste de mots anglais. Trouver et maintenir une liste de mots de haute qualité a été beaucoup plus difficile que je ne lavais prévu. À lorigine, je pensais que ce projet prendrait deux jours, mais cela a pris deux semaines en raison de ce problème de qualité des données.

Jai commencé avec le dictionnaire Unix, qui est une liste de mots anglais disponible gratuitement qui vient avec presque tous les systèmes dexploitation basés sur Unix. Jai immédiatement remarqué que la liste avait des problèmes de qualité. Premièrement, chaque lettre de lalphabet était considérée comme un mot dans le dictionnaire Unix, et elle comprenait beaucoup de non-mots, comme « vejoz ». Cela démontrait la nécessité dune liste noire pour gérer les listes de mots trouvés en ligne. Deuxièmement, le Le dictionnaire Unix manquait de pluriel pour les mots, le dictionnaire inclurait donc le mot « orange » mais pas « oranges ». La liste de mots est si restrictive, en fait, quaucun pangramme parfait connu auparavant nincluait uniquement des mots du dictionnaire Unix. Jai toujours trouvé certains, comme « squdgy kilp job zarf nth cwm vex ».

Je me suis alors tourné vers Internet pour trouver de plus grands ensembles de mots. Jai trouvé de très grands ensembles de mots qui étaient énormes, mais quand jai commencé à chercher des pangrammes parfaits à partir de ces listes, jai trouvé quils étaient beaucoup trop pollués avec des mots de mauvaise qualité qui ne sont pas des mots anglais valides. Même après de nombreuses séries ditérations, je nai toujours pas réussi à réduire la liste pour trouver des pangrammes raisonnables ou gérables. Jai essayé de le nettoyer en créant une liste blanche de mots de certaines longueurs, mais la liste était toujours de qualité extrêmement médiocre.

Enfin, après de nombreuses itérations, jai payé 15 $ pour acheter un abonnement dessai de lAmérique du Nord Scrabble® Players Association, qui ma donné accès à lOWL3 propriétaire et protégé par les droits dauteur, qui est à lorigine dune controverse. Même dans ce cas, jai dû ajouter quelques mots connus en anglais, tels que les mots à une seule lettre «a» et «I».

Armé dune liste de mots appropriée, jai implémenté un algorithme pour produire tous les ensembles de mots de cette liste contenant chacun une de chaque lettre de lalphabet anglais. Je décrirai lalgorithme en détail dans la section « Lalgorithme » ci-dessous.

Étape 2: Former des phrases en anglais à partir dun sac de mots

Étant donné un ensemble de mots, déterminer une phrase en anglais valide est possible avec tous les mots fournis est un problème non trivial, mais cest plus facile que la plupart des autres problèmes de traitement du langage naturel (PNL).

Il existe des heuristiques utiles pour éliminer les phrases inéligibles; Jai pu former des phrases anglaises valides à partir des mots restants après avoir suivi ces heuristiques. Les phrases étaient souvent absurdes, mais toujours valables. Voici les heuristiques que jai utilisées:

1. Il doit y avoir au moins un verbe.
2. Il ne peut y avoir quun seul nom de plus quil ny a de verbes à moins quil ny ait une conjonction ou une préposition, les deux sont très rares.
3. Sil y a des adjectifs, il doit aussi y avoir des noms.

Lheuristique fonctionne en partie à cause de la possibilité dimplicite sujets (ni parfait, ni un pangram, mais « bougez doucement et parlez doucement » est une phrase avec deux verbes et aucun nom, avec le sujet implicite de « vous »).

Depuis lespace des mots qui peut peut-être participer à des pangrammes parfaits est petit, il est assez facile de marquer manuellement chaque mot individuel avec ses parties éligibles du discours et de voir si lensemble de mots obéit à ces trois heuristiques simples. Que vous aimiez ou non la qualité des phrases produites est une question de goût.

Lalgorithme

Cette section est un peu technique, mais jespère toujours facile à suivre. Nhésitez pas à passer à la section « Résultats & Enseignements ».

Stratégie de haut niveau

Lobjectif est de produire tous les ensembles possibles de mots de la liste de mots donnée qui couvre «parfaitement» l’alphabet anglais.

1. Nettoyez la liste de mots pour réduire considérablement l’espace de recherche, par exemple supprimez les mots qui ont des lettres répétées, comme des «lettres».
2. Utilisez des masques binaires pour représenter efficacement les mots et les renvoyer aux ensembles de mots dorigine.
3. Effectuez une recherche dans tous les états possibles, représentant chacun une combinaison de lettres possible, en itérant à plusieurs reprises dans la liste des masques de bits. Les performances sont considérablement améliorées grâce à la programmation dynamique.
4. Dessinez des flèches (arêtes dirigées) à partir de létat de pangramme parfait, létat final qui a tout les lettres anglaises, aux états intermédiaires qui les ont composées. Répétez lopération avec les états intermédiaires pour créer une structure de données qui peut reconstruire les ensembles de mots qui sont des pangrammes parfaits possibles. Cest ce quon appelle le retour en arrière.
5. Sortie les ensembles de mots découverts qui sont peut-être des pangrammes parfaits en tant quarbres.

Nettoyage de la liste, alias Canonisation

La première étape consiste à nettoyer la liste de mots dorigine pour réduire lespace de recherche et augmenter la qualité de sortie.

1. Supprimez tous les espaces autour du mot et le convertir en minuscules uniquement
2. Assurez-vous que les mots ne contiennent que des lettres de lalphabet anglais; Jai utilisé un simple filtre dexpression régulière: /^+$/
3. Filtre par rapport à toute autre liste, par exemple listes noires; si un mot est dans la liste noire, ignorez ce mot
4. Supprimez tous les mots avec des lettres répétées

Cela a réduit considérablement lespace de recherche, passant de listes de 200 000 à 370 000 mots à un beaucoup plus petit 35 000 ~ 65 000 mots.

Utilisation de masques binaires

Les masques de bits sont des représentations entières détats. Les masques de bits présentent plusieurs avantages:

• Les masques de bits représentent bien ce problème. Lordre des lettres na pas dimportance, donc toutes les combinaisons de mots peuvent être représentées sous la forme dune longue série de 26 chiffres de 0 et de 1, chaque chiffre représentant si une lettre existe ou non dans la combinaison. Par exemple. si lensemble de mots contient la lettre «e», le 5ème chiffre sera un 1, sinon un 0.
• Les masques de bits sont efficaces: lespace de recherche étant constant, les masques de bits offrent un stockage efficace et représentation de toutes les combinaisons de lettres possibles. De plus, les opérations au niveau du bit sont rapides; pour tester si deux masques de bits peuvent être combinés pour produire un masque de bits plus grand, vérifiez si le ET au niveau du bit des deux masques est égal à 0, tous deux extrêmement opérations rapides.

Donc, transformez chaque mot en un masque de bits, qui peut être représenté comme un entier. Par exemple, le mot «cab» est mappé au masque de bits de 111, qui est le nombre décimal 7. Le mot «be» est mappé sur 10010, qui est le nombre décimal 18, etc. Le plus grand masque de bits possible est celui avec toutes les lettres de lalphabet, létat de pangramme parfait possible, 11111111111111111111111111, qui est le nombre décimal 67,108,863, ou 2²⁶ -1. Cela correspond bien à un entier standard signé de 32 bits, qui peut représenter jusquà à 2³¹-1.

Lutilisation de masques de bits compresse davantage lespace, car les anagrammes dun seul mot correspondent au même masque de bits. Le « four » et le « lien » correspondent au masque 10110100000000, qui est le nombre décimal 11520. Ceci réduit encore lespace de recherche de 35 000 à 65 000 mots à 25 000 à 45 000 masques de bits.

Conserver une correspondance entre le masque de bits et lensemble de mots dont ils sont dérivés. Cela sera utile lors de la sortie des ensembles de mots.

Recherche du pangramme parfait avec programmation dynamique

Le noyau de lalgorithme est assez simple:

Étant donné un état possible (qui est composé de combinaisons valides de mots existants), essayez tous les masques de la liste de mots initiale pour voir sil est possible de créer un nouvel état valide (en vérifiant si le ET au niveau du bit de létat et le masque sont égaux à 0, ce qui signifierait quil ny a pas de lettres qui se chevauchent). Créez le nouvel état à laide de lopération OR au niveau du bit qui fusionne tous les 1 ensemble. Pour chaque nouvel état découvert, répétez jusquà ce quil ny ait plus détats inexplorés. Si cela arrive à la fin, cela signifie que lalgorithme a trouvé au moins un ensemble de mots pangramme parfait possible. Le premier état possible qui peut énumérer tous les états possibles est létat vide ou 0, où aucune lettre de lalphabet nest incluse. Alors commencez par là et découvrez récursivement quels états sont possibles.

Un énorme gain defficacité est de remarquer quil existe de nombreuses façons datteindre un état intermittent et que le travail sur létat ne change pas en fonction de la façon dont il a été atteint. Ainsi, au lieu de répéter le travail lorsquun état est revisité, stockez le résultat de chaque état. Cette technique est appelée programmation dynamique et transforme un problème combinatoire complexe en un programme linéaire. Le processus de stockage de létat intermittent sappelle la mémorisation.

Créez donc un tableau de taille 2²⁶, entre 0 et 67 108 863 inclus. Chaque index représente un état de masque de bits comme expliqué précédemment. La valeur à chaque index du tableau représente ce que lon sait de létat. 0 signifie que létat est intact ou inaccessible. 1 signifie que lÉtat a trouvé un moyen datteindre létat de pangramme parfait possible. -1 signifie que létat na pas réussi à trouver un moyen datteindre la fin.

Pseudocode ci-dessous:

Interlude: Complexity and Practical Runtime Analysis

Il y a 2²⁶ masques de bits possibles pour une série de 26 bits. Comme chaque état nest traité quune seule fois à cause de la mémorisation, le runtime de cet algorithme est O (n 2 ^ d), où d est la taille de lalphabet, 26. La variable n ne représente pas le nombre de mots, mais le nombre de masques binaires. Avec 67 108 863 et environ 45 000 masques de bits, cela représente environ 3 billions de dollars, ce que mon MacBook Pro pourrait gérer en 45 minutes environ; traitable pour tout ordinateur moderne. Il convient également de noter que la pile dappels récursifs ne dépassera jamais 26 (probablement jamais plus de 15), donc elle est également très gérable à partir de cette dimension.

Un avantage de lapproche du masque de bits avec seulement 2²⁶ états est que tous les états peuvent être stockés en mémoire. Comme il ny a que 3 valeurs par état (-1, 0, 1), cela peut être stocké dans un seul octet. À un seul octet par état, 2²⁶ états sortent à environ 67 mégaoctets, ce qui est encore une fois très gérable.

À mesure que lalphabet augmente, cependant, lespace de recherche augmente de façon exponentielle, tout comme le temps dexécution, ce qui problème pour devenir insoluble très rapidement. Une brève discussion sur lapproche du pangramme parfait pour les alphabets plus grands se trouve dans la section « Langage avec alphabets plus grands » ci-dessous.

Construction dynamique dun graphe acyclique dirigé (DAG)

Maintenant que nous ont rempli les états du masque de bits, il est temps de récupérer la solution!

Pour trouver les ensembles de mots qui ont créé lensemble des pangrammes parfaits possibles, nous devons dériver quels états intermédiaires faisaient partie intégrante de la composition des états finaux . Ensuite, la question suivante est de savoir quels autres états intermédiaires ont composé ces états intermédiaires, et ainsi de suite jusquà ce quil ne reste plus que les états qui correspondent directement aux mots. Ce processus est appelé retour en arrière.

Pour conserver suivi des relations entre les états, lobjectif est de créer un Di graphique acyclique (DAG), qui maintient quels états intermédiaires composent un état donné. Les DAG sont faciles à parcourir pour récupérer les sorties, en particulier en raison de leur nature non cyclique. Pour construire, partez de létat de pangramme parfait possible, et créez un bord dirigé (flèche) qui pointe vers les états intermédiaires qui le composent. Répétez le processus avec les états intermédiaires, et il produira un DAG. Il ny aura jamais de cycles car les flèches pointent toujours vers un état avec une valeur plus petite.

Au lieu de reconstruire les relations découvertes lors de létape de recherche, ce qui implique de parcourir à nouveau des milliards de combinaisons détats possibles, il est plus efficace de créer le DAG pendant la phase de programmation dynamique. Dans la méthode de résolution, si un état nouvellement construit peut atteindre létat de pangram parfait possible, stockez une arête dirigée de létat nouvellement construit à létat dorigine uniquement si létat dorigine est plus petit que son complément (pour réduire la duplication des arêtes).

Imprimez les fruits de votre travail sous forme darbre!

Le format le plus simple pour visualiser les ensembles de mots résultants est probablement de les lister sous forme darbres avec le nœud racine comme état de pangramme parfait. Étant donné le DAG construit ci-dessus, la meilleure façon de le décompresser est de le faire de manière récursive, en écrivant chaque état sur le disque à chaque étape au lieu dêtre en mémoire puisque larbre est dun ordre de grandeur plus grand que le DAG.

Une amélioration de cette forme dexpansion est de résumer les états qui nont quune seule combinaison possible de mots. Un état qui est un masque pour les mots et aucun sous-état qui le compose peut être résumé de manière triviale. Un état peut être résumé si ses sous-états et ses composites peuvent être résumés, et tous les masques dérivés de lui-même et de ses enfants nont pas de bits / caractères qui se chevauchent. Limpression du DAG résumé améliore la lisibilité de larborescence de sortie résultante en la raccourcissant et en la simplifiant.

Comme la synthèse ne dépend que du plus petit des deux états, itérer dans le tableau à partir de létat initial de 0 et lutilisation des règles ci-dessus pour gérer la règle de récapitulation permet de terminer cela en temps linéaire.

Arbres de pangrams produits!

Nhésitez pas à parcourir les arbres de pangrammes parfaits pour voir si vous peut trouver des phrases intéressantes!

Il y a beaucoup de pangrammes parfaits possibles

Jai été surpris par le nombre de pangrammes parfaits possibles. Il y a beaucoup! La meilleure stratégie pour les assembler ne nécessite pas un processeur de langage naturel complexe. Une fois que les mots candidats ont été étiquetés comme nom ou verbe éligibles, le sac de mots doit contenir au moins un nom, un verbe et le bon ratio de noms et de verbes.

La qualité des données est un problème difficile

La section algorithme a pris deux jours, mais le problème de qualité des données a pris deux semaines. Lorsque jai mentionné cette découverte à mon ami, ingénieur senior chez Google, il na pas été surpris, disant que les problèmes de qualité des données sont parmi les problèmes les plus difficiles en ingénierie. Leçon apprise.

Les règles des pangrammes parfaits

Il y a beaucoup de nuances sur ce qui se qualifie comme un pangram parfait! Je voulais rechercher des pangrammes sans aucune interjections (par exemple hm, pht), mais il existe également dautres restrictions populaires telles que les abréviations, les acronymes, les contractions, les initialismes, les lettres isolées, les noms propres et les chiffres romains. Il y a aussi des mots qui sont des noms de lettres, comme Qoph, que jestime tricher.

Avec certaines de ces contraintes assouplies, il y a beaucoup de pangrammes « parfaits ». De lordre de trillions, probablement . Il y a beaucoup dacronymes et dinitiales.

Lastérisque

Lastérisque est en place car la définition de tous les pangrammes parfaits de langlais nest pas bien définie. Il y a des nuances lié à ce qui devrait être autorisé dans les pangrammes parfaits de langlais. Il y a aussi beaucoup de controverses quant à savoir si certains mots sont même des mots anglais. Compte tenu de ces nuances, il est vraiment difficile de dire que jai trouvé tous les pangrammes parfaits. Je peux faire deux affirmations en toute confiance:

1. Jai trouvé une méthodologie pour produire tous les pangrammes parfaits de langlais et dautres langues avec des jeux de caractères similaires ou plus petits.
2. I ont énuméré tous les ensembles de mots qui peuvent éventuellement former des pangrammes parfaits en utilisant le dictionnaire officiel du tournoi de Scrabble y, OWL3.

Nhésitez pas à produire vos propres pangrams parfaits avec les techniques décrites dans cet article!

La dépendance de Perfect Pangrams à des mots dorigine galloise et arabe

Les mots dérivés du gallois et de larabe étaient vraiment importants pour lexistence de pangrams anglais parfaits (à moins que les contraintes du pangram parfait ne soient assouplies). En utilisant la liste de mots OWL3 avec des règles strictes concernant les pangrammes parfaits, il ny a pas de pangrammes parfaits qui nincluent pas les mots «cwm (s)» ou «crwth (s)», les deux mots gallois. Au Scrabble international, le mot dérivé arabe « waqf (s) » est un mot valide qui peut produire des pangrammes parfaits sans recourir à « cwm (s) » ou « crwth (s) ».

Efficacité des flux de travail

Il était important de devenir plus efficace pour paralléliser les tâches au cours de ce projet. Une exécution complète prend 25 minutes pour le dictionnaire Unix et près dune heure pour les très gros dictionnaires. Jai eu quelques difficultés à changer de contexte pendant une fenêtre de 30 minutes, mais je me suis amélioré au fur et à mesure que je progressais pour améliorer ma productivité.

Extension / généralisation – Anagram Finder

Le pangramme parfait la recherche équivaut également à un chercheur danagrammes pour la chaîne « abcdefghijklmnopqrstuvwxyz ». Et si vous vouliez construire un chercheur danagrammes générique?

La même technique peut être utilisée tant que la représentation de létat et les règles de gestion pour la vérification la validité des combinaisons de mots est mise à jour. Au lieu de gérer les états comme un entier, il serait plus facile de suivre létat comme une carte des caractères pertinents. Voir si les combinaisons sont valides, cest dire que la combinaison de deux cartes ne dépasse pas le Le nombre de caractères souhaité par anagramme pour chaque lettre. Assurez-vous simplement que lespace détats est traitable; avec trop de lettres, lespace de recherche peut devenir vraiment grand en un tournemain. De plus, êtes-vous autorisé à répéter des mots? Assurez-vous de définir ces règles à lintérieur votre programmation dynamique solution.

Langues avec des alphabets plus grands

Cette approche et cette solution sont linéaires dans la taille de lensemble de mots, mais exponentielles dans la taille de lalphabet. Cette approche peut ne pas fonctionner avec un jeu de caractères plus grand, disons le japonais moderne qui compte 46 syllabaires. 2⁴⁶ est 70,368,744,177,664; plus dun million de fois plus grand que lespace de recherche anglais de 2²⁶ = 67 108 864.

Il nest pas tout à fait clair si cette approche fonctionnerait ou non pour le japonais. Si la langue japonaise a une entropie suffisamment faible, ce qui est possible, cette approche serait viable. Au lieu dinitialiser un tableau de taille 2⁴⁶, les états seront suivis dans une carte. De plus, la structure du japonais peut être exploitée; par exemple le kana を (wo) est presque exclusivement utilisé comme participe post-positionnel, et peut être exclu de la recherche, réduisant lespace de recherche.

La langue cambodgienne du khmer a le plus grand alphabet avec 74. Une autre étape possible consiste à explorer des solutions qui sont sous-exponentielles dans la taille de lalphabet.

Inspiration

Jai été inspiré par les progrès dAubrey De Grey dans la recherche du nombre chromatique du plan à être au moins 5. Cest une avancée significative qui a été obtenue grâce à des méthodes de calcul de base.

Il va sans dire que trouver des pangrammes parfaits ne tient pas une bougie pour améliorer la limite inférieure du nombre chromatique dun plan.

Cela me fait croire quil y a beaucoup de problèmes faciles à résoudre qui ont des méthodes de calcul simples pour résoudre un problème qui est manuellement insoluble. Je vous mets au défi de trouver et de résoudre certains de ces problèmes. Sil vous plaît laissez-moi savoir si vous trouvez quelque chose!

Merci

Je suis très reconnaissant pour mes très excellents amis qui mont aidé à relire et à jouer avec moi, en particulier Anna Zeng, Catherine Gao, Danny Wasserman, George Washington et Nick Wu!