Az angol összes * tökéletes pangramja

An Az angol pangram egy olyan mondat, amely az angol ábécé mind a 26 betűjét tartalmazza. A legismertebb angol pangram valószínűleg “A gyors barna róka átugrik a lusta kutyán.” A kedvenc pangramom “Elképesztően kevés diszkó nyújt zenegépet.”

A tökéletes pangram egy pangram, ahol az egyes betűk csak egyszer jelenik meg. Találtam néhány forrást az interneten, amelyek felsorolják az ismert tökéletes pangramokat. Úgy tűnik, senki sem próbálta sikeresen előállítani mindet kimerítően, ezért szórakoztató kihívásnak vettem fel. Így találtam meg az összes angol tökéletes pangramot. A csillagot később elmagyarázom.

• Crwth vox zaps qi gym fjeld emeletes. (A kelta hegedű hangja megüt egy keleti szellemi erőkre koncentráló fitneszközpontot, amely Skandinávia kopár fennsíkján található.) Ez mind Scrabble jogi szó!
• Squdgy kilp job zarf nth cwm vex. (A rosszul formált moszat egy díszes pohármelegítőt vásárol, amelyet a völgy vagy a hegyoldal tetején lévő sok félig nyitott meredek oldalú üreg egyike irritált.)
• Jock nimfák waqf drug vex blitz. (A jótékonysági adomány megrészegítette az erdei szellemeket, akik elkeserítették a támadásba keveredett sportolót.)
• Hm, fjordkering, cinq busk, pyx veg. (Lássuk, egy hosszú, keskeny mély bemenet táncol, az öt a kockán muzsikál az utcán, és a kis kerek tartály betegeknek és képteleneknek pihen.) Scrabble is legális, de van közbevetése (Hm).

Sajnos ezek a legolvasóbb mondatok közül néhányat találtam *. A Scrabble Hivatalos Verseny- és Klubszavas 3. listájából (OWL3) generált tökéletes pangramok közbeiktatás nélkül tartalmazzák a cwm vagy a crwth szót is. A Waqf Észak-Amerikán kívül legális Scrabble verseny.

Hogyan találhatjuk meg az összes tökéletes pangramot?

A tökéletes pangramok megtalálásának módja két lépésből áll. Az első az, hogy megtalálja az összes olyan szócsoportot, amely egyszer tartalmazza az angol ábécé minden betűjét. A második lépés annak megnézése, hogy ezek közül melyik sorozható át érvényes angol mondatokká.

1. Lépés: Szóhalmazok megkeresése a tökéletes pangram

A szavak halmazának megkezdéséhez Az angol ábécé átfogásához angol szavak listája szükséges. A szavak jó minőségű listájának megtalálása és fenntartása sokkal nehezebb volt, mint amire számítottam. Eredetileg azt gondoltam, hogy ez a projekt két napot vesz igénybe, de végül két hétig tartott ez az adatminőségi probléma.

A Unix szótárral kezdtem, amely egy szabadon elérhető angol szavak listája. amely szinte az összes Unix-alapú operációs rendszerrel együtt jár. Azonnal észrevettem, hogy a listának minőségi problémái vannak. Először is, az ábécé minden betűjét szónak tekintették a Unix szótárban, és sok olyan nem szót tartalmazott, mint a “vejoz”. Ez megmutatta, hogy feketelistára van szükség az online szavak listájának kezeléséhez. Másodszor, a A Unix szótárból hiányoztak a többes számok a szavakhoz, ezért a szótár tartalmazta volna a “narancs” szót, de nem a “narancs” szót. A szavak listája annyira korlátozó, valójában, hogy egyetlen korábban ismert tökéletes pangram sem tartalmazott csak szavakat a Unix szótárból. néhányat, például “squdgy kilp job zarf nth cwm vex”.

Ezután az internet felé fordultam, hogy nagyobb szavakat találjak. Nagyon nagy szóhalmazokat találtam, amelyek hatalmasak voltak, de amikor elkezdtem tökéletes pangramokat ásni ezekből a listákból, azt tapasztaltam, hogy túlságosan szennyezettek alacsony minőségű szavakkal, amelyek nem érvényesek angol szavakkal. Még a sokféle ismétlés után sem sikerült lerövidítenem a listát, hogy ésszerű vagy kezelhető pangramokat találjak. Megpróbáltam megtisztítani egy bizonyos hosszúságú szavak engedélyezési listájának létrehozásával, de a lista továbbra is rendkívül alacsony minőségű volt.

Végül sok ismétlés után 15 dollárt fizettem az észak-amerikai próba tagság megvásárlásáért. Scrabble® Players Association, amely hozzáférést biztosított a saját és szerzői jogokkal védett OWL3-hoz, ami némi vita forrása. Akkor is hozzá kellett adnom néhány ismert szót angolul, például az „1” és az „I” egybetűs szavakat.

Megfelelő szavak listájával felfegyverkezve végrehajtottam egy algoritmust a a lista összes szócsoportja, amelyek mindegyike tartalmazza az angol ábécé minden betűjét. Az algoritmust az alábbi “Az algoritmus” részben részletesen ismertetem.

2. Lépés: Angol mondatok kialakítása zacskóból

Adott szavak halmaza, hogy kitaláljuk, hogy érvényes angol mondat lehetséges, az összes megadott szóval nem triviális probléma, de könnyebb, mint a legtöbb más természetes nyelv feldolgozási (NLP) probléma.

Hasznos heurisztikák léteznek az alkalmatlan mondatok kigyomlálásához; A heurisztika követése után a fennmaradó szavakból érvényes angol mondatokat tudtam kialakítani. A mondatok gyakran értelmetlenek voltak, de mégis érvényesek. Itt vannak az általam használt heurisztikák:

1. Legalább egy igének kell lennie.
2. Csak egy főnév lehet több, mint ahány ige, hacsak nincs kötőszó ill. elöljárószó, mindkettő nagyon ritka.
3. Ha vannak melléknevek, akkor főneveknek is kell lenniük.

A heurisztika részben az implicit lehetőség lehetősége miatt működik. a tantárgyak (sem tökéletesek, sem pangramok, de a „halk haladás és halk beszéd” kifejezés két igével és főnév nélküli mondattal rendelkezik, a „te” hallgatólagos alanyával).

Mivel a szavak tere A tökéletes pangramokban való részvétel kicsi, elég könnyű manuálisan megcímkézni az egyes szavakat a megfelelő beszédrészekkel, és megnézni, hogy a szavak megfelelnek-e ennek a három egyszerű heurisztikának. Ízlés kérdése, hogy tetszik-e az előállított mondatok minősége.

Az algoritmus

Ez a szakasz kissé technikai jellegű, de remélhetőleg mégis könnyen követhető. Nyugodtan ugorjon az “Eredmények & Tanulások” szakaszra.

Magas szintű stratégia

A cél az összes lehetséges szavak a megadott szavak listájából, amelyek “tökéletesen” átfogják az angol ábécét.

1. Tisztítsa meg a szavak listáját a keresési hely drasztikus csökkentése érdekében, pl. távolítsa el az ismétlődő betűket tartalmazó szavakat, például a “betűket”.
2. Használjon bitmaszkokat a szavak hatékony ábrázolásához és az eredeti szavakhoz való visszacsatoláshoz.
3. Keressen minden lehetséges állapotot, mindegyik egy lehetséges betűkombinációt képvisel, a bitmaszkok listájának ismételt ismétlésével. A teljesítmény dinamikus programozással drámai módon javul.
4. Rajzoljon nyilakat (irányított éleket) a tökéletes pangram állapotból, a végső állapotból, amelyben minden megtalálható az angol betűk az azt alkotó közbenső államokhoz. Tegye meg újra ezt a közreműködő államokkal egy olyan adatstruktúra létrehozása érdekében, amely képes rekonstruálni a lehetséges tökéletes pangram szavak halmazát. Ezt nevezzük visszalépésnek.
5. Output a felfedezett szavak halmaza, amelyek fákként tökéletes pangramok lehetnek.

A lista tisztítása, más néven kanonizálás

Az első lépés az eredeti szavak listájának tisztítása a keresési hely csökkentése és a kimenet minőségének javítása érdekében.

1. Csíkozzon az összes szóközt a szó köré és konvertálja csak kisbetűvé
2. Győződjön meg arról, hogy a szavak csak az angol ábécé betűit tartalmazzák; Egy egyszerű reguláris kifejezés szűrőt használtam: /^+$/
3. Szűrés bármely más listához, pl. feketelisták; ha egy szó szerepel a feketelistán, hagyja ki ezt a szót
4. Távolítsa el az összes szót ismételt betűkkel

Ez jelentősen lerövidítette a keresési teret, a 200 000 ~ 370 000 szavak listájáról sokkal kisebb 35 000 ~ 65 000 szó.

Bitmaszkok használata

A bites maszkok az állapotok egész számát reprezentálják. A bitmaszkoknak számos előnye van:

• A bitmaszkok jól képviselik ezt a problémát. A betűk sorrendje nem számít, így a szavak minden kombinációja 26 számjegyű 0 és 1 hosszúságú sorozatként ábrázolható, és mindegyik számjegy azt jelzi, hogy létezik-e betű a kombinációban. Például. ha a szavak halmaza tartalmazza az “e” betűt, akkor az ötödik számjegy 1, különben 0 lesz.
• A bitmaszkok hatékonyak: Mivel a keresési hely állandó, a bitmaszkok hatékony tárolást kínálnak, és Ezenkívül a bitenkénti műveletek gyorsak; annak teszteléséhez, hogy két bitmaszk kombinálható-e nagyobb bitmaszk készítéséhez, ellenőrizze, hogy a két álarc bitenkénti ÉS értéke egyenlő-e 0-val, mindkettő rendkívüli gyors műveletek.

Tehát változtasson minden szót egy bit maszkká, amelyet egész számként ábrázolhatunk. Például a “cab” szót leképezzük a 111-es bitmaszkra, amely a 7. tizedesjegy. A “be” szó 10010-re kerül leképezésre, ami a 18. tizedesjegy, és így tovább. A lehető legnagyobb bitmaszk az ábécé összes betűje, a lehetséges tökéletes pangram állapot, 1111111111111111111111111111, amely a 67.108.863, vagy a 2⁶⁶ -1 tizedesjegy. Ez jól illeszkedik egy szabványos aláírt 32 bites egész számba, amely a 2³¹-1-ig.

A bitmaszkok használata tovább tömöríti a teret, mivel az egyszavas anagrammák ugyanarra a bitmaszkra vannak leképezve. A “kemence” és a “link” a 10110100000000 maszkhoz tartozik, amely az 11520 tizedesjegy. Ez tovább csökkenti a 35 000 ~ 65 000 szó keresési terét 25 000 ~ 45 000 bites maszkokra.

Tartsa meg a bitmaszk leképezését azokhoz a szavakhoz, amelyekből származnak. Ez hasznos lesz, ha kiadja a szavakat.

A tökéletes pangram keresése dinamikus programozással

Az algoritmus magja meglehetősen egyszerű:

Egy lehetséges állapotot figyelembe véve (amely a meglévő szavak érvényes kombinációiból áll), próbálja ki az összes maszkot a kezdeti szavak listájából, hogy meggyőződjön arról, hogy lehetséges-e új érvényes állapotot létrehozni (ellenőrizve, hogy a az állapot és a maszk értéke 0, ami azt jelentené, hogy nincsenek átfedő betűk). Hozza létre az új állapotot a bitenkénti VAGY művelet segítségével, amely egyesíti az összes 1-et. Minden új felfedezett állapot után ismételje meg addig, amíg nem lesz több feltáratlan állapot. Ha ez a végére ér, ez azt jelenti, hogy az algoritmus megtalált legalább egy lehetséges tökéletes pangram szókészletet. Az első lehetséges állapot, amely felsorolja az összes lehetséges állapotot, az üres állapot vagy 0, ahol az ábécé betűi nem szerepelnek. Tehát kezdje ott, majd rekurzív módon fedezze fel, mely állapotok lehetségesek.

Az egyik hatalmas hatékonyságnövekedés az, ha észrevesszük, hogy az időszakos állapot elérésének számos módja van, és hogy az állammal kapcsolatos munka nem változik attól függően, hogy miként alakul elérte. Tehát ahelyett, hogy megismételné a munkát, amikor egy állapotot felülvizsgálnak, tárolja az egyes állapotok eredményét. Ezt a technikát dinamikus programozásnak hívják, és egy komplex kombinatorikus problémát lineáris programmá alakít. A szakaszos állapot tárolásának folyamatát memoizálásnak hívják.

Tehát hozzon létre egy 2²⁶ méretű tömböt, 0 és 67 108 863 között. Minden index egy bit maszk állapotot képvisel, amint azt korábban kifejtettük. A tömb egyes indexein levő érték az állapotról ismertet képviseli. A 0 azt jelenti, hogy az állapot érintetlen vagy elérhetetlen. Az 1. azt jelenti, hogy az állam megtalálta a módját a lehetséges tökéletes pangram állapot elérésére. -1 azt jelenti, hogy az állam nem talált módot a végére.

Az alábbi álkód:

közbeszólás: összetettség és gyakorlati futásidejű elemzés

Vannak 2²⁶ lehetséges bitmaszk 26 bit sorozat esetén. Mivel az egyes állapotokat a memoizálás miatt csak egyszer dolgozzuk fel, ezen algoritmus futási ideje O (n 2 ^ d), ahol d az ábécé mérete, 26. Az n változó nem a szavak számát jelenti, hanem a bit maszkok száma. 67 108 863 és nagyjából 45 000 bites maszkokkal ez 3 billió nagyságrendűre jön ki, amelyet a MacBook Pro-m nagyjából 45 perc alatt képes kezelni; minden modern számítógéphez kezelhető. Érdemes megjegyezni azt is, hogy a rekurzív hívásverem soha nem lesz mélyebb 26-nál (valószínűleg soha nem lesz mélyebb 15-nél), ezért ettől a dimenziótól is nagyon kezelhető.

A bitmaszk-megközelítés egyik előnye a csak 2²⁶ állapot, hogy az összes állapot tárolható a memóriában. Mivel állapotonként csak 3 érték van (-1, 0, 1), ez egyetlen bájtban tárolható. Állapotonként egyetlen bájtnál 2² állapot körülbelül 67 megabájtig terjed, ami ismét nagyon kezelhető.

Az ábécé növekedésével azonban a keresési terület exponenciálisan növekszik, és a futási idő is nő, ami a nagyon gyorsan megoldhatatlanná válik. Az alábbi “Nyelv w / nagyobb ábécékkel” részben röviden tárgyaljuk a nagyobb ábécék tökéletes pangramjának megközelítését.

Irányított aciklusos grafikon (DAG) dinamikus felépítése

Most, hogy kitöltötték a bitmaszkállapotokat, ideje a megoldás lekérésére!

Ahhoz, hogy megtalálja azokat a szavak halmazait, amelyek létrehozták a lehetséges tökéletes pangramok halmazát, le kell vonnunk, hogy mely közvetítő állapotok szervesek voltak a végállapotok összeállításában. . Ezután a következő kérdés az, hogy mely más közvetítő államok alkották ezeket a közvetítő állapotokat, és így tovább, amíg csak azok az állapotok maradnak, amelyek közvetlenül a szavakhoz társulnak. Ezt a folyamatot visszalépésnek nevezzük.

az államok közötti kapcsolatok nyomon követése, a cél egy Di létrehozása kijavított Acyclical Graph (DAG), amely fenntartja, hogy az adott állapotot melyik közvetítő állapot alkotja. A DAG-ok könnyen áthaladhatnak a kimenetek lekérése érdekében, különösen nem ciklikus jellegük miatt. A felépítéshez induljon ki a lehetséges tökéletes pangram állapotból, és hozzon létre egy irányított élt (nyíl), amely az azt alkotó köztes állapotokra mutat. Ismételje meg a folyamatot a közbenső állapotokkal, és ez DAG-t állít elő. Soha nem lesznek ciklusok, mert a nyilak mindig egy kisebb értékű állapotra mutatnak.

A keresési lépésben felfedezett kapcsolatok újjáépítése helyett, amely több ezer lehetséges állapotkombináció ismételt áthaladásával jár, hatékonyabb a DAG felépítése a dinamikus programozási szakaszban. A megoldási módszeren belül, ha egy újonnan felépített állapot eléri a lehetséges tökéletes pangram állapotot, akkor csak akkor tároljon irányított élt az újonnan felépített állapotból az eredeti állapotba, ha az eredeti állapot kisebb, mint a komplementere (az él megkettőzésének csökkentése érdekében). p>

Nyomtassa ki munkája gyümölcsét fa formában!

Valószínűleg a legegyszerűbb formátum az eredményül kapott szavak megtekintéséhez, ha fákként sorolja fel őket, és a gyökércsomópont a tökéletes pangram állapot. Tekintettel a felülről felépített DAG-ra, a kicsomagolás legjobb módja, ha ezt rekurzív módon végezzük, minden állapotot lemezre írva az egyes lépésekre a memória helyett, mivel a fa nagyságrenddel nagyobb, mint a DAG.

A terjeszkedés ezen formájának fejlesztése az olyan állapotok összefoglalása, amelyeknek csak egyetlen lehetséges szókombinációja van. Az az állapot, amely maszk a szavakhoz, és nincsenek olyan alállomások, amelyek ezeket alkotják, triviálisan összefoglalható. Egy állapot akkor foglalható össze, ha az alállomásai és összetettjei összefoglalhatók, és az összes önmagától és gyermekeitől származó maszk nem rendelkezik átfedő bitekkel / karakterekkel. Az összesített DAG nyomtatása javítja a kapott kimeneti fa olvashatóságát azáltal, hogy lerövidíti és leegyszerűsíti.

Mivel az összegzés csak a két állapot közül a kisebbiktől függ, a tömbön keresztüli iteráció a kezdeti 0 állapottól felfelé és A fenti szabályok segítségével az összesítési szabály kezelhetővé válik, hogy ezt lineáris időben teljesítsük.

Termelt Pangram-fák!

Nyugodtan haladjon át a tökéletes pangramfákon, hogy lássa, érdekes mondatokat találhat!

Sok lehetséges tökéletes pangram

Meglepett a tökéletes lehetséges pangramok száma. Van egy csomó! Az összeillesztés legjobb stratégiája nem igényel komplex természetes nyelvi processzort. Miután a jelölt szavakat megfelelő névnek vagy igének jelölték meg, a szavak csomagjának tartalmaznia kell legalább egy főnevet, egy igét, valamint a főnevek és igék megfelelő arányát.

Az adatminőség nehéz probléma

Az algoritmus szakasz két napig tartott, az adatminőségi probléma azonban két hétig tartott. Amikor megemlítettem ezt a megállapítást barátomnak, aki a Google vezető személyzeti mérnöke, nem lepődött meg, és megjegyezte, hogy az adatminőséggel kapcsolatos problémák a mérnöki feladatok közül a legnehezebbek. Tanulság.

A tökéletes tangram szabályai

Nagyon sok árnyalat van abban, hogy mi minősül tökéletes pangramnak! Szerettem volna mindenféle közbeiktatás nélkül átkutatni a pangramokat (pl. Hm, pht), de vannak más népszerű korlátozások is, például rövidítések, rövidítések, összehúzódások, inicializálások, elszigetelt betűk, tulajdonnevek és római számok. Vannak olyan szavak is, amelyek betűk nevei, például a Qoph, amelyet csalásnak éreztem.

E korlátok némelyikének enyhülésével sok „tökéletes” pangram van. Ez valószínűleg billió nagyságrendű. . Nagyon sok rövidítés és iniciálé létezik.

Asterisk

A csillag a helyén van, mert az angol tökéletes pangramok meghatározása nincs pontosan meghatározva. Vannak árnyalatok kapcsolódik ahhoz, amit meg kell engedni az angol tökéletes pangramokban. Sok vita van azzal kapcsolatban is, hogy egyes szavak akár angol szavak-e vagy sem. Tekintve ezeket az árnyalatokat, nagyon nehéz azt mondani, hogy megtaláltam az összes tökéletes pangramot. Két állítást meglehetősen magabiztosan állíthatok:

1. Találtam egy módszertant az angol és más nyelv összes tökéletes pangramjának előállításához hasonló vagy kisebb karakterkészlettel.
2. I felsorolták az összes olyan szócsoportot, amely a tökéletes Scrabble versenyszótár segítségével tökéletes pangramokat képezhet y, OWL3.

Kérjük, készítse el saját tökéletes pangramjait az ebben a bejegyzésben leírt technikákkal!

Tökéletes Pangrams függősége walesi és arab gyökerek szavaihoz

A walesi és arab eredetű szavak valóban fontosak voltak a tökéletes angol pangramok létezéséhez (hacsak a tökéletes pangram korlátai nem enyhültek). Az OWL3 szójegyzéket a tökéletes pangramokra vonatkozó szigorú szabályokkal használva nincsenek olyan tökéletes pangramok, amelyek ne tartalmazzák a „cwm (s)” vagy „crwth (s)” szavakat, mindkettő walesi szót. A nemzetközi Scrabble-ben az arab eredetű “waqf (s)” szó olyan érvényes szó, amely tökéletes pangramokat képes előállítani anélkül, hogy a “cwm (s)” vagy “crwth (s)” -et igénybe venné.

Munkafolyamat hatékonyság

Fontos volt, hogy hatékonyabbá váljon a feladatok párhuzamosítása a projekt során. A teljes futás 25 percet vesz igénybe a Unix szótár számára, és közel egy órát vesz igénybe az igazán nagy szótárak esetében. Kezdeti problémám volt a kontextusváltás egy 30 perces ablakra, de jobb lettem benne, amikor javítottam a termelékenységemen.

Bővítés / Általánosítás – Anagram Finder

A tökéletes pangram A keresés egyenértékű az “abcdefghijklmnopqrstuvwxyz” karakterlánc anagramma keresőjével is. Mi lenne, ha általános anagramma keresőt akarna létrehozni? A szóösszetétel érvényessége frissül. Ahelyett, hogy az állapotokat egész számként kezelnék, könnyebb lenne az állapotot a releváns karakterek térképeként követni. Ha megnézzük, hogy a kombinációk érvényesek-e, azt mondjuk, hogy két térkép kombinációja nem haladja meg a az anagram kívánt betűinek száma minden betűnél. Csak győződjön meg arról, hogy az állapottér kezelhető; túl sok betűvel a keresési hely nagyon nagy lehet. Egyszerre megengedett szavakat ismételni? Győződjön meg arról, hogy belül definiálta ezeket a szabályokat dinamikus programozása megoldás.

Nyelvek nagyobb ábécével

Ez a megközelítés és megoldás lineáris a szókészlet méretében, de exponenciális ábécé méretében. Ez a megközelítés nem biztos, hogy nagyobb karakterkészlettel működik, mondjuk a modern japán nyelvnek, amelynek 46 szótagja van. 2⁴⁶ értéke 70,368,744,177,664; több mint egymilliószor nagyobb, mint az angol keresési tér 2² 2 = 67,108,864.

Nem teljesen világos, hogy ez a megközelítés működne-e a japánok számára. Ha a japán nyelv kellően alacsony entrópiával rendelkezik, ez lehetséges, ez a megközelítés életképes lenne. A 2⁴⁶ méretű tömb inicializálása helyett az állapotokat egy térképen követik nyomon. Továbbá kihasználható a japán szerkezet; például a kana を (wo) szót szinte kizárólag posztpozicionális tagként használják, és kizárható a keresésből, csökkentve a keresési teret.

A khmer kambodzsai nyelvben a legnagyobb ábécé található, 74-tel. Egy másik lehetséges következő lépés az olyan megoldások feltárása, amelyek ábécé méretében szubexponenciálisak.

Inspiráció

Aubrey De Grey előrelépése inspirált engem abban, hogy megtalálja a sík kromatikus számát. legalább 5. Ez egy jelentős előrelépés, amelyet alapvető számítási módszerekkel értek el.

Mondanom sem kell, hogy a tökéletes pangramok megtalálása nem tart gyertyát a sík kromatikus számának alsó határának javításához.

Ez elhiteti velem, hogy sok olyan alacsonyan függő gyümölcsprobléma létezik, amelyek egyszerű számítási módszerekkel rendelkeznek egy manuálisan megoldhatatlan probléma megoldására. Felhívom Önt, hogy találjon meg és oldjon meg néhány ilyen problémát. Kérlek, tudasd velem, ha találsz valamit!

Köszönet

Nagyon hálás vagyok nagyon kiváló barátaimnak, akik segítettek a lektoráláson és a velem való elakadáson, különösen Anna Zengnél, Catherine-nél. Gao, Danny Wasserman, George Washington és Nick Wu!