مقدمة

بدأ كل شيء بنص قصير كان من المفترض أن يجمع المعلومات حول العناوين بريد الإلكتروني تم الحصول عليها من قائمة مستخدمي القائمة البريدية مع مناصب موظفين تم الحصول عليها من قاعدة بيانات الموارد البشرية. تم تصدير كلتا القائمتين إلى ملفات نصية Unicode. UTF-8 وتخزينها بنهايات سطر Unix.

محتوى mail.txt

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

محتوى buhg.txt

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

للدمج ، تم فرز الملفات بواسطة أمر Unix sort وتقديمها إلى مدخلات برنامج Unix الانضمام، والتي انتهت بشكل غير متوقع بالخطأ:

$> 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
Абаканов Михаил;маляр
Ёлкина Элла;крановщица
Иванова Алла;маляр
Иванов Андрей;слесарь

يبدو وكأنه خلل في الفرز في Unicode أو مظهر من مظاهر النسوية في خوارزمية الفرز. الأول ، بالطبع ، معقول أكثر.

دعونا نؤجله الآن الانضمام والتركيز على 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

مرة أخرى ، لم يتغير شيء.

لا يمكن فعل أي شيء ، عليك البحث عن حل على الإنترنت. لا يوجد شيء مباشر حول الألقاب الروسية ، ولكن هناك أسئلة حول شذوذ الفرز الأخرى. على سبيل المثال ، إليك مشكلة: يعامل نظام unix sort أحرف "-" (الشرطة) على أنها غير مرئية. باختصار ، يتم ترتيب السلاسل "ab" و "aa" و "ac" كـ "aa" و "ab" و "ac".

الجواب قياسي في كل مكان: استخدم لغة المبرمج "C" وستكون سعيدا. نحاول:

$> 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

عملت دون أخطاء ، كما وعدت من قبل الإنترنت. وهذا على الرغم من Yolkina في السطر الأول.

يبدو أن المشكلة قد تم حلها ، ولكن في حالة حدوث ذلك ، دعنا نجرب ترميزًا روسيًا آخر - Windows CP1251:

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

نتيجة الفرز ، بشكل غريب بما فيه الكفاية ، سوف تتطابق مع اللغة "C"، والمثال كله ، وفقا لذلك ، يمر دون أخطاء. نوع من الصوفي.

لا أحب التصوف في البرمجة لأنه عادة ما يخفي الأخطاء. سيتعين علينا أن نكون جادين بشأن كيفية عمله. sort وماذا يؤثر LC_COLLATE .

في النهاية سأحاول الإجابة على الأسئلة:

لماذا تم فرز ألقاب النساء بشكل غير صحيح
لماذا LANG = ru_RU.CP1251 تبين أن يكون معادلا لانج = ج
لماذا انت sort и الانضمام أفكار مختلفة حول ترتيب السلاسل المصنفة
لماذا توجد أخطاء في كل أمثلتي
أخيرًا كيفية فرز السلاسل حسب رغبتك

الفرز في Unicode

ستكون المحطة الأولى هي التقرير الفني رقم 10 بعنوان خوارزمية ترتيب Unicode على الانترنت unicode.org. يحتوي التقرير على الكثير من التفاصيل الفنية ، لذلك سأسمح لي بتقديم ملخص للأفكار الرئيسية.

الترتيب - "مقارنة" السلاسل هي أساس أي خوارزمية فرز. قد تختلف الخوارزميات نفسها ("فقاعة" ، "دمج" ، "سريعة") ، لكنها ستستخدم جميعًا مقارنة بين زوج من السلاسل لتحديد ترتيبها.

يعتبر فرز السلاسل بلغة طبيعية مشكلة صعبة نوعًا ما. حتى في أبسط الترميزات أحادية البايت ، فإن ترتيب الحروف في الأبجدية ، حتى لو كان مختلفًا نوعًا ما عن الأبجدية اللاتينية الإنجليزية ، لن يتطابق مع ترتيب القيم الرقمية التي يتم بها ترميز هذه الأحرف. لذلك في الأبجدية الألمانية الحرف Ö يقف بين О и P، وفي الترميز CP850 تقع بين ÿ и Ü.

يمكنك محاولة التجريد بعيدًا عن الترميز المحدد والنظر في الأحرف "المثالية" المرتبة بترتيب ما ، كما هو الحال في Unicode. ترميزات Utf8, Utf16 أو بايت واحد KOI8-R (إذا كانت هناك حاجة إلى مجموعة فرعية محدودة من Unicode) فسوف تعطي تمثيلات رقمية مختلفة للأحرف ، ولكنها تشير إلى نفس عناصر الجدول الأساسي.

اتضح أنه حتى لو قمنا ببناء جدول رموز من البداية ، فلا يمكننا تعيين ترتيب رمز عام له. في الأبجديات الوطنية المختلفة التي تستخدم نفس الأحرف ، قد يختلف ترتيب هذه الأحرف. على سبيل المثال ، باللغة الفرنسية Æ سيتم التعامل معها على أنها ضمد ويتم فرزها كسلسلة AE. باللغة النرويجية Æ سيكون حرفًا منفصلاً يقع بعده Z. بالمناسبة ، بصرف النظر عن الحروف المركبة مثل Æ هناك حروف مكتوبة بعدة أحرف. لذلك يوجد في الأبجدية التشيكية حرف Chالذي يقف بين H и I.

بالإضافة إلى الاختلاف في الحروف الهجائية ، هناك تقاليد وطنية أخرى تؤثر على الفرز. على وجه الخصوص ، السؤال الذي يطرح نفسه: في أي ترتيب يجب أن تظهر الكلمات المكونة من أحرف كبيرة وصغيرة في القاموس؟ أيضًا ، يمكن أن يتأثر الفرز بخصائص استخدام علامات الترقيم. في اللغة الإسبانية ، توضع علامة استفهام مقلوبة في بداية جملة الاستفهام (هل تحب الموسيقى؟). في هذه الحالة ، من الواضح أنه لا ينبغي تجميع جمل الاستفهام في مجموعة منفصلة خارج الأبجدية ، ولكن كيف تفرز الأسطر بعلامات ترقيم مختلفة؟

لن أسهب في فرز الأوتار بلغات مختلفة تمامًا عن اللغات الأوروبية. لاحظ أن اللغات التي تُكتب من اليمين إلى اليسار أو من أعلى إلى أسفل تميل إلى تخزين الأحرف في سطور بترتيب القراءة ، وحتى النصوص غير الأبجدية لها طريقتها الخاصة في ترتيب الأسطر حرفًا بحرف. على سبيل المثال ، يمكن ترتيب الحروف الهيروغليفية حسب النمط (مفاتيح الأحرف الصينية) أو بالنطق. كيف يجب طلب الرموز التعبيرية ، ليس لدي أي فكرة بصراحة ، لكن يمكنك التفكير في شيء لهم.

بناءً على الميزات المذكورة أعلاه ، تمت صياغة المتطلبات الرئيسية لمقارنة السلاسل بناءً على جداول Unicode:

لا تعتمد مقارنة السلاسل على موضع الأحرف في جدول التعليمات البرمجية ؛
يتم تقليل تسلسل الأحرف التي تشكل حرفًا واحدًا إلى الشكل المتعارف عليه (A + الدائرة العلوية هي نفسها Å);
عند مقارنة السلاسل ، يتم اعتبار الحرف في سياق سلسلة ، وإذا لزم الأمر ، يتم دمجه مع الجيران في وحدة واحدة للمقارنة (Ch باللغة التشيكية) أو مقسمة إلى عدة (Æ بالفرنسية)؛
يجب تكوين جميع الميزات الوطنية (الأبجدية ، والأحرف الكبيرة / الصغيرة ، وعلامات الترقيم ، وترتيب أنواع الكتابة) حتى التعيين اليدوي للترتيب (الرموز التعبيرية) ؛
المقارنة مهمة ليس فقط للفرز ، ولكن أيضًا في العديد من الأماكن الأخرى ، على سبيل المثال ، لتحديد نطاقات من السلاسل (استبدال {A ... z} في سحق);
يجب أن تكون المقارنة سريعة بما يكفي.

بالإضافة إلى ذلك ، صاغ مؤلفو التقرير خصائص مقارنة لا ينبغي لمطوري الخوارزميات الاعتماد عليها:

يجب ألا تتطلب خوارزمية المقارنة مجموعة أحرف منفصلة لكل لغة (تشترك اللغات الروسية والأوكرانية في معظم الأحرف السيريلية) ؛
يجب ألا تستند المقارنة إلى ترتيب الأحرف في جداول Unicode ؛
يجب ألا يكون وزن السلسلة سمة من سمات السلسلة ، لأن نفس السلسلة في سياقات ثقافية مختلفة يمكن أن يكون لها أوزان مختلفة ؛
يمكن أن تتغير أوزان الصفوف عند الدمج أو الانقسام (من x < y لا يتبع ذلك xz < yz);
تعتبر السلاسل المختلفة التي لها نفس الأوزان متساوية من حيث خوارزمية الفرز. من الممكن إدخال ترتيب إضافي لمثل هذه السلاسل ، ولكنه قد يؤدي إلى تدهور الأداء ؛
يمكن تبديل الصفوف التي لها نفس الأوزان أثناء عمليات الفرز المتكررة. الثبات هو خاصية لخوارزمية فرز معينة ، وليس خاصية خوارزمية مقارنة السلسلة (انظر النقطة السابقة) ؛
قد تتغير قواعد الفرز بمرور الوقت حيث يتم صقل / تغيير الممارسات الثقافية.

يشترط أيضًا أن خوارزمية المقارنة لا تعرف أي شيء عن دلالات السلاسل المعالجة. لذلك ، لا ينبغي مقارنة السلاسل التي تتكون من أرقام فقط كأرقام ، وفي قوائم الأسماء الإنجليزية ، لا ينبغي إزالة المقالة (البيتلز).

من أجل تلبية كل هذه المتطلبات ، تم اقتراح خوارزمية فرز جدولي متعددة المستويات (في الواقع من أربعة مستويات).

في السابق ، تم تحويل الأحرف الموجودة في السلسلة إلى شكل أساسي وتم تجميعها في وحدات مقارنة. يتم تخصيص عدة أوزان لكل وحدة مقارنة تتوافق مع عدة مستويات للمقارنة. أوزان وحدات المقارنة هي عناصر المجموعات المرتبة (في هذه الحالة ، الأعداد الصحيحة) التي يمكن مقارنتها بأكثر أو أقل. معنى خاص تجاهل (0 × 0) يعني أن هذه الوحدة لا تشارك في المقارنة على المستوى المقابل للمقارنة. يمكن تكرار مقارنة السلسلة عدة مرات ، باستخدام أوزان المستويات المناسبة. في كل مستوى ، تتم مقارنة أوزان وحدات المقارنة لسلسلتين بالتتابع مع بعضها البعض.

في التطبيقات المختلفة للخوارزمية للتقاليد الوطنية المختلفة ، قد تختلف قيم المعاملات ، لكن معيار Unicode يتضمن جدول وزن أساسي - "جدول عنصر ترتيب Unicode الافتراضي" (القناة). أريد أن أشير إلى أن تحديد المتغير LC_COLLATE هو في الواقع إشارة إلى اختيار جدول الوزن في دالة مقارنة السلسلة.

معاملات الوزن القناة مرتبة على النحو التالي:

في المستوى الأول ، يتم تقليل جميع الأحرف إلى نفس الحالة ، ويتم تجاهل علامات التشكيل ، ويتم تجاهل علامات الترقيم (وليس جميعها) ؛
في المستوى الثاني ، يتم أخذ علامات التشكيل فقط في الاعتبار ؛
المستوى الثالث هو حالة فقط ؛
في المستوى الرابع ، يتم أخذ علامات الترقيم فقط في الاعتبار.

تتم المقارنة بعدة مسارات: أولاً ، تتم مقارنة معاملات المستوى الأول ؛ إذا كانت الأوزان متطابقة ، تتم إعادة مقارنتها بأوزان المستوى الثاني ؛ ثم ربما الثلث والرابع.

تنتهي المقارنة عندما تحتوي السلاسل على وحدات مقارنة مطابقة بأوزان مختلفة. تعتبر الصفوف التي لها أوزان متساوية في المستويات الأربعة متساوية مع بعضها البعض.

أعطت هذه الخوارزمية (مع مجموعة من التفاصيل الفنية الإضافية) اسمًا للتقرير رقم 10 - خوارزمية ترتيب Unicode (UCA).

هذا هو المكان الذي يصبح فيه سلوك الفرز من مثالنا أكثر وضوحًا. سيكون من الجيد مقارنتها بمعيار Unicode.

لاختبار التطبيقات UCA هناك خاص اختباراستخدام ملف الوزنيدرك القناة. في ملف الأوزان ، يمكنك أن تجد العديد من وسائل التسلية. على سبيل المثال ، هناك ترتيب الماهجونج والدومينو الأوروبية ، بالإضافة إلى ترتيب البدلات في مجموعة أوراق اللعب (الرمز 1F000 و كذلك). يتم وضع بدلات البطاقات وفقًا لقواعد الجسر - PCBT ، والبطاقات الموجودة في الدعوى - في التسلسل T ، 2,3،XNUMX ... K.

التحقق اليدوي من الفرز الصحيح للسلاسل وفقًا لـ القناة سيكون مملاً للغاية ، ولكن لحسن الحظ بالنسبة لنا ، هناك تطبيق مكتبة مرجعية للعمل مع Unicode - "المكونات الدولية لليونيكود"(وحدة العناية المركزة).

على موقع هذه المكتبة ، تم تطويرها في IBM، هناك صفحات تجريبية ، بما في ذلك صفحة خوارزمية مقارنة السلسلة. ندخل سلاسل الاختبار الخاصة بنا بالإعدادات الافتراضية ، وها نحن نحصل على الترتيب الروسي المثالي.

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

بالمناسبة ، الموقع وحدة العناية المركزة يمكنك العثور على تنقيح لخوارزمية المقارنة عند معالجة علامات الترقيم. في الأمثلة الأسئلة الشائعة حول التجميع يتم تجاهل الفاصلة العليا والواصلة.

ساعدنا Unicode ، لكن ابحث عن أسباب السلوك الغريب sort в لينكس سوف تضطر إلى الذهاب إلى مكان آخر.

الفرز في glibc

نظرة سريعة على رموز مصدر الأداة sort من أدوات جنو الأساسية أظهر أنه في الأداة نفسها ، يتم تقليل الترجمة إلى طباعة القيمة الحالية للمتغير LC_COLLATE عند التشغيل في وضع التصحيح:

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

يتم إجراء مقارنة السلاسل بواسطة الوظيفة القياسية نزهة، مما يعني أن كل شيء مثير للاهتمام موجود في المكتبة سي العمومية.

في ويكي مشروع سي العمومية مخصصة لمقارنة السلسلة فقرة واحدة. من هذه الفقرة يمكن فهم ذلك سي العمومية يعتمد الفرز على الخوارزمية المعروفة لدينا بالفعل UCA (خوارزمية ترتيب Unicode) و / أو على مستوى قريب منه إعتماد ISO-14651 (ترتيب ومقارنة السلسلة الدولية). فيما يتعلق بأحدث المعايير ، تجدر الإشارة إلى ذلك في الموقع معايير iso.org إعتماد ISO-14651 أعلن رسميًا للجمهور ، لكن الرابط المقابل يؤدي إلى صفحة غير موجودة. تقدم Google عدة صفحات بها روابط لمواقع رسمية تعرض شراء نسخة إلكترونية من المعيار مقابل مائة يورو ، ولكن في الصفحة الثالثة أو الرابعة من نتائج البحث توجد أيضًا روابط مباشرة إلى PDF. بشكل عام ، لا يختلف المعيار عمليًا عن UCA، لكنها تبدو مملة أكثر لأنها لا تحتوي على أمثلة حية للسمات الوطنية لفرز الأوتار.

المعلومات الأكثر إثارة للاهتمام ويكي كان هناك ارتباط إلى bugtracker مع مناقشة تنفيذ مقارنة السلاسل في سي العمومية. يمكن أن نرى من المناقشة أن سي العمومية لمقارنة السلسلة المستخدمة ISOطاولة شنايا جدول القوالب المشترك (CTT) ، يمكن العثور على عنوانها في التطبيق A معيار إعتماد ISO-14651. بين عامي 2000 و 2015 هذا الجدول في سي العمومية لم يكن لديه مشرف وكان مختلفًا تمامًا (على الأقل ظاهريًا) عن الإصدار الحالي من المعيار. من عام 2015 إلى عام 2018 ، كان هناك تعديل للإصدار الجديد من الجدول ، وفي الوقت الحالي لديك فرصة للقاء في الحياة الواقعية كإصدار جديد من الجدول (CentOS 8) والقديم (CentOS 7).

الآن بعد أن أصبح لدينا جميع المعلومات حول الخوارزمية والجداول المساعدة ، يمكننا العودة إلى المشكلة الأصلية وفهم كيفية فرز السلاسل بشكل صحيح في اللغة الروسية.

إسو شنومكس / شنومكس

الكود المصدري للجدول الذي نهتم به 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 من مجموعة مفتوحة. كبديل لقراءة المعيار ، يمكنك دراسة النصوص المصدر للوظيفة ترتيب_القراءة в glibc / locale / البرامج / ld-collate.c.

تبدو بنية الملف كما يلي:

بشكل افتراضي ، يتم استخدام الحرف كحرف هروب ، ونهاية السطر بعد الحرف # عبارة عن تعليق. يمكن إعادة تعريف كلا الرمزين ، وذلك في النسخة الجديدة من الجدول:

escape_char /
comment_char %

سيحتوي الملف على رموز مميزة بالتنسيق أو (أين x هو رقم سداسي عشري). هذا هو التمثيل السداسي العشري لنقاط رمز Unicode في الترميز يو سي إس-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.
FFFF в رمز الترتيب يشبه عددًا صحيحًا كبيرًا بدون إشارة بالنظام الست عشري ، ولكن إنه مجرد اسم قد يبدو
اسم يعني نقطة رمز في الترميز يو سي إس-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، والتي يتم تعيينها إلى الذاكرة الافتراضية لجميع العمليات باستخدام سي العمومية. يخضع اسم المكان في التنسيق الحديث لبعض تحديد العنوان المتعارف عليه - تظل الأرقام والأحرف الصغيرة فقط في اسم الترميز. لذا ar_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 تحت الاسم en_RU.maccyrillic

إذا قمت بتعيين متغير LANG = en_US.UTF-8 أن سي العمومية سيبحث عن ثنائيات الإعدادات المحلية في التسلسل التالي للملفات والأدلة:

/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 من المستودع سي العمومية إلى الدليل الرئيسي الخاص بك ~ / .local / share / i18n / locales / وقم بتحرير القسم قليلاً LC_COLLATE в ru_RU. الإصدارات الجديدة من الملفات متوافقة تمامًا مع الإصدار الخاص بي سي العمومية. إذا كنت تريد استخدام إصدارات أقدم من الملفات ، فسيتعين عليك تغيير الأسماء الرمزية والمكان الذي يبدأ فيه الاستبدال في الجدول.

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 بحيث يشيرون إلى اللغة ar_MY، ولكن في المثال الخاص بي لم يكن هذا مطلوبًا ، لأنني استبعدت الأرشيف من البحث عن اللغات أرشيف اللغة.

أن localdef عملت مع الملفات في مجلدي من خلال متغير I18NPAT يمكنك إضافة دليل إضافي للبحث عن ملفات الإدخال ، ويمكن تحديد دليل حفظ الثنائيات كمسار بشرطة مائلة:

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

POSIX يقترح أن في لانج يمكنك كتابة مسارات مطلقة إلى الدلائل بملفات محلية ، بدءًا بشرطة مائلة للأمام ، ولكن سي العمومية в لينكس يتم عد جميع المسارات من الدليل الأساسي ، والذي يمكن تجاوزه عبر متغير لوكباث. بعد التثبيت LOCPATH = ~ / .local / lib / locale / سيتم البحث في جميع الملفات المتعلقة بالترجمة في مجلدي فقط. أرشيف الإعدادات المحلية عند تعيين المتغير لوكباث تجاهله.

ها هو الاختبار النهائي:

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

الصيحة! لقد فعلناها!

بعض الأخطاء

لقد أجبت بالفعل على الأسئلة المتعلقة بفرز السلاسل ، التي طرحت في البداية ، ولكن لا يزال هناك سؤالان حول الأخطاء - المرئية وغير المرئية.

دعنا نعود إلى المشكلة الأصلية.

والبرنامج sort والبرنامج الانضمام استخدام نفس وظائف مقارنة السلاسل من سي العمومية. كيف حدث ذلك الانضمام أعطى خطأ في الفرز على الأسطر التي تم فرزها بواسطة الأمر sort في اللغة en_US.UTF-8؟ الجواب بسيط: sort يقارن السلسلة بأكملها ، و الانضمام يقارن المفتاح فقط ، والذي يكون افتراضيًا بداية السلسلة حتى الحرف الأول للمسافة البيضاء. في المثال الخاص بي ، أدى ذلك إلى ظهور رسالة خطأ لأن فرز الكلمات الأولى في السطور لم يتطابق مع فرز الأسطر الكاملة.

لغة "C" يضمن أنه في السلاسل التي تم فرزها ، سيتم أيضًا فرز السلاسل الفرعية البادئة حتى المساحة الأولى ، لكن هذا يخفي الخطأ فقط. يمكنك التقاط مثل هذه البيانات (الأشخاص الذين لديهم نفس الاسم الأخير ، ولكن بأسماء مختلفة) والتي ، بدون رسالة خطأ ، من شأنها أن تعطي نتيجة غير صحيحة لدمج الملفات. إذا كنا نريد أن الانضمام أسطر الملفات المدمجة بالاسم الكامل ، فإن الطريقة الصحيحة هي تحديد فاصل الحقل بشكل صريح والفرز حسب حقل المفتاح ، وليس حسب السطر بأكمله. في هذه الحالة ، سيعمل الدمج أيضًا بشكل صحيح ولن تكون هناك أخطاء في أي لغة:

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

تم تنفيذ مثال مشفر بنجاح CP1251 يحتوي على خطأ آخر. الحقيقة هي أنه في جميع التوزيعات المعروفة لي لينكس حزم مفقودة لغة مترجمة ar_RU.CP1251. إذا لم يتم العثور على اللغة المترجمة ، ثم sort يستخدم بصمت مقارنة بايت ، وهو ما لاحظناه.

بالمناسبة ، هناك خلل صغير آخر مرتبط بعدم إمكانية الوصول إلى المواقع المترجمة. فريق LOCPATH = / tmp locale -a سيعرض قائمة بجميع اللغات في أرشيف اللغة، ولكن مع مجموعة المتغيرات لوكباث لجميع البرامج (بما في ذلك معظم محلي) لن تكون هذه اللغات متاحة.

$> 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.

إذا كنت لغويًا أو مترجمًا للقاموس ، فمن الأفضل أن تقوم بتجميع لغتك.

إذا كنت مستخدمًا بسيطًا ، فأنت بحاجة فقط إلى التعود على حقيقة أن الأمر ls -a يطبع الملفات بدءًا من نقطة تتخللها ملفات تبدأ بحرف ، و قائد منتصف الليل، الذي يستخدم وظائفه الداخلية لفرز الأسماء ، ينقل الملفات التي تبدأ بنقطة إلى مقدمة القائمة.