Autor Wątek: Kompresja i optymalizacja mapy  (Przeczytany 438 razy)

Offline Sarann

  • Użytkownik

# Wrzesień 02, 2017, 05:28:49
Sprawa wygląda tak, że mam dwuwymiarową mapę o wielkości 1m^2, lub większą. Każde pole na mapie zajmuje 1 bajt.
Jak mogę to zoptymalizować, by taka mapka 1m^2 nie zajmowała 1000 GB? Możliwe jest, iż będzie dużo więcej pustych pól niż tych wypełnionych, nawet w proporcji 100 do 1.

W RAM z tego co wiem mogę trzymać w jednej chwili fragment mapy o wielkości 100k^2, czyli około 10 GB. Jednak nawet kiedy wczytuję fragmenty tylko wtedy, kiedy są potrzebne, cała mapa zajmować będzie aż 1000 GB dysku.

Przykładowa mapka o wielkości 32^2:


No to czekam na geniuszy, którzy wpadną na pomysł jak skompresować takie coś.
« Ostatnia zmiana: Wrzesień 02, 2017, 05:30:26 wysłana przez Sarann »

Offline Mr. Spam

  • Miłośnik przetworów mięsnych

Offline Kurak

  • Użytkownik

# Wrzesień 02, 2017, 06:43:59
https://en.m.wikipedia.org/wiki/Sparse_matrix

Inna sprawa to skad te dane pochodza. Rzadko sie zdarza zeby taka ilosc danych nie byla po prostu wygenerowana, i w takiej sytuacji lepiej po prostu deterministycznie generowac na zadanie.

Sa ofc przypadki gdzie faktycznie taka ilosc danych albo i wiecej jest przechowywana, wtedy optymalnym rozwiazaniem jest dokupic wiekszy dysk i troche ramu ;)

Offline Karol

  • Użytkownik

  • +1
# Wrzesień 02, 2017, 13:34:36
Jak mogę to zoptymalizować, by taka mapka 1m^2 nie zajmowała 1000 GB? Możliwe jest, iż będzie dużo więcej pustych pól niż tych wypełnionych, nawet w proporcji 100 do 1.
Hmm, czyli jedno pole ma wielkość nanometra? ;)

No to czekam na geniuszy, którzy wpadną na pomysł jak skompresować takie coś.
Powodzenia :P
« Ostatnia zmiana: Wrzesień 02, 2017, 13:40:47 wysłana przez Karol »

Offline wezu

  • Użytkownik

# Wrzesień 02, 2017, 17:07:49
Najłatwiej to zrobić mniejszą mapę.

Weźmy czarny scenariusz, że 1 punkt mapy w jakiś sposób odpowiada 1 pixelowi na ekranie i ktoś to całe ustrojstwo wyświetla na ekranie 8k. Na raz na ekranie zmieści się 7680 × 4320 punktów z twojej mapy, która ma  1000000x1000000.

Podziel swoją mapkę na 4, potem podziel każdy z każdy z kwadratów na 4, potem każdy z podzielonych kwadratów podziel jeszcze raz na 4 i zrób tak 64 razy. Potem... nie wiesz co, potem zatrzymaj sobie jeden taki fragment, wywal resztę i zastanów się jeszcze raz czy na pewno jest ci potrzeba tak wielka mapa. Co to będzie? Symulator układu słonecznego w skali?

Offline Sarann

  • Użytkownik

# Wrzesień 02, 2017, 19:39:16
Wiadomo, że tak wielka mapa nie zmieści się na ekranie ;)

Ale można ją przeskalować do mniejszych rozmiarów, być może tracąc przy tym nieco mało istotnych szczegółów.

Żaden symulator Układu Słonecznego, tylko automat komórkowy Mrówki Langtona :)
Z nieco zmodyfikowanymi zasadami oczywiście.

Może ten przykład z dwuwymiarową mapką o takiej wielkości jest nieco naciągany, ale identyczna wielkość będzie w przypadku czterowymiarowej mrówki o dość małym rozmiarze, bo jedynie 1000^4. Taką ilość spokojnie da się wyświetlić na większości ekranów w postaci trójwymiarowej. Mimo to także zajmować będzie 1000 GB.
W tym przypadku niemożliwe będzie wczytywanie danych z dysku na bieżąco, bo prędkość wczytywania musiałaby być większa od jakichś 15 GB/s.

Offline matheavyk

  • Użytkownik
    • rabagames.com

# Wrzesień 02, 2017, 22:04:45
Kurak świetnie podlinkował do Sparse Matrix. A tutaj link do dwóch sposobów przechowywania: http://www.alglib.net/matrixops/sparse.php#header0

W zależności od gęstości tej mapy (czyli liczby niezerowych punktów) zyskasz (lub stracisz) więcej lub mniej.

Na pewno znajdziesz w internecie dużo materiałów naukowych np. pod hasłem "storing sparse matrices". Ale z tego, co widzę, większość formatów przechowywania tych macierzy kładzie duży nacisk na możliwość wykonywania jakichś tam operacji na skompresowanych macierzach, a nie na jak największą kompresję. Może jednak coś fajnego znajdziesz ;p

Offline wezu

  • Użytkownik

# Wrzesień 02, 2017, 22:35:59
Sparse Voxel Octrees:
https://pdfs.semanticscholar.org/2c9a/6d9b27c1eccd438d0685ad4c04c5a9e1d311.pdf

W 4D to chyba nie będzie octree tylko sedectree?

Offline Liosan

  • Redaktor

# Wrzesień 02, 2017, 22:45:35
To wszystko co poprzednicy + proponuję poczytać https://en.wikipedia.org/wiki/Page_replacement_algorithm, przyjmując że jeden fragment drzewa to "strona" pamięci w rozumieniu tych algorytmów, żeby dobrać jakiś sensowny sposób wyboru fragmentu drzewa do usunięcia z pamięci i serializacji na dysk.

Liosan

Offline Iwan91

  • Użytkownik

# Wrzesień 03, 2017, 00:03:19
Wydaje mi się, że w tym przypadku można zastosować run length encoding. Powinno to zredukować dość znacznie rozmiar.
https://en.wikipedia.org/wiki/Run-length_encoding

Znalazłem jeszcze coś takiego jak Position Aware RunLength:
https://twistedpairdevelopment.wordpress.com/2011/06/10/run-length-encoding-with-positioning-information-in-python/

edit1: Kiedyś się bawiłem kompresją danych dla gry ala minecraft i napisałem bibliotekę w javie do tego
https://github.com/Iwan91/PositionAwareRunLengthEncoding-java
« Ostatnia zmiana: Wrzesień 03, 2017, 00:13:00 wysłana przez Iwan91 »

Offline Sarann

  • Użytkownik

# Wrzesień 03, 2017, 14:11:50
Dzięki za propozycje, sprawdzę i podeślę rezultaty ;)