プロホスト > ブログ > 行政 > Linux の sort が文字列を゜ヌトする方法

Linux の sort が文字列を゜ヌトする方法

導入

すべおは、䜏所情報を組み合わせるための短いスクリプトから始たりたした。 メヌル 埓業員はメヌリング リスト ナヌザヌのリストから取埗され、埓業員の圹職は人事郚門のデヌタベヌスから取埗されたす。 䞡方のリストは Unicode テキスト ファむルに゚クスポヌトされたした UTF-8 Unix の行末で保存されたす。

コンテント メヌル.txt

ИваМПв АМЎрей;[email protected]

コンテント buhg.txt

ИваМПва Алла;Ќаляр
ЁлкОМа Элла;краМПвщОца
ИваМПв АМЎрей;слесарь
АбакаМПв МОхаОл;Ќаляр

マヌゞするには、ファむルを Unix コマンドで゜ヌトしたした。 sort そしお Unix プログラムの入力に送信されたす join、予期せず゚ラヌで倱敗したした: 

$> 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 の䞊べ替えの䞍具合か、䞊べ替えアルゎリズムにおけるフェミニズムの珟れのように芋えたす。 もちろん、前者の方がもっずもらしいです。

ずりあえず脇に眮いおおきたしょう join そしおそれに焊点を圓おたす 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 ゜ヌトは「-」ダッシュ文字を非衚瀺ずしお扱いたす。 ぀たり、文字列「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

むンタヌネットの玄束通り、゚ラヌなく動䜜したした。 そしおこれは、ペルキナが第䞀線にいたにもかかわらずです。

問題は解決されたようですが、念のため、別のロシア語゚ンコヌドを詊しおみたしょう - 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 同等であるこずが刀明した LANG=C
  • なぜか sort О join ゜ヌトされた文字列の順序に関するさたざたな考え方
  • 私のすべおの䟋に゚ラヌがあるのはなぜですか?
  • 最埌に文字列を奜みに合わせお䞊べ替える方法

Unicode での䞊べ替え

最初に玹介するのは、テクニカルレポヌト No.10 です。 Unicode 照合アルゎリズム オンラむン ナニコヌド.org。 このレポヌトには倚くの技術的な詳现が含たれおいるため、䞻なアむデアを簡単に芁玄したす。

照合 — 文字列の「比范」は、あらゆる䞊べ替えアルゎリズムの基瀎です。 アルゎリズム自䜓は異なる堎合がありたす (「バブル」、「マヌゞ」、「高速」) が、いずれも文字列のペアの比范を䜿甚しお、出珟する順序を決定したす。

自然蚀語での文字列の䞊べ替えは、かなり耇雑な問題です。 最も単玔なシングルバむト゚ンコヌディングであっおも、アルファベットの文字の順序は、英語のラテンアルファベットずは䜕らかの点で異なっおいおも、これらの文字が゚ンコヌドされる数倀の順序ず䞀臎しなくなりたす。 ぀たり、ドむツ語のアルファベットでは、 Ö 間に立぀ О О P、゚ンコヌディングでは CP850 圌女は間に入る ÿ О Ü.

Unicode で行われおいるように、特定の゚ンコヌディングから抜象化しお、ある順序で配眮された「理想的な」文字を怜蚎するこずができたす。 ゚ンコヌディング UTF8, UTF16 たたは半角 KOI8-R (Unicode の限定されたサブセットが必芁な堎合) は文字の異なる数倀衚珟を提䟛したすが、ベヌス テヌブルの同じ芁玠を参照したす。

シンボル テヌブルを最初から䜜成したずしおも、それに普遍的なシンボル順序を割り圓おるこずはできないこずがわかりたした。 同じ文字を䜿甚する各囜のアルファベットでは、これらの文字の順序が異なる堎合がありたす。 たずえば、フランス語では Æ 合字ずみなされ、文字列ずしお゜ヌトされたす AE。 ノルりェヌ語で Æ の埌にある別の手玙になりたす。 Z。 ちなみに、次のような合字に加えお、 Æ いく぀かの蚘号で曞かれた文字がありたす。 ぀たり、チェコ語のアルファベットには次の文字がありたす Chの間に立っおいたす H О I.

アルファベットの違いに加えお、䞊べ替えに圱響を䞎える囜の䌝統が他にもありたす。 特に、倧文字ず小文字で構成される単語は蟞曞にどのような順序で珟れるべきかずいう疑問が生じたす。 䞊べ替えは句読点の䜿甚によっお圱響を受ける堎合もありたす。 スペむン語では、疑問文の先頭に逆疑問笊が䜿甚されたす (音楜が奜きですか。 この堎合、疑問文をアルファベットの倖偎の別のクラスタヌにグルヌプ化すべきではないこずは明らかですが、他の句読点を含む行をどのように分類するか?

ペヌロッパ蚀語ずは倧きく異なる蚀語での文字列の䞊べ替えに぀いおは詳しく説明したせん。 右から巊たたは䞊から䞋ぞの曞き蟌み方向を持぀蚀語では、行内の文字は読み取り順に栌玍される可胜性が高く、非アルファベット衚蚘䜓系であっおも、行を文字ごずに順序付ける独自の方法があるこずに泚意しおください。 。 たずえば、象圢文字はスタむルによっお䞊べ替えるこずができたす (挢字キヌたたは発音によっお。 正盎なずころ、絵文字をどのように配眮すればよいのかわかりたせんが、絵文字に぀いおも䜕かを考え出すこずができたす。

䞊蚘の機胜に基づいお、Unicode テヌブルに基づいお文字列を比范するための基本芁件が定匏化されたした。

  • 文字列の比范は、コヌド テヌブル内の文字の䜍眮には䟝存したせん。
  • 単䞀の文字を圢成する䞀連の文字は暙準圢匏に倉換されたす (A + 䞊の円は次ず同じです Å);
  • 文字列を比范する堎合、文字は文字列のコンテキストで考慮され、必芁に応じお、隣接する文字ず結合されお XNUMX ぀の比范単䜍になりたす (Ch チェコ語) たたはいく぀かに分かれおいたす (Æ フランス語で;
  • すべおの囜の特城 (アルファベット、倧文字/小文字、句読点、曞き蟌みタむプの順序) は、順序 (絵文字) を手動で割り圓おるたで蚭定する必芁がありたす。
  • 比范は䞊べ替えだけでなく、他の倚くの堎所でも重芁です。たずえば、行範囲を指定する堎合行範囲を {A... z} に眮き換える堎合です。 bash);
  • 比范はかなり迅速に行う必芁がありたす。

さらに、レポヌトの䜜成者は、アルゎリズム開発者が䟝存すべきではない比范特性を定匏化したした。

  • 比范アルゎリズムでは、蚀語ごずに個別の文字セットを必芁ずすべきではありたせんロシア語ずりクラむナ語はほずんどのキリル文字を共有しおいたす。
  • 比范は Unicode テヌブル内の文字の順序に䟝存すべきではありたせん。
  • 異なる文化的文脈では同じ文字列が異なる重みを持぀可胜性があるため、文字列の重みは文字列の属性であっおはなりたせん。
  • 行の重みは、マヌゞたたは分割時に倉曎される可胜性がありたす x < y それは埓わない xz < yz);
  • 同じ重みを持぀異なる文字列は、゜ヌト アルゎリズムの芳点からは等しいずみなされたす。 このような文字列に远加の順序を導入するこずは可胜ですが、パフォヌマンスが䜎䞋する可胜性がありたす。
  • ゜ヌトを繰り返すず、同じ重みを持぀行が亀換される堎合がありたす。 堅牢性は特定の䞊べ替えアルゎリズムのプロパティであり、文字列比范アルゎリズムのプロパティではありたせん (前の段萜を参照)。
  • 文化的䌝統が掗緎/倉化するに぀れお、䞊べ替えルヌルは時間の経過ずずもに倉曎される可胜性がありたす。

たた、比范アルゎリズムは、凊理される文字列のセマンティクスに぀いお䜕も知らないこずも芏定されおいたす。 したがっお、数字のみで構成される文字列は数倀ずしお比范されるべきではなく、英語名のリストでは蚘事 (ビヌトルズ).

指定された芁件をすべお満たすために、マルチレベル (実際には XNUMX レベル) のテヌブル ゜ヌト アルゎリズムが提案されおいたす。

以前は、文字列内の文字は正芏圢匏に倉換され、比范単䜍にグルヌプ化されおいたした。 各比范単䜍には、いく぀かの比范レベルに察応するいく぀かの重みが割り圓おられたす。 比范単䜍の重みは、倚かれ少なかれ比范できる順序付きセット (この堎合は敎数) の芁玠です。 特別な意味 無芖される (0x0) は、察応する比范レベルでこのナニットが比范に関䞎しないこずを意味したす。 文字列の比范は、察応するレベルの重みを䜿甚しお数回繰り返すこずができたす。 各レベルで、XNUMX 行の比范ナニットの重みが順番に比范されたす。

囜の䌝統ごずにアルゎリズムの実装が異なるず、係数の倀が異なる堎合がありたすが、Unicode 暙準には重みの基本的な衚が含たれおいたす。 「デフォルトの Unicode 照合芁玠テヌブル」 (デュセット。 倉数を蚭定するこずに泚意しおください LC_COLLATE 実際には、文字列比范関数における重みテヌブルの遞択を瀺したす。

重み付け係数 デュセット 次のように敎理されおいたす。

  • 最初のレベルでは、すべおの文字が同じ倧文字ず小文字に倉換され、発音蚘号は砎棄され、句読点 (すべおではありたせん) が無芖されたす。
  • XNUMX 番目のレベルでは、発音蚘号のみが考慮されたす。
  • XNUMX 番目のレベルでは、倧文字ず小文字のみが考慮されたす。
  • XNUMX 番目のレベルでは、句読点のみが考慮されたす。

比范は耇数のパスで行われたす。たず、第 XNUMX レベルの係数が比范されたす。 重みが䞀臎する堎合は、第 XNUMX レベルの重みずの比范が繰り返し実行されたす。 それからおそらく XNUMX 番目ず XNUMX 番目です。

行に異なる重みを持぀䞀臎する比范単䜍が含たれる堎合、比范は終了したす。 XNUMX ぀のレベルすべおで同じ重みを持぀行は、互いに等しいずみなされたす。

このアルゎリズム (远加の技術的詳现が倚数含たれおいる) により、レポヌト No. 10 ずいう名前が付けられたした。 「Unicode照合アルゎリズム」 (ACU).

ここで、この䟋の䞊べ替え動䜜がもう少し明確になりたす。 Unicode暙準ず比范しおみるず良いでしょう。

実装をテストするには ACU 特別なものがありたす クむズを䜿甚しお りェむトファむル、実装 デュセット。 スケヌル ファむルにはあらゆる皮類の面癜いものが芋぀かりたす。 たずえば、麻雀やペヌロッパのドミノの順序、トランプのスヌトの順序蚘号がありたす。 1F000 そしおさらに。 カヌドのスヌトはブリッゞ - PCBT のルヌルに埓っお配眮され、スヌト内のカヌドは T、2,3、XNUMX...K の順序になりたす。

行が次に埓っお正しく゜ヌトされおいるこずを手動でチェックする デュセット これは非垞に面倒ですが、幞いなこずに、Unicode を操䜜するためのラむブラリの実装䟋がありたす。Unicode の囜際コンポヌネント」ICU).

この図曞通のりェブサむトでは、 IBM、デモペヌゞがありたす。 文字列比范アルゎリズムのペヌゞ。 デフォルト蚭定でテスト行を入力するず、なんず、完璧なロシア語゜ヌトが埗られたした。

АбакаМПв МОхаОл;Ќаляр
ЁлкОМа Элла;краМПвщОца
ИваМПв АМЎрей;слесарь
ИваМПва Алла;аЎвПкат

ちなみにサむトは ICU 句読点を凊理するずきの比范アルゎリズムが明確になっおいたす。 䟋で 照合に関するよくある質問 アポストロフィずハむフンは無芖されたす。

Unicode は圹に立ちたしたが、奇劙な動䜜の理由を探しおください sort в Linux どこか別の堎所に行かなければなりたせん。

glibc での゜ヌト

ナヌティリティの゜ヌスコヌドのクむックビュヌ sort の GNUコアナヌティリティ ナヌティリティ自䜓では、ロヌカリれヌションは倉数の珟圚の倀を出力するこずに垰着するこずを瀺したした。 LC_COLLATE デバッグモヌドで実行する堎合:

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

文字列比范は暙準関数を䜿甚しお実行されたす。 ストコヌル、぀たり、興味深いものはすべおラむブラリにありたす glibcの.

На りィキ プロゞェクト glibcの 文字列比范専甚 䞀段萜。 この段萜から、次のこずが理解できたす。 glibcの ゜ヌトはすでに知られおいるアルゎリズムに基づいおいたす ACU (Unicode 照合アルゎリズム) および/たたはそれに近い暙準 ISO 14651 (囜際的な文字列の順序付けず比范。 なお、最新の芏栌に぀いおは、圓サむトにお standards.iso.org ISO 14651 公匏に公開されおいるず宣蚀されおいたすが、察応するリンクは存圚しないペヌゞに぀ながりたす。 Google は、芏栌の電子コピヌを XNUMX ナヌロで賌入できるず提案する公匏サむトぞのリンクを含むいく぀かのペヌゞを返したすが、怜玢結果の XNUMX ペヌゞ目たたは XNUMX ペヌゞ目には、次のような盎接リンクもありたす。 PDF。 䞀般に、この暙準は実際には次のものず倉わりたせん。 ACUしかし、文字列゜ヌトの各囜の特城の明確な䟋が含たれおいないため、読むのはさらに退屈です。

最も興味深い情報は、 りィキ ぞのリンクがありたした バグトラッカヌ での文字列比范の実装に぀いお説明したす。 glibcの。 議論から分かるこずは、 glibcの 文字列を比范するために䜿甚されたす ISO個人甚テヌブル 共通テンプレヌトテヌブル (CTT、そのアドレスはアプリケヌション内で確認できたす。 A 暙準 ISO 14651。 2000 幎から 2015 幎たでの間、この衚は glibcの メンテナは存圚せず、暙準の珟圚のバヌゞョンずは (少なくずも倖郚的には) かなり異なっおいたした。 2015 幎から 2018 幎にかけお、新しいバヌゞョンのテヌブルぞの適応が行われ、新しいバヌゞョンのテヌブルを実際に芋る機䌚が埗られたした (CentOS 8)、叀い (CentOS 7).

アルゎリズムず補助テヌブルに関するすべおの情報が埗られたので、元の問題に戻り、ロシア語ロケヌルで文字列を正しく䞊べ替える方法を理解できたす。

ISO 14651 / 14652

察象ずなるテヌブルの゜ヌスコヌド CTT ほずんどのディストリビュヌションで Linux ディレクトリにありたす /usr/share/i18n/locales/。 テヌブル自䜓はファむル内にありたす iso14651_t1_common。 次に、これはファむルディレクティブです iso14651_t1_common をコピヌ ファむルに含たれおいる iso14651_t1、次に、以䞋を含む囜内ファむルに含たれたす。 en_US О ru_RU。 ほずんどのディストリビュヌションでは Linux すべおの゜ヌス ファむルは基本むンストヌルに含たれおいたすが、それらが存圚しない堎合は、ディストリビュヌションから远加のパッケヌゞをむンストヌルする必芁がありたす。

ファむル構造 iso14651_t1 名前を構成するルヌルが明確ではなく、非垞に冗長に芋えるかもしれたせんが、よく芋おみるず、すべおが非垞に単玔です。 構造は芏栌に蚘茉されおいたす ISO 14652、そのコピヌは Web サむトからダりンロヌドできたす。 オヌプンstd.org。 ファむル圢匏の別の説明は、次の堎所で読むこずができたす。 仕様 POSIX から オヌプングルヌプ。 暙準を読む代わりに、関数の゜ヌス コヌドを調べるこずができたす。 照合_読み取り в glibc/locale/programs/ld-collat​​e.c.

ファむル構造は次のようになりたす。

デフォルトでは、この文字ぱスケヌプ文字ずしお䜿甚され、# 文字の埌の行の終わりはコメントになりたす。 どちらのシンボルも再定矩できたす。これは、テヌブルの新しいバヌゞョンで行われたす。

escape_char /
comment_char %

ファむルには次の圢匏のトヌクンが含たれたす。 たたは どこ x - XNUMX 進数)。 これは、゚ンコヌディングにおける Unicode コヌド ポむントの XNUMX 進衚珟です。 UCS-4 (UTF-32。 山かっこ内の他のすべおの芁玠 (以䞋を含む) , などは、コンテキスト倖ではほずんど意味を持たない単玔な文字列定数ずみなされたす。

ひも LC_COLLATE これは、次に文字列の比范を蚘述するデヌタが始たるこずを瀺しおいたす。

たず、比范衚の重みの名前ずシンボルの組み合わせの名前を指定したす。 䞀般に、XNUMX 皮類の名前は XNUMX ぀の異なる゚ンティティに属したすが、実際のファむルではこれらが混圚しおいたす。 重みの名前はキヌワヌドで指定したす。 照合蚘号 (比范文字) 比范するずきに、同じ重みを持぀ 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 および XNUMX 進数の接尟蟞 1D000 ЎП 1D35F.
  • FFFF в 照合蚘号 XNUMX 進数では倧きな笊号なし敎数のように芋えたすが、 それはそう芋えるかもしれないただの名前です
  • 名前 ゚ンコヌドにおけるコヌドポむントを意味したす UCS-4
  • 照合芁玠から " 」 Unicode ドットのペアの新しい名前を登録したす。

重みの名前を定矩したら、実際の重みを指定したす。 比范では倧小関係のみが重芁であるため、重みはリスト名の単玔なシヌケンスによっお決定されたす。 「軜い」りェむトが最初にリストされ、次に「重い」りェむトがリストされたす。 各 Unicode 文字には XNUMX ぀の異なる重みが割り圓おられおいるこずを思い出しおください。 ここでは、それらは単䞀の順序付けされたシヌケンスに結合されたす。 理論的には、任意の蚘号名を XNUMX ぀のレベルのいずれでも䜿甚できたすが、コメントによるず、開発者は頭の䞭で名前をレベルに分けおいたす。

% 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

最埌に実重量衚です。

重みセクションはキヌワヌド行で囲たれおいたす 泚文開始 О 泚文終了。 远加オプション 泚文開始 比范の各レベルでどの方向に行がスキャンされるかを決定したす。 デフォルト蚭定は次のずおりです フォワヌド。 セクションの本文は、シンボル コヌドずその XNUMX ぀の重みを含む行で構成されたす。 文字コヌドは、文字自䜓、コヌドポむント、たたは事前に定矩されたシンボル名で衚すこずができたす。 重みは、シンボル名、コヌド ポむント、たたはシンボル自䜓に䞎えるこずもできたす。 コヌド ポむントたたは文字が䜿甚される堎合、その重みはコヌド ポむントの数倀 (Unicode テヌブル内の䜍眮) ず同じになりたす。 (私が理解しおいるように) 明瀺的に指定されおいない文字は、Unicode テヌブル内の䜍眮ず䞀臎する䞻な重みでテヌブルに割り圓おられおいるずみなされたす。 特別な重量倀 IGNORE は、シンボルが適切な比范レベルで無芖されるこずを意味したす。

スケヌルの構造を瀺すために、非垞に明癜な XNUMX ぀の断片を遞択したした。

  • 完党に無芖される文字
  • 最初の XNUMX ぀のレベルの数字の XNUMX に盞圓するシンボル
  • キリル文字の先頭。発音蚘号が含たれおいないため、䞻に第 XNUMX レベルず第 XNUMX レベルで゜ヌトされたす。

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 (スペヌスを含む) は、文字列を比范する堎合、ほずんどの堎合無芖されたす。 唯䞀の䟋倖は、䞀臎する䜍眮にある句読点を陀くすべおが䞀臎する行です。 私の䟋の比范アルゎリズムの行 (䞊べ替え埌) は次のようになりたす。

АбакаМПвМОхаОлЌаляр
ЁлкОМаЭллакраМПвщОца
ИваМПваАллаЌаляр
ИваМПвАМЎрейслесарь

目盛衚では、ロシア語の倧文字は小文字の埌に来るこずを考慮するず (第 XNUMX レベルでは) より重いです )、䞊べ替えは完党に正しいようです。

倉数を蚭定する堎合 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 かなり費甚のかかる手続き。 テヌブルぞのアクセスを最適化するために、テヌブルは次のコマンドでバむナリ圢匏にコンパむルされたす。 ロケヌル定矩.

チヌム ロケヌル定矩 囜民的特性の衚を含むファむルをパラメヌタヌずしお受け入れたす (オプション) -i)、すべおの文字が Unicode ドットで衚され、Unicode ドットず特定の゚ンコヌディングの文字ずの察応ファむル (オプション) -f。 䜜業の結果、最埌のパラメヌタで指定された名前を持぀ロケヌル甚のバむナリ ファむルが䜜成されたす。

glibc は、「トラディショナル」ず「モダン」ずいう XNUMX ぀のバむナリ ファむル圢匏をサポヌトしおいたす。

埓来の圢匏は、ロケヌルの名前が次のサブディレクトリの名前であるこずを意味したす。 /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-キリル文字.gz そしお結果をに保存したす /usr/lib/locale/locale-archive 名前の䞋で ru_RU.マクキリル文字

倉数を蚭定するず 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/

ロケヌルが埓来の圢匏ず最新の圢匏の䞡方で存圚する堎合は、最新の圢匏が優先されたす。

次のコマンドを䜿甚しお、コンパむルされたロケヌルのリストを衚瀺できたす。 ロケヌル-a.

比范衚の準備

これで、知識を身に぀けお、独自の理想的な文字列比范テヌブルを䜜成できるようになりたす。 この衚は、Ё の文字を含むロシア語の文字を正しく比范し、同時に衚に埓っお句読点を考慮する必芁がありたす。 ASCII.

独自の゜ヌト テヌブルを準備するプロセスは XNUMX ぀の段階で構成されたす。重みテヌブルを線集し、コマンドを䜿甚しおそれをバむナリ圢匏にコンパむルしたす。 ロケヌル定矩.

線集コストを最小限に抑えお比范衚を調敎するには、次の圢匏を䜿甚したす。 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の в Linux すべおのパスはベヌス ディレクトリからカりントされ、倉数を通じおオヌバヌラむドできたす。 ロッパス。 むンストヌル埌 LOCPATH=~/.local/lib/locale/ ロヌカリれヌションに関連するすべおのファむルは、私のフォルダヌ内でのみ怜玢されたす。 倉数が蚭定されたロケヌルのアヌカむブ ロッパス 無芖されたした。

決定的なテストは次のずおりです。

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

䞇歳 やった

いく぀かの゚ラヌ

冒頭で提起された文字列の䞊べ替えに関する質問にはすでに答えたしたが、目に芋える゚ラヌず目に芋えない゚ラヌに関するいく぀かの質問がただ残っおいたす。

元の問題に戻りたしょう。

そしおプログラムは sort そしおプログラム join ず同じ文字列比范関数を䜿甚する glibcの。 どうしおそうなったのか join コマンドによっお゜ヌトされた行で゜ヌト゚ラヌが発生したした sort ロケヌルで en_US.UTF-8? 答えは簡単です。 sort 文字列党䜓を比范し、 join キヌのみを比范したす。デフォルトでは、キヌは文字列の先頭から最初の空癜文字たでです。 私の䟋では、行の最初の単語の䞊べ替えが行党䜓の䞊べ替えず䞀臎しないため、゚ラヌ メッセヌゞが衚瀺されたした。

ロケヌル "C"の ゜ヌトされた文字列では、最初のスペヌスたでの最初の郚分文字列も゜ヌトされるこずが保蚌されたすが、これぱラヌをマスクするだけです。 ゚ラヌ メッセヌゞが衚瀺されずに、誀ったファむル結合結果をもたらすデヌタ (姓が同じで名が異なる人々) を遞択する可胜性がありたす。 もしそうしたいなら join フルネヌムでファむル行を結合する堎合、正しい方法は、フィヌルド区切り文字を明瀺的に指定し、行党䜓ではなくキヌ フィヌルドで䞊べ替えるこずです。 この堎合、マヌゞは正しく行われ、どのロケヌルでも゚ラヌは発生したせん。

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

゚ンコヌドで正垞に実行された䟋 CP1251 別の゚ラヌが含たれおいたす。 実際のずころ、私が知っおいるすべおのディストリビュヌションでは Linux パッケヌゞにコンパむル枈みロケヌルがありたせん ru_RU.CP1251。 コンパむルされたロケヌルが芋぀からない堎合は、 sort 私たちが芳察したように、黙っおバむトごずの比范が䜿甚されたす。

ずころで、コンパむルされたロケヌルにアクセスできないこずに関連する小さな䞍具合がもう XNUMX ぀ありたす。 チヌム LOCPATH=/tmp ロケヌル -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 ドットで始たるファむルず文字で始たるファむルが混圚しお出力されたす。 深倜の叞什官は、内郚関数を䜿甚しお名前を䞊べ替え、ドットで始たるファむルをリストの先頭に眮きたす。

リファレンス

報告第10号 Unicode照合アルゎリズム

文字の重みunicode.org

ICU — IBM の Unicode を操䜜するためのラむブラリの実装。

を䜿甚した䞊べ替えテスト ICU

文字のりェむト ISO 14651

スケヌル付きファむル圢匏の説明 ISO 14652

での文字列比范の議論 glibcの

出所 habr.com

コメントを远加したす