Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > pl.comp.programming > #31746 > unrolled thread

Problemik nie całkiem teoretyczny

Back to article view | Back to pl.comp.programming

Contents

  Problemik nie całkiem teoretyczny slawek <x.y@org.org> - 2018-08-04 10:38 +0200
    Re: Problemik nie całkiem teoretyczny Maciej Sobczak <see.my.homepage@gmail.com> - 2018-08-06 06:13 -0700
      Re: Problemik nie całkiem teoretyczny bartekltg <bartekltg@gmail.com> - 2018-08-06 21:03 +0200
        Re: Problemik nie całkiem teoretyczny slawek <x.y@org.org> - 2018-08-09 08:24 +0200
    Re: Problemik nie całkiem teoretyczny Wojciech Muła <wojtek.mula@gmail.com> - 2018-08-06 13:23 -0700

#31746 — Problemik nie całkiem teoretyczny

Takie małe coś, akurat na wakacje:

Ciąg liczb zmiennoprzecinkowych 64 bitowych powstał po pomnożeniu
 przez niezerową stałą ciągu liczb stałoprzecinkowych 16-bitowych.
 Czy istnieje prosta metoda kompresji, taka że nie znając tej
 stałej, można ograniczyć liczbę przesyłanych bajtów? Tzn. przy
 1000 liczbach przesłać (niewiele ponad) 2000 bajtów zamiast
 8000?

Definicja "prostej metody": LZW nie jest, RLE jest.

Problem powstał w związku z pytaniem: czy lepiej przesyłać raw
 data - czy wielkości przeskalowane do fizycznych jednostek (np.
 miliamperów na hektar i węzeł)?


Have fun.


----Android NewsGroup Reader----
http://usenet.sinaapp.com/

[toc] | [next] | [standalone]

#31751

> Takie małe coś, akurat na wakacje:

Skoro wakacje, to...

> Ciąg liczb zmiennoprzecinkowych 64 bitowych powstał po pomnożeniu
>  przez niezerową stałą ciągu liczb stałoprzecinkowych 16-bitowych.
>  Czy istnieje prosta metoda kompresji, taka że nie znając tej
>  stałej, można ograniczyć liczbę przesyłanych bajtów? Tzn. przy
>  1000 liczbach przesłać (niewiele ponad) 2000 bajtów zamiast
>  8000?

Chyba nie ma sensu szukać tego mnożnika, bo np. mając w ciągu liczby 10.0 i 20.0 nie wiemy, czy oryginałem było 1 i 2 z mnożnikiem 10.0, czy może 2 i 4 z mnożnikiem 5.0.
Więc może wiedząc z góry, jakie jest ograniczenie na liczbę różnych wartości (16bit), warto je poukładać w kubełkach i przesyłać numery kubełków? Może się okazać, że oszczędność będzie jeszcze większa, jeśli nie wykorzystano wszystkich 2^16 różnych wartości a dodatkowym bonusem jest fakt, że to działa nawet wtedy, gdy skalowanie nie było liniowe (co obejmuje również zaokrąglenia przy skalowaniu). Oczywiście ciąg numerów kubełków można dalej kompresować niezależnie, np. RLE, jeśli spodziewamy się, że to ma sens.

Problemem jest przesłanie słownika - czyli jaka zakodowana wartość jest w każdym wykorzystanym kubełku. Pełny słownik to potencjalnie 2^16*64 bity, ale jeżeli ciąg jest długi albo jeden słownik jest wspólny dla wielu takich ciągów, to może się zamortyzować.

> Problem powstał w związku z pytaniem: czy lepiej przesyłać raw
>  data - czy wielkości przeskalowane do fizycznych jednostek (np.
>  miliamperów na hektar i węzeł)?

To zależy. Nie wiemy, co to za dane i jaka jest wymagana wierność transmisji. Skalowanie zmiennoprzecinkowe sugeruje, że 100% dokładność nie jest wymagana, więc może jakieś znane metody stratne (zależnie od rodzaju danych) byłyby akceptowalne. Bo po co napinać się na dokładny transfer niedokładnych danych?

-- 
Maciej Sobczak * http://www.inspirel.com

[toc] | [prev] | [next] | [standalone]

#31752

On 06.08.2018 15:13, Maciej Sobczak wrote:
>> Takie małe coś, akurat na wakacje:
> 
> Skoro wakacje, to...
> 
>> Ciąg liczb zmiennoprzecinkowych 64 bitowych powstał po pomnożeniu
>>   przez niezerową stałą ciągu liczb stałoprzecinkowych 16-bitowych.
>>   Czy istnieje prosta metoda kompresji, taka że nie znając tej
>>   stałej, można ograniczyć liczbę przesyłanych bajtów? Tzn. przy
>>   1000 liczbach przesłać (niewiele ponad) 2000 bajtów zamiast
>>   8000?
> 
> Chyba nie ma sensu szukać tego mnożnika, bo np. mając w ciągu liczby 10.0 i 20.0 nie wiemy, czy oryginałem było 1 i 2 z mnożnikiem 10.0, czy może 2 i 4 z mnożnikiem 5.0.

Tego nie, ale bez większych trudności znajdziesz mnożnik będący 
oryginalnym mnożnikiem razy największy wspolny dzielnik wszystkich
danych.

Taki mnożnik jest równie dobry do przesłania, a po drugiej stronie
i tak obchodzi nas tylko iloczyn danych i mnoznika, więc nie ma różnicy.


> Więc może wiedząc z góry, jakie jest ograniczenie na liczbę różnych wartości (16bit), warto je poukładać w kubełkach i przesyłać numery kubełków? Może się okazać, że oszczędność będzie jeszcze większa, jeśli nie wykorzystano wszystkich 2^16 różnych wartości a dodatkowym bonusem jest fakt, że to działa nawet wtedy, gdy skalowanie nie było liniowe (co obejmuje również zaokrąglenia przy skalowaniu). Oczywiście ciąg numerów kubełków można dalej kompresować niezależnie, np. RLE, jeśli spodziewamy się, że to ma sens.
> 
> Problemem jest przesłanie słownika - czyli jaka zakodowana wartość jest w każdym wykorzystanym kubełku. Pełny słownik to potencjalnie 2^16*64 bity, ale jeżeli ciąg jest długi albo jeden słownik jest wspólny dla wielu takich ciągów, to może się zamortyzować.
> 
>> Problem powstał w związku z pytaniem: czy lepiej przesyłać raw
>>   data - czy wielkości przeskalowane do fizycznych jednostek (np.
>>   miliamperów na hektar i węzeł)?
> 
> To zależy. Nie wiemy, co to za dane i jaka jest wymagana wierność transmisji. Skalowanie zmiennoprzecinkowe sugeruje, że 100% dokładność nie jest wymagana, więc może jakieś znane metody stratne (zależnie od rodzaju danych) byłyby akceptowalne. Bo po co napinać się na dokładny transfer niedokładnych danych?
> 


Da sie znacznie prościej. I liniowo.
Oczywiście trzeba wykorzystać to, że double ma znaczny zapas
precyzji w stosunku do int16_t.


pzdr
bartekltg

[toc] | [prev] | [next] | [standalone]

#31756

bartekltg <bartekltg@gmail.com> Wrote in message:
> Da sie znacznie prościej. I liniowo.

Zapewne... gdyż mnożnik i liczby int16_t są znane. Więc można po
 prostu wysyłać właśnie te liczby.

> Oczywiście trzeba wykorzystać to, że double ma znaczny zapas
> precyzji w stosunku do int16_t.

Otóż to. Jednym z prostszych trików mogłoby być nie wysyłanie
 mantysy. I znaku. I być może najmniej znaczących bitów.
 Oczywiście przy założeniu że mantysa jest zero, liczby są
 dodatnie, a nieznaczące bajty są nieznaczące.

Generalnie: dane są wysyłane przez łącze o określonej
 przepustowości; dane są 10-cio bitowymi int; miło byłoby gdyby
 przychodziły jako float, bo nie trzeba byłoby zastanawiać się nad
 mnożnikami, jednostkami itp.

Wychodzi na to że nie da się zrobić tego ładnie inaczej niż...
 przesyłając te 10 bitów i mnożnik.

Teoretycznie każda liczba int 10 bitowa ma swoją ścisłą
 reprezentację jako float. Ale choć przejscie z int na float jest
 trywialne, to w drugą stronę (bez zaokrągleń) nie jest. Entropia
 i takie tam.


----Android NewsGroup Reader----
http://usenet.sinaapp.com/

[toc] | [prev] | [next] | [standalone]

#31753

On Saturday, August 4, 2018 at 10:38:56 AM UTC+2, slawek wrote:
> Takie małe coś, akurat na wakacje:
> 
> Ciąg liczb zmiennoprzecinkowych 64 bitowych powstał po pomnożeniu
>  przez niezerową stałą ciągu liczb stałoprzecinkowych 16-bitowych.
>  Czy istnieje prosta metoda kompresji, taka że nie znając tej
>  stałej, można ograniczyć liczbę przesyłanych bajtów? Tzn. przy
>  1000 liczbach przesłać (niewiele ponad) 2000 bajtów zamiast
>  8000?
> 
> Definicja "prostej metody": LZW nie jest, RLE jest.
> 
> Problem powstał w związku z pytaniem: czy lepiej przesyłać raw
>  data - czy wielkości przeskalowane do fizycznych jednostek (np.
>  miliamperów na hektar i węzeł)?
> 
> 
> Have fun.

1. Rozbić liczbę zmiennoprzecinkową na: bit znaku, wykładnik, mantysę. Kompresować je jako osobne strumienie danych. (Zawołać abort gdy isfinite(x) == false).

2. Potraktować mantysę jako liczbę całkowitą i kodować różnice między kolejnymi wartościami. Albo w ogóle wprowadzić predykcję i kodować różnice między aproksymowaną i rzeczywistą wartością.

3. Kodowanie liczb całkowitych można zrobić np. kodem Rice'a albo Eliasa, czyli kodami, gdzie liczba bitów zależy od kodowanej wartości.

4. Pogooglać za bazami do timeseries i poczytać, jak oni sobie radzą.

w.

[toc] | [prev] | [standalone]

Back to top | Article view | pl.comp.programming

csiph-web