צריך עזרה במציאת אלגוריתם לחיפוש מידת התאמה בין מסמכים

[QuAKeR_996]

שלום חברה.

קיבלתי פרוייקט די מנופח יחסית לידע שלי כרגע כמתכנת.

מה שאני צריך זה אלגוריתם שמחזיר מידת התאמה בין שני מסמכים

למעשה התוכנית שאני צריך לפתח צריכה לנסות למצוא העתקות בין עבודות (מסמכי WORD) של סטודנטים.

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

יבורך מי שיעזור לי. אני לא ממש הצלחתי למצוא משהו כזה דרך Google.

תודה!

[שניצל]

זה באמת נושא די מורכב. אתה יכול להתחיל מכאן:

http://en.wikipedia.org/wiki/Near_Duplicate_Algorithms

http://en.wikipedia.org/wiki/Plagiarism_detection

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

לדוגמה, האם היא צריכה להתמודד רק עם העתקה מלאה של שורות/פסקאות, או שהיא צריכה לדעת להתמודד גם עם מקרה שבו העתיקו את הטקסט, אבל שינו בו מילים מסויימות?

[QuAKeR_996]

תודה קודם כל.

אני לא ממש מתעמק בנושא כי בעיקרון התוכנית לא ממש צריכה להשיג את המטרה שלה.

הדבר החשוב הוא האינטרגציה בין כל החלקים של התוכנה.

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

אני יתסכל על הלינקים ויכתוב כאן שוב.

תודה!

עריכה:

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

אם יש למישהו הצעה כלשהי אני אשמח לשמוע

[שניצל]

גרר. כתבתי תגובה ואז המחשב שלי קרס.

קודם כל, מה שמומלץ לעשות הוא לחלק את הטקסט לחלקים (שורות/פסקאות), בהנחה שרק חלק מועתק. עכשיו, אפשר לעשות כמה דברים:

א. להשוות השוואה מלאה בין חלקים שונים.

ב. לבדוק כמה פעמים מופיעה כל מילה/אות בכל חלק. בטקסטים דומים כנראה יופיעו אותן אותיות או מילים.

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

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

[Niseg]

אני במקרה שיחקתי עם תוכנית כזאת . היא נקראת bsdiff ו bspatch התוכנית יודעת ליצר patch לקבצים בינארים ויודעת לעשות התאמות חלקיות .

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

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

נ.ב

בגלל שעבר הרבה זמן בין כתיבת התגובה לשליחתה אולי הרעיון של שניצל יותר מוצלח

בהצלחה נשמע כמו פרויקט מעניין

[QuAKeR_996]

תודה שניצל!

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

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

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

אני אשמח לשמוע עליו.

Niseg - תודה רבה. זה דווקא נראה לי יותר כמו משהו שאני יכול לעשות לו אינטגרציה עם התוכנית שלי.

[Aurora Borealis]

יש כלי שבעקרון מגיע עם ווינדוס.

שמו הוא windiff.

אם אין לך אותו, אז אפשר בקלות למצוא אותו באינטרנט, כולה קובץ exe קטן.

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

[QuAKeR_996]

תודה.

אתה חושב שהוא מסוגל לתת לי מידת התאמה בין שני טקסטים ?

כלומר אחוזים ?

[Aurora Borealis]

אולי אפשר ליצור תוכנה שתתממשק מול windiff, ואז תספור הבדלים או משהו כזה.

מעולם לא ניסיתי לעשות דבר כזה. אני תמיד משתמש בwindiff כמו שהוא.

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

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

אז אין לי זמן לכל מיני דברים אקסטרה.

אם תגלה שאפשר לעשות דבר כזה עם windiff, יהיה מעניין לשמוע איך עשית את זה.

[Zelig]

כתבתי פעם אלגוריתם diff שמתבסס על least common subsequence. זה לקח פחות מיום, ולדעתי זה מספיק פשוט ומהיר לבעיה מסוג זה (אלא אם כן מדובר בקבצים בגודל מאות KB).

הפתרון שהשתמשתי בו מבוסס על dynamic programming, ולא עשיתי כמעט שום אופטימיזציה, ובכל זאת הוא מהיר מספיק להרבה בעיות:

http://en.wikipedia.org/wiki/Longest_common_subsequence_problem

הסיבוכיות תהיה O(MN) כאשר M הוא אורך טקסט אחד ו-N הוא אורך טקסט אחר.

diff על לינוקס משתמש באלגוריתם השוואה מבוסס על LCS, אבל מחשב את ה-LCS בדרך יותר יעילה.

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

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

וכו'.

[QuAKeR_996]

LCS זה אלגוריתם ל STRING נראה לי. אני לא חושב שהוא מספיק יעיל בשביל להשתמש בו לטקסטים ארוכים..

בכל זאת אני גם ינסה את הכיוון הזה.

יש דרך לכתוב תוכנה ב JAVA שתוכל להתמשק ל WINDIFF ?

[EAD]

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

לא הייתי עובד עם JAVA או C דווקא לומרות שהן פופלריות.

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

לדעתי LCS הוא פתרון נחמד ופשוט אך לא בטוח שיעבוד עבור מה שאתה צריך.

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

בסופו של דבר, הכי לא יעיל יהיה להתייחס לקובץ כמשהו בינארי של 0-1 ולבדוק, יותר יעיל יהיה לנסות לספק לאלגו' שתבנה כמה שיותר מידע ואפשרות "פירוק" קל יותר של הקובץ.

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

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

שיהיה בהצלחה

[Niseg]

אגב חשבתי על זה אתמול שאם אתה רוצה להשתמש ב bsdiff חוץ מהפיכה לטקסט כדאי לך גם למחוק את כל ה"'white space " עדיין יש סיכוי שהbsdiff ימצא שרוב העבודות דומות כי הן נכתבו על אותו נושא. בעיקר צריך להסתקל על כמה פעולות צריך לעשות כדי להגיע ממסמך אחד לשני והאורך של ההתאמות ואם הן התאמות של 100% או קרוב.

כעיקרון מה שbsdiff עושה זה מיצר קובץ עם פעולות שדומות לכאילו של Turing machine .

אם הוא נותן X,Y,Z (משמאל לימין) אז המשמעות של זה הוא קפוץ X בייטים בקובץ הישן( X יכול להיות שלילי) , העתק Y בייטים מהקובץ הישן לחדש בזמן שאתה סוכם אותם עם ה diff section (רמת ההתאמה נשמרת כסדרת בייטים והתאמה מלאה היא שורה של אפסים) ואז תעתיק Z בייטים מהextra section

דוגמה אחת שאני יכול לתת היא שפעם לקחתי קובץ ולקחתי את מהאמצע לסוף ושמתי בהתחלת הקובץ ובהמשך את התחלת הקובץ עד איפה שחתכתי והוא יצר קובץ פיצפון שכלל שתי פעולות . לך לאמצע ותעתיק עד הסוף ואז לך להתחלה ותעתיק עד האמצע. לא היה לו שום extra section שאם הקבצים שונים מאוד יהיה גדול מאוד.

קחו בחשבון שההודעה נשלחה 4-5 שעות אחרי שנכתבה