הערות שיש לי על אלגוריתם ה-BiDi של Unicode

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

כחלק מהעבודה שלי על bidiedit החלטתי שלא להשתמש בספריות מוכנות למימוש ה-Unicode BiDi Algorithm (להלן UBA), אלא לממש אותו בעצמי. אני מאוד שמח שכך עשיתי, מכיוון שיצא לי להכיר אותו כפי שעוד לא יצא לי להכיר אותו בעבר. כתוצאה מכך, אני חושב שיש בו מקום לשיפור. אני מתאר את הרעיונות שלי פה, למרות שהם מאוד לא בשלים, מתוך תקווה לקבל תגובות מאנשים שמכירים את האלגוריתם ויש להם משהו אינטיליגנטי להוסיף. למרבה הצער, לא מצאתי רשימות תפוצה פתוחות לציבור הרחב באתר של Unicode. אם מישהו מכיר, אנא תנו לי הפניה.

ההערות שלי בסדר אקראי:

  • ניתן לפתור את בעיית המקף הידועה ע”י הוספת חוק לפני W4 (אני לא בטוח בדיוק איפה) שאומר “ES שבה מייד אחרי R הופך ל-ON, אחרת ל-ET”. זה יאפשר לכתוב הן “נפגש ב-12” ו-“היתרה שלי היא ‎-12” בלי להשתמש בתווי בקרה כדי לגרום למינוס להופיע במקום הנכון.
  • בפרק 5.2, התיקון לחוק X9 גורם לתווי הבקרה למצוא את עצמם במקומות לא הגיוניים בעליל. צריך לתת לתווים שמתחילים ריצה חדשה (LRE, RLE, LRO, RLO) את הרמה שהם מתחילים, ול-PDF את הרמה שהוא מסיים. במילים אחרות, תווי הבקרה צריכים לקבל את הרמה הגבוהה מבין השתיים שבהן הם נוגעים. זה ימקם את תו הבקרה שמתחיל רמה בתחילת הרמה (מימין עבור רמות של ימין שמאל, שמאל עבור רמות של שמאל ימין) ואת התו שמסיים את הרמה בקצה השני.
  • באותו הפרק צריך להוסיף המצלה שבמידה ומציגים את התווים בצורה כלשהי, לתת לתו ה-PDF צורה שהיא כיוונית (משהו בסגנון של U21B6,‏ “↶”), ולבצע לה mirroring אם היא ברמה זוגית (במקרה של ההמלצה שלי, זה יהפוך אותו ל-U21B7‏, “↷”). טקסט לדוגמא:
    ‭הוא אמר “‎<LRE>Car in Hebrew is מכונית<PDF>”.‬
    יוצג כ:
    הוא אמר “‪↦Car in Hebrew is מכונית↶‬”.

מאת

שחר שמש

מייסד–שותף וחבר ועד בתנועה לזכויות דיגיטליות מייסד שותף בעמותת „המקור”. פעיל קוד פתוח. מפתח שפת התכנות Practical

32 תגובות בנושא “הערות שיש לי על אלגוריתם ה-BiDi של Unicode”

  1. באמת, אני לא חושב שלשנות אלגוריתם של Unicode זה רעיון טוב בכלל.

    1. סביר להניח שזה יהיה מאוד קשה
    2. המימוש יהיה שבור בהרבה מקרים והאלגוריתם לא יהיה תואם לאחור.

    לפי דעתי צריך לאמץ את פריסת מקלדת lyx ולהסביר כיצד להשתמש בתווי כיווניות.

    הבעיה היא שהיום אנשים לא משתמשים בתווים כאלה בגלל שב־Windows מאוד קשה להקליד אותם.

    ואגב, “נפגש ב-12” צריך לכתוב “נפגש ב־12” – שוב עוד בעיית מקלדת עברית הנוכחית שלא נותנת בקלות להקליד את “־”

  2. עוד משהו קטן, לממש אלגוריתם Unicode זה בד”כ רעיון רע… כי זה מסובך, קל לטעות וגם הרבה מימושים בפועל יוצאים שבורים, ראה דוגמה bidi ב־KDE 3 שהמקף מתנהג שם שונה.

    אז, אלא אם אתה מומחה גדול ב־Unicode לא כדאי לכתוב מימושים בעצמך.

  3. לא מצאתי רשימות תפוצה פתוחות לציבור הרחב באתר של Unicode. אם מישהו מכיר, אנא תנו לי הפניה.

    send a message to ecartis@unicode.org and write “subscribe bidi” in the subject line

  4. ארתיום:

    לפי דעתי צריך לאמץ את פריסת מקלדת lyx ולהסביר כיצד להשתמש בתווי כיווניות.

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

    ואגב, “נפגש ב-12” צריך לכתוב “נפגש ב־12”

    פה אתה רק בתיאוריה צודק. העובדה הפשוטה היא שיוניקוד שברו את המקרה ה”נכון” (כלומר, זה שקשור ב- ‎-12) רק כדי ש-12 יעבוד. העובדה הפשוטה היא שתקנים בכלל, ויוניקוד בפרט, מתחשבים במצב הקיים. זו הסיבה שבעברית יש code points נפרדים עבור האותיות הסופיות, על אף שהתקן של יוניקוד מגדיר שה-code points מיועדים רק עבור אותיות ממש, ושאת ה-presentation forms מנוע התצוגה אמור לעשות (מה שאכן קורה בערבית).

    עוד משהו קטן, לממש אלגוריתם Unicode זה בד”כ רעיון רע… כי זה מסובך, קל לטעות וגם הרבה מימושים בפועל יוצאים שבורים, ראה דוגמה bidi ב־KDE 3 שהמקף מתנהג שם שונה.

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

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

    שחר

  5. כמה הערות – למה עוד עורך טקסט גרפי? למה לא לעשות חלופה חדשה לגרש ז”ל בתכנות שורת הפקודה?

    בנוסף, בדקתי את העורך.
    א. למה אין שורות [בעצם פסקאות] משתנות כמו בעורכים geresh & gedit & kate שנהפכות בכיוונים בהתאם לשפה השלטת באותה שורה?
    ב. העורך אינו מופיע בתפריטי kde?

  6. שאלת הדיוט סקרן: אתה חושב שיש טעם להשקיע (עכשיו, או בדיעבד) בLRO, LRM, PDF וכל הג’אז הזה? לא עדיף היה לתת ליוניקוד לעסוק בתכונות הכיווניות של הסימנים השונים ולהשאיר לרמה הגבוהה יותר (HTML או מה שלא יהיה) הגדרות כיווניות רקרוסיביות על קטעי טקסט?

  7. יואל – קראת את ההסבר באתר לגבי הגרסה?
    לגבי ב. – למיטב ידיעתי, גרסה 0.02 כן מופיעה.

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

    סיימון – אז למי היא כן פתוחה?

    שחר

  8. בעניין האותיות הסופיות, אני לא מסכים איתך. כבר מזמן שאותיות סופיות הן לא רק presentation form. יש להן מקשי מקלדת משלהן ויש לכותב בחירה אם להשתמש באות סופית או רגילה לפי שיקולים שונים. בעברית מודרנית אפשר ונכון להשתמש באותיות פ’ ו-כ’ בצורתן הרגילה, ולא הסופית, בסוף מלה (בעיקר תעתיקים מלועזית, תיעתוק פונטי, או ראשי־תיבות), כדי לציין שיש בהן דגש קל, מה שאומר שלסופיות האות יש משמעות פונטית — ומכיוון שיש לא-מעט מלים שהאיות הסטנדרטי שלהן כולל אות אחרונה לא-סופית, גם משמעות לקסיקלית. אפשר אפילו לחשוב על מקרים אפשריים של זוגות מלים שיהפכו להומוגראפים אם תתבטל ההבחנה בין אותיות סופיות לרגילות. זה לא presentation form כמו בערבית, שבה צורת האות ניתנת אחד-לאחד על־ידי המיקום שלה במלה. יוניקוד החליטו נכון בעניין הזה (לא שהייתה להם ברירה, בהתחשב בתקדימים של סטנדרטים ישנים יותר בעברית).

  9. אפשר למצוא workaround לכל בעיה, אבל זה לא אומר שצריך להיכנס לבעיה מלכתחילה. יש לך אותיות שמשתמשים רגילים להשתמש בהן בחופשיות, שיש להן משמעות פונטית ולקסיקלית. “ביפ” היא באמת מלה בת שלוש אותיות שאחרונה מהן היא פ’ רגילה, ולא “ביף” עם שפצור לצורך הצגה. למה לסבך את השימוש?

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

    בתקן כפי שהוא כיום כבר קיימים RLM ו-LRM, ועובדה שאף אחד לא משתמש בהם.

    כי בן אדם שעובד בחלונות לא יכול להקליד אותו בצורה שפויה! כנ”ל קיים סימן “־” – מקף־עליון ואף אחד (חוץ מבתי־דפוס) לא משתמש בו מאותה סיבה לחלוטין.

    קשה מאוד להשתמש במשהו שאי אפשר להקליד אותו!

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

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

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

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

    מימשתי כמה אלגוריתמים בunicode בעצמי, גם הבנתי הרבה יותר טוב דברים ובזכות זה גם למדתי המון מזה, דברים שמלווים אותי גם כאשר אין קשר ישיר לדברים האלו. למשל חישובים על מופע בינארי של בתים, דבר שלא היה לי ברור לפני 9-10 שנים,נהיה יותר ברור אחרי מימוש של בדיקה האם התו ב UTF-8 שלם או לא.
    ועוד הרבה דברים אחרים.

    שחר, אני ובעצם כל מי שמכיר ומבין את PDF, LRM ו RLM משתמשים בהם כאשר ניתן לעשות את זה.

    דעתי האישית היא שכל הגישה של דו כיווניות כרגע אינה נכונה (קראתי את התקן בגרסה 3 שלו לפני יותר מידי שנים כבר), ולדעתי צריך לפשט יותר את הצורך ואז למצוא את הפתרון לבעיה. עדיין גם במימוש “מושלם” של unicode tr9, יש הרבה מאוד בעיות של עבודה עם דו כיווניות, וזה מה שמביא אותי להבנה הזו (בתקווה שאני מפספס דברים).

  12. מימוש של אלגוריתמים כמו BiDi ובכלל של דברים זו הדרך הנכונה ללמוד ולהבין

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


    117 for( wxString::const_iterator i=str.begin(); i!=str.end(); ++i ) {
    118 classes.push_back( get_char_class(*i) );
    119 }

    ה־wxChar הוא wchar_t הוא לאו דווקא מכיל codepoint בודד (בפרט בחלונות)

    צריך לעשות איטרציה על code-points ולא על wxCharים.

    למה? כי זאת בעיה מאווווד נפוצה.

  13. ארתיום,

    אני חושב שהבנתי את מקור הבעיה. bidiedit זה לא קוד production. זהו reference implementation, וככזה, הוא מתמקד בחלקים שחשובים להבנה של התקן שהוא נועד להמחיש, ופחות בחלקים האחרים.

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

    שחר

  14. עדי סתיו – הערה דקדוקית קטנה – דגש בסוף מילה הוא תמיד דגש חזק, ולא דגש קל. ההבדל הוא שדגש חזק הוא חלק מה”שורש” של המילה.

    כמובן שאני מסכים לגמרי עם הנקודה שעלית, ואפילו יש לי אנקדוטה בעניין. לפני כמה שנים היה לי טלפון סלולרי של סמסונג עם מנגנון “חכם” לאותיות סופיות. רק שהוא בכלל לא היה חכם, והתוצאה היתה שנאלצתי לכתוב הודעות SMS ללא קיצורים – אחרת מילה כמו ‘אח”כ’ היתה הופכת ל-‘אח”ך’.

  15. לא מצאתי התייחסות ל־mirroring 😉 אבל ייתכן שאני טועה.

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

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

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

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

  16. לא, ה-mirroring פשוט עוד לא ממומש. הבעיה השניה קשורה למימוש של כלל W4 כאשר יש ריצה שאחרי הורדת תווי הבקרה שאמורים לרדת הופכת לריקה בין תו ET לבין תווי EN שמקיפים אותו. זה אפילו מתועד בקוד המקור תחת “ידוע, לא אכפת לי, אף אחד לא עושה דברים כאלו” 🙂

    וזה שיש לתקן בעיות מימוש לא אומר שלא צריך לנסות לשפר אותו.

    שחר

  17. הי שחר,

    א. run באנגלית, בהקשרים שכאן, זה “רצף”, לא “ריצה”.

    ב. מה שעדי וארתיום אמרו על אותיות סופיות (דוגמה להומוגרפים שעדי הזכיר זו מרצ, המפלגה, ששמה כבר אינו ראשי תבות; לפעמים יש סיבה, בכתיבה, לקטוע מילה באמצ — זה היה נהרס; לפי מילון אבן־שושן, לאותיות הסופיות יש גם ערכים שונים מהאמצעיות בגימטריה — 500-900, לפי הסדר). ומה זה SPNJ שהזכרת? גוגל מספר לי על המפלגה הסוציאליסטית של ניו ג’רזי, ואיכשהו נראה לי שהם לא קשורים.

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

    ד. ניסיתי למצוא חורים בהצעה שלך לגבי מקף\מינוס, ולא הצלחתי (אם כי אני מסכים עם ארתיום: – לא צריך להיות מקף). עם זאת, אני לא מחזיק מעצמי מומחה BiDi.

  18. לכולם – אני לא מדבר על RLM ועל LRM. אני מדבר על RLE, LRE, RLO ו-LRO, ועל כן גם PDF.

    שי,

    א. אני לא בטוח מה התרגום הנכון. במקרה של uba, המילה run מתייחסת לרצף של תוים שנמצאים באותו embedding level, אבל הם לאו דווקא באותו הכיוון. למעשה, אלא אם אתה משתמש בתווי הבקרה, כל הפסקה עומדת להיות run אחד.

    ב. לא מצאת כי זכרתי את שמו לא נכון. מדובר על ZWNJ, או Zero Width Non-Joiner, או U200C. אם תשים אותו אחרי אות שמקבלת shaping אוטומטי (למשל בערבית), תקבל את צורתה הסופית גם אם היא באמצע מילה. בן זוגו הוא U200D, או Zero Width Joiner, שגורם לאות לקבל את צורתה האמצעית גם אם היא בסוף מילה.

    ג. התקן לא מתאים אותם החוצה. התקן שם אותם במקומות אקראיים לחלוטין. אם אתה לא מאמין לי, תבדוק את המחשת ה-BiDi ותגיד לי אם היית מצפה למצוא את ה-PDF בין המילה “מכונית” לבין “is”.

    ד. אני לא במיוחד אוהב את ההצעה הזו. אני עדיין מתלבט.

    מאיר,
    אין לי מושג על מה אתה מדבר.

    שחר

  19. לפי מה שמודגם שם, תווי הבקרה מקבלים את הרמה של התו שלפניהם, מה שאומר באמת שה”פתח” וה”סגור” מקבלים רמות שונות; ומכאן, התנהגויות משונות.

    ההצעה שלך עדיין מאפשרת רמות שונות — למשל, בדוגמה שנתת, התו PDF עדיין יופיע באותו מקום (השינוי שלך יגרום לתו RLE להופיע בתחילת הרצף האנגלי, אבל PDF עדיין יוצמד לסוף הרצף העברי). הפתרון השפוי היחידי, אני חושב, הוא להגדיר שתו PDF יקבל את אותה רמה כמו התו שאותו הוא סוגר (כלומר, ההערה “במילים אחרות, תווי הבקרה צריכים לקבל את הרמה הגבוהה מבין השתיים שבהן הם נוגעים” לא נכונה).

  20. אתה כבר הדגמת: בהמחשה שקישרת אליה, PDF נוגע ברמות 1,3. אם הוא מקבל את “הרמה הגבוהה מבין השתיים שבהן [הוא נוגע]”, זו רמה 3, והוא שייך לרצף העברי ויופיע בסופו כלומר משמאלו. הרמה שהוא צריך לקבל היא או 1 (כמו LRE, “מוצמד החוצה” שיזרוק אותו לסוף המחרוזת שבמירכאות (מה שאני הצעתי) או 2 (במקרה שתו LRE מקבל רמה 2, וזה באמת ייתן את התצוגה שרצית, אבל זו לא אחת הרמות שהוא נוגע בהן).

  21. לא נכון. התווים נמצאים ב-levels ‏3 ו-1, אבל הרמות של הריצות הן 1 ו-2. ה-PDF מסיים את הריצה שברמה 2, וזו הרמה שהוא צריך לקבל.

    שחר

  22. אה, כל הויכוח הוא על המשמעות של הניסוח “הרמה שבה התו נוגע”; על המהות אנחנו מסכימים.

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

  23. 3.3.5 מוסיף character levels, אבל הוא לא מוסיף runs. אלו מחושבים עד X10, ואז נשארים סטטיים.

    כמות ה-embedding levels היא אחד לכל run, כאשר לשני runs סמוכים יש, בהכרח, embedding levels שונים (גם אם יוצא שיש להם אותיות באותו ה-level, מה שבהחלט יכול לקרות).

    שחר

  24. אני קורא שוב, ואני מסתכל שוב בהמחשה, ואני לא מוצא את המושג הזה של “run” שיש לו קיום עצמאי. כל מה שהם מדברים עליו הוא “level run”, כלומר, רצף של תווים באותה רמה; אף פעם לא “run level”. כל הרמות שהם מציינים — הן בהמחשה, הן לכל אורך סעיף 3.4 — הן רמות ששייכות לתווים בודדים, ואיך מטפלים ברצפי תווים עם אותה רמה (או אותה רמה ומעלה).

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

    מה החמצתי?

  25. שי,

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

    שחר

  26. הבנתי את השגיאה שלי: התיקון מופעל בשלב X9, ואז באמת יש רק שתי רמות (בדוגמה) — והכללים הנוכחיים מייצרים רמות שונות לפותח ולסוגר כבר אז.

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

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

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

    שחר

סגור לתגובות.