Wyniki wyszukiwania - BazTech

Ograniczanie wyników

Znaleziono wyników: 1

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: q-grams

Sortuj według:

Ogranicz wyniki do:

Making dense codes even denser

Grabowski S.

Automatyka / Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie

2008

T. 12, z. 3

769-779

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.

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.