Чарговы карыстач жадае запісаць на цвёрдую кружэлку новы кавалак дадзеных, але яму бракуе вольнага месца для гэтага. Выдаляць таксама нічога не хочацца, бо "ўсё вельмі важнае і патрэбнае". І што нам з ім рабіць?
Такая праблема ўстае ні ў яго аднаго. На нашых жорсткіх дысках тэрабайты інфармацыі, і гэтая колькасць не імкнецца памяншацца. Але наколькі яна ўнікальная? У рэшце рэшт, бо ўсе файлы гэта толькі наборы біт вызначанай даўжыні і, хутчэй за ўсё, новая не моцна адрозніваецца ад той, што ўжо захоўваецца.
Зразумелая справа, што шукаць ужо якія захоўваюцца кавалкі інфармацыі на цвёрдым дыску - задача калі не правальная, то як мінімум не эфектыўная. З іншага боку, калі розніца невялікая, то можна трохі і падагнаць…
TL; DR – другая спроба распавесці аб дзіўным метадзе аптымізацыі дадзеных з дапамогай JPEG-файлаў, зараз у больш зразумелай форме.
Аб бітах і розніцы
Калі ўзяць два цалкам выпадковых кавалка дадзеных, то ў іх супадае ў сярэднім палова якія змяшчаюцца бітаў. І праўда, сярод магчымых раскладаў для кожнай пары ('00, 01, 10, 11′) роўна палова мае супадаючыя значэнні, тут усё проста.
Але вядома, калі мы проста возьмем два файла і падгонім адзін пад другі, то мы пазбавімся аднаго з іх. Калі ж будзем захоўваць змены, то проста вынайдзем , якое і без нас цудоўна існуе, хоць і не выкарыстоўваецца звычайна ў такіх жа мэтах. Можна спрабаваць убудаваць меншую паслядоўнасць у вялікую, але нават так мы рызыкуем стратай крытычных сегментаў дадзеных пры неабдуманым выкарыстанні са ўсім запар.
Паміж чым і чым тады можна розніцу ўстараняць? Ну гэта значыць, які запісваецца карыстачом новы файл - проста паслядоўнасць біт, з якой самой па сабе мы нічога зрабіць не можам. Тады трэба проста знайсці на цвёрдым дыску такія біты, каб іх можна было змяняць без неабходнасці захоўваць розніцу, каб можна было перажыць іх страту без сур'ёзных наступстваў. Ды і змяняць ёсць сэнс не проста сам файл на ФС, але нейкую меней адчувальную інфармацыю ўсярэдзіне яго. Але якую і як?
Метады падганяння
На дапамогу прыходзяць файлы, сціснутыя са стратамі. Усе гэтыя jpeg, mp3 і іншыя хоць і з'яўляюцца сціскам са стратамі, утрымоўваюць кучу біт, даступных для бяспечнага змены. Можна выкарыстоўваць прасунутыя тэхнікі, незаўважнай выявай якія мадыфікуюць іх складнікі на розных участках кадавання. Пачакайце. Прасунутыя тэхнікі… незаўважная мадыфікацыя… адны бітыя ў іншыя… ды гэта ж амаль што !
І праўда, убудаванне адной інфармацыі ў іншую як ні што нагадвае яе метады. Імпануе таксама незаўважнасць праведзеных змен для чалавечых органаў пачуццяў. Вось у чым шляхі разыходзяцца — дык гэта ў сакрэтнасці: наша задача зводзіцца да занясення карыстачом на сваю цвёрдую кружэлку дадатковай інфармацыі, яму яна толькі пашкодзіць. Забудзе яшчэ.
Таму мы хоць і можам выкарыстоўваць іх, трэба правесці некаторыя мадыфікацыі. І далей я раскажу і пакажу іх на прыкладзе аднаго з існуючых метадаў і распаўсюджанага фармату файлаў.
Аб шакалах
Калі ўжо сціскаць, тое самае сцісканае ў свеце. Гаворка ідзе, вядома ж, аб JPEG-файлах. Мала таго, што існуе тона інструментара і існуючых метадаў для ўбудавання ў яго дадзеных, дык ён з'яўляецца самым папулярным графічным фарматам на гэтай планеце.
Тым не менш, каб не займацца сабакагадоўляй, трэба абмежаваць сваё поле дзейнасці ў файлах гэтага фармату. Ніхто не любіць аднакаляровыя квадрацікі, якія ўзнікаюць з-за залішняга сціску, таму трэба абмежавацца працай з ужо сціснутым файлам, пазбягаючы перакадавання. Канкрэтней - з цэлалікавымі каэфіцыентамі, якія і застаюцца пасля аперацый, якія адказваюць за страты дадзеных - ДКП і квантавання, што выдатна адлюстравана на схеме кадавання (дзякуй вікі нацыянальнай бібліятэкі ім. Баумана):
Існуе мноства магчымых метадаў аптымізацыі jpeg-файлаў. Ёсць аптымізацыя без страт (jpegtran), ёсць аптымізацыя.«, якія насамрэч яшчэ якія ўносяць, але нас яны не хвалююць. Бо калі карыстач гатовы ўбудоўваць адну інфармацыю ў іншую дзеля павелічэнні вольнага месца на дыску, то ён свае выявы або даўно аптымізаваў, або зусім гэтага рабіць не жадае з-за боязі страты якасці.
F5
Пад такія ўмовы падыходзіць цэлае сямейства алгарытмаў, з якім можна азнаёміцца. . Самым прасунутым з іх з'яўляецца алгарытм за аўтарствам Андрэаса Вестфелда, які працуе з каэфіцыентамі кампаненты яркасці, бо чалавечае вока найменш адчувальны менавіта да яе змен. Больш таго, ён выкарыстоўвае методыку ўбудавання, заснаваную на кадаванні матрыцы, дзякуючы чаму дазваляе можна здзяйсняць тым менш іх змен пры ўбудаванні адной і той жа колькасці інфармацыі, чым больш памер выкарыстоўванага кантэйнера.
Самі змены пры гэтым зводзяцца да памяншэння абсалютнага значэння каэфіцыентаў на адзінку ў вызначаных умовах (гэта значыць, не заўсёды), што і дазваляе выкарыстоўваць F5 для аптымізацыі захоўвання дадзеных на цвёрдым дыску. Справа ў тым, што каэфіцыент пасля такой змены, хутчэй за ўсё, будзе займаць меншую колькасць біт пасля правядзення кадавання Хаффмана з-за статыстычнага размеркавання значэнняў у JPEG, а новыя нулі дадуць выйгрыш пры кадаванні іх з дапамогай RLE.
Неабходныя мадыфікацыі зводзяцца да ўхілення часткі, якая адказвае за сакрэтнасць (парольнай перастановы), якая дазваляе эканоміць рэсурсы і час выканання, і даданні механізму працы з мноствам файлаў замест аднаго за раз. Больш падрабязна працэс змены чытачу ці наўрад будзе цікавы, таму пераходзім да апісання рэалізацыі.
Высокія тэхналогіі
Для дэманстрацыі працы такога падыходу я рэалізаваў метад на чыстым Сі і правёў шэраг аптымізацый як па хуткасці выканання, так і па памяці (вы не ўяўляеце, колькі гэтыя малюначкі важаць без сціску нават да DCT). Крос-платформеннасць дасягнута выкарыстаннем камбінацыі бібліятэк , и , за што ім дзякуй. Усё гэта збіраецца 'make»ам, таму карыстачы Windows для адзнакі жадаюць усталяваць сабе які-небудзь Cygwin, альбо разбірацца з Visual Studio і бібліятэкамі самастойна.
Рэалізацыя даступна ў форме кансольнай утыліты і бібліятэкі. Падрабязней пра выкарыстанне апошняй жадаючыя могуць азнаёміцца ў рыдмі ў рэпазітары на гітхабе, спасылку на які я прыкладу ў канцы посту.
Як выкарыстоўваць?
З асцярогай. Выкарыстоўваныя для пакавання малюнка выбіраюцца пошукам па рэгулярным выразе ў зададзенай каранёвай дырэкторыі. Па завяршэнні файлы можна перамяшчаць, пераназываць і капіяваць па жаданні ў яе межах, змяняць файлавую і аперацыйныя сістэмы і інш. Аднак, варта быць вельмі акуратным і ніяк не змяняць непасрэднае змесціва. Страта значэння нават аднаго біта можа прывесці да немагчымасці аднаўлення інфармацыі.
Па завяршэнні працы ўтыліта пакідае спецыяльны файл архіва, які змяшчае ўсю неабходную для распакавання інфармацыю, уключаючы дадзеныя аб выкарыстаных малюнках. Сам па сабе ён важыць парадку пары кілабайт і хоць колькі істотнага ўплыву на занятую дыскавую прастору не аказвае.
Можна аналізаваць магчымую ёмістасць дапамогай сцяга '-a': './f5ar -a [тэчка пошуку] [Perl-сумяшчальны рэгулярны выраз]’. Упакоўка вырабляецца камандай './f5ar -p [тэчка пошуку] [Perl-сумяшчальны рэгулярны выраз] [упакоўваны файл] [імя архіва]', а распакаванне з дапамогай './f5ar -u [файл архіва] [імя адноўленага файла]' .
Дэманстрацыя працы
Каб паказаць эфектыўнасць працы метаду, я загрузіў калекцыю з 225 абсалютна бясплатных фатаграфій сабак з сэрвісу і адкапаў у дакументах вялікую pdf-ку на 45 метраў другога тома Пуга.
Паслядоўнасць даволі просты:
$ 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/Скрыншоты для аматараў
Распакаваны файл усё яшчэ можна і трэба чытаць:
Як відаць, з зыходных 633 + 36 == 669 мегабайт дадзеных на цвёрдай кружэлцы мы дашлі да прыямнейшых 551. Такая радыкальная розніца тлумачыцца тым самым памяншэннем значэнняў каэфіцыентаў, якія ўплываюць на іх наступнае сціск без страт: памяншэнне аднаго ўсяго толькі на адзінку можа спакойна. зрэзаць» парачку байт з выніковага файла. Тым не менш, гэта ўсё роўна страты дадзеных, няхай і вельмі невялікія, з якімі давядзецца мірыцца.
На шчасце, для вока яны не прыкметныя абсалютна. Пад спойлерам (бо habrastorage не ўмее ў вялікія файлы) чытач можа ацаніць розніцу як на вока, так і іх інтэнсіўнасць, атрыманую адніманне значэнняў змененай кампаненты з арыгінальнай: , , (чым цьмяней колер, тым менш адрозненне ў блоку).
замест заключэння
Гледзячы на ўсе гэтыя складанасці, купіць цвёрдую кружэлку або заліць усё ў воблака можа здацца куды прасцейшым рашэннем праблемы. Але хоць зараз мы і жывем у такі цудоўны час, няма ніякіх гарантый, што заўтра ўсё яшчэ можна будзе выйсці ў інтэрнэт і заліць куды-небудзь усе свае лішнія дадзеныя. Або прыйсці ў краму і купіць сабе чарговую цвёрдую кружэлку на тысячу тэрабайт. А вось выкарыстоўваць ужо ляжалыя дамы можна заўсёды.
->
Крыніца: habr.com