Alle * perfecte Engelse pangrammen

Een Engelse pangram is een zin die alle 26 letters van het Engelse alfabet bevat. De meest bekende Engelse pangram is waarschijnlijk “De snelle bruine vos springt over de luie hond”. Mijn favoriete pangram is “Verbazingwekkend weinig discotheken bieden jukeboxen aan.”

Een perfecte pangram is een pangram waarin elk van de letters verschijnt slechts één keer. Ik heb online enkele bronnen gevonden met de bekende perfecte pangrams. Niemand lijkt met succes te hebben geprobeerd ze allemaal uitputtend te produceren, dus ik nam het op als een leuke uitdaging. Dit is hoe ik alle * de perfecte pangrammen van het Engels vond. Ik zal de asterisk later uitleggen.

• Crwth vox zaps qi gym fjeld bunk. (Het geluid van een Keltische viool klinkt in een oostelijk op spirituele krachten gericht fitnesscentrum gelegen op een kaal plateau van Scandinavië.) Dit zijn allemaal juridische Scrabble-woorden!
• Squdgy kilp job zarf nth cwm vex. (De slechtgevormde kelp koopt een decoratieve bekerwarmer die een van de vele halfopen steile holtes aan de kop van een vallei of berghelling heeft geïrriteerd.)
• Jocknimfen waqf drug-erger-blitz. (De liefdadigheidsinstelling bedwelmde de bosgeesten, die de atleet frustreerden, die zich bezighield met een aanval.)
• Hm, fjordwals, cinq busk, pyx veg. (Eens kijken, een lange smalle diepe inlaat danst, de vijf op de dobbelstenen maken muziek op straat, en de kleine ronde container voor de zieke en onbekwame rust.) Ook Scrabble legaal, maar heeft een tussenwerpsel (Hm).

Helaas zijn dit enkele van de best leesbare zinnen die ik kon vinden *. Alle perfecte pangrams die zijn gegenereerd op basis van de Official Tournament and Club Word List 3 (OWL3) voor Scrabble zonder tussenwerpsels, bevatten het woord cwm of crwth. Waqf is legaal voor Scrabble-toernooien buiten Noord-Amerika.

Hoe alle perfecte pangrams te vinden

De methode om perfecte pangrams te vinden bestaat uit twee stappen. De eerste is om alle sets woorden te vinden die elke letter van het Engelse alfabet één keer bevatten. De tweede stap is om te zien welke van die sets herschikt kunnen worden in geldige Engelse zinnen.

Stap 1: zoeksets woorden voor de perfecte pangram

Om te beginnen met het vinden van reeksen woorden die span het Engelse alfabet vereist een lijst met Engelse woorden. Het vinden en bijhouden van een woordenlijst van hoge kwaliteit was veel moeilijker dan ik had verwacht. Oorspronkelijk dacht ik dat dit project twee dagen zou duren, maar het duurde uiteindelijk twee weken als gevolg van dit datakwaliteitsprobleem.

Ik begon met het Unix-woordenboek, een gratis beschikbare lijst met Engelse woorden dat wordt geleverd met bijna alle op Unix gebaseerde besturingssystemen. Ik merkte meteen dat de lijst kwaliteitsproblemen had. Ten eerste werd elke letter van het alfabet als een woord in het Unix-woordenboek beschouwd en bevatte het veel niet-woorden, zoals vejoz. Dit toonde de noodzaak aan van een zwarte lijst om de lijsten met woorden die online werden gevonden te beheren. Unix-woordenboek miste meervoudsvormen voor woorden, dus het woordenboek zou het woord “oranje” bevatten, maar niet “sinaasappels”. De woordenlijst is zo beperkend dat geen voorheen bekende perfecte pangrammen alleen woorden uit het Unix-woordenboek bevatten. Ik vond nog steeds sommige, zoals “squdgy kilp job zarf nth cwm vex”.

Ik ging toen naar het internet om grotere groepen woorden te vinden. Ik vond zeer grote woordgroepen die enorm waren, maar toen ik begon te graven naar perfecte pangrams uit die lijsten, ontdekte ik dat ze veel te vervuild waren met woorden van lage kwaliteit die geen geldige Engelse woorden zijn. Zelfs na vele iteratieronden, slaagde ik er nog steeds niet in om de lijst af te werken om redelijke of beheersbare pangrammen te vinden. Ik heb geprobeerd het op te ruimen door een witte lijst met woorden van een bepaalde lengte te maken, maar de kwaliteit was nog steeds van zeer lage kwaliteit.

Eindelijk, na vele herhalingen, betaalde ik $ 15 om een proeflidmaatschap van de North American Scrabble® Players Association, die me toegang gaf tot de gepatenteerde en auteursrechtelijk beschermde OWL3, die de bron is van enige controverse. Zelfs toen moest ik enkele bekende Engelse woorden toevoegen, zoals de woorden “a” en “I” die uit één letter bestaan.

Gewapend met een behoorlijke lijst met woorden implementeerde ik een algoritme om alle sets woorden uit die lijst die elk een van elke letter van het Engelse alfabet bevatten. Ik zal het algoritme uitvoerig beschrijven in het gedeelte Het algoritme hieronder.

Stap 2: Engelse zinnen vormen uit een zak met woorden

Gegeven een reeks woorden, uitzoeken of een geldige Engelse zin is mogelijk met alle geleverde woorden is een niet-triviaal probleem, maar het is gemakkelijker dan de meeste andere natuurlijke taalverwerking (NLP) problemen.

Er zijn handige heuristieken om niet-geschikte zinnen te verwijderen; Ik was in staat om geldige Engelse zinnen te vormen uit de resterende woorden nadat ik die heuristieken had gevolgd. De zinnen waren vaak onzinnig, maar toch geldig. Hier zijn de heuristieken die ik heb gebruikt:

1. Er moet minstens één werkwoord zijn.
2. Er kan maar één zelfstandig naamwoord meer zijn dan er werkwoorden, tenzij er een voegwoord is of een voorzetsel, die beide zeer zeldzaam zijn.
3. Als er bijvoeglijke naamwoorden zijn, moeten er ook zelfstandige naamwoorden zijn.

De heuristiek werkt gedeeltelijk vanwege de mogelijkheid van impliciete onderwerpen (noch perfect, noch een pangram, maar beweeg rustig en spreek zacht is een zin met twee werkwoorden en geen zelfstandige naamwoorden, met het geïmpliceerde onderwerp jij).

Aangezien de ruimte van woorden die kan mogelijk deelnemen aan perfecte pangrams is klein, het is gemakkelijk genoeg om elk afzonderlijk woord handmatig te taggen met de in aanmerking komende woordsoorten en te kijken of de reeks woorden aan deze drie eenvoudige heuristieken voldoet. Of je de kwaliteit van de geproduceerde zinnen al dan niet leuk vindt, is een kwestie van smaak.

Het algoritme

Dit gedeelte is een beetje technisch, maar hopelijk nog steeds gemakkelijk te volgen. Ga gerust naar het gedeelte “Resultaten & Leren”.

Strategie op hoog niveau

Het doel is om alle mogelijke sets van woorden uit de gegeven lijst met woorden die het Engelse alfabet “perfect” overspannen.

1. Maak de lijst met woorden schoon om de zoekruimte drastisch te verminderen, bijv. verwijder woorden met herhaalde letters, zoals letters.
2. Gebruik bitmaskers om woorden efficiënt weer te geven en wijs ze terug naar de oorspronkelijke woordenreeksen.
3. Doorzoek alle mogelijke staten, elk vertegenwoordigen een mogelijke lettercombinatie, door herhaaldelijk door de lijst met bitmaskers te lopen. De prestaties zijn drastisch verbeterd met dynamisch programmeren.
4. Teken pijlen (gerichte randen) vanuit de perfecte pangramtoestand, de eindtoestand die alle de Engelse letters, aan de tussenstaten die het hebben samengesteld. Doe dat opnieuw met de tussenliggende staten om een datastructuur te creëren die de sets woorden kan reconstrueren die mogelijk perfecte pangrammen zijn. Dit wordt backtracking genoemd.
5. Output de ontdekte woordenreeksen die mogelijk perfecte pangrams zijn als bomen.

De lijst opschonen, ook bekend als Canonicalization

De eerste stap is het opschonen van de oorspronkelijke lijst met woorden om de zoekruimte te verkleinen en de uitvoerkwaliteit te verhogen.

1. Verwijder alle witruimte rond het woord en converteer het alleen naar kleine letters.
2. Zorg ervoor dat de woorden alleen letters van het Engelse alfabet bevatten; Ik heb een eenvoudig filter voor reguliere expressies gebruikt: /^+$/
3. Filter tegen andere lijsten, bijv. zwarte lijsten; als een woord op de zwarte lijst staat, sla dat woord dan over.
4. Verwijder alle woorden met herhaalde letters

Dit verkortte de zoekruimte aanzienlijk, van lijsten van 200.000 ~ 370.000 woorden naar een veel kleinere 35.000 ~ 65.000 woorden.

Bitmaskers gebruiken

Bitmaskers zijn representaties van staten met gehele getallen. Er zijn verschillende voordelen van bitmaskers:

• Bitmaskers vertegenwoordigen dit probleem goed. Lettervolgorde doet er niet toe, dus alle combinaties van woorden kunnen worden weergegeven als een 26-cijferige reeks van nullen en enen, waarbij elk cijfer aangeeft of er al dan niet een letter in de combinatie voorkomt. Bijvoorbeeld. als de set woorden de letter e bevat, is het 5e cijfer een 1, anders een 0.
• Bitmaskers zijn efficiënt: aangezien de zoekruimte constant is, bieden bitmaskers een efficiënte opslag en weergave van alle mogelijke combinaties van letters. Bovendien zijn bitsgewijze bewerkingen snel; om te testen of twee bitmaskers kunnen worden gecombineerd om een groter bitmasker te produceren, controleert u of de bitsgewijze EN van de twee maskers gelijk is aan 0, die beide extreem zijn snelle bewerkingen.

Dus verander elk woord in een bitmasker, dat kan worden weergegeven als een geheel getal. Het woord cab wordt bijvoorbeeld toegewezen aan het bitmasker van 111, dat is het decimale getal 7. Het woord “be” wordt toegewezen aan 10010, dat is het decimale getal 18, enzovoort. Het grootst mogelijke bitmasker is een met alle letters van het alfabet, de mogelijke perfecte pangramtoestand, 1111111111111111111111111111, dat is het decimale getal 67,108,863, of 2²⁶ -1. Dit past goed binnen een standaard 32-bits geheel getal met teken, dat kan vertegenwoordigen tot 2³¹-1.

Door bitmaskers te gebruiken, wordt de ruimte verder gecomprimeerd, aangezien enkelvoudige woordanagrammen naar hetzelfde bitmasker verwijzen. Zowel “oven” als “link” verwijzen naar het masker 10110100000000, wat het decimale getal 11520 is. Dit reduceert de zoekruimte van 35.000 ~ 65.000 woorden verder tot 25.000 ~ 45.000 bit maskers.

Bewaar een afbeelding van het bitmasker terug naar de set woorden waarvan ze zijn afgeleid. Dit zal handig zijn bij het uitvoeren van de sets woorden.

Zoeken naar het perfecte pangram met dynamische programmering

De kern van het algoritme is vrij eenvoudig:

Gegeven een mogelijke toestand (die is samengesteld uit geldige combinaties van bestaande woorden), probeer dan alle maskers uit de initiële woordenlijst om te zien of het mogelijk is om een nieuwe geldige toestand te creëren (door te controleren of de bitsgewijze EN van de staat en het masker zijn gelijk aan 0, wat zou betekenen dat er geen overlappende letters zijn). Creëer de nieuwe staat door de bitsgewijze OR-bewerking te gebruiken die alle enen samenvoegt. Voor elke nieuwe ontdekte staat, blijf herhalen totdat er geen onontgonnen staten meer zijn. Als dit het einde bereikt, betekent dit dat het algoritme ten minste één mogelijke perfecte pangramwoordset heeft gevonden. De eerste mogelijke toestand die alle mogelijke staten kan opsommen, is de lege staat of 0, waar geen letters van het alfabet zijn opgenomen. Dus begin daar en ontdek dan recursief welke toestanden mogelijk zijn.

Een enorme efficiëntiewinst is te merken dat er veel manieren zijn om een onderbroken toestand te bereiken en dat het werk aan de toestand niet verandert op basis van hoe het was bereikt. Dus in plaats van het werk te herhalen wanneer een staat opnieuw wordt bezocht, slaat u het resultaat van elke staat op. Deze techniek heet dynamisch programmeren en verandert een complex combinatorisch probleem in een lineair programma. Het proces van het opslaan van de intermitterende toestand wordt memoisatie genoemd.

Maak dus een array van 2²⁶, tussen 0 en 67.108.863, inclusief. Elke index vertegenwoordigt een bitmaskertoestand zoals eerder uitgelegd. De waarde bij elke index van de array vertegenwoordigt wat er bekend is over de staat. 0 betekent ofwel dat de staat onaangetast of onbereikbaar is. 1 betekent dat de staat een manier heeft gevonden om de mogelijke perfecte pangramstaat te bereiken. -1 betekent dat de staat er niet in is geslaagd een manier te vinden om het einde te bereiken.

Pseudocode hieronder:

Intermezzo: Complexiteit en praktische runtime-analyse

Er zijn 2²⁶ mogelijke bitmaskers voor een serie van 26 bits. Omdat elke toestand slechts één keer wordt verwerkt vanwege memoisatie, is de looptijd van dit algoritme O (n 2 ^ d), waarbij d de grootte van het alfabet is, 26. De variabele n staat niet voor het aantal woorden, maar de aantal bitmaskers. Met 67.108.863 en ongeveer 45.000 bit-maskers komt dit neer op ongeveer 3 biljoen, wat mijn MacBook Pro in ongeveer 45 minuten aankan; traceerbaar voor elke moderne computer. Het is ook vermeldenswaard dat de recursieve call-stack nooit dieper zal worden dan 26 (waarschijnlijk nooit dieper dan 15), dus het is ook zeer beheersbaar vanuit die dimensie.

Een voordeel van de bitmaskerbenadering met slechts 2²⁶ toestanden is dat alle toestanden in het geheugen kunnen worden opgeslagen. Aangezien er slechts 3 waarden per toestand zijn (-1, 0, 1), kunnen deze in één byte worden opgeslagen. Met een enkele bytes per toestand, komt 2²⁶ toestanden uit op ongeveer 67 megabytes, wat opnieuw zeer beheersbaar is.

Naarmate het alfabet toeneemt, neemt de zoekruimte echter exponentieel toe, evenals de looptijd, waardoor de probleem om heel snel hardnekkig te worden. Een korte bespreking over het benaderen van de perfecte pangram voor grotere alfabetten vindt u in de sectie “Taal met grotere alfabetten” hieronder.

Dynamisch bouwen van een Directed Acyclical Graph (DAG)

Nu we hebben de bitmaskerstatussen ingevuld, tijd om de oplossing op te halen!

Om de sets woorden te vinden die de set van mogelijke perfecte pangrammen creëerden, moeten we afleiden welke tussenliggende toestanden integraal waren bij het samenstellen van de eindtoestanden . Vervolgens is de vervolgvraag welke andere tussenstaten die tussenstaten hebben samengesteld, enzovoort, totdat het enige dat overblijft de staten zijn die rechtstreeks aan woorden zijn toegewezen. Dit proces wordt backtracking genoemd.

Behouden om de relaties tussen staten te volgen, het doel is om een Di te creëren gerectificeerde Acyclical Graph (DAG), waarin wordt bijgehouden welke tussenliggende staten een bepaalde staat vormen. DAGs zijn gemakkelijk te doorlopen om uitgangen op te halen, vooral vanwege hun niet-cyclische aard. Om te construeren, start u met de mogelijke perfecte pangram-toestand en maakt u een gerichte rand (pijl) die naar de tussenliggende staten wijst waaruit het bestaat. Herhaal het proces met de tussenliggende staten en het zal een DAG produceren. Er zullen nooit cycli zijn omdat de pijlen altijd naar een toestand met een kleinere waarde wijzen.

In plaats van de relaties die tijdens de zoekstap zijn ontdekt opnieuw op te bouwen, waarbij je opnieuw triljoenen mogelijke toestandscombinaties moet doorlopen, is het efficiënter om de DAG te bouwen tijdens de dynamische programmeerfase. Als een nieuw geconstrueerde toestand binnen de oplossingsmethode de mogelijke perfecte pangramtoestand kan bereiken, sla dan een gerichte rand op van de nieuw gebouwde toestand naar de oorspronkelijke toestand alleen als de oorspronkelijke toestand kleiner is dan zijn complement (om randduplicatie te verminderen).

Druk de vruchten van uw werk af in boomvorm!

Waarschijnlijk is de gemakkelijkste indeling voor het bekijken van de resulterende woordenreeksen door ze op te sommen als bomen met de root-node als de perfecte pangram-toestand. Gegeven de DAG die van bovenaf is opgebouwd, is de beste manier om het uit te pakken door dit recursief te doen, waarbij elke toestand bij elke stap naar schijf wordt geschreven in plaats van in het geheugen, aangezien de boom een orde van grootte groter is dan de DAG.

Een verbetering van deze vorm van expansie is om staten samen te vatten die slechts één mogelijke combinatie van woorden hebben. Een toestand die een masker is voor woorden en geen substaten waaruit het bestaat, kan triviaal worden samengevat. Een toestand kan worden samengevat als zijn substaten en zijn samenstellingen kunnen worden samengevat, en alle maskers die van zichzelf en zijn kinderen zijn afgeleid, hebben geen overlappende bits / tekens. Het afdrukken van de samengevatte DAG verbetert de leesbaarheid van de resulterende uitvoerboom door deze in te korten en te vereenvoudigen.

Aangezien de samenvatting alleen afhangt van de kleinste van de twee toestanden, itereren door de array vanaf de begintoestand 0 naar boven en door de bovenstaande regels te gebruiken om de samenvattingsregel te beheren, kan dit in lineaire tijd worden voltooid.

Geproduceerde pangrambomen!

Voel je vrij om door de perfecte pangrambomen te lopen om te zien of je kan interessante zinnen vinden!

Er zijn veel mogelijke perfecte pangrammen

Ik was verrast door het aantal perfect mogelijke pangrams. Er zijn veel! De beste strategie om ze samen te voegen, vereist geen complexe natuurlijke taalprocessor. Zodra de kandidaat-woorden zijn gelabeld als geschikt zelfstandig naamwoord of werkwoord, moet de zak met woorden ten minste één zelfstandig naamwoord, één werkwoord en de juiste verhouding tussen zelfstandige naamwoorden en werkwoorden bevatten.

Datakwaliteit is een moeilijk probleem

Het algoritme-gedeelte duurde twee dagen, maar het datakwaliteitsprobleem duurde twee weken. Toen ik deze bevinding vertelde aan mijn vriend, een senior stafingenieur bij Google, was hij niet verbaasd en merkte op dat problemen met de gegevenskwaliteit enkele van de moeilijkste problemen in engineering zijn. Geleerde les.

De regels van perfecte pangrams

Er zijn veel nuances met betrekking tot wat kwalificeert als een perfecte pangram! Ik wilde pangrams doorzoeken zonder tussenwerpsels (bijv. Hm, pht), maar er zijn ook andere populaire beperkingen, zoals afkortingen, acroniemen, samentrekkingen, initialismen, losse letters, eigennamen en Romeinse cijfers. Er zijn ook woorden die namen van letters zijn, zoals Qoph, waarvan ik dacht dat het bedrog is.

Met een aantal van die beperkingen zijn er wat minder, er zijn veel “perfecte” pangrams. In de orde van triljoenen, waarschijnlijk . Er zijn veel afkortingen en initialismen.

De asterisk

De asterisk is aanwezig omdat de definitie van alle perfecte pangrammen van het Engels niet goed is gedefinieerd. Er zijn nuances gerelateerd aan wat moet worden toegestaan in perfecte pangrammen van het Engels. Er zijn ook veel twijfels over het feit of sommige woorden wel of niet Engelse woorden zijn. Gezien deze nuances is het erg moeilijk om te zeggen dat ik alle perfecte pangrammen heb gevonden. Ik kan redelijk zeker twee beweringen doen:

1. Ik heb een methodologie gevonden om alle perfecte pangrammen van het Engels en andere talen te produceren met vergelijkbare of kleinere tekensets.
2. I hebben alle reeksen woorden opgesomd die mogelijk perfecte pangrams kunnen vormen met behulp van de officiële Scrabble-toernooi-dictionar y, OWL3.

Voel je vrij om je eigen perfecte pangrams te produceren met de technieken die in dit bericht worden beschreven!

Perfecte afhankelijkheid van Pangrams van woorden van Welshe en Arabische wortels

Woorden afgeleid van het Welsh en Arabisch waren erg belangrijk voor het bestaan van perfecte Engelse pangrams (tenzij de beperkingen van de perfecte pangram worden versoepeld). Door gebruik te maken van de OWL3-woordenlijst met strikte regels voor perfecte pangrams, zijn er geen perfecte pangrams die niet de woorden “cwm (s)” of “crwth (s)” bevatten, beide Welshe woorden. In internationale Scrabble is het Arabisch afgeleide woord “waqf (s)” een geldig woord dat perfecte pangrams kan produceren zonder toevlucht te nemen tot “cwm (s)” of “crwth (s)”.

Werkstroomefficiëntie

Het was belangrijk om efficiënter te worden in het parallelliseren van taken tijdens dit project. Een volledige uitvoering duurt 25 minuten voor het Unix-woordenboek en bijna een uur voor de echt grote woordenboeken. Ik had in het begin wat problemen met het wisselen van context gedurende een periode van 30 minuten, maar werd er steeds beter in om mijn productiviteit te verbeteren.

Uitbreiding / generalisatie – Anagram Finder

Het perfecte pangram zoeken is ook gelijk aan een anagramzoeker voor de tekenreeks “abcdefghijklmnopqrstuvwxyz”. Wat als je een generieke anagramzoeker wilde bouwen?

Dezelfde techniek kan worden gebruikt zolang de statusweergave en beheerregels voor het controleren de geldigheid van woordcombinaties wordt bijgewerkt. In plaats van staten te laten beheren als een geheel getal, zou het gemakkelijker zijn om de staat bij te houden als een kaart van de relevante tekens. Zien of combinaties geldig zijn, wil zeggen dat de combinatie van twee kaarten de het gewenste aantal tekens van het anagram voor elke letter. Zorg ervoor dat de toestandsruimte traceerbaar is; met te veel letters kan de zoekruimte in een handomdraai erg groot worden. Mag je ook woorden herhalen? Zorg ervoor dat je die regels binnen uw dynamische programmering oplossing.

Talen met grotere alfabetten

Deze benadering en oplossing zijn lineair in de grootte van de woordset, maar exponentieel in alfabetische grootte. Deze benadering werkt mogelijk niet met een grotere tekenset, bijvoorbeeld modern Japans, dat 46 lettergrepen heeft. 20 is 70.368.744.177.664; meer dan een miljoen keer groter dan de Engelse zoekruimte van 2²⁶ = 67,108,864.

Het is niet helemaal duidelijk of deze benadering al dan niet zou werken voor Japanners. Als de Japanse taal een voldoende lage entropie heeft, wat mogelijk is, zou deze benadering levensvatbaar zijn. In plaats van een array van grootte 2⁴⁶ te initialiseren, worden de toestanden bijgehouden in een kaart. Bovendien kan de structuur van het Japans worden uitgebuit; de kana を (wo) wordt bijvoorbeeld bijna uitsluitend gebruikt als een post-positioneel deelwoord en kan worden uitgesloten van de zoekopdracht, waardoor de zoekruimte wordt verkleind.

De Cambodjaanse taal Khmer heeft het grootste alfabet met 74. Een andere mogelijke volgende stap is het onderzoeken van oplossingen met een sub-exponentiële alfabetgrootte.

Inspiratie

Ik werd geïnspireerd door Aubrey De Greys vorderingen bij het vinden van het chromatische nummer van het vliegtuig dat ten minste 5. Dit is een aanzienlijke vooruitgang die werd bereikt door middel van elementaire computationele methoden.

Onnodig te zeggen dat het vinden van perfecte pangrammen geen kaars is om de ondergrens van het chromatische getal van een vlak te verbeteren.

Dit doet me geloven dat er veel laaghangende fruitproblemen zijn die eenvoudige rekenmethoden hebben om een probleem op te lossen dat handmatig hardnekkig is. Ik daag je uit om enkele van deze problemen op te sporen en op te lossen. Laat het me alsjeblieft weten als je iets vindt!

Bedankt

Ik ben heel dankbaar voor mijn uitstekende vrienden die hebben geholpen door met mij proeflezen en jammen, vooral Anna Zeng, Catherine Gao, Danny Wasserman, George Washington en Nick Wu!