מעט עזרה - ערכי האש

[ron369]

מעט עזרה - ערכי האש

בוקר טוב. בהתחלה חשבתי לשאול בפורום מתמ', והחלטתי שעדיף פה, בכל זאת. בשביל פרוייקט שאני מנסה לכתוב עכשיו (בעצם - בודק האם זה בכלל אפשרי ברמתי), אני אצטרך, קרוב לוודאי, פונקציית האש מיוחדת (לא צריך להסביר פה מה זה hash

). המטרה של פונקציית ההאש היא לאפשר pattern matching מהיר. כלומר, לכל "תמונה" בייצוג דו מימדי, אני צריך למצוא את החלק הגדול ביותר ממנה, שנמצא באיזה DB מוכן (אשר, כמובן, ייטען בחלקו הגדול לראם). כלומר, ה"מפות" שצריך להשוות הן מטריצות, שמכילות 0 או 1 או 2 בכל תא. בדקתי קצת את הנושא, וגיליתי שפונקציית ההאש הנוכחית שמומלצת במקרה שלי (xor של הכל, פחות או יותר), לא מתאימה, כי אני מחפש כמה תכונות ספציפיות שישפרו את המהירות: א) התמונה של שני ערכים קרובים במישור הבעה, צריכה להיות קרובה גם בתמונה, כדי לאפשר "חיפוש מקורב" של pattern. ב) כאשר מחפשים pattern כלשהו, צריכה להתאפשר אחת משתי האופציות הבאות. או שאם נחפש pattern מינימלי, גם כאלו הגדולים ממנו שמכילים אותו יימצאו ב"קלות", או שאם נחפש pattern מקסימלי, גם כאלו שהוא מכיל יימצאו ב"קלות". (אלו שני הפכים של הטענה). ג) הפיכת הערכים 1 ו-2, עדיף שתהיה מהירה ככל האפשר. כלומר, אם אפשר, שניתן יהיה להגיע מהר מההאש של המטריצה שמכילה את הערכים 0,1,2, להאש של המטריצה שמכילה את הערכים 0,2,1. המטרה של החלק השני (ב' - החשוב ביותר), היא שבמקרה שאנו רוצים לחפש למשל מטריצה בגודל 5X5, בתוך מסד נתונים המכיל "דברים" בגודל 20X20, לא נצטרך לחפש את כל התת-התאמות האפשריות. חשבתי, חשבתי, וחשבתי, ואין לי ממש מושג איך לעשות את זה. במילא, לרוב תיעבתי, hash. יש רעיונות?

בתודה, רון.

 

[ron369]

מצטער אם זה קצת מבולגן,

קשה לי להסביר מה אני צריך

 

[johnny d]

DCT אתה מכיר ?

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

 

[johnny d]

אופס לא שמתי לב

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

 

[ron369]

אני לא בטוח אם הבנתי למה אתה מתכוון

אני לא בדיוק רוצה שחלק מהתמונה יהיה תואם, אלא ש, בדרך מסויימת, אם המטריצה M מוכלת במטריצה N, אזי תמונת המטריצה M תהיה מוכלת, או קשורה בדרך כלשהי, לתמונת המטריצה N. למשל, שפעולה כלשהיא על התמונות של N ו-M תחזור 1 אמ"מ M מוכל ב-N, למרות שהתמונות לא בהכרח מוכלות (אבל הפונקציה, כמובן, צריכה לעבוד יעיל. איכשהו.) ובקשר לאיבוד המידע - אני מודע לכך. אני לא צריך התאמה חח"ע, אלא רק "סיכוי טוב" לכך שההתאמה קיימת, ואחר"כ ניתן לוודא את הסיטואציה. ובקשר להודעה הקודמת שלך - אני לא בטוח שהבנתי מה הכוונה. אתה מתכוון לעיבוד תמונה? ה"תמונה" שלי כבר נמצאת במחשב (ומכילה רק 0, 1, או 2 בכל תא). בכל מקרה, תודה על התשובה

 

[johnny d]

זה שהתמונה נמצאת במחשב

לא ממש קשור לעובדה שניתן לעבד אותה לצרכים מסויימים. לדוגמה בהינתן תמונה כלשהי, ניתן לבצע סילום התמונה לרזולוציה של 10x10. זו פונקצית גיבוב לכל דבר, היא לא בטוחה, לא יעילה, ולא פרקטית לשום שימוש שאני יכול לחשוב עליו כרגע אבל זה אכן פ' גיבוב. בנוגע לאיבוד מידע, אם בתמונה המקורית ישנו איזור הדומה לתמונה במאגר המידע שלך ולאחר הסילום חלק זה של התמונה הופך להיות אחוז בודד מהאינפורציה שפיקסל בודד לאחר הסילום מכיר, לא תוכל בשום צורה להסיק כי חלק זה היה קיים בתמונה המקורית. בנודע למטריצות, מה שאמרתי שמספר התת-מטריצות של מטריצה אקספוננציאלי לגודל הקלט.

 

[ron369]

סילום?

בכל מקרה, מה שאתה טוען הוא שזה בלתי אפשרי? אני לא מחפש פתרון מושלם, אבל קיוויתי שנוכל לקבל אינדיקציה לגבי שייכות, לפי השוואה פשוטה "יחסית" של ההאש-ים.

 

[johnny d]

scaling

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

 

[ron369]

תודה על העזרה ../images/Emo13.gif

טוב נו. עכשיו אני פשוט... אחפש דרך אחרת, או משהו כזה.