מבוא

הכל התחיל בתסריט קצר שהיה אמור לשלב מידע כתובת דוא"ל עובדים שהתקבלו מרשימת המשתמשים ברשימת התפוצה, כאשר תפקידי עובדים מתקבלים ממאגר מחלקת משאבי אנוש. שתי הרשימות יוצאו לקובצי טקסט של Unicode UTF-8 ונשמר עם סיומות קו יוניקס.

תוֹכֶן mail.txt

Иванов Андрей;[email protected]

תוֹכֶן buhg.txt

Иванова Алла;маляр
Ёлкина Элла;крановщица
Иванов Андрей;слесарь
Абаканов Михаил;маляр

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

$> sort buhg.txt > buhg.srt
$> sort mail.txt > mail.srt
$> join buhg.srt mail.srt > result
join: buhg.srt:4: is not sorted: Иванов Андрей;слесарь

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

$> sort buhg.txt
Абаканов Михаил;маляр
Ёлкина Элла;крановщица
Иванова Алла;маляр
Иванов Андрей;слесарь

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

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

$> LANG=ru_RU.UTF-8 sort buhg.txt
Абаканов Михаил;маляр
Ёлкина Элла;крановщица
Иванова Алла;маляр
Иванов Андрей;слесарь

שום דבר לא השתנה.

בואו ננסה לקודד מחדש את הקבצים לקידוד של בייט בודד:

$> iconv -f UTF-8 -t KOI8-R buhg.txt 
 | LANG=ru_RU.KOI8-R sort 
 | iconv -f KOI8-R -t UTF8

שוב שום דבר לא השתנה.

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

התשובה היא סטנדרטית בכל מקום: השתמשו באיזור המתכנת "ג" ואתה תהיה מאושר. בוא ננסה:

$> LANG=C sort buhg.txt
Ёлкина Элла;крановщица
Абаканов Михаил;маляр
Иванов Андрей;слесарь
Иванова Алла;адвокат

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

$> LANG=C sort buhg.txt > buhg.srt
$> LANG=C sort mail.txt > mail.srt
$> LANG=C join buhg.srt mail.srt > result

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

נראה שהבעיה נפתרה, אבל ליתר ביטחון, בואו ננסה קידוד רוסי אחר - Windows CP1251:

$> iconv -f UTF-8 -t CP1251 buhg.txt 
 | LANG=ru_RU.CP1251 sort 
 | iconv -f CP1251 -t UTF8 

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

אני לא אוהב מיסטיקה בתכנות כי היא בדרך כלל מחפה על טעויות. נצטרך לבדוק ברצינות איך זה עובד. sort ועל מה זה משפיע? LC_COLLATE .

בסוף אנסה לענות על השאלות:

• מדוע שמות משפחה נשיים מוינו בצורה שגויה?
• מדוע LANG=ru_RU.CP1251 התברר כשווה ערך LANG=C
• למה sort и להצטרף רעיונות שונים לגבי סדר המחרוזות הממוינות
• למה יש שגיאות בכל הדוגמאות שלי?
• סוף סוף איך למיין מחרוזות לפי הטעם שלך

מיון ביוניקוד

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

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

מיון מחרוזות בשפה טבעית היא בעיה מורכבת למדי. אפילו בקידוד הבתים הפשוטים ביותר, סדר האותיות באלפבית, אפילו באופן כלשהו שונה מהאלפבית הלטיני האנגלי, לא יעלה עוד בקנה אחד עם סדר הערכים המספריים שבהם מקודדות האותיות הללו. אז באלפבית הגרמני האות Ö עומד בין О и P, ובקידוד CP850 היא עוברת ביניהם ÿ и Ü.

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

מסתבר שגם אם נבנה טבלת סמלים מאפס, לא נוכל להקצות לה סדר סמלים אוניברסלי. באלפבית לאומיים שונים המשתמשים באותיות זהות, סדר האותיות עשוי להיות שונה. למשל, בצרפתית Æ ייחשב כקשירה וממוין כמחרוזת AE. בנורבגית Æ יהיה מכתב נפרד, אשר ממוקם לאחר Z. אגב, בנוסף לקשרים כמו Æ יש אותיות הכתובות עם מספר סמלים. אז באלפבית הצ'כי יש אות Ch, העומד ביניהן H и I.

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

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

בהתבסס על התכונות המפורטות לעיל, גובשו הדרישות הבסיסיות להשוואת מחרוזות המבוססות על טבלאות Unicode:

• השוואת מחרוזות אינה תלויה במיקום התווים בטבלת הקוד;
• רצפים של תווים היוצרים תו בודד מצטמצמים לצורה קנונית (A + העיגול העליון זהה לזה Å);
• כאשר משווים מחרוזות, תו נחשב בהקשר של המחרוזת ובמידת הצורך משולבת עם שכנותיה ליחידה אחת של השוואה (Ch בצ'כית) או מחולק לכמה (Æ בצרפתית);
• יש להגדיר את כל המאפיינים הלאומיים (אלפבית, אותיות רישיות/קטנות, סימני פיסוק, סדר סוגי כתיבה) עד להקצאה ידנית של הסדר (אימוג'י);
• השוואה חשובה לא רק למיון, אלא גם במקומות רבים אחרים, למשל לציון טווחי שורות (החלפת {A... z} ב לחבוט);
• ההשוואה צריכה להיעשות די מהר.

בנוסף, מחברי הדו"ח גיבשו מאפייני השוואה שמפתחי אלגוריתמים לא צריכים להסתמך עליהם:

• אלגוריתם ההשוואה לא צריך לדרוש קבוצה נפרדת של תווים עבור כל שפה (שפות רוסית ואוקראינית חולקות את רוב התווים הקיריליים);
• ההשוואה לא צריכה להסתמך על סדר התווים בטבלאות Unicode;
• משקל מחרוזת לא אמור להיות תכונה של המחרוזת, שכן לאותה מחרוזת בהקשרים תרבותיים שונים יכולים להיות משקלים שונים;
• משקלי השורות יכולים להשתנות בעת מיזוג או פיצול (מ x < y זה לא נובע מכך xz < yz);
• מחרוזות שונות בעלות משקל זהה נחשבות שוות מנקודת המבט של אלגוריתם המיון. הצגת סדר נוסף של מחרוזות כאלה אפשרית, אך היא עלולה לפגוע בביצועים;
• במהלך מיון חוזר, ניתן להחליף שורות עם אותם משקלים. עמידה היא תכונה של אלגוריתם מיון ספציפי, ולא תכונה של אלגוריתם השוואת מחרוזות (ראה הפסקה הקודמת);
• כללי המיון עשויים להשתנות עם הזמן כאשר מסורות תרבותיות מתעדנות/משתנות.

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

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

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

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

מקדמי משקל DUCET מסודר באופן הבא:

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

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

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

האלגוריתם הזה (עם שלל פרטים טכניים נוספים) נתן את השם לדוח מס' 10 - "אלגוריתם איסוף יוניקוד" (ACU).

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

לבדיקת יישומים ACU יש מיוחד тест, באמצעות קובץ משקולות, יישום DUCET. אפשר למצוא כל מיני דברים מצחיקים בקובץ המאזניים. לדוגמה, יש את סדר המהג'ונג והדומינו האירופאי, כמו גם סדר החליפות בחפיסת קלפים (סמל 1F000 ועוד). חליפות הקלפים ממוקמות לפי כללי ברידג' - PCBT, והקלפים בחליפה נמצאים ברצף T, 2,3, XNUMX...K.

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

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

Абаканов Михаил;маляр
Ёлкина Элла;крановщица
Иванов Андрей;слесарь
Иванова Алла;адвокат

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

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

מיון ב-glibc

תצוגה מהירה של קודי המקור של השירות sort של GNU Core Utils הראה כי בכלי השירות עצמו, לוקליזציה מסתכמת בהדפסת הערך הנוכחי של המשתנה LC_COLLATE כאשר פועל במצב ניפוי באגים:

$ sort --debug buhg.txt > buhg.srt
sort: using ‘en_US.UTF8’ sorting rules

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

על ויקי פרוייקט glibc מוקדש להשוואת מחרוזות פסקה אחת. מפסקה זו ניתן להבין כי ב glibc המיון מבוסס על אלגוריתם שכבר ידוע לנו ACU (אלגוריתם האיסוף של Unicode) ו/או בתקן קרוב אליו ISO 14651 (הזמנה והשוואה בינלאומית של מחרוזות). לגבי התקן העדכני, יש לציין כי באתר standards.iso.org ISO 14651 הוכרז רשמית כזמין לציבור, אך הקישור המתאים מוביל לדף שאינו קיים. גוגל מחזירה מספר עמודים עם קישורים לאתרים רשמיים שמציעים לקנות עותק אלקטרוני של התקן במאה יורו, אבל בעמוד השלישי או הרביעי של תוצאות החיפוש יש גם קישורים ישירים ל PDF. באופן כללי, הסטנדרט כמעט אינו שונה ממנו ACU, אבל משעמם יותר לקריאה כי הוא אינו מכיל דוגמאות ברורות למאפיינים לאומיים של מיון מחרוזות.

המידע המעניין ביותר על ויקי היה קישור ל עוקב אחר באגים עם דיון ביישום השוואת מחרוזות ב glibc. מהדיון ניתן ללמוד זאת glibc משמש להשוואת מחרוזות ISOשולחן אישי טבלת התבניות המשותפת (CTT), שאת כתובתו ניתן למצוא באפליקציה A תֶקֶן ISO 14651. בין 2000 ל-2015 הטבלה הזו נכנסה glibc לא היה מתחזק והיה שונה למדי (לפחות חיצונית) מהגרסה הנוכחית של התקן. משנת 2015 עד 2018 התקיימה התאמה לגרסה החדשה של הטבלה, ועכשיו יש לך הזדמנות לפגוש בחיים האמיתיים גרסה חדשה של הטבלה (CentOS 8), וזקן (CentOS 7).

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

ISO 14651 / 14652

קוד המקור של הטבלה בה אנו מעוניינים CTT ברוב ההפצות לינוקס נמצא בקטלוג /usr/share/i18n/locales/. הטבלה עצמה נמצאת בקובץ iso14651_t1_common. אז זו הנחיית הקבצים העתק את iso14651_t1_common כלול בקובץ iso14651_t1, אשר, בתורו, נכלל בתיקים לאומיים, לרבות en_US и ru_RU. ברוב ההפצות לינוקס כל קבצי המקור כלולים בהתקנה הבסיסית, אך אם הם אינם קיימים, תצטרך להתקין חבילה נוספת מההפצה.

מבנה הקובץ iso14651_t1 אולי נראה מאוד מילולי, עם כללים לא ברורים לבניית שמות, אבל אם מסתכלים על זה, הכל די פשוט. המבנה מתואר בתקן ISO 14652, עותק שלו ניתן להוריד מהאתר open-std.org. ניתן לקרוא תיאור נוסף של פורמט הקובץ מפרטים POSIX מ קבוצת פתוח. כחלופה לקריאת התקן, ניתן ללמוד את קוד המקור של הפונקציה collate_read в glibc/locale/programs/ld-collate.c.

מבנה הקובץ נראה כך:

כברירת מחדל, התו משמש כתו בריחה, וסוף השורה אחרי התו # הוא הערה. ניתן להגדיר מחדש את שני הסמלים, וזה מה שנעשה בגרסה החדשה של הטבלה:

escape_char /
comment_char %

הקובץ יכיל אסימונים בפורמט או (איפה x - ספרה הקסדצימלית). זהו הייצוג ההקסדצימלי של נקודות קוד Unicode בקידוד UCS-4 (UTF-32). כל שאר האלמנטים בסוגריים זווית (כולל , וכדומה) נחשבים קבועי מחרוזת פשוטים שיש להם מעט משמעות מחוץ להקשר.

מחרוזת LC_COLLATE אומר לנו שלאחר מכן מתחילים הנתונים המתארים את ההשוואה של מחרוזות.

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

האורך הכולל של הקטע בגרסה הנוכחית של הקובץ הוא כ-900 שורות. שלפתי דוגמאות מכמה מקומות כדי להראות את השרירותיות של שמות וכמה סוגים של תחביר.

LC_COLLATE

collating-symbol <RES-1>
collating-symbol <BLK>
collating-symbol <MIN>
collating-symbol <WIDE>
...
collating-symbol <ARABIC>
collating-symbol <ETHPC>
collating-symbol <OSMANYA>
...
collating-symbol <S1D000>..<S1D35F>
collating-symbol <SFFFF> % Guaranteed largest symbol value. Keep at end of this list
...
collating-element <U0413_0301> from "<U0413><U0301>"
collating-element <U0413_0341> from "<U0413><U0341>"

• איסוף-סמל רושם מחרוזת אוסמניה בטבלת השמות של סולמות
• איסוף-סמל .. רושם רצף של שמות המורכב מקידומת S וסיומת מספרית הקסדצימלית מ 1D000 до 1D35F.
• פ פ פ פ в איסוף-סמל נראה כמו מספר שלם גדול ללא סימן בהקסדצימלי, אבל זה רק שם שעשוי להיראות כמו
• שם פירושו נקודת קוד בקידוד UCS-4
• אלמנט איסוף מ " " רושם שם חדש לזוג נקודות Unicode.

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

% Symbolic weight assignments

% Third-level weight assignments
<RES-1>
<BLK>
<MIN>
<WIDE>
...
% Second-level weight assignments
<BASE>
<LOWLINE> % COMBINING LOW LINE
<PSILI> % COMBINING COMMA ABOVE
<DASIA> % COMBINING REVERSED COMMA ABOVE
...
% First-level weight assignments
<S0009> % HORIZONTAL TABULATION 
<S000A> % LINE FEED
<S000B> % VERTICAL TABULATION
...
<S0434> % CYRILLIC SMALL LETTER DE
<S0501> % CYRILLIC SMALL LETTER KOMI DE
<S0452> % CYRILLIC SMALL LETTER DJE
<S0503> % CYRILLIC SMALL LETTER KOMI DJE
<S0453> % CYRILLIC SMALL LETTER GJE
<S0499> % CYRILLIC SMALL LETTER ZE WITH DESCENDER
<S0435> % CYRILLIC SMALL LETTER IE
<S04D7> % CYRILLIC SMALL LETTER IE WITH BREVE
<S0454> % CYRILLIC SMALL LETTER UKRAINIAN IE
<S0436> % CYRILLIC SMALL LETTER ZHE

לבסוף, טבלת המשקולות בפועל.

קטע המשקולות מוקף בשורות מילות מפתח order_start и order_end. אפשרויות נוספות order_start לקבוע באיזה כיוון שורות נסרקות בכל רמת השוואה. הגדרת ברירת המחדל היא קָדִימָה. גוף הקטע מורכב משורות המכילות את קוד הסמל ואת ארבעת משקליו. קוד התו יכול להיות מיוצג על ידי התו עצמו, נקודת קוד או שם סמלי שהוגדר קודם לכן. ניתן לתת משקלים גם לשמות סמליים, לנקודות קוד או לסמלים עצמם. אם נעשה שימוש בנקודות קוד או תווים, משקלן זהה לערך המספרי של נקודת הקוד (מיקום בטבלת Unicode). תווים שלא צוינו במפורש (כפי שהבנתי) נחשבות למוקצות לטבלה עם משקל ראשי התואם את המיקום בטבלת Unicode. ערך משקל מיוחד להתעלם פירושו שמתעלמים מהסמל ברמת ההשוואה המתאימה.

כדי להדגים את מבנה המאזניים, בחרתי שלושה שברים ברורים למדי:

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

order_start forward;forward;forward;forward,position
<U0000> IGNORE;IGNORE;IGNORE;IGNORE % NULL (in 6429)
<U0001> IGNORE;IGNORE;IGNORE;IGNORE % START OF HEADING (in 6429)
<U0002> IGNORE;IGNORE;IGNORE;IGNORE % START OF TEXT (in 6429)
...
<U0033> <S0033>;<BASE>;<MIN>;<U0033> % DIGIT THREE
<UFF13> <S0033>;<BASE>;<WIDE>;<UFF13> % FULLWIDTH DIGIT THREE
<U2476> <S0033>;<BASE>;<COMPAT>;<U2476> % PARENTHESIZED DIGIT THREE
<U248A> <S0033>;<BASE>;<COMPAT>;<U248A> % DIGIT THREE FULL STOP
<U1D7D1> <S0033>;<BASE>;<FONT>;<U1D7D1> % MATHEMATICAL BOLD DIGIT THREE
...
<U0430> <S0430>;<BASE>;<MIN>;<U0430> % CYRILLIC SMALL LETTER A
<U0410> <S0430>;<BASE>;<CAP>;<U0410> % CYRILLIC CAPITAL LETTER A
<U04D1> <S04D1>;<BASE>;<MIN>;<U04D1> % CYRILLIC SMALL LETTER A WITH BREVE
<U0430_0306> <S04D1>;<BASE>;<MIN>;<U04D1> % CYRILLIC SMALL LETTER A WITH BREVE
...
<U0431> <S0431>;<BASE>;<MIN>;<U0431> % CYRILLIC SMALL LETTER BE
<U0411> <S0431>;<BASE>;<CAP>;<U0411> % CYRILLIC CAPITAL LETTER BE
<U0432> <S0432>;<BASE>;<MIN>;<U0432> % CYRILLIC SMALL LETTER VE
<U0412> <S0432>;<BASE>;<CAP>;<U0412> % CYRILLIC CAPITAL LETTER VE
...
order_end

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

<U0020> IGNORE;IGNORE;IGNORE;<U0020> % SPACE
<U0021> IGNORE;IGNORE;IGNORE;<U0021> % EXCLAMATION MARK
<U0022> IGNORE;IGNORE;IGNORE;<U0022> % QUOTATION MARK
...

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

АбакановМихаилмаляр
ЁлкинаЭллакрановщица
ИвановаАлламаляр
ИвановАндрейслесарь

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

בעת הגדרת משתנה LC_COLLATE=C נטען טבלה מיוחדת המציינת השוואה של בתים-בתים

static const uint32_t collseqwc[] =
{
  8, 1, 8, 0x0, 0xff,
  /* 1st-level table */
  6 * sizeof (uint32_t),
  /* 2nd-level table */
  7 * sizeof (uint32_t),
  /* 3rd-level table */
  L'x00', L'x01', L'x02', L'x03', L'x04', L'x05', L'x06', L'x07',
  L'x08', L'x09', L'x0a', L'x0b', L'x0c', L'x0d', L'x0e', L'x0f',

...
  L'xf8', L'xf9', L'xfa', L'xfb', L'xfc', L'xfd', L'xfe', L'xff'
};

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

טקסט וטבלאות בינאריות

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

קבוצה localdef מקבל כפרמטרים קובץ עם טבלת מאפיינים לאומיים (אפשרות -i), שבו כל התווים מיוצגים על ידי נקודות Unicode, וקובץ התאמה בין נקודות Unicode ותווים של קידוד ספציפי (אפשרות -f). כתוצאה מהעבודה, נוצרים קבצים בינאריים עבור המקום עם השם שצוין בפרמטר האחרון.

גליבק תומך בשני פורמטים של קבצים בינאריים: "מסורתי" ו"מודרני".

הפורמט המסורתי אומר ששם המקום הוא השם של ספריית המשנה ב /usr/lib/locale/. ספריית משנה זו מאחסנת קבצים בינאריים LC_COLLATE, LC_CTYPE, LC_TIME וכולי. קוֹבֶץ LC_IDENTIFICATION מכיל את השם הרשמי של המקום (שעשוי להיות שונה משם הספרייה) והערות.

הפורמט המודרני כולל אחסון כל האזורים בארכיון אחד /usr/lib/locale/locale-archive, אשר ממופה לזיכרון הוירטואלי של כל התהליכים המשתמשים glibc. שם המקום בפורמט המודרני כפוף לקנוניזציה מסוימת - רק מספרים ואותיות מופחתים לאותיות קטנות נשארות בשמות הקידוד. כך ru_RU.KOI8-R, יישמר בשם ru_RU.koi8r.

קבצי קלט מתבצעים בחיפוש בספרייה הנוכחית, כמו גם בספריות /usr/share/i18n/locales/ и /usr/share/i18n/charmaps/ עבור קבצים CTT וקבצי קידוד, בהתאמה.

למשל, הפקודה

localedef -i ru_RU -f MAC-CYRILLIC ru_RU.MAC-CYRILLIC

ירכיב את הקובץ /usr/share/i18n/locales/ru_RU באמצעות קובץ קידוד /usr/share/i18n/charmaps/MAC-CYRILLIC.gz ושמור את התוצאה ב /usr/lib/locale/locale-archive תחת השם ru_RU.maccyrillic

אם תגדיר את המשתנה LANG = en_US.UTF-8 то glibc יחפש קבצים בינאריים מקומיים ברצף הבא של קבצים וספריות:

/usr/lib/locale/locale-archive
/usr/lib/locale/en_US.UTF-8/
/usr/lib/locale/en_US/
/usr/lib/locale/enUTF-8/
/usr/lib/locale/en/

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

אתה יכול להציג את רשימת המקומות הקומפיליים עם הפקודה אזור - א.

הכנת טבלת ההשוואה שלך

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

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

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

העתקתי גרסאות חדשות של הקבצים iso14651_t1_common и ru_RU מהמאגר glibc לספריית הבית שלי ~/.local/share/i18n/locales/ וערכת מעט את הקטע LC_COLLATE в ru_RU. גרסאות חדשות של קבצים תואמות לחלוטין לגרסה שלי glibc. אם תרצו להשתמש בגרסאות ישנות יותר של קבצים, תצטרכו לשנות את השמות הסמליים ואת המקום בו מתחילה ההחלפה בטבלה.

LC_COLLATE
% Copy the template from ISO/IEC 14651
copy "iso14651_t1"
reorder-after <U000D>
<U0020> <S0020>;<BASE>;<MIN>;<U0020> % SPACE
<U0021> <S0021>;<BASE>;<MIN>;<U0021> % EXCLAMATION MARK
<U0022> <S0022>;<BASE>;<MIN>;<U0022> % QUOTATION MARK
...
<U007D> <S007D>;<BASE>;<MIN>;<U007D> % RIGHT CURLY BRACKET
<U007E> <S007E>;<BASE>;<MIN>;<U007E> % TILDE
reorder-end
END LC_COLLATE

למעשה, יהיה צורך לשנות את השדות ב LC_IDENTIFICATION כדי שיצביעו על המקום ru_MY, אבל בדוגמה שלי זה לא היה נדרש, מכיוון שלא הכללת את הארכיון מהחיפוש אחר מקומות locale-archive.

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

$> I18NPATH=~/.local/share/i18n localedef -i ru_RU -f UTF-8 ~/.local/lib/locale/ru_MY.UTF-8

POSIX מניח שב שפה אתה יכול לכתוב נתיבים מוחלטים לספריות עם קבצי מקומיים, החל בקו נטוי קדימה, אבל glibc в לינוקס כל הנתיבים נספרים מספריית הבסיס, אותה ניתן לעקוף באמצעות משתנה LOCPATH. אחרי ההתקנה LOCPATH=~/.local/lib/locale/ כל הקבצים הקשורים ללוקליזציה יחפשו רק בתיקייה שלי. ארכיון של מקומות עם ערכת המשתנים LOCPATH התעלמו.

הנה המבחן המכריע:

$> LANG=ru_MY.UTF-8 LOCPATH=~/.local/lib/locale/ sort buhg.txt
Абаканов Михаил;маляр
Ёлкина Элла;крановщица
Иванов Андрей;слесарь
Иванова Алла;адвокат

הידד! עשינו זאת!

עבודה באג

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

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

וגם התוכנית sort והתוכנית להצטרף השתמש באותן פונקציות השוואת מחרוזות מ glibc. איך זה קרה להצטרף נתן שגיאת מיון בשורות שממוינות לפי הפקודה sort במקום en_US.UTF-8? התשובה פשוטה: sort משווה את כל המחרוזת, ו להצטרף משווה רק את המפתח, שהוא כברירת מחדל את תחילת המחרוזת עד לתו הרווח הראשון. בדוגמה שלי, זה הביא להודעת שגיאה מכיוון שהמיון של המילים הראשונות בשורות לא תאם את המיון של השורות השלמות.

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

$> sort -t ; -k 1 buhg.txt > buhg.srt
$> sort -t ; -k 1 mail.txt > mail.srt
$> join -t ; buhg.srt mail.srt > result

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

אגב, יש עוד תקלה קטנה שקשורה לחוסר נגישות של מקומות מקומפלים. קְבוּצָה LOCPATH=/tmp locale -a ייתן רשימה של כל האזורים ב locale-archive, אבל עם ערכת המשתנים LOCPATH עבור כל התוכניות (כולל המרבית אזור) אזורים אלה לא יהיו זמינים.

$> LOCPATH=/tmp locale -a | grep en_US
locale: Cannot set LC_CTYPE to default locale: No such file or directory
locale: Cannot set LC_MESSAGES to default locale: No such file or directory
locale: Cannot set LC_COLLATE to default locale: No such file or directory
en_US
en_US.iso88591
en_US.iso885915
en_US.utf8

$> LC_COLLATE=en_US.UTF-8 sort --debug
sort: using ‘en_US.UTF-8’ sorting rules

$> LOCPATH=/tmp LC_COLLATE=en_US.UTF-8 sort --debug
sort: using simple byte comparison

מסקנה

אם אתה מתכנת שרגיל לחשוב שמחרוזות הן קבוצה של בתים, אז הבחירה שלך LC_COLLATE=C.

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

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

תזכור

דוח מס' 10 אלגוריתם איסוף Unicode

משקלי תווים ב-unicode.org

המחלקה לטיפול נמרץ - הטמעת ספריה לעבודה עם Unicode מ-IBM.

מבחן מיון באמצעות המחלקה לטיפול נמרץ

הדמות שוקללת פנימה ISO 14651

תיאור פורמט הקובץ עם סולמות ISO 14652

דיון על השוואת מחרוזות ב glibc

מקור: www.habr.com