Inny użytkownik chce zapisać nowy fragment danych na dysku twardym, ale nie ma na to wystarczającej ilości wolnego miejsca. Nie chcę też niczego usuwać, bo „wszystko jest bardzo ważne i konieczne”. I co powinniśmy z tym zrobić?
Nikt nie ma tego problemu. Na naszych dyskach twardych znajdują się terabajty informacji i ilość ta nie ma tendencji do zmniejszania się. Ale na ile jest to wyjątkowe? Ostatecznie wszystkie pliki to po prostu zestawy bitów o określonej długości i najprawdopodobniej nowy nie różni się zbytnio od tego, który jest już zapisany.
Oczywiste jest, że wyszukiwanie informacji już zapisanych na dysku twardym jest, jeśli nie porażką, to przynajmniej nieefektywnym zadaniem. Natomiast jeśli różnica jest niewielka to można ją trochę skorygować...
TL;DR - druga próba omówienia dziwnej metody optymalizacji danych przy użyciu plików JPEG, teraz w bardziej zrozumiałej formie.
O bitach i różnicach
Jeśli weźmiesz dwa całkowicie losowe fragmenty danych, to średnio połowa bitów, które zawierają, pokrywa się. Rzeczywiście, spośród możliwych układów dla każdej pary („00, 01, 10, 11′) dokładnie połowa ma takie same wartości, tutaj wszystko jest proste.
Ale oczywiście, jeśli po prostu weźmiemy dwa pliki i dopasujemy jeden do drugiego, stracimy jeden z nich. Jeśli zapiszemy zmiany, po prostu wymyślimy je na nowo , który doskonale funkcjonuje bez nas, choć zwykle nie jest wykorzystywany do tych samych celów. Możemy spróbować osadzić mniejszą sekwencję w większej, ale mimo to ryzykujemy utratę krytycznych segmentów danych, jeśli użyjemy ich lekkomyślnie do wszystkiego.
Pomiędzy czym a czym zatem można wyeliminować różnicę? Otóż, czyli nowy plik napisany przez użytkownika to po prostu ciąg bitów, z którym sami nie jesteśmy w stanie nic zrobić. Następnie wystarczy znaleźć na dysku takie bity, aby dało się je podmienić bez konieczności zapamiętywania różnicy, tak aby można było przeżyć ich utratę bez poważnych konsekwencji. Sensowne jest także zmienianie nie tylko pliku w samym systemie plików, ale także niektórych mniej wrażliwych informacji w nim zawartych. Ale który i jak?
Metody dopasowania
Na ratunek przychodzą pliki skompresowane stratnie. Wszystkie te pliki JPEG, MP3 i inne, mimo kompresji stratnej, zawierają kilka bitów, które można bezpiecznie zmienić. Możliwe jest zastosowanie zaawansowanych technik, które w niezauważalny sposób modyfikują swoje składowe na różnych etapach kodowania. Czekać. Zaawansowane techniki... niezauważalna modyfikacja... kawałek w drugi... to prawie tak !
Rzeczywiście, osadzanie jednej informacji w drugiej przypomina jej metody jak nic innego. Imponuje mi także niedostrzegalność zmian, jakie zachodzą w ludzkich zmysłach. Tam, gdzie ścieżki się rozchodzą, pozostaje tajemnicą: nasze zadanie sprowadza się do tego, że użytkownik wprowadzi na swój twardy dysk dodatkowe informacje, co mu tylko zaszkodzi. Znowu zapomni.
Dlatego chociaż możemy z nich skorzystać, musimy wprowadzić pewne modyfikacje. A potem opowiem i pokażę na przykładzie jednej z istniejących metod i wspólnego formatu pliku.
O szakalach
Jeśli naprawdę go ściśniesz, jest to najbardziej ściśliwa rzecz na świecie. Mówimy oczywiście o plikach JPEG. Nie tylko istnieje mnóstwo narzędzi i istniejących metod osadzania w nim danych, ale jest to najpopularniejszy format graficzny na tej planecie.
Aby jednak nie zajmować się hodowlą psów, należy ograniczyć swoje pole działania w plikach tego formatu. Nikt nie lubi monochromatycznych kwadratów pojawiających się na skutek nadmiernej kompresji, dlatego należy ograniczyć się do pracy z już skompresowanym plikiem, unikanie przekodowywania. A dokładniej ze współczynnikami całkowitymi, które pozostają po operacjach odpowiedzialnych za utratę danych - DCT i kwantyzacji, co doskonale widać w schemacie kodowania (dzięki wiki Biblioteki Narodowej Baumana):
Istnieje wiele możliwych metod optymalizacji plików JPEG. Jest optymalizacja bezstratna (jpegtran), jest optymalizacja”„, które tak naprawdę wnoszą coś innego, ale nie przejmujemy się nimi. W końcu, jeśli użytkownik jest gotowy osadzić jedną informację w drugiej, aby zwiększyć ilość wolnego miejsca na dysku, to albo już dawno zoptymalizował swoje obrazy, albo w ogóle nie chce tego robić w obawie przed utratą jakości.
F5
Do tych warunków spełnia cała rodzina algorytmów, z którymi możesz się zapoznać . Najbardziej zaawansowanym z nich jest algorytm Andreasa Westfelda, pracującego ze współczynnikami składowej jasności, ponieważ oko ludzkie jest najmniej wrażliwe na jej zmiany. Ponadto wykorzystuje technikę osadzania opartą na kodowaniu macierzowym, co pozwala na dokonanie mniejszej liczby zmian przy osadzaniu tej samej ilości informacji, im większy jest rozmiar użytego kontenera.
Same zmiany sprowadzają się do zmniejszenia wartości bezwzględnej współczynników o jeden pod pewnymi warunkami (czyli nie zawsze), co pozwala wykorzystać klawisz F5 do optymalizacji przechowywania danych na dysku twardym. Rzecz w tym, że współczynnik po takiej zmianie najprawdopodobniej będzie zajmował mniej bitów po kodowaniu Huffmana ze względu na statystyczny rozkład wartości w JPEG, a nowe zera dadzą zysk przy kodowaniu ich za pomocą RLE.
Niezbędne modyfikacje sprowadzają się do wyeliminowania części odpowiedzialnej za tajemnicę (przegrupowanie haseł), co pozwala zaoszczędzić zasoby i czas wykonania, oraz dodania mechanizmu pracy z wieloma plikami zamiast jednego na raz. Bardziej szczegółowy przebieg procesu zmiany raczej nie zainteresuje czytelnika, zatem przejdźmy do opisu wdrożenia.
High tech
Aby zademonstrować działanie tego podejścia, zaimplementowałem metodę w czystym C i przeprowadziłem szereg optymalizacji zarówno pod kątem szybkości wykonania, jak i pamięci (nie możesz sobie wyobrazić, ile te zdjęcia ważą bez kompresji, nawet przed DCT). Wieloplatformowość osiągnięta dzięki kombinacji bibliotek , и , za co im dziękujemy. Wszystko to składa się w całość za pomocą narzędzia „make”, więc użytkownicy systemu Windows chcą zainstalować Cygwin dla siebie w celu oceny lub samodzielnie zająć się Visual Studio i bibliotekami.
Implementacja jest dostępna w postaci narzędzia konsolowego i biblioteki. Zainteresowani mogą dowiedzieć się więcej na temat korzystania z tego ostatniego w pliku readme w repozytorium na Githubie, do którego link załączę na końcu wpisu.
Jak korzystać?
Ostrożnie. Obrazy użyte do pakowania wybierane są poprzez wyszukiwanie za pomocą wyrażenia regularnego w podanym katalogu głównym. Po zakończeniu pliki można dowolnie przenosić, zmieniać ich nazwy i kopiować w ich granicach, zmieniać pliki i systemy operacyjne itp. Należy jednak zachować szczególną ostrożność i nie zmieniać w żaden sposób bezpośredniej zawartości. Utrata wartości choćby jednego bitu może uniemożliwić odzyskanie informacji.
Po zakończeniu narzędzie pozostawia specjalny plik archiwum zawierający wszystkie informacje niezbędne do rozpakowania, w tym dane o użytych obrazach. Sam waży około kilku kilobajtów i nie ma znaczącego wpływu na zajętą przestrzeń dyskową.
Możesz przeanalizować możliwą pojemność za pomocą flagi „-a”: „./f5ar -a [folder wyszukiwania] [wyrażenie regularne zgodne z Perlem]”. Pakowanie odbywa się za pomocą polecenia „./f5ar -p [folder wyszukiwania] [wyrażenie regularne zgodne z Perlem] [plik spakowany] [nazwa archiwum]”, a rozpakowywanie za pomocą „./f5ar -u [plik archiwum] [nazwa odzyskanego pliku ]' .
Demonstracja pracy
Aby pokazać skuteczność metody, wgrałem kolekcję 225 całkowicie darmowych zdjęć psów z serwisu i znalazłem w dokumentach duży plik PDF zawierający 45 metrów drugiego tomu Knuta.
Sekwencja jest dość prosta:
$ du -sh knuth.pdf dogs/
44M knuth.pdf
633M dogs/
$ ./f5ar -p dogs/ .*jpg knuth.pdf dogs.f5ar
Reading compressing file... ok
Initializing the archive... ok
Analysing library capacity... done in 17.0s
Detected somewhat guaranteed capacity of 48439359 bytes
Detected possible capacity of upto 102618787 bytes
Compressing... done in 39.4s
Saving the archive... ok
$ ./f5ar -u dogs/dogs.f5ar knuth_unpacked.pdf
Initializing the archive... ok
Reading the archive file... ok
Filling the archive with files... done in 1.4s
Decompressing... done in 21.0s
Writing extracted data... ok
$ sha1sum knuth.pdf knuth_unpacked.pdf
5bd1f496d2e45e382f33959eae5ab15da12cd666 knuth.pdf
5bd1f496d2e45e382f33959eae5ab15da12cd666 knuth_unpacked.pdf
$ du -sh dogs/
551M dogs/Zrzuty ekranu dla fanów
Rozpakowany plik można i należy nadal czytać:
Jak widać z oryginalnych 633 + 36 == 669 megabajtów danych na dysku twardym doszliśmy do przyjemniejszego 551. Tak radykalną różnicę tłumaczy się spadkiem wartości współczynników, co wpływa na ich późniejsza kompresja bezstratna: redukcja jeden po drugim może z łatwością „odciąć kilka bajtów z pliku końcowego”. Jest to jednak nadal utrata danych, choć niezwykle niewielka, z którą będziesz musiał się pogodzić.
Na szczęście są one całkowicie niewidoczne dla oka. Pod spoilerem (ponieważ Habrastorage nie radzi sobie z dużymi plikami) czytelnik może ocenić różnicę zarówno naocznie, jak i ich intensywność, uzyskaną poprzez odjęcie wartości zmienionego komponentu od oryginału: , , (im ciemniejszy kolor, tym mniejsza różnica w bloku).
Zamiast zawierania
Biorąc pod uwagę wszystkie te trudności, zakup dysku twardego lub przesłanie wszystkiego do chmury może wydawać się znacznie prostszym rozwiązaniem problemu. Ale mimo że żyjemy teraz w tak cudownych czasach, nie ma gwarancji, że jutro nadal będzie można połączyć się z Internetem i przesłać gdzieś wszystkie dodatkowe dane. Lub idź do sklepu i kup sobie kolejny tysiąc terabajtowy dysk twardy. Ale zawsze możesz skorzystać z istniejących domów.
->
Źródło: www.habr.com