Kolejny użytkownik chce zapisać nowy fragment danych na dysku twardym, ale brakuje mu wolnego miejsca. Niczego też nie chce usuwać, ponieważ „wszystko jest bardzo ważne i potrzebne”. I co z tym zrobić?
Taki problem dotyczy nie tylko jego. Na naszych dyskach twardych spoczywa terabajty informacji, a ta ilość nie ma tendencji do zmniejszania się. Ale jak unikalne są te dane? W końcu, wszystkie pliki to tylko zbiory bitów o określonej długości i, najprawdopodobniej, nowy plik niewiele różni się od tego, który już jest przechowywany.
Oczywiście, że szukanie już przechowywanych fragmentów informacji na dysku twardym to zadanie, które, jeśli nie jest beznadziejne, to przynajmniej mało efektywne. Z drugiej strony, jeśli różnica jest mała, to można ją nieco dostosować...
TL;DR — druga próba opowiedzenia o dziwacznej metodzie optymalizacji danych za pomocą plików JPEG, teraz w bardziej zrozumiałej formie.
O bitach i różnicy
Jeśli weźmiemy dwa całkowicie losowe kawałki danych, to w średniej połowa zawartych w nich bitów się pokrywa. To prawda, wśród możliwych rozkładów dla każdej pary (’00, 01, 10, 11′) dokładnie połowa ma pokrywające się wartości, zatem sprawa jest prosta.
Jednak oczywiście, jeśli po prostu weźmiemy dwa pliki i dostosujemy jeden do drugiego, to stracimy jeden z nich. Jeśli jednak będziemy zapisywać zmiany, to na nowo wynajdziemy , które i bez nas doskonale funkcjonuje, choć zazwyczaj nie jest stosowane w tych samych celach. Można próbować wbudować mniejszą sekwencję w większą, ale nawet w ten sposób ryzykujemy utratę krytycznych segmentów danych przy nieprzemyślanym użyciu wszystkiego naraz.
Czego zatem można używać do eliminacji różnicy? Chodzi o to, że nowy plik zapisywany przez użytkownika to po prostu sekwencja bitów, z którą samej w sobie nic nie możemy zrobić. Należy zatem znaleźć na dysku twardym takie bity, które można zmieniać bez konieczności przechowywania różnicy, aby można było przeżyć ich utratę bez poważnych konsekwencji. Zmiany mają sens nie tylko dla samego pliku na systemie plików, ale także dla jakiejś mniej wrażliwej informacji wewnątrz niego. Ale jaką i jak?
Metody dopasowania
Na pomoc przychodzą pliki kompresowane z utratą jakości. Wszystkie te jpeg, mp3 i inne, choć są kompresją stratną, zawierają mnóstwo bitów dostępnych do bezpiecznej modyfikacji. Można użyć zaawansowanych technik, które w sposób niewidoczny modyfikują ich składniki w różnych fragmentach kodowania. Poczekaj, zaawansowane techniki… niewidoczna modyfikacja… jedne bity w inne… to prawie coś jak !
Rzeczywiście, wstawianie jednej informacji w drugą przypomina jej metody. Imponuje także niewidoczność przeprowadzonych zmian dla ludzkich organów zmysłów. Tutaj drogi się rozchodzą — chodzi o tajność: nasze zadanie sprowadza się do wprowadzenia przez użytkownika dodatkowej informacji na jego twardym dysku, co tylko mu zaszkodzi. Jeszcze o tym zapomni.
Dlatego, choć możemy je wykorzystać, musimy wprowadzić pewne modyfikacje. I dalej opowiem i pokażę to na przykładzie jednej z istniejących metod i popularnego formatu plików.
O szakalach
Jeśli już kompresować, to najbardziej kompresowalny na świecie. Mowa oczywiście o plikach JPEG. I nie dość, że istnieje tona narzędzi i metod do wstawiania danych w ten format, to jest on najpopularniejszym formatem graficznym na tej planecie.
Niemniej jednak, aby nie zajmować się kynologią, należy ograniczyć swoje pole działania do plików tego formatu. Nikt nie lubi jednolitych kwadratów, które powstają w wyniku nadmiernej kompresji, dlatego należy ograniczyć się do pracy z już skompresowanym plikiem, unikać ponownego kodowania. Konkretne — całkowitymi współczynnikami, które pozostają po operacjach odpowiadających za utraty danych — DCT i kwantyzacji, co doskonale ilustruje schemat kodowania (dzięki wiki Narodowej Biblioteki im. Bauman):
Istnieje wiele możliwych metod optymalizacji plików jpeg. Istnieje optymalizacja bezstratna (jpegtran), jest też optymalizacja „“, które tak naprawdę jeszcze wiele wprowadzają, ale nas to nie interesuje. Jeśli użytkownik jest gotów wstawiać jedną informację w drugą, aby zwiększyć wolne miejsce na dysku, to jego obrazy zostały albo dawno zoptymalizowane, albo wręcz nie chce tego robić z obawy przed utratą jakości.
F5
Do takich warunków pasuje całe rodziny algorytmów, z którymi można się zapoznać . Najbardziej zaawansowanym z nich jest algorytm opatrzony nazwiskiem Andreasa Westfelda, który działa na współczynnikach jasności, ponieważ ludzkie oko jest najsłabiej wrażliwe na jej zmiany. Co więcej, wykorzystuje metodę osadzania opartą na kodowaniu macierzy, dzięki czemu może wprowadzać tym mniej zmian przy osadzaniu tej samej ilości informacji, im większy rozmiar używanego kontenera.
Same zmiany sprowadzają się do zmniejszenia bezwzględnej wartości współczynników o jeden w określonych warunkach (to znaczy, nie zawsze), co pozwala wykorzystać F5 do optymalizacji przechowywania danych na dysku twardym. Chodzi o to, że współczynnik po takiej zmianie prawdopodobnie zajmie mniejszą liczbę bitów po przeprowadzeniu kodowania Huffmana z powodu statystycznego rozkładu wartości w JPEG, a nowe zera przyniosą korzyści przy kodowaniu ich za pomocą RLE.
Wymagane modyfikacje sprowadzają się do usunięcia części odpowiedzialnej za poufność (złożoną permutację), co pozwala oszczędzać zasoby i czas wykonywania, oraz dodania mechanizmu pracy z wieloma plikami zamiast jednego na raz. Bardziej szczegółowy proces zmiany czytelnikowi raczej nie będzie interesujący, dlatego przechodzimy do opisu implementacji.
Wysokie technologie
Aby zademonstrować działanie takiego podejścia, zaimplementowałem metodę w czystym C i przeprowadziłem szereg optymalizacji zarówno pod względem szybkości wykonania, jak i pamięci (nie wyobrażacie sobie, ile te obrazki ważą nawet bez kompresji do DCT). Międzyplatformowość osiągnięto dzięki kombinacji bibliotek , i , za co im dziękuję. Wszystko to kompiluje się za pomocą 'make', więc użytkownicy Windows, aby ocenić, muszą zainstalować Cygwin lub samodzielnie poradzić sobie z Visual Studio i bibliotekami.
Implementacja jest dostępna w postaci narzędzia konsolowego i biblioteki. Osoby zainteresowane korzystaniem z tej ostatniej mogą zapoznać się z instrukcją w readme w repozytorium na GitHubie, link do którego dołączę na końcu postu.
Jak z tego korzystać?
Z ostrożnością. Obrazy używane do pakowania są wybierane za pomocą wyrażeń regularnych w określonym katalogu głównym. Po zakończeniu pliki można przenosić, zmieniać nazwy oraz kopiować według uznania w jego obrębie, zmieniać systemy plików i operacyjne itp. Jednakże, należy być niezwykle ostrożnym i w żadnym wypadku nie zmieniać samej treści. Utrata wartości nawet jednego bitu może prowadzić do niemożności przywrócenia informacji.
Po zakończeniu pracy, narzędzie pozostawia specjalny plik archiwum, zawierający wszystkie niezbędne informacje do rozpakowania, w tym dane o użytych obrazach. Sam w sobie waży około kilku kilobajtów i nie ma znaczącego wpływu na zajmowaną przestrzeń dyskową.
Można analizować możliwą pojemność za pomocą flagi ‘-a’: ‘.\/f5ar -a [katalog wyszukiwania] [wyrażenie regularne zgodne z Perl]’. Pakowanie odbywa się poleceniem ‘.\/f5ar -p [katalog wyszukiwania] [wyrażenie regularne zgodne z Perl] [pakowany plik] [nazwa archiwum]’, a rozpakowanie za pomocą ‘.\/f5ar -u [plik archiwum] [nazwa przywróconego pliku]’.
Prezentacja działania
Aby pokazać skuteczność metody, załadowałem kolekcję 225 całkowicie darmowych zdjęć psów z serwisu i odkryłem w dokumentach dużego pdf-a o 45 metrach drugiego tomu Knutha.
Sekwencja jest dość prosta:
$ du -sh knuth.pdf dogs\/
44M knuth.pdf
633M dogs\/
$ .\/f5ar -p dogs\/ .*jpg knuth.pdf dogs.f5ar
Czytam plik kompresji... ok
Inicjalizuję archiwum... ok
Analizuję pojemność biblioteki... zakończono w 17.0s
Wykryto wstępną pojemność 48439359 bajtów
Wykryto możliwą pojemność do 102618787 bajtów
Kompresuję... zakończono w 39.4s
Zapisuję archiwum... ok
$ .\/f5ar -u dogs\/dogs.f5ar knuth_unpacked.pdf
Inicjalizuję archiwum... ok
Czytam plik archiwum... ok
Wypełniam archiwum plikami... zakończono w 1.4s
Dezypresja... zakończono w 21.0s
Piszę dane wyekstrahowane... ok
$ sha1sum knuth.pdf knuth_unpacked.pdf
5bd1f496d2e45e382f33959eae5ab15da12cd666 knuth.pdf
5bd1f496d2e45e382f33959eae5ab15da12cd666 knuth_unpacked.pdf
$ du -sh dogs\/
551M dogs\/Zrzuty ekranu dla miłośników
Rozpakowany plik wciąż można i należy czytać:
Jak widać, z początkowych 633 + 36 == 669 megabajtów danych na dysku twardym doszliśmy do bardziej zadowalających 551. Taka radykalna różnica wynika z tego samego zmniejszenia wartości współczynników, które wpływają na ich późniejsze bezstratne kompresowanie: zmniejszenie jednej wartości zaledwie o jedno może spokojnie "odciąć" kilka bajtów z końcowego pliku. Niemniej jednak, to wciąż są straty danych, choć bardzo niewielkie, z którymi trzeba się pogodzić.
Na szczęście, dla oka są one zupełnie niewidoczne. Pod spoilerem (ponieważ habrastorage nie obsługuje dużych plików) czytelnik może ocenić różnicę zarówno na oko, jak i jej intensywność, uzyskaną przez odjęcie wartości zmienionej komponenty od oryginalnej: , , (im bardziej stonowany kolor, tym mniejsze różnice w bloku).
Zamiast zakończenia
Patrząc na te wszystkie trudności, zakup dysku twardego lub wrzucenie wszystkiego do chmury może wydawać się znacznie prostszym rozwiązaniem problemu. Ale mimo że teraz żyjemy w tak wspaniałych czasach, nie ma żadnych gwarancji, że jutro nadal będziemy mogli połączyć się z Internetem i gdzieś wrzucić wszystkie swoje zbędne dane. Lub przyjść do sklepu i kupić kolejny dysk twardy o pojemności tysiąca terabajtów. A już istniejące w domu zawsze można wykorzystać.
->
Źródło: habr.com
