Teh­tä­vä:
Da­tan pak­kaa­mi­nen ja Kol­mo­go­rov-komp­lek­si­suus

Ly­hyt Math­Check-oh­je (uu­teen vä­li­leh­teen)

Da­tan mää­rää mi­ta­taan yleen­sä sil­lä, mon­ta­ko ta­vua tar­vi­taan tal­let­ta­maan se. Ta­vu­mää­rä riip­puu kui­ten­kin esi­tys­ta­vas­ta. On ole­mas­sa hä­viöt­tö­miä pak­kaus­me­ne­tel­miä, joil­la tie­dos­toa voi pie­nen­tää toi­si­naan mer­kit­tä­väs­ti, mut­ta al­ku­pe­räi­nen tie­dos­to pys­ty­tään pa­laut­ta­maan pa­ka­tus­ta tie­dos­tos­ta. Tä­mä he­rät­tää ky­sy­myk­sen, voi­ko in­for­maa­tion mää­rää mi­ta­ta toi­sel­la ta­val­la, niin et­tä tu­lok­sek­si tu­lee pie­nim­män sel­lai­sen tie­dos­ton ko­ko, jo­hon in­for­maa­tio saa­daan mah­tu­maan niin et­tä se voi­daan siel­tä pa­laut­taa.

Täs­sä teh­tä­väs­sä käy­dään tä­män ky­sy­myk­sen kimp­puun, mut­ta si­tä en­nen kä­si­tel­lään da­tan pak­kaa­mi­seen liit­ty­viä pe­rus­asioi­ta. Pal­jas­tuu, et­tä pie­nim­män pa­ka­tun tie­dos­ton kool­la mit­taa­mi­nen ei toi­mi sel­lai­se­naan, kos­ka niin saa­ta­vaa tu­los­ta voi kei­no­te­koi­ses­ti ma­ni­pu­loi­da pak­kaus­me­ne­tel­män yk­si­tyis­koh­tia va­lit­se­mal­la. Pa­ka­tun tie­dos­ton pur­ka­va oh­jel­ma­kin si­säl­tää in­for­maa­tio­ta, ja se on otet­ta­va oi­keal­la ta­val­la huo­mioon.

Nä­mä poh­din­nat joh­ta­vat Kol­mo­go­rov-komp­lek­si­suu­te­na tun­net­tuun kä­sit­tee­seen, jo­ka on osa al­go­rit­mis­ta in­for­maa­tio­teo­riaa. Kol­mo­go­rov-komp­lek­si­suus vas­taa var­sin hy­vin mo­nien ih­mis­ten in­tu­i­tii­vi­sia odo­tuk­sia sii­tä, mi­ten in­for­maa­tion tu­li­si käyt­täy­tyä. Va­li­tet­ta­vas­ti sii­hen liit­tyy myös rank­ka rat­kea­mat­to­muus­tu­los, jo­ka te­kee sen käyt­tä­mi­ses­tä mit­ta­ri­na käy­tän­nös­sä mah­do­ton­ta.

1. Merk­ki­jo­not ja koo­dit
2. In­for­maa­tion pak­kaa­mi­nen
3. Kol­mo­go­rov-komp­lek­si­suus
4. Rank­ka rat­kea­mat­to­muus­tu­los
5. Lo­puk­si

Merk­ki­jo­not ja koo­dit

Aak­kos­to on mi­kä ta­han­sa ää­rel­li­nen jouk­ko. Sen al­kioi­ta kut­su­taan mer­keik­si. Täs­sä teh­tä­väs­sä ole­te­taan, et­tä on va­lit­tu jo­kin aak­kos­to Σ, jo­ka si­säl­tää ai­na­kin esi­mer­keis­sä käy­tet­tä­vät mer­kit. Mer­kit­sem­me merk­ki­jo­no­ja eli Σ*:n al­kioi­ta pie­nil­lä kreik­ka­lai­sil­la kir­jai­mil­la σ, ρ ja niin edel­leen. Merk­ki­jo­no­va­kiot esi­te­tään ”lai­naus­mer­keis­sä” ja merk­ki­va­kiot näin: ’0’.

Merk­ki­jo­non pi­tuus on sen merk­kien mää­rä. Si­tä mer­ki­tään |σ|. Esi­mer­kik­si |”pituus”| = …6. Jos σ ja ρ ovat merk­ki­jo­no­ja, niin σρ tar­koit­taa si­tä merk­ki­jo­noa, jos­sa on en­sin σ:n si­säl­tö ja he­ti pe­rään ρ:n si­säl­tö. Jos esi­mer­kik­si σ = ”yli”, niin σ”opisto” = …”yliopisto”.

On tär­keää, et­tä aak­kos­ton ko­ko on vä­hin­tään 2. Tyh­jäl­lä aak­kos­tol­la ei syn­ny mie­len­kiin­tois­ta in­for­maa­tion teo­riaa täs­tä syys­täSil­loin eri­lai­sia merk­ki­jo­no­ja on vain yk­si, ni­mit­täin tyh­jä merk­ki­jo­no ε.. Jos Σ = {’0’}, niin Σ* = tä­mä{ε, ”0”, ”00”, ”000”, ”0000”, …}. Sik­si jos |Σ| = 1, niin merk­ki­jo­nos­sa on olen­nais­ta vain sen pi­tuus, jol­loin teo­ria kä­sit­te­lee it­se asias­sa luon­nol­li­sia lu­ku­ja. Se on omal­la ta­val­laan mie­len­kiin­toi­nen asia, mut­ta ei tä­män teh­tä­vän ai­he.

Mo­nis­sa käy­tän­nön so­vel­luk­sis­sa mer­kit ovat ta­vu­ja. Da­ta on siis esi­tet­ty ta­vu­jen jo­no­na. Ta­vu koos­tuu 8 bi­tis­tä. Sil­loin |Σ| = näin pal­jon2⁸ = 256.

In­for­maa­tio­teo­rias­sa aja­tel­laan, et­tä on jo­kin jouk­ko läh­de­sa­no­ja, joil­le va­li­taan esi­tys­ta­vat koo­di­sa­noi­na. Koo­di­sa­nat ovat Σ*:n al­kioi­ta. Täs­sä teh­tä­väs­sä (ja usein muual­la­kin) ole­te­taan, et­tä läh­de­sa­no­jen jouk­ko on ää­rel­li­nen. Läh­de­sa­no­jen esi­tys­ta­pa ei ole olen­nai­nen. Läh­de­sa­no­jen ja koo­di­sa­no­jen muo­dos­ta­ma ko­ko­nai­suus on koo­di. Kah­del­la eri läh­de­sa­nal­la ei saa ol­la sa­ma koo­di­sa­na täs­tä syys­täMuu­ten koo­di­sa­nan muun­ta­mi­nen ta­kai­sin läh­de­sa­nak­si ei ai­na on­nis­tu. Jos esi­mer­kik­si se­kä ”spruce”:n et­tä ”six”:n koo­di­sa­na on ”kuusi”, niin ta­kai­sin kään­net­täes­sä ei tie­de­tä, pi­täi­si­kö ”kuusi” kään­tää ”spruce” vai ”six”.. Funk­tion, jo­ka ku­vaa läh­de­sa­nat koo­di­sa­noik­si on siis ol­ta­va …in­jek­tio. ”In­jek­tio” tar­koit­taa funk­tio­ta, jo­ka ei ku­vaa läh­tö­jou­kon mi­tään kah­ta eri al­kio­ta sa­mak­si maa­li­jou­kon al­kiok­si..

On ta­val­lis­ta, et­tä vies­tis­sä on usei­ta läh­de­sa­no­ja pe­räk­käin. Täl­löin koo­di­sa­nat pi­tää va­li­ta si­ten, et­tä ku­kin nii­den jo­no voi­daan pur­kaa niik­si vain yh­del­lä ta­val­la. Jol­lei näin teh­dä, niin voi käy­dä esi­mer­kik­si si­ten, et­tä läh­de­kie­len il­maus ”result evening” kään­tyy koo­di­sa­nak­si ”tulosilta”, jo­ka kään­tyy ta­kai­sin il­mauk­sek­si ”income bridge” (”tulo silta”). (Te­le­vi­sios­sa esi­tet­tiin 14.4.2019 Edus­kun­ta­vaa­lit 2019: Tu­los­il­ta.)

Ylei­sin ta­pa var­mis­taa tä­mä on va­li­ta koo­di­sa­nat si­ten, et­tä mi­kään niis­tä ei ole toi­sen ai­to al­ku­osa. Sa­na etu­lii­te­koo­di (prefix code) tar­koit­taa mi­tä ta­han­sa täl­lais­ta koo­dia. Siis esi­mer­kik­si ei voi ol­la niin, et­tä se­kä ”maa” et­tä ”maali” ovat koo­di­sa­no­ja. Ma­te­maat­ti­ses­ti sa­not­tu­na ei ole ole­mas­sa sel­lai­sia merk­ki­jo­no­ja σ ja ρ, et­tä ρ ≠ ε ja se­kä σ et­tä σρ on koo­di­sa­na. Äs­kei­ses­sä ”maali”-esi­mer­kis­sä σ = …”maa”, ρ = …”li”, ja σρ = …”maali”.

Jos kaik­ki koo­di­sa­nat ovat yh­tä pit­kiä, niin mi­kään niis­tä ei ole toi­sen ai­to al­ku­osa. Tie­to­tek­nii­kan maail­man­laa­jui­nen stan­dar­di­mer­kis­tö Uni­co­de si­säl­si 137 994 merk­kiä (jois­ta var­si­nai­sia nä­ky­viä merk­ke­jä 137 766) tou­ko­kuus­sa 2019, ja sii­nä on laa­jen­nus­va­raa suun­nil­leen mil­joo­naan merk­kiin saak­ka. UTF-32 esit­tää ne kaik­ki käyt­täen täs­mäl­leen nel­jä ta­vua merk­kiä koh­den.

Kaik­kien koo­di­sa­no­jen te­ke­mi­nen yh­tä pit­kik­si joh­taa hel­pos­ti muis­tin ja tie­to­lii­ken­ne­ka­pa­si­tee­tin tuh­laa­mi­seen. Täs­tä syys­tä UTF-32:sta käy­te­tään vä­hän. Esi­mer­kik­si suo­men­kie­lel­le riit­täi­si mai­nios­ti yk­si ta­vu merk­kiä koh­den. (Ai­koi­naan suo­sit­tu mer­kis­tö ISO/IEC 8859-1 oli­kin sel­lai­nen.) Syys­kuus­sa 2019 yli­voi­mai­ses­ti suo­si­tuin esi­tys­ta­pa (94 % maail­man vep­pi­si­vuis­ta) oli UTF-8. Se käyt­tää yh­des­tä nel­jään ta­vua merk­kiä koh­den. UTF-8-koo­da­tun mer­kin en­sim­mäi­nen ta­vu si­säl­tää tie­don, mon­ta­ko ta­vua mer­kin koo­di­sa­na si­säl­tää. Sik­si mi­kään UTF-8-koo­dat­tu merk­ki ei voi ol­la toi­sen UTF-8-koo­da­tun mer­kin ai­to al­ku­osa.

Usein esiin­ty­vil­le läh­de­sa­noil­le kan­nat­taa an­taa ly­hyet koo­di­sa­nat ja har­voin esiin­ty­vil­le pi­tem­mät koo­di­sa­nat. Tä­tä ei kui­ten­kaan voi teh­dä si­ten, et­tä 256 useim­min esiin­ty­vää läh­de­sa­naa saa yh­den ta­vun pi­tui­sen koo­di­sa­nan, seu­raa­vat 256² = 65 536 kah­den ta­vun pi­tui­sen ja niin edel­leen, kos­ka …Sil­loin esi­mer­kik­si koo­di­sa­no­jen jo­nos­ta ”aa” ei tie­det­täi­si, esit­tää­kö se si­tä läh­de­sa­naa, jon­ka koo­di­sa­na on ”aa”, vai kah­ta pe­räk­käis­tä esiin­ty­mää sii­tä läh­de­sa­nas­ta, jon­ka koo­di­sa­na on ”a”.

Olet­ta­kaam­me ha­vain­nol­li­suu­den vuok­si, et­tä Σ = {’0’, ’1’, …, ’9’} ja ha­luam­me koo­da­ta sa­ta eri­lais­ta läh­de­sa­naa etu­lii­te­koo­dil­la. Yk­si mah­dol­li­suus on käyt­tää kul­le­kin koo­di­sa­nal­le kak­si merk­kiä, eli koo­di­sa­nat ovat ”00”, ”01”, …, ”09”, ”10”, …, ”99”. Jos jol­le­kin läh­de­sa­nal­le an­ne­taan­kin koo­di­sa­nak­si ”0”, niin kuin­ka mo­nel­le läh­de­sa­nal­le jou­du­taan an­ta­maan vä­hin­tään kol­men mer­kin pi­tui­nen koo­di­sa­na? vih­je 1Muo­dos­ta eh­dot täyt­tä­vä koo­di. En­sim­mäi­nen koo­di­sa­na on ”0” ja mi­kään muu ei ala ’0’:lla. Kol­men mer­kin pi­tui­sia on niin pal­jon, et­tä koo­di­sa­no­ja on kaik­kiaan sa­ta. Mi­kään kol­men mer­kin pi­tui­nen ei ole min­kään kah­den mer­kin pi­tui­sen jat­ke. Sel­lai­ses­ta koo­dis­ta on esi­merk­ki vih­je 2:ssa. vih­je 2”0”, ”10”, ”11”, …, ”19”, ”20”, …, ”98”, ”990”, ”991”, …, ”999”. vas­taus10 Kaik­kein useim­min esiin­ty­vän läh­de­sa­nan esit­tä­mi­nen yh­del­lä mer­kil­lä kan­nat­taa täs­sä esi­mer­kis­sä siis vain, jos se esiin­tyy vä­hin­tään yh­tä useas­ti kuin näin mon­ta10 har­vi­nai­sin­ta läh­de­sa­naa yh­teen­sä.

Mer­kit­sem­me eri läh­de­sa­no­jen to­den­nä­köi­syyk­siä p₁, …, p_n ja vas­taa­vien koo­di­sa­no­jen pi­tuuk­sia l₁, …, l_n. Koo­da­tun vies­tin pi­tuus on kes­ki­mää­rin p₁l₁ + p₂l₂ + … + p_nl_n. Esi­mer­kik­si jos koo­di­sa­nat ja nii­den osuu­det ovat ohei­sen tau­lu­kon mu­kai­set, niin koo­dat­tu vies­ti on kes­ki­mää­rin näin pit­kä0,60 ⋅ 1 + 0,25 ⋅ 3 + 0,10 ⋅ 3 + 0,05 ⋅ 3 = 1,8. On­ko tau­lu­kon koo­di etu­lii­te­koo­di? vas­tausOn.

”0”	”100”	”101”	”111”
60 %	25 %	10 %	5 %

Tä­tä koo­dia on help­po muun­taa si­ten, et­tä muun­net­tu­kin koo­di on etu­lii­te­koo­di mut­ta koo­dat­tu­jen vies­tien kes­ki­mää­räi­nen pi­tuus vä­he­nee. Näin se käy!Koo­di­sa­nan ”111” ti­lal­la voi ol­la ”11”. Sen jäl­keen kes­ki­pi­tuus on 1,75. Vie­lä pa­rem­pi tu­los 1,55 saa­daan va­raa­mal­la ”11” sil­le läh­de­sa­nal­le, jon­ka to­den­nä­köi­syys on 25 % (jol­loin se läh­de­sa­na, jon­ka to­den­nä­köi­syys on 5 %, saa koo­di­sa­nan ”100”).

Kun sa­nom­me, et­tä etu­lii­te­koo­di on op­ti­maa­li­nen, niin ole­tam­me, et­tä eri läh­de­sa­no­jen esiin­ty­mis­to­den­nä­köi­syy­det on kiin­ni­tet­ty ja tar­koi­tam­me, et­tä koo­di tuot­taa kes­ki­mää­rin niin ly­hyet koo­da­tut vies­tit kuin mah­dol­lis­ta. Tar­koi­tam­me siis, et­tä p₁l₁ + p₂l₂ + … + p_nl_n on mah­dol­li­sim­man pie­ni. Jos Σ = {’0’, ’1’} ja läh­de­sa­no­jen to­den­nä­köi­syy­det ovat 60 %, 25 %, 10 % ja 5 %, niin on­ko koo­di {”00”, ”01”, ”10”, ”11”} op­ti­maa­li­nen? vas­tausEi ole. Sen tuot­ta­ma kes­ki­pi­tuus on 2. Edel­lä näy­tet­ty koo­di tuot­ti 1,8 ja sen pa­ran­net­tu ver­sio 1,55.

Näil­lä to­den­nä­köi­syyk­sil­lä siis kan­nat­taa an­taa eri läh­de­sa­noil­le eri­pi­tui­sia koo­di­sa­no­ja. Osoi­tam­me seu­raa­vak­si tu­lok­sen, jo­ka tus­kin yl­lät­tää.

Lau­se 1 Jos kaik­ki läh­de­sa­nat ovat yh­tä to­den­nä­köi­siä, niin op­ti­maa­li­ses­sa etu­lii­te­koo­dis­sa koo­di­sa­no­jen pi­tuu­det poik­kea­vat toi­sis­taan enin­tään yh­del­lä.

To­dis­tus. Osoi­tam­me, et­tä jos etu­lii­te­koo­dis­sa on kak­si koo­di­sa­naa, joi­den pi­tuus­ero on ai­na­kin 2, niin si­tä voi muut­taa tii­viim­mäk­si si­ten, et­tä se säi­lyy etu­lii­te­koo­di­na. An­nam­me ly­hyem­mäl­le niis­tä ni­men σ ja si­tä vas­taa­val­le läh­de­sa­nal­le s. Pi­dem­mäl­le an­nam­me ni­men ρa₁, mis­sä ρ on merk­ki­jo­no ja a₁ on merk­ki. An­nam­me täl­lai­sen ni­men, kos­ka se tu­lee ole­maan kä­te­vä jat­kos­sa. Lu­pa an­taa täl­lai­nen ni­mi tu­lee sii­tä, et­tä pi­dem­mäs­sä koo­di­sa­nas­sa on var­mas­ti ai­na­kin yk­si merk­ki, kos­ka se on ai­na­kin 2 merk­kiä pi­tem­pi kuin σ.

Ole­te­tun pi­tuus­eron vuok­si pä­tee |ρa₁| ≥ |σ| + 2. Sii­tä seu­raa |ρ| ≥ |σ| + 1 eli |ρ| > |σ|.

Jos koo­dis­sa ei ole mui­ta ρ-al­kui­sia koo­di­sa­no­ja kuin ρa₁, niin si­tä voi tii­vis­tää täl­lä ta­val­laVaih­de­taan ρa₁:n ti­lal­le ρ..

Muus­sa ta­pauk­ses­sa ol­koot ρ-al­kui­set koo­di­sa­nat ρa₁, …, ρa_n, mis­sä n ≥ …2 täs­tä syys­täTo­dis­tuk­sen alun pe­rus­teel­la ρ-al­kui­sia koo­di­sa­no­ja on ai­na­kin yk­si, ja olem­me muus­sa ta­pauk­ses­sa kuin sii­nä, jos­sa nii­tä on vain yk­si.. Ol­koot s₁, …, s_n nii­tä vas­taa­vat läh­de­sa­nat. Vaih­de­taan nii­den koo­di­sa­noik­si σa₁, …, σa_n ja s:n koo­di­sa­nak­si ρ. Mi­kään min­kään σa_i:n ai­to al­ku­osa ei ole syn­ty­vän koo­din koo­di­sa­na täs­tä syys­täMi­kään min­kään σa_i:n ai­to al­ku­osa ei ole ρ, kos­ka |ρ| > |σ|. σ lak­kaa ole­mas­ta koo­di­sa­na. Mi­kään σ:n ai­to al­ku­osa ei ole koo­di­sa­na, kos­ka se ei ol­lut koo­di­sa­na al­ku­pe­räi­ses­sä koo­dis­sa, kos­ka σ oli sii­nä koo­di­sa­na ja se oli etu­lii­te­koo­di.. Mi­kään ρ:n ai­to al­ku­osa ei ole syn­ty­vän koo­din koo­di­sa­na täs­tä syys­täσ ei voi ol­la ρ:n al­ku­osa, kos­ka al­ku­pe­räi­nen koo­di oli etu­lii­te­koo­di ja sii­nä σ ja ρa₁ oli­vat koo­di­sa­no­ja. Sik­si myös­kään mi­kään σa_i ei voi ol­la ρ:n al­ku­osa. Mi­kään ρ:n ai­to al­ku­osa ei ole koo­di­sa­na, kos­ka se ei ol­lut koo­di­sa­na al­ku­pe­räi­ses­sä koo­dis­sa, kos­ka ρa₁ oli sii­nä koo­di­sa­na ja se oli etu­lii­te­koo­di.. Sik­si koo­di säi­lyy etu­lii­te­koo­di­na.

Tä­mä muut­tuu sel­vem­mäk­si, kun piir­rät ku­van. Va­lit­se ku­vaan koo­di­sa­noi­ksi ”tali”, ”talk”, ”talo” ja ”te”. Nyt σ = …”te”, ρ = …”tal”, n = …3, ja a₁, …, a_n ovat …’i’, ’k’ ja ’o’. Piir­rä de­ter­mi­nis­ti­sen ää­rel­li­sen au­to­maa­tin nä­köi­nen ku­va jos­sa haa­rat ei­vät yh­dis­ty, ja muun­na se ku­vak­si, jos­sa koo­di­sa­nat ovat σa₁ ja niin edel­leen.

s:n koo­di­sa­na pi­te­nee näin mo­nen|ρ| − |σ| mer­kin ver­ran ja jo­kai­sen s_i:n koo­di­sa­na ly­he­nee näin mo­nen|ρa_i| − |σa_i| = |ρ| − |σ| mer­kin ver­ran. Nä­mä ly­he­ne­mät ja pi­te­ne­mät ovat po­si­tii­vi­sia täs­tä syys­täEdel­lä to­det­tiin, et­tä |ρ| > |σ|.. Kos­ka n ≥ 2, ly­he­ne­mis­tä on enem­män kuin pi­te­ne­mis­tä. □ 

Jos kaik­ki läh­de­sa­nat ei­vät ole­kaan yh­tä to­den­nä­köi­siä, niin op­ti­maa­li­sen koo­din muo­dos­ta­mi­nen on mie­len­kiin­toi­nen teh­tä­vä. MIT:n pro­fes­so­ri Ro­bert Fa­no oli si­tä tur­haan yrit­tä­nyt. Hän an­toi vuon­na 1951 opis­ke­li­ja­ryh­mäl­le teh­tä­väk­si kir­joit­taa on­gel­maa kä­sit­te­le­vä es­see. Da­vid Huff­man on­nis­tui rat­kai­se­maan on­gel­man. Huff­ma­nin koo­di on tie­to­ko­neil­le help­po laa­tia ja käyt­tää, ja sen op­ti­maa­li­suu­den to­dis­tus on kieh­to­va. Jos ha­luat tu­tus­tua nii­hin pe­rus­teel­li­sem­min, niin suo­ri­ta teh­tä­vä Shan­no­nin ala­ra­ja.

Huff­ma­nin koo­di ei kui­ten­kaan ole ko­ko to­tuus, kos­ka läh­de­sa­no­jen to­den­nä­köi­syy­det voi­vat riip­pua edel­tä­vis­tä läh­de­sa­nois­ta. Ha­vain­nol­lis­tam­me tä­tä esi­mer­kil­lä, jo­ka on käy­tän­nön kan­nal­ta ty­pe­rä, mut­ta sii­tä huo­li­mat­ta osoit­taa, et­tä toi­si­naan in­for­maa­tio­ta voi tii­vis­tää pal­jon enem­män kuin mi­hin Huff­ma­nin koo­di pys­tyy.

Esi­mer­kis­sä vies­ti muo­dos­tuu merk­ki­pa­reis­ta, jois­sa sa­ma merk­ki esiin­tyy kah­des­ti tä­hän tyy­liin: ”eessiimmeerrkkkkii”. Jos a ja b ovat kak­si eri merk­kiä, niin merk­ki­pa­rit aa ja bb ovat yh­tä to­den­nä­köi­set, ja merk­ki­pa­rin ab to­den­nä­köi­syys on tä­mä0, kos­ka juu­ri sa­noim­me, et­tä merk­ki­pa­rin mer­kit ovat sa­ma merk­ki.. (ab voi kui­ten­kin esiin­tyä si­ten, et­tä en­sin on merk­ki­pa­ri aa ja he­ti sen pe­räs­sä merk­ki­pa­ri bb.) Op­ti­maa­li­nen etu­lii­te­koo­di esit­tää jo­kai­sen mer­kin yh­del­lä mer­kil­lä, mut­ta puo­let pa­rem­paan tu­lok­seen pääs­tään ot­ta­mal­la kun­kin merk­ki­pa­rin jäl­kim­mäi­nen merk­ki pois. Esi­mer­kik­si ”eessiimmeerrkkkkii”:stä tu­lee tä­mä”esimerkki”.

Rea­lis­ti­sem­pi esi­merk­ki saa­daan suo­men­kie­les­tä. Kir­jai­men ’a’ ylei­syys on yli 11 %, mut­ta jos kak­si vii­mek­si luet­tua merk­kiä oli­vat ’a’ ja ’a’, niin to­den­nä­köi­syys sil­le, et­tä seu­raa­va­kin merk­ki on ’a’, on li­ki­main nol­la.

Tä­mä il­miö voi­daan ot­taa Huff­ma­nin koo­dis­sa huo­mioon koo­daa­mal­la merk­ki­pa­re­ja, merk­ki­kol­mi­koi­ta tai niin edel­leen. Täl­löin kui­ten­kin läh­de- ja koo­di­sa­no­jen mää­rä kas­vaa no­peas­ti hal­lit­se­mat­to­mak­si ja läh­de­sa­no­jen to­den­nä­köi­syys­ja­kau­ma muut­tuu ta­paus­koh­tai­sek­si. Esi­mer­kik­si vii­den mer­kin jo­no ”koodi” esiin­tyy jois­sa­kin suo­men­kie­li­sis­sä teks­teis­sä pal­jon useam­min kuin jois­sa­kin toi­sis­sa. Sik­si on ke­hi­tet­ty mui­ta koo­de­ja, ku­ten Lem­pel–Ziv–Welch.

In­for­maa­tion pak­kaa­mi­nen

In­for­maa­tion pak­kaa­mi­ses­sa myös läh­de­sa­nat ovat Σ*:n al­kioi­ta. Ta­voit­tee­na on koo­da­ta läh­de­vies­ti­nä ole­va merk­ki­jo­no si­ten, et­tä koo­dat­tu merk­ki­jo­no oli­si mah­dol­li­sim­man ly­hyt.

Jo­kai­nen pak­kaus­me­ne­tel­mä voi­daan hel­pos­ti muun­taa sel­lai­sek­si, et­tä se ei pi­den­nä mi­tään merk­ki­jo­noa enem­män kuin yh­den mer­kin. Näin se käy!Ole­tim­me, et­tä aak­kos­tos­sa on ai­na­kin kak­si merk­kiä. Ol­koot ne ’0’ ja ’1’. Ol­koon σ al­ku­pe­räi­nen merk­ki­jo­no ja ρ sen koo­dat­tu ver­sio. Jos |ρ| ≥ |σ|, niin pa­lau­te­taan ”0”σ, muu­toin pa­lau­te­taan ”1”ρ. Toi­sin sa­noen, koe­te­taan jos­ko koo­daa­mi­nen ly­hen­täi­si merk­ki­jo­noa. Jos kyl­lä, pa­lau­te­taan koo­dat­tu merk­ki­jo­no ja jos ei, niin pa­lau­te­taan al­ku­pe­räi­nen merk­ki­jo­no. Eteen li­sä­tään ’1’ tai ’0’ ker­to­maan, kum­mal­la ta­val­la pa­lau­tet­tu merk­ki­jo­no pi­tää tul­ki­ta. Jos ihan tark­ko­ja ol­laan, niin täl­lai­sis­sa poh­din­nois­sa täy­tyy ot­taa huo­mioon eräs asia. En us­kal­la jät­tää si­tä ko­ko­naan mai­nit­se­mat­ta, kos­ka yk­si ta­pa tuot­taa huu­haa­tu­lok­sia on unoh­taa se. Se on kui­ten­kin niin vä­hä­mer­ki­tyk­sel­li­nen ja toi­saal­ta kons­ti­kas, et­tä mai­nit­sen sen vain täs­säAl­ku­pe­räi­nen­kin merk­ki­jo­no täy­tyy esit­tää si­ten, et­tä sen lop­pu­koh­ta voi­daan tun­nis­taa. Käy­tän­nös­sä tä­hän­kin käy­te­tään etu­lii­te­koo­dia. Esi­mer­kik­si C:ssä merk­ki­jo­non si­säi­nen esi­tys­ta­pa päät­tyy ai­na merk­kiin, jon­ka bit­ti­ku­vio on 00000000, ei­kä se merk­ki voi esiin­tyä merk­ki­jo­non merk­ki­nä. C++:ssa merk­ki­jo­non si­säi­sen esi­tys­ta­van voi tä­män on­gel­man nä­kö­kul­mas­ta aja­tel­la al­ka­van tie­dol­la, kuin­ka pit­kä merk­ki­jo­no on (vaik­ka to­del­li­suu­des­sa nä­mä tie­dot ei­vät ole muis­tis­sa pe­räk­käin).. Täs­tä nä­kö­kul­mas­ta on tär­keää, et­tä jos al­ku­pe­räi­set merk­ki­jo­not on esi­tet­ty etu­lii­te­koo­dil­la ja al­ku­pe­räi­nen pak­kaus­me­ne­tel­mä on etu­lii­te­koo­di, niin myös äs­kei­nen enin­tään yh­del­lä pi­den­tä­vä koo­di …on etu­lii­te­koo­di. Mi­kään al­ku­pe­räi­se­nä pa­lau­tet­tu ei voi ol­la koo­dat­tu­na pa­lau­te­tun ai­to al­ku­osa ei­kä päin­vas­toin, kos­ka toi­set al­ka­vat ’0’:lla ja toi­set ’1’:llä. Mi­kään al­ku­pe­räi­se­nä pa­lau­tet­tu ei voi ol­la toi­sen al­ku­pe­räi­se­nä pa­lau­te­tun ai­to al­ku­osa, kos­ka al­ku­pe­räi­nen esi­tys­ta­pa oli etu­lii­te­koo­di, ja sa­man yh­den mer­kin (täs­sä ta­pauk­ses­sa ’0’) li­sää­mi­nen eteen ei tu­hoa etu­lii­te­koo­di­omi­nai­suut­ta. Sa­man­kal­tai­nen pe­rus­te pä­tee koo­dat­tu­na pa­lau­tet­tui­hin.

Sa­tun­nai­sis­sa merk­ki­jo­nois­sa jo­kai­nen merk­ki on yh­tä to­den­nä­köi­nen riip­pu­mat­ta sii­tä, mi­tä merk­ke­jä on tul­lut si­tä en­nen. Sik­si lau­set­ta 1 voi käyt­tää. Se ker­too, et­tä mi­kään koo­di ei voi kes­ki­mää­rin ly­hen­tää sa­tun­nai­sia merk­ki­jo­no­ja. Edel­lä näim­me, et­tä voim­me kui­ten­kin yrit­tää jo­tain koo­dia niin et­tä on­nis­tu­nees­ta yri­tyk­ses­tä saam­me yh­tä merk­kiä vail­le täy­den hyö­dyn, ja epäon­nis­tu­nees­ta yri­tyk­ses­tä mak­sam­me vain yh­den mer­kin ver­ran. Se on hy­vin mo­nia käy­tän­nön tar­pei­ta aja­tel­len mi­tä­tön li­sä­hin­ta, jo­ten tut­kim­me het­ken, oli­si­ko tä­mä hyö­dyl­li­nen kei­no toi­si­naan ly­hen­tää sa­tun­nai­sia merk­ki­jo­no­ja.

Täl­tä kan­nal­ta on tär­keää ym­mär­tää kak­si asiaa, jot­ka kos­ke­vat kaik­kia koo­de­ja, siis ei pel­käs­tään etu­lii­te­koo­de­ja. Niis­tä en­sim­mäi­nen on jo mai­nit­tu ja jäl­kim­mäis­tä kä­sit­te­lem­me seu­raa­vak­si:

• Eri läh­de­sa­noil­la täy­tyy ol­la eri koo­di­sa­nat.
• Jos va­li­taan mi­kä ta­han­sa merk­ki­jo­no kaik­kein ly­hyim­piä lu­kuun ot­ta­mat­ta, niin si­tä olen­nai­ses­ti ly­hyem­piä merk­ki­jo­no­ja on hy­vin pal­jon vä­hem­män kuin sen pi­tui­sia merk­ki­jo­no­ja.

Jäl­kim­mäi­sen ha­vain­nol­lis­ta­mi­sek­si ole­tam­me, et­tä ha­luam­me ly­hen­tää joi­ta­kin merk­ki­jo­no­ja 10 % ja hy­väk­sym­me sen, et­tä koo­dim­me ei ky­ke­ne esit­tä­mään mui­ta merk­ki­jo­no­ja lain­kaan. Etu­lii­te­koo­dien ta­pauk­ses­sa, jot­ta ly­hen­net­ty­jä merk­ki­jo­no­ja oli­si käy­tet­tä­vis­sä mah­dol­li­sim­man pal­jon, nii­den on ol­ta­va sa­man­pi­tui­set. Las­ku­jen hel­pot­ta­mi­sek­si ole­tam­me en­sin, et­tä Σ = {’0’, ’1’, …, ’9’}. Sil­loin eri­lai­sia 10 merk­kiä pit­kiä merk­ki­jo­no­ja on näin mon­ta10¹⁰ = 10 000 000 000 kap­pa­let­ta ja 10 % ly­hyem­piä eli 9 merk­kiä pit­kiä näin mon­ta10⁹ = 1 000 000 000 kap­pa­let­ta. Jäl­kim­mäi­nen lu­ku on näin mon­ta10 % edel­li­ses­tä. Teem­me sa­man las­kel­man muu­ta­mal­le muul­le merk­ki­jo­no­jen pi­tuu­del­le.

pi­tuus	kap­pa­let­ta	pi­tuus	kap­pa­let­ta	osuus
20	näin mon­ta1020	18	näin mon­ta1018	%1
30	näin mon­ta1030	27	näin mon­ta1027	%0,1
100	näin mon­ta10100	90	näin mon­ta1090	%0,000 000 01
10n	näin mon­ta1010n	9n	näin mon­ta109n	% 100 ⋅  109n 1010n = 100 ⋅ 10−n = 102−n

Ole­tam­me sit­ten, et­tä mer­kit ovat ta­vu­ja. Jos al­ku­pe­räis­ten merk­ki­jo­no­jen pi­tuus on 10, niin niis­tä noin 0,4 % voi­daan esit­tää koo­dil­la, jos­sa jo­kai­sen koo­di­sa­nan pi­tuus on 9. Tau­lu­kos­sa on tä­mä ja muu­ta­ma muu tu­los. Älä las­ke mii­nus­ta it­sel­le­si, vaik­ka ylei­sen kaa­van joh­ta­mi­nen ei on­nis­tui­si­kaan.

pi­tuus	pi­tuus	osuus
10	9	0,4 %
20	18	0,0015 %
100	90	0,000 000 000 000 000 000 000 1 %
10n	9n	näin mon­ta % 100 ⋅  |Σ|9n |Σ|10n = 100 ⋅ |Σ|−n = 100 ⋅ 256−n

Siis ly­hen­tä­mi­nen c mer­kil­lä vä­hen­tää merk­ki­jo­no­jen mää­rää niin pal­jon, et­tä vä­hen­net­ty mää­rä saa­daan ker­to­mal­la al­ku­pe­räi­nen mää­rä lu­vul­la |Σ|^−c. Ly­hen­tä­mi­nen 10 pro­sen­til­la tar­koit­taa, et­tä c = …0,1n, mis­sä n on al­ku­pe­räi­nen pi­tuus.. Jos |Σ| = 256, niin 10 % ly­hyem­piä merk­ki­jo­no­ja riit­tää suun­nil­leen 0,574ⁿ osal­le al­ku­pe­räi­siä merk­ki­jo­no­ja. Tä­mä lu­ku pie­ne­nee hy­vin no­peas­ti, kun n kas­vaa.

Sa­man­kal­tai­nen tu­los voi­daan joh­taa myös sil­lä ole­tuk­sel­la, et­tä kaik­ki tiet­tyä ra­jaa ly­hyem­mät merk­ki­jo­not ovat käy­tet­tä­vis­sä. Tark­ka kaa­va on han­ka­la, mut­ta jos Σ on iso (ja var­sin­kin jos myös n on iso), niin merk­ki­jo­no­ja, joi­den pi­tuus on kor­kein­taan n − c, on suun­nil­leen |Σ|^−c ker­taa nii­den merk­ki­jo­no­jen mää­rä, joi­den pi­tuus on täs­mäl­leen n. Ker­roin on siis sa­ma kuin äs­ken, mut­ta nyt se on vain li­ki­mää­räi­ses­ti pä­te­vä. Tä­mä ar­vio heit­tää enin­tään 10 % kun |Σ| > 10.

Ol­koon va­lit­tu mi­kä ta­han­sa hä­viö­tön pak­kaus­me­ne­tel­mä. Edel­lä ol­leis­ta lu­vuis­ta voi ar­va­ta ja kaa­vois­ta voi las­kea täs­mäl­li­ses­ti, et­tä to­den­nä­köi­syys sil­le, et­tä se pys­tyy ly­hen­tä­mään sa­tun­nai­ses­ti va­lit­tua vaik­ka­pa 1000 merk­kiä pit­kää ta­vu­jo­noa edes 10 % on ker­ta­kaik­ki­sen mi­tät­tö­män pie­ni, ja to­den­nä­köi­syys pie­ne­nee vie­lä sii­tä­kin si­tä mu­kaa kuin ta­vu­jo­non pi­tuus kas­vaa. Pit­kän sa­tun­nai­sen merk­ki­jo­non olen­nai­nen ly­he­ne­mi­nen ei siis ole täy­sin mah­do­ton­ta, mut­ta on niin har­vi­nais­ta, et­tä sil­lä ei ole käy­tän­nös­sä mi­tään mer­ki­tys­tä. Toi­si­naan tä­mä il­mais­taan ly­hye­nä väit­tee­nä, jo­ka ei ole ma­te­maat­ti­sen tark­ka, mut­ta on käy­tän­nön tar­pei­ta aja­tel­len tot­ta:

Sa­tun­nais­ta da­taa ei voi pa­ka­ta hä­viöt­tö­mäs­ti.

Kui­ten­kin mo­nen­lais­ta da­taa pys­ty­tään käy­tän­nös­sä pak­kaa­maan tun­tu­vas­ti. Se pe­rus­tuu kol­meen asiaan.

• Osa pak­kaus­me­ne­tel­mis­tä hä­vit­tää in­for­maa­tio­ta. Esi­mer­kik­si ku­vis­ta voi­daan pois­taa pal­jon in­for­maa­tio­ta il­man et­tä ih­mi­nen huo­maa olen­nais­ta eroa. Ohei­sis­ta lin­keis­tä saa sa­man ku­van pa­kat­tu­na eri mää­rään ta­vu­ja. Lin­kin lu­ku il­moit­taa pa­ka­tun tie­dos­ton koon ta­vui­na.  156 708  68 984  41 863  29 841  23 319  21 084
• Mo­net tie­don esi­tys­ta­vat hyö­dyn­tä­vät käy­tet­tä­vis­sä ole­vis­ta eri­lai­sis­ta ta­vuis­ta vain osan. Esi­mer­kik­si vaik­ka useim­mat mil­jar­dia pie­nem­mät lu­vut käyt­tä­vät nu­me­ro­mer­keil­lä ’0’, ’1’, …, ’9’ esi­tet­ty­nä näin mon­tayh­dek­sän merk­kiä, tie­to­ko­neen si­säi­ses­sä esi­tyk­ses­sä ne vie­vät vain nel­jä ta­vua. Si­säi­nen esi­tys­ta­pa hyö­dyn­tää täy­si­mää­räi­ses­ti sen, et­tä yk­si ta­vu voi esit­tää näin mon­ta256 eri vaih­to­eh­toa, mut­ta nu­me­ro­mer­keil­lä esit­tä­mi­nen käyt­tää niis­tä vain kym­men­tä. Tä­mä ei ole sy­väl­li­nen il­miö, mut­ta otin sen esil­le, kos­ka se se­lit­tää osan sii­tä käy­tän­nön ha­vain­nos­ta, et­tä pak­kaa­mi­nen usein pie­nen­tää tie­dos­to­ko­koa huo­mat­ta­vas­ti.
• Pa­kat­ta­vat tie­dos­tot ei­vät yleen­sä ole sa­tun­nai­sia, vaan niis­sä on pal­jon ra­ken­net­ta tai sään­nön­mu­kai­suut­ta. Tyy­pil­li­ses­sä suo­men­kie­li­ses­sä teks­ti­tie­dos­tos­sa vä­li­lyön­ti esiin­tyy pal­jon useam­min kuin ’k’, ja ’k’ esiin­tyy pal­jon useam­min kuin ’q’. Tyy­pil­li­ses­sä C++-oh­jel­mas­sa ”while” esiin­tyy useam­min kuin ”hwile”. Pak­kaus­me­ne­tel­mä voi esi­mer­kik­si tun­nis­taa usein esiin­ty­viä merk­ki­jo­no­ja ja an­taa niil­le ly­hyi­tä koo­di­sa­no­ja.

Seu­raa­vas­sa lu­vus­sa viem­me tie­dos­tos­sa si­jait­se­vaan sään­nön­mu­kai­suu­teen pe­rus­tu­van pak­kaa­mi­sen aja­tuk­sen ää­rim­mil­leen. Si­tä en­nen: olet suun­nit­te­le­mas­sa hy­vis­ten val­tion puo­lus­tus­voi­mil­le vies­tin­tä­jär­jes­tel­mää. Tie­dot pi­tää sa­la­ta, jot­ta vi­hol­li­nen ei voi­si nii­tä lu­kea, ja pa­ka­ta, kos­ka tie­don­siir­to­ka­pa­si­teet­ti on so­ta­ti­lan­tees­sa niuk­ka. En­sin kan­nat­taa teh­dä tä­mäpa­ka­ta ja vas­ta sit­ten teh­dä se toi­nen täs­tä syys­täSa­laa­mi­sen jäl­keen vies­ti näyt­tää sa­tun­nai­sel­ta, jo­ten pak­kaa­mi­nen ei pys­ty si­tä ly­hen­tä­mään..

Kol­mo­go­rov-komp­lek­si­suus

Toi­vot­ta­vas­ti hok­sa­sit, et­tä

w&6.$e!'*<&1jd5ä&>5ä}ä`'n1!,72-e,
+%+e*(+&b+>&+st5~4,%9t;m

Vies­tis­sä voi to­ki oi­keas­ti­kin ol­la mer­ki­tyk­se­tön­tä si­säl­töä. Esi­mer­kik­si täs­tä löy­tyy his­to­rial­li­ses­ti mer­kit­tä­vä jul­kai­su skan­nat­tu­na. Sen etu­si­vul­la ole­vat tah­rat ei­vät ole jul­kai­sun kir­joit­ta­jan tar­koit­ta­maa in­for­maa­tio­ta, mut­ta ovat sil­ti tie­dos­toa kä­sit­te­le­vien tie­to­ko­neoh­jel­mien nä­kö­kul­mas­ta in­for­maa­tio­ta. Täl­lais­ta häi­riö­in­for­maa­tio­ta sa­no­taan ko­hi­nak­si. Pa­laam­me ko­hi­naan myö­hem­min. Tä­män lu­vun ajan ole­tam­me, et­tä tar­kas­tel­ta­vis­sa merk­ki­jo­nois­sa ei ole ko­hi­naa.

Merk­ki­jo­no ”+++++++++” ei si­säl­lä ko­hi­naa ja on yh­tä pit­kä kuin ”lentokone”, mut­ta in­tu­i­tio sa­noo, et­tä sii­nä on vä­hem­män in­for­maa­tio­ta kuin merk­ki­jo­nos­sa ”lentokone”. Sa­moin in­tu­i­tio sa­noo, et­tä kir­jat ”As­te­rix His­pa­nias­sa” ja ”As­te­rix Bri­tan­nias­sa” si­säl­tä­vät yh­teen­sä enem­män in­for­maa­tio­ta kuin kak­si kap­pa­let­ta kir­jaa ”As­te­rix His­pa­nias­sa” si­säl­tää yh­teen­sä.

In­tu­i­tiol­le so­pi­si in­for­maa­tio­kä­si­te, jon­ka mu­kaan merk­ki­jo­non si­säl­tä­män in­for­maa­tion mää­rä voi ol­la pal­jon merk­ki­jo­non pi­tuut­ta pie­nem­pi. Kut­sum­me tä­tä hy­po­teet­tis­ta in­for­maa­tio­kä­si­tet­tä i-in­for­maa­tiok­si. Merk­ki­jo­non ly­he­ne­mi­nen hä­viöt­tö­mäs­sä pak­kaa­mi­ses­sa oli­si mah­dol­lis­ta vain sil­loin, kun …merk­ki­jo­no si­säl­tää pi­tuut­taan vä­hem­män i-in­for­maa­tio­ta. Pa­ka­tun merk­ki­jo­non pi­tuus oli­si ai­na vä­hin­tään …al­ku­pe­räi­sen merk­ki­jo­non i-in­for­maa­tion mää­rä. I-in­for­maa­tion tark­ka mää­rä oli­si ly­hyim­män sel­lai­sen merk­ki­jo­non pi­tuus, jok­si al­ku­pe­räi­nen merk­ki­jo­no voi­daan pa­ka­ta kun pak­kaus­me­ne­tel­män saa va­li­ta va­paas­ti.

Ihan täl­lai­se­naan tä­tä aja­tus­ta ei voi to­teut­taa sik­si, et­tä mi­kä ta­han­sa merk­ki­jo­no saa­daan pa­kat­tua yh­teen merk­kiin va­lit­se­mal­la so­pi­va pak­kaus­me­ne­tel­mä. Joh­dan­nok­si sii­hen näy­tän esi­mer­kin toi­ses­ta, sa­man­kal­tai­ses­ta il­miös­tä. Jol­let vie­lä ko­keil­lut, mi­tä edel­lä ol­lut sa­laus­ko­ne te­kee merk­ki­jo­nol­le ”+++++++++”, niin ko­kei­le nyt! vih­je 1Älä syö­tä sa­laus­ko­neel­le ”-merk­ke­jä, kos­ka ne ei­vät ole osa merk­ki­jo­noa vaan vain osoit­ta­vat sen al­ku- ja lop­pu­koh­dan. Syö­tä pel­käs­tään +-merk­ke­jä. vih­je 2Ko­kei­le myös suu­rem­pia mää­riä +-merk­ke­jä.

On­gel­ma on siis se, et­tä jo­kai­sen merk­ki­jo­non i-in­for­maa­tion mää­räk­si tu­lee yk­si merk­ki, kos­ka jo­kai­sel­le merk­ki­jo­nol­le voi­daan kek­siä pak­kaus­me­ne­tel­mä, jol­la juu­ri se merk­ki­jo­no pak­kau­tuu yh­teen merk­kiin. Muu­ta ei tar­vi­ta kuin so­pia, et­tä ”\\” tar­koit­taa tä­tä’\’ merk­kiä , ”\”” tar­koit­taa tä­tä’”’ merk­kiä, ”\!” tar­koit­taa tä­tä’!’ merk­kiä, ja ”!” tar­koit­taa esi­mer­kik­si jon­kin tu­hat­si­vui­sen kir­jan ko­ko si­säl­töä. Tä­mä voi­daan vält­tää so­pi­mal­la, et­tä i-in­for­maa­tion mää­rään tu­lee las­kea pait­si pa­kat­tu merk­ki­jo­no, myös se me­ne­tel­mä, jol­la pa­kat­tu merk­ki­jo­no pu­re­taan.

Mi­ten pur­ku­me­ne­tel­män i-in­for­maa­tion mää­rä mi­ta­taan? Pur­ka­mi­sen to­teut­ta­van ali­oh­jel­man pi­tuu­del­la! Jos jär­ke­vä tu­hat­si­vui­nen kir­ja on pa­kat­tu yh­dek­si mer­kik­si ’!’ edel­lä ku­va­tul­la ta­val­la, niin kir­jan si­säl­tö jou­du­taan jok­seen­kin var­mas­ti kir­joit­ta­maan pur­ku­ali­oh­jel­maan. Täl­löin tun­tui­si epä­rei­lul­ta las­kea kir­jan i-in­for­maa­tion mää­räk­si yk­si merk­ki, mut­ta ot­ta­mal­la pur­ku­ali­oh­jel­man pi­tuus mu­kaan las­kel­maan tu­lee sii­hen kir­joi­tet­tu kir­jan si­säl­tö otet­tua asian­mu­kai­ses­ti huo­mioon.

Pa­kat­tua merk­ki­jo­noa ei enää tar­vi­ta eril­li­se­nä kä­sit­tee­nä täs­tä syys­täSe voi­daan si­säl­lyt­tää ali­oh­jel­maan merk­ki­jo­no­va­kio­na.. Sil­loin syn­tyy ali­oh­jel­ma, jo­ka ei ota mi­tään syöt­teek­seen ja jo­ka pa­laut­taa sen merk­ki­jo­non, jon­ka i-in­for­maa­tion mää­räs­tä on ky­se. Ku­ten kaik­ki ali­oh­jel­mat, pa­lau­tet­tuaan tuo­tok­sen­sa tä­mä­kin ali­oh­jel­ma py­säh­tyy.

Tä­mä lä­hes­ty­mis­ta­pa kat­taa pait­si kaik­ki tun­ne­tut ja tun­te­mat­to­mat pak­kaus- ja pur­ku­ali­oh­jel­mi­na to­teu­tet­ta­vis­sa ole­vat pak­kaus­me­ne­tel­mät, myös kaik­ki muut­kin ta­vat tuot­taa ky­sees­sä ole­va merk­ki­jo­no ali­oh­jel­mal­la. Olem­me mo­ti­voi­neet seu­raa­van kä­sit­teen.

Mää­ri­tel­mä Merk­ki­jo­non σ Kol­mo­go­rov-komp­lek­si­suus K(σ) on ly­hyim­män sel­lai­sen ali­oh­jel­man pi­tuus, jo­ka tyh­jäl­lä syöt­teel­lä pa­laut­taa σ:n.

Tä­mä mää­ri­tel­mä ei pois­ta täy­sin si­tä on­gel­maa, et­tä jon­kin pit­kän merk­ki­jo­non komp­lek­si­suu­des­ta teh­dään kei­no­te­koi­ses­ti pie­ni, sil­lä oh­jel­moin­ti­kie­les­sä voi ol­la val­miik­si mää­ri­tel­ty merk­ki­jo­no­va­kio paksu_kirja, jo­ka si­säl­tää jon­kin tu­hat­si­vui­sen kir­jan si­säl­lön. Täl­lai­sia ei kui­ten­kaan voi ol­la mi­ten pal­jon ta­han­sa, sil­lä va­kioil­la täy­tyy ol­la ni­met ja ly­hyet ni­met lop­pu­vat jos­sain vai­hees­sa kes­ken. Tär­keäm­pää on, et­tä ku­ten koh­ta ha­vain­nol­lis­te­taan esi­mer­keil­lä, tä­mä kä­si­te tuot­taa pie­nen komp­lek­si­suu­den kai­kis­sa niis­sä ta­pauk­sis­sa, jois­sa merk­ki­jo­non voi ”re­hel­li­sin kei­noin” tii­vis­tää ly­hyek­si.

Kol­mo­go­rov-komp­lek­si­suus siis riip­puu va­li­tun oh­jel­moin­ti­kie­len yk­si­tyis­koh­dis­ta. Al­la ole­vis­sa konk­reet­ti­sis­sa lu­vuis­sa mit­ta­yk­sik­kö­nä on ta­vu, ja ta­vu­jen mää­rä on las­ket­tu UTF-8-koo­da­tus­ta esi­tyk­ses­tä. Jot­ta ei lip­sah­det­tai­si edel­lä mai­ni­tun huu­haan puo­lel­le, merk­ki­jo­non pi­tuus ole­te­taan tul­kit­ta­van jon­kin etu­lii­te­koo­di­esi­tyk­sen mu­kaan. Mer­kit­sem­me sel­lai­se­naan ali­oh­jel­maan kir­joi­tet­tua merk­ki­jo­noa ”…σ…” ja nu­me­ro­mer­keil­lä kir­joi­tet­tua luon­nol­lis­ta lu­kua ”…n…”. Jos n = 314 ja σ = ”314”, niin se­kä return ”…σ…” et­tä return ”…n…” tar­koit­taa return ”314”.

K ∈ Σ*
ρ := ”…σ…”
return ρρ

Kuin­ka olen­nai­nen edel­lä saa­tu konk­reet­ti­nen lu­ku­ar­vo 35 on? vas­tausEi yh­tään olen­nai­nen. Se riip­puu va­li­tus­ta oh­jel­moin­ti­kie­les­tä. Esi­tän konk­reet­ti­sia lu­ku­ar­vo­ja vain sel­ven­tääk­se­ni si­tä, et­tä jois­sa­kin koh­dis­sa jo­kin ar­vo to­del­la on konk­reet­ti­nen ar­vo, ei­kä esi­mer­kik­si jon­kin b-ni­mi­sen, ali­oh­jel­mas­sa si­jait­se­van muut­tu­jan si­säl­tö.

Merk­ki­jo­non li­sää­mi­nen it­sen­sä pe­rään siis li­sää sen Kol­mo­go­rov-komp­lek­si­suut­ta vain hie­man, sen si­jaan et­tä kak­sin­ker­tais­tai­si sen. Tä­mä täs­mää sii­hen in­tu­i­tioon, et­tä kak­si kap­pa­let­ta sa­maa kir­jaa ei si­säl­lä enem­pää tie­toa kuin yk­si kap­pa­le. Tar­vi­taan kui­ten­kin kir­jan pak­suu­des­ta riip­pu­ma­ton mää­rä li­sä­in­for­maa­tio­ta sa­no­maan ”ja sa­ma kir­ja toi­seen ker­taan”.

Edel­lä pii­le­väs­ti ole­tin, et­tä merk­ki­jo­non Kol­mo­go­rov-komp­lek­si­suus on enin­tään suun­nil­leen sen pi­tuus. Va­li­tet­ta­vas­ti unoh­din to­dis­taa sen, kun laa­din tä­män teh­tä­vän. Sik­si si­nä jou­dut paik­kaa­maan huo­li­mat­to­muu­te­ni ja to­dis­ta­maan sen it­se.

Lau­se 2 On ole­mas­sa sel­lai­nen va­kio b, et­tä jo­kai­sel­la σ ∈ Σ* pä­tee K(σ) ≤ |σ| + b.

To­dis­tus. Ohei­nen ali­oh­jel­ma pa­laut­taa σ:n. Sen pi­tuus on |σ| + 24 ta­vua.

K ∈ Σ*
return ”…σ…” □ 

Seu­raa­va ali­oh­jel­ma pa­laut­taa √2:n de­si­maa­li­esi­tyk­ses­tä alun ja n de­si­maa­lia. Sen pi­tuus on n:n esit­tä­mi­seen tar­vit­ta­vien nu­me­ro­merk­kien mää­rä + 227 ta­vua. Niin­pä on ole­mas­sa sel­lai­nen va­kio b, et­tä √2:n de­si­maa­li­esi­tyk­sen n + 2 merk­kiä pit­kän al­ku­osan Kol­mo­go­rov-komp­lek­si­suus on enin­tään log n + b, mis­sä lo­ga­rit­mi on 10-kan­tai­nen.

K ∈ Σ*
m := 2
k := 1
σ := ”1,”
for i := 1 to ”…n…” do
   m := 100 ⋅ m
   k := 10 ⋅ k + 9
   c := ’9’
   while k ⋅ k > m do
      k := k − 1
      c := c − 1
   σ := σc
return σ

Osoi­ta, et­tä kun n > 0, niin merk­ki­jo­non, jos­sa on n ’a’:ta pe­räk­käin ei­kä muu­ta, Kol­mo­go­rov-komp­lek­si­suus on enin­tään log n + b, mis­sä lo­ga­rit­mi on 10-kan­tai­nen ja b on jo­kin va­kio. vas­tausAl­la ole­va ali­oh­jel­ma pa­laut­taa ky­sees­sä ole­van merk­ki­jo­non. Sen pi­tuus on 76 + ⌊log n⌋ + 1 ≤ log n + 77 ta­vua, mis­sä ⌊x⌋ tar­koit­taa suu­rin­ta ko­ko­nais­lu­kua, jo­ka on enin­tään x, ja ⌊log n⌋ + 1 on n:n esit­tä­mi­ses­sä tar­vit­ta­vien nu­me­ro­merk­kien mää­rä.

K ∈ Σ*
σ := ””
for i := 1 to ”…n…” do
   σ := σ”a”
return σ

Osoi­ta, et­tä joil­la­kin n:n ar­voil­la merk­ki­jo­non, jos­sa on n ’a’:ta pe­räk­käin ei­kä muu­ta, Kol­mo­go­rov-komp­lek­si­suu­del­le voi­daan an­taa pal­jon pie­nem­pi ylä­ra­ja kuin edel­lä. vas­tausTäl­le on lo­put­to­mas­ti toi­nen tois­taan dra­maat­ti­sem­pia rat­kai­su­ja. Esi­mer­kik­si al­la ole­van ali­oh­jel­man pi­tuus on enin­tään log n + b, mis­sä lo­ga­rit­mi on 10-kan­tai­nen ja b on jo­kin va­kio. (Edel­lä käy­te­tyl­lä las­ku­ta­val­la b = 124.) Se pa­laut­taa 10ⁿ ’a’:ta pe­räk­käin. Jos syn­ty­vän merk­ki­jo­non pi­tuut­ta mer­ki­tään m:llä, niin al­la ole­van ali­oh­jel­man pi­tuus on log log m + b.

K ∈ Σ*
σ := ””
m := 1
for i := 1 to ”…n…” do
   m := 10 ⋅ m
for i := 1 to m do
   σ := σ”a”
return σ

Rank­ka rat­kea­mat­to­muus­tu­los

Edel­lä näim­me, et­tä K(σ):n voi­daan to­dis­taa ole­van enin­tään an­ne­tun lu­vun n suu­rui­nen an­ta­mal­la syöt­tee­tön ali­oh­jel­ma, jon­ka pi­tuus on n ja jo­ka pa­laut­taa σ:n. Kuin­ka voi­daan to­dis­taa, et­tä merk­ki­jo­non Kol­mo­go­rov-komp­lek­si­suus on vä­hin­tään jon­kin lu­vun suu­rui­nen? Han­kim­me seu­raa­vak­si hie­man tun­tu­maa tä­hän ky­sy­myk­seen.

Kun edel­lä ol­lees­sa esi­mer­kis­sä va­li­taan n = 99, niin saa­daan 126 merk­kiä pit­kä ali­oh­jel­ma, jo­ka pa­laut­taa merk­ki­jo­non, jos­sa on 1 000 000 ⋯ 000 (99 nol­laa) ’a’-kir­jain­ta pe­räk­käin. Siis hy­vin­kin pit­kän merk­ki­jo­non Kol­mo­go­rov-komp­lek­si­suus voi ol­la pie­ni.

Toi­saal­ta näim­me aiem­min, et­tä an­net­tua pi­tuut­ta olen­nai­ses­ti ly­hyem­piä merk­ki­jo­no­ja on hy­vin pal­jon vä­hem­män kuin sen pi­tui­sia merk­ki­jo­no­ja. Esi­mer­kik­si enin­tään 126 merk­kiä pit­kiä merk­ki­jo­no­ja on hy­vin pal­jon vä­hem­män kuin esi­mer­kik­si 10⁹⁹ merk­kiä pit­kiä tai edes 150 merk­kiä pit­kiä merk­ki­jo­no­ja. Sii­tä voi­daan täl­lä ta­val­laMerk­ki­jo­no­ja, joi­den pi­tuus on olen­nai­ses­ti pie­nem­pi kuin |σ|, on hy­vin pal­jon vä­hem­män kuin merk­ki­jo­no­ja, joi­den pi­tuus on |σ|. Ali­oh­jel­mat ovat merk­ki­jo­no­ja. An­ne­tun pi­tui­sia ali­oh­jel­mia on kor­kein­taan sa­man ver­ran kuin sen pi­tui­sia merk­ki­jo­no­ja. Sik­si vain hy­vin pie­nel­le osal­le |σ|:n pi­tui­sia merk­ki­jo­no­ja riit­tää sen pa­laut­ta­va ali­oh­jel­ma, jo­ka on olen­nai­ses­ti σ:aa ly­hyem­pi.

Toi­saal­ta Lau­seen 2 mu­kaan K(σ) ei voi ol­la olen­nai­ses­ti suu­rem­pi kuin |σ|. pää­tel­lä, et­tä mel­kein jo­kai­sen merk­ki­jo­non σ Kol­mo­go­rov-komp­lek­si­suus on suun­nil­leen |σ|.

Sa­maan tyy­liin Enin­tään 100 merk­kiä pit­kiä merk­ki­jo­no­ja on ää­rel­li­nen mää­rä, jo­ten enin­tään 100 merk­kiä pit­kiä ali­oh­jel­mia on ää­rel­li­nen mää­rä. voi­daan pää­tel­lä, et­tä mel­kein jo­kai­sen merk­ki­jo­non Kol­mo­go­rov-komp­lek­si­suus on suu­rem­pi kuin 100. Mut­ta mi­ten voi­daan to­dis­taa jos­tain ni­men­omai­ses­ta merk­ki­jo­nos­ta, et­tä juu­ri sen Kol­mo­go­rov-komp­lek­si­suus on suu­rem­pi kuin 100?

Voi­daan­ko Kol­mo­go­rov-komp­lek­si­suu­dek­si to­dis­taa vä­hin­tään n aja­mal­la kaik­ki si­tä ly­hyem­mät syöt­teet­tö­mät ali­oh­jel­mat ja to­tea­mal­la, et­tä mi­kään niis­tä ei pa­lau­ta ky­sees­sä ole­vaa merk­ki­jo­noa? vas­tausJos n on jo­tain ra­jaa isom­pi, niin ei voi­da. Osa ali­oh­jel­mis­ta ei py­säh­dy ja py­säh­ty­mi­sen tes­taa­mi­nen on rat­kea­ma­ton­ta, jo­ten tar­peek­si isol­la n jou­du­taan lo­put­to­mas­ti odot­ta­maan jon­kin ali­oh­jel­man val­mis­tu­mis­ta il­man et­tä voi­daan saa­da sel­vil­le, et­tä se ei val­mis­tu kos­kaan.

Jäl­leen ker­ran tu­los­ta voi­daan ma­ni­pu­loi­da oh­jel­moin­ti­kie­len va­lin­nal­la. Jos ali­oh­jel­mas­ta pa­luun avain­sa­nak­si vaih­de­taan return:n si­jaan ”nyt on ai­ka tul­la ulos täs­tä ali­oh­jel­mas­ta, sil­lä las­kut on saa­tu val­miik­si, ja täs­sä­pä on­kin nät­ti merk­ki­jo­no, jo­ka tä­ten pa­lau­te­taan ali­oh­jel­man tu­lok­se­na”, niin jo­kai­nen ali­oh­jel­ma on yli 100 merk­kiä pit­kä, jo­ten jo­kai­sen merk­ki­jo­non Kol­mo­go­rov-komp­lek­si­suus on yli 100. Sik­si em­me joh­da tu­los­ta, jos­sa on konk­reet­ti­nen lu­ku­ar­vo, vaan ai­noas­taan tu­lok­sen, jos­sa sa­no­taan, et­tä jo­kin lu­ku­ar­vo on ole­mas­sa.

Muis­sa suh­teis­sa tu­lok­sem­me on­kin hy­vin vah­va. Se kat­taa kaik­ki rea­lis­ti­set kei­not yrit­tää osoit­taa, et­tä an­ne­tun merk­ki­jo­non Kol­mo­go­rov-komp­lek­si­suus on vä­hin­tään an­ne­tun suu­rui­nen. Se kat­taa ma­te­maat­ti­sen to­dis­ta­mi­sen, syöt­teet­tö­mien ali­oh­jel­mien koe­aja­mi­sen ja niin edel­leen. Se kat­taa myös kei­not, jot­ka ei­vät vas­taa ”kyl­lä” tai ”ei”, vaan ”kyl­lä” tai ”en tie­dä”.

Mää­ri­tel­mä Ai­na­kin-to­dis­ta­ja on ali­oh­jel­ma, jo­ka ot­taa syöt­teek­si merk­ki­jo­non σ ja luon­nol­li­sen lu­vun n, ja py­säh­tyy pa­laut­taen T tai F. Jos se pa­laut­taa T, niin K(σ) ≥ n.

Ai­na­kin-to­dis­ta­ja py­säh­tyy kai­kil­la syöt­teil­lä. Jos se pa­laut­taa F, niin K(σ) saa ol­la mi­tä ta­han­sa.

Ku­ten teh­tä­väs­sä Li­sää py­säh­ty­mi­sen tes­taa­mi­ses­ta to­det­tiin, al­la ole­vaa ali­oh­jel­maa tois­tu­vas­ti kut­su­mal­la saa­daan kaik­ki merk­ki­jo­not ly­him­mäs­tä al­kaen. Ha­vain­nol­li­suu­den vuok­si ali­oh­jel­ma käyt­tää merk­ke­jä ’0’ ja ’9’, mut­ta ne edus­ta­vat aak­kos­ton pie­nin­tä ja suu­rin­ta merk­kiä. Yk­kö­sen li­sää­mi­nen merk­kiin tuot­taa aak­kos­jär­jes­tyk­sen mu­kaan seu­raa­van mer­kin.

seuraava(σ ∈ Σ*) ∈ Σ*
i := 1
while i ≤ σ.pituus ∧ σ[i] = ’9’ do
   σ[i] := ’0’
   i := i + 1
if i ≤ σ.pituus then
   σ[i] := σ[i] + 1
else
   lisää σ:n loppuun '0'

Ol­koon ainakin ai­na­kin-to­dis­ta­ja. Tar­kas­te­lem­me al­la ole­van mal­lin mu­kais­ta ali­oh­jel­maa κ_n, jos­sa while-sil­mu­kan eh­dos­sa esiin­ty­vä lu­ku on n > 0. Ha­vain­nol­li­suu­den vuok­si n on kir­joi­tet­tu myös ali­oh­jel­man ni­meen, mut­ta ole­tam­me, et­tä to­del­li­ses­ta ali­oh­jel­mas­ta se puut­tuu. Pä­tee |κ_n| = |κ₁| + ⌊log n⌋.

κ₂₃ ∈ Σ*
σ := ””
while ¬ ainakin(σ, 23) do
   σ := seuraava(σ)
return σ

Jos n on tar­peek­si iso, niin n > |κ₁| + log n. Ole­te­taan, et­tä ainakin(σ, n) pa­laut­taa T sel­lai­sel­la n ai­na­kin yh­del­lä σ. Sil­loin κ_n pa­laut­taa merk­ki­jo­non σ, jol­le K(σ) ≥ n while-sil­mu­kan eh­don vuok­si. Toi­saal­ta K(σ) ≤ |κ_n| = |κ₁| + ⌊log n⌋, kos­ka κ_n pa­laut­taa σ:n. Siis K(σ) ≥ n > |κ₁| + log n ≥ |κ_n| ≥ K(σ), jo­ten K(σ) > K(σ), mi­kä on mah­do­ton­ta. Tä­mä ris­ti­rii­ta osoit­taa, et­tä jos n on tar­peek­si iso, niin ainakin(σ, n) ei voi mil­le­kään merk­ki­jo­nol­le σ pa­laut­taa tie­toa, et­tä K(σ) ≥ n.

Olem­me to­dis­ta­neet seu­raa­van.

Lau­se 3 Jo­kai­sel­le ai­na­kin-to­dis­ta­jal­le ainakin on ole­mas­sa sel­lai­nen va­kio c, et­tä jo­kai­sel­le σ ∈ Σ* ja jo­kai­sel­le n ≥ c ainakin(σ, n) pa­laut­taa F.

Täs­tä voi­daan joh­taa tu­lok­sia, jot­ka ker­to­vat, et­tä vaik­ka mel­kein jo­kai­sen merk­ki­jo­non Kol­mo­go­rov-komp­lek­si­suus on suun­nil­leen sa­ma kuin merk­ki­jo­non pi­tuus, mi­kään kei­no ei pys­ty to­dis­ta­maan kuin poik­keus­ta­pauk­sis­sa, et­tä jon­kin ni­men­omai­sen merk­ki­jo­non Kol­mo­go­rov-komp­lek­si­suus on suun­nil­leen sa­ma kuin merk­ki­jo­non pi­tuus. Al­la on muo­toil­tu täs­mäl­li­ses­ti yk­si täl­lai­nen väi­te.

Lau­se 4 Jo­kai­nen ai­na­kin-to­dis­ta­ja pa­laut­taa T vain ää­rel­li­sel­le mää­räl­le syöt­tei­tä, jois­sa n ≥ 0,9|σ|.

To­dis­tus.Jos |σ| ≥ 0,111… ⋅ c ja n ≥ 0,9|σ|, niin n ≥ 0,9 ⋅ 0,111… ⋅ c = c. Sil­loin lau­seen 3 mu­kaan ai­na­kin-to­dis­ta­ja pa­laut­taa F. Sik­si n ≥ 0,9|σ| ja tu­los T ovat yh­tä­ai­kaa mah­dol­li­set vain, jos |σ| < 0,111… ⋅ c. Sel­lai­sia σ on ää­rel­li­nen mää­rä, kos­ka jo­kai­sel­le luon­nol­li­sel­le lu­vul­le k pä­tee, et­tä enin­tään k:n pi­tui­sia merk­ki­jo­no­ja on ää­rel­li­nen mää­rä. □ 

Pu­hu­mi­sen hel­pot­ta­mi­sek­si sa­nom­me epä­täs­mäl­li­ses­ti, et­tä merk­ki­jo­non Kol­mo­go­rov-komp­lek­si­suus on suu­ri, jos ja vain jos se on ai­na­kin suun­nil­leen sa­ma kuin merk­ki­jo­non pi­tuus, ja pie­ni muu­toin. Ta­pauk­set, jois­sa merk­ki­jo­non Kol­mo­go­rov-komp­lek­si­suus on pal­jon suu­rem­pi kuin merk­ki­jo­non pi­tuus, ei­vät ole kiin­nos­ta­via, kos­ka …Lau­se 2 ker­too, et­tä nii­tä ei ole.

Täl­la pu­he­ta­val­la il­mais­tu­na tä­mäMel­kein jo­kai­sen merk­ki­jo­non σ Kol­mo­go­rov-komp­lek­si­suus on suun­nil­leen |σ|. ai­kai­sem­min ker­rot­tu to­si­asia ja Lau­se 4 ker­to­vat, et­tä mel­kein kaik­kien merk­ki­jo­no­jen Kol­mo­go­rov-komp­lek­si­suus on suu­ri, mut­ta mi­kä ta­han­sa ta­pa yrit­tää to­dis­taa merk­ki­jo­non Kol­mo­go­rov-komp­lek­si­suus suu­rek­si epä­on­nis­tuu mel­kein kai­kis­sa ta­pauk­sis­sa (on­nis­tuu vain ää­rel­li­ses­sä mää­räs­sä ta­pauk­sia). Meil­lä on siis väi­te, jo­ka on mel­kein kai­kil­le merk­ki­jo­noil­le tot­ta, mut­ta on mel­kein kai­kil­le merk­ki­jo­noil­le mah­do­ton to­dis­taa to­dek­si!

Vie­lä pa­hem­paa:

Lau­se 5 Ol­koon c ku­ten Lau­sees­sa 3. Mel­kein jo­kai­sen merk­ki­jo­non Kol­mo­go­rov-komp­lek­si­suus on vä­hin­tään c, mut­ta mis­tään merk­ki­jo­nos­ta ei voi to­dis­taa, et­tä sen Kol­mo­go­rov-komp­lek­si­suus on vä­hin­tään c.

To­dis­tus.Kos­ka al­le c:n pi­tui­sia merk­ki­jo­no­ja on vain ää­rel­li­nen mää­rä, on al­le c:n pi­tui­sia ali­oh­jel­mia vain ää­rel­li­nen mää­rä, jo­ten vain ää­rel­li­sen mää­rän merk­ki­jo­no­ja Kol­mo­go­rov-komp­lek­si­suus on al­le c. Tä­mä on mi­tä­tön osuus kai­kis­ta merk­ki­jo­nois­ta, kos­ka kaik­kiaan nii­tä on ää­ret­tö­mäs­ti. Lau­se 3 sa­noo, et­tä mis­tään merk­ki­jo­nos­ta ei voi to­dis­taa, et­tä sen Kol­mo­go­rov-komp­lek­si­suus on vä­hin­tään c. □ 

Lo­puk­si

Edel­li­sen lu­vun tu­los tar­koit­taa, et­tä pää­sään­töi­ses­ti ei ole mi­tään kei­noa ol­la var­ma, et­tä merk­ki­jo­non Kol­mo­go­rov-komp­lek­si­suus ei ole pie­nem­pi kuin pie­nin sil­le jo tun­net­tu ala­ra­ja. Jos tie­de­tään kei­no tuot­taa σ ly­hyel­lä ali­oh­jel­mal­la, niin tie­de­tään, et­tä σ:n Kol­mo­go­rov-komp­lek­si­suus on enin­tään ali­oh­jel­man pi­tui­nen. Jos myö­hem­min löy­tyy ly­hyem­pi ali­oh­jel­ma, niin ar­vio pa­ra­nee. Jol­lei löy­dy, niin yleen­sä jää avoi­mek­si, on­ko ar­vio jo pa­ras mah­dol­li­nen. An­ne­tun merk­ki­jo­non Kol­mo­go­rov-komp­lek­si­suu­des­ta ei siis pää­sään­töi­ses­ti voi­da tie­tää mi­tään muu­ta kuin et­tä se on kor­kein­taan jo­kin tun­net­tu lu­ku.

Vie­lä on kä­sit­te­le­mät­tä se mah­dol­li­suus, et­tä merk­ki­jo­nos­sa on mu­ka­na ko­hi­naa. Ko­hi­nai­sen merk­ki­jo­non Kol­mo­go­rov-komp­lek­si­suus koos­tuu hyö­ty­in­for­maa­tion Kol­mo­go­rov-komp­lek­si­suu­des­ta ja ko­hi­nan Kol­mo­go­rov-komp­lek­si­suu­des­ta. Kos­ka ko­hi­na on usein täy­sin tai mel­ko sa­tun­nais­ta ja …sa­tun­nais­ta da­taa ei voi pa­ka­ta hä­viöt­tö­mäs­ti, pää­sään­tö on, et­tä ko­hi­nai­sen merk­ki­jo­non Kol­mo­go­rov-komp­lek­si­suus mää­räy­tyy ko­hi­nan ei­kä hyö­ty­in­for­maa­tion Kol­mo­go­rov-komp­lek­si­suu­den mu­kaan.

Sik­si ko­hi­nai­nen da­ta pak­kau­tuu yleen­sä huo­nos­ti hä­viöt­tö­mil­lä pak­kaus­me­ne­tel­mil­lä. Hä­viöl­li­set pak­kaus­me­ne­tel­mät pois­ta­vat ko­hi­naa te­hok­kaas­ti, ja si­ten mah­dol­lis­ta­vat esi­mer­kik­si va­lo­ku­vien pak­kaa­mi­sen huo­mat­ta­vas­ti pie­nem­pään ti­laan kuin ka­me­ra­ken­nol­ta tu­le­va raa­ka­da­ta vie. Va­li­tet­ta­vas­ti ne sa­mal­la pois­ta­vat myös hyö­ty­in­for­maa­tio­ta.

Ku­ten mo­nes­ta muus­ta­kin ai­hees­ta, täs­tä­kin ai­hees­ta tie­de­tään pal­jon enem­män kuin täl­lai­nen ly­hyt vep­pi­si­vu voi ker­toa. Li­sä­tie­toa voi met­säs­tää vaik­ka avain­sa­noil­la ”algorithmic information theory”.