Alle * perfekte pangrams på engelsk

En Engelsk pangram er en sætning, der indeholder alle 26 bogstaver i det engelske alfabet. Den mest kendte engelske pangram er sandsynligvis “Den hurtige brune ræv springer over den dovne hund”. Min yndlingspangram er “Utroligt få diskoteker giver jukebokse.”

Et perfekt pangram er et pangram, hvor hvert af bogstaverne vises kun én gang. Jeg har fundet nogle kilder online, der viser de kendte perfekte pangrammer. Ingen ser ud til at have bestræbt sig på at producere dem alle udtømmende, så jeg tog det på som en sjov udfordring. Sådan fandt jeg alle * de perfekte pangrams på engelsk. Jeg forklarer stjernen senere.

• Crwth vox zaps qi gym fjeld bunk. (Lyden af en keltisk violin rammer et østligt åndeligt kræftfokuseret fitnesscenter beliggende på et ufrugtbart plateau i Skandinavien.) Dette er alle Scrabble-juridiske ord!
• Squdgy kilp job zarf nth cwm vex. (Den dårligt dannede tare køber en ornamental kopvarmer, som en af de mange halvåbne stejle huler i spidsen for en dal eller bjergsiden har irriteret.)
• Jock nymfer waqf drug vex blitz. (Den velgørende gave berusede skovåndene, der frustrerede atleten, der deltager i et angreb.)
• Hm, fjord vals, cinq busk, pyx veg. (Lad os se, en lang, smal dyb indløbsdans, de fem på terningerne laver musik på gaden og den lille runde beholder til syge og ude af stand til at hvile.) Også Scrabble lovligt, men har en indskæring (Hm).

Dette er desværre nogle af de mest læselige sætninger, jeg kunne finde *. Alle perfekte pangrammer genereret fra den officielle turnering og klubordliste 3 (OWL3) til Scrabble uden indskud inkluderer enten ordet cwm eller crwth. Waqf er Scrabble-turnering lovlig uden for Nordamerika.

Sådan finder du alle de perfekte pangrammer

Metoden til at finde perfekte pangrammer kommer i to trin. Den første er at finde alle sæt ord, der indeholder hvert bogstav i det engelske alfabet en gang. Det andet trin er at se, hvilke af disse sæt der kan omarrangeres til gyldige engelske sætninger.

Trin 1: Find sæt af ord til det perfekte pangram

For at begynde at finde sæt af ord, der spænder det engelske alfabet kræver en liste med engelske ord. At finde og vedligeholde en ordliste af høj kvalitet var meget sværere end jeg havde forventet. Oprindeligt troede jeg, at dette projekt ville tage to dage, men det endte med at tage to uger som et resultat af dette datakvalitetsproblem.

Jeg startede med Unix-ordbogen, som er en frit tilgængelig liste over engelske ord. der kommer med næsten alle Unix-baserede operativsystemer. Jeg bemærkede straks, at listen havde kvalitetsproblemer. For det første blev hvert bogstav i alfabetet betragtet som et ord i Unix-ordbogen, og det indeholdt en masse ikke-ord, som “vejoz”. Dette demonstrerede behovet for en sortliste til at styre de lister med ord, der blev fundet online. For det andet, Unix-ordbogen manglede flertal for ord, så ordbogen ville indeholde ordet “orange” men ikke “appelsiner”. Ordlisten er faktisk så restriktiv, at ingen tidligere kendte perfekte pangrams kun indeholder ord fra Unix-ordbogen. Jeg fandt stadig nogle, såsom “squdgy kilp job zarf nth cwm vex”.

Derefter vendte jeg mig til internettet for at finde større sæt ord. Jeg fandt meget store ordsæt, der var enorme, men da jeg begyndte at grave efter perfekte pangrams fra disse lister, fandt jeg ud af, at de var alt for forurenede med ord af lav kvalitet, der ikke er gyldige engelske ord. Selv efter mange runder af iteration kunne jeg stadig ikke parere listen for at finde nogen rimelige eller håndterbare pangrammer. Jeg forsøgte at rydde op ved at oprette en hvidliste med ord af bestemte længder, men listen var stadig ekstremt lav kvalitet.

Endelig betalte jeg efter mange iterationer $ 15 for at købe et prøvemedlemskab af det nordamerikanske Scrabble® Players Association, som gav mig adgang til den proprietære og copyright-beskyttede OWL3, som er kilden til en vis kontrovers. Allerede da var jeg nødt til at tilføje nogle kendte ord på engelsk, såsom ordene med et bogstav “a” og “I”.

Bevæbnet med en ordentlig liste over ord implementerede jeg en algoritme til at producere alle sæt ord fra denne liste, der hver indeholder et af hvert bogstav i det engelske alfabet. Jeg vil beskrive algoritmen dybtgående i afsnittet “Algoritmen” nedenfor.

Trin 2: Dannelse af engelske sætninger ud fra en pose ord

Givet et sæt ord, hvor jeg finder ud af, om en gyldig engelsk sætning er mulig med alle de angivne ord er et ikke-trivielt problem, men det er lettere end de fleste andre NLP-problemer (Natural Language Processing).

Der er nyttige heuristikker til at udrydde ikke-kvalificerede sætninger; Jeg var i stand til at danne gyldige engelske sætninger ud fra de resterende ord efter at have fulgt disse heuristikker. Dommene var ofte meningsløse, men stadig gyldige. Her er de heuristikker, jeg brugte:

1. Der skal være mindst et verbum.
2. Der kan kun være et substantiv mere end der er verbum, medmindre der er en sammenhæng eller en præposition, som begge er meget sjældne.
3. Hvis der er adjektiver, skal der også være navneord.

Den heuristiske fungerer delvis på grund af muligheden for underforstået emner (hverken perfekte eller et pangram, men “bevæg dig stille og tal blødt” er en sætning med to verb og uden substantiver med det underforståede emne for “dig”).

Da det rum af ord, der kan muligvis deltage i perfekte pangrammer er lille, det er let nok til manuelt at mærke hvert enkelt ord med dets kvalificerede dele af talen og se om ordsættet adlyder de tre enkle heuristikker. Hvorvidt du kan lide kvaliteten af de producerede sætninger er et spørgsmål om smag.

Algoritmen

Dette afsnit er lidt teknisk, men forhåbentlig stadig let at følge. Gå gerne til afsnittet “Resultater & Læring.

Strategi på højt niveau

Målet er at producere alle mulige sæt ord fra den givne liste over ord, der spænder over det engelske alfabet “perfekt”.

1. Rens listen over ord for drastisk at reducere søgerummet, f.eks. fjern ord, der har gentagne bogstaver, som “bogstaver”.
2. Brug bitmasker til at repræsentere ord effektivt og kortlæg dem tilbage til de originale sæt ord.
3. Søg gennem alle mulige tilstande, hver repræsenterer en mulig bogstavkombination ved gentagne gange at gentage gennem listen over bitmasker. Ydelse forbedres dramatisk med dynamisk programmering.
4. Tegn pile (rettet kanter) fra den perfekte pangram-tilstand, den endelige tilstand, der har alle de engelske bogstaver til mellemmændene, der sammensatte det. Gør det igen med mellemtilstandene for at skabe en datastruktur, der kan rekonstruere de sæt ord, der er mulige perfekte pangrammer. Dette kaldes backtracking.
5. Output de opdagede sæt ord, der muligvis er perfekte pangrammer som træer.

Rengøring af listen, også kaldet Canonicalization

Første skridt er at rense den oprindelige ordliste for at reducere søgerummet og øge outputkvaliteten.

1. Fjern hele det hvide område omkring ordet og konverter det kun til små bogstaver
2. Sørg for, at ordene kun indeholder bogstaver i det engelske alfabet; Jeg brugte et simpelt filter til regulært udtryk: /^+$/
3. Filtrer mod andre lister, f.eks. sortlister; hvis et ord er på den sorte liste, skal du springe det over
4. Fjern alle ord med gentagne bogstaver

Dette forkortede søgerummet markant fra lister på 200.000 ~ 370.000 ord til en meget mindre 35.000 ~ 65.000 ord.

Brug af bitmasker

Bitmasker er heltalsrepræsentationer af tilstande. Der er flere fordele ved bitmasker:

• Bitmasker repræsenterer dette problem godt. Bogstavsbestilling betyder ikke noget, så alle kombinationer af ord kan repræsenteres som en 26-cifret lang række på 0 og 1, hvor hvert ciffer repræsenterer, om der findes et bogstav i kombinationen eller ej. For eksempel. hvis ordsættet indeholder bogstavet “e”, vil det 5. ciffer være et 1, ellers en 0.
• Bitmasker er effektive: Da søgerummet er konstant, tilbyder bitmasker en effektiv opbevaring og repræsentation af alle mulige kombinationer af bogstaver. Endvidere er bitvis-operationer hurtige; for at teste, om to bitmasker kan kombineres til at producere en større bitmaske, skal du kontrollere, om bitvise OG af de to masker er lig med 0, som begge er ekstremt hurtige operationer.

Så drej hvert ord til en bitmaske, som kan repræsenteres som et heltal. F.eks. kortlægges ordet “cab” til bitmasken på 111, som er decimaltallet 7. Ordet “være” kortlægges til 10010, hvilket er decimaltallet 18 osv. Den største mulige bitmaske er en med alle bogstaverne i alfabetet, den mulige perfekte pangram-tilstand, 11111111111111111111111111, hvilket er decimaltallet 67.108.863 eller 2²⁶ -1. Dette passer godt inden for et standardunderskrevet 32-bit heltal, som kan repræsentere op til 2³¹-1.

Brug af bitmasker komprimerer yderligere plads, da anagrammer med enkelt ord kortlægges til den samme bitmaske. Både “ovn” og “link” kortlægges til masken 10110100000000, hvilket er decimaltallet 11520. Dette reducerer yderligere søgerummet på 35.000 ~ 65.000 ord til 25.000 ~ 45.000 bitmasker.

Behold en kortlægning af bitmasken tilbage til det sæt ord, de stammer fra. Dette vil være nyttigt, når du sætter ordsættene ud.

Søgning efter det perfekte pangram med dynamisk programmering

Kernen i algoritmen er ret enkel:

Givet en mulig tilstand (der består af gyldige kombinationer af eksisterende ord), prøv alle maskerne fra den oprindelige ordliste for at se, om det er muligt at oprette en ny gyldig tilstand (ved at kontrollere, om bitvis OG af tilstanden og masken er lig med 0, hvilket vil betyde, at der ikke er nogen overlappende bogstaver). Opret den nye tilstand ved hjælp af bitvis ELLER-operation, der fletter alle 1erne sammen. For hver ny opdaget tilstand skal du gentage, indtil der ikke er flere uudforskede stater. Hvis dette når slutningen, betyder det, at algoritmen har fundet mindst et muligt perfekt pangram-ordsæt. Den første mulige tilstand, der kan tælle alle mulige tilstande, er den tomme tilstand eller 0, hvor ingen bogstaver i alfabetet er inkluderet. Så start der og find derefter rekursivt ud, hvilke tilstande der er mulige.

En enorm effektivitetsgevinst er at bemærke, at der er mange måder at nå en intermitterende tilstand på, og at arbejdet med staten ikke ændres baseret på hvordan det blev nået. Så i stedet for at gentage arbejdet, når en stat genbesøges, skal du gemme resultatet af hver stat. Denne teknik kaldes dynamisk programmering og forvandler et komplekst kombinatorisk problem til et lineært program. Processen med lagring af den intermitterende tilstand kaldes memoization.

Så lav et array med størrelse 2²⁶, mellem 0 og 67.108.863 inklusive. Hvert indeks repræsenterer en bitmaske-tilstand som forklaret før. Værdien ved hvert indeks i matrixen repræsenterer det, der er kendt om tilstanden. 0 betyder enten, at staten er uberørt eller ikke kan nås. 1 betyder, at staten har fundet en måde at nå den mulige perfekte pangram-tilstand. -1 betyder, at staten ikke har fundet en måde at nå slutningen på.

Pseudokode nedenfor:

Interlude: Complexity and Practical Runtime Analysis

Der er 2²⁶ mulige bitmasker til en serie på 26 bits. Da hver tilstand kun behandles en gang på grund af memoization, er denne algoritmes kørselstid O (n 2 ^ d), hvor d er størrelsen på alfabetet, 26. Variablen n står ikke for antallet af ord, men antal bitmasker. Med 67.108.863 og cirka 45.000 bit masker kommer dette til i størrelsesordenen 3 billioner, som min MacBook Pro kunne håndtere på cirka 45 minutter; kan trækkes til enhver moderne computer. Det er også værd at bemærke, at den rekursive opkaldsstak aldrig bliver dybere end 26 (sandsynligvis aldrig bliver dybere end 15), så den er også meget håndterbar fra den dimension også.

En fordel ved bitmaske-tilgangen med kun 2²⁶ stater er, at alle stater kan lagres i hukommelsen. Da der kun er 3 værdier pr. Tilstand (-1, 0, 1), kan dette lagres i en enkelt byte. Ved en enkelt byte pr. Tilstand kommer 2²⁶ stater ud til omkring 67 megabyte, hvilket igen er meget håndterbart.

Når alfabetet øges, øges søgerummet imidlertid eksponentielt, og det samme gør løbetiden, hvilket forårsager problem at blive uhåndterlig meget hurtigt. En kort diskussion om, hvordan man nærmer sig det perfekte pangram til større alfabeter, findes i afsnittet “Sprog med større alfabeter” nedenfor.

Dynamisk opbygning af en styret cyklisk graf (DAG)

Nu hvor vi har udfyldt bitmaske-tilstande, tid til at hente løsningen!

For at finde sæt af ord, der skabte sæt af mulige perfekte pangrammer, er vi nødt til at udlede hvilke mellemliggende stater, der var integrerede i komponering af de endelige tilstande Opfølgningsspørgsmålet er derefter, hvilke andre mellemliggende stater der sammensatte disse mellemliggende stater, og så videre, indtil det eneste, der er tilbage, er de stater, der kortlægges direkte til ord. Denne proces kaldes backtracking.

For at beholde sporing af forholdet mellem stater, er målet at skabe en Di rected Acyclical Graph (DAG), som opretholder, hvilke mellemliggende stater der sammensætter en given tilstand. DAGer er lette at krydse for at hente output, især på grund af deres ikke-cykliske natur. For at konstruere skal du starte fra den mulige perfekte pangram-tilstand og oprette en rettet kant (pil), der peger på de mellemliggende tilstande, der komponerer den. Gentag processen med de mellemliggende tilstande, og den producerer en DAG. Der vil aldrig være nogen cyklusser, fordi pilene altid peger på en tilstand med en mindre værdi.

I stedet for at genopbygge de forhold, der blev opdaget i søgetrinet, hvilket indebærer at krydse igen gennem billioner af mulige tilstandskombinationer, er det mere effektivt at opbygge DAG i den dynamiske programmeringsfase. Inde i løsningsmetoden, hvis en nyligt konstrueret tilstand kan nå den mulige perfekte pangram-tilstand, skal du kun gemme en rettet kant fra den nyligt konstruerede tilstand til den oprindelige tilstand, hvis den oprindelige tilstand er mindre end dens komplement (for at reducere kantdublering). p>

Udskriv frugterne af dit arbejde i træform!

Det nemmeste format for visning af de resulterende sæt ord er sandsynligvis ved at angive dem som træer med rodnoden som den perfekte pangram-tilstand. I betragtning af DAG konstrueret ovenfra er den bedste måde at pakke den ud på at gøre det rekursivt ved at skrive hver tilstand til disk på hvert trin i stedet for i hukommelsen, da træet er en størrelsesorden større end DAG.

En forbedring af denne form for udvidelse er at opsummere tilstande, der kun har en enkelt mulig kombination af ord. En tilstand, der er en maske for ord og ingen underformater, der komponerer den, kan opsummeres trivielt. En tilstand kan opsummeres, hvis dens underformater og dens kompositter kan sammenfattes, og alle masker, der stammer fra sig selv og dets børn, ikke har overlappende bits / tegn. Udskrivning af den opsummerede DAG forbedrer læsbarheden af det resulterende outputtræ ved at forkorte og forenkle det.

Da opsummeringen kun afhænger af den mindste af de to tilstande, gentager den sig gennem arrayet fra den oprindelige tilstand 0 op og ved hjælp af ovenstående regler til at styre opsummeringsreglen kan dette udfyldes lineært.

Producerede Pangram-træer!

Du er velkommen til at krydse gennem de perfekte pangramtræer for at se om du kan finde interessante sætninger!

Der er mange mulige perfekte pangrammer

Jeg blev overrasket over antallet af perfekte mulige pangrammer. Der er meget! Den bedste strategi for at sætte dem sammen kræver ikke en kompleks naturlig sprogprocessor. Når kandidatordene er blevet mærket som kvalificerede substantiv eller verb, skal posen med ord indeholde mindst et substantiv, et verb, og det rigtige forhold mellem substantiver og verb.

Datakvalitet er et hårdt problem

Algoritmesektionen tog to dage, men datakvalitetsproblemet tog to uger. Da jeg nævnte dette fund til min ven, der er senioringeniør Google, blev han ikke overrasket og kommenterede, at datakvalitetsproblemer er nogle af de sværeste problemer inden for teknik. Lærdommen.

Reglerne for perfekte pangrammer

Der er mange nuancer med hensyn til, hvad der kvalificerer som et perfekt pangram! Jeg ønskede at søge gennem pangrammer uden nogen interjektioner (fx hm, pht), men der er også andre populære begrænsninger såsom forkortelser, akronymer, sammentrækninger, initialismer, isolerede bogstaver, egennavne og romertal. Der er også ord, der er navne på bogstaver, som Qoph, som jeg følte snyder.

Med nogle af disse begrænsninger afslappet, er der mange “perfekte” pangrammer. I trillions rækkefølgen, sandsynligvis Der er mange akronymer og initialismer.

Stjernen

Stjernen er på plads, fordi definitionen af alle de perfekte pangrammer på engelsk ikke er veldefineret. Der er nuancer relateret til hvad der skal tillades i perfekte pangrams på engelsk. Der er også mange indvendinger om, hvorvidt nogle ord endda er engelske ord. I betragtning af disse nuancer er det virkelig svært at sige, at jeg har fundet alle de perfekte pangrammer. Jeg kan gøre to påstande temmelig fortroligt:

1. Jeg har fundet en metode til at fremstille alle de perfekte pangrams på engelsk og andre sprog med lignende eller mindre tegnsæt.
2. I har opregnet alle sæt ord, der muligvis kan danne perfekte pangrammer ved hjælp af den officielle Scrabble-turneringsordbog y, OWL3.

Du er velkommen til at fremstille dine egne perfekte pangrammer med de teknikker, der er beskrevet i dette indlæg!

Perfekt Pangrams afhængighed af ord fra walisiske og arabiske rødder

Welsh- og arabisk-afledte ord var virkelig vigtige for eksistensen af perfekte engelske pangrams (medmindre begrænsningerne for det perfekte pangram er afslappet). Brug af OWL3-ordlisten med strenge regler for perfekte pangrammer, der er ingen perfekte pangrammer, der ikke inkluderer ordene “cwm (s)” eller “crwth (s)”, begge walisiske ord. I international Scrabble er det arabisk afledte ord “waqf (s)” et gyldigt ord, der kan producere perfekte pangrammer uden at ty til “cwm (s)” eller “crwth (s)”.

Effektivitet i arbejdsstrømmen

Det var vigtigt at blive mere effektiv til at parallelisere opgaver under dette projekt. En fuld løb tager 25 minutter for Unix-ordbogen og tæt på en time for de virkelig store ordbøger. Jeg havde nogle indledende problemer med at skifte kontekst i et 30 minutters vindue, men blev bedre til det, da jeg gik sammen for at forbedre min produktivitet.

Udvidelse / generalisering – Anagram Finder

Det perfekte pangram søgning svarer også til en anagramfinder efter strengen “abcdefghijklmnopqrstuvwxyz”. Hvad hvis du ville bygge en generisk anagramfinder?

Den samme teknik kan bruges, så længe statens repræsentation og styringsregler for kontrol ordkombinationens gyldighed opdateres. I stedet for at få stater administreret som et heltal, ville det være lettere at spore tilstanden som et kort over de relevante tegn. At se, om kombinationer er gyldige, er at sige, at kombinationen af to kort ikke overstiger anagrams ønskede tegnantal for hvert bogstav. Bare sørg for, at tilstandsrummet er let at følge; med for mange bogstaver kan søgerummet blive meget stort i et øjeblik. Har du også lov til at gentage ord? Sørg for at definere disse regler inde din dynamiske programmering løsning.

Sprog med større bogstaver

Denne tilgang og løsning er lineær i ordsætstørrelsen, men eksponentiel i alfabetstørrelse. Denne tilgang fungerer muligvis ikke med et større tegnsæt, siger moderne japansk, der har 46 pensum. 2⁴⁶ er 70.368.744.177.664; over en million gange større end det engelske søgerum på 2²⁶ = 67.108.864.

Det er ikke helt klart, om denne tilgang vil fungere for japansk eller ej. Hvis det japanske sprog har tilstrækkelig lav entropi, hvilket er muligt, ville denne tilgang være levedygtig. I stedet for at initialisere en matrix af størrelse 2⁴⁶ holdes staterne på et kort. Desuden kan japansk struktur udnyttes; for eksempel kana を (wo) næsten udelukkende bruges som postpositionsposition, og kan udelukkes fra søgningen, hvilket reducerer søgerummet.

Det kambodjanske sprog i Khmer har det største alfabet med 74. Et andet muligt næste trin er at udforske løsninger, der er undereksponentielle i alfabetstørrelse.

Inspiration

Jeg blev inspireret af Aubrey De Greys fremskridt med at finde det kromatiske nummer på flyet, der skal være mindst 5. Dette er en betydelig fremgang, der blev opnået gennem grundlæggende beregningsmetoder.

Det er overflødigt at sige, at finde perfekte pangrammer ikke holder et lys for at forbedre den nedre grænse for det kromatiske tal i et plan.

Dette får mig til at tro, at der er mange problemer med lavt hængende frugt, der har enkle beregningsmetoder til at løse et problem, der er manuelt umuligt. Jeg udfordrer dig til at finde og løse nogle af disse problemer. Lad mig vide, hvis du finder noget!

Tak

Jeg er ret taknemmelig for mine meget fremragende venner, der hjalp med korrekturlæsning og jamming på dette med mig, især Anna Zeng, Catherine Gao, Danny Wasserman, George Washington og Nick Wu!