פורום השדים האדומים

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

אם למישהו יש פה הסבר הגיוני לזה, אני אשמח לשמוע.

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

את הנוסחא אני מכיר-
סכום אינסופי של מספרים מהצורה

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

מה שאמרת, בדיוק מתאר אקראיות. בנוסף, אם ההתפלגות של הספרות היא אחידה, אתה לא אמור להיות מסוגל לדחוס את המקור.

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

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

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

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

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

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

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

מצטער להקפיץ אשכול ישן, אבל היתה לי הארה ואני מרגיש צורך לשתף, איציק.

כמו שאמרתי, דחסתי לבערך 40 אחוז את המספר פאי.
אממה, הקובץ אותו דחסתי מורכב מאלפבית בגודל 10, כלומר דרושים 3.32 ביטים לתאר כל סימבול בו, כלומר דחיסה של 3.32/8=41.5%. מצד שני, הקובץ במחשב מיוצג בASCII, כלומר 8 ביטים למספר. לכן הגיוני שהדחיסה היא לאזור ה40 אחוז, והמספר פאי לא דחיס.

אז, איציק. תגובתך?

42.

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

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

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

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

ממה שזכור לי דחיסה בהכללה גסה מאד עובדת ע"י שמירת "מילון", כאשר הקידוד שלו עובד תחת ההנחה שאין באמת חלוקה יוניפורמית מושלמת.
כלומר יש "אותיות"/"מילים" במילון שיחזרו לעיתים קרובות, ואפשר לקודד אותן בקידוד קצר יותר. נניח למשל שכל הקובץ שלך מורכב משלוש מילים AAA BBB CCC
תוכל לדחוס את הקובץ שלך עם המילון A B C, ולשמור את המילון עצמו בצד
A => AAA
B=> BBB
וכו

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

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

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

אלו היו 60 שניות של מה שנדמה לי שאני יודע על דחיסה

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

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


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

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

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

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

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

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

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

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

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

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

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

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

השיטה שאתה מציע, קוד שיודע לומר לי במאה אחוז מה הספרה הבאה, היא לא שיטת דחיסה.
למשל, הפונקציה y=x^2 היא אוסף של זוגות סדורים (אוסף שהוא לא בן מניה). אתה יכול לייצג את האוסף הזה באמצעות 4 סימבולים בלבד. אבל זה לא אומרת שדחסת אותו. מבין?

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

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

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

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

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