מילון

[gilad_no]

מילון

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

 

[galh]

יש את trie tree או משהו דומה...

אולי המילון יציע לך את השם הנכון.

 

[IsraeliSecretToilets]

גם אני הייתי ממליץ..

על trie, אבל עם trie יש בעיה לא קטנה של זיכרון. הוא אוכל אותו בכמויות. אבל אם הזיכרון לא חושב, אז זה פ'סדר

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

 

[gilad_no]

על זה בדיוק שאלתי

 

[IsraeliSecretToilets]

זה לא ממש אלגוריתם לתיקון מילה..

ואני לא מכיר אלגוריתמים כאלה. אבל אני מכיר אלגוריתם מאד פשוט למציאת מרחק עריכה בין מחרוזות. בהנתן מחרוזת נגדיר עליה פעולות עריכה: 1) מציאת תו במקום כלשהו 2) מחיקת תו במקום כלשהו 3) החלפת תו במקום כלשהו בתו אחר. בהנתן שתי מחרוזות S,T מרחק העריכה ביניהן הוא המספר המינימאלי של פעולות עריכה שיש לבצע על מנת להגיע מ-S ל-T. אני יכול לתת לך אלגוריתם מאד פשוט למציאת מרחק עריכה. ומה שאתה תצטרך לעשות זה לחרוש על המילון שלך, ולחפש בו מילים שמרחק העריכה שלהן מהמילה השגויה הוא נמוך. הנה האלגוריתם. נתונות שתי מחרוזות S באורך n ו-T באורך m. התו הראשון יסומן על ידי אינדקס 1 (ולא 0, כמקובל בשפת C). נקצה מטריצה M בגודל n+1,m+1 (במטריצה האינדקסים מתחילים מאפס), ולאחר מכן נבצע את הפעולות הבאות:

for i = 0 to n do M[i,0] = i for j = 0 to m do M[0,j] = j for i = 1 to n for j = 1 to m if S = T[j] then p = 0 else p = 1 M[i,j] = min( M[i-1,j]+1, M[i,j-1]+1, M[i-1,j-1]+p ) return M[n,n]​

 

[IsraeliSecretToilets]

ועוד משהו..

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

 

[IP yuval]

אולי hspell יעזור לך.

http://www.ivrix.org.il/projects/spell-checker/

 

[annefan]

map

זה הסטנדרט, עם מימוש פנימי של עץ, לטוב ולרע. בלא מעט STL-ים יש את hash_map (שעשוי להיכנס לסטנדרט הבא) והוא מממש map ע"י טבלת גיבוב (

). STLport נותן לך אותו, והוא cross-platform אם זה חשוב לך. STL של VS.NET כנ"ל (שים לב שהוא יושב ב-stdext ולא ב-std, זו דרישה של הסטנדרט). אני חושב שגם ב-gcc יש אותו.