TRIE, DAWG

Om SAOL och andra ordlistor.

TRIE, DAWG

Inläggav ANDERStG » ons 15 dec, 2010 19:19

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?
ANDERStG
Ordlistekommittén
 
Inlägg: 523
Blev medlem: ons 07 mar, 2007 21:14

Re: TRIE, DAWG

Inläggav Radagast » ons 15 dec, 2010 23:55

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.
Radagast
Ordlistekommittén
 
Inlägg: 962
Blev medlem: tis 05 okt, 2004 21:01
Ort: Solna

Re: TRIE, DAWG

Inläggav Merko » fre 17 dec, 2010 01:46

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.
Merko
Regelkommittén
 
Inlägg: 1052
Blev medlem: mån 17 jan, 2005 16:37

Re: TRIE, DAWG

Inläggav ANDERStG » fre 17 dec, 2010 09:32

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).
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å?
ANDERStG
Ordlistekommittén
 
Inlägg: 523
Blev medlem: ons 07 mar, 2007 21:14

Re: TRIE, DAWG

Inläggav Radagast » fre 17 dec, 2010 17:46

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.
Radagast
Ordlistekommittén
 
Inlägg: 962
Blev medlem: tis 05 okt, 2004 21:01
Ort: Solna

Re: TRIE, DAWG

Inläggav Merko » fre 17 dec, 2010 20:28

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??".
Merko
Regelkommittén
 
Inlägg: 1052
Blev medlem: mån 17 jan, 2005 16:37

Re: TRIE, DAWG

Inläggav ANDERStG » mån 03 sep, 2012 09:47

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?
ANDERStG
Ordlistekommittén
 
Inlägg: 523
Blev medlem: ons 07 mar, 2007 21:14

Re: TRIE, DAWG

Inläggav Radagast » sön 09 sep, 2012 21:01

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.
Radagast
Ordlistekommittén
 
Inlägg: 962
Blev medlem: tis 05 okt, 2004 21:01
Ort: Solna


Återgå till Ordlistor

Vilka är online

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

cron