Nais ng isa pang user na magsulat ng bagong piraso ng data sa hard drive, ngunit wala siyang sapat na libreng espasyo para gawin ito. Hindi ko rin gustong tanggalin ang anuman, dahil "lahat ay napakahalaga at kailangan." At ano ang dapat nating gawin dito?
Walang sinuman ang may ganitong problema. Mayroong mga terabyte ng impormasyon sa aming mga hard drive, at ang halagang ito ay hindi malamang na bumaba. Ngunit gaano ito kakaiba? Sa huli, ang lahat ng mga file ay mga hanay lamang ng mga piraso ng isang tiyak na haba at, malamang, ang bago ay hindi gaanong naiiba sa isa na nakaimbak na.
Malinaw na ang paghahanap ng mga piraso ng impormasyon na nakaimbak na sa isang hard drive ay, kung hindi isang pagkabigo, hindi bababa sa hindi isang epektibong gawain. Sa kabilang banda, kung maliit ang pagkakaiba, maaari mo itong ayusin ng kaunti...
TL;DR - ang pangalawang pagtatangka na pag-usapan ang tungkol sa isang kakaibang paraan ng pag-optimize ng data gamit ang mga JPEG file, ngayon sa isang mas naiintindihan na anyo.
Tungkol sa mga bit at pagkakaiba
Kung kukuha ka ng dalawang ganap na random na piraso ng data, pagkatapos ay sa average na kalahati ng mga bit na naglalaman ng mga ito ay nag-tutugma. Sa katunayan, kabilang sa mga posibleng layout para sa bawat pares ('00, 01, 10, 11β²), eksaktong kalahati ay may parehong mga halaga, ang lahat ay simple dito.
Pero siyempre, kung kukuha lang tayo ng dalawang file at magkasya ang isa sa pangalawa, mawawala ang isa sa kanila. Kung i-save namin ang mga pagbabago, iimbento lang namin , na ganap na umiiral nang wala tayo, bagama't hindi ito karaniwang ginagamit para sa parehong mga layunin. Maaari naming subukang mag-embed ng mas maliit na sequence sa mas malaki, ngunit kahit na ganoon ay nanganganib kaming mawala ang mga kritikal na segment ng data kung gagamitin namin ito nang walang ingat sa lahat.
Sa pagitan ng ano at ano pagkatapos ay maaaring alisin ang pagkakaiba? Well, iyon ay, ang isang bagong file na isinulat ng gumagamit ay isang pagkakasunud-sunod lamang ng mga bit, kung saan hindi namin magagawa ang anumang bagay nang mag-isa. Pagkatapos ay kailangan mo lamang na makahanap ng mga naturang piraso sa hard drive na maaari silang mabago nang hindi kinakailangang mag-imbak ng pagkakaiba, upang makaligtas ka sa kanilang pagkawala nang walang malubhang kahihinatnan. At makatuwirang baguhin hindi lamang ang file sa FS mismo, ngunit ang ilang hindi gaanong sensitibong impormasyon sa loob nito. Ngunit alin at paano?
Mga pamamaraan ng angkop
Ang mga nawawalang naka-compress na file ay sumagip. Ang lahat ng mga jpeg, mp3 at iba pa na ito, bagama't lossy compression, ay naglalaman ng isang grupo ng mga bit na maaaring ligtas na baguhin. Posibleng gumamit ng mga advanced na diskarte na hindi mahahalata na nagbabago ng kanilang mga bahagi sa iba't ibang yugto ng pag-encode. Teka. Mga advanced na diskarte... hindi mahahalata na pagbabago... isang bit sa isa pa... ito ay halos tulad ng !
Sa katunayan, ang pag-embed ng isang impormasyon sa isa pa ay nagpapaalala sa kanyang mga pamamaraan na walang iba. Ako din ay humanga sa hindi mahahalata ng mga pagbabagong ginawa sa pandama ng tao. Kung saan ang mga landas ay naghihiwalay ay nasa lihim: ang aming gawain ay napupunta sa gumagamit na magpasok ng karagdagang impormasyon sa kanyang hard drive; ito ay makakasama lamang sa kanya. Makakalimutin na naman siya.
Samakatuwid, kahit na maaari nating gamitin ang mga ito, kailangan nating gumawa ng ilang mga pagbabago. At pagkatapos ay sasabihin at ipapakita ko sa kanila gamit ang halimbawa ng isa sa mga umiiral na pamamaraan at isang karaniwang format ng file.
Tungkol sa jackals
Kung talagang pipigain mo ito, ito ang pinaka-compressible na bagay sa mundo. Siyempre, pinag-uusapan natin ang tungkol sa mga JPEG file. Hindi lamang mayroong maraming mga tool at umiiral na mga pamamaraan para sa pag-embed ng data dito, ngunit ito ang pinakasikat na format ng graphics sa planetang ito.
Gayunpaman, upang hindi makisali sa pag-aanak ng aso, kailangan mong limitahan ang iyong larangan ng aktibidad sa mga file ng format na ito. Walang may gusto sa mga monochrome na parisukat na lumilitaw dahil sa labis na compression, kaya kailangan mong limitahan ang iyong sarili sa pagtatrabaho sa isang naka-compress na file, pag-iwas sa recoding. Mas partikular, na may mga integer coefficient, na nananatili pagkatapos ng mga operasyon na responsable para sa pagkawala ng data - DCT at quantization, na perpektong ipinapakita sa encoding scheme (salamat sa wiki ng Bauman National Library):
Maraming posibleng paraan para sa pag-optimize ng mga jpeg file. Mayroong lossless optimization (jpegtran), mayroong optimization "", na talagang nag-aambag ng iba, ngunit wala kaming pakialam sa kanila. Pagkatapos ng lahat, kung ang gumagamit ay handa na upang i-embed ang isang impormasyon sa isa pa upang madagdagan ang libreng puwang sa disk, pagkatapos ay na-optimize niya ang kanyang mga imahe nang matagal na ang nakalipas, o ayaw niyang gawin ito dahil sa takot sa pagkawala ng kalidad.
F5
Ang isang buong pamilya ng mga algorithm ay umaangkop sa mga kundisyong ito, na maaari mong maging pamilyar sa iyong sarili . Ang pinaka-advanced sa kanila ay ang algorithm ni Andreas Westfeld, nagtatrabaho sa mga coefficient ng bahagi ng liwanag, dahil ang mata ng tao ay ang pinaka-sensitive sa mga pagbabago nito. Bukod dito, gumagamit ito ng diskarte sa pag-embed batay sa pag-encode ng matrix, na ginagawang posible na gumawa ng mas kaunting mga pagbabago kapag nag-embed ng parehong dami ng impormasyon, mas malaki ang sukat ng container na ginamit.
Ang mga pagbabago mismo ay bumagsak sa pagbabawas ng ganap na halaga ng mga koepisyent ng isa sa ilalim ng ilang mga kundisyon (iyon ay, hindi palaging), na nagpapahintulot sa iyo na gumamit ng F5 upang i-optimize ang imbakan ng data sa iyong hard drive. Ang punto ay ang koepisyent pagkatapos ng naturang pagbabago ay malamang na sumasakop ng mas kaunting mga piraso pagkatapos ng pag-encode ng Huffman dahil sa istatistikal na pamamahagi ng mga halaga sa JPEG, at ang mga bagong zero ay magbibigay ng pakinabang kapag na-encode ang mga ito gamit ang RLE.
Ang mga kinakailangang pagbabago ay kumukulo hanggang sa pag-aalis ng bahaging responsable para sa paglilihim (pag-aayos ng password), na nakakatipid ng mga mapagkukunan at oras ng pagpapatupad, at pagdaragdag ng isang mekanismo para sa pagtatrabaho sa maraming mga file sa halip na isa-isa. Ang mambabasa ay malamang na hindi interesado sa proseso ng pagbabago nang mas detalyado, kaya lumipat tayo sa isang paglalarawan ng pagpapatupad.
Mataas na tech
Upang ipakita kung paano gumagana ang diskarteng ito, ipinatupad ko ang pamamaraan sa purong C at nagsagawa ng ilang mga pag-optimize kapwa sa mga tuntunin ng bilis ng pagpapatupad at memorya (hindi mo maiisip kung gaano kabigat ang mga larawang ito nang walang compression, kahit na bago ang DCT). Nakamit ang cross-platform gamit ang kumbinasyon ng mga library , ΠΈ , kung saan pinasasalamatan namin sila. Ang lahat ng ito ay pinagsama-sama sa pamamagitan ng 'gumawa', kaya ang mga gumagamit ng Windows ay gustong mag-install ng ilang Cygwin para sa kanilang sarili para sa pagsusuri, o makitungo sa Visual Studio at mga aklatan nang mag-isa.
Ang pagpapatupad ay magagamit sa anyo ng isang console utility at library. Ang mga interesado ay maaaring malaman ang higit pa tungkol sa paggamit ng huli sa readme sa repositoryo sa Github, ang link kung saan ilalagay ko sa dulo ng post.
Paano gamitin?
Maingat. Ang mga larawang ginamit para sa packaging ay pinili sa pamamagitan ng paghahanap gamit ang isang regular na expression sa ibinigay na root directory. Sa pagkumpleto, ang mga file ay maaaring ilipat, palitan ang pangalan at kopyahin sa loob ng mga hangganan nito, baguhin ang file at mga operating system, atbp. Gayunpaman, dapat kang maging lubhang maingat at huwag baguhin ang agarang nilalaman sa anumang paraan. Ang pagkawala ng halaga ng kahit isang bit ay maaaring maging imposible na mabawi ang impormasyon.
Sa pagkumpleto, ang utility ay nag-iiwan ng isang espesyal na archive file na naglalaman ng lahat ng impormasyong kinakailangan para sa pag-unpack, kabilang ang data tungkol sa mga imaheng ginamit. Sa sarili nito, tumitimbang ito ng mga ilang kilobytes at walang anumang makabuluhang epekto sa inookupahang espasyo sa disk.
Maaari mong suriin ang posibleng kapasidad gamit ang '-a' flag: './f5ar -a [search folder] [Perl-compatible regular expression]'. Ginagawa ang pag-iimpake gamit ang command na './f5ar -p [search folder] [Perl-compatible na regular na expression] [packed file] [archive name]', at pag-unpack gamit ang './f5ar -u [archive file] [recovered file name] ]' .
Pagpapakita ng trabaho
Upang ipakita ang pagiging epektibo ng pamamaraan, nag-upload ako ng isang koleksyon ng 225 ganap na libreng mga larawan ng mga aso mula sa serbisyo. at natagpuan sa mga dokumento ang isang malaking pdf na 45 metro ng pangalawang volume Knuta.
Ang pagkakasunud-sunod ay medyo simple:
$ 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/Mga screenshot para sa mga tagahanga
Ang na-unpack na file ay maaari at dapat pa ring basahin:
Tulad ng nakikita mo, mula sa orihinal na 633 + 36 == 669 megabytes ng data sa hard drive, nakarating kami sa mas kaaya-aya na 551. Ang gayong radikal na pagkakaiba ay ipinaliwanag sa pamamagitan ng pagbaba sa mga halaga ng mga coefficient, na nakakaapekto sa kanilang kasunod na lossless compression: ang pagbabawas ng isa-isa ay madaling " maputol ang ilang byte mula sa huling file. Gayunpaman, ito ay isang pagkawala pa rin ng data, kahit na isang napakaliit, na kailangan mong tiisin.
Sa kabutihang palad, sila ay ganap na hindi nakikita ng mata. Sa ilalim ng spoiler (dahil hindi mahawakan ng habrastorage ang malalaking file), masusuri ng mambabasa ang pagkakaiba kapwa sa pamamagitan ng mata at kanilang intensity, na nakuha sa pamamagitan ng pagbabawas ng mga halaga ng binagong bahagi mula sa orihinal: , , (mas duller ang kulay, mas maliit ang pagkakaiba sa block).
Sa halip ng isang konklusyon
Isinasaalang-alang ang lahat ng mga paghihirap na ito, ang pagbili ng isang hard drive o pag-upload ng lahat sa cloud ay maaaring mukhang isang mas simpleng solusyon sa problema. Ngunit kahit na nabubuhay tayo sa napakagandang panahon ngayon, walang mga garantiya na bukas ay posible pa ring mag-online at mag-upload ng lahat ng iyong karagdagang data sa isang lugar. O pumunta sa tindahan at bumili ng isa pang libong terabyte hard drive. Ngunit palagi mong magagamit ang mga umiiral na bahay.
->
Pinagmulan: www.habr.com