Przeskocz do treści

Delta mi!

Loading

Co to jest?

Migawki informatyczne

Algorytmy strumieniowe

Wojciech Czerwiński

o artykule ...

  • Publikacja w Delcie: lipiec 2017
  • Publikacja elektroniczna: 30 czerwca 2017
  • Autor: Wojciech Czerwiński
    Afiliacja: adiunkt, Instytut Informatyki, Uniwersytet Warszawski
  • Wersja do druku [application/pdf]: (49 KB)

W dzisiejszym świecie cyfrowym mamy do czynienia z olbrzymią ilością danych, wielu Czytelników słyszało zapewne modne ostatnio hasło "Big Data". I trzeba sobie z tym radzić, a problemy mogą pojawiać się w nieoczekiwanych miejscach. Przyzwyczajeni jesteśmy do myślenia, że programy mają pewne dane na wejściu i te dane są tam na stałe, program może je w dowolnym momencie przeczytać. Czasami jednak nie do końca przystaje to do rzeczywistości...

obrazek

Wyobraźmy sobie, że analizujemy kamerę online, która transmituje obraz 24 godziny na dobę i chcemy po miesiącu wydobyć pewne statystyki z tego, co nagrała. Możemy, oczywiście, zapisać całość na dysk i potem obliczyć to, co trzeba. Łatwo sobie jednak wyobrazić, że potrzeba na to wiele pamięci, którą niekoniecznie zamierzamy właśnie na to przeznaczać. Dobrze byłoby na bieżąco obliczać to, co chcemy, i nie zapisywać całego filmu - pamiętać tylko statystyki z przeszłości i uaktualniać je w czasie rzeczywistym. Podobne problemy spotykamy w wielu miejscach, gdy rozważamy duży strumień danych, przykładowo film lub dźwięk, ale również inne, jak ruch pakietów TCP/IP w sieci. Taka jest geneza powstania dziedziny algorytmów strumieniowych, czyli działających na strumieniu danych i obliczających na bieżąco pewne jego własności. Jej matematyczne podstawy są, moim zdaniem, wyjątkowo piękne.

Założymy, że nasz strumień danych to ciąg a1,...,am dla pewnego dużego |m oraz że ai ∈{1,...,n} dla każdego i. Niech mi będzie liczbą wystąpień liczby i w całym strumieniu. Naszym celem będzie obliczenie pewnych własności strumienia w pamięci istotnie mniejszej niż |𝒪(m).

Na początek przyjrzyjmy się następującej zagadce. Rozważmy strumień, w którym pewna wartość występuje więcej niż na połowie miejsc. Czyli istnieje i| takie, że mi Jak wtedy znaleźć i? Nie jest jasne, jak to zrobić bez trzymania aktualnych wartości mi dla wszystkich |i podczas przeglądania strumienia. Okazuje się, że działa algorytm naprawdę banalny. W każdej chwili pamiętamy parę liczb. Pierwsza liczba to kandydat na odpowiedź, a druga liczba to coś jakby jego przewaga nad resztą. Inicjalizujemy parę jako (0,0). Powiedzmy, że po przeczytaniu |a,...,a 1 j pamiętamy parę |(i,c). Są dwie możliwości. Jeśli c = 0, to po przeczytaniu |a j+1 ustawiamy parę na (a j+1,1). Jeśli natomiast c > 0, to rozważamy dwa przypadki. Jeżeli |a j+1 = i, to zwiększamy przewagę, czyli ustawiamy |(i,c + 1). Jeśli natomiast |a j+1 ≠i, to ustawiamy |(i,c − 1). Na końcu zwracamy pierwszy element z pary. Zauważmy jednak, że algorytm wcale nie trzyma prawdziwego dotychczasowego rekordzisty wraz z jego przewagą. Po przeczytaniu pierwszych sześciu elementów ciągu |1,1,1,2,2,2,3 będzie trzymał parę |(2,0), a więc po przeczytaniu ostatniego wyrazu parę (3,1). Dlaczego więc działa poprawnie? Przypomnijmy, że pewien element i występuje na więcej niż połowie miejsc. Niech wartość pary ( j,c) będzie równa c, o ile i = j oraz − c, o ile |i≠ j. Zauważmy, że napotkanie elementu i zawsze zwiększa o jeden wartość pary, a innego niż i - zmniejsza ją lub zwiększa o jeden. Na początku wartość pary to |0. Zatem po przeczytaniu całego ciągu wartość pary będzie dodatnia, czyli pierwszy jej element to faktycznie |i.

obrazek

Ważnej informacji o własnościach strumienia dostarczają liczby |Fk zdefiniowane jako  m P i 1m Dla k = 0 to liczba różnych elementów, dla |k = 1 to po prostu m, a dla k | = 2 jest to ważna miara równomierności występowania wartości w ciągu. Bardzo ładny i elegancki jest przybliżony algorytm liczenia wartości F 2 w pamięci jedynie 𝒪(log n + log m). My najpierw pokażemy, jak to zrobić w pamięci |𝒪(n + log m), co nie jest takie złe, bo to zwykle m jest olbrzymie, a n | może być niewielkie. Algorytm używa losowości. Dla każdego i | ∈{1,...,n} losujemy wartość |x ∈{ −1,1} i tak, że P(x = 1) = P(x =− 1) = 1/2 i i oraz losowania są niezależne. Na początek ustalamy licznik c na 0 i zaczynamy przeglądać strumień. Gdy czytamy element i, to zwiększamy licznik o |xi. Na końcu zwracamy c2, twierdząc, że jest to dobre przybliżenie F2. Algorytm prosty, ale dlaczego to w ogóle ma działać? Najpierw zauważmy, że każde |i zwiększyło wartość c o xi, czyli w sumie wszystkie i zwiększyły go o |ximi. A więc na końcu  n c | = P i 1ximi. Obliczmy wartość oczekiwaną |c2. Mamy

 n 2 n n E(c2) = E ⎛(Q x m ⎞= E ⎛ Q x xm = Q m ⎝ i 1 i ⎠ ⎝i, j 1 i j i, j 1

Zauważmy, że E(x x ) = 0, i j o ile tylko |i≠ j, bo |x i oraz x j są niezależne. A zatem

 n E(c2) = Q m2i i 1

I ten fakt wydaje się najciekawszy. Wypadałoby jeszcze wykazać, że błąd tego obliczenia (czyli wariancja) jest nie za duży. My tutaj jedynie podamy na wiarę, że Var(c2) ⩽F2 . 2 Ambitnych Czytelników zachęcamy do przerachowania. Błąd możemy łatwo zmniejszyć, uruchamiając 1000 takich samych algorytmów równocześnie, a na końcu uśredniając ich wyniki rezultat oznaczmy  -- |c2. Wówczas wartość oczekiwana się nie zmieni, a wariancja zmaleje 1000 razy. Przypomnijmy nierówność Czebyszewa: 2 −EX >t)⩽Var(X)/t |P( X dla dowolnego . X Dostajemy więc  -- |P( c2 − F2 > F2/10) ⩽ 1/10, czyli wynik wychodzi całkiem niezły.

Przypomnijmy, że nasz algorytm działa w pamięci 𝒪(n + log m), a jednak |n czasem może być duże. Liczba n bierze się stąd, że przez cały czas przeglądania strumienia pamiętamy n zmiennych xi. Wydaje się to nieuniknione przy tej technice. Okazuje się jednak, że stosunkowo łatwo można zamienić n na logn, używając bardzo pomysłowej metody. Przypomnijmy, jaka własność zmiennych xi była nam potrzebna. Mianowicie chcieliśmy, by E(xixj ) = 0 dla |i≠ j, czyli by były one parami niezależne. Przy szacowaniu wariancji przydaje się ponadto niezależność czwórkami, dzięki której wiele ze składników postaci E(xixj xkx ℓ) znika. Można skonstruować obiekt wielkości 𝒪(log n), z którego można wydobyć n zmiennych czwórkami niezależnych. My pokażemy jedynie, że da się tak zrobić dla zmiennych parami niezależnych. Zachęcamy Ambitnego Czytelnika do uogólnienia tego faktu. Dla uproszczenia załóżmy, że n = 2k− 1, w tym przypadku mamy k = 𝒪(log n). Wówczas pamiętamy k niezależnych zmiennych losowych y1,...,yk, takich, że |P(y = 1) = P(y = −1) = 1/2. i i Dla dowolnego niepustego podzbioru |S⊆ {1,...,k} definiujemy zmienną xS = Π i>Syi. Łatwo sprawdzić, że xS i xT istotnie są niezależne dla dwóch różnych zbiorów |S i T .

Algorytm obliczający przybliżoną wartość F2 został opublikowany w 1999 roku przez Alona (patrz też str. 8), Matiasa i Szegedego jako chyba najbardziej zaskakujący wynik ich przełomowej pracy. Praca ta położyła fundamenty pod bardzo szybko rosnącą dziedzinę algorytmów strumieniowych, a autorzy otrzymali prestiżową nagrodę Gödla.