Všechny * dokonalé pangramy angličtiny

Anglický pangram je věta, která obsahuje všech 26 písmen anglické abecedy. Nejznámějším anglickým pangramem je pravděpodobně „Rychlá hnědá liška skáče přes líného psa.“ Můj oblíbený pangram je „Úžasně málo diskoték poskytuje jukeboxy.“

Perfektní pangram je pangram, kde každé z písmen se zobrazí pouze jednou. Našel jsem online nějaké zdroje, které uvádějí známé dokonalé pangramy. Zdá se, že se nikdo nepokusil úspěšně je všechny vyrobit vyčerpávajícím způsobem, takže jsem to vzal jako zábavnou výzvu. Takto jsem našel všechny * perfektní pangramy angličtiny. Hvězdičku vysvětlím později.

• Crwth vox zaps qi gym fjeld bunk. (Zvuk keltských houslí zasáhne fitness centrum zaměřené na východní duchovní síly, které se nachází na pusté skandinávské náhorní plošině.) Toto jsou všechna legální slova Scrabble!
• Squdgy kilp job zarf nth cwm vex. (Neformovaná řasa si koupí ozdobný ohřívač šálků, který dráždila jedna z mnoha pootevřených strmých prohlubní v údolí nebo na úbočí hory.)
• Jock nymfy waqf drog vex blitz. (Charitativní nadace intoxikovala lesní duchy, kteří frustrovali sportovce, který se účastní útoku.)
• Hm, fjordský valčík, cinq busk, pyx veg. (Podívejme se, dlouhý úzký hluboký vstupní tanec, pět na kostkách dělá hudbu na ulici a malý kulatý kontejner pro nemocné a neschopné odpočívá.) Také Scrabble legální, ale má citoslovce (Hm).

Bohužel, toto jsou některé z nejčtenějších vět, které jsem našel *. Všechny dokonalé pangramy generované z oficiálního turnaje a seznamu klubových slov 3 (OWL3) pro Scrabble bez citoslovce obsahují buď slovo cwm, nebo crwth. Waqf je turnaj Scrabble legální mimo Severní Ameriku.

Jak najít všechny dokonalé pangramy

Metoda hledání dokonalých pangramů má dva kroky. Prvním je najít všechny sady slov, která obsahují každé písmeno anglické abecedy jednou. Druhým krokem je zjistit, které z těchto sad lze přeskupit do platných anglických vět.

Krok 1: Hledání sad slov pro dokonalý pangram

Chcete-li začít hledat sady slov, která anglická abeceda vyžaduje seznam anglických slov. Nalezení a udržování vysoce kvalitního seznamu slov bylo mnohem těžší, než jsem předpokládal. Původně jsem si myslel, že tento projekt bude trvat dva dny, ale v důsledku tohoto problému s kvalitou dat to trvalo dva týdny.

Začal jsem slovníkem Unix, což je volně dostupný seznam anglických slov který je dodáván s téměř všemi operačními systémy založenými na Unixu. Okamžitě jsem si všiml, že seznam má problémy s kvalitou. Za prvé, každé písmeno abecedy bylo ve slovníku Unixu považováno za slovo a obsahovalo mnoho slov, například „vejoz“. To prokázalo potřebu černé listiny pro správu seznamů slov nalezených online. Ve slovníku Unixu chybí slova v množném čísle, takže by slovník obsahoval slovo „oranžová“, ale ne „pomeranče“. Seznam slov je ve skutečnosti tak omezující, že žádné dříve známé dokonalé pangramy neobsahují pouze slova ze slovníku Unix. Stále jsem našel některé, například „squdgy kilp job zarf nth cwm vex“.

Poté jsem se obrátil na internet a našel větší sady slov. Našel jsem velmi velké sady slov, které byly obrovské, ale když jsem z těchto seznamů začal kopat dokonalé pangramy, zjistil jsem, že jsou příliš znečištěné slovy nízké kvality, která nejsou platnými anglickými slovy. I po mnoha kolech iterace se mi nepodařilo vypátrat seznam a najít rozumné nebo zvládnutelné pangramy. Snažil jsem se to vyčistit vytvořením seznamu povolených slov určité délky, ale seznam byl stále extrémně nízký.

Nakonec jsem po mnoha iteracích zaplatil 15 $ za zakoupení zkušebního členství v Severní Americe Sdružení hráčů Scrabble®, které mi umožnilo přístup k vlastnickému a autorsky chráněnému OWL3, který je zdrojem určité kontroverze. I tehdy jsem musel přidat některá známá slova v angličtině, například jednopísmenná slova „a“ a „já“.

Vyzbrojen správným seznamem slov jsem implementoval algoritmus pro vytvoření všechny sady slov z tohoto seznamu, z nichž každé obsahuje jedno z každého písmene anglické abecedy. Algoritmus podrobně popíšu v části „Algoritmus“ níže.

Krok 2: Vytváření anglických vět z pytle slov

Vzhledem k množině slov, zjišťování, zda a platná anglická věta je možná se všemi zadanými slovy je netriviální problém, ale je jednodušší než většina ostatních problémů se zpracováním přirozeného jazyka (NLP).

Existují užitečné heuristiky pro vytrhávání nezpůsobilých vět; Po provedení těchto heuristik jsem ze zbývajících slov dokázal sestavit platné anglické věty. Věty byly často nesmyslné, ale stále platné. Zde jsou heuristiky, které jsem použil:

1. Musí existovat alespoň jedno sloveso.
2. Může existovat pouze jedno podstatné jméno více než sloves, pokud neexistuje spojka nebo předložka, obě jsou velmi vzácné.
3. Pokud existují adjektiva, musí existovat i podstatná jména.

Heuristika částečně funguje kvůli možnosti implicitního předměty (ani dokonalý, ani pangram, ale „pohybujte se tiše a mluvte tiše“ je věta se dvěma slovesy a podstatnými jmény, s implikovaným předmětem „vy“).

Protože prostor slov, která mohou možná účast na dokonalých pangramech je malá, je dost snadné ručně označit každé jednotlivé slovo příslušnými částmi řeči a zjistit, zda se soubor slov řídí těmito třemi jednoduchými heuristikami. To, zda se vám líbí nebo nelíbí kvalita vytvářených vět, je věcí vkusu.

Algoritmus

Tato část je trochu technická, ale doufejme, že bude stále snadná. Neváhejte přeskočit do části „Výsledky & Učení“.

Strategie na vysoké úrovni

Cílem je vytvořit všechny možné sady slova z daného seznamu slov, která překlenují anglickou abecedu „dokonale“.

1. Vyčistěte seznam slov, abyste drasticky zmenšili prostor pro vyhledávání, např. odstranit slova, která mají opakovaná písmena, například „písmena“.
2. Pomocí bitových masek můžete slova efektivně reprezentovat a namapovat je zpět na původní sady slov.
3. Hledat ve všech možných stavech, každé představuje možnou kombinaci písmen opakovaným iterací seznamem bitových masek. Výkon se dramaticky zlepší pomocí dynamického programování.
4. Nakreslete šipky (směrované hrany) ze stavu dokonalého pangramu, konečného stavu, který má všechny anglická písmena zprostředkujícím státům, které jej složily. Udělejte to znovu se zprostředkujícími stavy a vytvořte datovou strukturu, která dokáže rekonstruovat sady slov, které jsou možné dokonalými pangramy. Toto se nazývá zpětné sledování.
5. objevené sady slov, které jsou pravděpodobně dokonalými pangramy jako stromy.

Čištění seznamu, alias kanonizace

Prvním krokem je vyčištění původního seznamu slov, aby se zmenšil prostor pro vyhledávání a zvýšila kvalita výstupu.

1. Odstraňte veškerý bílý prostor kolem slova a převést je pouze na malá písmena
2. Zkontrolujte, zda slova obsahují pouze písmena anglické abecedy; Použil jsem jednoduchý filtr regulárních výrazů: /^+$/
3. Filtr proti jiným seznamům, např. černé listiny; pokud je slovo na černé listině, toto slovo přeskočte
4. Odeberte všechna slova s opakovanými písmeny

Tím se významně zkrátil prostor pro vyhledávání, ze seznamů 200 000 ~ 370 000 slov na mnohem menší 35 000 až 65 000 slov.

Použití bitových masek

Bitové masky jsou celočíselné reprezentace stavů. Existuje několik výhod bitových masek:

• Bitové masky tento problém dobře reprezentují. Na pořadí písmen nezáleží, takže všechny kombinace slov lze reprezentovat jako 26místnou řadu 0 a 1, přičemž každá číslice představuje, zda v kombinaci existuje písmeno. Například. pokud sada slov obsahuje písmeno „e“, bude 5. číslice číslo 1, jinak bude 0. 0.
• Bitové masky jsou účinné: Protože prostor pro vyhledávání je konstantní, bitové masky nabízejí efektivní úložiště a reprezentace všech možných kombinací písmen. Bitové operace jsou navíc rychlé; k otestování, zda lze kombinovat dvě bitové masky za účelem vytvoření větší bitové masky, zkontrolujte, zda se bitové AND dvou masek rovná 0, obě jsou extrémně rychlé operace.

Takže každé slovo změňte na bitovou masku, kterou lze reprezentovat jako celé číslo. Například slovo „cab“ bude namapováno na bitovou masku 111, která je desetinné číslo 7. Slovo „be“ se namapuje na 10010, což je desítkové číslo 18. atd. Největší možná bitová maska je jedna se všemi písmeny abecedy, možný dokonalý stav pangramu, 1111111111111111111111111111, což je desítkové číslo 67 108 863 nebo 2²⁶ -1. To se dobře hodí pro standardní 32bitové celé číslo se znaménkem, které může představovat až na 2³¹-1.

Použití bitových masek dále komprimuje prostor, protože jednoslovné anagramy se mapují na stejnou bitovou masku. Jak „pec“, tak „odkaz“ se mapují na masku 10110100000000, což je desítkové číslo 11520. To dále zmenšuje prostor hledání 35 000 ~ 65 000 slov na 25 000 ~ 45 000 bitových masek.

Zachovat mapování bitové masky zpět na sadu slov, z nichž jsou odvozeny. To bude užitečné při výstupu sad slov.

Hledání dokonalého pangramu pomocí dynamického programování

Jádro algoritmu je poměrně jednoduché:

Vzhledem k možnému stavu (který se skládá z platných kombinací existujících slov), vyzkoušejte všechny masky z počátečního seznamu slov, abyste zjistili, zda je možné vytvořit nový platný stav (kontrolou, zda je bitové AND stav a maska se rovnají 0, což by znamenalo, že neexistují žádná překrývající se písmena). Vytvořte nový stav pomocí bitové operace NEBO, která sloučí všechny jedničky dohromady. Pro každý nový objevený stav opakujte, dokud nenastanou další neprozkoumané stavy. Pokud to dosáhne konce, znamená to, že algoritmus našel alespoň jednu možnou sadu slov dokonalého pangramu. První možný stav, který umožňuje výčet všech možných stavů, je prázdný stav nebo 0, kde nejsou zahrnuta žádná písmena abecedy. Začněte tedy tam a poté rekurzivně zjistěte, které stavy jsou možné.

Jedním z obrovských zvýšení efektivity je všimnout si, že existuje mnoho způsobů, jak dosáhnout přerušovaného stavu a že práce na stavu se nemění podle toho, jak bylo dosaženo. Takže místo opakování práce, když je stav znovu navštíven, uložte výsledek každého stavu. Tato technika se nazývá dynamické programování a převádí složitý kombinatorický problém na lineární program. Proces ukládání přerušovaného stavu se nazývá memoizace.

Vytvořte tedy pole o velikosti 2²⁶, mezi 0 a 67,108,863, včetně. Každý index představuje stav bitové masky, jak bylo vysvětleno výše. Hodnota u každého indexu pole představuje to, co je známo o stavu. 0 znamená, že stav je nedotčený nebo nedosažitelný. 1 znamená, že stát našel způsob, jak dosáhnout možného dokonalého stavu pangramu. -1 znamená, že státu se nepodařilo najít způsob, jak dosáhnout konce.

Pseudokód níže:

Interlude: Složitost a praktická analýza za běhu

Existují 2²⁶ možných bitových masek pro sérii 26 bitů. Protože každý stav je kvůli memoizaci zpracován pouze jednou, je runtime tohoto algoritmu O (n 2 ^ d), kde d je velikost abecedy, 26. Proměnná n nestojí za počet slov, ale počet bitových masek. S 67 108 863 a zhruba 45 000 bitovými maskami to vyšlo na řádově 3 biliony, které můj MacBook Pro zvládl zhruba za 45 minut; vhodný pro jakýkoli moderní počítač. Za zmínku stojí také to, že zásobník rekurzivního volání se nikdy nedostane hlouběji než 26 (pravděpodobně se nedostane hlouběji než 15), takže je také velmi dobře zvládnutelný i z této dimenze.

Jedna výhoda přístupu bitové masky s pouze 2²⁶ stavy je, že všechny stavy lze uložit do paměti. Vzhledem k tomu, že na jeden stav existují pouze 3 hodnoty (-1, 0, 1), lze je uložit do jednoho bajtu. Při jediném bajtu na stát vycházejí stavy 2²⁶ na přibližně 67 megabajtů, což je opět velmi dobře zvládnutelné.

Se zvyšující se abecedou se však prostor pro vyhledávání exponenciálně zvětšuje, stejně jako doba běhu, což problém stát se velmi rychle neřešitelným. Krátká diskuse o tom, jak dosáhnout dokonalého pangramu pro větší abecedy, je v části „Jazyk s většími abecedami“ níže.

Dynamické vytváření přímého acyklického grafu (DAG)

Teď, když jsme mají vyplněné stavy bitové masky, čas na načtení řešení!

Chcete-li najít sady slov, které vytvořily sadu možných dokonalých pangramů, musíme odvodit, které mezilehlé stavy byly nedílnou součástí skládání konečných stavů Následná otázka pak zní, které další zprostředkující státy tyto zprostředkující stavy složily, a tak dále, dokud nezbývají jen státy, které se mapují přímo na slova. Tento proces se nazývá zpětné sledování.

Zachovat sledovat vztahy mezi státy, cílem je vytvořit Di rect Acyclical Graph (DAG), který udržuje, které zprostředkující stavy tvoří jakýkoli daný stav. DAG lze snadno procházet a načítat výstupy, zejména kvůli jejich necyklické povaze. Chcete-li sestrojit, začněte od možného dokonalého stavu pangramu a vytvořte směrovanou hranu (šipku), která ukazuje na zprostředkující stavy, které jej tvoří. Opakujte postup se zprostředkujícími státy a vytvoří se DAG. Nikdy nebudou žádné cykly, protože šipky vždy ukazují na stav s menší hodnotou.

Namísto opětovného budování vztahů, které byly objeveny v kroku vyhledávání, což zahrnuje opětovné procházení biliony možných kombinací stavů, je efektivnější vytvořit DAG během fáze dynamického programování. Pokud v rámci metody řešení může nově vytvořený stav dosáhnout možného dokonalého stavu pangramu, uložte namířenou hranu z nově vytvořeného stavu do původního stavu pouze v případě, že je původní stav menší než jeho doplněk (aby se snížila duplikace hran).

Vytiskněte plody své práce ve formě stromu!

Pravděpodobně nejjednodušší formát pro prohlížení výsledných sad slov je jejich vypsání jako stromů s kořenovým uzlem jako dokonalým stavem pangramu. Vzhledem k tomu, že DAG je konstruován shora, je nejlepším způsobem, jak to rozbalit, rekurzivní zápis každého stavu na disk v každém kroku namísto v paměti, protože strom je řádově větší než DAG.

Vylepšením této formy expanze je shrnutí stavů, které mají pouze jednu možnou kombinaci slov. Stav, který je maskou slov a žádné substáty, které ji tvoří, nelze triviálně shrnout. Stav lze shrnout, pokud lze shrnout jeho substráty a jeho kompozity, a všechny masky odvozené od něj a jeho podřízených nemají překrývající se bity / znaky. Tisk souhrnného DAG zlepšuje čitelnost výsledného výstupního stromu zkrácením a zjednodušením.

Protože sumarizace závisí pouze na menším ze dvou stavů, iterace maticí od počátečního stavu 0 nahoru a použití výše uvedených pravidel ke správě pravidla sumarizace umožňuje, aby bylo toto dokončeno v lineárním čase.

Vytvořené stromy Pangramu!

Nebojte se procházet dokonalými stromy pangramů, abyste zjistili, zda najdete zajímavé věty!

Existuje spousta možných dokonalých pangramů

Byl jsem překvapen množstvím dokonalých možných pangramů. Je jich hodně! Nejlepší strategie pro jejich sestavení nevyžaduje složitý procesor přirozeného jazyka. Jakmile jsou kandidátská slova označena jako způsobilá pro podstatné jméno nebo sloveso, balíček slov musí obsahovat alespoň jedno podstatné jméno, jedno sloveso a správný poměr podstatných jmen a sloves.

Kvalita dat je těžký problém

Sekce algoritmu trvala dva dny, ale problém s kvalitou dat trval dva týdny. Když jsem toto zjištění zmínil svému příteli, který je vedoucím technikem společnosti Google, nepřekvapilo ho to, když uvedl, že problémy s kvalitou dat jsou jedny z nejtěžších problémů ve strojírenství. Poučení.

Pravidla dokonalých pangramů

Existuje mnoho nuancí, co se kvalifikuje jako dokonalý pangram! Chtěl jsem prohledávat pangramy bez jakéhokoli citoslovce (např. Hm, pht), ale existují i další populární omezení, jako jsou zkratky, akronymy, kontrakce, inicialismy, izolovaná písmena, vlastní jména a římské číslice. Existují také slova, která jsou jmény písmen, jako Qoph, který jsem cítil podvádění.

S některými uvolněnými omezeními existuje spousta „dokonalých“ pangramů. Pravděpodobně v řádu bilionů . Existuje spousta zkratek a inicialismů.

Hvězdička

Hvězdička je na místě, protože definice všech dokonalých pangramů angličtiny není dobře definována. Existují nuance související s tím, co by mělo být povoleno v dokonalých pangramech angličtiny. Existuje také spousta sporů ohledně toho, zda jsou některá slova dokonce anglickými slovy. Vzhledem k těmto nuancím je opravdu těžké říci, že jsem našel všechny perfektní pangramy. Docela jistě mohu učinit dvě tvrzení:

1. Našel jsem metodiku pro vytváření všech dokonalých pangramů angličtiny a dalších jazyků s podobnými nebo menšími znakovými sadami.
2. I vyjmenovali všechny sady slov, která mohou vytvořit perfektní pangramy pomocí oficiálního turnajového slovníku Scrabble y, OWL3.

Neváhejte a vytvořte si své vlastní dokonalé pangramy pomocí technik popsaných v tomto příspěvku!

Závislost dokonalých pangramů na slovech velšských a arabských kořenů

Slova odvozená z velštiny a arabštiny byla skutečně důležitá pro existenci dokonalých anglických pangramů (pokud nejsou omezení dokonalého pangramu uvolněna). Při použití seznamu slov OWL3 s přísnými pravidly týkajícími se dokonalých pangramů neexistují žádné dokonalé pangramy, které by neobsahovaly slova „cwm (s)“ nebo „crwth (s)“, obě velšská slova. V mezinárodním Scrabble je arabské slovo „waqf (s)“ platné slovo, které může vytvářet dokonalé pangramy, aniž by se uchýlil k „cwm (s)“ nebo „crwth (s)“.

Účinnost pracovního proudu

Bylo důležité zefektivnit paralelizaci úkolů během tohoto projektu. Úplný běh trvá 25 minut pro slovník Unix a téměř hodinu pro opravdu velké slovníky. Měl jsem nějaké počáteční potíže s přepínáním kontextu na 30minutové okno, ale zlepšil jsem se tím, jak jsem zlepšoval svoji produktivitu.

Rozšíření / Zobecnění – Anagram Finder

Perfektní pangram vyhledávání je také ekvivalentní vyhledávači anagramů pro řetězec „abcdefghijklmnopqrstuvwxyz“. Co kdybyste chtěli vytvořit obecný vyhledávač anagramů?

Stejnou techniku lze použít, pokud jsou pro kontrolu stavu reprezentována a pravidla správy platnost kombinace slov se aktualizuje. Místo toho, aby byly stavy spravovány jako celé číslo, bylo by jednodušší sledovat stav jako mapu příslušných znaků. Ověření platnosti kombinací znamená, že kombinace dvou map nepřekročí počet požadovaných znaků anagramu pro každé písmeno. Jen se ujistěte, že je stavový prostor spojitelný; s příliš velkým počtem písmen může být vyhledávací prostor za okamžik opravdu velký. Máte také povoleno opakovat slova? Ujistěte se, že definujete tato pravidla uvnitř vaše dynamické programování řešení.

Jazyky s většími abecedami

Tento přístup a řešení jsou lineární ve velikosti množiny slov, ale exponenciální ve velikosti abecedy. Tento přístup nemusí fungovat s větší znakovou sadou, řekněme moderní japonštinou, která má 46 slabik. 2 je 70 368 744 177 664; více než milionkrát větší než anglický vyhledávací prostor 2²⁶ = 67 108 864.

Není zcela jasné, zda by tento přístup fungoval nebo ne pro japonštinu. Pokud má japonský jazyk dostatečně nízkou entropii, což je možné, byl by tento přístup životaschopný. Namísto inicializace pole o velikosti 2⁴⁶ budou státy sledovány na mapě. Dále lze využít strukturu japonštiny; například kana を (wo) se téměř výlučně používá jako post poziční příčestí a lze jej z vyhledávání vyloučit, čímž se zmenší prostor pro vyhledávání.

Kambodžský jazyk Khmer má největší abecedu se 74. Dalším možným dalším krokem je prozkoumat řešení, která jsou subexponenciální ve velikosti abecedy.

Inspirace

Byl jsem inspirován pokrokem Aubrey De Grey při hledání chromatického čísla roviny, která má být přinejmenším 5. Jedná se o významný pokrok, kterého bylo dosaženo základními výpočetními metodami.

Není nutné říkat, že nalezení dokonalých pangramů neobstojí při zlepšování spodní hranice chromatického čísla roviny.

Tím se domnívám, že existuje spousta problémů s nízkým zaváděním ovoce, které mají jednoduché výpočetní metody k řešení problému, který je ručně neřešitelný. Vyzývám vás, abyste našli a vyřešili některé z těchto problémů. Pokud něco najdete, dejte mi vědět!

Děkuji

Jsem vděčný za své velmi vynikající přátele, kteří mi pomohli korekturami a rušením se mnou, zejména Annou Zeng, Catherine Gao, Danny Wasserman, George Washington a Nick Wu!