על שיטה מוזרה לחיסכון בשטח בדיסק הקשיח

משתמש אחר רוצה לכתוב פיסת נתונים חדשה לכונן הקשיח, אך אין לו מספיק מקום פנוי לעשות זאת. אני גם לא רוצה למחוק שום דבר, שכן "הכל מאוד חשוב והכרחי." ומה עלינו לעשות עם זה?

לאף אחד אין את הבעיה הזו. יש טרה-בייט של מידע על הכוננים הקשיחים שלנו, וכמות זו אינה נוטה לרדת. אבל עד כמה הוא ייחודי? בסופו של דבר, כל הקבצים הם רק סטים של ביטים באורך מסוים, וסביר להניח שהחדש לא שונה בהרבה מזה שכבר מאוחסן.

ברור שחיפוש אחר פיסות מידע שכבר מאוחסנות בכונן קשיח הוא, אם לא כשל, אז לפחות לא משימה יעילה. מצד שני, אם ההבדל קטן, אז אתה יכול להתאים אותו קצת...

TL;DR - הניסיון השני לדבר על שיטה מוזרה לאופטימיזציה של נתונים באמצעות קבצי JPEG, כעת בצורה מובנת יותר.

על קטעים והבדלים

אם אתה לוקח שני פיסות נתונים אקראיות לחלוטין, אז בממוצע מחצית מהסיביות שהם מכילים חופפים. ואכן, בין הפריסות האפשריות לכל זוג ('00, 01, 10, 11′), בדיוק למחצית יש את אותם ערכים, הכל פשוט כאן.

אבל כמובן, אם רק ניקח שני קבצים ונתאים אחד לשני, אז נאבד אחד מהם. אם נשמור את השינויים, פשוט נמציא מחדש קידוד דלתא, שמתקיים מצוין בלעדינו, למרות שבדרך כלל לא משתמשים בו לאותן מטרות. אנחנו יכולים לנסות להטמיע רצף קטן יותר לתוך רצף גדול יותר, אבל גם ככה אנחנו מסתכנים באובדן מקטעים קריטיים של נתונים אם נשתמש בו בפזיזות בכל דבר.

בין מה למה אם כן ניתן לבטל את ההבדל? ובכן, כלומר, קובץ חדש שנכתב על ידי המשתמש הוא רק רצף של ביטים, שאיתם איננו יכולים לעשות דבר בעצמו. אז אתה רק צריך למצוא סיביות כאלה בכונן הקשיח שניתן לשנות אותם מבלי לאחסן את ההפרש, כך שתוכל לשרוד את האובדן שלהם ללא השלכות חמורות. וזה הגיוני לשנות לא רק את הקובץ ב-FS עצמו, אלא קצת מידע פחות רגיש בתוכו. אבל איזה ואיך?

שיטות התאמה

קבצים דחוסים מאבדים באים להצלה. כל ה-JPEG, MP3s ואחרים האלה, למרות דחיסה אובדת, מכילים חבורה של ביטים שניתן לשנות בבטחה. אפשר להשתמש בטכניקות מתקדמות שמשנות באופן בלתי מורגש את מרכיביהן בשלבים שונים של הקידוד. לַחֲכוֹת. טכניקות מתקדמות... שינוי בלתי מורגש... אחד לתוך השני... זה כמעט כמו סטגנוגרפיה!

ואכן, הטמעת מידע אחד באחר מזכירה את השיטות שלה כמו שום דבר אחר. אני גם מתרשם מחוסר המורגש של השינויים שנעשו בחושים האנושיים. היכן שהדרכים מתפצלות הוא בסודיות: המשימה שלנו מסתכמת בכך שהמשתמש מזין מידע נוסף על הכונן הקשיח שלו; זה רק יזיק לו. הוא ישכח שוב.

לכן, למרות שאנחנו יכולים להשתמש בהם, אנחנו צריכים לעשות כמה שינויים. ואז אספר ואראה אותם באמצעות הדוגמה של אחת השיטות הקיימות ופורמט קובץ נפוץ.

על תנים

אם אתה באמת לוחץ את זה, אז זה הדבר הכי דחיסה בעולם. אנחנו, כמובן, מדברים על קבצי JPEG. לא רק שיש טונות של כלים ושיטות קיימות להטמעת נתונים לתוכו, אלא שזהו הפורמט הגרפי הפופולרי ביותר על הפלנטה הזו.

עם זאת, כדי לא לעסוק בגידול כלבים, עליך להגביל את תחום הפעילות שלך בקבצים בפורמט זה. אף אחד לא אוהב ריבועים מונוכרום המופיעים עקב דחיסה מוגזמת, אז אתה צריך להגביל את עצמך לעבודה עם קובץ שכבר דחוס, הימנעות מקידוד מחדש. ליתר דיוק, עם מקדמים שלמים, שנשארים לאחר פעולות האחראיות לאובדן נתונים - DCT ו-quantization, שמוצג בצורה מושלמת בסכימת הקידוד (הודות לוויקי של הספרייה הלאומית באומן):

ישנן שיטות רבות אפשריות לאופטימיזציה של קבצי jpeg. יש אופטימיזציה ללא הפסדים (jpegtran), יש אופטימיזציה "ללא הפסד", שלמעשה תורמים משהו אחר, אבל לא אכפת לנו מהם. אחרי הכל, אם המשתמש מוכן להטמיע מידע אחד באחר כדי להגדיל את שטח הדיסק הפנוי, אז הוא עשה אופטימיזציה לתמונות שלו מזמן, או לא רוצה לעשות זאת בכלל מחשש לאובדן איכות.

F5

משפחה שלמה של אלגוריתמים מתאימה לתנאים הללו, שתוכלו להכיר במצגת הטובה הזו. המתקדם שבהם הוא האלגוריתם F5 מאת אנדראס ווסטפלד, שעובד עם המקדמים של מרכיב הבהירות, שכן העין האנושית היא הכי פחות רגישה לשינויים שלה. יתרה מכך, הוא משתמש בטכניקת הטמעה המבוססת על קידוד מטריצה, המאפשרת לבצע פחות שינויים בעת הטמעת אותה כמות מידע, ככל שגודל המיכל בו נעשה שימוש גדול יותר.

השינויים עצמם מסתכמים בהפחתת הערך המוחלט של המקדמים באחד בתנאים מסוימים (כלומר, לא תמיד), מה שמאפשר לך להשתמש ב-F5 כדי לייעל את אחסון הנתונים בכונן הקשיח שלך. הנקודה היא שככל הנראה המקדם לאחר שינוי כזה יתפוס פחות ביטים לאחר קידוד האפמן בגלל ההתפלגות הסטטיסטית של הערכים ב-JPEG, והאפסים החדשים יתנו רווח בעת קידודם באמצעות RLE.

השינויים הנדרשים מסתכמים בביטול החלק האחראי על הסודיות (סידור מחדש של סיסמא), החוסך משאבים וזמן ביצוע, והוספת מנגנון לעבודה עם קבצים רבים במקום אחד בכל פעם. לא סביר שהקורא יתעניין בתהליך השינוי ביתר פירוט, אז בואו נעבור לתיאור היישום.

היי טק

כדי להדגים איך גישה זו עובדת, יישמתי את השיטה ב-C טהור וביצעתי מספר אופטימיזציות הן מבחינת מהירות הביצוע והן מבחינת הזיכרון (אתם לא יכולים לדמיין כמה שוקלות התמונות הללו ללא דחיסה, אפילו לפני DCT). חוצה פלטפורמות מושגת באמצעות שילוב של ספריות libjpeg, PCRE и tinydir, ועל כך אנו מודים להם. כל זה מורכב על ידי 'make', כך שמשתמשי Windows רוצים להתקין לעצמם קצת Cygwin לצורך הערכה, או להתמודד עם Visual Studio וספריות בעצמם.

ההטמעה זמינה בצורה של כלי עזר וספרייה למסוף. המעוניינים יכולים לברר עוד על השימוש באחרון ב-readme במאגר ב-Github, הקישור אליו אצרף בסוף הפוסט.

כיצד להשתמש?

בקפידה. התמונות המשמשות לאריזה נבחרות על ידי חיפוש באמצעות ביטוי רגולרי בספריית השורש הנתונה. בסיום, ניתן להעביר קבצים, לשנות את שמותיהם ולהעתיקם כרצונם בגבולותיו, לשנות קבצים ומערכות הפעלה וכו'. עם זאת, יש להיזהר ביותר ולא לשנות את התוכן המיידי בשום צורה. איבוד הערך של סיביות אחת יכול להפוך את זה לבלתי אפשרי לשחזר מידע.

בסיום, כלי השירות משאיר קובץ ארכיון מיוחד המכיל את כל המידע הדרוש לפריקה, כולל נתונים על התמונות בהן נעשה שימוש. כשלעצמו, הוא שוקל בערך כמה קילובייטים ואין לו השפעה משמעותית על שטח הדיסק התפוס.

אתה יכול לנתח את הקיבולת האפשרית באמצעות הדגל '-a': './f5ar -a [תיקיית חיפוש] [ביטוי רגולרי תואם Perl]'. האריזה מתבצעת עם הפקודה './f5ar -p [תיקיית חיפוש] [ביטוי רגולרי תואם Perl] [קובץ ארוז] [שם ארכיון]', ופריקה עם './f5ar -u [קובץ ארכיון] [שם קובץ משוחזר ]'.

הדגמת עבודה

כדי להראות את יעילות השיטה, העליתי אוסף של 225 תמונות בחינם לחלוטין של כלבים מהשירות Unsplash ומצא במסמכים 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 אינו יכול להתמודד עם קבצים גדולים), הקורא יכול להעריך את ההבדל הן לפי העין והן בעוצמתם, המתקבל על ידי הפחתת הערכים של הרכיב שהשתנה מהמקור: מקורי, עם מידע בפנים, הבדל (ככל שהצבע עמום יותר, ההבדל בבלוק קטן יותר).

במקום מסקנה

בהתחשב בכל הקשיים הללו, קניית כונן קשיח או העלאת הכל לענן עשוי להיראות כמו פתרון הרבה יותר פשוט לבעיה. אבל למרות שאנחנו חיים בתקופה כל כך נפלאה עכשיו, אין ערובה שמחר עדיין יהיה אפשר להיכנס לאינטרנט ולהעלות את כל הנתונים הנוספים שלך לאנשהו. או לך לחנות וקנה לעצמך עוד כונן קשיח של אלף טרה-בייט. אבל אתה תמיד יכול להשתמש בבתים קיימים.

-> GitHub

מקור: www.habr.com