« Skånsk bloggmiddag söndagen 9 oktober, 14.00 restaurang Aten, Malmö (OBS! Klockslag ändrat) | Main | Enkel textsummering (mestadels åt Thebe) »
september 21, 2005
Skapa enkla anagram
För några veckor sedan såg jag på en av de reklamfinansierade TV-kanalerna (ärligt talat har jag glömt vilken) det där bokstavsspelet som går ut på att man ska gissa vilket "förvanskat" ord (anagram) som står i rutan. Så kan man vinna en massa pengar om man gissar rätt och om man svarar på lite fler frågor och så.
Flera av de anagram som visades var enkla att lösa och jag misstänker att de är handskapade just för att inte vara så svåra. T.ex. stod det ungefär följande anagram:
vonellörftfaaetr
Hur skapa "enkla anagram"?
Hur som helst påbörjades funderingar på hur man automatiskt kan skapa enkla sådana anagram eller skapa en sorteringsmetod där man kan sortera genererade anagram efter hur enkla de är att lösa.
Not: "enkel att lösa" bygger på subjektiva grunder och detta är ingen vetenskapligt undersökning.
Generate Simple Anagram
Resultatet av detta funderande blev programmet Generate Simple Anagram som visar några olika metoder för att skapa eller sortera "enkla" anagram. Här nedan förklaras några delar av programmet.
n-step-metoden
En metod som jag tycker fungerar rätt bra är n-step-metoden som går ut på att man tar två bokstäver i ordet som ligger ganska nära varandra och låter dem byta plats; så fortsätter man med det nya angrammet och byter ut två andra bokstäver etc. n i n-step refererar till det maximala avstånd mellan bokstäverna man använder. Både position, avståndet och riktningen väljs slumpmässigt.
De par tre första genererade orden är troligen alldeles för enkla, men efter några körningar så kan det bli tillräckligt svårt att lösa så att det blir i alla fall någon minuts fundering; för den som inte känner till grundordet vill säga.
Två avstånds-metriker för sortering
För att testa min intuition kring n-step-metoden görs även jämförelse med andra typer av sorteringar av de ord som skapades:
* ordavstånd (edit distance)
* ngram-avstånd
Dessa metriker beskrivs mer nedan.
Som ytterligare en test slumpas det även ett gäng anagram (för närvarande 500 stycken) för att se hur bra dessa två avstånds-metriker sköter sig i detta sammanhang, nämligen hur lätt det är att identifiera anagrammets grundord. Tanken är att enklare anagram ska komma så tidigt som möjligt i listan, och svårare lite längre ned.
Min subjektiva åsikt är att ngram-avstånd ger rätt hyfsat resultat, i alla fall bättre än edit distance. (Sedan kan man alltid jämföra snabbheten/komplexiteten för respektive avståndsmetod men det är för tillfället en annan och möjligen senare fråga.,)
Exempel
Låt oss då ta ovanstående ord, som ju är novellförfattare, som exempel.
De första anagram som skapas (vid en slumpmässig n-stepkörning) är:
...
Första raden novellförftatare (10 <-> 11 : t <-> a edit dist: 2 ngram dist: 0.43) innebär fölljande:
* det skapade anagrammet är novellförftatare
* bokstäverna "t" och "a" har bytt plats med varandra och de var i respektive position 10 och 11 i ordet
* ordavståndet (edit distance) är 2 vilket innebär att det krävs två "redigeringar" för att transformera "novellförfattare" till "novellförftatare". Se vidare om ordavstånd i Ordavstånd (edit distances): Levenshtein och Hirschberg med lite extra finesser-
* ngram-avståndet visas sedan, här 0.43. Detta ngram-avstånd förklaras i nästa sektion.
ngram-avstånd
Ett ngram (n-gram) är en del av ett ord där
Grundtanken bakom ngram-avstånd är att man först skapar grundordets ngram (här för "novellförfattare") och jämför sedan de ngram som de genererade anagrammen har. De genererade ord som har mest gemensamma ngram med grundordet är alltså mest lika (har bäst ngram-avstånd). För att kunna göra jämförelser av ngram-avstånd mellan (anagram av) olika ord normaliseras det genom att man delar antalet gemensamma ngram med antalet möjliga ngram.
Subjektivt: Någonstans kring ngram-avståndet 0.5-0.6 och lägre värden blir det svårt att direkt se vilket grundordet anagrammet bygger på. Det beror även på sådana saker som längden på ordet, hur vanligt det är och om man känner till det.
(Tekniken bakom ngram-avstånd används bland annat för att automatiskt lista ut vilket språk en text är skriven på. Se vidare om detta i Automatisk identifikation av språk (språkidentifiering) och Bloggidentifiering (Blog Identification) där den senare beskriver språkidentifieringsalgoritmen mer.)
Övrigt i programmet
Programmet har även några andra finesser såsom:
* slumpa ett ord på svenska eller engelska Eftersom n-step-metoden börjar väldigt enkelt är det tillrådligt att bläddra ner lite på sidan och starta i slutet på listan. Det korrekta ordet ser man om man markerar området till höger om "Word" i Resultat-avsnittet (det är alltså dolt genom att har color="white").
* man kan ändra hur många ord som ska visas (Number to show)
* ändra maximalt avstånd mellan bokstäverna (Max steps)
Lek gärna med parametrarna och orden!
Slutord
Som en förberedelse till programskrivandet gjordes lite olika statistiska undersökningar och simuleringar med lite skoj saker som resultat, men dessa får anstå till en annan dag.
Se även
Två program som är lite av samma stuk är:
Reading scrambled words
Generate spelling errors.
Posted by hakank at september 21, 2005 09:06 EM Posted to Språk
Comments
De där anagrammen på tv brukar vara väldigt lätta, även när de är riktigt långa. Jag bläddrar ibland förbi kanalen och ser lösningen på under en sekund. (Det är förstås tanken; att så många som möjligt ska lösa dem och ringa in.) Jag inbillar mig att bokstäverna är omflyttade väldigt lite och att man gör ett anagram av varje del av ordet för sig.
Men det kan också vara så att varje orddel behåller första och sista bokstaven, eftersom det ofta är allt som behövs för att vi ska utläsa hela ordet. Intressant är det iaf.
Posted by: Christian Davén at september 26, 2005 02:45 EM