« Amazontest | Main | Segregeringseffekter inom yrken »
september 26, 2003
Lek: Hitta gömt ord
Som ett delprojekt i något annat har jag skapat en liten lek: Hitta ett gömt ord i en slumpsträng. Programmet kallas Find hidden words.
Principen bakom programmet är enkel: slumpa fram ett ord från en ordlista, skapa sedan en sträng med "meningslösa" bokstäver och göm det korrekta ordet i denna sträng.
Hur lätt/svårt är det att hitta det gömda ordet?
Naturligtvis finns det en koppling mellan detta och de nyliga projekt som beskrivits i Förvanskade ord - liten empirisk undersökning, Läsning av förvanskade ord samt Skapa stavfel.
Det intressanta med programmet är att det använder en n-gram-fördelning för att generera de meningslösa bokstäverna. Detta innebär att ju högre n-värde (n som i n-gram) desto större är chansen att delsträngar i texten liknar riktiga delsträngar. Generering av text med Markov-kedjor bygger på samma princip (se nedan).
Man kan leka med olika värden för n för att se om/hur det påverkar hur lätt/svårt det är att hitta det gömda ordet.
N-gramfördelningen har jag tagit genom att gå analysera mina ordlistor, vilket säkert inte är helt optimalt. Man borde nog använda en stor fet korpus av "vanliga" texter.
Lite andra program som använder n-gram (Markov-kedjor) för att skapa slumpmässiga texter:
Posted by hakank at september 26, 2003 01:29 EM Posted to Diverse
Comments
"Find hidden words" var intressant. Jag kom på en sak som ställde till det lite när jag provade. Bland de slumpvalda bokstäverna kan det genereras riktiga ord.
Jag fick exempelvis strängen "uristeadventivmbliotprängutterrkoanation". De ord jag hittar är:
ur
i
is
ris
riste
iste
te
advent
ven
bli
äng
utter
ko
ana
anat
På något sätt skulle man behöva säkerställa att inga ord genereras av slumpen, fast det är kanske inte så lätt. Det blir dock lite enkelt att hitta ord nu.
Jag har kanske rentav missuppfattat "tävlingen"?
:-)
Vänliga hälsningar
Niklas
Posted by: Niklas Johansson at september 29, 2003 12:04 EM
Niklas: Nej, du har inte alls missuppfattat tävlingen.
Du har naturligtvis en stor poäng. Tyvärr går det inte att garantera att inget annat ord kan bildas, eftersom även riktiga ord som "riste" och "advent" innehåller riktiga (del)ord ("i", "ris", "ven" etc), och dem vill vi väl inte utesluta, eller hur?
Det är säkerligen också praktiskt ogörbart (dvs tar för lång runtime-tid) att se till att inget av de 110000 riktiga orden inte finns någonstans i den skapade strängen. Att _detektera_ att det finns andra ord är enkelt (se nedan), däremot är det, som jag ser det nu, betydligt svårare att garantera att inga finns.
Därför har jag nu lagt till lite finesser som kan vara till hjälp:
* Man kan sätta en minimigräns för längden på det gömda ordet, default 5 bokstäver. Man kan sätta mellan 1 och 15 bokstäver som minimum. Ingen maxgräns finns.
* Man kan ange att längden på ordet ska visas.
* samt en sak jag kom att tänka på när jag såg din lista: visa alla riktiga ord (av korrekt längd) som finns i strängen.
Den sistnämnda funktionen skulle man kunna använda för att se hur stor chans det är att ett riktigt ord skapas givet ett visst n-ngram-värde. Men det är ett annat program...
Stort tack för kommentarer, kritik och inspiration!
Posted by: Håkan Kjellerstrand at september 29, 2003 01:37 EM
Bra förändringar! Genom att kunna sätta längden på ordet kan man delvis komma ifrån problemet med andra ord som har råkat bildas.
Det var intressant att se vilka ord programmet hittade i strängen. Jag vet inte vad du använder för ordlista, men se på denna sträng:
stisotifllistyvhalningecdaagglutdelbnast
De ord programmet hittade var halning och styvhalning. De ord jag hittade, utöver dessa, var:
i, is, sot, hal, list, ge, agg, lut, ut, de, del och as
Jag antar att det beror på att orden inte finns i ordlistan. :-)
Vänliga hälsningar
Niklas
Posted by: Niklas Johansson at september 30, 2003 12:36 EM
Eller snarare att de är kortare än den satta minimi-längden, en restriktion som "klart och tydlig" stod i instruktionerna. :-).
Tydligen var det inte så klart och tydligt, och jag var själv inte helt nöjd med restriktionen. Sålunda har jag nu ändrat så att alla ord, oavsett längd, kommer med i subwords-listan.
Posted by: Håkan Kjellerstrand at september 30, 2003 12:52 EM
Jag läste uppenbarligen slarvigt. Nu hittar den i vilket fall som helst betydligt fler ord än vad jag gör. Många visste jag inte ens att de existerade.
Det kan bli en tävling i sig, att hitta så många ord som möjligt och sedan jämföra sig med facit längst ner.
:-)
Vänliga hälsningar
Niklas
Posted by: Niklas Johansson at september 30, 2003 04:47 EM