דחיסת נתונים

מידע על דחיסה

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

הדחיסה מוגדרת באמצעות השדה supportedCompressions ו-CompressionType. לקוחות צריכים להשתמש בסוגי הדחיסה RICE ו-RAW. ב-Web Risk נעשה שימוש בסוג COMPRESSION_TYPE_UNSPECIFIED כשסוג הדחיסה לא מוגדר (תתבצע דחיסה מסוג RAW).

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

דחיסת אורז

כמו שצוין, שרת Web Risk תומך כרגע בדחיסת Rice. מידע נוסף זמין במאמר Golomb coding בוויקיפדיה.

דחיסה/פריסה

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

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

כלומר, הרשימה של המספרים השלמים [1, 5, 7, 13] תעבור קידוד כ-1 (הערך הראשון) והדלתאות [4, 2, 6].

הערך הראשון מאוחסן בשדה firstValue והדלתאות מקודדות באמצעות מקודד Golomb-Rice. הפרמטר Rice‏ k (ראו בהמשך) מאוחסן ב-riceParameter. השדה numEntries מכיל את מספר הדלתאות שמקודדות במקודד Rice (3 בדוגמה שלמעלה, לא 4). השדה encodedData מכיל את הדלתאות המקודדות בפועל.

מקודד/מפענח

במקודד/מפענח של Rice, כל דלתא n מקודדת כ-q ו-r, כאשר n = (q<<k) + r (או n = q * (2**k) + r) הוא קבוע ופרמטר של המקודד/מפענח של Rice.k הערכים של q ושל r מקודדים בזרם הביטים באמצעות סכימות קידוד שונות.

המנה q מקודדת בקידוד אונרי ואחריה 0. כלומר, 3 יקודד כ-1110, 4 כ-11110 ו-7 כ-11111110. המנה q מפוענחת קודם.

השאר r מקודד באמצעות קידוד בינארי קטום. רק k הביטים הכי פחות משמעותיים של r נכתבים (ולכן נקראים) מזרם הביטים. השארית r מפוענחת אחרי שq מפוענח.

מקודד/מפענח של ביטים

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

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

ראשים שנוספו	BitEncoder After Adding Bits
	[]
0	[00000000]
1	[00000010]
1	[00000110]
1,0,1	[00101110]
0,0,0	[00101110, 00000000]
1,1,0	‪[00101110, 00000110]