המכפלה הישרה של שתי חבורות ציקליות formula_41 היא חבורה ציקלית, אם ורק אם formula_6 ו-formula_43 זרים. במקרה זה, כמובן, היא איזומורפית ל-formula_44. מן המשפט היסודי של האריתמטיקה נובע שאפשר לפרק כל חבורה ציקלית למכפלה ישרה של חבורות ציקליות שכל אחת מהן מסדר חזקה של ראשוני. לדוגמה, formula_45.
גלגל שבירה
גלגל שבירה היה מתקן הוצאה להורג תוך כדי עינויים מתקופת ימי הביניים. הגלגל עצמו היה דומה לגלגל עץ גדול של קרון, עם חישורים רבים. ידיו ורגליו של הקורבן היו נקשרות זו אחר זו על שתי קורות עץ חזקות. לאחר מכן היו מכים בעוצמה בפטיש גדול על אחת הגפיים באזור שבין הקורות, ושוברים בכך את העצם. פעולה זו חזרה על עצמה מספר פעמים לכל אחת מהגפיים.
לאחר מכן, הגפיים המנופצות של הקורבן היו נארגות דרך החישורים של הגלגל, והגלגל הורם על מוט גבוה כך שציפורים יוכלו לאכול את הקורבן בעודו חי.
חוקרים טוענים שהגלגל שימש במקורו לייבוש בשר בשמש. את הבשר היו מצמידים לגלגל ומסובבים אותו. השמש והרוח גרמו לייבוש הבשר. באזור טורקיה מוכר הגלגל עד היום בשם שורבודיל.
האגדה מספרת שאת הקדושה קתרינה מאלכסנדריה ניסו להוציא להורג באחד מהמתקנים הללו, ועל שמה מכונה גלגל השבירה "גלגל קתרין".
כללי.
גלגל השבירה נמצא בתיאורי עינויים רבים והוצאות להורג לאורך ההיסטוריה מלפנה"ס, החל מתיאורי עינויים של החשמונאים על ידי השליט בסוריה, עד לכיבוש אדמות אמריקה הצפונית וריסון העבדים בהאיטי בסוף המאה ה-18. גלגל השבירה מראשית דרכו סימל את שבירת המעונה, בניגוד למכשירי עינויים רבים אשר היו משאירים צלקות ושברים, גלגל השבירה סימל גזר דין מוות, כאשר מעונה היה שורד עינויים רבים, השלב הסופי היה להביאו אל גלגל השבירה. בימי הביניים שימש גלגל השבירה כאחת הדרכים הפופולריות ביותר להוצאה להורג. מלכים ועריצים רבים השתמשו בסמלו של גלגל השבירה כדי לעורר פחד בקרב אויביהם ולהדגיש עוצמה בקרב, בממלכות בקולוניות.
דחיסת נתונים
במדעי המחשב, דחיסת נתונים היא התחום העוסק בהקטנת נפחם של נתונים, כך שיתפסו פחות מקום מאשר בצורתם המקורית.
עקרונות דחיסת הנתונים.
דחיסת נתונים אפשרית משום שבצורתם הגולמית של הנתונים קיימת פעמים רבות יתירות גבוהה, כלומר מידע החוזר על עצמו או מידע שניתן לייצג בצורה חסכונית יותר. העיקרון הבסיסי בדחיסה הוא כי במידע שאנו עושים בו שימוש יש "סדר" מסוים. מציאת הסדר הזה מאפשרת לייצג את המידע בדרך יעילה יותר. מידע שהוא מקרי (רעש) לא יכול להידחס. מידת אי-הסדר מכונה "אנטרופיה".
דחיסת הנתונים מאפשרת לנו לעשות שימוש יעיל במדיה (תמונות, קול, וידאו). הדחיסה מאפשרת יעילות גבוהה בפעולות כגון העברת תמונות על גבי האינטרנט, שמירת סרט על תקליטור DVD ודיבור בטלפון סלולרי.
כמו כן, דחיסת הנתונים מאפשרת אחסון קבצים על אמצעי לאחסון נתונים בנפח הקטן מנפחם המקורי, וכך ניתן לאחסן מידע רב יותר בשטח זיכרון פיזי נתון. דחיסת קבצים לשם מטרה זו מתרחשת לרוב במחשבים ביתיים ומשרדיים, או בשרתים המאפשרים אחסון קבצים על-ידי שירותי ענן. דחיסת הקבצים יכולה להתרחש בין באופן יזום על-ידי המשתמש, ובין באופן אוטומטי; דחיסה אוטומטית יכולה להתבצע, למשל, כאשר נעשה שימוש, על-ידי המשתמש, בקובץ בפורמט מסוים הכולל דחיסת נתונים, או על ידי שרת המשמש לאחסון קבצים, ללא צורך בידיעת המשתמשים בשירות הענן.
בעולם המחשב קיימים פורמטים שונים לקבצים דחוסים, ובהם: ZIP, MP3, JPEG, DIVX, MPEG. לעומתם, קיימים סוגי קבצים של מידע לא דחוס כגון: BMP ו-WAV (קובץ WAV גם הוא דחוס לעיתים). מידע שמאוחסן בקבצים כאלו גדול משמעותית מהקבצים הדחוסים. כך תמונה לא דחוסה (בקובץ BMP) יכולה להגיע לגודל של כ-1,000,000 בתים (1MB) ואילו אותה תמונה דחוסה (בקובץ JPEG) בדחיסה מאבדת יכולה להיות בגודל של כ-50,000 בתים (50KB) - יחס של 1:20.
חסרונה העיקרי של הדחיסה הוא שהיא מגדילה את הסיבוכיות של השימוש במדיה, ולכן במערכות רבות עושים שימוש במדיה לא דחוסה למען הפשטות. תקליטור מוזיקה רגיל (CD) לדוגמה מכיל מוזיקה לא דחוסה, ולכן הנגנים שלו פשוטים מנגנים שקוראים פורמטים כגון MP3.
בדחיסה ניתן להבחין בין שני סוגים עיקריים: דחיסה משמרת (Lossless) ודחיסה מאבדת (Lossy). בדחיסה משמרת, המידע הדחוס משוחזר בדיוק מלא למידע המקורי. לעומת זאת בדחיסה מאבדת המידע המשוחזר קרוב מאוד אך לא זהה למידע המקורי. פורמט PNG הוא דוגמה לדחיסה משמרת של תמונה, ולכן מתאים לשמירת תמונות כלליות. JPEG הוא פורמט של דחיסה מאבדת של תמונה, ולכן תמונת JPEG לעולם לא תהיה זהה לתמונה המקורית. ה-JPEG מתוכנן בצורה כזו שעין אנוש לא תבחין בהבדל.
טכניקות דחיסה.
דחיסה משמרת מידע.
דחיסה משמרת היא דחיסה המאפשרת לנו להפעיל פונקציה הפוכה לפונקציית הדחיסה, כך שהתוצאה שתתקבל תהיה זהה למקור. טכניקות דחיסה אלו מנצלות את העובדה שבמידע הנבדק יש חוקיות מתמטית.
קידוד אורך חזרה RLE.
טכניקת דחיסה פשוטה שאינה מאבדת מידע היא הטכניקה המכונה "קידוד אורך חזרה" או RLE (ראשי תיבות של Run Length Encoding) כאשר יחידת מידע החוזרת על עצמה מספר פעמים תקודד על ידי ציון יחידת המידע ומספר הפעמים בו יחידת המידע חוזרת על עצמה.
לדוגמה: נניח שאנחנו מבקשים לאחסן תמונה בשחור-לבן, כאשר האות ל תציין לבן ו-ש תציין שחור. המידע הלא דחוס עשוי להיות:
ואילו המידע הדחוס יהיה (הפסיקים והרווחים הוספו להבהרת הדוגמה):
כפי שניתן לראות בדוגמה זו, המידע הדחוס מיוצג באמצעות 15 תווים במקום 65 תווים, שזה חיסכון של 77 אחוז.
קידוד גודל משתנה וקוד האפמן.
אותיות מסוימות באלפבית שכיחות יותר מאותיות אחרות. כך האותיות יוּד ו-וו נפוצות בעברית פי עשרה לערך מהאותיות צ ו-ז. אם נרצה לייצג טקסט נוכל להקטין את גודלו תוך שימוש בקוד קצר לאותיות נפוצות וקוד יותר ארוך לאותיות נדירות, כפי שהדבר נעשה בקוד מורס. השיטה הנפוצה ביותר לדחיסה כזו קרויה קוד האפמן. רוב פורמטי הדחיסה עושים שימוש באלגוריתם זה.
רוב קובצי הטקסט משתמשים בקידוד ASCII על מנת לייצג את התווים שבהם. לפי קידוד זה לכל תו יש ערך בעל 7 ביטים (כלומר סה"כ 2 בחזקת 7 - 128 תווים שונים), או בעל ערך של שמונה ביטים כאשר הביט השמיני הוא ביט זוגיות. בקבצים כאלה כדי לשמור n תווים בעצם כותבים 8*n ביטים. בהרבה מקובצי הטקסט לא משתמשים בכל התווים ובנוסף לתווים מסוימים יש סיכוי יותר גדול להופיע מאשר לתווים אחרים (למשל האותיות י' או ו' מופיעות הרבה יותר מאשר צ' או ט'). כלומר, קודם כל ניתן לייצג את כל התווים בקובץ מסוים בפחות ביטים - למשל כדי לייצג שמונה תווים צריך סה"כ 3 ביטים לכל תו. חוץ מכך, ניתן לתת לתווים מסוימים, שמופיעים יותר פעמים, קוד קצר יותר ולעומת זאת תווים שמופיעים לעיתים רחוקות ניתן קודים ארוכים יותר (על מנת לשמור על הקוד ניתן לפענוח).
קידוד כזה נקרא "קידוד גודל משתנה", מאחר שלכל תו יכול להיות גודל שונה. הבעיה בגודל משתנה היא שהמפענח של הקוד לא יכול לדעת מה מספר הביטים שהוא צריך לקרוא לכל תו, ואיך להפוך את אותו קוד חזרה לתו. עבור קבצים רגילים כל מה שהמפענח צריך לעשות זה לקרוא 7 או שמונה ביטים ולהמיר אותם לפי טבלת ה-ASCII. כדי להתגבר על הבעיה הזאת נותנים לכל תו קוד משלו שתלוי במספר הפעמים בו הוא מופיע בטקסט וכדי להבדיל בין הקודים השונים לכל קוד יש תחילית שונה.
לדוגמה ניקח את הטקסט "אאבגאדאב". כאשר מספר הפעמים שהאותיות מופיעות הם: א-4, ב-2, ג-1, ד-1.
אם היינו מייצגים כל אות על ידי שני ביטים, היינו מקבלים מחרוזת בגודל של 4*2+2*2+1*2+1*2=16.
לעומת זאת ניתן לתווים את התחיליות הבאות:
א - 1
ב - 01
ג - 001
ד - 000
כעת נחשב כמה ביטים צריך על מנת לקודד את ההודעה. מאחר שא' מופיעה 4 פעמים על מנת לקודד אותה אנחנו צריכים 4 ביטים. ב' מופיעה פעמיים ומאחר שכל קידוד שלה הוא שני ביטים אז הסך הכול שווה ל-4. ג' וד' מופיעות פעם אחת כל אחת ותורמות שלושה ביטים כל אחת. לכן הגענו סך הכול ל-4+4+3+3=14.
מאחר שהתחיליות שונות נדע תמיד איפה מסתיים הקוד. למשל אם המפענח קורא 0 הוא יודע שחייבים להגיע עוד ביטים לאותו תו. אם לאחר מכן הוא קורא 1 אז הוא יודע שהתו הוא ב', אם לעומת זאת הוא קורא עוד 0 אז הוא שוב מחכה לעוד ביטים וחוזר חלילה. קוד זה נקרא גם "קוד תחיליות".
קוד התחיליות הנפוץ ביותר כיום הוא קוד הופמן, שמקצה את התחיליות על ידי בניית עץ בינארי. קוד נוסף למציאת תחיליות הוא קוד שאנון פאנו.
אפשר להראות שכל קבוצת מילים (סופית או בת מנייה) בעלת תחיליות שונות, חייבת לקיים את אי-שוויון קראפט.
אלגוריתם למפל-זיו.
מלבד קוד הופמן ו-RLE, אחת מטכניקות הדחיסה ללא איבוד מידע המקובלת ביותר כיום מבוססת על אלגוריתם שפיתחו פרופ' אברהם למפל ופרופ' יעקב זיו מהטכניון בחיפה. וריאציות שונות של אלגוריתם למפל-זיו (LZ, LZW) מיושמות כיום בתוכנות דחיסה פופולריות כגון PkZip ו-gzip, ובפורמטים ליצוג תמונות כגון GIF ו-PNG.
האלגוריתמים והווריאציות של למפל זיו מבוססים על בניית מילון בו נשמרים צירופים של אותיות שהופיעו בקובץ וכאשר אותו צירוף מופיע שוב במקום לכתוב אותו לקובץ, פשוט כותבים מצביע לאותו ערך במילון. השיטה אפקטיבית כאשר יש קובץ ובו ישנם צירופים שחוזרים על עצמם לעיתים קרובות (כמו למשל הצירוף "צירו" שהופיע 4 פעמים בפסקה הנוכחית עד עתה).
טכניקות נוספות.
טכניקות דחיסה נוספות כגון PPM, CTW, ו-BWT משיגות ביצועים טובים יותר (חיסכון בתווים) בתמורה לאיטיות מסוימת יחסית ל-LZ.
דחיסה מאבדת מידע.