Kolika je vrednost recimo Tolstojevog romana Ana Karenjina? Nesvrsishodno i podrobno opisivanje okoline i likova sa kojima ne delim apsolutno ni jednu zajednicku stvar su ako pitate mladog mene, gimnazijalca kojem je to bila obavezna literatura, izuzetno mala. Drugima ta, na moje iskreno zaprepašćenje, vrednost nije bila infinitezimalna ... ali što se kaže o subjektivnim doživljajima i neukusu se ne raspravlja.
 |
| Illustration by BIG MOUTH for Quanta Magazine |
Zamislimo inicijalno prazan rečnik. Pretpostavimo da neki roman započinje sa sledećom rečju od 16 slova
\[
\begin{array}
A & A & A & A & B & B & A & B & A & A & B & A & A & A & B & A & B \\
& 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16\\
\end{array}
\]
Ovaj primer preuzet iz Ref [1]. Drugi red predstavlja prosto numerisanje slova zbog preglednosti, jer se kasnije pozivamo na njih pojedinačno. Konstrukciju i popunjavanje rečnika započinjemo na sledeći način. Počinjemo sa najkraćom mogućem reči i to sdesna koja trenutno ne postoji u rečniku i sastoji se samo od jednog slova. To slovo u ovom slučaju je slovo \(A \). To omogućava da prethodnu reč napišemo kao
\begin{align}
A \cdot AABBABAABAAABAB \notag
\end{align}
i trenutno naš rečnik se sastoji od jednog elementa i to mozemo da zapišemo kao \( \{ A\} \). Nadalje sledeće i drugo slovo reči je ponovo \( A \). Ali \( A \) vec postoji u rečniku \( \{ A\} \), stoga prelazimo na treće slovo u kombinaciji sa drugim i imamo \( AA \). Unutar \( AA \) već postoji koren reči koja postoji u rečniku i to je \( A \). Stoga \( AA \) ne predstavlja novu reč. Nadalje kombinujući drugo, treće i četvrto slovo dobijamo \( AAB .\) Ovo predstavlja novu reč zato što nismo u mogućnosti da je oformimo isključivo od reči u trenutnom rečniku. Nadalje zato imamo
\begin{align}
A \cdot AAB \cdot BABAABAAABAB \notag
\end{align}
i rečnik sada čini set \( \{ A, AAB \} \). Peto slovo je slovo \( B \) koje zapravo već postoji trenutno u rečniku kao izolovni 'pattern' (obrazac ili kako već treba prevesti) stoga on kao takav ne ulazi u rečnik. Stoga moramo da posmatramo peto i šesto slovo zajedno tj. \( BA \). Ova kombinacija ne postoji kao obrazac u dosadašnjem rečniku i dobijamo
\begin{align}
A \cdot AAB \cdot BA \cdot BAABAAABAB \notag
\end{align}
Ponavljajući ovaj process dolazimo do krajnjeg zapisa ove reči
\begin{align}
A \cdot AAB \cdot BA \cdot BAA \cdot BAAA \cdot BAB \notag
\end{align}
sa odgovarajući rečnikom \( \{ A, AAB, BA, BAA, BAA, BAB\} \). Uspeli smo da svedemo datu reč na 6 delova i stoga obeležavamo \( c = 6 \).
Moguće je raditi sa nulama i jedinicam umesto slovima. Recimo neki primeri su
\begin{align}
&1011010 \to 1 \cdot 0 \cdot 11 \cdot 010 \quad {\rm gde } \quad c = 4 \notag\\
&0010 \to 0 \cdot 01 \cdot 0 \quad {\rm gde} \quad c = 3 , \quad {\rm Ref.} \quad [2] \notag \\
&000000... \to 0 \cdot 0000... \quad {\rm gde} \quad c = 2, \quad {\rm Ref.} \quad [2] \notag \\
&01010101... \to 0 \cdot 1 \cdot 010101... \quad {\rm gde} \quad c = 3, \quad {\rm Ref.} \quad [2] \notag
\end{align}
Kolmogorova informaciona komplesnost (KC) se može sad izračunati ukoliko \( c \) normalizujemo sa odgovarajućem brojem. Taj broj predstavlja maksimalnu kompleksnost koji neki beskonačan niz može da ima. Recimo ukoliko uzmemo neki iracionaln broj i gledamo u njegove decimale. Te decimale ukoliko pretvorimo u niz nula i jedinica možemo očekivati da broj obrazaca a samim tim i rečnik da bude beskonačno dugačak jer nema ponavljanja i periodičnih struktura u decimalama.
U orignalnom radu Ref. [1] je pokazano da taj maksimalan broj iznosi
\begin{align}
{\rm norm} = \dfrac{N}{\log_{2}{N}},
\end{align}
gde je \( N \) dužina stringa. Sada praktično da bi izračunali kompleksnost imamo
\begin{align}
{\rm KC } = \dfrac{c}{{\rm norm}} = \dfrac{c}{N} \dfrac{\log_{10}{N}}{\log_{10} {2}}.
\end{align}
Predstavimo sad sledeće primere
\( \bullet \) AAABBABAABAAABAB
\begin{align}
{\rm KC} = \dfrac{6}{16} \dfrac{\log_{10}{16}}{\log_{10} {2}} = 1.5,
\end{align}
\( \bullet \) 1011010
\begin{align}
{\rm KC} = \dfrac{4}{7} \dfrac{\log_{10}{7}}{\log_{10} {2}} = 1.6042,
\end{align}
\( \bullet \) 0010
\begin{align}
{\rm KC} = 1.5,
\end{align}
\( \bullet \) 000000000000000 (x15 nula)
\begin{align}
{\rm KC} = 0.52091,
\end{align}
\( \bullet \) 00000000000000000000000000000 (x30 nula)
\begin{align}
{\rm KC} = 0.3271.
\end{align}
Treba naglasiti da ukoliko je neki niz potpuno i sasvim random (kao tipa decimale irracionalnih brojeva) i onda \( {\rm KC} \to 1 \). Ukoliko je neki niz potpuno trivijalan (kao recimo samo niz nula i jedinica kao u datom primeru) \( {\rm KC} \to 0 \) teži nuli, tj. u slučaju beskonačnih nizova vrednost kompleksnosti se kreće izmedju 0 i 1. Vidimo zapravo da ukoliko je niz zapravo konačne dužine onda te vrednosti izlaze iz ovog domena. Svakako ovaj algoritam omogućava usporedbu nizova različite dužine čak i sa normiranjem na beskončnost kao što smo do sad prezentovali.
U praksi, kad posmatramo neki eksperimentalni odziv ili izlaz iz simulacije potrebno je pretvoriti originalni niz u nule i jedinice (moze i u A, B) nekim pravilom. To pravilo može biti recimo da uporedimo pojedinačne unose sa srednjom vrednošču ukupnog niza. Ukoliko je pojedinačni unos manji od srednje vrednosti onda dodelimo nulu, dok je veći onda jedinicu i na taj način svaki niz možemo svesti i propustiti kroz šake.
Reference:
1. Lempel, A. and Ziv, J. On the Complexity of Finite Sequences. IEEE Transactions on Information Theory 22, 75–81 (1976).
2. Kaspar, F. and Schuster, H. G. Easily calculable measure for the complexity of spatiotemporal patterns. Phys. Rev. A 36, 842–848 (1987).
Comments
Post a Comment