בתשובה לeasy, 26/11/02 10:04
 |
|
 |
||
|
||||
 |
הגדרה מענינת, לא מקובלת במיוחד, הלקוחה מתחום תורת האינפורמציה במקום תורת ההסתברות. לרוע מזלך, אני משוכנע שסידרה כמו שהגדרת חייבת להכיל כל תת סדרה סופית ולמעשה חייבת להיות נורמלית. אם לא, יהיה אלגוריתם דחיסה שיתאר רישא בפחות מאורכה. אין לי זמן כרגע לחשוב על כך, אבל אופתע מאוד אם לא כך הוא המצב. בהבטחת תשובה מדויקת יותר מחר.. |
 |
 |
 |
|
|
|
||
|
||||
|
נכון, זו לא הגדרה מקובלת, אבל כאמור, היא שימושית. (ולא סתם היא מגיעה מהתחום בו יש שימוש לסדרות אקראיות - תורת האינפורמציה) אני לא מצליח לחשוב על נימוק טוב למה לסידרה לא נורמלית חייב להיות אלגוריתם דחיסה כפי שתארת. אשמח אם תביא כזה. |
|
|
|
|
|
|
||
|
||||
|
יחס הדחיסה של אלגוריתם למפל-זיו שואף לאינפורמציה הממוצעת לספרה, ולכן סדרה שאינה נורמלית אפשר לדחוס באופן אפקטיבי. | |
|
|
|
|
|
||
|
||||
|
יחס הדחיסה ידוע, אבל אני לא רואה איך כמות האינפורמציה הממוצעת לספרה משתנה באופן משמעותי בסדרה שהיא ''כמעט'' נורמלית. (דהיינו מכילה כמעט כל תת-סדרה סופית) השינוי במקרה של סדרה כזו לעומת סדרה נורמלית ''ממש'' צריך להיות די זניח. אתה מוזמן להסביר לי למה אני טועה. |
|
|
|
|
|
|
||
|
||||
|
1. התייחסתי להגדרה של סדרה נורמלית שכתבתי למעלה, כלומר סדרה שבה השכיחות של כל רצף סופי שווה למה שהיינו מצפים מסדרה אקראית. כמובן שסדרה שבה רצף סופי מסויים הוא "אסור" אינה נורמלית, כך שהטענה שלי (שסדרות נורמליות אפשר לדחוס אפקטיבית) היא חזקה יותר (מהטענה שסדרה בלי רצף מסויים אפשר לדחוס אפקטיבית). 2. נניח שהאלפא-בית הוא בן K אותיות (למשל 2 או 10), ונניח שיש מלה מסויימת, באורך N, שאינה מופיעה כלל. אז אפשר לחשוב על הסדרה כאילו היא כתובה ב- N^K-1 ה"אותיות" שהן מלים מותרות באורך K; בפרט, האינפורמציה הממוצעת לאותיות החדשות חסומה על-ידי (log(N^K-1, וקטנה ממש מ- (K*log(N. 3. המלה "זניח" עשויה להטעות. אני לא טוען שהאנטרופיה יורדת באופן משמעותי; למשל, אם מספר תעודת הזהות שלי (9 ספרות) אינו מופיע, האינפורמציה הממוצעת לספרה היא לכל היותר (log(10)*(1-1e-10.31; פחות מ-(log(10 במידה זניחה, אבל עדיין פחות. |
|
|
|
| חזרה לעמוד הראשי | המאמר המלא |
| מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים | |
 RSS מאמרים |
כתבו למערכת |
אודות האתר |
טרם התעדכנת |
ארכיון |
חיפוש |
עזרה |
תנאי שימוש
|
© כל הזכויות שמורות |