Archiwum X

Na potrzeby pracy zarobkowej, projektuje od czasu do czasu struktury danych i algorytmy. Niby swiat bardzo duzo wie o kompresji i o indeksowaniu, a nawet calkiem sporo o indeksowaniu skompresowanych tekstow, ale bardzo malo wie o dzieciach neo. Jezyk polski, ze swa fleksja, ogonkami, lub ich brakiem, wielobajtowymi znakami, wzbogacony o internetowe literowki, emotikony, linki i formy fatyczne, wydaje sie byc nieindeksowalny i niekompresowalny, a juz na pewno nie jedno i drugie.

Postanowilem, wiec przemyslec sprawe od wlasciwego konca: co uzytkownik chce miec. Uzytkownik chce w archiwum moc wyszukac wiadomosci od konkretnej osoby, znalezc ciekawy link, ktory ktos mu podeslal, byc moze jakas wazna date, godzine czy adres imprezy, lub ewentualnie jakies slowo, ktore wydaje mu sie charakterystyczne dla tematu rozmowy.

Zadne z powyzszych zastosowan wyszukiwarki nie wymaga full text indexu. Co wiecej, niektorych nie da sie przy jej pomocy w ogole wykonac.

Rozwazmy sztuczny, acz tresciwy przyklad wypowiedzi: 

Jak pójde na http://pl.wikipedia.org/ to moze znajed tam cos o Burrowsie-Wheelerze
Zawiera on bledy ortograficzne, literowki, zle odmienione slowa, nazwy wlasne i urle. Wydaje mi sie, ze pierwsze co nalezy zrobic z takim wpisem w archiwum, to wzorem Wavelet Compression, rozdzielic strumien informacji na dwa kanaly. Na niosacy tresc potrzebna do wyszukiwania, oraz na upiekszajacy. 
jak pojde na                          to moze znajde tam cos o burrowsie wheelerze

J    ó                                            ed           B        -

Jak widac, link traktujemy zupelnie osobno, bo chcemy miec kolekcje linkow w osobnym miejscu. Drugi kanal zawiera bardzo malo, acz nieco losowej informacji. Nie widac tego na powyzszym obrazku, ale litera ó zajmuje wiecej niz jeden bajt, co sprawia, ze te dwa teksty nie do konca do siebie pasuja. Mozna jednak raz na 200 bajtow wstawiac jakies synchronizujace znaczniki. Kusi tez, by zamiast literki J, czy B, wydzielic do drugiego kanalu tylko informacje o tym, ze nalezy wcisnac shift, czyli po prostu drugi kanal moglby byc xorem pierwszego kanalu i oryginalnego tekstu.

Drugi kanal mozemy sobie skompresowac jak nam sie zywnie podoba, byleby umiec rozkompresowac fragment rozsadnej wielkosci w rozsadnym czasie. Mozemy przykladowo pociac go na bloki i skompresowac BW + MTF + 0-RLE + Huffman.

Pierwszy kanal fajnie by bylo skompresowac uzywajac jakiejs wspolnej wiedzy wyciagnietej z calej bazy wiadomosci. A najlepiej w oparciu o slownik jezyka polskiego. Metoda taka nie bedzie zbyt przenosna, jednak numer wersji uzytego slownika zawsze mozna sobie gdzies zapisac w naglowku. Trzeba koniecznie wybrac metode umozliwiajaca szybkie wyszukiwanie wystapien jakiegos slowa. Warto zauwazyc, ze rozdzielajac kanaly poprawilismy literowke w slowie 'znajde' co umozliwi jego znalezienie. Dla jezyka z bogata fleksja taka jak nasz, warto tez pomyslec, czy koncowek wyrazow nie przerzucic do drugiego kanalu, aby ulatwic wyszukiwanie. W przeciwnym razie wyszukiwarka bedzie musiala wyszukiwac wszystkich mozliwych odmian podanego slowa. Sprowadzenie wszystkich slow w pierwszym kanale do formy bazowej, ma tez te zalete, ze w drugim kanale mamy wtedy informacje o gramatyce, ktora ma szanse zawierac pewne zaleznosci -- na przyklad po przymiotniku konczacym sie na "ą" zapewne nastapi rzeczownik z literka "ą". Tymczasem pierwszy kanal rowniez ma szanse zawierac pewne zaleznosci, ale zwiazane z semantyka -- na przyklad po slowie 'bialy' jest duza szansa na slowo 'dom' niezaleznie od koncowek tych slow, ktore niepotrzebnie zmylilyby kompresor. Wazne, ze tekst w pierwszym kanale na pewno bedzie zawieral slowa, ktore nie istnieja w jezyku, takie jak 'wheelerze', wiec jesli mamy uzywac kompresji opartej o slowniki, to musi ona wspierac sie pomocniczym slownikiem. Po co dodawac do slownika slowo, ktore uzylismy raz w calym zyciu? W zasadzie to po nic i byc moze nie trzeba tego robic, pytanie tylko jak wtedy wydajnie wyszukac takie slowa?

Rozdzielenie na kanaly ma wiele zalet, na przyklad mozliwosc odciazenia serwera, kosztem aplikacji ajaxowej, ktora w progresywny sposob najpierw sciagnie i wyswietli pierwszy kanal, a potem sciagnie drugi i sama naniesie poprawki. Jest to nieglupie, bo zapewne kanaly te beda kompresowane w odmienny sposob i byc moze na osobnych maszynach. Co wiecej dekompresje drugiego kanalu mozna pozostawic javascriptowi, bo nawet jesli nie zadziala ona dobrze, to tekst nadal bedzie w miare czytelny.

Popularne posty z tego bloga

Szczęście jako problem inżynieryjny

Jako, że od kilku lat nie czuję się szczęśliwy, od czasu do czasu trochę myślę i czytam o tym, co to w zasadzie jest to "szczęście" i jak to osiągnąć. Wielu ludzi ma wiele ciekawych rad i obserwacji, jest nawet cały instytut co to bada. Pewnie wiele z tego co tu przeczytacie wyda się Wam oczywiste, tak jak i mi się teraz wydaje - natomiast zupełnie takim nie było dla mnie wcześniej i dopiero teraz złożyło mi się w spójny obraz. Chciałbym się z Wami podzielić pewną perspektywą, do której doszedłem myśląc nad uczuciem szczęściem od zupełnie innej strony: Dlaczego projektując robota chciałbym mu dodać możliwość uśmiechania się do innych? Skąd w ogóle pomysł by atakować problem z takiego kąta? Ano, mocno wierzę, że mechanizmy, które widzimy u ludzi do czegoś służą - są wynikiem ewolucji czy cywilizacji i musiały się do czegoś przydać skoro przetrwały i są powszechne. Mimo, że ewolucja jest głupim i ślepym inżynierem, to jednak może da się zreverse-engineerować "do czego
Czytaj więcej

Kilka rzeczy, o których żałuję, że nie powiedziano mi, gdy byłem młody

Jakiś czas temu, z okazji jubileuszu mojego liceum, miałem okazję jako absolwent opowiedzieć cokolwiek wpółczesnym licealistom. Wykorzystałem to jako okazję do zrobienia czegoś w stylu Back To The Future: gdybym był nastolatkiem i przyszła wersja mnie samego mogła cofnąć się do mnie w czasie i dać mi parę wskazówek, co by to było? Poniżej (niekompletna) lista rzeczy, za które byłbym wdzięczny gdyby ktoś mi powiedział. Po pierwsze, byłoby super gdyby ktoś powiedział mi z wyprzedzeniem o wszystkich wypadkach i tragediach, którym mógłbym zapobiec. OK, szczerze mówiąc dodałem ten punkt do listy dopiero jako nasty i zawstydziłem się, że tak dużo rzeczy zdążyłem wymienić, zanim o tym pomyślałem. W szczególności to pewnie oznacza, że za późno dowiedziałem się o Negative Average Preference Utilitarianism i nie zdążyłem jeszcze tego zinternalizować (albo oglądałem za mało "Wydarzyło się jutro" i "Zagubiony w czasie"). Po drugie, szkoda, że nie dostałem na tacy wyników l
Czytaj więcej

Produkt: Ojciec*

Należę do rodziców, którzy traktują wychowanie dziecka jako projekt. Czy może raczej, z racji braku klarownego deadlineu - jako produkt . A to dlatego, że nie ma co ukrywać, że zajmuje to masę zasobów, wymaga nauki, koordynacji, komunikacji, planowania krótko- i długofalowego. Wszystko to można zrobić lepiej, albo gorzej. Moim zdaniem lepiej, jeśli nie ucieka się przed nazywaniem rzeczy po imieniu. Należę też do ludzi, którzy są przerażeni, gdy widzą rodzica próbującego spełnić swoje ambicje poprzez dziecko. Jedna obawa, to, że dziecko może zwyczajnie cierpieć będąc przymuszane do gry na pianinie. Inna, to, że dziecko, które oryginalnie lubiło konie, znienawidzi je po godzinach jazdy konnej na siłe. Sądzę, że odpowiednio "profesjonalny" rodzic, jest w stanie dobierając techniki zaszczepić miłość do pianina, nie zniszczyć miłości do koni i jeszcze wcisnąć gdzieś łacinę (choć to pewnie rzadkość) jednak nawet wtedy jest ryzyko, że dziecko znienawidzi samego rodzica i gdy tylk
Czytaj więcej