درباره روشی عجیب برای صرفه جویی در فضای هارد

کاربر دیگری می خواهد یک داده جدید روی هارد دیسک بنویسد، اما فضای خالی کافی برای انجام این کار ندارد. من همچنین نمی خواهم چیزی را حذف کنم، زیرا "همه چیز بسیار مهم و ضروری است." و با آن چه کنیم؟

هیچکس این مشکل رو نداره ترابایت اطلاعات روی هارد دیسک های ما وجود دارد و این مقدار تمایلی به کاهش ندارد. اما چقدر منحصر به فرد است؟ در پایان، همه فایل‌ها فقط مجموعه‌ای از بیت‌ها با طول معین هستند و به احتمال زیاد، فایل جدید تفاوت چندانی با موردی که قبلاً ذخیره شده است ندارد.

واضح است که جستجوی اطلاعاتی که قبلاً روی یک هارد دیسک ذخیره شده اند، اگر ناموفق نباشد، حداقل کار مؤثری نیست. از طرفی اگر تفاوت کم است، می توانید کمی آن را تنظیم کنید...

TL;DR - دومین تلاش برای صحبت در مورد روشی عجیب برای بهینه سازی داده ها با استفاده از فایل های JPEG، اکنون به شکل قابل درک تر.

در مورد بیت و تفاوت

اگر دو قطعه کاملا تصادفی از داده ها را انتخاب کنید، به طور متوسط ​​نیمی از بیت های موجود در آنها منطبق هستند. در واقع، در میان طرح‌بندی‌های ممکن برای هر جفت ('00، 01، 10، 11')، دقیقاً نیمی از آنها مقادیر یکسانی دارند، همه چیز در اینجا ساده است.

اما مسلماً اگر فقط دو فایل برداریم و یکی را به دومی جا دهیم، یکی از آنها را از دست خواهیم داد. اگر تغییرات را ذخیره کنیم، به سادگی دوباره اختراع می کنیم رمزگذاری دلتا، که بدون ما به خوبی وجود دارد، اگرچه معمولاً برای اهداف مشابه استفاده نمی شود. می‌توانیم سعی کنیم دنباله‌ای کوچک‌تر را در یک دنباله بزرگ‌تر جاسازی کنیم، اما با این وجود، اگر بی‌دیده از آن در همه چیز استفاده کنیم، خطر از دست دادن بخش‌های حیاتی داده‌ها را داریم.

بین چه چیزی و چه چیزی می توان تفاوت را از بین برد؟ خوب، یعنی یک فایل جدید نوشته شده توسط کاربر فقط یک دنباله از بیت ها است که با آن ما به تنهایی نمی توانیم کاری انجام دهیم. سپس شما فقط باید چنین بیت هایی را در هارد دیسک پیدا کنید که بدون نیاز به ذخیره تفاوت آنها را تغییر دهید تا بتوانید از دست دادن آنها بدون عواقب جدی جان سالم به در ببرید. و منطقی است که نه تنها فایل روی خود FS، بلکه برخی اطلاعات کمتر حساس داخل آن را تغییر دهید. اما کدام یک و چگونه؟

روش های مناسب سازی

فایل های فشرده از دست رفته به کمک می آیند. همه این jpeg ها، mp3 ها و موارد دیگر، اگرچه فشرده سازی ضعیفی دارند، حاوی یک سری بیت هستند که می توان با خیال راحت آنها را تغییر داد. می توان از تکنیک های پیشرفته ای استفاده کرد که به طور نامحسوس اجزای خود را در مراحل مختلف رمزگذاری تغییر می دهند. صبر کن. تکنیک های پیشرفته ... تغییر نامحسوس ... یک بیت به دیگری ... تقریبا شبیه است استگانوگرافی!

در واقع، جاسازی یک اطلاعات در اطلاعات دیگر مانند هیچ چیز دیگری یادآور روش های او است. من همچنین تحت تاثیر نامحسوس بودن تغییرات ایجاد شده در حواس انسان هستم. جایی که مسیرها از هم جدا می‌شوند محرمانه است: وظیفه ما این است که کاربر اطلاعات اضافی را روی هارد دیسک خود وارد کند؛ این فقط به او آسیب می‌زند. او دوباره فراموش خواهد کرد.

بنابراین، اگرچه می‌توانیم از آن‌ها استفاده کنیم، باید تغییراتی را انجام دهیم. و سپس با استفاده از مثال یکی از روش های موجود و فرمت فایل رایج، آنها را می گویم و نشان می دهم.

درباره شغال ها

اگر واقعاً آن را فشار دهید، تراکم پذیرترین چیز در جهان است. البته ما در مورد فایل های JPEG صحبت می کنیم. نه تنها هزاران ابزار و روش های موجود برای جاسازی داده ها در آن وجود دارد، بلکه محبوب ترین فرمت گرافیکی در این سیاره است.

با این حال، برای اینکه درگیر پرورش سگ نباشید، باید زمینه فعالیت خود را در فایل‌هایی با این فرمت محدود کنید. هیچ کس مربع های تک رنگ را که به دلیل فشرده سازی بیش از حد ظاهر می شوند دوست ندارد، بنابراین باید خود را به کار با یک فایل از قبل فشرده محدود کنید. اجتناب از رمزگذاری مجدد. به طور خاص، با ضرایب صحیح، که پس از عملیات مسئول از دست دادن داده ها باقی می مانند - DCT و کوانتیزاسیون، که کاملاً در طرح رمزگذاری نمایش داده می شود (به لطف ویکی کتابخانه ملی باومن):

روش های زیادی برای بهینه سازی فایل های jpeg وجود دارد. بهینه سازی بدون ضرر (jpegtran) وجود دارد، بهینه سازی وجود دارد.بدون از دست دادن"، که در واقع به برخی چیزهای دیگر کمک می کند، اما ما به آنها اهمیت نمی دهیم. از این گذشته ، اگر کاربر برای افزایش فضای خالی دیسک آماده است یک اطلاعات را در اطلاعات دیگری جاسازی کند ، یا مدتها پیش تصاویر خود را بهینه کرده است یا از ترس از دست دادن کیفیت اصلاً نمی خواهد این کار را انجام دهد.

F5

یک خانواده کامل از الگوریتم ها با این شرایط مطابقت دارند که می توانید با آنها آشنا شوید در این ارائه خوب. پیشرفته ترین آنها الگوریتم است F5 توسط آندریاس وستفلد، کار با ضرایب جزء روشنایی، زیرا چشم انسان کمترین حساسیت را نسبت به تغییرات آن دارد. علاوه بر این، از یک تکنیک جاسازی مبتنی بر رمزگذاری ماتریسی استفاده می‌کند، که باعث می‌شود تغییرات کمتری هنگام جاسازی همان مقدار اطلاعات، هر چه اندازه ظرف مورد استفاده بزرگتر باشد، ایجاد کند.

تغییرات به خودی خود منجر به کاهش یک مقدار مطلق ضرایب تحت شرایط خاص (یعنی نه همیشه) می شود، که به شما امکان می دهد از F5 برای بهینه سازی ذخیره سازی داده ها در دیسک سخت خود استفاده کنید. نکته این است که ضریب پس از چنین تغییری به دلیل توزیع آماری مقادیر در JPEG، به احتمال زیاد بیت های کمتری را پس از رمزگذاری هافمن اشغال می کند و صفرهای جدید هنگام رمزگذاری آنها با استفاده از RLE، سود می دهند.

اصلاحات لازم به حذف بخشی که مسئول محرمانه بودن (بازآرایی رمز عبور) است خلاصه می شود که باعث صرفه جویی در منابع و زمان اجرا می شود و مکانیزمی برای کار با بسیاری از فایل ها به جای یکی در یک زمان اضافه می شود. بعید است که خواننده به جزئیات بیشتر به فرآیند تغییر علاقه مند باشد، بنابراین اجازه دهید به توضیح پیاده سازی برویم.

فناوری پیشرفته

برای نشان دادن نحوه عملکرد این روش، من این روش را در C خالص پیاده‌سازی کردم و تعدادی بهینه‌سازی را هم از نظر سرعت اجرا و هم از نظر حافظه انجام دادم (شما نمی‌توانید تصور کنید که وزن این تصاویر بدون فشرده‌سازی، حتی قبل از DCT چقدر است). کراس پلتفرم با استفاده از ترکیبی از کتابخانه ها به دست آمد libjpeg, pcr и tinydir، که از آنها تشکر می کنیم. همه این‌ها توسط «make» جمع‌آوری می‌شوند، بنابراین کاربران ویندوز می‌خواهند برای ارزیابی کمی Cygwin را برای خود نصب کنند یا به تنهایی با ویژوال استودیو و کتابخانه‌ها سروکار داشته باشند.

پیاده سازی در قالب یک ابزار کنسول و کتابخانه در دسترس است. علاقه‌مندان می‌توانند در مورد استفاده از دومی در readme در مخزن Github، پیوندی که در انتهای پست به آن پیوست خواهم کرد، اطلاعات بیشتری کسب کنند.

چگونه استفاده کنیم؟

با دقت. تصاویر مورد استفاده برای بسته بندی با جستجو با استفاده از یک عبارت منظم در دایرکتوری ریشه داده شده انتخاب می شوند. پس از تکمیل، فایل ها را می توان به دلخواه در محدوده آن جابه جا، تغییر نام و کپی کرد، فایل و سیستم عامل ها را تغییر داد و غیره. با این حال، باید نهایت دقت را داشته باشید و به هیچ وجه محتوای فوری را تغییر ندهید. از دست دادن ارزش حتی یک بیت می تواند بازیابی اطلاعات را غیرممکن کند.

پس از تکمیل، ابزار یک فایل بایگانی ویژه حاوی تمام اطلاعات لازم برای باز کردن بسته بندی، از جمله داده های مربوط به تصاویر استفاده شده، باقی می گذارد. وزن آن به خودی خود حدود چند کیلوبایت است و تأثیر قابل توجهی بر فضای اشغال شده دیسک ندارد.

می توانید ظرفیت ممکن را با استفاده از پرچم '-a' تجزیه و تحلیل کنید: './f5ar -a [پوشه جستجو] [عبارت منظم سازگار با Perl]'. بسته بندی با دستور './f5ar -p [پوشه جستجو] [عبارت منظم سازگار با Perl] [فایل بسته] [نام بایگانی]' و باز کردن با './f5ar -u [پرونده بایگانی] [نام فایل بازیابی شده انجام می شود. ]'.

نمایش کار

برای نشان دادن اثربخشی روش، من مجموعه ای از 225 عکس کاملا رایگان از سگ ها را از سرویس آپلود کردم. می Unsplash و در اسناد یک پی دی اف بزرگ 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 نمی تواند فایل های بزرگ را مدیریت کند)، خواننده می تواند تفاوت را هم با چشم و هم شدت آنها را که با کم کردن مقادیر مولفه تغییر یافته از اصلی به دست می آید ارزیابی کند: اصل, با اطلاعات داخل, تفاوت (هرچه رنگ تیره تر باشد، تفاوت بلوک کمتر است).

به جای یک نتیجه گیری

با در نظر گرفتن همه این مشکلات، خرید یک هارد دیسک یا آپلود همه چیز در فضای ابری ممکن است راه حل بسیار ساده تری برای مشکل به نظر برسد. اما با وجود اینکه اکنون در چنین زمان فوق‌العاده‌ای زندگی می‌کنیم، هیچ تضمینی وجود ندارد که فردا همچنان می‌توانید آنلاین شوید و همه داده‌های اضافی خود را در جایی آپلود کنید. یا به فروشگاه بروید و برای خودتان یک هارد هزار ترابایتی دیگر بخرید. اما همیشه می توانید از خانه های موجود استفاده کنید.

-> GitHub

منبع: www.habr.com