Eksperimenter med ord og reducering af kompleksitet
Krav: Maven & JDK 1.6
java -jar wordsquare-20130108.jar
Man vælger en ordlængde, f.eks. 5 bogstaver, og danner et kvadrat ved at skrive 5 af disse ord under hinanden. De ord der dannes af både de vandrette rækker og de lodrette søjler af bogstaver skal eksistere i ordbogen. Et ordkvadrat er f.eks.
adict tenes opdra moser stuts
Man kan stille flere krav, som f.eks. at de to skrå rækker af bogstaver, læst fra venstre mod højre, skal være korrekte ord. I kvadratet ovenfor er det aedes og sodet. Et større ordkvadrat kan f.eks. være denne på 8x8 bogstaver:
abbedier brunalge buketten eneboers datoerne ilterhed egernene rensedes
Selvom det er et større kvadrat, er det ikke nær så elegant som det på 5x5 bogstaver. Dels danner diagonalerne ikke korrekte ord og dels er det præcis de samme ord der findes i de vandrette og lodrette rækker.
Når beregninger tager for lang tid, er der forskellige muligheder. To af disse er at foredre algoritmen og at øge hastigheden for afviklingen af algoritmen. I dette tilfælde hjælper det ikke rigtigt at øge hastigheden. Selv hvis man brugte en maskine der var en milliard gange hurtigere end en 2012-model, ville Solen stadig nå at brænde ud. Så der er brug for at finde ordkvadrater på en smartere måde end bare at prøve alle kombinationer.
På det sproglige niveau er det på linje med at løse rebusser. Man har søgt efter ordkvadrater i årtusinder på forskellige sprog, men jeg har ikke kunnet finde meget om det på dansk og slet ingen af de større løsninger. Det skal der rettes op på!
Jeg synes både det er spændende at finde på bedre algoritmer og at optimere hastigheden af disse, dvs. forbedre implementationen. Jeg vil prøve at skelne mellem de to dele når jeg beskriver de forskellige ideer jeg afprøver. Der er selvfølgelig også selve de fundne ordkvadrater - jeg håber at kunne finde nogen pæne af slagsen på 8x8, 9x9 eller måske 10x10 bogstaver. På denne side vil jeg dokumentere de ting jeg prøver undervejs.
Allerhelst ville jeg gerne bruge ordbogen fra Dansk Sprognævn og har kontaktet dem for at høre om de vil sende mig en fil med ordene. Indtil der kommer nyt derfra benytter jeg ordbogen fra da.speling.org, der efter en oprydning (ingen egennavne, ingen bindestreger, ingen forkortelser, ingen cifre) indeholder 600.000 ord af forskellig længde.
To indledende teknikker bragte processeringstiden for et 6x6 ordkvadrat med en ordbog på 2000 ord ned fra anslået 20.000 år til 6-8 minutter. Interesserede kan hente SquareTest.java.
Hvis man forsøger at bygge et 5x5 ordkvadrat op hvor første ord er abbed og næste ord er abers vil det foreløbige ordkvadrat se således ud:
abbed abers
Løber man igennem de lodrette søjler, altså aa, bb, be, er & ds og kontrollerer i ordbogen om der eksisterer ord der starter med disse bogstavkombinationer, vil man få at vide at der ikke eksisterer ord der starter med bb. Altså er der ingen grund til at bygge videre på kvadratet og man kan prøve med ordet efter abers.
Ved at konstruere et hash-sæt for alle længder af ordbegyndelser, blev opslag efter ordbegyndelser hurtigere end f.eks. binær søgning (det var i hvert fald teorien).
Selvom alle 8x8 ordkvadrater med en ordbog på 4200 ord kunne findes på ca. 10 minutter, gik det helt i stå med en ordbog der var 10 gange større. Den nåede ikke engang em promille gennem opgaven i løbet af et døgn på en god computer.
To nye teknikker bragte processeringstiden for et 6x6 ordkvadrat med en ordbog på 2000 ord ned fra de forgående 6-8 minutter til 5-6 sekunder. Interesserede kan hente wordsquare-20121128.zip (kræver Java og er lettest at bygge med Maven).
Ved skiftevis at indsætte et vandret og et lodret ord behøver man kun afprøve ordkandidater med det givne præfix der dannes. Derved reduceres mængden af ordkandidater væsentligt. Der blev anvendt sorterede lister og binær søgning til (rimelig) hurtigt opslag og meget hurtig iterering af ord med givne præfix. For et ordkvadrat på 3x3 bogstaver kunne et succesfuldt forløb være som følger (hvor punktum angiver at der ikke er noget bogstav).
Skridt 0: Ordkvadratet er blankt.
... ... ...
Skridt 1: Der vælges et vilkårligt ord fra ordbogen, som indsættes i første række.
hun ... ...
Skridt 2: Der kontrolleres at der eksisterer ord der starter med henholdsvis h, u og n (teknik 1). Dernæst reduceres mængden af mulige kandidater til de ord der starter med h og dette indsættes lodret i første søjle.
hun a.. l..
Skridt 3: Der kontrolleres at der eksisterer ord der starter med henholdsvis a og l. Dernæst reduceres mængden af mulige kandidater til de ord der starter med a. Et af disse ord indsættes i anden række
hun ara l..
Skridt 4: Der kontrolleres at der eksisterer ord der starter med henholdsvis ur og na. Dernæst reduceres mængden af mulige kandidater til de ord der starter med ur. Et af disse indsættes i anden søjle.
hun ara le.
Skridt 5: Der kontrolleres at der eksisterer ord der starter med le. Dernæst reduceres mængden af mulige kandidater til de ord der starter med le. Et af disse indsættes i tredje række.
hun ara let
Skridt 5: Et fuldt ordkvadrat blev fundet. Såfremt diagonaler er et krav, kontrolleres disse (diagonalerne er ikke gyldige i dette eksempel).
Såfremt der med teknik 1 findes en ugyldig ordstart, kan alle ord med denne ordstart ignoreres. I ordkvadratet nedenfor er onkel kandidat, men forkastes fordi ingen ord starter med rk. Det betyder at samtlige ord der starter med onk kan ignoreres.
kerte onkel n.... e.... r....
Selvom hastigheden blev væsentligt forbedret, var processeringstiden stadig for høj. Ved en søgning efter ordkvadrater på 8x8 fra en ordliste på 44.000 ord kom en moderne maskine kun 1-2 promille gennem opgaven på et døgn.
Når 1-2 promille af opgaven kan løses på et døgn, er det værd at prøve om implementationen kan forbedres så hele opgaven kan løses på et par uger eller lignende. Det kræver at programmets hastighed forbedres med en faktor 50. Det er ikke helt urealistisk, men ret svært eftersom der allerede benyttes temmelig hurtige datastrukturer.
De sæt der benyttes til præfixopslag giver svar i praksis i noget nær konstant tid. Men når der jages rå hastighed er det interessant at se på hvad den tid er. Når en nydannet ord eller ordbegyndelse skal verificeres, skal det først udregnes en hashværdi. Det gøres ved at løbe gennem alle bogstaverne og opdatere værdien undervejs. Dernæst laves et direkte opslag i et array og såfremt der er flere ord med samme hash, løbes disse igennem og sammenlignes.
Der er flere problemer med sæt til opslag: Det ord der skal slås op bliver gennemløbet mindst én og muligvis to gange, der skal muligvis løbes gennem en lille liste af ord med samme hash og - her kommer det kritiske - hele strukturen med forskellige sæt til hver præfixlængde fylder så meget at den ikke kan caches fuld ud i level 2 cache på en 2012-maskine.
En trie har den interessante egenskab at ordet gennemgås bogstav for bogstav. Gennemgangen afbrydes så snart et præfix af ordet ikke er i ordbogen og såfremt gennemgangen ikke afbrydes, er ordet i ordbogen. Der er altså færre operationer end med et sæt og samme struktur kan bruges til alle længder af præfix. Som udgangspunkt fylder trier en hel del i hukommelsen så den del skal der gøres noget ved. Målet er at få en ordbog af rimelig størrelse til at kunne ligge i level 2 cache på en moderne maskine.
Den komprimerede Trie begynder at ligne noget. Der kan laves opslag på ord, men gennemløb af ordbogen er ikke på plads endnu. En ordbog på 44.000 ord á 8 tegn fylder 820KB, altså ca. 2½ gange den rå størrelse. Jeg havde nok håbet på at den ville fylde mindre, men den kan sagtens ligge i cache på en moderne maskine.
Kollegaen Thomas Egense gjorde opmærksom på at alle løsninger kan transponeres så rækker bliver til søjler og omvendt. Det betyder at det kun er nødvendigt at gennemsøge halvdelen af alle muligt kombinationer for at finde alle løsninger. Det kan f.eks. gøres ved kun at afprøve ord i første søjle fra teknik 3 der er de samme eller kommer efter ordet i første række. Det skulle meget gerne fordoble hastigheden og gør at der "kun" er en faktor 25 der skal hentes ved teknik 5, for at få processeringstiden ned i et realistisk leje.
En Trie er en graf hvor øverste knude indeholder en liste med alle begyndelsesbogstaver. Hvert bogstav peger på en ny knude med en liste med alle de mulige bogstaver på position 2 efter det første bogstav og så fremdeles. Den kompakte Trie, der anvendes her, holder styr på bogstaverne ved at have én bit for hvert muligt bogstav: Hvis den komplette mængde af unikke bogstaver i korpus er c, d, e, k, r, m, o &z, vil en liste med bogstaverne e, r & m kunne udtrykkes som 00101100, hvilket kun fylder én byte.
Når ordbogen gennemløbes efter kandidater skal bitlisten for bogstaver i knuderne gennemløbes. Ved at sortere tegnene efter antal forekomster og ved at holde styr på længden af listen af tegn, vil det for de fleste knuder betyde at kun en lille del af listen skal gennemløbes.
En førsteudgave af den komprimerede Trie er implementeret. Hele strukturen gemmes i en long[] og opslag håndteres med bitpilleri. Den kan givetvis optimeres yderligere (kvalificeret gæt: Faktor 2-5). Den har følgende interessante egenskaber:
Dette leder på elegant vis hen til:
I nedenstående benyttes eksempelordbogen alt, art, asa, ash, agt, hat, sky, sya, syl & syr.
Skridt 0: Ordkvadratet er blankt.
... ... ...
Skridt 1: Et vilkårligt ord fra ordbogen indsættes.
asa ... ...
Skridt 2: De næste gyldige tegn for ordbegyndelserne a, s & a udtrækkes. De er henholdsvis [lrsg], [yk] & [lrsg]. Gyldige kandidater for række 2 er derfor alle ord der opfylder [lrsg[yk][lrsg], hvilket er sya, syl & syr. Det tegnafgrænsede ordgennemløb fra teknik 8 benyttes til at udtrække dem fra ordbogen. Et af ordene indsættes i kvadratet.
asa sya ...
Skridt 3: De næste gyldige tegn for ordbegyndelserne as, sy & aa udtrækkes. De er henholdsvis [ah], [al] & []. Eftersom der ikke er nogen gyldige tegn på plads 3, opgives kandidaten sya og der forsøges med næste ordkandidat fra skridt 2.
asa syl ...
Skridt 4: De næste gyldige tegn for ordbegyndelserne as, sy & al udtrækkes. De er henholdsvis [ah], [al] & [t]. Gyldige kandidater for række 3 er derfor alt & hat. Et af disse indsættes i kvadratet.
asa syl hat
Skridt 5: Ordkvadratet er udfyldt. Eftersom der kun er indsat ord der garanterer konsistens, er der ikke behov for kontrollerende opslag. Resultatet registreres og næste ord fra skridt 4 indsættes.
Den 1. december var målet at øge hastigheden 50 gange. Kombinationen af teknik 5, 7, 8 og 9 har sænket processeringstiden for et 15x15 ordkvadrat med 35.000 ordkandidater fra 2 timer og 32 minutter til 30 sekunder. Det er en faktor 300, så målet er klart nået og bringer den forventede processeringstid for det hårde 9x9 ordkvadrat ned fra 1-2 år til 2-3 dage.
Der er nu stadig lidt at arbejde med: Teknik 6 er ikke implementeret da det ikke er trivielt at få den til at fungere sammen med teknik 9. Det betyder at der stadig findes dobbelt så mange ordkvadrater som nødvendigt, så der er en oplagt optimering at gå i gang med.
Den binære Triestruktur har en hel del redundans i form af slutkknuder med kun ét tegn, så der burde størrelsen kunne bringes ned til det halve eller bedre. Mindre struktur = større sandsynlighed for at det hele ligger i level 2/3 cache på processoren = højere hastighed.
Lidt spredte puslerier med at optimere ved at genbruge objekter gav på skuffende vis næsten ingen hastighedsforbedring. Til gengæld er den nuværende hastighed god nok til at der kan laves komplette afsøgninger for alle størrelser ordkvadrater med den nuværende ordbog. Der ventes stadig på ordbogen fra Dansk Sprognævn (det ser ud til at falde på plads, så der kan testes med 2001-udgaven), men indtil da forsøges der med listen fra da.speling.org. Der var desværre ingen 9x9 ordkvadrat (54876 ordkandidater, 32 timers processeringstid) så chancen for et 10x10 ordkvadrat (62253 ordkandidater, udtømmende søgning forventes færdig 2012-12-16) er meget ringe. Der er til gengæld masser af 8x8 ordkvadrater (43898 ordkandidater, udtømmende søgning forventes færdig senest 2012-12-25), så med lidt held er der også nogen pæne imellem.
Skulle nogen have lyst til at forsøge selv, kan programmet hentes i form af wordsquare-20121216.zip (Java & Maven).
Med en forventet maksimal processeringstid for 8x8 ordkvadrater på 10 dage er min motivation for yderligere hastighedsoptimeringer faldende. Det kan være jeg pusler lidt videre med den del på et tidspunkt, men mere aktuelt har jeg fået øje på Form Records, der indeholder rekorder for en masse andre former end kvadrater. Selvom det nuværende program er lavet til kvadrater, burde det være overskueligt at tilpasse det til at understøtte vilkårlige former, så længe reglerne er at de gyldige ord blot behøver at være alle vandrette og lodrette ord. På sigt kunne man muligvis indføre understøttelse for andre regler, så ting som skrå ord eller bi-grams kunne håndteres, men det ligner en større opgave.
Næste udvidelse må derfor være at gøre det nemt at definere og afsøge andre former. Jeg forestiller mig at man laver et simpelt bitmap i form af en tekstfil, f.eks.
..***.. .*****. ******* ******* ******* .*****. ..***..
hvor programmet vil indsætte ord på de definerede felter og sikre at alle vandrette og lodrette ord er gyldige. En løsning fra Newrow, 2001 via Puzzlers.org på ovenstående er
OPA SPICE SEAPORT ALLELIC CLOTHES SITUS DEA
Det ser ud til at der kom styr på rektangler og pyramider, som f.eks.
selskabstømmersag
mineralogiernes
torarullernes
geleddernes
tindernes
edernes
ernes
ses
s
Jeg valgte at tillade alle enkeltbogstaver i spidsen. Der er for få løsninger hvis man skal holde sig til i, å & ø og det bliver for arbitrært hvis der kommer bogstaver som c og m med (lysets hastighed og meter), men ikke f.eks. b. Teoretisk burde programmet nu understøtte alle former, som beskrevet tidligere, men det er ikke testet endnu og jeg har ikke lavet en parser til brugerdefinerede former.
Og klokken blev henad midnat... Det virker glimrende med vilkårlige former, her er f.eks. et s:
essenser
definitionerne
parvise eis
isings
revenes
kriderpapirers
sensibilitetens
rebslagerier
egnene
a snæres
karakterbristers
bådehuses
Det der mangler er en indpakning, så de brugerdefinerede former kan angives fra kommandolinjen. Det der også mangler er en afrapportering. Dansk Sprognævn har meget venligt stillet ordene fra Retsskrivningsordbogen 2001 til rådighed til dette projekt (jeg må desværre ikke viderelevere ordlisten) og jeg har kørt alle de mulige størrelser ordkvadrater igennem. Jeg laver en liste med resultaterne senere, men kan med det samme sige at der desværre ikke var nogen af størrelse 9x9 eller derover. Der var 2145 8x8 ordkvadrater, men de var alle spejlede så de samme ord gik igen i søjlerne og rækkerne.
Så kom brugerdefinerede former ordentligt på plads. Der skal lige lidt finpudsning til før der er et reelt release, men jeg havde lovet en rapport over ordkvadrater ud fra Retsskrivningsordbogen 2001, så den gives hermed: I nedenstående tabel er "Gyldige" samtlige ordkvadrater, "Unikke" er dem hvor samme ord ikke optræder flere gange og "Diagonal" er dem hvor mindst én diagonal har et korrekt ord. Interesserede kan hente alle gyldige 8x8 (20 KB)
| Sider | Ord | Tid | Gyldige | Unikke | Diagonal | Unikke+diagonal |
|---|---|---|---|---|---|---|
| 2x2 | 174 | 224 ms | 4.911 | 3.663 | 1.171 | 841 |
| 3x3 | 1.089 | 11 sek | 739.139 | 506.875 | 61.813 | 43.273 |
| 4x4 | 3.373 | 8 min | 41.896.336 | 32.994.946 | 2.462.345 | 1.978.007 |
| 5x5 | 7.835 | 49 min | 145.421.782 | 104.178.728 | 3.626.620 | 2.761.695 |
| 6x6 | 15.830 | 3 timer | 40.348.491 | 19.335.652 | 438.959 | 273.244 |
| 7x7 | 24.644 | 7 timer | 361.236 | 14.140 | 48 | 6 |
| 8x8 | 33.933 | 8 timer | 2.145 | 0 | 0 | 0 |
Vigtigt: Dansk Sprognævn angiver at endelserne på ordene i den fil de har udleveret er delvist autogenererede og dermed ikke autoritative. Ovenstående er dermed ikke garanteret at være 100% korrekt. Den nye udgave af ordbogen skulle være korrekt og jeg laver gerne afsøgning på den, men Dansk Sprognævn offentliggør den først i starten af 2013 og de vil have penge for den, så jeg venter lige og ser hvad det helt konkret betyder.
De 6 ordkvadrater af størrelse 7x7, som både bestod af unikke ord og som havde mindst én diagonal med gyldigt ord, kan transponeres (søjlerne og rækkerne ombyttes). Det kan alle ordkvadrater. Det betyder at der reelt kun er 3 pæne løsninger i størrelsen 7x7. Disse løsninger er som følger:
opkomst provoer poderne everten fonders rederne anelses
skifers toneren ordrige lagenes plyndre rederen ertsers
skifere toneren ordrige lagener plyndre rederen ertsers
En evert er et lille sejlskib, trense er en form for snor, fer er en del af et bræt der kan sættes sammen med andre brædder i deres not og erts er en geologisk dannelse, hvis nogen skulle undre sig.
Lidt løs eksperimentering med forskellige former fra The National Puzzler's League Form Records afslørede en svaghed ved programmet: Princippet med kun at iterere over mulige ord virker skidt, hvis der ikke er nogen bogstaver ovenfor. Det kan illustreres med en pyramide:
Skridt 0: Pyramiden er blank.
* *** *****
Skridt 1: Første række har kun ét tegn, så et vilkårligt af slagsen indsættes.
a *** *****
Skridt 2: Tegnafgrænsning for række 2 beregnes ud fra tegnene i række 1. Eftersom der kun er tegnet a, er det kun pladsen umiddelbart under a, der kan afgrænses (symboliseret med !). Tegnene til venstre og højre for dette kan være hvadsomhelst (symboliseret med ?). Dette resulterer i mange ordkandidater.
a ?!? *****
Skridt 2: En af de mange ordkandidater vælges og indsættes i række 2.
a abc *****
Skridt 3: Ækvivalent med skridt 2 kommer der igen 2 jokere i tegnafgrænsningen. Når listen af ordkandidater itereres, vil Trien internt gennemløbe samtlige mulige tegn på plads 1 i ordet (da det er en joker) for først derefter af lave reel afgrænsning. Dette er tungt arbejde. Jokere er onde!
a abc ?!!!?
Hvis pyramiden fra ovenstående eksempel står på hovedet, er der ingen jokere. Et forløb kunne være
***** *** *
abers !!! *
abers ise !
abers ise t
Alle ordgennemløb vil være "perfekte", forstået på den måde at Trie iteratoren kan afgrænse ordene ét tegn af gangen, i stedet for at skulle kassere en masse blindgyder.
Det er nemt at beregne hvorvidt et top-bund- eller et bund-top-gennemløb vil være det mest effektive. Foretages et bund-top-gennemløb skal man dog være opmærksom på opslagene i ordbogen vil være fra slutningen af ordet (postfix) i stedet for starten (præfix). Det snedige og programmeringsarbejdebesparende trick er at spejle formen vandret og lodret, samt vende alle ordene i ordbogen om. Når resultaterne skal udskrives skal de også spejles vandret og lodret, men ellers skal der ikke ændres noget som helst i implementationen.
Den optimale gennemløbsretning var et fint trick, specielt fordi det ikke var besværligt at implementere. Desværre hjælper det ikke på former der er tunge i midten, som f.eks.
*
***
********
***
*
Her er top-bund præcis lige så tung som bund-top. En optimal gennemgang ville være
*
!!!
abemaden
***
*
!
abe
abemaden
***
*
a
abe
abemaden
!!!
*
a
abe
abemaden
bad
!
a
abe
abemaden
bad
g
Problemet er naturligvis at der skal afgrænses efter både præ- og post-fix. Det kunne man håndtere med to ordbøger, men hvad så med en form som f.eks. en ruder?
* *** ***** *** *
Igen er det muligt at foretage et ideelt gennemløb, altså et gennemløb uden jokere.
* !!! atlas *** *
* erg atlas !!! *
! erg atlas bæk *
e erg atlas bæk !
e erg atlas bæk g
Her er det ikke bare præ- og post-fix der skal afgrænses på, men også forskellige infix. Det betyder ret mange ordbøger, for slet ikke at tale om udfordringen ved at beregne det optimale gennemløb for en vilkårlig form. Der er nok af arbejde at gå i gang med.
Teknik 10 er implementeret og programmet er blevet pudset af så det burde kunne bruges af andre end undertegnede. Det kan hentes fra download-boksen i toppen af denne side. Jeg har andre projekter, så jeg tror ikke jeg pusler videre med infix-opslag lige med det samme.
Et par indledende forsøg på at slå rekorder fra siden The National Puzzler's League Form Records virkede lovende for former som halfsquares, lattices og pyramids. Til gengæld var det meget tungt med octagons, pentagons og diamonds, hvor infix-opslag virkelig ville hjælpe.
Double right windmill 13
eeriest
clammer
palmeri
hilario
odinian
ninette
palingenesies
agendas
vangeli
ephebes
teamers
tiralee
actress