sunnuntai 26. joulukuuta 2010

Sanoista mittaa

Salausten purkamisessa frekvenssianalyysi on tehokas työkalu. Syynä on se, että kielissä kirjaimet eivät ole yhtä yleisiä. Ja toisten kirjainten jälkeen ei ole aivan mitä tahansa kirjaimia. Toisin sanoen kielessä kirjaimet eivät ole toisistaan riippumattomia. Näin tekstiin syntyy redundanssia, joka eroaa satunnaisuudesta. Näihin tarttumalla analyysissä voidaan päästä eteenpäin. Jokaisella kielellä on hieman omanlaisensa kirjainyleisyys, joten frekvenssianalyysi voi ilman muuta taustainformaatiota kertoa jopa sen, mitä kieltä jokin salakielinen viesti on.

Viestin sisältöä voidaan tarkastella tietysti myös hajeen, entropian, kautta. Shannonin informaatioteoriassa tällä onkin suuri merkitys: Hän esittää että mitä suurempi entropia viestissä on, sitä satunnaisempi se on. Ja sitä enemmän se sisältää järjestystä. Tämä järjestys taas on informaatiota. Frekvenssianalyysi perustuu tietoon kielestä ; Kielellä on havaittu olevan tiettyjä lainomaisuuksia. Kielessä on järjestystä.

Salakielisen viestin purkamisessa "ilman avainta" tämä järjestys on kiinnostava löytää, koska se auttaa viestin purkamisessa.

Esimerkiksi suomen kielessä Q on sanoissa hyvin harvinainen kirjain. A on melko yleinen. Tästä saanee hyvän esimerkin siitä, mitä kävi kun pistin frekvenssianalyysin parista arpomastani bloggauksistani:

Toinen esimerkki on otettu tekemällä sama isommasta otoksesta. Tässä erottelin isot ja pienet alkukirjaimet. Ja koska isot kirjaimet näyttivät vaakaviivalla, tein kolmannen käyrän, jossa isojen ja pienten kirjainten erot on tasattu: Isot kirjaimet saivat painokertoimen, jonka kautta isojen ja pienten kirjainten keskiarvo pysyy samana. Näin sain aikaan näkyvän piikin, joka voi olla mielenkiintoinen. Näin ollen keltaisessa käyrässä on "isojen kirjainten määrä on yliedustunut" tunnetulla tavalla. Mutta samalla kirjainten esiintyvyysyleisyys tulee selvemmin esiin:Tämänkaltainen empiirinen tieto siitä, että eri merkit ovat tavallisempia auttaa viestien purkamisessa. Voidaan nimittäin arvata että viestissäkin luultavasti on yleisemmin jotain merkkiä kuin jotain toista.

Tätä voidaan kiertää monilla tavoilla salausjärjestelmissä. Itse asiassa hyvät salausmenetelmät pyrkivät tähän. Yksinkertaisia keinoja asiaan tunnetaan useitakin. Esimerkiksi kuuluisa mutta selvittämättä jäänyt sarjamurhaaja "ZODIAC -killer" käytti salaamisessaan menetelmää joka vaikeutti frekvenssianalyysiä ; Yleisille kirjaimille oli useampia symboleja joita käytettiin kirjaimen yhteydessä satunnaisesti. Näin yleinen merkki en antanut itseään ilmi. Viesti selvisikin "osittain arvaamalla" : Koodin purkanut ajatteli että sarjamurhaaja kirjoittaisi viesteihinsä usein lyhyehkön englannin kielen sanan "kill". Tämä viestin sisällön epäsatunnaisuus auttoi asiassa eteenpäin.

Tämä melko yksinkertainen esimerkki kertookin laajemmasta ilmiöstä : Tehokkaissa salausjärjestelmissäkin lopputuloksena on hajeen kasvua. Viestissä ei ole mitään arvattavaa säännönmukaisuutta joka tarjoaisi jonkun kikan johon koodinpurkaja voisi tarttua. Tämä on sinällään mielenkiintoinen yhteys, koska myös pakkausjärjestemissä syntyy suuri haje ; Syynä on se, että satunnaisuus tuottaa helposti sellaista jossa on "paljon rakennetta". Kun muistamme Shannonia, tämä voi tuntua ihmeelliseltä ; Satunnaisuushan kertoi juurikin informaation ja säännönmukaisuuksien puutteesta. Kuitenkin salaviestissä tuntuu olevan "merkitys".
1: Arkiajattelu ajaa tässä kohden siis harhaan. Sillä, mielenkiintoista kyllä, frekvenssianalyysi, jonka avulla saadaan kaivettua esiin vaikkapa salakielisenviestin merkitys, ei itse asiassa käsittele lainkaan merkitystä. Sen sijaan siinä katsotaan kielen rakennetta joka on induktiivisten tutkimusten avulla liitetty kieleen. Tämä ei ole sinällään yllättävää, koska merkitys on pohjimmiltaan mielivaltainen sopimus. Eri kielissä sama asia sisältää erilaisia viittauksia. "cat" ja "kissa" viittaavat samaan kohteeseen. Periaatteessa joku voisi aloittaa uuden kielen jossa merkkiyhdistelmä "koira" merkitsisi samaa kuin sana "kissa" suomen kielessä.
2: On hyvä muistaa että me kaikki myös pakkaamme esimerkiksi zippaamalla vaikkapa pelejä tai sähköpostiviestejä. Pakkaaminen johtaa viestin entropiatason nousuun, säännönmukaisuushan lisäsi entropiaa. Näin saadaan syntymään mielenkiintoinen viittaus algoritmiseen kompleksisuuteen.

Tässä kohden mukaan voidaan ottaa myös Zipfin laki. Sekin on hieman frekvenssianalyysin kaltainen. Siinä jos jonkin merkkijonon sisältö otetaan käsittelyyn, ja esiintymien todennäköisyys laitetaan Zipfin kaavioon, on satunnainen tulos vaakasuora; Toisin sanoen yksittäiset merkit tai vaikkapa merkkiyhdistelmät ovat kaikki suunnilleen yhtä yleisiä. Sen sijaan kielissä syntyy jonkinlainen laskeva käyrä, joka näyttää että merkit eivät ole satunnaisia. Tämän huomaa vaikkapa tekemällä yleisyyspainotuksen aineistolle, josta tein aikaisemmin frekvenssianalyysin:Kuten blogauksissani, on kielissä yleisemminkin tämäntapainen yleisyysjärjestys. Tälläisen jakauman löytyminen vihjaa siis siitä, että niissä voisi ajatella olevan informaatiota, joka voi olla vaikkapa viesti.

Tämä on empiirinen havainto kielistä. Sen keksi ensin Harvardin kielitieteilijä George Kingsley Zipf. Idea tiivistyy seuraavaan kaavaan : jos kielessä on jokin n:nneksi käytetyin sana, merkki tai jonkin muun mitattava yksikkö kuten vaikkapa äänne, on niillä erikoinen käyttötiheys. Zipfin mukaan luonnollisessa kielessä on käänteisesti verrannollinen lukuun n. Zipfin laki on empiirinen tulos, eikä teoreettinen malli. Se ei itse asiassa sano että kielessä olisi pakko olla tämänlainen rakenne.
1: Kielitieteellinen tutkimus vuodelta 2005 nimeltään "True reason for Zipf's law in language" esitti huomion, että yleisimmin analysoidut kielet, kuten englanti, ranska ja muut kielet noudattivat Zipfin jakaumaa. Sen sijaan huomattiin että kiinan kieli onkin tässä kohden poikkeus ; Kiinan kieli lakkasi noudattamasta Zipfin jakaumaa Qin -dynastian jälkeen. Syyksi tutkimus esitti sen, että uusien kiinan sanamerkkien luominen ja merkistön satunnainen muuttuminen on hitaampaa. Näin ollen kielen satunnaismuutokset johtaisivat Zipfin lain syntymiseen.
___1.1: Tämä onkin hyvin mielenkiintoinen huomio, sillä tiedetään että Zipfin laki tosiaankin liittyy muuhunkin, kuin kieleen ; Esimerkiksi kaaosteoriassa on huomattu että esimerkiksi iteratiivisissa järjestelmissä zipfin jakaumia syntyy; Kun järjestelmän lopputulos on "seuraavan kierroksen alku", syntyy juuri tämänlaisia rakenteita. Näin ollen jakauma on myös itseorganisaatioon kuuluva rakenne. Tästä päästään esimerkiksi kieleen : Esimerkiksi geenitutkimuksessa "Linguistic Features of Noncoding DNA Sequences" vuodelta 1994 osoitettiin, että Tilke-DNA noudattaa Zipfin lakia, ja varsinaiset toimivat geenit eivät. Intelligent Designin kannattaja ja YEC - Kreationisti Salvador Cordova innostui löydöstä, koska ei muistanut tätä rakenteen synnyn osuutta asiaan.
_____1.1.1: Salvador Cordovan harmiksi tämäkin on itse asiassa malliesimerkki siitä, miten viestien tunnistaminen muusta ei suinkaan perustu minkäänlaiseen lainomaisuuksien ja satunnaisuuden eliminointiin. Toki esimerkiksi GMT1 -havainnon säännönmuaksiuus tulkittiin säännönmukaisuutensa vuoksi viestiksi, ja tästä tulkinnasta luovuttiin koska havaittiin että rytmisesto toimivat pulsarit olivat niiden lähde, eikä mikään avaruussivilisaatio. Mutta tämä on "systemaattisen virheen" karsimista. Itse tunnistus siis perustuukin täysin tiettyyn positiiviseen rakenteeseen, ei eliminointiin. Eliminointi on varmistamiseen liittyvä huolellisuuskysymys. Ei gravitonienkaan metsästys perustu kaikkien värähtelyjen eliminointiin, vaikka hiukkaskiihdyttimen rakentamisen ja kalibroinnin kohdalla onkin korostettu sitä, miten muut vaikutukset, kuten vaikkapa junien aikaansaama värinä, saadaan minimoitua ja huomioitua.

Itse asiassa kielellä on kompleksisuuden ja lainomaisuuden lisäksi yksi hyvin tärkeä rakenne. Se on "ennustettavan pätkän pituus". Laurance Doyle, joka on SETI -tutkija on esimerkiksi tuttu niille, joita kiinnostaa ikään kuin ääntelyn lauserakenne. Hän nimittäin auttoi todistamaan sen, että delfiinit kommunikoivat keskenään. Hän havaitsi että delfiinit ymmärtävät "5 sanan" kokonaisuuksia, lauseita, kun taas ihmisten kirjakielissä on 8-10 sanan mittaisia lauseita. Tämä tuo esiin uuden tarkastelutason ; Tässä ideana on nimittäin se, että siinä missä frekvenssianalyysi tai Zipfin lain hakeminen laskee koko merkkijonon jakaumaa, voidaan asiaa tarkastella eri mittaisina pätkinä. Jokin viesti voi olla melkoisen ennustettava vaikkapa 5 merkin pätkissä, mutta pidemmät osat ovat toisistaan riippumattomia. Jos tilastollisesti voidaan arvata mikä sana on viiden merkin jälkeen, mutta jos ei ole mitenkään ennustettavissa mikä sana toistuu jotain kuuden äänteen jakson jälkeen, se viittaa siihen että vastaanottajan ei tarvitse käsitellä viittä merkkiä pidempiä yhteyksiä. Ajatus voi olla hankalasti hahmotettava, mutta se muuttuu kenties ymmärrettäväksi jos huomataan että pelkkää pakattavuutta ja kompleksisuutta katsoessa katsotaan koko merkkijonon kokonaisuustarkastelua, kun taas tässä kohden tarkastellaan "viestin ennustettavuutta" eri mittaisissa pätkissä ja katsotaan minkälaisia eroja näissä "tarkastelun mitoissa" syntyy keskenään.

Ei kommentteja: