ניתוח מחרוזות חלק א' התאוריה (על רגל אחת)

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

על פניו, זה נשמע די קל ופשוט, אני מוצא משהו המוגדר כ"גבול", ואז אני מחפש על זה משמעות נכון? ובכן, מסתבר שזה לא כזה פשוט. יותר מזה, גיליתי שישנם 2 סוגים של "שפות" כאשר רוצים לנתח מידע – אחת נקראת "שפה דטרמיניסטית" והשנייה "שפה לא דטרמיניסטית". באנגלית הם קיבלו את השמות Deterministic language ו Nondeterministic . כאשר מדברים עליהם, מדברים על הבנת ההקשר (context).

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

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

כיצד מחשב יבין זאת, כשפה אנושית?

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

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

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

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

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

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

עוד שפה דטרמיניסטית היא אוטומט מתמטי. האוטומט המוכר ביותר הוא Regular Expression . על רגל אחת, מדובר על מודל חישובי, אשר יוצר סוג של תבנית, אשר מספקת התנהגות ברורה בכל מצב, בשביל להגיע לתשובה סופית מוחלטת על ידי פעולות מובנות ומוכרות.

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

עכשיו שאלה – כאשר מדובר בדף HTML, האם מדובר בשפה דטרמיניסטית או לא?

כתיבת תגובה

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

הלוגו של WordPress.com

אתה מגיב באמצעות חשבון WordPress.com שלך. לצאת מהמערכת / לשנות )

תמונת Twitter

אתה מגיב באמצעות חשבון Twitter שלך. לצאת מהמערכת / לשנות )

תמונת Facebook

אתה מגיב באמצעות חשבון Facebook שלך. לצאת מהמערכת / לשנות )

תמונת גוגל פלוס

אתה מגיב באמצעות חשבון Google+ שלך. לצאת מהמערכת / לשנות )

מתחבר ל-%s