Alle * perfekte pangrammer på engelsk

En Engelsk pangram er en setning som inneholder alle 26 bokstaver i det engelske alfabetet. Den mest kjente engelske pangramen er sannsynligvis «The quick brown fox jumps over the lazy dog». Min favorittpangram er «Utrolig få diskoteker gir jukebokser.»

En perfekt pangram er et pangram der hver av bokstavene vises bare en gang. Jeg har funnet noen kilder på nettet som viser de kjente perfekte pangramene. Ingen ser ut til å ha forsøkt å lykkes med å produsere dem alle uttømmende, så jeg tok det på meg som en morsom utfordring. Slik fant jeg alle * de perfekte pangramene på engelsk. Jeg vil forklare stjernen senere.

• Crwth vox zaps qi gym fjeld bunk. (Lyden av en keltisk fiolin treffer et østlig åndelig kreftfokusert treningssenter som ligger på et kargt platå i Skandinavia.) Dette er alle lovlige ord fra Scrabble! (Den dårlige formede taren kjøper en dekorativ koppvarmer som en av mange halvåpne bratte sider i hodet av en dal eller fjellsiden har irritert.)
• Jock nymfer waqf drug vex blitz. (Veldedighetsbegavelsen beruset skogsåndene, som frustrerte utøveren, som driver et angrep.)
• Hm, fjord vals, cinq busk, pyx veg. (La oss se, en lang, smal, dyp innløp danser, de fem på terningen lager musikk på gaten, og den lille runde beholderen for syke og ute av stand til å hvile.) Også Scrabble lovlig, men har et interjeksjon (Hm).

Dette er dessverre noen av de mest lesbare setningene jeg kunne finne *. Alle perfekte pangrammer generert fra den offisielle turneringen og Club Word List 3 (OWL3) for Scrabble uten interjections inkluderer enten ordet cwm eller crwth. Waqf er Scrabble-turnering lovlig utenfor Nord-Amerika.

Hvordan finne alle de perfekte pangramene

Metoden for å finne perfekte pangrammer kommer i to trinn. Den første er å finne alle sett med ord som inneholder hver bokstav i det engelske alfabetet en gang. Det andre trinnet er å se hvilke av disse settene som kan omorganiseres til gyldige engelske setninger.

Trinn 1: Finne sett med ord for det perfekte pangramet

Å begynne å finne sett med ord som spenner det engelske alfabetet krever en liste med engelske ord. Å finne og vedlikeholde en ordliste av høy kvalitet var mye vanskeligere enn jeg hadde forventet. Opprinnelig trodde jeg dette prosjektet ville ta to dager, men det endte opp med å ta to uker som et resultat av dette datakvalitetsproblemet.

Jeg startet med Unix-ordboken, som er en fritt tilgjengelig liste over engelske ord. som kommer med nesten alle Unix-baserte operativsystemer. Jeg la merke til umiddelbart at listen hadde kvalitetsproblemer. For det første ble hver bokstav i alfabetet ansett som et ord i Unix-ordboken, og den inneholdt mange ikke-ord, som «vejoz». Dette demonstrerte behovet for en svarteliste for å administrere ordlister som ble funnet online. Unix-ordboken manglet flertall for ord, så ordboken ville inneholde ordet «oransje» men ikke «appelsiner». Ordlisten er faktisk så begrensende at ingen tidligere kjente perfekte pangrammer bare inneholder ord fra Unix-ordboken. Jeg fant fremdeles noen, for eksempel «squdgy kilp job zarf nth cwm vex».

Jeg vendte meg da mot internett for å finne større sett med ord. Jeg fant veldig store ordsett som var enorme, men da jeg begynte å grave etter perfekte pangrammer fra disse listene, fant jeg ut at de var altfor forurenset med ord av lav kvalitet som ikke er gyldige engelske ord. Selv etter mange iterasjonsrunder klarte jeg fortsatt ikke å pare ned listen for å finne noen rimelige eller håndterbare pangrammer. Jeg prøvde å rydde opp ved å lage en hvitliste med ord av bestemte lengder, men listen var fortsatt ekstremt lav kvalitet.

Til slutt, etter mange gjentakelser, betalte jeg $ 15 for å kjøpe et prøvemedlemskap i Nord-Amerika. Scrabble® Players Association, som ga meg tilgang til den proprietære og copyright-beskyttede OWL3, som er kilden til noe kontrovers. Allerede da måtte jeg legge til noen kjente ord på engelsk, for eksempel ordene med en bokstav «a» og «I».

Bevæpnet med en ordentlig liste over ord implementerte jeg en algoritme for å produsere alle sett med ord fra den listen som hver inneholder en av hver bokstav i det engelske alfabetet. Jeg vil beskrive algoritmen på dybden i «Algoritmen» -seksjonen nedenfor.

Trinn 2: Danner engelske setninger fra en pose med ord

Gitt et sett med ord for å finne ut om en gyldig engelsk setning er mulig med alle de oppgitte ordene er et ikke-trivielt problem, men det er lettere enn de fleste andre NLP-problemer.

Det er nyttige heuristikker for å lukke ut ikke-kvalifiserte setninger; Jeg var i stand til å danne gyldige engelske setninger fra de resterende ordene etter å ha fulgt disse heuristikkene. Setningene var ofte meningsløse, men fortsatt gyldige. Her er heuristikken jeg brukte:

1. Det må være minst ett verb.
2. Det kan bare være ett substantiv mer enn det er verb med mindre det er en sammenheng eller en preposisjon, som begge er veldig sjeldne.
3. Hvis det finnes adjektiver, må det også være substantiver.

Heuristikken fungerer delvis på grunn av muligheten for underforstått subjekter (verken perfekte eller et pangram, men «beveg deg stille og snakk forsiktig» er en setning med to verb og ingen substantiver, med det underforståtte emnet «deg»).

Siden ordrommet som kan muligens delta i perfekte pangrammer er liten, det er lett nok å manuelt merke hvert enkelt ord med dets kvalifiserte delespråk og se om ordsettet adlyder de tre enkle heuristikkene. Hvorvidt du liker kvaliteten på setningene som er produsert, er et spørsmål om smak.

Algoritmen

Denne delen er litt teknisk, men forhåpentligvis fortsatt lett å følge. Gå gjerne til «Resultater & Læringer» -delen.

Strategi på høyt nivå

Målet er å produsere alle mulige sett med ord fra den gitte listen over ord som spenner over det engelske alfabetet «perfekt».

1. Rengjør listen over ord for drastisk å redusere søkeområdet, f.eks. fjern ord som har gjentatte bokstaver, som «bokstaver».
2. Bruk bitmasker til å representere ord effektivt og tilordne dem til de originale settene med ord.
3. Søk gjennom alle mulige tilstander, hver representerer en mulig bokstavkombinasjon, gjentatte ganger gjennom listen over bitmasker. Ytelsen forbedres dramatisk med dynamisk programmering.
4. Tegn piler (rettet kanter) fra den perfekte pangram-tilstanden, den endelige tilstanden som har alle de engelske bokstavene til mellomstatene som komponerte det. Gjør det igjen med mellomstatene for å lage en datastruktur som kan rekonstruere settene med ord som er mulige perfekte pangram. Dette kalles backtracking.
5. Output de oppdagede settene med ord som muligens er perfekte pangrammer som trær.

Rengjøring av listen, aka Canonicalization

Første trinn er å rense den opprinnelige ordlisten for å redusere søkeområdet og øke utskriftskvaliteten.

1. Fjern hele det hvite området rundt ordet og konverter den bare til små bokstaver
2. Forsikre deg om at ordene bare inneholder bokstaver i det engelske alfabetet; Jeg brukte et enkelt filter for regulært uttrykk: /^+$/
3. Filtrer mot andre lister, f.eks. svartelister; hvis et ord er i svartelisten, hopp over det ordet
4. Fjern alle ord med gjentatte bokstaver

Dette forkortet søkeområdet betydelig, fra lister på 200 000 ~ 370 000 ord til en mye mindre 35.000 ~ 65.000 ord.

Bruk av bitmasker

Bitmasker er heltallrepresentasjoner av tilstander. Det er flere fordeler med bitmasker:

• Bitmasker representerer dette problemet godt. Bokstavsbestilling betyr ikke noe, så alle kombinasjoner av ord kan representeres som en 26-sifret lang serie på 0 og 1, hvor hvert siffer representerer om det finnes en bokstav i kombinasjonen eller ikke. For eksempel. hvis ordsettet inneholder bokstaven «e», vil det femte sifferet være en 1, ellers en 0.
• Bitmasker er effektive: Siden søkeområdet er konstant, tilbyr bitmasker en effektiv lagring og representasjon av alle mulige bokstavkombinasjoner. Videre er bitvis-operasjoner rask; for å teste om to-bitmasker kan kombineres for å produsere en større bitmaske, sjekk om bitvise OG av de to maskene er lik 0, som begge er ekstremt raske operasjoner.

Så snu hvert ord til en bitmaske, som kan vises som et heltall. For eksempel blir ordet «cab» kartlagt til bitmasken på 111, som er desimaltallet 7. Ordet «være» blir kartlagt til 10010, som er desimaltallet 18, og så videre. Den største mulige bitmasken er en med alle bokstavene i alfabetet, den mulige perfekte pangram-tilstanden, 11111111111111111111111111, som er desimaltallet 67.108.863, eller 2²⁶ -1. Dette passer godt innenfor et standard signert 32-biters heltall, som kan representere opp til 2³¹-1.

Bruk av bitmasker komprimerer ytterligere plass, da anagrammer med enkelt ord tilordnes til samme bitmaske. Både «ovn» og «lenke» tilordnes masken 10110100000000, som er desimaltallet 11520. Dette reduserer søkeområdet på 35.000 ~ 65.000 ord ytterligere til 25.000 ~ 45.000 bitmasker.

Behold en kartlegging av bitmasken tilbake til ordsettet de er avledet fra. Dette vil være nyttig når du skriver ut ordsettene.

Søker etter det perfekte pangramet med dynamisk programmering

Kjernen i algoritmen er ganske enkel:

Gitt en mulig tilstand (som består av gyldige kombinasjoner av eksisterende ord), prøv alle maskene fra den første ordlisten for å se om det er mulig å opprette en ny gyldig tilstand (ved å sjekke om bitvis OG av tilstanden og masken er lik 0, noe som vil bety at det ikke er noen overlappende bokstaver). Opprett den nye tilstanden ved å bruke bitvis ELLER-operasjonen som fletter alle 1-ene sammen. For hver ny oppdaget stat, fortsett å gjenta til det ikke er flere uutforskede stater. Hvis dette når slutten, betyr det at algoritmen har funnet minst ett mulig perfekt pangram-ordsett. Den første mulige tilstanden som kan telle opp alle mulige tilstander er tom tilstand eller 0, hvor ingen bokstaver i alfabetet er inkludert. Så start der og oppdag deretter rekursivt hvilke stater som er mulige.

En stor effektivitetsgevinst er å legge merke til at det er mange måter å nå en intermitterende tilstand på, og at arbeidet med staten ikke endres basert på hvordan det ble nådd. Så i stedet for å gjenta arbeidet når en stat blir revidert, lagre resultatet av hver stat. Denne teknikken kalles dynamisk programmering og gjør et komplekst kombinatorisk problem til et lineært program. Prosessen med å lagre den intermitterende tilstanden kalles memoization.

Så lag en matrise med størrelse 2²⁶, mellom 0 og 67108 863, inkludert. Hver indeks representerer en bit maske tilstand som forklart før. Verdien ved hver indeks i matrisen representerer det som er kjent om staten. 0 betyr enten at staten er uberørt eller utilgjengelig. 1 betyr at staten har funnet en måte å nå den mulige perfekte pangram-tilstanden. -1 betyr at staten ikke har funnet en måte å nå slutten på.

Pseudokode nedenfor:

Interlude: Complexity and Practical Runtime Analysis

Det er 2²⁶ mulige bitmasker for en serie på 26 bits. Siden hver tilstand bare behandles en gang på grunn av memoisering, er kjøretiden til denne algoritmen O (n 2 ^ d), hvor d er størrelsen på alfabetet, 26. Variabelen n står ikke for antall ord, men antall bitmasker. Med 67.108.863 og omtrent 45.000 bit masker kommer dette til i størrelsesorden 3 billioner, som min MacBook Pro kunne takle på omtrent 45 minutter; kan trekkes for enhver moderne datamaskin. Det er også verdt å merke seg at den rekursive samtalestakken aldri blir dypere enn 26 (sannsynligvis aldri blir dypere enn 15), så den er også veldig håndterbar fra den dimensjonen også.

En fordel med bitmaske-tilnærmingen med bare 2²⁶ stater er at alle tilstandene kan lagres i minnet. Siden det bare er 3 verdier per tilstand (-1, 0, 1), kan dette lagres i en enkelt byte. Ved ett enkelt byte per tilstand kommer 2²⁶ stater ut til rundt 67 megabyte, noe som igjen er veldig håndterlig.

Når alfabetet øker, øker imidlertid søkeområdet eksponentielt, og det gjør også kjøretiden, og forårsaker problemet blir veldig vanskelig. En kort diskusjon om tilnærming til det perfekte pangramet for større alfabeter er i avsnittet «Språk m / større alfabet» nedenfor.

Dynamisk bygging av en rettet syklisk graf (DAG)

Nå som vi har fylt ut bitmaske-tilstandene, tid til å hente løsningen!

For å finne settene med ord som skapte settet med mulige perfekte pangram, må vi utlede hvilke mellomtilstander som var integrerte i å komponere de endelige tilstandene Så er oppfølgingsspørsmålet hvilke andre mellomstater som har sammensatt disse mellomstatene, og så videre til det eneste som gjenstår er tilstandene som kartlegges direkte til ord. Denne prosessen kalles backtracking. oversikt over forholdet mellom stater, er målet å skape en Di rected Acyclical Graph (DAG), som opprettholder hvilke mellomstater som komponerer en gitt tilstand. DAGs er enkle å krysse for å hente utganger, spesielt på grunn av deres ikke-sykliske natur. For å konstruere, start fra den mulige perfekte pangram-tilstanden, og opprett en rettet kant (pil) som peker på mellomstatene som komponerer den. Gjenta prosessen med mellomstatene, og den vil produsere en DAG. Det vil aldri være noen sykluser fordi pilene alltid peker på en tilstand med en mindre verdi.

I stedet for å gjenoppbygge relasjonene som ble oppdaget i søketrinnet, som innebærer å krysse igjen gjennom billioner av mulige tilstandskombinasjoner, er det mer effektivt å bygge DAG i løpet av den dynamiske programmeringsfasen. Inne i løsningsmetoden, hvis en nylig konstruert tilstand kan nå den mulige perfekte pangram-tilstanden, lagrer du en rettet kant fra den nylig konstruerte tilstanden til den opprinnelige tilstanden bare hvis den opprinnelige tilstanden er mindre enn komplementet (for å redusere kant duplisering). p>

Skriv ut fruktene av arbeidet ditt i treform!

Det enkleste formatet for å se på de resulterende settene med ord er sannsynligvis ved å oppføre dem som trær med rotnoden som den perfekte pangram-tilstanden. Gitt DAG konstruert ovenfra, er den beste måten å pakke den ut å gjøre det rekursivt, skrive hver tilstand til disk på hvert trinn i stedet for i minnet, siden treet er en størrelsesorden større enn DAG.

En forbedring av denne utvidelsesformen er å oppsummere tilstander som bare har en enkelt mulig kombinasjon av ord. En tilstand som er en maske for ord og ingen substater som komponerer den, kan oppsummeres trivielt. En tilstand kan oppsummeres hvis dens underformater og dens kompositter kan oppsummeres, og alle masker avledet fra seg selv og barna har ikke overlappende biter / tegn. Utskrift av den oppsummerte DAG forbedrer lesbarheten til det resulterende utgangstreet ved å forkorte og forenkle det.

Siden oppsummeringen bare avhenger av den minste av de to tilstandene, går den gjennom matrisen fra den opprinnelige tilstanden 0 og oppover og ved å bruke reglene ovenfor for å administrere oppsummeringsregelen, kan dette fullføres på lineær tid.

Produserte Pangram-trær!

Kryss gjerne gjennom de perfekte pangramtrærne for å se om du kan finne interessante setninger!

Det er mange mulige perfekte pangrammer

Jeg ble overrasket over antall perfekte mulige pangrammer. Det er mange! Den beste strategien for å sette dem sammen krever ikke en kompleks naturlig språkprosessor. Når kandidatordene er merket som kvalifiserende substantiv eller verb, må posen med ord inneholde minst ett substantiv, ett verb og riktig forhold mellom substantiver og verb.

Datakvalitet er et vanskelig problem

Algoritmeseksjonen tok to dager, men datakvalitetsproblemet tok to uker. Da jeg nevnte dette funnet til min venn som er senioringeniør Google, ble han ikke overrasket, og kommenterte at datakvalitetsproblemer er noen av de vanskeligste problemene innen engineering. Leksjon lært.

Reglene for perfekte pangrammer

Det er mange nyanser om hva som kvalifiserer som et perfekt pangram! Jeg ønsket å søke gjennom pangrammer uten noen interjeksjoner (f.eks. Hm, pht), men det er også andre populære begrensninger som forkortelser, akronymer, sammentrekninger, initialismer, isolerte bokstaver, substantiv og romertall. Det er også ord som er navn på bokstaver, som Qoph, som jeg følte som juks.

Med noen av disse begrensningene avslappede, er det mange «perfekte» pangrammer. I størrelsesorden trillioner, sannsynligvis . Det er mange akronymer og initialismer.

Stjernen

Stjernen er på plass fordi definisjonen av alle de perfekte pangramene på engelsk ikke er veldefinert. Det er nyanser relatert til hva som skal være tillatt i perfekte pangrams på engelsk. Det er også mange innvendinger om hvorvidt noen ord er engelske ord eller ikke. Gitt disse nyansene, er det veldig vanskelig å si at jeg har funnet alle de perfekte pangramene. Jeg kan komme med to påstander ganske trygt:

1. Jeg har funnet en metode for å produsere alle de perfekte pangramene på engelsk og andre språk med lignende eller mindre tegnsett.
2. I har oppregnet alle ordene som muligens kan danne perfekte pangrammer ved hjelp av den offisielle Scrabble-turneringsordboken y, OWL3.

Du er velkommen til å produsere dine egne perfekte pangrammer med teknikkene som er beskrevet i dette innlegget!

Perfekt Pangrams avhengighet av ord fra walisiske og arabiske røtter

Welsh- og arabisk-avledede ord var veldig viktige for eksistensen av perfekte engelske pangrammer (med mindre begrensningene for det perfekte pangram er avslappet). Ved å bruke OWL3-ordlisten med strenge regler om perfekte pangrammer, er det ingen perfekte pangrammer som ikke inkluderer ordene «cwm (s)» eller «crwth (s)», begge walisiske ord. I internasjonal Scrabble er det arabisk avledede ordet «waqf (s)» et gyldig ord som kan produsere perfekte pangram uten å ty til «cwm (s)» eller «crwth (s)».

Work Stream Efficiencies

Det var viktig å bli mer effektiv til å parallellisere oppgaver under dette prosjektet. En full løp tar 25 minutter for Unix-ordboken og nærmere en time for de virkelig store ordbøkene. Jeg hadde noen problemer med å bytte kontekst i et 30-minuttersvindu, men ble bedre på det da jeg gikk for å forbedre produktiviteten min.

Extension / Generalization – Anagram Finder

Det perfekte pangramet søk tilsvarer også en anagramfinner for strengen «abcdefghijklmnopqrstuvwxyz». Hva om du vil bygge en generisk anagramfinner?

Den samme teknikken kan brukes så lenge statens representasjon og styringsregler for kontroll ordkombinasjonens gyldighet oppdateres. I stedet for at tilstander administreres som et heltall, ville det være lettere å spore tilstanden som et kart over de aktuelle tegnene. Å se om kombinasjoner er gyldige, er å si at kombinasjonen av to kart ikke overstiger anagrammets ønskede tegnantall for hver bokstav. Bare vær sikker på at tilstandsrommet kan spores; med for mange bokstaver kan søkeområdet bli veldig stort i en blikk. Har du også lov til å gjenta ord? Sørg for at du definerer disse reglene inne din dynamiske programmering løsning.

Språk med større alfabet

Denne tilnærmingen og løsningen er lineær i ordsettet, men eksponentiell i alfabetstørrelse. Denne tilnærmingen fungerer kanskje ikke med et større tegnsett, si moderne japansk som har 46 pensum. 2⁴⁶ er 70,368,744,177,664; over en million ganger større enn det engelske søkeområdet på 2²⁶ = 67.108.864.

Det er ikke helt klart om denne tilnærmingen vil fungere for japansk. Hvis japansk språk har tilstrekkelig lav entropi, noe som er mulig, vil denne tilnærmingen være levedyktig. I stedet for å initialisere en matrise med størrelse 2⁴⁶, vil tilstandene bli sporet på et kart. Videre kan strukturen til japansk utnyttes; for eksempel kana を (wo) brukes nesten utelukkende som postposisjonspartisipp, og kan ekskluderes fra søket, noe som reduserer søkeområdet.

Det kambodsjanske språket Khmer har det største alfabetet med 74. Et annet mulig neste trinn er å utforske løsninger som er subeksponentiell i alfabetstørrelse.

Inspirasjon

Jeg ble inspirert av Aubrey De Greys fremgang for å finne det kromatiske nummeret på flyet som skal være minst 5. Dette er en betydelig fremgang som ble oppnådd gjennom grunnleggende beregningsmetoder.

Det er unødvendig å si at det å finne perfekte pangrammer ikke holder et lys for å forbedre den nedre grensen for det kromatiske tallet i et plan. / p>

Dette får meg til å tro at det er mange fruktproblemer med lav hengende frukt som har enkle beregningsmetoder for å løse et problem som er uoppnåelig manuelt. Jeg utfordrer deg til å finne og løse noen av disse problemene. Gi meg beskjed hvis du finner noe!

Takk

Jeg er ganske takknemlig for mine meget gode venner som hjalp til med korrekturlesing og jamming på dette med meg, spesielt Anna Zeng, Catherine Gao, Danny Wasserman, George Washington og Nick Wu!