עבור לתוכן
  • צור חשבון
  • מי אנחנו?

    שלום אורח/ת!

     
    שים לב - על מנת להשתתף בקהילה שלנו, להגיב ולפתוח דיונים חדשים, עליך להצטרף כחבר רשום.

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

    לא אוהבים שמציקים לכם במייל? ניתן להירשם לאתר אך לוותר על הרישום לעידכוני המייל השבועיים.

ארכיון

דיון זה הועבר לארכיון ולא ניתן להוסיף בו תגובות חדשות.

toxigun

מרחק עריכה בין שתי מלים

Recommended Posts

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

הנה פונקציה edit_distance שמחשבת מרחק עריכה הין שתי מלים (הפתרון של שעורי הבית שלנו ::)):


#include <stdio.h>
#include <stdlib.h>

int min3(int a, int b, int c)
{
if (a<=b && a<=c) {
return a;
} else if (b<=a && b<=c) {
return b;
} else if (c<=a && c<=b) {
return c;
} else {
printf("BUG!\n");
exit(EXIT_FAILURE);
}
}

int edit_distance(char *word1, char *word2)
{
int *D, len1, len2, i, j, p;
len1 = strlen(word1);
len2 = strlen(word2);
p=(len1+1)*(len2+1)*sizeof(int);
if (NULL==(D=(int *)malloc(p))) {
printf("Not enough memory!\n.");
exit(EXIT_FAILURE);
}
for(i=0;i<=len1;i++) {
D[i]=i; /* d[i,0]=i; */
}
for(i=0;i<=len2;i++) {
D[i*(len1+1)]=i;
}
for(i=1;i<=len1;i++) {
for(j=1;j<=len2;j++) {
p=!(word1[i-1]==word2[j-1]);
D[j*(len1+1)+i]=min3(D[(j-1)*(len1+1)+(i-1)]+p,
D[j*(len1+1)+(i-1)]+1,
D[(j-1)*(len1+1)+i]+1);
}
}
p=D[len2*(len1+1)+len1];
free(D);
return p;
}

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

שתף דיון


קישור ישיר להודעה
שתף באתרים אחרים

מישהו יכול לתת לי דוגמא למשהו פרקטי שמשתמשים בזה? :P;)

שתף דיון


קישור ישיר להודעה
שתף באתרים אחרים

משהו פרקטי?

לקבל 100 במבחן :)

בתכלס אני בתור סטונדט בטכניון הבנתי כבר שמה שאנחנו עושים לא ישמש אותנו אף פעם

התרגיל מיועד רק בשביל לבדוק ידע בתכנות (רקורסיה וכו) וחשיבה טובה על אלגורתמים

וסתם להעשרה

אני לומד על מעבד MIPS שמת כבר לפני איזה 10 שנה

אני לומד אסמבלר של PDP-11 שמת לפני 10 שנה

מה שחשוב זה העקרונות ולא השימוש :)

שתף דיון


קישור ישיר להודעה
שתף באתרים אחרים

זה לא נכון לדבר על שפות מתות!

Cobol שמת לפני 10 שנה לדוגמא (זה השפה השנייה בעתיקותה אחרי Fortran), אז רוב מערכות המחשוב של בנק הפועלים מבוססות עליו...

שתף דיון


קישור ישיר להודעה
שתף באתרים אחרים

חחחחחחחחח

אהבתי :)

PDP-11 זה מחשב שלוקח חדר

סתם לידע כללי :)

שתף דיון


קישור ישיר להודעה
שתף באתרים אחרים

ועוד משהו ליידע כללי:

PDP-11 נקרא "מיני-מכונה" בגלל שהוא תפס שטח בגודל של רק ארון! (כל השאר היו הרבה יותר גדולים...)

שתף דיון


קישור ישיר להודעה
שתף באתרים אחרים

מישהו יכול לתת לי דוגמא למשהו פרקטי שמשתמשים בזה? :P;)

ל-Word יש מילון של מלים, ואם הוא מוצא מילה שגויה, הוא מציע מילים "קרובות" אל המילה השגויה כאפשרויות לתיקון. מילה קרובה למילה X היא מילה עם מרחק עריכה נמוך מהמילה X.

שתף דיון


קישור ישיר להודעה
שתף באתרים אחרים

×
  • צור חדש...
Back to top button
Close