Re: Liczby całkowite zmiennej długości - Grupy dyskusyjne w eGospodarka.pl

eGospodarka.pl › Grupy › pl.comp.programming › Liczby całkowite zmiennej długości › Re: Liczby całkowite zmiennej długości

X-Received: by 10.140.101.107 with SMTP id t98mr7123qge.5.1398807515111; Tue, 29 Apr
2014 14:38:35 -0700 (PDT)
X-Received: by 10.140.101.107 with SMTP id t98mr7123qge.5.1398807515111; Tue, 29 Apr
2014 14:38:35 -0700 (PDT)
Path: news-archive.icm.edu.pl!agh.edu.pl!news.agh.edu.pl!newsfeed2.atman.pl!newsfeed.
atman.pl!goblin3!goblin.stu.neva.ru!news.ripco.com!news.glorb.com!l13no12074788
iga.0!news-out.google.com!du2ni19042qab.0!nntp.google.com!dc16no95114qab.0!post
news.google.com!glegroupsg2000goo.googlegroups.com!not-for-mail
Newsgroups: pl.comp.programming
Date: Tue, 29 Apr 2014 14:38:34 -0700 (PDT)
In-Reply-To: <ljou5f$uob$1@node1.news.atman.pl>
Complaints-To: g...@g...com
Injection-Info: glegroupsg2000goo.googlegroups.com; posting-host=31.61.138.121;
posting-account=VFwkXwoAAADdT4-lLKRZrMYkTjizGoyn
NNTP-Posting-Host: 31.61.138.121
References: <ljou5f$uob$1@node1.news.atman.pl>
User-Agent: G2/1.0
MIME-Version: 1.0
Message-ID: <e...@g...com>
Subject: Re: Liczby całkowite zmiennej długości
From: Wojciech Muła <w...@g...com>
Injection-Date: Tue, 29 Apr 2014 21:38:35 +0000
Content-Type: text/plain; charset=ISO-8859-2
Content-Transfer-Encoding: quoted-printable
Xref: news-archive.icm.edu.pl pl.comp.programming:205524
[ ukryj nagłówki ]

On Tuesday, April 29, 2014 9:21:55 PM UTC+2, Borneq wrote:
> Narzut = 1/8, jeden bit z bajta użyty.Czy są jeszcze bardziej wydajne
> sposoby? Kodowanie utf-8 jest podobnie kodem zmiennej długości.
> Jak zakodować liczbę ujemną? zygzakiem:
> dla ciągu 0,-1,1,-2,2,-3,3,-4,4... przyjmujemy 0,1,2,3,4,5,6...
>
> Czy jest jakieś kodowanie zmiennej długości bitów a nie bajtów?

Np. kodowania Eliasa, kodowanie Golomba/Rice'a, kodowanie
Tunstalla. Są też inne kody podobne do varint, przegląd
znajdziesz w pracy "Inverted Index Compression and Query
Processing with Optimized Document Ordering" (autorzy:
Hao Yan, Shuai Ding, Torsten Suel).

Problemem w kodowaniu na poziomie bitów jest mała szybkość,
procesory działają jednak na poziomie bajtów. Np. w indeksach
Google liczby 32-bitowe kodowane są w paczkach po 4: w pierwszym
bajcie są długości tych liczb (po 2 bity), za nim zmienna
liczba bajtów - od 4 do 16.

w.