Կոշտ սկավառակի տարածք խնայելու տարօրինակ մեթոդի մասին

Մեկ այլ օգտատեր ցանկանում է նոր տվյալներ գրել կոշտ սկավառակի վրա, բայց նա չունի բավարար ազատ տարածք դա անելու համար: Ես նաև չեմ ուզում որևէ բան ջնջել, քանի որ «ամեն ինչ շատ կարևոր է և անհրաժեշտ»: Իսկ ի՞նչ անենք դրա հետ։

Ոչ ոք այս խնդիրը չունի: Մեր կոշտ սկավառակների վրա կա տերաբայթ տեղեկատվություն, և այդ քանակությունը նվազման միտում չունի: Բայց որքանո՞վ է այն յուրահատուկ: Ի վերջո, բոլոր ֆայլերը պարզապես որոշակի երկարության բիթերի հավաքածու են և, ամենայն հավանականությամբ, նորը շատ չի տարբերվում արդեն պահվածից:

Հասկանալի է, որ կոշտ սկավառակի վրա արդեն պահված տեղեկատվության որոնումը, եթե ոչ ձախողում է, ապա գոնե արդյունավետ խնդիր չէ: Մյուս կողմից, եթե տարբերությունը փոքր է, ապա կարելի է մի փոքր հարմարեցնել...

TL;DR - JPEG ֆայլերի միջոցով տվյալների օպտիմալացման տարօրինակ մեթոդի մասին խոսելու երկրորդ փորձը, այժմ ավելի հասկանալի ձևով:

Բիթերի և տարբերության մասին

Եթե ​​վերցնում եք երկու լրիվ պատահական տվյալներ, ապա միջինում դրանց պարունակած բիթերի կեսը համընկնում են։ Իրոք, յուրաքանչյուր զույգի համար հնարավոր դասավորությունների շարքում ('00, 01, 10, 11'), ուղիղ կեսն ունեն նույն արժեքները, այստեղ ամեն ինչ պարզ է:

Բայց իհարկե, եթե մենք պարզապես վերցնենք երկու ֆայլ և տեղավորենք մեկը երկրորդին, ապա մենք կկորցնենք դրանցից մեկը: Եթե ​​մենք պահպանենք փոփոխությունները, մենք պարզապես նորից կհայտնենք դելտա կոդավորում, որը հիանալի գոյություն ունի առանց մեզ, թեև սովորաբար չի օգտագործվում նույն նպատակների համար։ Մենք կարող ենք փորձել ավելի փոքր հաջորդականություն ներդնել ավելի մեծի մեջ, բայց նույնիսկ այդ դեպքում մենք ռիսկի ենք դիմում կորցնել տվյալների կարևոր հատվածները, եթե դրանք անխոհեմ կերպով օգտագործենք ամեն ինչում:

Ինչի՞ և ինչի՞ միջև կարելի է վերացնել տարբերությունը: Դե, այսինքն՝ օգտատիրոջ կողմից գրված նոր ֆայլը ընդամենը բիթերի հաջորդականություն է, որոնցով մենք ինքնուրույն ոչինչ չենք կարող անել։ Այնուհետև պարզապես անհրաժեշտ է կոշտ սկավառակի վրա գտնել այնպիսի բիթեր, որոնք կարող են փոխվել առանց տարբերությունը պահելու, որպեսզի կարողանաք գոյատևել դրանց կորուստը առանց լուրջ հետևանքների: Եվ իմաստ ունի փոխել ոչ միայն բուն FS-ի ֆայլը, այլ դրա ներսում որոշ ավելի քիչ զգայուն տեղեկատվություն: Բայց ո՞րը և ինչպե՞ս:

Տեղադրման մեթոդներ

Փրկության են գալիս կորցրած սեղմված ֆայլերը: Այս բոլոր jpeg-երը, mp3-ները և մյուսները, թեև սեղմում են կորուստներով, պարունակում են մի շարք բիթներ, որոնք կարող են ապահով կերպով փոխվել: Հնարավոր է օգտագործել առաջադեմ տեխնիկա, որոնք աննկատ կերպով փոփոխում են դրանց բաղադրիչները կոդավորման տարբեր փուլերում: Սպասեք։ Ընդլայնված տեխնիկա... աննկատ մոդիֆիկացիա... մի բիթ մյուսի մեջ... դա գրեթե նման է ստեգանոգրաֆիա!

Իրոք, մեկ տեղեկատվության ներկառուցումը մյուսի մեջ հիշեցնում է նրա մեթոդները, ինչպես ուրիշ ոչինչ: Տպավորված եմ նաև մարդու զգայարաններում կատարված փոփոխությունների աննկատելիությամբ։ Այնտեղ, որտեղ ուղիները տարբերվում են գաղտնիության մեջ. մեր խնդիրն այն է, որ օգտատերը լրացուցիչ տեղեկություններ մուտքագրի իր կոշտ սկավառակի վրա, դա միայն կվնասի նրան: Նա նորից կմոռանա։

Ուստի, թեև մենք կարող ենք օգտագործել դրանք, մենք պետք է որոշ փոփոխություններ կատարենք: Եվ հետո ես կասեմ և ցույց կտամ նրանց՝ օգտագործելով գոյություն ունեցող մեթոդներից մեկի օրինակը և ֆայլի ընդհանուր ձևաչափը։

Շակալների մասին

Եթե ​​դուք իսկապես սեղմում եք այն, ապա դա աշխարհի ամենասեղմվող բանն է: Խոսքը, իհարկե, JPEG ֆայլերի մասին է։ Ոչ միայն կան բազմաթիվ գործիքներ և գոյություն ունեցող մեթոդներ դրանում տվյալներ ներդնելու համար, այլև դա այս մոլորակի վրա ամենահայտնի գրաֆիկական ձևաչափն է:

Այնուամենայնիվ, շան բուծմամբ չզբաղվելու համար հարկավոր է սահմանափակել ձեր գործունեության ոլորտը այս ձևաչափի ֆայլերում։ Ոչ ոք չի սիրում մոնոխրոմ քառակուսիները, որոնք հայտնվում են չափից ավելի սեղմման պատճառով, այնպես որ դուք պետք է սահմանափակվեք արդեն սեղմված ֆայլի հետ աշխատելով, խուսափելով վերակոդավորվելուց. Ավելի կոնկրետ՝ ամբողջ թվային գործակիցներով, որոնք մնում են տվյալների կորստի համար պատասխանատու գործառնություններից հետո՝ DCT և քվանտացում, որը հիանալի կերպով ցուցադրվում է կոդավորման սխեմայում (Բաումանի ազգային գրադարանի վիքիի շնորհիվ).

Կան բազմաթիվ հնարավոր մեթոդներ jpeg ֆայլերի օպտիմալացման համար: Կա անկորուստ օպտիմալացում (jpegtran), կա օպտիմալացում:ոչ մի կորուստ«, որոնք իրականում նպաստում են այլ բանի, բայց մենք թքած ունենք դրանց վրա: Ի վերջո, եթե օգտվողը պատրաստ է մի տեղեկություն ներդնել մյուսի մեջ՝ սկավառակի ազատ տարածությունը մեծացնելու համար, ապա նա կամ վաղուց օպտիմիզացրել է իր պատկերները, կամ ընդհանրապես չի ցանկանում դա անել՝ վախենալով որակի կորստից:

F5

Ալգորիթմների մի ամբողջ ընտանիք համապատասխանում է այս պայմաններին, որոնց կարող եք ծանոթանալ այս լավ ներկայացման մեջ. Դրանցից ամենաառաջադեմը ալգորիթմն է F5 Անդրեաս Վեստֆելդի կողմից՝ աշխատելով պայծառության բաղադրիչի գործակիցների հետ, քանի որ մարդու աչքը ամենաքիչ զգայուն է դրա փոփոխությունների նկատմամբ: Ավելին, այն օգտագործում է ներկառուցման տեխնիկա, որը հիմնված է մատրիցային կոդավորման վրա, ինչը հնարավորություն է տալիս ավելի քիչ փոփոխություններ կատարել նույն քանակությամբ տեղեկատվության ներդրման ժամանակ, որքան մեծ է օգտագործվող կոնտեյների չափը:

Փոփոխություններն ինքնին հանգում են որոշակի պայմաններում գործակիցների բացարձակ արժեքը մեկով նվազեցնելուն (այսինքն, ոչ միշտ), ինչը թույլ է տալիս օգտագործել F5-ը՝ կոշտ սկավառակի վրա տվյալների պահպանման օպտիմալացման համար: Բանն այն է, որ նման փոփոխությունից հետո գործակիցը, ամենայն հավանականությամբ, ավելի քիչ բիթ կզբաղեցնի Huffman-ի կոդավորումից հետո JPEG-ում արժեքների վիճակագրական բաշխվածության պատճառով, իսկ նոր զրոները շահույթ կտան RLE-ի միջոցով դրանք կոդավորելիս:

Անհրաժեշտ փոփոխությունները հանգում են գաղտնիության համար պատասխանատու մասի վերացմանը (գաղտնաբառի վերադասավորում), որը խնայում է ռեսուրսները և կատարման ժամանակը, և ավելացնում է բազմաթիվ ֆայլերի հետ աշխատելու մեխանիզմ՝ միաժամանակ մեկից հետո: Դժվար թե ընթերցողին ավելի մանրամասն հետաքրքրի փոփոխության գործընթացը, ուստի եկեք անցնենք կատարման նկարագրությանը:

Բարձր տեխնոլոգիաներ

Ցույց տալու համար, թե ինչպես է աշխատում այս մոտեցումը, ես մեթոդը կիրառեցի մաքուր C-ում և կատարեցի մի շարք օպտիմալացումներ ինչպես կատարման արագության, այնպես էլ հիշողության առումով (չեք պատկերացնում, թե որքան են այս նկարները կշռում առանց սեղմման, նույնիսկ մինչև DCT): Cross-platform-ը ձեռք է բերվել գրադարանների համակցության միջոցով libjpeg, հատ и փոքրիկ դիր, ինչի համար շնորհակալություն ենք հայտնում նրանց։ Այս ամենը հավաքվում է «make»-ի միջոցով, ուստի Windows-ի օգտատերերը ցանկանում են իրենց համար տեղադրել Cygwin-ի մի մասը՝ գնահատման համար, կամ ինքնուրույն զբաղվել Visual Studio-ի և գրադարանների հետ:

Իրականացումը հասանելի է կոնսոլի օգտակար և գրադարանի տեսքով: Ցանկացողները կարող են ավելին իմանալ վերջինիս օգտագործման մասին readme-ում Github-ի պահեստում, որի հղումը կցեմ գրառման վերջում։

Ինչպես օգտվել

Զգուշորեն. Փաթեթավորման համար օգտագործվող պատկերներն ընտրվում են տվյալ արմատային գրացուցակում կանոնավոր արտահայտություն օգտագործելով որոնելով: Ավարտից հետո ֆայլերը կարող են տեղափոխվել, վերանվանվել և պատճենվել ըստ ցանկության՝ դրա սահմաններում, փոխել ֆայլերը և օպերացիոն համակարգերը և այլն: Այնուամենայնիվ, դուք պետք է չափազանց զգույշ լինեք և ոչ մի կերպ չփոխեք անմիջական բովանդակությունը: Անգամ մեկ բիտի արժեքը կորցնելը կարող է անհնարին դարձնել տեղեկատվության վերականգնումը:

Ավարտից հետո կոմունալը թողնում է հատուկ արխիվային ֆայլ, որը պարունակում է փաթեթավորման համար անհրաժեշտ բոլոր տեղեկությունները, ներառյալ օգտագործված պատկերների մասին տվյալները: Ինքնին, այն կշռում է մոտ մի քանի կիլոբայթ և որևէ էական ազդեցություն չի ունենում զբաղեցրած սկավառակի տարածության վրա:

Դուք կարող եք վերլուծել հնարավոր հզորությունը՝ օգտագործելով «-a» դրոշը. «./f5ar -a [որոնման թղթապանակ] [Perl-համատեղելի կանոնավոր արտահայտություն]»: Փաթեթավորումը կատարվում է «./f5ar -p [որոնման թղթապանակ] [Perl-համատեղելի կանոնավոր արտահայտություն] [փաթեթավորված ֆայլ] [արխիվի անուն]» հրամանով և ապափաթեթավորումը «./f5ar -u [արխիվային ֆայլ] [վերականգնված ֆայլի անունը» ]'.

Աշխատանքի ցուցադրում

Մեթոդի արդյունավետությունը ցույց տալու համար ես վերբեռնեցի ծառայությունից շների 225 բացարձակապես անվճար լուսանկարների հավաքածու։ Unsplash և փաստաթղթերում գտել է երկրորդ հատորի 45 մետրանոց մեծ pdf Ծրագրավորման արվեստ Կնուտա.

Հերթականությունը բավականին պարզ է.

$ 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-ը չի կարող կառավարել մեծ ֆայլեր), ընթերցողը կարող է գնահատել տարբերությունը ինչպես աչքի, այնպես էլ դրանց ինտենսիվությամբ, որը ստացվում է փոփոխված բաղադրիչի արժեքները բնօրինակից հանելով. բնօրինակը, ներսում տեղեկություններով, տարբերությունը (որքան ավելի ձանձրալի է գույնը, այնքան փոքր է բլոկի տարբերությունը):

Փոխարենը մի եզրակացության

Հաշվի առնելով այս բոլոր դժվարությունները՝ կոշտ սկավառակ գնելը կամ ամեն ինչ ամպի մեջ վերբեռնելը կարող է թվալ խնդրի շատ ավելի պարզ լուծում: Բայց չնայած մենք հիմա ապրում ենք այսպիսի հիանալի ժամանակներում, երաշխիք չկա, որ վաղը դեռ հնարավոր կլինի մտնել առցանց և ինչ-որ տեղ վերբեռնել ձեր բոլոր լրացուցիչ տվյալները: Կամ գնացեք խանութ և ինքներդ գնեք ևս հազար տերաբայթանոց կոշտ սկավառակ: Բայց դուք միշտ կարող եք օգտագործել գոյություն ունեցող տները:

-> GitHub

Source: www.habr.com