Mapowanie stringów na inne obiektu

10.11.2009
TrudnośćTrudnośćTrudność

Z pewnych względów nie mogłem odpowiedzieć na to pytanie przed CEPCem, ale teraz postaram się zrewanżować.

W niektórych zadaniach chcielibyśmy przyporządkować napisom jakieś obiekty. Czyli chcielibyśmy mieć coś co w STLu nazwalibyśmy map<string,T> gdzie T to typ obiektów jakie chcemy przyporządkować stringom.
Nie omawialiśmy jeszcze tego jak jest zaimplementowany map<KeyT,ValT>, ale w gruncie rzeczy jest do binarne drzewo wyszukiwań (czerwono-czarne), w którym każdy węzeł przechowuje jakąś parę <KeyT,ValT>, oraz ma dwa wskaźniki na (być może puste) poddrzewa, w których są odpowiednio elementy o mniejszych i większych kluczach.
Wyszukiwanie w takiej strukturze elementu o kluczu k polega na tym, że podążając od korzenia w dół drzewa, porównujemy zawsze klucz k, z kluczem przechowywanym w danym wierzchołku -- jeśli są równe, to super, a jeśli nierówne, to wiemy do którego poddrzewa zejść rekurencyjnie.
Jak łatwo się przekonać, czas znalezienia odpowiedniego węzła zależy od pewnych czynników:
- głębokość drzewa
- czas potrzebny na porównanie dwóch elementów typu KeyT
Sam fakt, że map używa drzew zrównoważonych, daje nam gwarancję, że głębokość drzewa jest O(lg n), gdzie n to liczba elementów w kolekcji.
Niestety map, nie ma za bardzo wpływu na to, jak zaimplementowany jest  "bool operator < (KeyT x, KeyT y)" -- na to wpływ mamy już tylko my.
Zauważmy, że porównywanie leksykograficzne dwóch stringów trwa pesymistycznie O(m), gdzie m to długość krótszego z nich.
Oznacza to, że map<string,T> to nie jest najlepszy sposób na zaimplementowanie słownika, bo wymagać może aż m lg n operacji, aby coś w nim znaleźć.

Z nie do końca jasnych powodów map<KeyT,ValT> jest jednym z ulubionych narzędzi po jakie sięga wiele osób na zawodach, mimo, że tak naprawdę wcale nie jest im do szczęścia potrzebny. Główną zaletą map'a jest bowiem to, że trzyma elementy w posortowany sposób, co pozwala po nich iterować wg kolejności kluczy (w naszym przypadku: alfabetycznie) a także wykonywać operację lower_bound/upper_bound (czyli znajdowania najmniejszego klucza, ciut większego od tego, o który pytamy i viceversa). Karą jaką płacimy za te (najczęściej niepotrzebne) operacje jest lg n  razy większy koszt operacji odczytu i zapisu. Istnieje jednak sporo alternatyw.

Po pierwsze, jeśli nie interesuje nas porządek kluczy, a jedynie powiązanie między kluczami i wartościami, to potrzebujemy tak naprawdę czegoś co nazywa się unordered_map, a zaimplementowane jest np. jako hash_map. Takie struktury danych zaimplementowane są nie jako drzewa, ale jako tablice hashujące, zajmują zatem po pierwsze mniej miejsca, a po drugie zapis i odczyt wymaga tylko O(1) operacji liczenia hasha i O(1) operacji porównań kluczy. Jako, że porównywanie stringów i liczenie funkcji hashującej z tychże trwają O(m), gdzie m to długość stringa, to uzyskujemy strukturę lg n razy szybszą niż map<string,T>.

Być może jednym z powodów dla których hash_map / unordered_map nie są zbyt często używane, jest to, że ich implementacje nie są do końca ustandaryzowane, a co za tym idzie udokumentowane, a co najgorsze są trochę kiepsko zaimplementowane. Aby zrozumieć główny mankament, trzeba trochę wiedzieć czym jest tablica hashująca. W dużym skrócie i najprostszej wersji, tablica hashująca to coś co ma n "kubełków", i daną o kluczu k, umieszczamy w kubełku hash(k)%n, gdzie hash to jakaś fajna funkcja hashująca. Mankamentem widzianych przeze mnie implementacji jest to, że liczą owo %n używając operacji modulo, co strasznie spowalnia cały algorytm -- trzeba pamietać, że dzielenie to niestety jedna z najwolniejszych operacji. Znacznie sprytniej byłoby mieć zawsze n=2^k, dla pewnego k, wtedy zamiast liczyć hash(x)%n, wystarczyłoby liczyć hash(x)&((1<<k)-1), co jest znacznie szybsze.

Kolejnym sprytnym pomysłem jest nieco "pomóc" operatorowi porównania stringów. Użyłem raz z powodzeniem tej techniki, ale trzeba mieć świadomość, że jest to dość niebezpieczny hack, bo bardzo zależy od (niezdefiniowanej) implementacji map<,>. Pomysł polega na tym, że do konstruktora map, można przekazać swój własny obiekt porównywujący klucze. Jeśli wiemy (a na 99% tak jest), że map szukając czegoś w drzewie będzie wykonywał porównania z kolejnymi wierzchołkami na ścieżce od korzenia w dół, to możemy zaobserwować, pewne zjawisko. Mianowicie jeśli wierzchołki na ścieżce wyszukiwania podzielimy na dwie grupy: te przy których skręciliśmy w prawo i te przy których skręciliśmy w lewo, to łatwo się przekonać, że w obrębie tych grup elementy są posortowane dokładnie w takiej kolejności w jakiej je odwiedzamy. Mówiąc prościej: gdy idziemy wzdłuż ścieżki wyszukiwania to kolejny napotykany wierzchołek jest:
- albo równy szukanemu
- albo większy od szukanego i jednocześnie najmniejszy ze wszystkich, które dotąd mijaliśmy i były większe
- albo mniejszy od szukanego i jednocześnie największy ze wszystkich, które dotąd mijaliśmy i były mniejsze.
Warto to sobie chyba chociaż raz narysować na kartce i przekontemplować.
Istotny jest następujący wniosek z powyższych obserwacji:
- kolejne klucze spotykane na ścieżce wyszukiwania zawsze należą do przedziału (F,T), gdzie F to wartość ostatnio mijanego w prawo klucza, a T to wartość klucza który mijaliśmy w lewo jako ostatni. F oraz T mogą być równe odpowiednio -INF bądź +INF, jeśli jeszcze nie skręciliśmy w prawo, bądź w lewo.
Co nam to daje?
Jeśli F i T są stringami, które mają długi wspólny początek, np. F="kaloryfer", zaś T="kalosze", to wiemy, że zarówno element, którego szukamy, jak i wszystkie elementy w poddrzewie, które właśnie przeglądamy muszą się zaczynać od liter "kalo". Oznacza to, że porównywanie stringów możemy zacząć od 5 litery, bo pierwsze 4 na pewno są równe. Im głębiej w drzewie będziemy i im bardziej ciasny przedział (F,T), tym szybsze porównania możemy wykonywać.

Oczywiście to jest tylko heurystyka, a więc algorytm, który fajnie działa tylko dla niektórych zapytań (głównie dla tych, do których dochodzi się "zygzakiem").
Prowadzi jednak do kilku innych fajnych struktur danych.

Po pierwsze patricia-tree. Główny koncept w tym drzewku to taki, że w każdym węźle chcielibyśmy mieć dwoje dzieci i wiedzieć dokładnie na której pozycji one się różnią. Wyobraźmy sobie nasze stringi jako ciągi bitów (a zatem string o długości m znaków, to np. 8m bitów). Albo wszystkie stringi są identyczne, albo umiemy wskazać pierwszy od lewej bit (pozycję), na której nie wszystkie się zgadzają. Niech tą pozycją będzie p. Drzewko budujemy tak, żeby w korzeniu pamietać liczbę p, zaś w lewym poddrzewie wszystkie słowa mające na pozycji p bit równy 0, zaś w prawym poddrzewie, te słowa które mają bit równy 1.
Jeśli wszystkie stringi są identyczne, to znaczy, że mamy liść, a więc specjalny typ wierzchołka, w którym przechowujemy cały string.
Wyszukiwanie w takim drzewie jest całkiem proste -- z korzenia root, idziemy do root->child[ !! ( text[p/8]&(1<<p&7)) ], czyli innymi słowy idziemy albo do dziecka numer 0 albo numer 1, w zależności od tego jaką wartość ma p-ty bit naszego stringa. Jeśli wierzchołek, w którym jesteśmy jest już liściem, to prawdopodobnie znaleźliśmy wynik, ale nie możemy być tego pewni, gdyż sprawdziliśmy przecież tylko niektóre bity naszego szukanego klucza -- dokładniej, tylko te, których numery znajdowały się na ścieżce od korzenia do liścia, w którym jesteśmy. Właśnie po to, w liściu przechowujemy oryginalną wartość całego stringa, aby móc się teraz upewnić, wykonując leaf->original_string == text.
Czas wyszukiwania w takiej strukturze danych to w najgorszym razie głębokość drzewa plus długość szukanego napisu. Tak czy owak nie przekracza to raczej O((8+1)*m) = O(m) operacji, gdzie m to długość szukanego napisu.

Wstawianie nowego elementu do takiej struktury nie jest zbyt proste, o ile nie wzbogacimy każdego wierzchołka wewnętrznego o pewne dodatkowe dane.
Aby wstawić nowy napis do takiego drzewa, trzeba znaleźć pierwszy bit na którym różni się on od pozostałych w danym poddrzewie. Teoretycznie wystarczy w tym celu wziąć pierwszy lepszy liść w danym poddrzewie, no ale do tego potrzebny byłby jakiś wskaźnik na ten pierwszy liść. Od biedy można to właśnie tak rozwiązać. Można też zrobić inaczej i na każdej krawędzi pamiętać ciąg bitów jaki do niej prowadzi. Jest tu trochę detali do dopracowania samemu, ale na pewno przydatnym trickiem jest umieć szybko znaleźć pierwszy bit, na którym różnią się dwie liczby. W asemblerze jest do tego pojedyncza instrukcja, ale jeśli nie umiecie/nie możecie używać wstawek asemblerowych, to pozostaje Wam wymyśleć jakieś własne sprytne rozwiązanie.

Powyższa struktura jest jedną z moich ulubionych, bo ma fajne gwarancje czasu dostępu i modyfikacji, a przy okazji zachowuje porządek na elementach. Jakkolwiek go zachowuje (da się iterować po węzłach w kolejności alfabetycznej), to wcale nie jest oczywiste w jaki sposób wykonać na niej operacje upper_bound, czy lower_bound, bo będąc w danym wierzchołku wcale nie jest oczywiste czy należy skręcić w lewo czy w prawo. To było oczywiste tylko wtedy gdy szukaliśmy czegoś dokładnie równego szukanemu kluczowi, niestety robi się bardziej zawikłane, jeśli szukamy czegoś co nie jest równe, bo wtedy nie bardzo wiadomo co sądzić na temat tych wszystkich bitów, które "przeskakujemy". Ten problem również da się jako tako rozwiązać, trzymając pewne dodatkowe informacje na każdej krawędzi.

Kolejną strukturą, jest radix-tree. Zazwyczaj omawia się je zanim przejdzie się do patricia-tree, bo jest na swój sposób mniej mądre.
Jak sama nazwa wskazuje, struktura drzewa ma dużo wspólnego z reprezentacją liczb w systemem pozycyjnym o jakiejś podstawie.
Dla ustalenia uwagi, rozważmy system binarny. Chcemy mianowicie, aby każdy poziom drzewa odpowiadał kolejnym pozycjom (bitom) liczby (stringa).
Czyli np. korzeń odpowiada pierwszemu bitowi naszego napisu i jeśli jest on zerem, to nalezy pójść w lewo, a jeśli jedynką, to należy iść w prawo.
Drzewo takie ma głębokość dokładnie 8*m gdzie m to liczba liter, jest więc nieco bardziej zasobożerne niż patricia-tree, w którym staraliśmy się aby wierzchołków było mało. Zauważmy bowiem, że w drzewku patricia-tree, każdy wierzchołek miał albo 2 albo 0 dzieci, co oznacza, że liczba wierzchołków wynosiła 2*n-1, gdzie n to liczba napisów w kolekcji. Tymczasem w drzewku radix-tree, może być całkiem sporo wierzchołków stopnia 1.
Radix-tree ma na pewno nie więcej wierzchołków niż wynosi suma długości wszystkich napisów w kolekcji, co zazwyczaj jest rozsądne, bo przecież dane wejściowe i tak trzeba kiedyś wczytać.

To co jest w nim trochę smutne, to to, że aby znaleźć słowo długości m, trzeba wykonać aż 8*m odczytów z dość losowych miejsc w pamięci.
Zdecydowanie wpływ na to miał dobór bazy w jakiej reprezentowaliśmy liczby (napisy), a więc binarnej, co zmusiło nas, do porównywania wszystkiego bit po bicie. Znacznie naturalniej wydaje się porównywać napisy znak po znaku, a więc w systemie o podstawie 256.
Tak oto dochodzimy do kolejnej struktury.

TRIE, to drzewko, w którym krawędzie etykietowane są pojedynczymi literkami. Aby odszukać w nim słowo "kuba", startujemy z korzenia i patrzymy czy istnieje dziecko do którego prowadzi etykietka 'k', jeśli tak, to przechodzimy do niego i rekurencyjnie szukamy "uba".

Teoria jest tu niezwykle prosta i przyjemna, nie mniej nie jedna osoba doszła do ściany, próbując zaimplementować to w wydajny sposób. Trudność jest następująca: w jaki sposób przechowywać dzieci korzenia, tak aby łatwo było znaleźć dziecko o etykietce "k"?
Pierwsze narzucające się rozwiązania to:
- użyć tablicy o rozmiarze 256, a więc: struct tree{ tree * children[256];}
- użyć mapy, a więc struct tree{map<char,tree*> children;}
Pierwsze rozwiązanie wymaga koszmarnej ilości pamięci, bo około 1000 razy więcej niż zjamowały oryginalne dane wejściowe.
Drugie rozwiązanie, wymaga co prawda ilości pamięci w miarę proporcjonalnej do danych wejściowych, jednak szukanie dziecka z etykietką 'k', może trwać lg 256 . To oczywiście jakaś tam stała, ale na zawodach dość dokuczliwa.

Kolejne rozwiązania są zapewne takie:
- użyć tablicy o takim rozmiarze jak mi potrzebne, czyli struct tree{ tree * children['z'-'a'+1];}
- użyć posortowanej tablicy par, a więc struct tree{ vector<char,tree *> children;}
Pierwsze rozwiązanie czasem jest całkiem spoko, ale często w zadaniu nie mamy żadnych gwarancji, że alfabet składa się tylko z małych liter.
Drugie rozwiązanie, wymaga używania binarysearch'a, a więc nadal lg 256 operacji, ale przynajmniej zużywa mniej pamięci i to zaalokowanej w spójnym rejonie, co zmniejsza liczbę cache-missów i generalnie jest prostsze niż łażenie po drzewku czerwonoczarnym.

Z teoretycznego punktu widzenia i pamiętając początek tego wywodu, najsłuszniejszym rozwiązaniem wydaje się użycie tablicy hashującej. Gwarantuje ona stały czas dostępu i liniowe zużycie pamięci. Czyli struct tree{hash_map<char,tree*> children;}.
Niestety, hash_mapki do małych nie należą, szybkie też nie są, a co gorsza nie pozwalają wykonywac upper_bound ani lower_bound, czyli nie dowiemy się jakie słowo jest zaraz po "kuba" w naszym słowniku.

Czytałem kiedyś prackę, w której używano bardzo sprytnej heurystyki, polegającej na tym, że użyto wskaźnika na 256 elementową tablicę, tak jak w pierwszym z pomysłów, ale tablice używane przez różne węzły się zazębiały. Zauważmy, że skoro nie używamy wszystkich pól 256elementowej tablicy, to być może istnieje jakas inna 256elementowa tablica, która używa własnie tych pozostałych. Generalnie pomysł wymagał napisania własnego alokatora pamięci, który starał się znaleźć takie miejsce w pamięci, że pattern wolnych i zajętych komórek pamięci pasował do patternu, który jest nam potrzebny. Dało to jakieś niesamowite efekty oszczędności czasu i pamięci.

Oczywiście podobnie jak radix-tree ma swój sprytniejszy odpowiednik: patricia-tree, tak samo dla drzewka TRIE da się zrobić sprytniejszy odpowiednik, w którym nie ma wierzchołków stopnia jeden. Usuwanie wierzchołków stopnia jeden, często nazywamy "kompresją ścieżek" i polega z grubsza na tym, że pozwalamy aby etykietki na krawędziach składały sie nie z jednej litery, ale z dłużych stringów.

Problem mapowania stringów na inne obiekty jest dość powszechny w informatyce i nadal jest obszarem gorących badań. Obecnie modne są bowiem dwa obszary informatyki: Zwięzłe Struktury Danych i Algorytmy Cache Oblivious. A już w ogóle szałem jest wszystko co leży na przecięciu tych dwóch działów. Ostatnio powstało więc trochę prac na temat tego jak w zwięzły sposób pamiętać kolekcję stringów i to tak, aby niezależnie od konfirugarcji Cacheów procesora, algorytm robił jak najmniej Cache missów. Rozwiązania bazują na różnego rodzaju kompresjach, ścieżkach centroidalnych i innych rzeczach, które raczej na zawodach nie dają się zaimplementować, ale chyba to właśnie Waszemu pokoleniu przyjdzie zaimplementować biblioteki standardowe, któreby to realizowały.

 

Snippet icon

Zdefiniuj typ s2n, który udostępnia

1
int& operator [](string &x);
czyli pozwala np. uruchomić taki program:
1
2
3
4
5
6
char text[100];
s2n s;
for(int i=0;i<10;++i){
  sprintf(text,"%d",i);
  s[text] = i;
}

0
Twoja ocena: Brak

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com