בתשובה לגדי אלכסנדרוביץ', 17/10/04 13:36
בלי קשר לכלום 254036
ערן בילינסקי • בתשובה לגדי אלכסנדרוביץ' יום א', 17/10/2004, 13:40
לא יודע.
<אזהרת גיקים>
אני יכול לראות יתרון לפונקציית ערבול (זמן שליפה). עם זאת, אם מאחסנים את מחרוזת המפתח ב-Trie אפשר להגיע לזמן חיפוש קבוע לכל צורך מעשי, לדעתי.
</אזהרת גיקים>
בלי קשר לכלום 254401
ירדן ניר-בוכבינדר • בתשובה לערן בילינסקי יום ב', 18/10/2004, 15:15
<למה סגרת את אזהרת הגיקים?>
(ולפני שכותבים <אזהרת גיקים>, לא צריך <אזהרת גיקים>?)
למה Trie כשאפשר hash? אתה לא צריך להדפיס רשימה אלפביתית שלהם, אני מניח.
בלי קשר לכלום 254406
ערן בילינסקי • בתשובה לירדן ניר-בוכבינדר יום ב', 18/10/2004, 15:24
העדפתי Trie כי לא היה לי רעיון לפונקציית ערבול עבור URL, אז אני יכול ליצר מפתח (פשוט את הבא בתור ב-Trie) ולהשתמש בו. זה פחות טוב מבחינת ביצועים?
בלי קשר לכלום 254509
גדי אלכסנדרוביץ' • בתשובה לערן בילינסקי יום ב', 18/10/2004, 20:28
על קצה המזלג, מה זה Trie?
בלי קשר לכלום 254520
ערן בילינסקי • בתשובה לגדי אלכסנדרוביץ' יום ב', 18/10/2004, 20:58
(תנאי מוקדם כדי להבין הסבר זה יש להכיר את המושגים "מצביע" ו"מערך" בתכנות)

Trie הוא מבנה נתונים שבנוי כך:

הצומת הראשון מצביע אל מערך שמכיל את כל אותיות האלפבית של המפתח של המידע. כל איבר במערך, בנוסף לכך שהוא מכיל אות כלשהי (נסמנה a), מכיל גם מצביע למערך נוסף בעל אותו מבנה (שמאותחל ל-null - "כלום"), ומצביע לערך (Value), שמאותחל גם הוא ל-null. המצביע למערך הנוסף אכן מצביע למערך שכזה רק אם הוכנס ערך שהמפתח שלו, במקום המתאים, כולל את האות המתאימה (a). כלומר, עבור הכנסת המפתחות abc, abd ו-abdd נקבל את המבנה הבא:

מצביע לתחילת המבנה - המערך (נסמנו 1).

מערך (1) שמכיל את כל אותיות האלפבית. בתא של האות a המצביע אל מערך נוסף אינו null אלא מצביע למערך (נסמנו 2), כל שאר המצביעים במערך זה הם null.

מערך (2) שמכיל את כל אותיות האלפבית. בתא של האות b המצביע אל מערך נוסף אינו null אלא מצביע למערך (נסמנו 3), כל שאר המצביעים במערך זה הם null.

מערך (3) שמכיל את כל אותיות האלפבית. בתא של האות c המצביע אל *ערך* אינו ריק אלא מצביע אל הערך המתאים למפתח abc. בתא של האות d המצביע אל ערך גם אינו ריק אלא מצביע אל הערך המתאים למפתח abd. כמו כן, בתא זה גם המצביע למערך נוסף אינו null אלא מצביע למערך (נסמנו 4), כל שאר המצביעים במערך זה הם null.

מערך (4) שמכיל את כל אותיות האלפבית. בתא של האות d המצביע אל הערך אינו ריק אלא מצביע אל הערך המתאים למפתח abdd. כל שאר המצביעים במערך זה הם null.

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

מאד נוח להחזיק בצורה כזו מילון של ערכים, כי כפי שציין ירדן, קל מאד להדפיס אותם לפי סדר אלפביתי - ערוך טיול DFS על המבנה והדפס כל צומת שנכנסת אליו לראשונה ושהמצביע לערך שלו אינו null.
בלי קשר לכלום 254541
ירדן ניר-בוכבינדר • בתשובה לערן בילינסקי יום ב', 18/10/2004, 22:29
מה רע בפונקציית הערבול הסטנדרטית למחרוזות (למשל זו של ג'אווה)?

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

אבל רגע, אם אני זוכר נכון לקח מאיזשהו קורס, מה שנכון למבני נתונים בזכרון גישה אקראית, לא בהכרח נכון לנתונים בדיסק - שם יש שיקולים של גישות סמוכות וכאלו, מה שעשוי להיות רלוונטי לאתר מבוקש כמו tinyurl.
בלי קשר לכלום 254553
ערן בילינסקי • בתשובה לירדן ניר-בוכבינדר יום ב', 18/10/2004, 23:03
נזכרתי למה Trie. כי המפתח שאני רוצה לייצר צריך להיות גם קריא לדפדפנים (שכן זו הרי הבעיה שרצינו לפתור - קישורים ש"נשברים"). Trie, עם האלפבית המוגבל שלו, מתאים למשימה - אני מגדיר מהו האלפבית, ואני אגדיר כזה שמכיל רק אותיות מתאימות. עם זאת, ברור שאפשר בקלות להגדיר פונקציה חד-חד ערכית פשוטה גם על התוצאה של פונקציית הערבול הסטנדרטית שהטווח שלה הוא מילים מהאלפבית המוגבל הנ"ל.
חזרה לעמוד הראשי המאמר המלא
מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים
האייל הקורא RSS מאמרים | כתבו למערכת | אודות האתר | טרם התעדכנת | ארכיון | חיפוש | עזרה | תנאי שימוש © כל הזכויות שמורות