Uporaba kriptografije v internetu
Kazalo   
 

Statistične lastnosti in entropija jezikov

V naravnem jeziku posamezni glasovi oziroma črke ne nastopajo enako pogosto in se pojavljajo samo v določenih kombinacijah. Zato lahko uganemo neko besedo, čeprav ne poznamo vseh črk, ki jo sestavljajo.

Naslednji tabeli prikazujeta frekvence črk v odstotkih v nekaj jezikih. Prepisani sta iz CLASSICAL CRYPTOGRAPHY COURSE (avtor Randy Nichols). Za slovenščino so podatki povzeti iz doktorske disertacije Primoža Jakopina (5.poglavje - Statistični opis).

latinsko francosko italijansko špansko portugalsko
I 10 E 18 E 13 EA 13 A 14
E 9 AN 8 A 12 O 9 E 13
UTA 7 RSIT 7 I 11 S 8 O 12
SRN 6 UO 6 O 9 RNI 7 RS 8
OM 4 L 5 L 7 DL 5 IN 6
CPL 3 D 4 NRT 6 CTU 4 DMT 5
druge <2 CMP 3 SC 5 MP 3 UCL 4
    VB 2 DMOU 3 GYB 1 P 3
    druge <1 VG 2 druge <1 QV 2
        druge <1     druge <1

nemško angleško norveško holandsko madžarsko slovensko
E 18 E 12 E 16 E 20 E 16 AE 10,5
N 11 T 10 RNS 8 N 10 A 13 OI 9
I 8 AO 8 T 7 IAT 7 T 8 N 6,3
RS 7 NIS 7 AI 6 O 6 OS 6 LSR 5
ADTU 5 R 6 LDO 5 DL 5 LNZ 5 JT 4,7 ; 4,2
AGHO 4 H 5 GKM 4 S 4 KIM 4 VKDPM 3,8 - 3,2
LBM 3 LDCU 4-3 UVFHPA 2 GKH 3 RGU 3 ZBU 2
CW 2 PFMV 2 druge <1 UVWBJMPZ 2 druge <2 1,5
druge <1 YBGV 1     druge <1     1
    KQXJZ <1             CŽF <1

Frekvence za slovenščino so dobljene iz vzorca iz 19.281.418 znakov, ki vsebuje leposlovna dela (celoten opus Cirila Kosmača ter še 46 izvirnih del in 14 prevodov).

Poleg frekvenc posameznih črk se pri kriptoanalizi šifropisov, narejenih po klasičnih algoritmih, uporablja še frekvence n-terčkov črk. Za slovenščino jih prav tako najdemo v disertaciji Primoža Jakopina.

Ali lahko to lastnost jezikov, da črke nastopajo samo v določenih kombinacijah, na kakšen način merimo? Kako bi ocenili, za koliko bolj varčno bi lahko pisali v tem jeziku? Utemeljitelj teorije informacij Claude Shannon je v svojem članku A Mathematical Theory of Communication (1948) prevzel izraz iz termodinamike entropija za mero nedoločenosti oziroma neurejenosti v sistemu: bolj je sistem neurejen (čim težje uganemo naslednje stanje sistema), tem večja je njegova entropija:

kjer je n število vseh možnih stanj sistema X, pi pa verjetnost pojavitve i-tega stanja.

Drugače povedano: količino informacije nekega sporočila določimo kot najmanjše število bitov, potrebnih, da zajamemo vse možne pomene sporočila. Entropija meri količino informacije v bitih.

Če ima nek sistem samo eno stanje, je njegova entropija 0, saj tu ni nedoločenosti. Če ima sistem n stanj, ki vsa nastopajo z enako verjetnostjo pi = 1/n, gornjo formulo preoblikujemo v:

V takem primeru je entropija tega sistema največja, saj imamo najmanj možnosti, da uganemo naslednje stanje. Redundanca pa je komplement entropije, določena je kot razlika med največjo možno entropijo sistema in dejansko entropijo sistema:

R = log2n - H.

Vzemimo kot primer sistem s štirimi stanji. Če vsa nastopajo z enako verjetnostjo, je entropija tega sistema enaka H = log24 = 2. Če pa se pojavljajo z naslednjimi verjetnostmi: P1 = 1/2; P2 = 1/4; P3= 1/8; P4 = 1/8 , dobimo H = 1,75. V prvem primeru je redundanca enaka 0, v drugem pa 0,25 bita oziroma 12,5%.

V naravnem jeziku so stvari bolj zapletene - kaj sploh vzeti kot stanja v tem živem sistemu? Če kot stanja vzamemo samo posamezne črke oziroma znake, ne upoštevamo v celoti redundance, ki je posledica tega, da so možne samo nekatere kombinacije črk. Sklepamo lahko, da če v istem vzorcu vzamemo v poštev daljše n-terčke, manjšo entropijo dobimo. V praksi izračunane vrednosti entropije jezika so približki, ki so odvisni od tega, kako dolge kose besedila so upoštevali, ali so upoštevali ločila in druge znake, pa še vzorec ponavadi ne zajema dovolj raznovrstnih besedil.

Problemi pri računanju entropije so podrobno predstavljeni v Jakopinovi disertaciji v poglavju 6- Entropija.

Izračunal je entropijo za n od 1 do 62 za vsakega od svojih dveh vzorcev, v disertaciji pa navaja vrednosti do n=24. Poglejmo nekaj vrednosti entropije na črko besedila Hn = 1/nH, ki pove, koliko bitov povprečno je potrebno za najkrajse zakodiranje ene črke besedila, če bi ga kodirali z n-terčki. Vrednosti so za vzorec iz različnih leposlovnih del:

n Hn število različnih n-terčkov
1 4,456 133
2 3,538 3683
3 3,673 30023
10 2,233 9385084
24 0,996 15684179

Vidimo, da pri upoštevanju kombinacij črk do deset dobimo vrednost 2,2 bita entropije na črko. Za angleščino je ustrezna ocena 2 bita na črko. Iz tega izračunana redundanca je

za slovenščino log225 - 2,2 = 4,6 - 2,2 = 2,4 bita (52%),

za angleščino pa log226 - 2,0 = 4,7 -2,0 = 2,7 bita (57%).

Če bi upoštevali daljše n-terčke, bi seveda dobili še večjo redundanco. To ne pomeni, da lahko izpustimo pol črk v nekem besedilu, pa ga bomo še razumeli, ampak, da lahko s primernim načinom zapisovanja skrčimo dolžino zapisov na polovico in tako zmanjšamo redundanco na minimum. Znake in n-terčke bi razvrstili po pogostosti in jih po vrsti označevali - najbolj pogoste z najmanj biti. Tak sistem označevanja znakov in kombinacij znakov se imenuje Huffmanovo kodiranje.

V praksi pa porabimo na črko 7, 8, 16 ali celo 32 bitov, zato je redundanca še višja. To se pri siceršnjem razmetavanju s prostorom na diskih ne zdi posebej pomembno, prepričana pa sem, da bo v bodoče, ko bo treba dolgoročno hraniti vedno več dokumentov, drugače.

December 2002