Scrabbleforumet

Diskussionsforum om Scrabble
Aktuellt datum och tid: lör 18 nov, 2017 06:40

Alla tidsangivelser är UTC + 1 timme [ Sommartid ]




Ny tråd Svara på tråd  [ 8 inlägg ] 
Författare Meddelande
 Inläggsrubrik: TRIE, DAWG
InläggPostat: ons 15 dec, 2010 19:19 
Offline
Ordlistekommittén

Blev medlem: ons 07 mar, 2007 21:14
Inlägg: 512
Nej, inte gangstaspråk utan datastrukturer för att lagra ordlistor.
http://en.wikipedia.org/wiki/Trie
http://en.wikipedia.org/wiki/Directed_a ... word_graph

Jag vet att några här är insatta så jag tänkte fråga lite om den senare strukturen.

Jag genererade en TRIE av tävlingsordlistan, det blev 432.715 noder (att jämföre med ordlistans 1.053.550 bokstäver).

Frågan är nu, hur genererar man en optimal DAWG? Att generera en som bara går ihop vid gemensamma suffix är troligen rätt bra, men inte nödvändigtvis optimalt. Jag hittade http://www.pathcom.com/~vadco/dawg.html men finns det någon bättre beskrivning, gärna med optimalitetsbevis om det inte är självklart när man förstått algoritmen?


Upp
 Profil  
 
 Inläggsrubrik: Re: TRIE, DAWG
InläggPostat: ons 15 dec, 2010 23:55 
Offline
Ordlistekommittén

Blev medlem: tis 05 okt, 2004 21:01
Inlägg: 960
Ort: Solna
Jag har kod som skapar en DAWG. Inte nödvändigtvis optimal tror jag eftersom det spelar väldigt liten roll för sökprestanda.

Jag har också skrivit kod som skapar en DAGGAD men jag har inte skrivit draggeneratorn för det.

_________________
Det är skönare lyss till en sträng, som brast, än att aldrig spänna en båge.


Upp
 Profil  
 
 Inläggsrubrik: Re: TRIE, DAWG
InläggPostat: fre 17 dec, 2010 01:46 
Offline
Regelkommittén

Blev medlem: mån 17 jan, 2005 16:37
Inlägg: 1051
Spontant tror jag att det är ett (mycket) svårt problem att bevisa att en viss generator är optimal, eller för den delen att generera en optimal lösning för en ordlista av någorlunda storlek.

Tror dock att man bör fråga sig vad det är man försöker åstadkomma med den här kompressionen. Om man vill ha små filer att distribuera är det nog bättre att använda en vanlig textkompressor. Att hålla nere kravet på arbetsminne är väl förmodligen inte så intressant i dessa dagar när vi talar om någon megabyte. Och om man vill få snabbare algoritmer så gäller det ju att overheaden i hanteringen inte äter upp eventuella vinster från bättre cacheutnyttjande osv.

Jag brukar för sådana här syften oftast använda algoritmer som opererar på representationer av fix storlek, exempelvis 32 bitar per ord, vilket går att använda till det mesta när det gäller ordletande osv. Det blir bara approximativt men det kan ge väldigt hög tillförlitlighet.


Upp
 Profil  
 
 Inläggsrubrik: Re: TRIE, DAWG
InläggPostat: fre 17 dec, 2010 09:32 
Offline
Ordlistekommittén

Blev medlem: ons 07 mar, 2007 21:14
Inlägg: 512
Merko skrev:
Spontant tror jag att det är ett (mycket) svårt problem att bevisa att en viss generator är optimal, eller för den delen att generera en optimal lösning för en ordlista av någorlunda storlek.
Du har nog rätt. Det finns väl på sin höjd några kanoniska DAWG:ar som det finns algoritmer för att generera.
Spelar det alls någon roll för sökprestandan att fortsätta från TRIE till DAWG? Jag har inget direkt mål med det här, var mest intresserad av representationerna. Kanske jag försöker skriva en draggenerator utgående från GADDAG när jag har tid (haha).
Citera:
Jag brukar för sådana här syften oftast använda algoritmer som opererar på representationer av fix storlek, exempelvis 32 bitar per ord, vilket går att använda till det mesta när det gäller ordletande osv. Det blir bara approximativt men det kan ge väldigt hög tillförlitlighet.
Vad/Hur gör du då?


Upp
 Profil  
 
 Inläggsrubrik: Re: TRIE, DAWG
InläggPostat: fre 17 dec, 2010 17:46 
Offline
Ordlistekommittén

Blev medlem: tis 05 okt, 2004 21:01
Inlägg: 960
Ort: Solna
ANDERStG skrev:
Merko skrev:
Spontant tror jag att det är ett (mycket) svårt problem att bevisa att en viss generator är optimal, eller för den delen att generera en optimal lösning för en ordlista av någorlunda storlek.
Du har nog rätt. Det finns väl på sin höjd några kanoniska DAWG:ar som det finns algoritmer för att generera.
Spelar det alls någon roll för sökprestandan att fortsätta från TRIE till DAWG? Jag har inget direkt mål med det här, var mest intresserad av representationerna. Kanske jag försöker skriva en draggenerator utgående från GADDAG när jag har tid (haha).


Bättre packad datastruktur ger mindre minnesskyfflande och därmed färre cachemissar. Jag tror att skillnaden mellan TRIE och DAWG är rätt stor, en DAWG för SAOL är så liten att den får plats i L2-cachen på de flesta moderna processorer. Skillnaden blir ännu mycket större för en GADDAG.

_________________
Det är skönare lyss till en sträng, som brast, än att aldrig spänna en båge.


Upp
 Profil  
 
 Inläggsrubrik: Re: TRIE, DAWG
InläggPostat: fre 17 dec, 2010 20:28 
Offline
Regelkommittén

Blev medlem: mån 17 jan, 2005 16:37
Inlägg: 1051
Citera:
Vad/Hur gör du då?

När jag var arbetslös fick jag in en artikel med en snarlik algoritm som kan användas även för att lösa problem som "hitta alla ord som kan läggas med brickorna EEDMST??".


Upp
 Profil  
 
 Inläggsrubrik: Re: TRIE, DAWG
InläggPostat: mån 03 sep, 2012 09:47 
Offline
Ordlistekommittén

Blev medlem: ons 07 mar, 2007 21:14
Inlägg: 512
Jag plockade upp det här projektet igen. Ordlistan som sådan gav en DAWG med drygt 100 000 noder, medan ordlistan som GADDAG (med ankartecken) gav cirka 1 000 000 noder. Lagrade som integer array blir det alltså 450 kB respektive 4 MB.

Hur gör man draggenerering med den mindre strukturen? Jag tänker mig att man kan:
1. Generera alla "huvudord" med enbart egna brickor och kontrollera mot förberäknade hakningsmöjligheter
2. Generera ord och förgrena algoritmen till alla möjliga positioner med liggande bokstäver
Det låter omständligt jämfört med att använda ankartecken, har någon en bättre algoritmbeskrivning?


Upp
 Profil  
 
 Inläggsrubrik: Re: TRIE, DAWG
InläggPostat: sön 09 sep, 2012 21:01 
Offline
Ordlistekommittén

Blev medlem: tis 05 okt, 2004 21:01
Inlägg: 960
Ort: Solna
ANDERStG skrev:
Jag plockade upp det här projektet igen. Ordlistan som sådan gav en DAWG med drygt 100 000 noder, medan ordlistan som GADDAG (med ankartecken) gav cirka 1 000 000 noder. Lagrade som integer array blir det alltså 450 kB respektive 4 MB.

Hur gör man draggenerering med den mindre strukturen? Jag tänker mig att man kan:
1. Generera alla "huvudord" med enbart egna brickor och kontrollera mot förberäknade hakningsmöjligheter
2. Generera ord och förgrena algoritmen till alla möjliga positioner med liggande bokstäver
Det låter omständligt jämfört med att använda ankartecken, har någon en bättre algoritmbeskrivning?


Steven Gordon, A Faster Scrabble Move Generation Algorithm, Software - Practice and Experience, 1994

_________________
Det är skönare lyss till en sträng, som brast, än att aldrig spänna en båge.


Upp
 Profil  
 
Visa inlägg nyare än:  Sortera efter  
Ny tråd Svara på tråd  [ 8 inlägg ] 

Alla tidsangivelser är UTC + 1 timme [ Sommartid ]


Vilka är online

Användare som besöker denna kategori: Inga registrerade användare och 2 gäster


Du kan inte skapa nya trådar i denna kategori
Du kan inte svara på trådar i denna kategori
Du kan inte redigera dina inlägg i denna kategori
Du kan inte ta bort dina inlägg i denna kategori
Du kan inte bifoga filer i denna kategori

Sök efter:
Hoppa till:  
cron
Powered by phpBB® Forum Software © phpBB Group
Swedish translation by Peetra & phpBB Sweden © 2006-2010