معرفی

همه چیز با یک اسکریپت کوتاه شروع شد که قرار بود اطلاعات آدرس را ترکیب کند پست الکترونیک کارمندانی که از لیست کاربران لیست پستی به دست آمده اند، با موقعیت های کارمندی که از پایگاه داده بخش منابع انسانی به دست آمده اند. هر دو لیست به فایل های متنی یونیکد صادر شدند UTF-8 و با انتهای خط یونیکس ذخیره شد.

محتوا mail.txt

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

محتوا buhg.txt

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

برای ادغام، فایل ها با دستور یونیکس مرتب شدند نوع و به ورودی برنامه یونیکس ارسال شد پیوستن، که به طور غیرمنتظره ای با یک خطا ناموفق بود:

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

به نظر می رسد یک اشکال مرتب سازی در یونیکد یا شبیه تجلی فمینیسم در الگوریتم مرتب سازی است. البته اولی قابل قبول تر است.

فعلاً آن را به تعویق بیندازیم پیوستن و تمرکز کنید نوع. بیایید سعی کنیم با استفاده از پوک علمی مشکل را حل کنیم. ابتدا بیایید محلی را از آن تغییر دهیم 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" مرتب شده اند.

پاسخ در همه جا استاندارد است: از محلی برنامه نویس استفاده کنید "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

همانطور که اینترنت وعده داده بود بدون خطا کار کرد. و این با وجود یولکینا در خط اول.

به نظر می رسد مشکل حل شده است، اما در هر صورت، بیایید یک رمزگذاری روسی دیگر - ویندوز را امتحان کنیم CP1251:

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

نتیجه مرتب سازی، به اندازه کافی عجیب، با منطقه منطبق خواهد شد "C"، و کل مثال، بر این اساس، بدون خطا اجرا می شود. نوعی عرفان.

من از عرفان در برنامه نویسی خوشم نمی آید چون معمولا اشتباهات را می پوشاند. ما باید به طور جدی بررسی کنیم که چگونه کار می کند. نوع و چه تاثیری دارد؟ LC_COLLATE .

در پایان سعی می کنم به سوالات زیر پاسخ دهم:

چرا نام خانوادگی زنانه اشتباه مرتب شده است؟
چرا LANG=ru_RU.CP1251 معادل شد LANG=C
چرا انجام دهید نوع и پیوستن ایده های مختلف در مورد ترتیب رشته های مرتب شده
چرا در همه مثال های من خطا وجود دارد؟
در نهایت چگونه رشته ها را به دلخواه مرتب کنیم

مرتب سازی در یونیکد

اولین توقف گزارش فنی شماره 10 با عنوان خواهد بود الگوریتم ترکیب یونیکد آنلاین unicode.org. این گزارش حاوی جزئیات فنی زیادی است، بنابراین اجازه دهید خلاصه ای از ایده های اصلی را ارائه دهم.

تلفیق - "مقایسه" رشته ها اساس هر الگوریتم مرتب سازی است. خود الگوریتم ها ممکن است متفاوت باشند ("حباب"، "ادغام"، "سریع")، اما همه آنها از مقایسه یک جفت رشته برای تعیین ترتیب ظاهر شدنشان استفاده می کنند.

مرتب سازی رشته ها در زبان طبیعی یک مشکل نسبتاً پیچیده است. حتی در ساده‌ترین رمزگذاری‌های تک بایتی، ترتیب حروف در الفبا، حتی به نحوی متفاوت از الفبای لاتین انگلیسی، دیگر با ترتیب مقادیر عددی که این حروف با آن کدگذاری می‌شوند، مطابقت نخواهد داشت. بنابراین در الفبای آلمانی حرف Ö بین می ایستد О и P، و در رمزگذاری CP850 او بین می رود ÿ и Ü.

می توانید سعی کنید از یک رمزگذاری خاص انتزاعی کنید و حروف "ایده آل" را در نظر بگیرید که به ترتیبی مرتب شده اند، همانطور که در یونیکد انجام می شود. رمزگذاری ها UTF8, UTF16 یا یک بایتی KOI8-R (اگر زیر مجموعه محدودی از یونیکد مورد نیاز باشد) نمایش های عددی متفاوتی از حروف ارائه می دهد، اما به همان عناصر جدول پایه اشاره می کند.

معلوم می شود که حتی اگر یک جدول نماد را از ابتدا بسازیم، نمی توانیم یک نظم نماد جهانی را به آن اختصاص دهیم. در الفبای ملی مختلف که از حروف یکسان استفاده می کنند، ممکن است ترتیب این حروف متفاوت باشد. مثلا در زبان فرانسه Æ لیگاتور در نظر گرفته می شود و به عنوان یک رشته مرتب می شود AE. در نروژی Æ یک نامه جداگانه خواهد بود که بعد از آن قرار دارد Z. به هر حال، علاوه بر لیگاتور مانند Æ حروفی با چند علامت نوشته شده است. بنابراین در الفبای چک یک حرف وجود دارد Ch، که بین H и I.

علاوه بر تفاوت در حروف الفبا، سنت های ملی دیگری نیز وجود دارد که بر مرتب سازی تأثیر می گذارد. به طور خاص، این سؤال مطرح می شود: کلمات متشکل از حروف بزرگ و کوچک به چه ترتیبی باید در فرهنگ لغت ظاهر شوند؟ مرتب سازی ممکن است تحت تأثیر استفاده از علائم نگارشی قرار گیرد. در زبان اسپانیایی از علامت سوال معکوس در ابتدای جمله پرسشی استفاده می شود.موسیقی دوست دارید؟). در این صورت، بدیهی است که جملات پرسشی را نباید در یک خوشه جداگانه در خارج از حروف الفبا دسته بندی کرد، اما چگونه می توان خطوط را با سایر علائم نگارشی مرتب کرد؟

من به مرتب کردن رشته ها در زبان های بسیار متفاوت از زبان های اروپایی نمی پردازم. توجه داشته باشید که در زبان‌هایی با جهت نوشتن از راست به چپ یا از بالا به پایین، نویسه‌ها در خطوط به احتمال زیاد به ترتیب خواندن ذخیره می‌شوند و حتی سیستم‌های نوشتاری غیرالفبایی روش‌های خاص خود را برای ترتیب خطوط کاراکتر به کاراکتر دارند. . به عنوان مثال، هیروگلیف ها را می توان بر اساس سبک مرتب کرد (کلیدهای حروف چینی) یا با تلفظ. صادقانه بگویم، من نمی‌دانم ایموجی‌ها چگونه باید چیده شوند، اما شما هم می‌توانید چیزی برای آن‌ها بسازید.

بر اساس ویژگی های ذکر شده در بالا، الزامات اساسی برای مقایسه رشته ها بر اساس جداول یونیکد فرموله شد:

مقایسه رشته ها به موقعیت کاراکترها در جدول کد بستگی ندارد.
دنباله ای از شخصیت ها که یک کاراکتر واحد را تشکیل می دهند به شکل متعارف کاهش می یابد (A + دایره بالا همان است Å);
هنگام مقایسه رشته ها، یک کاراکتر در زمینه رشته در نظر گرفته می شود و در صورت لزوم با همسایگان آن در یک واحد مقایسه ترکیب می شود.Ch در چک) یا به چندین (Æ به زبان فرانسه)؛
تمام ویژگی‌های ملی (الفبا، حروف بزرگ/کوچک، نشانه‌گذاری، ترتیب انواع نوشتار) باید تا تخصیص دستی سفارش (اموجی) پیکربندی شوند.
مقایسه نه تنها برای مرتب‌سازی، بلکه در بسیاری از مکان‌های دیگر نیز مهم است، به عنوان مثال برای تعیین محدوده ردیف (جایگزینی {A... z} در بر هم زدن);
مقایسه باید نسبتاً سریع انجام شود.

علاوه بر این، نویسندگان گزارش ویژگی های مقایسه ای را فرموله کردند که توسعه دهندگان الگوریتم نباید به آنها اعتماد کنند:

الگوریتم مقایسه نباید به مجموعه ای از کاراکترهای جداگانه برای هر زبان نیاز داشته باشد (زبان های روسی و اوکراینی اکثر کاراکترهای سیریلیک را به اشتراک می گذارند).
مقایسه نباید به ترتیب کاراکترها در جداول یونیکد متکی باشد.
وزن رشته نباید یک ویژگی رشته باشد، زیرا یک رشته در زمینه های فرهنگی مختلف می تواند وزن های متفاوتی داشته باشد.
وزن ردیف می تواند هنگام ادغام یا تقسیم (از x < y از آن پیروی نمی کند xz < yz);
رشته های مختلف با وزن های یکسان از دیدگاه الگوریتم مرتب سازی برابر در نظر گرفته می شوند. معرفی ترتیب اضافی چنین رشته‌هایی ممکن است، اما ممکن است عملکرد را کاهش دهد.
در طول مرتب سازی مکرر، ردیف هایی با وزن های یکسان ممکن است تعویض شوند. استحکام ویژگی یک الگوریتم مرتب‌سازی خاص است و نه ویژگی یک الگوریتم مقایسه رشته‌ای (به پاراگراف قبلی مراجعه کنید).
قوانین مرتب‌سازی ممکن است در طول زمان با اصلاح/تغییر سنت‌های فرهنگی تغییر کنند.

همچنین تصریح شده است که الگوریتم مقایسه چیزی در مورد معنایی رشته های در حال پردازش نمی داند. بنابراین، رشته‌هایی که فقط از ارقام تشکیل شده‌اند نباید به عنوان اعداد مقایسه شوند و در فهرست‌های نام‌های انگلیسی مقاله (بیتلز، The).

به منظور ارضای تمام الزامات مشخص شده، یک الگوریتم مرتب سازی جدول چند سطحی (در واقع چهار سطح) پیشنهاد شده است.

قبلاً کاراکترهای رشته به شکل متعارف کاهش یافته و در واحدهای مقایسه گروه بندی می شوند. به هر واحد مقایسه چندین وزن مربوط به چندین سطح مقایسه اختصاص داده می شود. اوزان واحدهای مقایسه، عناصری از مجموعه‌های مرتب شده (در این مورد، اعداد صحیح) هستند که می‌توان آنها را کم و بیش مقایسه کرد. معنی خاص نادیده گرفته شد (0x0) به این معنی است که در سطح مقایسه مربوطه این واحد در مقایسه دخالت ندارد. مقایسه رشته ها را می توان چندین بار با استفاده از وزن سطوح مربوطه تکرار کرد. در هر سطح، وزن واحدهای مقایسه دو ردیف به ترتیب با یکدیگر مقایسه می شوند.

در پیاده سازی های مختلف الگوریتم برای سنت های ملی مختلف، مقادیر ضرایب ممکن است متفاوت باشد، اما استاندارد یونیکد شامل یک جدول اساسی از وزن ها است - "جدول عناصر دسته بندی پیش فرض یونیکد" (DUCET). من می خواهم توجه داشته باشم که تنظیم متغیر LC_COLLATE در واقع نشانه ای از انتخاب جدول وزن در تابع مقایسه رشته است.

ضرایب وزنی DUCET به شرح زیر ترتیب داده شده است:

در سطح اول، همه حروف به یک مورد کاهش می‌یابند، نشانه‌ها کنار گذاشته می‌شوند، علائم نگارشی (نه همه) نادیده گرفته می‌شوند.
در سطح دوم، فقط نشانه ها در نظر گرفته می شود.
در سطح سوم، تنها مورد در نظر گرفته می شود.
در سطح چهارم، فقط علائم نگارشی در نظر گرفته شده است.

مقایسه در چندین مرحله انجام می شود: ابتدا ضرایب سطح اول مقایسه می شوند. اگر وزن ها منطبق باشند، مقایسه مکرر با وزن های سطح دوم انجام می شود. سپس شاید یک سوم و چهارم.

مقایسه زمانی پایان می‌یابد که سطرها دارای واحدهای مقایسه با وزن‌های مختلف باشند. ردیف هایی که در هر چهار سطح دارای وزن مساوی هستند با یکدیگر برابر در نظر گرفته می شوند.

این الگوریتم (با یک سری جزئیات فنی اضافی) نام گزارش شماره 10 را داد - "الگوریتم مجموعه یونیکد" (ACU).

اینجاست که رفتار مرتب‌سازی از مثال ما کمی واضح‌تر می‌شود. خوب است که آن را با استاندارد یونیکد مقایسه کنید.

برای آزمایش پیاده سازی ها ACU خاص وجود دارد آزمون، استفاده كردن فایل وزن، اجرا می کند DUCET. شما می توانید انواع چیزهای خنده دار را در فایل ترازو پیدا کنید. به عنوان مثال، ترتیب فال ماهجونگ و دومینوی اروپایی، و همچنین ترتیب لباس‌ها در یک دسته کارت (نماد) وجود دارد. 1F000 و بیشتر). کت و شلوارهای کارتی طبق قوانین بریج - PCBT قرار می گیرند و کارت های موجود در کت و شلوار به ترتیب T, 2,3, XNUMX... K قرار می گیرند.

بررسی دستی اینکه ردیف‌ها بر اساس درستی مرتب شده‌اند DUCET بسیار خسته کننده خواهد بود، اما، خوشبختانه برای ما، اجرای نمونه ای از کتابخانه برای کار با یونیکد وجود دارد - "مؤلفه های بین المللی برای یونیکد"(ICU).

در وب سایت این کتابخانه، توسعه یافته در آی بی ام، صفحات نمایشی از جمله وجود دارد صفحه الگوریتم مقایسه رشته ها. ما با تنظیمات پیش‌فرض وارد خطوط آزمایشی خود می‌شویم و ببینید، مرتب‌سازی کامل روسی را دریافت می‌کنیم.

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

به هر حال، وب سایت ICU هنگام پردازش علائم نگارشی می توانید توضیحی درباره الگوریتم مقایسه پیدا کنید. در مثال ها مجموعه سوالات متداول آپستروف و خط فاصله نادیده گرفته می شوند.

یونیکد به ما کمک کرد، اما به دنبال دلایل رفتار عجیب باشید نوع в لینـوکــس باید به جای دیگری برود

مرتب سازی در glibc

مشاهده سریع کدهای منبع ابزار نوع از ابزارهای هسته گنو نشان داد که در خود ابزار، محلی سازی به چاپ مقدار فعلی متغیر می رسد LC_COLLATE هنگام اجرا در حالت اشکال زدایی:

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

مقایسه رشته ها با استفاده از تابع استاندارد انجام می شود strcoll، یعنی همه چیز جالب در کتابخانه است از glibc.

بر ویکی پروژه از glibc اختصاص داده شده به مقایسه رشته ها یک پاراگراف. از این بند می توان فهمید که در از glibc مرتب سازی بر اساس الگوریتمی است که قبلاً برای ما شناخته شده است ACU (الگوریتم دسته بندی یونیکد) و/یا در یک استاندارد نزدیک به آن 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 از OpenGroup. به عنوان جایگزینی برای خواندن استاندارد، می توانید کد منبع تابع را مطالعه کنید collate_read в glibc/locale/programs/ld-collate.c.

ساختار فایل به شکل زیر است:

به طور پیش فرض، کاراکتر به عنوان یک کاراکتر فرار استفاده می شود و انتهای خط بعد از کاراکتر # یک نظر است. هر دو نماد را می توان دوباره تعریف کرد، که در نسخه جدید جدول انجام می شود:

escape_char /
comment_char %

فایل حاوی نشانه هایی با فرمت خواهد بود یا (جایی که x - رقم هگزادسیمال). این نمایش هگزادسیمال نقاط کد یونیکد در رمزگذاری است UCS-4 (UTF-32). تمام عناصر دیگر در براکت های زاویه (از جمله , <2> و مانند آن) ثابت های رشته ای ساده ای در نظر گرفته می شوند که در خارج از زمینه معنای کمی دارند.

خط LC_COLLATE به ما می گوید که در مرحله بعد، داده هایی که مقایسه رشته ها را توصیف می کنند آغاز می شود.

ابتدا نام برای وزن ها در جدول مقایسه و نام برای ترکیب نمادها مشخص می شود. به طور کلی، این دو نوع نام متعلق به دو نهاد متفاوت هستند، اما در فایل واقعی آنها مخلوط شده اند. نام اوزان با کلمه کلیدی مشخص می شود تطبیق-نماد (کاراکتر مقایسه) زیرا هنگام مقایسه، کاراکترهای یونیکد که دارای وزن یکسان هستند، کاراکترهای معادل در نظر گرفته می شوند.

طول کل بخش در ویرایش فایل فعلی حدود 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 в تطبیق-نماد به نظر می رسد یک عدد صحیح بدون علامت بزرگ در هگزادسیمال، اما این فقط یک نام است که ممکن است شبیه باشد
نام به معنای نقطه کد در رمزگذاری است UCS-4
عنصر ترکیبی از جانب " " یک نام جدید برای یک جفت نقطه یونیکد ثبت می کند.

هنگامی که نام وزن ها مشخص شد، وزن های واقعی مشخص می شوند. از آنجایی که فقط روابط بیشتر از کمتر در مقایسه مهم است، وزن ها با یک دنباله ساده از نام های فهرست تعیین می شوند. ابتدا وزن‌های سبک‌تر و سپس وزن‌های «سنگین‌تر» فهرست می‌شوند. اجازه دهید به شما یادآوری کنم که به هر کاراکتر یونیکد چهار وزن مختلف اختصاص داده شده است. در اینجا آنها در یک توالی مرتب شده ترکیب می شوند. در تئوری، هر نام نمادینی را می توان در هر یک از چهار سطح استفاده کرد، اما نظرات نشان می دهد که توسعه دهندگان از نظر ذهنی نام ها را به سطوح جدا می کنند.

% 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 تعیین کنید که ردیف‌ها در کدام جهت در هر سطح مقایسه اسکن می‌شوند. تنظیمات پیش فرض است رو به جلو. بدنه بخش شامل خطوطی است که حاوی کد نماد و چهار وزن آن است. کد کاراکتر را می توان با خود کاراکتر، یک نقطه کد یا یک نام نمادین که قبلاً تعریف شده بود نشان داد. همچنین می توان به نام های نمادین، نقاط رمز یا خود نمادها وزن داد. اگر از نقاط کد یا کاراکترها استفاده شود، وزن آنها با مقدار عددی نقطه کد (موقعیت در جدول یونیکد) برابر است. کاراکترهایی که به صراحت مشخص نشده‌اند (همانطور که من متوجه شدم) با وزن اصلی که با موقعیت جدول یونیکد مطابقت دارد، به جدول اختصاص داده می‌شوند. ارزش وزن ویژه چشم پوشی به این معنی است که نماد در سطح مناسب مقایسه نادیده گرفته می شود.

برای نشان دادن ساختار مقیاس ها، سه قطعه نسبتاً واضح را انتخاب کردم:

شخصیت هایی که کاملا نادیده گرفته می شوند
نمادهایی معادل عدد سه در دو سطح اول
ابتدای الفبای سیریلیک، که شامل دیاکریتیک نیست، و بنابراین عمدتا بر اساس سطوح اول و سوم مرتب شده است.

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'
};

از آنجایی که در یونیکد نقطه کد Ё قبل از A قرار می گیرد، رشته ها بر این اساس مرتب می شوند.

جداول متنی و باینری

بدیهی است که مقایسه رشته ها یک عملیات بسیار رایج و تجزیه جدول است CTT یک روش کاملا پرهزینه برای بهینه سازی دسترسی به جدول، با دستور به شکل باینری کامپایل می شود محلی.

تیم محلی فایلی با جدول مشخصات ملی را به عنوان پارامتر می پذیرد (گزینه -i) که در آن همه کاراکترها با نقاط یونیکد نشان داده می شوند و یک فایل مربوط به نقاط یونیکد و کاراکترهای یک رمزگذاری خاص (گزینه). -f). در نتیجه کار، فایل های باینری برای محلی با نام مشخص شده در آخرین پارامتر ایجاد می شود.

glibc از دو فرمت فایل باینری پشتیبانی می کند: "سنتی" و "مدرن".

فرمت سنتی به این معنی است که نام محلی، نام دایرکتوری فرعی در است /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/

اگر محلی در هر دو قالب سنتی و مدرن رخ دهد، اولویت به مدرن داده می شود.

با دستور می توانید لیستی از مناطق کامپایل شده را مشاهده کنید locale-a.

آماده کردن جدول مقایسه شما

اکنون، با داشتن دانش، می توانید جدول مقایسه رشته های ایده آل خود را ایجاد کنید. این جدول باید حروف روسی از جمله حرف Ё را به درستی مقایسه کند و در عین حال علائم نگارشی مطابق جدول را در نظر بگیرد. ASCII.

فرآیند تهیه جدول مرتب سازی شما شامل دو مرحله است: ویرایش جدول وزن و کامپایل آن به شکل باینری با دستور محلی.

برای اینکه جدول مقایسه با کمترین هزینه ویرایش، در قالب تنظیم شود 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، اما در مثال من این مورد نیاز نبود، زیرا من بایگانی را از جستجوی مناطق حذف کردم محلی-آرشیو.

که محلی با فایل های موجود در پوشه من از طریق یک متغیر کار کرد I18NPATH می‌توانید یک فهرست اضافی برای جستجوی فایل‌های ورودی اضافه کنید، و دایرکتوری برای ذخیره فایل‌های باینری را می‌توان به‌عنوان یک مسیر با اسلش مشخص کرد:

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

POSIX فرض می کند که در زبان شما می توانید مسیرهای مطلق دایرکتوری ها را با فایل های محلی بنویسید، که با اسلش رو به جلو شروع می شود، اما از glibc в لینـوکــس همه مسیرها از دایرکتوری پایه شمارش می‌شوند که می‌توان آن‌ها را از طریق یک متغیر لغو کرد محل کار... پس از نصب LOCPATH=~/.local/lib/locale/ تمام فایل های مربوط به محلی سازی فقط در پوشه من جستجو می شود. بایگانی مناطق با مجموعه متغیر محل کار نادیده گرفته شده است.

در اینجا آزمون تعیین کننده است:

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

هورا! ما آن را انجام دادیم!

برخی از اشتباهات

من قبلاً به سؤالات مربوط به مرتب سازی رشته ها در ابتدا پاسخ داده ام، اما هنوز چند سؤال در مورد خطاها وجود دارد - قابل مشاهده و نامرئی.

بیایید به مشکل اصلی برگردیم.

و برنامه نوع و برنامه پیوستن از همان توابع مقایسه رشته استفاده کنید از glibc. چطور شد که اینطور شد پیوستن یک خطای مرتب‌سازی در ردیف‌های مرتب‌سازی شده توسط دستور داد نوع در محلی en_US.UTF-8? پاسخ ساده است: نوع کل رشته را مقایسه می کند و پیوستن فقط کلید را مقایسه می کند که به طور پیش فرض ابتدای رشته تا اولین کاراکتر فضای خالی است. در مثال من، این منجر به یک پیام خطا شد زیرا مرتب‌سازی اولین کلمات در خطوط با مرتب‌سازی خطوط کامل مطابقت نداشت.

محلی "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 حاوی خطای دیگری است واقعیت این است که در تمام توزیع های شناخته شده برای من لینـوکــس بسته‌ها فاقد منطقه کامپایل شده هستند ru_RU.CP1251. اگر محل کامپایل شده یافت نشد، پس نوع بی‌صدا از مقایسه بایت به بایت استفاده می‌کند، چیزی که مشاهده کردیم.

به هر حال، یک اشکال کوچک دیگر مربوط به عدم دسترسی به مناطق کامپایل شده وجود دارد. تیم 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 خروجی فایل هایی که با یک نقطه مخلوط با فایل هایی که با یک حرف شروع می شوند شروع می شود و فرمانده نیمه شب، که از توابع داخلی خود برای مرتب کردن نام ها استفاده می کند، فایل هایی را که با نقطه شروع می شوند در ابتدای لیست قرار می دهد.