Making dense codes even denser

Tyt. z nagłówka.Bibliografia s. 778-779.Dostępny również w formie drukowanej.STRESZCZENIE: Gęste kody bajtowe są użytecznym narzędziem kompresji tekstowych baz danych, przy założeniu, że alfabet użytych symboli jest duży. To założenie jest w prosty sposób spełnione dla większości języków naturalnych, gdzie symbolami są słowa; jednakże również teksty bez segmentacji mogą być obsługiwane w podobny sposób, przy użyciu q-gramów. W ostatnich latach zostało przedstawionych w literaturze kilka interesujących algorytmów kodowania dla dużych alfabetów, łączących szybkość kompresji i dekompresji, wysokie stopnie kompresji, wsparcie dla szybkiego wyszukiwania wzorca bezpośrednio w tekście, a przy tym cechujących się prostotą. W niniejszej pracy przedstawiamy kilka prostych idei zwiększających nieco stopień kompresji popularnych kodów bajtowych, takich jak (s,c)-DC oraz otagowany Huffman, przy założeniu, że kompresowany tekst jest statyczny. Wstępne eksperymenty z użyciem jednej z zaproponowanych technik pokazują, iż jest ona bardziej efektywna przy kompresji na bazie q-gramów niż na bazie słów, a stopień kompresji poprawia się w tych przypadkach często o 1% lub więcej, bez uszczerbku szybkości wyszukiwania wzorca czy dekompresji, oraz przy zachowaniu prostoty oryginalnych idei. SŁOWA KLUCZOWE: wyszukiwanie w tekście skompresowanym, modele oparte na słowach, q-gramy, kody bajtowe. ABSTRACT: Dense byte oriented compression codes are a useful tool for compressing textual databases over a large alphabet. The requirement for large alphabet is naturally fulfilled for most human languages, where the symbols can be words, but also non segmented texts can be handled similarly, using q-grams. Recently, several interesting schemes, combining speed, high compression ratios, fast search support and simplicity, have been presented. In this work, we show a couple of simple ideas increasing slightly the compression ratios of common byte codes, like (s,c)-DC or tagged Huffman, assuming the text is static. Preliminary experimental results with one of those techniques show that it is more efficient with q-gram compression, and the compression ratio improves in those cases often by 1% or more, without compromising the search or decoding efficiency and simplicity. KEYWORDS: compressed pattern matching, word-based models, q-grams, byte codes