Kompresja danych na poziomie 99%

4

https://github.com/philipl/pifs
co o tym myślicie? ;)

0

Rzekłbym, że genialne w swojej prostocie i metodzie działania, lecz kompresowanie tym większych plików (> 1 GB) to zapewne katorga i raczej nawet na uber-clockowanym procesorze nie doczekalibyśmy końca w rozsądnym czasie (jak na aktualne standardy, poczekamy - prawo Moore'a zrobi swoje ;>).
Niemniej, sam teraz się zastanawiam, dlaczego na to nie wpadłem ;D

1

no tak... tylko, że offset może być liczbą o "grubości" kilku/set Terabajtów

0

No to offset również skompresujemy ;P

0

Tak naprawdę stopień kompresji wynosi 200%. <ironia>Genialne!</ironia>

0

Jeśli odpowiednia ilość szympansów będzie losowo stukała na maszynach do pisania to w końcu jedna z nich napisze dramat szekspira. Jeśli mamy plik ważący 100MB to w reprezentacji cyfrowej zawiera on w sobie 209715200 'cyfr' w zapisie 0x. 1 Cyfra to 16 możliwości biorąc pod uwagę, że plik MOŻE się zaczynać od 0 mamy 16209715200 różnych plików ważących 100MB. Jeśli przyjmiemy założenie, że liczba pi będzie zawierała w sobie niepowtarzalne sekwencje w nieskończoność to w najgorszym wypadku offset będzie wynosił 16209715200 =(zaokrąglając) 10252522263, a to jest offset o wielkości 240MB.

Przypominam, że tą liczbę trzeba gdzieś w tym pi znaleźć.

0

Hej, ale przecież nie wiadomo czy Pi jest normalna, a to założenie które przyjmują autorzy tej superkompresji.
Wg. wiki: The hypothesis that π is normal has not been proven or disproven.

Poza tym - przecież nikt (oby) nie traktuje tego poważnie, wiadomo że offset na którym będzie szukany ciąg bajtów będzie w 99% przypadków zajmował dużo więcej miejsca niż sam plik ;]. A kompresja idealna (kompresująca dowolny ciąg bitów) nie istnieje o czym też wszyscy wiemy.

0

Wystarczy popatrzeć na ten fragment, żeby stwierdzić, że autor tego FSa trolluje:

static int pifs_write(const char *path, const char *buf, size_t count,
                      off_t offset, struct fuse_file_info *info)
{
  int ret = lseek(info->fh, offset * 2, SEEK_SET);
  if (ret == -1) {
    return -errno;
  }

  for (size_t i = 0; i < count; i++) {
    short index;
    for (index = 0; index < SHRT_MAX; index++) {
      if (get_byte(index) == *buf) {
        break;
      }
    }
    ret = write(info->fh, &index, sizeof index);
    if (ret == -1) {
      return -errno;
    }
    buf++;
  }

  return count;
}
0

Metoda brute force zapisu danych... :D

Swoją drogą musieli od razu robić "FS"? Nie można było tego zrobić normalnie na plikach?

0

Jakieś 11 lat temu wymysliłem coś podobnego(trochę).
Wystarczy, że ktoś znajdzie szybką metodę na podanie czynników jeżeli dostanie ich liczbę i iloczyn :)

To było chyba w tym czsie kiedy dowiedziałem się o istnieniu RSA i próbowałem to złamać :)

0
DużaTajemnicaWiedzy. napisał(a):

Wystarczy, że ktoś znajdzie szybką metodę na podanie czynników jeżeli dostanie ich liczbę i iloczyn :)
Ale przecież łączna długość poszczególnych czynników jest bardzo zbliżona do długości ich iloczynu.
Nie mówiąc już o możliwości wyznaczenia czynników z iloczynu.

2

Długość liczby to praktycznie logarytm z liczby - dokładnie to nieco więcej. Im większa liczba, tym bardziej jest to zbliżone.

log(a * b) = log a + log b
Z powyższego wzoru wynika, że rozłożenie liczby na czynniki na pewno nie spowoduje ogólnego skrócenia wyrażenia, bo długość czynników nie jest krótsza niż długość iloczynu.

Można by dodawać potęgi przy czynnikach, ale tutaj znowu nie dostaniemy żadnej kompresji, bo:

  1. albo zawsze dodajemy wykładnik, wobec czego w prawie każdym przypadku mamy narzut na wykładnik równy 1,
  2. albo musimy dodać specjalną flagę która oznacza czy wykładnik jest różny od 1, ale tutaj znowu nic nie zyskamy, bo rzadko kiedy wykładnik jest różny od jeden, a flaga zawsze trochę miejsca zajmuje,

Ogólnie kompresja uniwersalna nie jest możliwa: http://mattmahoney.net/dc/dce.html#Section_11
Kompresor uniwersalny to w skrócie taki kompresor, który kompresuje wszystko powyżej pewnego ustalonego skończonego rozmiaru (oczywiście nie istnieje; jak napisałem w poprzednim zdaniu).

0

@Łukasz
No właśnie tą(w dodatku "szybką") możliwość zakładałem :)
Po iluś iteracjach liczba by w końcu wystarczająco zmalała.

@Wibowit
Młody wtedy byłem.

0

Ale wlasnie chodzilo mi o to, ze takiej mozliwosci nie ma. Taki sam iloczyn moga dawac rozne czynniki, czyli nie wiadomo ktore czynniki sa wlasciwe.

1 użytkowników online, w tym zalogowanych: 0, gości: 1