Toate * pangramele perfecte de engleză

Un Pangrama engleză este o propoziție care conține toate cele 26 de litere din alfabetul englez. Cea mai cunoscută pangramă engleză este probabil „Vulpea brună rapidă sare peste câinele leneș”. Pangrama mea preferată este „Uimitor de puține discoteci care oferă cutii de tonomat.”

Un pangram perfect este un pangram în care fiecare dintre litere apare o singură dată. Am găsit câteva surse online care listează pangramele perfecte cunoscute. Nimeni nu pare să fi încercat cu succes să le producă pe toate în mod exhaustiv, așa că am luat-o ca o provocare distractivă. Așa am găsit toate * pangramele perfecte de engleză. Voi explica asteriscul mai târziu.

• Crwth vox zaps qi gym fjeld bunk. (Sunetul unei vioare celtice lovește un centru de fitness orientat spre forțele spirituale din est situat într-un platou sterp al Scandinaviei.) Acesta este doar cuvinte legale Scrabble!
• Squdgy kilp job zarf nth cwm vex. (Alge malformat cumpără un încălzitor de ceașcă ornamentală pe care una dintre multele goluri pe jumătate deschise, abrupte, în capul unei văi sau pe malul muntelui a iritat-o.)
• Jock nimfele waqf droguri vex blitz. (Dotarea caritabilă a intoxicat spiritele pădurii, care l-au frustrat pe sportiv, care se angajează într-un atac.)
• Hm, vals fiord, cinci busk, pyx veg. (Să vedem, un dans lung îngust și adânc dansează, cei cinci de pe zaruri fac muzică pe stradă și micul container rotund pentru bolnavi și care nu se pot odihni.) De asemenea, Scrabble este legal, dar are o interjecție (Hm).

Din păcate, acestea sunt unele dintre cele mai lizibile propoziții pe care le-aș putea găsi *. Toate pangramele perfecte generate din Turneul Oficial și Club Word List 3 (OWL3) pentru Scrabble fără interjecții includ fie cuvântul cwm, fie crwth. Waqf este un turneu Scrabble legal în afara Americii de Nord.

Cum să găsești toate pangramele perfecte

Metoda pentru găsirea pangramelor perfecte vine în doi pași. Primul este să găsiți toate seturile de cuvinte care conțin o singură literă din alfabetul englez. Al doilea pas este de a vedea care dintre aceste seturi poate fi rearanjat în propoziții valide în limba engleză.

Pasul 1: Găsirea seturilor de cuvinte pentru pangrama perfectă

Pentru a începe să găsiți seturi de cuvinte care pentru alfabetul englez, este necesară o listă de cuvinte în limba engleză. Găsirea și menținerea unei liste de calitate a cuvintelor a fost mult mai dificilă decât anticipasem. Inițial, am crezut că acest proiect va dura două zile, dar a ajuns să dureze două săptămâni ca urmare a acestei probleme de calitate a datelor.

Am început cu dicționarul Unix, care este o listă disponibilă gratuit de cuvinte în limba engleză. care vine cu aproape toate sistemele de operare bazate pe Unix. Am observat imediat că lista are probleme de calitate. În primul rând, fiecare literă a alfabetului a fost considerată un cuvânt în dicționarul Unix și a inclus o mulțime de non-cuvinte, cum ar fi „vejoz”. Acest lucru a demonstrat necesitatea unei liste negre pentru a gestiona listele de cuvinte găsite online. Dicționarului Unix îi lipseau pluralele pentru cuvinte, așa că dicționarul ar include cuvântul „portocaliu”, dar nu „portocale”. Lista de cuvinte este atât de restrictivă, de fapt, încât nicio pangramă perfectă cunoscută anterior nu include doar cuvinte din dicționarul Unix. unele, cum ar fi „squdgy kilp job zarf nth cwm vex”.

Am apelat apoi la internet pentru a găsi seturi mai mari de cuvinte. Am găsit seturi de cuvinte foarte mari, care erau uriașe, dar când am început să caut pangrame perfecte din acele liste, am constatat că erau mult prea poluate cu cuvinte de calitate scăzută care nu sunt cuvinte engleze valabile. Chiar și după multe runde de iterații, tot nu am reușit să descopăr lista pentru a găsi pangrame rezonabile sau gestionabile. Am încercat să o curăț, creând o listă albă de cuvinte de anumite lungimi, dar lista era încă extrem de scăzută.

În cele din urmă, după multe iterații, am plătit 15 USD pentru a cumpăra un membru de încercare din America de Nord Scrabble® Players Association, care mi-a permis accesul la OWL3 proprietară și protejată prin drepturi de autor, care este sursa unor controverse. Chiar și atunci, a trebuit să adaug câteva cuvinte cunoscute în limba engleză, cum ar fi cuvintele dintr-o singură literă „a” și „I”.

Înarmat cu o listă adecvată de cuvinte, am implementat un algoritm pentru a produce toate seturile de cuvinte din acea listă care conțin fiecare una din fiecare literă a alfabetului englez. Voi descrie algoritmul în profunzime în secțiunea „Algoritmul” de mai jos.

Pasul 2: Formarea propozițiilor în limba engleză dintr-o pungă de cuvinte

Având în vedere un set de cuvinte, aflând dacă un o propoziție valabilă în limba engleză este posibilă cu toate cuvintele furnizate este o problemă banală, dar este mai ușoară decât majoritatea celorlalte probleme de procesare a limbajului natural (NLP).

Există euristici utile pentru eliminarea propozițiilor neeligibile; Am reușit să formez propoziții valide în limba engleză din cuvintele rămase după ce am urmat acele euristici. Frazele au fost adesea absurd, dar încă valabile. Iată euristicile pe care le-am folosit:

1. Trebuie să existe cel puțin un verb.
2. Nu poate exista decât un substantiv mai mult decât există verbe dacă nu există o conjuncție sau o prepoziție, ambele fiind foarte rare.
3. Dacă există adjective, trebuie să existe și substantive.

Euristicul funcționează parțial din cauza posibilității implicitului subiecți (nici perfectă, nici o pangramă, dar „mișcă-te liniștit și vorbește încet” este o propoziție cu două verbe și fără substantive, cu subiectul implicit al „tu”).

Deoarece spațiul cuvintelor este posibil să participați la pangrame perfecte, este destul de ușor să etichetați manual fiecare cuvânt individual cu părțile sale de vorbire eligibile și să vedeți dacă setul de cuvinte respectă aceste trei euristici simple. Dacă vă place sau nu calitatea frazelor produse este o chestiune de gust.

Algoritmul

Această secțiune este un pic tehnică, dar sperăm că este ușor de urmat. Simțiți-vă liber să treceți la secțiunea „Rezultate & Învățări”.

Strategie la nivel înalt

Scopul este de a produce toate seturile posibile de cuvinte din lista dată de cuvinte care acoperă alfabetul englezesc „perfect”.

1. Curățați lista de cuvinte pentru a reduce drastic spațiul de căutare, de ex. eliminați cuvintele care au litere repetate, cum ar fi „litere”.
2. Utilizați măști de biți pentru a reprezenta cuvintele în mod eficient și mapați-le înapoi la seturile originale de cuvinte.
3. Căutați în toate stările posibile, fiecare reprezentând o posibilă combinație de litere, prin repetarea repetată a listei de măști de biți. Performanța este îmbunătățită dramatic cu programarea dinamică.
4. Desenați săgețile (marginile direcționate) din starea de pangramă perfectă, starea finală care are scrisorile engleze, către statele intermediare care l-au compus. Faceți asta din nou cu statele intermediare pentru a crea o structură de date care poate reconstitui seturile de cuvinte care sunt posibile pangrame perfecte. Aceasta se numește backtracking.
5. seturile de cuvinte descoperite care sunt, eventual, pangrame perfecte ca copaci.

Curățarea listei, aka Canonicalization

Primul pas este de a curăța lista originală de cuvinte pentru a reduce spațiul de căutare și pentru a crește calitatea de ieșire.

1. Îndepărtați tot spațiul alb în jurul cuvântului și convertiți-l numai cu minuscule
2. Asigurați-vă că cuvintele conțin doar litere din alfabetul englez; Am folosit un filtru simplu de expresie regulată: /^+$/
3. Filtrează împotriva oricăror alte liste, de ex. liste negre; dacă un cuvânt se află pe lista neagră, săriți peste acel cuvânt
4. Eliminați toate cuvintele cu litere repetate

Acest lucru a scurtat semnificativ spațiul de căutare, de la liste de 200.000 ~ 370.000 de cuvinte la o mult mai mică de 35.000 ~ 65.000 de cuvinte.

Utilizarea măștilor de biți

Măștile de biți sunt reprezentări întregi ale stărilor. Există mai multe avantaje ale măștilor de biți:

• Măștile de biți reprezintă bine această problemă. Ordinea literelor nu contează, astfel încât toate combinațiile de cuvinte pot fi reprezentate ca o serie lungă de 26 de cifre de 0 și 1, fiecare cifră reprezentând dacă există sau nu o literă în combinație. De exemplu. dacă setul de cuvinte conține litera „e”, a cincea cifră va fi un 1, altfel un 0.
• Măștile de biți sunt eficiente: Deoarece spațiul de căutare este constant, măștile de biți oferă o stocare eficientă și reprezentarea tuturor combinațiilor posibile de litere. În plus, operațiunile în biți sunt rapide; pentru a testa dacă două măști de biți pot fi combinate pentru a produce o mască de biți mai mare, verificați dacă ȘI bitul celor două măști este egal cu 0, ambele fiind extrem de operații rapide.

Deci, transformați fiecare cuvânt într-o mască de biți, care poate fi reprezentată ca un întreg. De exemplu, cuvântul „cabină” este mapat la masca de biți de 111, care este numărul zecimal 7. Cuvântul „fi” este mapat la 10010, care este numărul zecimal 18 și așa mai departe. Cea mai mare mască de biți posibilă este una cu toate literele alfabetului, posibila stare de pangramă perfectă, 11111111111111111111111111, care este numărul zecimal 67.108.863 sau 2²⁶ -1. Aceasta se potrivește bine într-un număr întreg de 32 de biți semnat standard, care poate reprezenta la 2³¹-1.

Utilizarea măștilor de biți comprimă mai mult spațiul, deoarece anagramele cu un singur cuvânt se mapează la aceeași mască de biți. Atât „cuptorul”, cât și „legătura” se conectează la masca 10110100000000, care este numărul zecimal 11520. Aceasta reduce și mai mult spațiul de căutare de 35.000 ~ 65.000 de cuvinte la 25.000 ~ 45.000 de măști de biți.

Păstrați o mapare a măștii de biți înapoi la setul de cuvinte din care sunt derivate. Acest lucru va fi util la ieșirea seturilor de cuvinte.

Căutarea pangramului perfect cu programare dinamică

Nucleul algoritmului este destul de simplu:

Având în vedere o stare posibilă (care este compusă din combinații valide de cuvinte existente), încercați toate măștile din lista inițială de cuvinte pentru a vedea dacă este posibil să creați o nouă stare validă (verificând dacă bitul ȘI al starea și masca sunt egale cu 0, ceea ce ar însemna că nu există litere suprapuse). Creați noua stare utilizând operația SAU în biți care îmbină toate 1-urile împreună. Pentru fiecare nouă stare descoperită, continuați să repetați până când nu mai există stări neexplorate. Dacă acest lucru ajunge la final, asta înseamnă că algoritmul a găsit cel puțin un posibil set de cuvinte pangram perfect. Prima stare posibilă care poate enumera toate stările posibile este starea goală sau 0, unde nu sunt incluse litere ale alfabetului. Deci, începeți de acolo și apoi descoperiți recursiv care sunt stările posibile.

Un câștig imens de eficiență este să observați că există multe modalități de a ajunge la o stare intermitentă și că lucrarea la stat nu se schimbă în funcție de modul a fost atins. Deci, în loc să repetați lucrarea atunci când un stat este revizitat, stocați rezultatul fiecărui stat. Această tehnică se numește programare dinamică și transformă o problemă combinatorie complexă într-un program liniar. Procesul de stocare a stării intermitente se numește memoizare.

Deci, creați o matrice de dimensiune 2²⁶, între 0 și 67.108.863, inclusiv. Fiecare index reprezintă o stare de mască de biți, așa cum am explicat mai înainte. Valoarea la fiecare index al tabloului reprezintă ceea ce se știe despre stare. 0 înseamnă fie că statul este neatins, fie inaccesibil. 1 înseamnă că statul a găsit o modalitate de a ajunge la posibila stare de pangramă perfectă. -1 înseamnă că statul nu a reușit să găsească o modalitate de a ajunge la final.

Pseudocodul de mai jos:

Interlude: Complexitate și analiză practică a timpului de executare

Există 2²⁶ măști de biți posibili pentru o serie de 26 de biți. Deoarece fiecare stare este procesată o singură dată din cauza memoizării, timpul de rulare al acestui algoritm este O (n 2 ^ d), unde d este dimensiunea alfabetului, 26. Variabila n nu reprezintă numărul de cuvinte, ci numărul de măști de biți. Cu 67.108.863 și aproximativ 45.000 de măști de biți, acest lucru se dovedește a fi de ordinul a 3 trilioane, pe care MacBook Pro l-ar putea gestiona în aproximativ 45 de minute; tractabil pentru orice computer modern. De asemenea, merită remarcat faptul că stiva de apeluri recursive nu va ajunge niciodată mai adânc de 26 (probabil nu va ajunge niciodată mai adânc de 15), deci este, de asemenea, foarte ușor de gestionat și din acea dimensiune.

Un avantaj al abordării cu masca de biți cu numai 2²⁶ stări înseamnă că toate stările pot fi stocate în memorie. Deoarece există doar 3 valori pe stare (-1, 0, 1), aceasta poate fi stocată într-un singur octet. La un singur octeți pe stare, stările de 2²⁶ se ridică la aproximativ 67 de megaocteți, ceea ce este din nou foarte ușor de gestionat.

Pe măsură ce alfabetul crește, totuși, spațiul de căutare crește exponențial, la fel și timpul de rulare, provocând problema de a deveni intratabil foarte repede. O scurtă discuție despre abordarea pangramei perfecte pentru alfabete mai mari se află în secțiunea „Limbă cu alfabete mai mari” de mai jos.

Construirea dinamică a unui grafic aciclic direcționat (DAG)

Acum că au completat stările de mască de biți, este timpul să recuperăm soluția!

Pentru a găsi seturile de cuvinte care au creat setul de posibile pangrame perfecte, trebuie să obținem care state intermediare au fost esențiale pentru compunerea stărilor finale Apoi, întrebarea de urmărire este ce alte state intermediare au compus acele state intermediare și așa mai departe până când singurul lucru care rămâne sunt statele care se mapează direct la cuvinte. Acest proces se numește backtracking.

urmărirea relațiilor dintre state, scopul este crearea unui Di Acyclical Graph (DAG), care menține care state intermediare compun orice stare dată. DAG-urile sunt ușor de parcurs pentru a prelua ieșirile, mai ales datorită naturii lor neciclice. Pentru a construi, porniți de la posibila stare pangramă perfectă și creați o margine direcționată (săgeată) care indică stările intermediare care o compun. Repetați procesul cu statele intermediare și va produce un DAG. Nu vor exista niciodată cicluri deoarece săgețile indică întotdeauna o stare cu o valoare mai mică.

În loc să reconstruiți relațiile care au fost descoperite în etapa de căutare, care implică parcurgerea din nou prin trilioane de combinații de stări posibile, este mai eficient să construiți DAG în timpul fazei de programare dinamică. În interiorul metodei de rezolvare, dacă o stare nou construită poate ajunge la starea de pangramă perfectă posibilă, stocați o margine direcționată de la starea nou construită la starea inițială numai dacă starea inițială este mai mică decât complementul său (pentru a reduce duplicarea muchiilor). p>

Imprimați fructele muncii dvs. sub formă de copac!

Probabil cel mai ușor format pentru vizualizarea seturilor de cuvinte rezultate este prin listarea lor ca arborii cu nodul rădăcină drept starea pangramă perfectă. Având în vedere DAG-ul construit de sus, cel mai bun mod de a-l despacheta este de a face acest lucru recursiv, scriind fiecare stare pe disc pe fiecare pas în loc de în memorie, deoarece arborele este un ordin de mărime mai mare decât DAG.

îmbunătățire a acestei forme de extindere este de a rezuma stările care au o singură combinație posibilă de cuvinte. O stare care este o mască pentru cuvinte și fără substate care o compun poate fi rezumată în mod trivial. O stare poate fi rezumată dacă substatele și compozitele sale pot fi rezumate și toate măștile derivate din ea însăși și din copiii săi nu au biți / caractere suprapuse. Imprimarea DAG-ului rezumat îmbunătățește lizibilitatea arborelui de ieșire rezultat prin scurtarea și simplificarea acestuia.

Întrucât rezumarea depinde doar de cea mai mică dintre cele două stări, iterând prin matrice de la starea inițială de la 0 în sus și utilizarea regulilor de mai sus pentru a gestiona regula de rezumare permite ca aceasta să fie finalizată în timp liniar.

Arborii Pangram Produși!

Simțiți-vă liber să traversați copacii Pangram perfecți pentru a vedea dacă pot găsi propoziții interesante!

Există o mulțime de pangrame perfecte posibile

Am fost surprins de numărul de pangrame perfecte posibile. Există o mulțime! Cea mai bună strategie pentru asocierea lor nu necesită un procesor de limbaj natural complex. Odată ce cuvintele candidate au fost etichetate ca substantiv sau verb eligibil, pachetul de cuvinte trebuie să conțină cel puțin un substantiv, un verb și raportul corect dintre substantive și verbe.

Calitatea datelor este o problemă dificilă

Secțiunea algoritmului a durat două zile, dar problema calității datelor a durat două săptămâni. Când i-am menționat această constatare prietenului meu care este inginer senior Google, el nu a fost surprins, comentând că problemele legate de calitatea datelor sunt unele dintre cele mai dificile probleme din inginerie. Lecția învățată.

Regulile Pangramelor Perfecte

Există o mulțime de nuanțe în ceea ce privește ceea ce se califică ca o Pangramă perfectă! Am vrut să caut prin pangrame fără interjecții (de exemplu, hm, pht), dar există și alte restricții populare, cum ar fi abrevieri, acronime, contracții, inițialisme, litere izolate, substantive proprii și cifre romane. Există, de asemenea, cuvinte care sunt nume de litere, cum ar fi Qoph, pe care am simțit că le înșeală.

Cu unele dintre aceste constrângeri relaxate, există o mulțime de pangrame „perfecte”. În ordinea trilioanelor, probabil . Există o mulțime de acronime și inițialisme.

Asteriscul

Asteriscul este în loc, deoarece definiția tuturor pangramelor perfecte ale limbii engleze nu este bine definită. Există nuanțe legat de ceea ce ar trebui permis în pangramele perfecte de engleză. Există, de asemenea, o mulțime de contestații cu privire la faptul dacă unele cuvinte sunt sau nu chiar cuvinte în limba engleză. Având în vedere aceste nuanțe, este cu adevărat dificil de spus că am găsit toate pangramele perfecte. Pot face două afirmații destul de încrezător:

1. Am găsit o metodologie pentru a produce toate pangramele perfecte de engleză și alte limbi cu seturi de caractere similare sau mai mici.
2. I au enumerat toate seturile de cuvinte care pot forma pangrame perfecte folosind dicționarul oficial al turneului Scrabble y, OWL3.

Vă rugăm să nu ezitați să vă produceți propriile pangrame perfecte cu tehnicile descrise în această postare!

Dependența Perfect Pangrams de cuvintele cu rădăcini galeze și arabe

Cuvintele derivate din galeză și arabă au fost cu adevărat importante pentru existența pangramelor englezești perfecte (cu excepția cazului în care constrângerile pangramului perfect sunt relaxate). Folosind lista de cuvinte OWL3 cu reguli stricte privind pangramele perfecte, nu există pangrame perfecte care să nu includă cuvintele „cwm (s)” sau „crwth (s)”, ambele cuvinte galeze. În Scrabble internațional, cuvântul derivat din arabă „waqf (s)” este un cuvânt valid care poate produce pangrame perfecte fără a recurge la „cwm (s)” sau „crwth (s)”.

Eficiențe ale fluxului de lucru

A fost important să devenim mai eficienți în paralelizarea sarcinilor în timpul acestui proiect. O cursă completă durează 25 de minute pentru dicționarul Unix și aproape o oră pentru dicționarele cu adevărat mari. Am avut câteva probleme inițiale de schimbare a contextului pentru o fereastră de 30 de minute, dar m-am îmbunătățit în timp ce mergeam pentru a-mi îmbunătăți productivitatea.

Extensie / Generalizare – Anagram Finder

căutarea este, de asemenea, echivalentă cu un căutător de anagramă pentru șirul „abcdefghijklmnopqrstuvwxyz”. Ce se întâmplă dacă ați dori să construiți un căutător de anagramă generic?

Aceeași tehnică poate fi utilizată atât timp cât regulile de reprezentare de stat și de gestionare pentru verificare validitatea combinației de cuvinte este actualizată. În loc ca statele să fie gestionate ca un număr întreg, ar fi mai ușor să urmăriți starea ca o hartă a caracterelor relevante. A vedea dacă combinațiile sunt valabile înseamnă că combinația a două hărți nu depășește numărul de caractere dorit de anagramă pentru fiecare literă. Asigurați-vă că spațiul de stare este tractabil; cu prea multe litere, spațiul de căutare poate deveni foarte mare într-o clipită. De asemenea, aveți permisiunea de a repeta cuvinte? Asigurați-vă că definiți aceste reguli în interior programarea ta dinamică soluție.

Limbi cu alfabete mai mari

Această abordare și soluție sunt liniare în dimensiunea setului de cuvinte, dar exponențiale în dimensiunea alfabetului. Este posibil ca această abordare să nu funcționeze cu un set de caractere mai mare, spune japoneza modernă care are 46 de silabare. 2⁴⁶ este 70.368.744.177.664; de peste un milion de ori mai mare decât spațiul de căutare în limba engleză de 2²⁶ = 67.108.864.

Nu este clar dacă această abordare ar funcționa sau nu pentru japonezi. Dacă limba japoneză are o entropie suficient de scăzută, ceea ce este posibil, această abordare ar fi viabilă. În loc să inițializeze o matrice de dimensiunea 2⁴⁶, stările vor fi urmărite pe o hartă. Mai mult, structura japoneză poate fi exploatată; de exemplu kana を (wo) este folosit aproape exclusiv ca participiu post pozițional și poate fi exclus din căutare, reducând spațiul de căutare.

Limba cambodgiană din Khmer are cel mai mare alfabet cu 74. Un alt posibil pas următor este explorarea soluțiilor care sunt sub-exponențiale în dimensiunea alfabetului.

Inspirație

Am fost inspirat de progresul lui Aubrey De Grey în găsirea numărului cromatic al planului care urmează să fie cel puțin 5. Acesta este un progres semnificativ care a fost realizat prin metode de calcul de bază.

Inutil să spun că găsirea pangramelor perfecte nu menține o lumânare pentru îmbunătățirea limitei inferioare a numărului cromatic al unui plan.

Acest lucru mă face să cred că există o mulțime de probleme cu fructe cu agățare redusă, care au metode de calcul simple pentru a rezolva o problemă care poate fi rezolvată manual. Vă provoc să găsiți și să rezolvați unele dintre aceste probleme. Vă rog să-mi spuneți dacă găsiți ceva!

Mulțumesc

Sunt foarte recunoscător pentru prietenii mei foarte excelenți care au ajutat prin corectarea și blocarea cu mine, în special Anna Zeng, Catherine Gao, Danny Wasserman, George Washington și Nick Wu!