שיטות כיווץ - דיון

[Bh]

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

[zurkin1232]

לדעתי רק עד כדי קבוע קטן.

קח למשל את המחרוזת הבינארית הפשוטה 111111... (או לחלופין 00000...)

הכיווץ הכי טוב שלה לא יכול להיות קטן יותר ממס' הביטים. כלומר כיווץ יהיה פשוט לרשום את מספר ה-1ים במחרוזת.

הכיווץ הזה הוא בסדר גודל לוגריתמי, כי לוקח log (בבסיס 2) ביטים לשמור את מס' הביטים של המחרוזת.

מכאן אני חושב שאפשר להניח שכל כיווץ של כל מחרוזת שהיא ייקח לפחות לוג-ביטים.

אגב יש איזה משפט במדעי המחשב שמתקשר לזה.

אה, עוד משהו.

תחשוב על העובדה שעם n ביטים אתה יכול לייצר לכל היותר 2 בחזקת n מחרוזות שונות.

אז לדוגמא... לא ייתכן אלג' שמכווץ כל מחרוזת באורך 100 למחרוזת באורך 2 למשל. כי 2 ביטים יכולים לייצג רק 4 מחרוזות שונות.

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

[kikkler]

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

[Bh]

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

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

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

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

011000111001 יהפוך ל:

01001110 מפה אפשר לצמצם עוד:

000111 מפה כפי שאמרת:

1303

כמובן שלמספרים ארוכים זה יותר אפקטיבי.

אך כאשר הולכים הפוך יש בעיה לזהות האם המספר 00 למשל הוא "00" או מייצג 2 אפסים כאשר כל 0 שווה ל-01. אני מקווה שהבנתם את הרעיון, יש פה מן תבנית קבועה שחוזרת על עצמה(00=00, 11=11, 01=0, 10=1).

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

abcdef

a=ab

c=cd

e=ef

וכך הלאה.. מה שיוצא:

ace

ac=d למשל לכן:

de

DE שווה ל-F למשל:

F

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

מקווה שהבנתם את הרעיונות. האם דבר כזה בר ביצוע לדעתכם?

[iceman90]

לדעתי רק עד כדי קבוע קטן.

קח למשל את המחרוזת הבינארית הפשוטה 111111... (או לחלופין 00000...)

הכיווץ הכי טוב שלה לא יכול להיות קטן יותר ממס' הביטים. כלומר כיווץ יהיה פשוט לרשום את מספר ה-1ים במחרוזת.

הכיווץ הזה הוא בסדר גודל לוגריתמי, כי לוקח log (בבסיס 2) ביטים לשמור את מס' הביטים של המחרוזת.

מכאן אני חושב שאפשר להניח שכל כיווץ של כל מחרוזת שהיא ייקח לפחות לוג-ביטים.

אגב יש איזה משפט במדעי המחשב שמתקשר לזה.

אה, עוד משהו.

תחשוב על העובדה שעם n ביטים אתה יכול לייצר לכל היותר 2 בחזקת n מחרוזות שונות.

אז לדוגמא... לא ייתכן אלג' שמכווץ כל מחרוזת באורך 100 למחרוזת באורך 2 למשל. כי 2 ביטים יכולים לייצג רק 4 מחרוזות שונות.

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

לא מדוייק. קח למשל את הסדרה - 1,2,3,,,,,1000000000000. לו הייתי רושם סדרה כזו על קובץ, גודלה היה גדול מאד, לו הייתי משתמש באחת מהשיטות המקובלות כיום לכיווץ, עדיין לא הייתי מצליח לכווץ את זה למקסימום... ישנם כמה דרכים מתמטיות לרשום סדרה זו בפחות מ30 בתים... פחות מ log של גודל הסדרה. אני מאמין שהשלב הבא בכיווץ (ובמחשבים בכלל) הוא בינה מלאכותית, כזו שתחילה תוכל לזהות חוקיות כזו וגם בסדרות קצת יותר מורכבות...

מטי.

[ktbnus]

וונזיפ פועל על עיקרון של תווים(במיקרה הנתון 0 ו- 1). מוציא את הכפילויות ובונה קובץ אינדקס.

לדחגמה: קובל(לא משנה איזה...הוא מפר אותו בצורה בינארית) 101101011 ווינזים יתור משהו כמו

1011* 2 0*1 פלוס מיקומים, winrar תיצג אותו קובץ בצורה דומה אבל שונה כגון 101*2 פלוס 011*1

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

[Boomerang]

winzip זאת לא שיטת דחיסה. עד כמה שאני זוכר, אחת מהשיטות שהיא משתמשת בהן היא Lempel-Ziv (שנעשה בה שימוש גם בפורמט gif)

לפי משפט הדחיסה (של שנון) אי אפשר לדחוס מידע יותר מהאנטרופיה שלו (שזה מדד לאי הסדר של המידע, שכחתי את הנוסחא המדויקת)

יש גם הרבה אלגוריתמים לדחיסת מידע מסוג ספציפי שמשיגים תוצאות יותר טובות מאלגוריתמים כלליים (למשל BZip לטקסט)

חלק גדול מהאלגוריתמים האלה משיגים תוצאות טובות ע"י איבוד חלק מהמידע ע"י מציאת קירוב (לתמונה/קול/וידאו...) שאפשר לשמור בצורה יותר יעילה.

למשל - jpeg מקרב את התמונה ע"י צירוף של פולינוומים.

[Ghosthunter]

בקובץ טקסט אתה יודע את התחום שלך(אותיות בלבד), ולכן, לכל אות אתר שומה את המספר שלה בABC(למשל A-0, B-1,...., Z-24).ומאחר שיש 24 אותיות, אז אתה צריך לשמור בין הערכים 0 ל- 24. זה הרבה יותר יעיל מלשמור את תחום הערכים 0-255(בית).

עריכה:

למשל - jpeg מקרב את התמונה ע"י צירוף של פולינוומים.

יש תוכנה שמראה את הגרפים שלהם? כאילו במקום להראות את הצבעים היא מראה גבהים, והכל בתלת מימד?

עריכה 2: כמו באטלס?

[montigo]

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

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

לא זוכר אפילו איך קוראים להוכחה הזו, אבל זה בדוק.

כמובן שאני מדבר רק על כיווץ ללא איבוד מידע (Loseless).

[Boomerang]

...ומאחר שיש 24 אותיות, אז אתה צריך לשמור בין הערכים 0 ל- 24.

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

יש תוכנה שמראה את הגרפים שלהם?

כן, explorer למשל. (הצירוף שלהם זו התמונה)

או שמעניין אותך להפריד בין הפולינומים? - ראיתי פעם הדגמה של זה ב- MATLAB, אני לא מכיר תוכנה שמראה את זה.

בכל אופן, אני לא מבין מה הקשר לתלת מימד.

אתה לא יכול להביע צבע בעזרת גובה (אתה מייצג צבע לפחות עם 3 ערכים - RGB/lab/CMYK...) אבל בכל תוכנת תלת מימד נורמלית (אפילו POVRay החינמית) אתה יכול לייצר height-map מערוץ בתמונה.

...לפיה כל עבור כל אלגוריתם לכיווץ יהיה קיים קלט מסויים שיגרום לפלט שאיננו מכווץ

...אבל גם לא תהיה לקלט הזה משמעות.

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

[icebreak]

לגבי משפט אנטופיית המידע של שאנון, הנה:

http://en.wikipedia.org/wiki/Information_entropy

אתר כללי די טוב על כל נושאי הדחיסה:

http://www.data-compression.com/index.shtml

http://www.faqs.org/faqs/compression-faq/

http://en.wikipedia.org/wiki/Data_compression

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

בכל מקרה, ישנם הרבה סוגי דחיסה והשאלה למה אתה מתכוון... מבחינת שיטת הדחיסה הגנרית (LOSELESS, שלא מעבדת מידע), השיטה הטובה ביותר כיום היא ה 7ZIP - http://www.7-zip.org/ , למרות שנעשים מחקרים בכיוון (והצרות מגוכחות אחת לכמה שנים של שיטה חדשה ומעולה, שבסוף מתברר כשטויות, היתה כתבה על זה לא מזמן ב WIRED), לא נראה כי כרגע קיימת שיטה כללית מהפכנית שטובה יותר...

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

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

אם אתה רוצה, תקרא / תיישם שיטת ה HOFFMAN ENCODING

[Ghosthunter]

כן, explorer למשל. (הצירוף שלהם זו התמונה)

או שמעניין אותך להפריד בין הפולינומים? - ראיתי פעם הדגמה של זה ב- MATLAB, אני לא מכיר תוכנה שמראה את זה.

בכל אופן, אני לא מבין מה הקשר לתלת מימד.

אתה לא יכול להביע צבע בעזרת גובה (אתה מייצג צבע לפחות עם 3 ערכים - RGB/lab/CMYK...) אבל בכל תוכנת תלת מימד נורמלית (אפילו POVRay החינמית) אתה יכול לייצר height-map מערוץ בתמונה..

התכוונתי שתהייה תמונה תלת מימדית שהרוחב שלה זה רוחב התמונה, הגובה שלה זה גובה התמונה והעומק שלה בין 0 ל255 והוא מייצג את ערך הערוץ באותו מקום XY. אני אבדוק את התוכנה ששלחת.

ד.א. אילו פולינומים אלה?

[icebreak]

התכוונתי שתהייה תמונה תלת מימדית שהרוחב שלה זה רוחב התמונה, הגובה שלה זה גובה התמונה והעומק שלה בין 0 ל255 והוא מייצג את ערך הערוץ באותו מקום XY. אני אבדוק את התוכנה ששלחת.

ד.א. אילו פולינומים אלה?

http://en.wikipedia.org/wiki/Jpeg

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

וגם

http://en.wikipedia.org/wiki/Discrete_cosine_transform

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

[Ghosthunter]

טוב, בדקתי את התוכנה POVRay והיא לא מה שחיפשתי. חיפשתי תוכנה שתציג תמונה (שהיא ב-2D), ותפריד את הערוצים שלה. איפה שהיא רואה שיש הרבה צבע, היא שמה את הנק במקום גבוה, ואיפה שאין הרבה מאותו צבע, היא שמה את הנק במקום נמוך. התוכנה שהבאת היא מציירת תמונות תלת מימדיות(ובצורה דיי מגניבה אני חייב לציין). את MATHLAB אני אפגוש בעתיד. האם היא תתן לי תשובה?

[icebreak]

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