מבנה נתונים תמציתי

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

עבור מידע מסוים, אם על פי תורת האינפורמציה דרושים $Z$ ביטים לייצוג של המידע, אזי ייצוג של המידע יקרא:

מרומז אם הוא צורך $Z+O(1)$ ביטים של זיכרון.
תמציתי אם הוא צורך $Z+o(Z)$ ביטים של זיכרון,
קומפקטי אם הוא צורך $O(Z)$ ביטים של זיכרון.

לדוגמה, מבנה נתונים המשתמש ב $2Z$ ביטים של אחסון הוא קומפקטי, $Z+{\sqrt {Z}}$ ביטים הוא תמציתי, $Z+\lg Z$ ביטים גם הוא תמציתי ו- $Z+3$ ביטים הוא מרומז.

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

מילונים תמציתיים

מילונים תמציתיים הניתנים לאינדוקס, או בשמם הנוסף מילוני דרגה/בחירה, מהווים בסיס למספר טכניקות של ייצוג תמציתי, כגון עצים בינאריים, עצים $k$ -ארים, רב-קבוצות,^[2] עצי סיפות ומערכים.^[3] הבעיה הבסיסית היא לאחסן תת-קבוצה $S$ של העולם $U=[0\dots n)=\{0,1,\dots ,n-1\}$ המיוצגת בדרך כלל על ידי מערך-סיביות $B[0\dots n)$ כאשר $B[i]=1$ אם ורק אם $i\in S$ . מילון הניתן לאינדוקס תומך בפעולות הרגילות על מילונים (שאילתות, ובמקרה הדינמי גם הוספות ומחיקות) כמו גם בפעולות הבאות:

דרגה (rank) - שאילתה המקבלת אינדקס i של איבר ואיבר q ( $q\in \{0,1\}$ ) ומחזירה את מספר האיברים ב-B עד האינדקס i שהערך שלהם הוא q. פורמלית: $\mathbf {rank} _{q}(i)=|\{k\in [0\dots i]:B[k]=q\}|$ .
בחר (select) - שאילתה המקבלת אינדקס i ואיבר q ( $q\in \{0,1\}$ ) ומחזירה את המיקום של האיבר ה-i שהערך שלו הוא q. פורמלית: $\mathbf {select} _{q}(i)=\min\{k\in [0\dots n):\mathbf {rank} _{q}(k)=i\}$ .

ישנו ייצוג פשוט^[4] המשתמש ב $n+o(n)$ ביטים של זיכרון (מערך הביטים המקורי ומבנה עזר בגודל $o(n)$ ) התומך בפעולות דרגה (rank) ובחירה (select) בזמן קבוע. הוא משתמש ברעיון דומה לזה של שאילתות מינימום-טווח; ישנו מספר קבוע של רקורסיות לפני שעוצרים בתת-בעיה בגודל מוגבל. מערך הביטים $B$ מחולק לגושים גדולים בגודל $l=\lg ^{2}n$ ביטים וגושים קטנים בגודל $s=\lg n/2$ ביטים. לכל גוש גדול מאחסנים את הדרגה של הביט הראשון בטבלה נפרדת $R_{l}[0\dots n/l)$ ; כל כניסה כזאת דורשת $\lg n$ ביטים וסך הכל של $(n/l)\lg n=n/\lg n$ ביטים של זיכרון. בגוש גדול מאוחסנת טבלה נוספת $R_{s}[0\dots l/s)$ , השומרת את הדרגה של כל אחד מ- $l/s=2\lg n$ הבלוקים הקטנים שהיא מכילה. ההבדל כאן הוא שדרושים רק $\lg l=\lg \lg ^{2}n=2\lg \lg n$ ביטים לכל כניסה, כיוון שמספיק לשמור רק את ההפרשים מהדרגה של הביט הראשון בגוש הגדול המכיל. לכן, הטבלה דורשת סך הכל $(n/s)\lg l=4n\lg \lg n/\lg n$ ביטים. ניתן להשתמש בטבלת חיפוש $R_{p}$ כדי לשמור את התשובה לכל שאילתת דרגה אפשרית במחרוזת ביטים באורך $s$ לכל $i\in [0,s)$ , בעלות של $2^{s}s\lg s=O({\sqrt {n}}\lg n\lg \lg n)$ ביטים של זיכרון. כיוון שכל טבלאות העזר הללו צורכות $o(n)$ זיכרון, מבנה הנתונים הזה תומך בשאילתות דרגה בזמן $O(1)$ ו $n+o(n)$ ביטים של זיכרון.

כדי לענות על שאילתה עבור $\mathbf {rank} _{1}(i)$ בזמן קבוע, האלגוריתם מחשב בזמן קבוע:

$\mathbf {rank} _{1}(i)=R_{l}[\lfloor i/l\rfloor ]+R_{s}[\lfloor i/s\rfloor ]+R_{p}[i\lfloor i/s\rfloor ,i{\text{ mod }}s]$

בפועל, ניתן להחליף את טבלת החיפוש $R_{p}$ בפעולות על ביטים ובטבלאות קטנות יותר כדי למצוא את מספר הביטים הדולקים בבלוקים הקטנים. זה לעיתים קרובות מועיל, שכן מבני נתונים תמציתיים משמשים למערכות נתונים גדולות, שבהן החטאות מטמון נעשות הרבה יותר תכופות, והסיכויים שטבלת החיפוש תפונה מהמטמון גדלים.^[5] ניתן לתמוך בקלות בשאילתות בחירה על ידי ביצוע חיפוש בינארי על אותו מבנה עזר המשמש לפעולות דרגה; עם זאת, דבר זה דורש $O(\lg n)$ זמן במקרה הגרוע ביותר. ניתן להשתמש במבנה מסובך יותר המשתמש ב- $3n/\lg \lg n+O({\sqrt {n}}\lg n\lg \lg n)=o(n)$ ביטים של זיכרון נוסף, כדי לתמוך בפעולות בחירה בזמן קבוע.^[6] למעשה, ברבים מהפתרונות האלה מוסתרים קבועים בסימון $O(\cdot )$ אשר שולטים בבעיה לפני שניכר יתרון אסימפטוטי כל שהוא; יישומים באמצעות פעולות נרחבות על מילים ובלוקים של מילים-מיושרות לעיתים קרובות מראים ביצועים טובים יותר בפועל.^[7]

מילונים דחוסי-אנטרופיה

גישת ה- $n+o(n)$ זיכרון ניתנת לשיפור בזכות ההבחנה כי ישנם $\textstyle {\binom {n}{m}}$ תתי קבוצות של $[n)$ באורך $m$ (או מחרוזות בינאריות באורך $n$ עם בדיוק $m$ 1ים), ולכן $\textstyle {\mathcal {B}}(m,n)=\lceil \lg {\binom {n}{m}}\rceil$ הוא החסם התחתון של תורת האינפורמציה על מספר הביטים הדרושים לאחסון $B$ . ישנו מילון (סטטי) תמציתי המשיג את החסם הזה, דהיינו משתמש ב- ${\mathcal {B}}(m,n)+o({\mathcal {B}}(m,n))$ זיכרון.^[8] ניתן להרחיב את המבנה הזה כדי לתמוך בשאילתות דרגה ובחירה, תוך שימוש ב- ${\mathcal {B}}(m,n)+O(m+n\lg \lg n/\lg n)$ זיכרון.^[2] ניתן לצמצם את החסם הזה לתחלופת זיכרון/זמן על ידי הקטנת מקום האחסון של המילון ל- ${\mathcal {B}}(m,n)+O(nt^{t}/\lg ^{t}n+n^{3/4})$ וזמן שאילתה $O(t)$ .^[9]

דוגמאות

כאשר צריך לקודד רצף של פריטים בעלי אורך משתנה (כגון מחרוזות), ישנן מספר אפשרויות: גישה ישירה היא לשמור את האורך ואת הפריט באותה רשומה- והללו יכולות להיות ממוקמות אחת אחרי השנייה. זה מאפשר מעבר יעיל לעוקב, אבל לא מוצא את הפריט הkי. אופציה נוספת היא למקם את הפריטים לפי הסדר עם תו מפריד (למשל, מחרוזת עם סיומת אפס). אפשרות זו משתמשת במפריד במקום באורך, והיא איטית יותר באופן משמעותי, מפני שיש לסרוק את כל הרצף כדי למצוא תווים מפרידים. שתי האפשרויות יעילות מבחינת זיכרון. גישה אחרת היא הפרדה מאוגדת: ניתן למקם את הפריטים זה אחר זה, ללא מפרידים. ניתן לשמור את גבולות הפריט יכולים כרצף של אורכים, או באופן יעיל יותר, כהיסטים בתוך רצף זה. לחלופין, מקודדים בנוסף מחרוזת בינארית נפרדת המורכבת מ1ים במקומות בהם פריט מתחיל, ו0ים בכל מקום אחר. בהינתן המחרוזת זאת, פונקציית ה $select$ יכולה לקבוע במהירות היכן כל פריט מתחיל, בהינתן האינדקס שלו.^[10] מבנה זה קומפקטי אך לא תמציתי, היות שהוא צורך 2Z זיכרון, דהיינו (O(Z.

דוגמה נוספת היא ייצוג של עץ בינארי: עץ בינארי שרירותי על $n$ צמתים ניתן לייצג ב- $2n+o(n)$ ביטים, תוך תמיכה במגוון רחב של פעולות על כל צומת, אשר כוללות את מציאת האב שלו, הילד הימני והשמאלי שלו, והחזרת גודל של תת-עץ, כל אחת בזמן קבוע. מספר העצים הבינאריים השונים על $n$ קודקודים הוא ${\tbinom {2n}{n}}/(n+1)$ . עבור $n$ גדול, ערך זה הוא בערך $4^{n}$ ; ולכן ידרשו לכל הפחות כ- $\log _{2}(4^{n})=2n$ ביטים כדי לקודד אותו. עץ בינארי תמציתי לפיכך יתפוס רק $2$ ביטים לכל צומת.

לקריאה נוספת

פונקציית גיבוב מינימלית מושלמת

הערות שוליים

^ Jacobson, G. J (1988). Succinct static data structures (Ph.D.). Pittsburgh, PA: Carnegie Mellon University.
^ ^2.0 ^2.1 Raman, R.; V. Raman; S. S Rao (2002). "Succinct indexable dictionaries with applications to encoding k-ary trees and multisets". Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms (PDF). pp. 233–242. ISBN 0-89871-513-X.
^ Sadakane, K.; R. Grossi (2006). "Squeezing succinct data structures into entropy bounds". Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm (PDF). pp. 1230–1239. ISBN 0-89871-605-5. אורכב מ-המקור (PDF) ב-2011-09-29. נבדק ב-2017-01-02.
^ Jacobson, G. (1989). "Space-efficient static trees and graphs" (PDF).
^ González, R.; S. Grabowski; V. Mäkinen; G. Navarro (2005). "Practical implementation of rank and select queries". Poster Proceedings Volume of 4th Workshop on Efficient and Experimental Algorithms (WEA) (PDF). pp. 27–38.
^ Clark, D. (1998). "Compact pat trees" (PDF).
^ Vigna, S. (2008). "Broadword implementation of rank/select queries" (PDF). Experimental Algorithms. Lecture Notes in Computer Science. pp. 154–168. doi:10.1007/978-3-540-68552-4_12. ISBN 978-3-540-68548-7. אורכב מ-המקור (PDF) ב-2016-06-11. נבדק ב-2017-01-02.
^ Brodnik, A.; J. I Munro (1999). "Membership in constant time and almost-minimum space" (PDF). SIAM J. Comput. pp. 1627–1640. doi:10.1137/S0097539795294165.
^ Pătraşcu, M. (2008). "Succincter". Foundations of Computer Science, 2008. FOCS'08. IEEE 49th Annual IEEE Symposium on (PDF). pp. 305–313.
^ Belazzougui, Djamal. "Hash, displace, and compress" (PDF).

הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0

33626266מבנה נתונים תמציתי

[1] Jacobson, G. J (1988). Succinct static data structures (Ph.D.). Pittsburgh, PA: Carnegie Mellon University.

[raman2002succinct-2] 2.0 ^2.1 Raman, R.; V. Raman; S. S Rao (2002). "Succinct indexable dictionaries with applications to encoding k-ary trees and multisets". Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms (PDF). pp. 233–242. ISBN 0-89871-513-X.

[sadakane2006squeezing-3] Sadakane, K.; R. Grossi (2006). "Squeezing succinct data structures into entropy bounds". Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm (PDF). pp. 1230–1239. ISBN 0-89871-605-5. אורכב מ-המקור (PDF) ב-2011-09-29. נבדק ב-2017-01-02.

[jacobson1989space-4] Jacobson, G. (1989). "Space-efficient static trees and graphs" (PDF).

[gonzález2005practical-5] González, R.; S. Grabowski; V. Mäkinen; G. Navarro (2005). "Practical implementation of rank and select queries". Poster Proceedings Volume of 4th Workshop on Efficient and Experimental Algorithms (WEA) (PDF). pp. 27–38.

[clark1998compact-6] Clark, D. (1998). "Compact pat trees" (PDF).

[vigna2008broadword-7] Vigna, S. (2008). "Broadword implementation of rank/select queries" (PDF). Experimental Algorithms. Lecture Notes in Computer Science. pp. 154–168. doi:10.1007/978-3-540-68552-4_12. ISBN 978-3-540-68548-7. אורכב מ-המקור (PDF) ב-2016-06-11. נבדק ב-2017-01-02.

[brodnik1999membership-8] Brodnik, A.; J. I Munro (1999). "Membership in constant time and almost-minimum space" (PDF). SIAM J. Comput. pp. 1627–1640. doi:10.1137/S0097539795294165.

[patrascu2008succincter-9] Pătraşcu, M. (2008). "Succincter". Foundations of Computer Science, 2008. FOCS'08. IEEE 49th Annual IEEE Symposium on (PDF). pp. 305–313.

[10] Belazzougui, Djamal. "Hash, displace, and compress" (PDF).

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]