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

[toxigun]

לפני זמן קצר נתנו לנו, הסטודנטים בקורס מבוא למדעי המחשב באונ' חיפה עבודת בית מאד מעניינת - למצוא מרחק עריכה בין שתי מלים. מרחק עריכה הוא הכמות המינימאלית של פעולות אלמנטריות שצריך לעשות בכדי להגיע ממחרוזת אחת לשניה. פעולות אלמנטריות הן החלפת תו בתו אחר, מחיקת תו והוספת תו חדש (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;
}

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

[Ewingum]

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

[Holy]

משהו פרקטי?

לקבל 100 במבחן

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

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

וסתם להעשרה

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

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

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

[Asystole]

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

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

[Holy]

חחחחחחחחח

אהבתי

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

סתם לידע כללי

[Asystole]

Cobol לוקח בניין שלם...

גם ליידע כללי...

[Asystole]

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

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

[toxigun]

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

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