hakank.blogg

« En liten undersökning om kuluriga ord | Main | Word Meld Simple - en etyd med Ajax-tekniken »

januari 23, 2006

Något om prefixträd sorterade på lite olika sätt samt komprimering

Av en privat (och personlig) orsak behövdes ett program för att skapa unika prefix av ord i en lista, och sedan att presentera dessa prefix som ett träd. Anledningen var ungefär att korta ner en lista av ord till kortare ord (dess prefix).

Ett exempel på ett sådant prefixträd är för de svenska månadsnamnen:

a:
  ap: april
  au: augusti
d: december
f: februari
j:
  ja: januari
  ju:
    jul: juli
    jun: juni
m:
  ma:
    maj: maj (!!!)
    mar: mars
n: november
o: oktober
s: september


Här ser vi t.ex. att månadsnamnen december, februari och november kan komprimeras till en enda bokstav, medan april och augusti båda börjar på bokstaven a så vi måste här ta till en extra bokstav för att skilja dem åt. Man kan också notera att maj inte blev något prefix alls, utan här behövs hela ordet eftersom mars, den rackaren, ligger och stör. Sådana fall markeras med !!!!

Program Prefix Trees
Det har naturligtvis skapats ett program för att kunna leka vidare med sådana här ord-listor, och som - möjligen något missledande - kallas för Prefix trees.

Programkörningen för ovanstående svenska månadsnamen finns ungefär här.

Komprimering och annat skoj
Även om det primära syftet med programmet var att skapa unika prefix och prefixträd så var det svårt att låta bli att studera vissa saker i mer detalj.

Om man kör programmet för de svenska månadsnamnet kommer det, förutom det fina prefixträdet, även lite statistik (längst ner på sidan):

...
Original total length of words: 74
Total length of prefixes: 23
Mean prefix length: 1.92
Compression factor (original length/prefix length): 3.217


Man kan bl.a. se att det medellängden av de skapade prefixen är 1.92, vilket ska jämföras med medellängden av de ursprungliga orden på 6.17. Komprimeringsfaktorn är 3.217, vilket räknas ut med formeln

(sammanlagda längden av original orden) / (sammanlagda längden av prefixerna)


Dvs: genom att använda de unika prefixen istället för de hela orden sparar man en hel del, t.ex. träd (sic!) om man skulle använda papper för att skriva dem. Det kanske blir svårt att läsa det, men man skulle kunna spara både tid och pengar på detta. Nedan kommer vi att studera hur man kan spara något mer tid/papper/pengar men i gengäld blir det i stort sett oläsbart...

Frekvenssortering av bokstäver
En finess med programmet är att man kan studera lite olika varianter av representation av orden innan det skapas prefix. T.ex.

• bokstäverna i ordet sorteras innan man gör prefixen, valet Sort (plain)
  
• bokstäverna i ordet sorteras i omvänd ordning, valet Reverse. Not: om man både sorterar och reverse, blir det i omvänd sorteringsordning, dvs "ö" kommer före "ä" etc.
  

Sedan den mest intressanta varianten: bokstavsfrekvenssortering (valet Sort by letter frequency, som innebär att innan man skapar prefixen sorterar man ordets bokstäver i ordning av hur vanliga/sällsynta bokstäverna är bland samtliga ords bokstäver. T.ex. så är det troligt att bokstaven "z" är sällsynt vilket gör att ett ord med "z" kommer att prefixas som z + eventuellt någon annan bokstav.

Om vi fortsätter med månadsnamnsexemplet får man med bokstavsfrekvenssortering följande prefixträd:

d: december
f: februari
g: augusti
j: maj
k: oktober
l: juli
n:
  nj:
    nju:
      njui: juni
        njuia: januari
p:
  pl: april
  ps: september
s: mars
v: november
....
Original total length of words: 74
Total length of prefixes: 21
Mean original length: 6.17
Mean prefix length: 1.75
Compression factor (original length/prefix length): 3.524


Om man jämför med det "vanliga" prefixträdet så är komprimeringsfaktorn något lägre för bokstavsfrekvenssorteringsvarianten (3.524 jämfört med 3.217).

Denna skillnad tenderar att vara beständigt: Detta innebär att om man använder bokstavsfrekvenser istället blir det något bättre komprimering. Nackdelen är naturligtvis att "förkortningen" (prefixet) är fullständigt obegriplig. Se även en mer systematisk genomgång nedan.

Några noter kring detta
Möjligen skulle man här kunna göra en analogi med Huffman-kodning (ref till en.wikiedia) som skapar binära koder efter bokstävernas frekvens, där den kortaste koden tilldeleas den vanligaste bokstaven etc.

En mer avancerad variant av prefixträd skulle vara att analysera prefixträdet för att komprimera det ännu mer.

Det går naturligtvis också att göra det väldigt enkelt för sig och koda varje ord till ett eller flera fullständigt slumpmässiga tecken alltefter ordens/bokstävernas frekvens i texten. Men det är en övning som lämnas åt vidare öden (eller övning åt läsaren/skribenten).

Den ursprungliga poängen med prefixträden var att de skulle vara lätta att skapa och (relativt) lätt att uttyda när man ser dem. När man använder sorteringar av olika slag förloras detta syfte bort i skymningen varvid endast nästa dags solstrålar är glada att se det.

Liten undersökning
Det gjordes också en undersökning hur antalet olika ord i listan påverkar komprimeringsfaktorn respektive medelprefixlängden. Detta gjordes för ett olika antal slupmässiga svenska ord (ur en ordlista på nästan 400000 ord).

Det visar sig - inte speciellt förvånande - att ju fler slumpmässiga ord listan innehåller, desto sämre blir komprimeringsfaktorn och desto längre blir medellängden på prefixen. Som variansen visar är det relativt stabila värden förutom för den första körningen (10 ord i listan). Av tidsskäl kördes endast 10 gånger med samma liststorlek.

Prefix utan någon bokstavssortering

Antal ord	Komprimeringsgrad	Komprimeringsgrad varians	Prefix medellängd	Prefix medellängd, varians
10	7.80730	4.67526	1.47000	0.12456
100	4.14080	0.02874	2.63700	0.00842
200	3.54860	0.03530	3.11500	0.01812
500	3.04260	0.00201	3.60800	0.00775
1000	2.70590	0.00199	4.10200	0.00368
2000	2.39940	0.00078	4.60200	0.00717
3000	2.23620	0.00063	4.96000	0.00207
5000	2.06810	0.00030	5.36400	0.00158
10000	1.84500	0.00009	5.99800	0.00057
20000	1.65400	0.00002	6.68800	0.00040
50000	1.44040	0.00001	7.68000	0.00031
100000	1.31520	0.00000	8.41300	0.00020

Prefix med frekvensbokstavssortering

Antal ord	Komprimeringsgrad	Komprimeringsgrad varians	Prefix medellängd	Prefix medellängd, varians
10	9.68830	4.15306	1.15000	0.02500
100	4.24470	0.02675	2.56800	0.01280
200	3.81910	0.02128	2.94800	0.00544
500	3.26520	0.00193	3.40900	0.00283
1000	2.89340	0.00351	3.83500	0.00372
2000	2.61810	0.00032	4.24200	0.00044
3000	2.47130	0.00082	4.48900	0.00159
5000	2.28780	0.00018	4.82100	0.00054
10000	2.06480	0.00009	5.36200	0.00042
20000	1.87310	0.00003	5.91000	0.00018
50000	1.65010	0.00001	6.70800	0.00008
100000	1.50710	0.00000	7.34400	0.00014

Andra exempel
Jag har även kört programmet på några andra exempel, t.ex. 1000 vanligaste svenska orden, svenska förnamnen samt svenska efternamnen (plus "Kjellerstrand") från Språkbanken:

• 1000 vanligaste svenska orden (inklusive siffror, årtal och delar av förkortningar)
  
• 1000 vanligaste svenska orden, sorterade enligt bokstavsfrekvens
  
• 1000 vanligaste svenska förnamnen
  
• 1000 vanligaste förnamnen, sorterade enligt bokstavsfrekvens
  
• 1000 vanligaste svenska efternamnen (plus "kjellerstrand")
  
• 1000 vanligaste svenska efternamnen, sorterade enligt bokstavsfrekvens (plus "kjellerstrand")
  
• 1000 slumpmässiga svenska ord.
  
• 500 slumpade svenska ord, utan sortering samt med bokstavsfrekvenssortering.
  

Se även
En möjlig variant att göra en komprimering eller på annat sätt förkorta saker och ting är att använda reguljära uttryck, t.ex. som i programmet MakeRegex,.

Posted by hakank at januari 23, 2006 10:51 EM Posted to Program | Språk | Statistik/data-analys

Comments

Posted by: mike at december 1, 2007 03:16 EM

Posted by: Håkan Kjellerstrand at december 1, 2007 10:29 EM