Tutti * i pangram perfetti dellinglese

Un Il pangram inglese è una frase che contiene tutte le 26 lettere dellalfabeto inglese. Il pangram inglese più noto è probabilmente “La rapida volpe marrone salta sul cane pigro”. Il mio pangram preferito è “Sorprendentemente poche discoteche forniscono jukebox”.

Un pangram perfetto è un pangram in cui ciascuna delle lettere appare solo una volta. Ho trovato alcune fonti online che elencano i noti pangram perfetti. Nessuno sembra aver tentato con successo di produrli tutti in modo esauriente, quindi lho presa come una sfida divertente. È così che ho trovato tutti * i pangram perfetti dellinglese. Spiegherò lasterisco più tardi.

• Crwth vox zaps qi gym fjeld bunk. (Il suono di un violino celtico colpisce un centro fitness incentrato sulle forze spirituali orientali situato in un altopiano arido della Scandinavia.) Queste sono tutte parole legali di Scrabble!
• Squdgy kilp job zarf nth cwm vex. (Lalga mal formata compra uno scaldino ornamentale che ha irritato uno dei tanti avvallamenti semiaperti in fondo a una valle o al fianco di una montagna.)
• Ninfe atletiche waqf droga vex blitz. (La dotazione caritatevole ha intossicato gli spiriti della foresta, che hanno frustrato latleta, che si impegna in un attacco.)
• Hm, fjord waltz, cinq busk, pyx veg. (Vediamo, uninsenatura profonda e lunga e stretta danza, il cinque sui dadi fa musica per strada e il piccolo contenitore rotondo per i malati e gli incapaci riposa.) Anche Scrabble legale, ma ha uninteriezione (Hm).

Sfortunatamente, queste sono alcune delle frasi più leggibili che ho trovato *. Tutti i pangram perfetti generati dal torneo ufficiale e dalla lista di parole del club 3 (OWL3) per Scrabble senza interiezioni includono la parola cwm o crwth. Waqf è legale per i tornei di Scrabble al di fuori del Nord America.

Come trovare tutti i pangram perfetti

Il metodo per trovare pangram perfetti prevede due passaggi. Il primo è trovare tutti i gruppi di parole che contengono ciascuna lettera dellalfabeto inglese una volta. Il secondo passaggio è vedere quale di questi insiemi può essere riorganizzato in frasi inglesi valide.

Passaggio 1: trovare insiemi di parole per il pangram perfetto

Per iniziare a trovare insiemi di parole che lalfabeto inglese richiede un elenco di parole inglesi. Trovare e mantenere un elenco di parole di alta qualità è stato molto più difficile di quanto mi aspettassi. Inizialmente, pensavo che questo progetto avrebbe richiesto due giorni, ma alla fine ci sono volute due settimane a causa di questo problema di qualità dei dati.

Ho iniziato con il dizionario Unix, che è un elenco di parole inglesi liberamente disponibile che viene fornito con quasi tutti i sistemi operativi basati su Unix. Ho notato subito che lelenco presentava problemi di qualità. In primo luogo, ogni lettera dellalfabeto era considerata una parola nel dizionario Unix e includeva molte non parole, come “vejoz”. Ciò dimostrava la necessità di una lista nera per gestire gli elenchi di parole trovate online. In secondo luogo, il Il dizionario Unix mancava di plurali per le parole, quindi il dizionario includeva la parola “arancione” ma non “arance”. Lelenco delle parole è così restrittivo, infatti, che nessun pangram perfetto precedentemente noto include solo parole dal dizionario Unix. Ho ancora trovato alcuni, come “squdgy kilp job zarf nth cwm vex”.

Mi sono poi rivolto a Internet per trovare gruppi di parole più grandi. Ho trovato gruppi di parole molto grandi che erano enormi, ma quando ho iniziato a cercare pangram perfetti da quegli elenchi, ho scoperto che erano troppo inquinati da parole di bassa qualità che non sono parole inglesi valide. Anche dopo molti round di iterazione, non sono riuscito ancora ad abbattere lelenco per trovare pangram ragionevoli o gestibili. Ho provato a ripulirlo creando una whitelist di parole di una certa lunghezza, ma lelenco era ancora di qualità estremamente bassa.

Alla fine, dopo molte iterazioni, ho pagato $ 15 per acquistare un abbonamento di prova al North American Scrabble® Players Association, che mi ha dato accesso al OWL3 proprietario e protetto da copyright, che è fonte di alcune controversie. Anche allora, ho dovuto aggiungere alcune parole conosciute in inglese, come le parole di una sola lettera “a” e “I”.

Armato di un elenco corretto di parole, ho implementato un algoritmo per produrre tutte le serie di parole da quella lista che ciascuna contiene una di ogni lettera dellalfabeto inglese. Descriverò in profondità lalgoritmo nella sezione “Lalgoritmo” di seguito.

Passaggio 2: formazione di frasi in inglese da un sacco di parole

Dato un insieme di parole, capire se un una frase inglese valida è possibile con tutte le parole fornite è un problema non banale, ma è più facile della maggior parte degli altri problemi di elaborazione del linguaggio naturale (PNL).

Esistono utili euristiche per eliminare le frasi non ammissibili; Sono stato in grado di formare frasi in inglese valide dalle parole rimanenti dopo aver seguito quelle euristiche. Le frasi erano spesso prive di senso, ma comunque valide. Ecco le euristiche che ho usato:

1. Deve esserci almeno un verbo.
2. Ci può essere solo un nome in più rispetto ai verbi a meno che non ci sia una congiunzione o una preposizione, entrambe molto rare.
3. Se ci sono aggettivi, devono esserci anche nomi.

Leuristica funziona in parte a causa della possibilità di impliciti soggetti (né perfetto né un pangram, ma “muoviti in silenzio e parla piano” è una frase con due verbi e nomi, con il soggetto implicito di “tu”).

Poiché lo spazio delle parole che può possibilmente partecipare a pangram perfetti è piccolo, è abbastanza facile etichettare manualmente ogni singola parola con le sue parti ammissibili del discorso e vedere se linsieme di parole obbedisce a queste tre semplici euristiche. Che ti piaccia o meno la qualità delle frasi prodotte è una questione di gusti.

Lalgoritmo

Questa sezione è un po tecnica, ma si spera ancora facile da seguire. Sentiti libero di passare alla sezione “Risultati & Apprendimento”.

Strategia di alto livello

Lobiettivo è produrre tutti i possibili set di parole dallelenco di parole fornito che abbraccia lalfabeto inglese “perfettamente”.

1. Pulisci lelenco di parole per ridurre drasticamente lo spazio di ricerca, ad es. rimuovere le parole che hanno lettere ripetute, come “lettere”.
2. Utilizzare maschere di bit per rappresentare le parole in modo efficiente e mapparle di nuovo ai gruppi di parole originali.
3. Cerca in tutti gli stati possibili, ognuna rappresenta una possibile combinazione di lettere, iterando ripetutamente lelenco delle maschere di bit. Le prestazioni sono notevolmente migliorate con la programmazione dinamica.
4. Disegna frecce (bordi diretti) dallo stato pangram perfetto, lo stato finale che ha tutto le lettere inglesi, agli stati intermedi che lhanno composto. Ripetilo con gli stati intermedi per creare una struttura dati che possa ricostruire gli insiemi di parole che sono possibili pangram perfetti. Questo si chiama backtracking.
5. Output gli insiemi di parole scoperti che potrebbero essere pangram perfetti come alberi.

Pulire lelenco, noto anche come Canonicalizzazione

Il primo passaggio è pulire lelenco originale di parole per ridurre lo spazio di ricerca e aumentare la qualità delloutput.

1. Elimina tutti gli spazi bianchi attorno alla parola e convertilo solo in minuscolo
2. Assicurati che le parole contengano solo lettere dellalfabeto inglese; Ho utilizzato un semplice filtro di espressioni regolari: /^+$/
3. Filtro rispetto a qualsiasi altro elenco, ad es. liste nere; se una parola è nella lista nera, salta quella parola
4. Rimuovi tutte le parole con lettere ripetute

Ciò ha ridotto notevolmente lo spazio di ricerca, da elenchi di 200.000 ~ 370.000 parole a 35.000 ~ 65.000 parole molto più piccole.

Uso di maschere di bit

Le maschere di bit sono rappresentazioni di interi di stati. Ci sono molti vantaggi delle maschere di bit:

• Le maschere di bit rappresentano bene questo problema. Lordinamento delle lettere non ha importanza, quindi tutte le combinazioni di parole possono essere rappresentate come una serie di 26 cifre di 0 e 1, con ogni cifra che rappresenta se una lettera esiste o meno nella combinazione. Per esempio. se linsieme di parole contiene la lettera “e”, la quinta cifra sarà 1, altrimenti 0.
• Le maschere di bit sono efficienti: poiché lo spazio di ricerca è costante, le maschere di bit offrono una memorizzazione efficiente e rappresentazione di tutte le possibili combinazioni di lettere. Inoltre, le operazioni bit per bit sono veloci; per verificare se due maschere di bit possono essere combinate per produrre una maschera di bit più grande, controllare se lAND bit per bit delle due maschere è uguale a 0, entrambi estremamente operazioni veloci.

Quindi, trasforma ogni parola in una maschera di bit, che può essere rappresentata come un numero intero. Ad esempio, la parola “cab” viene mappata alla maschera di bit di 111, che è il numero decimale 7. La parola “be” viene mappata a 10010, che è il numero decimale 18, e così via. La maschera di bit più grande possibile è quella con tutte le lettere dellalfabeto, il possibile stato pangram perfetto, 11111111111111111111111111, che è il numero decimale 67.108.863, o 2²⁶ -1. Questo si adatta bene a un intero standard a 32 bit con segno, che può rappresentare a 2³¹-1.

Luso di maschere di bit comprime ulteriormente lo spazio, poiché gli anagrammi di una singola parola mappano alla stessa maschera di bit. Sia “forno” che “collegamento” vengono mappati alla maschera 10110100000000, che è il numero decimale 11520. Questo riduce ulteriormente lo spazio di ricerca di 35.000 ~ 65.000 parole a 25.000 ~ 45.000 maschere di bit.

Conserva una mappatura della maschera di bit sullinsieme di parole da cui derivano. Ciò sarà utile durante loutput di gruppi di parole.

Ricerca del pangram perfetto con la programmazione dinamica

Il nucleo dellalgoritmo è abbastanza semplice:

Dato un possibile stato (che è composto da combinazioni valide di parole esistenti), provare tutte le maschere dallelenco di parole iniziale per vedere se è possibile creare un nuovo stato valido (controllando se lAND bit per bit di lo stato e la maschera sono uguali a 0, il che significherebbe che non ci sono lettere sovrapposte). Crea il nuovo stato utilizzando loperazione OR bit per bit che unisce tutti gli 1 insieme. Per ogni nuovo stato scoperto, continua a ripetere finché non ci sono più stati inesplorati. Se questo raggiunge la fine, significa che lalgoritmo ha trovato almeno un possibile set di parole pangram perfetto. Il primo stato possibile che può enumerare tutti gli stati possibili è lo stato vuoto o 0, dove non sono incluse lettere dellalfabeto. Quindi inizia da lì e poi scopri ricorsivamente quali stati sono possibili.

Un enorme guadagno di efficienza è notare che ci sono molti modi per raggiungere uno stato intermittente e che il lavoro sullo stato non cambia in base a come esso è stato raggiunto. Quindi, invece di ripetere il lavoro quando uno stato viene rivisitato, memorizza il risultato di ciascuno stato. Questa tecnica è chiamata programmazione dinamica e trasforma un complesso problema combinatorio in un programma lineare. Il processo di memorizzazione dello stato intermittente è chiamato memoizzazione.

Quindi crea un array di dimensione 2²⁶, tra 0 e 67.108.863 inclusi. Ogni indice rappresenta uno stato di maschera di bit come spiegato in precedenza. Il valore in ogni indice della matrice rappresenta ciò che è noto sullo stato. 0 significa che lo stato è intatto o irraggiungibile. 1 significa che lo stato ha trovato un modo per raggiungere il possibile stato pangram perfetto. -1 significa che lo stato non è riuscito a trovare un modo per raggiungere la fine.

Pseudocodice di seguito:

Interludio: complessità e analisi pratica del runtime

Ci sono 2²⁶ possibili maschere di bit per una serie di 26 bit. Poiché ogni stato viene elaborato una sola volta a causa della memoizzazione, il tempo di esecuzione di questo algoritmo è O (n 2 ^ d), dove d è la dimensione dellalfabeto, 26. La variabile n non rappresenta il numero di parole, ma il numero di maschere di bit. Con 67.108.863 e circa 45.000 maschere di bit, si ottiene un valore dellordine di 3 trilioni, che il mio MacBook Pro potrebbe gestire in circa 45 minuti; trattabile per qualsiasi computer moderno. Vale anche la pena notare che lo stack di chiamate ricorsive non diventerà mai più profondo di 26 (probabilmente non diventerà mai più profondo di 15), quindi è anche molto gestibile da quella dimensione.

Un vantaggio dellapproccio della maschera di bit con solo 2²⁶ stati è che tutti gli stati possono essere salvati in memoria. Poiché ci sono solo 3 valori per stato (-1, 0, 1), questo può essere memorizzato in un singolo byte. A un singolo byte per stato, gli stati di 2²⁶ arrivano a circa 67 megabyte, il che è di nuovo molto gestibile.

Con laumentare dellalfabeto, tuttavia, lo spazio di ricerca aumenta in modo esponenziale e così il tempo di esecuzione, causando problema di diventare intrattabile molto rapidamente. Una breve discussione sullapproccio al pangram perfetto per alfabeti più grandi si trova nella sezione “Lingua con alfabeti più grandi” di seguito.

Creazione dinamica di un grafico aciclico diretto (DAG)

Ora che abbiamo hanno compilato gli stati della maschera di bit, è ora di recuperare la soluzione!

Per trovare gli insiemi di parole che hanno creato linsieme dei possibili pangram perfetti, dobbiamo derivare quali stati intermedi erano parte integrante della composizione degli stati finali . Quindi, la domanda successiva è quali altri stati intermedi hanno composto quegli stati intermedi, e così via finché lunica cosa rimasta sono gli stati che mappano direttamente alle parole. Questo processo è chiamato backtracking.

traccia delle relazioni tra gli stati, lobiettivo è creare un Di rected Acyclical Graph (DAG), che mantiene quali stati intermedi compongono un dato stato. I DAG sono facili da attraversare per recuperare gli output, soprattutto a causa della loro natura non ciclica. Per costruire, partire dal possibile stato del pangramma perfetto e creare un bordo diretto (freccia) che punti agli stati intermedi che lo compongono. Ripeti il processo con gli stati intermedi e produrrà un DAG. Non ci saranno mai cicli perché le frecce indicano sempre uno stato con un valore inferiore.

Invece di ricostruire le relazioni scoperte nella fase di ricerca, che prevede lattraversamento di nuovo attraverso trilioni di possibili combinazioni di stati, è più efficiente costruire il DAG durante la fase di programmazione dinamica. Allinterno del metodo di risoluzione, se uno stato di nuova costruzione può raggiungere il possibile stato pangram perfetto, memorizzare un bordo diretto dallo stato di nuova costruzione allo stato originale solo se lo stato originale è più piccolo del suo complemento (per ridurre la duplicazione del bordo).

Stampa i frutti del tuo lavoro sotto forma di albero!

Probabilmente il formato più semplice per visualizzare gli insiemi di parole risultanti è elencarli come alberi con il nodo radice come stato del pangram perfetto. Dato il DAG costruito dallalto, il modo migliore per decomprimerlo è farlo in modo ricorsivo, scrivendo ogni stato su disco in ogni passaggio invece che in memoria poiché lalbero è un ordine di grandezza maggiore del DAG.

Un miglioramento di questa forma di espansione consiste nel riassumere gli stati che hanno una sola possibile combinazione di parole. Uno stato che è una maschera per le parole e non sottostati che lo compongono può essere banalmente riassunto. Uno stato può essere riassunto se i suoi sottostati e i suoi composti possono essere riassunti e tutte le maschere derivate da se stesso e dai suoi figli non hanno bit / caratteri sovrapposti. La stampa del DAG riepilogato migliora la leggibilità dellalbero di output risultante accorciandolo e semplificandolo.

Poiché il riepilogo dipende solo dal più piccolo dei due stati, iterando attraverso larray dallo stato iniziale di 0 in su e lutilizzo delle regole precedenti per gestire la regola di riepilogo consente di completare questa operazione in tempo lineare.

Alberi di pangram prodotti!

Sentiti libero di attraversare gli alberi di pangram perfetti per vedere se può trovare frasi interessanti!

Ci sono molti possibili pangram perfetti

Sono rimasto sorpreso dal numero di perfetti pangram possibili. Ci sono molti! La migliore strategia per metterli insieme non richiede un elaboratore di linguaggio naturale complesso. Una volta che le parole candidate sono state etichettate come sostantivo o verbo idonee, il pacchetto di parole deve contenere almeno un sostantivo, un verbo e il giusto rapporto tra nomi e verbi.

La qualità dei dati è un problema difficile

La sezione algoritmo ha richiesto due giorni, ma il problema della qualità dei dati ha richiesto due settimane. Quando ho menzionato questa scoperta al mio amico che è un ingegnere senior di Google, non è rimasto sorpreso, commentando che i problemi di qualità dei dati sono alcuni dei problemi più difficili in ingegneria. Lezione appresa.

Le regole dei pangram perfetti

Ci sono molte sfumature su ciò che si qualifica come un pangram perfetto! Volevo cercare attraverso i pangram senza alcuna interiezione (ad esempio hm, pht), ma ci sono anche altre restrizioni popolari come abbreviazioni, acronimi, contrazioni, inizialismi, lettere isolate, nomi propri e numeri romani. Ci sono anche parole che sono nomi di lettere, come Qoph, che ho sentito barare.

Con alcuni di questi vincoli allentati, ci sono molti pangram “perfetti”. Nellordine di trilioni, probabilmente . Ci sono molti acronimi e inizialismi.

Lasterisco

Lasterisco è a posto perché la definizione di tutti i pangrammi perfetti dellinglese non è ben definita. Ci sono sfumature relative a ciò che dovrebbe essere consentito in perfetti pangram di inglese. Ci sono anche molte controversie sul fatto che alcune parole siano o meno parole inglesi. Date queste sfumature, è davvero difficile dire che ho trovato tutti i pangram perfetti. Posso fare due affermazioni abbastanza fiduciosamente:

1. Ho trovato una metodologia per produrre tutti i pangram perfetti dellinglese e di altre lingue con set di caratteri simili o più piccoli.
2. I hanno enumerato tutte le serie di parole che possono eventualmente formare pangram perfetti utilizzando il dizionario ufficiale del torneo Scrabble y, OWL3.

Sentiti libero di produrre i tuoi pangram perfetti con le tecniche descritte in questo post!

La dipendenza di Perfect Pangrams da parole di origine gallese e araba

Le parole di derivazione gallese e araba erano davvero importanti per lesistenza di perfetti pangram inglesi (a meno che i vincoli del pangram perfetto non fossero allentati). Utilizzando lelenco di parole OWL3 con regole rigide riguardanti i pangram perfetti, non ci sono pangram perfetti che non includano le parole “cwm (s)” o “crwth (s)”, entrambe parole gallesi. Nello Scrabble internazionale, la parola derivata dallarabo “waqf (s)” è una parola valida che può produrre pangram perfetti senza ricorrere a “cwm (s)” o “crwth (s)”.

Efficienza del flusso di lavoro

Era importante diventare più efficienti nel parallelizzare le attività durante questo progetto. Unesecuzione completa richiede 25 minuti per il dizionario Unix e quasi unora per i dizionari molto grandi. Ho avuto qualche problema iniziale nel cambio di contesto per una finestra di 30 minuti, ma sono migliorato man mano che andavo avanti per migliorare la mia produttività.

Estensione / Generalizzazione – Anagram Finder

Il pangram perfetto la ricerca è anche equivalente a un cercatore di anagrammi per la stringa “abcdefghijklmnopqrstuvwxyz”. E se volessi creare un cercatore di anagrammi generico?

La stessa tecnica può essere utilizzata fintanto che la rappresentazione dello stato e le regole di gestione per il controllo la validità della combinazione di parole viene aggiornata. Invece di gestire gli stati come un numero intero, sarebbe più facile tracciare lo stato come una mappa dei caratteri rilevanti. Vedere se le combinazioni sono valide significa dire che la combinazione di due mappe non supera il il numero di caratteri desiderato dellanagramma per ogni lettera. Assicurati solo che lo spazio di stato sia trattabile; con troppe lettere, lo spazio di ricerca può diventare davvero grande in un batter docchio. Inoltre, puoi ripetere le parole? Assicurati di definire quelle regole allinterno la tua programmazione dinamica soluzione.

Lingue con alfabeti più grandi

Questo approccio e la soluzione sono lineari nella dimensione dellinsieme di parole, ma esponenziali nella dimensione dellalfabeto. Questo approccio potrebbe non funzionare con un set di caratteri più ampio, ad esempio il giapponese moderno che ha 46 sillabari. 2⁴⁶ è 70.368.744.177.664; oltre un milione di volte più grande dello spazio di ricerca inglese di 2²⁶ = 67.108.864.

Non è del tutto chiaro se questo approccio potrebbe funzionare o meno per il giapponese. Se la lingua giapponese ha unentropia sufficientemente bassa, il che è possibile, questo approccio sarebbe praticabile. Invece di inizializzare un array di dimensione 2⁴⁶, gli stati verranno tenuti tracciati in una mappa. Inoltre, la struttura del giapponese può essere sfruttata; per esempio il kana を (wo) è quasi esclusivamente usato come participio posizionale post, e può essere escluso dalla ricerca, riducendo lo spazio di ricerca.

La lingua cambogiana del Khmer ha lalfabeto più grande con 74. Un altro possibile passo successivo è esplorare soluzioni sotto-esponenziali nella dimensione dellalfabeto.

Ispirazione

Sono stato ispirato dal progresso di Aubrey De Grey nel trovare il numero cromatico del piano da almeno 5. Questo è un avanzamento significativo che è stato ottenuto attraverso metodi computazionali di base.

Inutile dire che trovare pangram perfetti non tiene una candela per migliorare il limite inferiore del numero cromatico di un piano.

Questo mi fa credere che ci siano molti problemi con frutta a bassa pendenza che hanno metodi di calcolo semplici per risolvere un problema che è manualmente intrattabile. Ti sfido a trovare e risolvere alcuni di questi problemi. Per favore fatemi sapere se trovate qualcosa!

Grazie

Sono molto grato per i miei eccellenti amici che mi hanno aiutato correggendo e provando con me, in particolare Anna Zeng, Catherine Gao, Danny Wasserman, George Washington e Nick Wu!