Alla * perfekta pangram på engelska

En Engelska pangram är en mening som innehåller alla 26 bokstäver i det engelska alfabetet. Det mest kända engelska pangramet är förmodligen ”Den snabba bruna räven hoppar över den lata hunden”. Min favoritpangram är ”Otroligt få diskotek ger jukeboxar.”

Ett perfekt pangram är ett pangram där var och en av bokstäverna visas bara en gång. Jag har hittat några källor online som visar de kända perfekta pangrammen. Ingen verkar ha strävat framgångsrikt att producera dem alla uttömmande, så jag tog det på mig som en rolig utmaning. Så här hittade jag alla * de perfekta pangrammen på engelska. Jag kommer att förklara asterisken senare.

• Crwth vox zaps qi gym fjeld bunk. (Ljudet av en keltisk fiol slår ett östligt andligt krafter-fokuserat fitnesscenter beläget på en karg platå i Skandinavien.) Det här är allt Scrabble-lagliga ord!
• Squdgy kilp job zarf nth cwm vex. (Den dåligt bildade kelpen köper en prydnadskoppare som en av många halvöppna branta sidor i huvudet av en dal eller bergssidan har irriterat.)
• Jock nymfer waqf drug vex blitz. (Den välgörenhetsfördelningen berusade skogsandarna, som frustrerade idrottaren, som engagerar sig i en attack.)
• Hm, fjordvals, cinq busk, pyx veg. (Låt oss se, en lång smal, djup inloppsdans, de fem på tärningarna gör musik på gatan och den lilla runda behållaren för sjuka och oförmögna vilar.) Också Scrabble lagligt, men har en interjektion (Hm).

Tyvärr är det här några av de mest läsbara meningarna jag kunde hitta *. Alla perfekta pangram som genereras från den officiella turneringen och klubbordlistan 3 (OWL3) för Scrabble utan interjektioner inkluderar antingen ordet cwm eller crwth. Waqf är Scrabble-turnering lagligt utanför Nordamerika.

Hur man hittar alla perfekta pangram

Metoden för att hitta perfekta pangram finns i två steg. Den första är att hitta alla uppsättningar ord som innehåller varje bokstav i det engelska alfabetet en gång. Det andra steget är att se vilka av dessa uppsättningar som kan ordnas om till giltiga engelska meningar.

Steg 1: Hitta uppsättningar ord för det perfekta pangramet

Att börja hitta uppsättningar ord som span det engelska alfabetet kräver en lista med engelska ord. Att hitta och underhålla en ordlista av hög kvalitet var mycket svårare än jag hade förväntat mig. Ursprungligen trodde jag att detta projekt skulle ta två dagar, men det tog två veckor till följd av detta datakvalitetsproblem.

Jag började med Unix-ordboken, som är en fritt tillgänglig lista med engelska ord. som kommer med nästan alla Unix-baserade operativsystem. Jag märkte genast att listan hade kvalitetsproblem. Först betraktades varje bokstav i alfabetet som ett ord i Unix-ordboken, och det innehöll många icke-ord, som ”vejoz”. Detta visade behovet av en svartlista för att hantera listorna med ord som hittades online. För det andra, Unix-ordlistan saknade flertalet ord, så ordboken skulle innehålla ordet ”orange” men inte ”apelsiner”. Ordlistan är faktiskt så begränsande att inga tidigare kända perfekta pangram endast innehåller ord från Unix-ordboken. Jag hittade fortfarande några, till exempel ”squdgy kilp job zarf nth cwm vex”.

Jag vände mig sedan till internet för att hitta större uppsättningar ord. Jag hittade mycket stora orduppsättningar som var enorma, men när jag började gräva efter perfekta pangram från dessa listor fann jag att de var alldeles förorenade med ord av låg kvalitet som inte är giltiga engelska ord. Även efter många omgångar av iteration misslyckades jag fortfarande med att para ner listan för att hitta några rimliga eller hanterbara pangram. Jag försökte städa upp den genom att skapa en vitlista med ord av vissa längder, men listan var fortfarande extremt låg kvalitet.

Slutligen, efter många iterationer, betalade jag $ 15 för att köpa ett provmedlemskap i Nordamerika. Scrabble® Players Association, som gav mig tillgång till den proprietära och upphovsrättsskyddade OWL3, vilket är källan till viss kontrovers. Redan då var jag tvungen att lägga till några kända ord på engelska, till exempel orden ”a” och ”I”.

Beväpnad med en ordentlig lista med ord implementerade jag en algoritm för att producera alla uppsättningar ord från listan som alla innehåller en av varje bokstav i det engelska alfabetet. Jag kommer att beskriva algoritmen på djupet i avsnittet ”Algoritmen” nedan.

Steg 2: Att bilda engelska meningar från en påse med ord

Givet en uppsättning ord och räknar ut om en giltig engelsk mening är möjlig med alla angivna ord är ett icke-trivialt problem, men det är lättare än de flesta andra NLP-problem (Natural Language Processing).

Det finns användbara heuristiker för att rensa bort icke kvalificerade meningar; Jag kunde skapa giltiga engelska meningar från de återstående orden efter att ha följt dessa heuristik. Meningarna var ofta meningslösa, men fortfarande giltiga. Här är de heuristik jag använde:

1. Det måste finnas minst ett verb.
2. Det kan bara finnas ett substantiv mer än det finns verb om det inte finns en sammankoppling eller en preposition, som båda är mycket sällsynta.
3. Om det finns adjektiv måste det också finnas substantiv.

Heuristiken fungerar delvis på grund av möjligheten att underförstått ämnen (varken perfekta eller ett pangram, men ”rör dig tyst och talar mjukt” är en mening med två verb och inga substantiv, med det underförstådda ämnet ”du”).

Eftersom det utrymme med ord som kan eventuellt delta i perfekta pangram är liten, det är tillräckligt enkelt att manuellt märka varje enskilt ord med dess stödberättigande ord och se om ordsatsen följer de tre enkla heuristiken. Oavsett om du gillar kvaliteten på de meningar som produceras är en fråga om smak.

Algoritmen

Det här avsnittet är lite tekniskt, men förhoppningsvis fortfarande lätt att följa. Hoppa gärna till avsnittet ”Resultat & Lärningar.

Strategi på hög nivå

Målet är att ta fram alla möjliga uppsättningar ord från den angivna listan med ord som spänner över det engelska alfabetet ”perfekt”.

1. Rengör ordlistan för att drastiskt minska sökutrymmet, t.ex. ta bort ord som har upprepade bokstäver, som ”bokstäver”.
2. Använd bitmasker för att representera ord effektivt och mappa dem tillbaka till de ursprungliga uppsättningarna av ord.
3. Sök igenom alla möjliga tillstånd, var och en representerar en möjlig bokstavskombination genom att upprepade gånger itera igenom listan över bitmasker. Prestanda förbättras dramatiskt med dynamisk programmering.
4. Rita pilar (riktade kanter) från det perfekta pangramtillståndet, det slutliga tillståndet som har alla de engelska bokstäverna, till mellantillstånden som komponerade det. Gör det igen med mellantillstånden för att skapa en datastruktur som kan rekonstruera de uppsättningar ord som är möjliga perfekta pangram. Detta kallas backtracking.
5. Output de upptäckta uppsättningar ord som möjligen är perfekta pangram som träd.

Rengöring av listan, aka Canonicalization

Första steget är att rengöra den ursprungliga listan med ord för att minska sökutrymmet och öka utskriftskvaliteten.

1. Ta bort alla vita utrymmen runt ordet och konvertera den till endast små bokstäver
2. Se till att orden endast innehåller bokstäver i det engelska alfabetet. Jag använde ett enkelt reguljärt uttrycksfilter: /^+$/
3. Filtrera mot andra listor, t.ex. svartlistor; om ett ord finns i den svarta listan, hoppa över det ordet
4. Ta bort alla ord med upprepade bokstäver

Detta förkortade sökutrymmet avsevärt, från listor med 200 000 ~ 370 000 ord till mycket mindre 35 000 ~ 65 000 ord.

Använda bitmasker

Bitmasker är heltalsrepresentationer av tillstånd. Det finns flera fördelar med bitmasker:

• Bitmasker representerar detta problem väl. Bokstavsbeställning spelar ingen roll, så alla kombinationer av ord kan representeras som en 26-siffrig lång serie med 0 och 1, varvid varje siffra representerar huruvida en bokstav finns i kombinationen eller inte. Till exempel. om uppsättningen ord innehåller bokstaven ”e” kommer den 5: e siffran att vara en 1, annars en 0.
• Bitmasker är effektiva: Eftersom sökutrymmet är konstant erbjuder bitmasker en effektiv lagring och representering av alla möjliga kombinationer av bokstäver. Dessutom är bitvisa operationer snabba; för att testa om två bitmasker kan kombineras för att producera en större bitmask, kontrollera om bitvis OCH av de två maskerna är lika med 0, som båda är extremt snabba operationer.

Så förvandla varje ord till en bitmask, som kan representeras som ett heltal. Exempelvis kartläggs ordet ”cab” till bitmask 111, som är decimaltal 7. Ordet ”vara” kartläggs till 10010, vilket är decimaltal 18 och så vidare. Den största möjliga bitmask är en med alla bokstäverna i alfabetet, det möjliga perfekta pangramtillståndet, 11111111111111111111111111, vilket är decimaltalet 67.108.863 eller 2²⁶ -1. Detta passar bra inom ett standardtecknat 32-bitars heltal, som kan representera upp till 2³¹-1.

Med hjälp av bitmasker komprimeras ytterligare utrymme, eftersom anagram med en ord ordnas till samma bitmask. Både ”ugn” och ”länk” kartläggs till masken 10110100000000, vilket är decimaltalet 11520. Detta minskar ytterligare sökutrymmet på 35 000 ~ 65 000 ord till 25 000 ~ 45 000 bitmasker.

Behåll en mappning av bitmasken tillbaka till den uppsättning ord de kommer från. Detta kommer att vara användbart när du matar ut uppsättningarna ord.

Söker efter det perfekta pangramet med dynamisk programmering

Kärnan i algoritmen är ganska enkel:

Med tanke på ett möjligt tillstånd (som består av giltiga kombinationer av befintliga ord), prova alla masker från den ursprungliga ordlistan för att se om det är möjligt att skapa ett nytt giltigt tillstånd (genom att kontrollera om bitvis OCH av tillståndet och masken är lika med 0, vilket skulle innebära att det inte finns några överlappande bokstäver). Skapa det nya tillståndet med bitvis ELLER-operation som slår samman alla 1-enheterna. För varje upptäckt nytt tillstånd, fortsätt upprepa tills det inte finns fler outforskade stater. Om detta når slutet betyder det att algoritmen har hittat minst en möjlig perfekt pangram-orduppsättning. Det första möjliga tillståndet som kan räkna upp alla möjliga tillstånd är det tomma tillståndet eller 0, där inga bokstäver i alfabetet ingår. Så börja där och upptäck sedan rekursivt vilka tillstånd som är möjliga.

En enorm effektivitetsvinst är att märka att det finns många sätt att nå ett intermittent tillstånd och att arbetet med staten inte förändras baserat på hur det Nåddes. Så istället för att upprepa arbetet när ett tillstånd återbesöks, lagra resultatet för varje tillstånd. Denna teknik kallas dynamisk programmering och förvandlar ett komplext kombinatoriskt problem till ett linjärt program. Processen för att lagra det intermittenta tillståndet kallas memoization.

Så skapa en matris med storlek 2²⁶, mellan 0 och 67108 863 inklusive. Varje index representerar ett bitmasktillstånd som förklarats tidigare. Värdet vid varje index i matrisen representerar det som är känt om tillståndet. 0 betyder antingen att staten är orörd eller oåtkomlig. 1 betyder att staten har hittat ett sätt att nå det möjliga perfekta pangramtillståndet. -1 betyder att staten misslyckades med att hitta ett sätt att nå slutet.

Pseudokod nedan:

Interlude: Complexity and Practical Runtime Analysis

Det finns 2²⁶ möjliga bitmasker för en serie på 26 bitar. Eftersom varje tillstånd endast behandlas en gång på grund av memoization är körningstiden för denna algoritm O (n 2 ^ d), där d är storleken på alfabetet, 26. Variabeln n står inte för antalet ord utan för antal bitmasker. Med 67108 863 och ungefär 45 000 bitmasker kommer detta till storleksordningen 3 biljoner, vilket min MacBook Pro kunde hantera på ungefär 45 minuter; kan användas för alla moderna datorer. Det är också värt att notera att den rekursiva samtalsstapeln aldrig kommer att bli djupare än 26 (troligen aldrig blir djupare än 15), så det är också mycket hanterbart från den dimensionen också.

En fördel med bitmaskeringen med endast 2²⁶ tillstånd är att alla tillstånd kan lagras i minnet. Eftersom det bara finns 3 värden per tillstånd (-1, 0, 1) kan detta lagras i en enda byte. Vid ett enda byte per tillstånd kommer 2²⁶ tillstånd att uppgå till cirka 67 megabyte, vilket återigen är mycket hanterbart.

När alfabetet ökar ökar dock sökutrymmet exponentiellt och körtiden ökar, vilket orsakar problem att bli svårt mycket snabbt. En kort diskussion om att närma sig det perfekta pangramet för större alfabet finns i avsnittet ”Språk med större alfabet” nedan.

Dynamiskt bygga en riktad cyklisk graf (DAG)

Nu när vi har fyllt i bitmasktillstånden, tid att hämta lösningen!

För att hitta de uppsättningar ord som skapade uppsättningen av möjliga perfekta pangram, måste vi härleda vilka mellanliggande tillstånd som var integrerade i att komponera de slutliga tillstånden Därefter är uppföljningsfrågan vilka andra mellanliggande stater som har sammansatt dessa mellanliggande tillstånd, och så vidare tills det enda som återstår är de stater som kartläggs direkt till ord. Denna process kallas backtracking.

spår av förhållandena mellan stater, är målet att skapa en Di rected Acyclical Graph (DAG), som upprätthåller vilka mellanliggande stater som utgör ett givet tillstånd. DAGs är lätta att korsa för att hämta utdata, särskilt på grund av deras icke-cykliska natur. För att konstruera, börja från det möjliga perfekta pangramtillståndet och skapa en riktad kant (pil) som pekar på de mellanliggande tillstånden som komponerar det. Upprepa processen med mellanliggande tillstånd, och det kommer att producera en DAG. Det kommer aldrig att finnas några cykler eftersom pilarna alltid pekar på ett tillstånd med ett mindre värde.

I stället för att återuppbygga relationerna som upptäcktes i söksteget, vilket innebär att man igenomkörs genom biljoner möjliga tillståndskombinationer, är det effektivare att bygga DAG under den dynamiska programmeringsfasen. Inom lösningsmetoden, om ett nykonstruerat tillstånd kan nå det möjliga perfekta pangramtillståndet, lagrar du en riktad kant från det nykonstruerade tillståndet till det ursprungliga tillståndet endast om det ursprungliga tillståndet är mindre än dess komplement (för att minska kantdublisering). p>

Skriv ut frukten av ditt arbete i trädform!

Det enklaste formatet för att visa de resulterande uppsättningarna ord är troligen att lista dem som träd med rotnoden som det perfekta pangramtillståndet. Med tanke på DAG konstruerad ovanifrån är det bästa sättet att packa upp det att göra det rekursivt, skriva varje tillstånd till disk i varje steg istället för i minnet eftersom trädet är en storleksordning större än DAG.

En förbättring av denna form av expansion är att sammanfatta tillstånd som endast har en enda möjlig kombination av ord. Ett tillstånd som är en mask till ord och inga substater som komponerar det kan kortfattas sammanfattas. Ett tillstånd kan sammanfattas om dess substrat och dess kompositer kan sammanfattas och alla masker som härrör från sig själv och dess barn inte har överlappande bitar / tecken. Utskrift av den sammanfattade DAG förbättrar läsbarheten för det resulterande utmatningsträdet genom att förkorta och förenkla det.

Eftersom sammanfattningen bara beror på det mindre av de två tillstånden, itererar det genom matrisen från det ursprungliga tillståndet 0 och uppåt och genom att använda reglerna ovan för att hantera sammanfattningsregeln kan detta slutföras linjärt.

Producerade pangramträd!

Korsa gärna genom de perfekta pangramträdarna för att se om du kan hitta intressanta meningar!

Det finns många möjliga perfekta pangram

Jag blev förvånad över antalet perfekta möjliga pangram. Det finns en hel del! Den bästa strategin för att sätta ihop dem kräver inte en komplex naturlig språkprocessor. När kandidatorden har märkts som substantiv eller verbberättigande måste påsen med ord innehålla minst ett substantiv, ett verb och rätt förhållande mellan substantiv och verb.

Datakvalitet är ett svårt problem

Algoritmsektionen tog två dagar, men datakvalitetsproblemet tog två veckor. När jag nämnde denna upptäckt för min vän som är senioringenjör Google, blev han inte förvånad och kommenterade att datakvalitetsproblem är några av de svåraste problemen inom teknik. Lärdom.

Reglerna för perfekta pangram

Det finns många nyanser vad som kvalificerar som ett perfekt pangram! Jag ville söka igenom pangram utan några interjektioner (t.ex. hm, pht), men det finns också andra populära restriktioner som förkortningar, akronymer, sammandragningar, initialismer, isolerade bokstäver, egennamn och romerska siffror. Det finns också ord som är bokstavsnamn, som Qoph, som jag kände som fusk.

Med några av dessa begränsningar avslappnade finns det många ”perfekta” pangram. . Det finns många akronymer och initialismer.

Asterisken

Asterisken är på plats eftersom definitionen av alla de perfekta pangrammen på engelska inte är väldefinierad. Det finns nyanser relaterade till vad som bör tillåtas i perfekta pangram på engelska. Det finns också många påståenden om huruvida vissa ord till och med är engelska ord. Med tanke på dessa nyanser är det verkligen svårt att säga att jag har hittat alla perfekta pangram. Jag kan göra två påståenden ganska säkert:

1. Jag har hittat en metod för att producera alla perfekta pangram på engelska och andra språk med liknande eller mindre teckenuppsättningar.
2. I har räknat upp alla uppsättningar ord som eventuellt kan bilda perfekta pangram med hjälp av den officiella Scrabble-turneringsdictionaren y, OWL3.

Tveka inte att producera dina egna perfekta pangram med de tekniker som beskrivs i det här inlägget!

Perfekt Pangrams beroende av ord av walesiska och arabiska rötter

Walesiska och arabiska härledda ord var verkligen viktiga för förekomsten av perfekta engelska pangram (om inte begränsningarna för det perfekta pangramet är avslappnade). Med hjälp av OWL3-ordlistan med strikta regler för perfekta pangram finns det inga perfekta pangram som inte innehåller orden ”cwm (s)” eller ”crwth (s)”, båda walesiska orden. I internationella Scrabble är det arabiska härledda ordet ”waqf (s)” ett giltigt ord som kan producera perfekta pangram utan att tillgripa ”cwm (s)” eller ”crwth (s)”.

Effektivitet i arbetsströmmen

Det var viktigt att bli effektivare vid parallellisering av uppgifter under detta projekt. En fullständig körning tar 25 minuter för Unix-ordlistan och nära en timme för de riktigt stora ordböckerna. Jag hade några initiala problem att byta sammanhang i ett 30-minutersfönster, men blev bättre på det när jag gick för att förbättra min produktivitet.

Extension / Generalization – Anagram Finder

Det perfekta pangramet sökning motsvarar också en anagramsökare för strängen ”abcdefghijklmnopqrstuvwxyz”. Vad händer om du vill bygga en generisk anagramsökare?

Samma teknik kan användas så länge som statens representations- och hanteringsregler för kontroll ordkombinationens giltighet uppdateras. I stället för att tillstånd ska hanteras som ett heltal skulle det vara lättare att spåra tillståndet som en karta över de relevanta tecknen. Att se om kombinationer är giltiga är att säga att kombinationen av två kartor inte överstiger anagrams önskade teckenantal för varje bokstav. Se bara till att tillståndsutrymmet är spårbart; med för många bokstäver kan sökutrymmet bli riktigt stort i ett ögonblick. Får du också upprepa ord? Se till att du definierar dessa regler inuti din dynamiska programmering lösning.

Språk med större alfabet

Detta tillvägagångssätt och lösning är linjära i orduppsättningsstorleken, men exponentiell i alfabetstorlek. Detta tillvägagångssätt kanske inte fungerar med en större karaktärsuppsättning, säg modern japansk som har 46 kursplaner. 2 är 70,368,744,177,664; över en miljon gånger större än det engelska sökutrymmet på 2²⁶ = 67,108,864.

Det är inte helt klart om denna metod skulle fungera för japanska. Om det japanska språket har tillräckligt låg entropi, vilket är möjligt, skulle detta tillvägagångssätt vara genomförbart. Istället för att initialisera en matris av storlek 2⁴⁶ kommer tillstånden att spåras på en karta. Dessutom kan japanska strukturer utnyttjas; till exempel kana を (wo) används nästan uteslutande som postpositionspartikel och kan uteslutas från sökningen, vilket minskar sökutrymmet.

Det kambodjanska språket Khmer har det största alfabetet med 74. Ett annat möjligt nästa steg är att utforska lösningar som är subexponentiella i alfabetstorlek.

Inspiration

Jag inspirerades av Aubrey De Greys framsteg när det gäller att hitta det kromatiska numret på planet som ska vara åtminstone 5. Detta är en betydande framsteg som uppnåddes genom grundläggande beräkningsmetoder.

Det behöver inte sägas att hitta perfekta pangram inte håller ett ljus för att förbättra den nedre gränsen för det kromatiska antalet i ett plan. / p>

Detta får mig att tro att det finns många låghängande fruktproblem som har enkla beräkningsmetoder för att lösa ett problem som är svårt att manuellt. Jag utmanar dig att hitta och lösa några av dessa problem. Snälla meddela mig om du hittar något!

Tack

Jag är ganska tacksam för mina mycket bra vänner som hjälpte till med korrekturläsning och jamming på detta med mig, särskilt Anna Zeng, Catherine Gao, Danny Wasserman, George Washington och Nick Wu!