文字列の照合順序(Collation)

作成日：2014.03.13

更新履歴
(2014.0313) 2013年6月27日の日記と2014年3月3日の日記から作成。

目次

• はじめに
  • strcoll 関数
  • strxfrm 関数
  • 疑問
• UTF-8 の話
• 文字列照合順序(Collation)
  • L1 Base Characters
  • L2 Accents
  • L3 Case/Variants
  • L4 Punctuation
  • Llast Identical
• ライブラリ実装
• 参考文献
• コメント

はじめに

C 言語の文字列の比較は strcmp() を用いるのが一般的である。 この関数は 2 つの NULL 終端文字列を先頭から符号なしバイトとして比較し大小関係を決める。

一方、文字列が各国のロケール(locale)を持つ場合、言語・国固有の文字列の照合順序(collation)が存在する。 Collation に基づいて文字比較を行うには strcoll() や strxfrm() を用いる。

strcoll 関数

strcoll() は現在のロケールに定義されている collation に基づき文字比較を行う関数である。 Collation の指定には環境変数 LC_COLLATE を設定する。 Linux のディストリビューションの多くは、デフォルトでは LC_COLLATE は設定されず、C を指定したとみなされている。

export LC_COLLATE=ja_JP.utf8

LC_COLLATE 指定する以外では、環境変数 LC_ALL を指定した場合も collation は設定される。 ただし環境変数 LANG は collation を設定しないので注意。

Collation を設定した上で strcoll() を呼び出すと、指定されたロケールの照合順序で文字比較が行われる。 指定しない場合(CやPOSIXの場合)は、strcoll() は strcmp() と同じ動作をする。

result = strcoll(str1, str2);

環境変数ではなく、プログラムの中で collation を変更したい場合は setlocale() に LC_COLLATE を与えて実行する。

setlocale(LC_COLLATE, "ja_JP.utf8");

プログラムの中で複数のロケールを用いたい場合、引数としてロケールを個別に指定することのできる strcoll_l() を使うことも可能である。

#define __USE_XOPEN2K8
#include <string.h>
#include <locale.h>

locale_t mylocale = newlocale(LC_ALL_MASK, "ja_JP.utf8", (locale_t)NULL);
result = strcoll_l(str1, str2, mylocale);

strxfrm 関数

strcoll() は strcmp() と比べると各段に重い関数である。 そのため文字ソートなどのように同じ文字列を何度も strcoll() していると遅くなる。

そこで strxfrm() という関数が用意されている。 この関数は元の文字列をロケールに従い、strcmp() で比較可能な文字列に変換する。 他に strcoll_l() も存在する。

size_t strxfrm(char *dest, const char *src, size_t n);

strxfrm() 関数の引数 src には元のロケールの文字列を指定する。 dest は変換後の結果が格納される領域で、そのバイト数を n で指定する。 strxfrm() の返り値は変換に必要なバイト数から終端の \0 を引いた値である。 もし返り値が n 未満の場合には変換は成功しており、返り値が n 以上の場合は dest の内容は保証されない。

ユーザーは 2 つのロケール文字列を個別に strxfrm() で変換しておき、変換後の文字列同士を strcmp() で比較する。 この結果は最初から strcoll() で比較した場合と一致することが保証されている(無論、変換が成功した場合)。 そのため同じ文字列を何度も strcoll() するよりは、一度だけ strxfrm() した変換結果を strcmp() で比較した方が効率がよい。

strxfrm(xfrm_str1, str1, xfrm_str1_len);
strxfrm(xfrm_str2, str2, xfrm_str2_len);

result = strcmp(xfrm_str1, xfrm_str2);

strxfrm() の変換結果は、もうロケールに沿った文字列ではない。 NULL 終端であることは保証されているが、その内容が何なのか分からない。

疑問

ところ strxfrm() を使っていると、strxfrm() は元の文字列のバイト数に対して、何バイトに変換されるか？という疑問が沸いてくる。

"ja_JP.utf8" を使っている場合、だいたいにおいて元も文字列よりも少ないバイト数に変換される。 しかし "en_US.utf8" ではビックリすることに元が 1 バイトの文字列でも5 バイトに変換される。

どういうルールになっているのだろうか？

UTF-8 の話

その前に UTF-8 のフォーマットの話をしておく。 Collation と文字コードは独立した話なのだが、strxfrm() の変換結果は UTF-8 と同じエンコード形式を持っているので理解しておく必要がある。

UTF-8 は 1〜6 バイトのマルチバイト文字列である。 今のところ 4 バイトまでが使われる。 ASCII を拡張しているので、NULL ターミネートされ、0x01〜0x7F までは ASCII と同じ配列をとる。

2 バイト以上の文字列はまず最初のバイトの MSB に 1 が立ち、そこから N ビット分 1 が続いて 0 で止まる。 続いた 1 の数がエンコーディングされている文字数となる。 2 文字目からは 0b10 がつく。 よって下の表のような構成となり、x が連続する部分を使ってユニコードを記録している。

ある UTF-8 文字列が解釈できない場合、1. エンコードに沿ってないバイト列と 2. ユニコード内に定義されてない番号の場合のパターンがある。

1. 誤ったエンコードは「無効」とされる。例えば最初の 1 バイトが 3 バイトシーケンス(0b110)を示したのに、後続の 2 バイトが並ばなかった場合。 あるいは UTF-8 は一つのエンコードに対して、1つのフォーマットしか許さないので、0x7F なら 0xC1BF のようにも書けるが、後者は「無効」となる。 あるいは 0xFE や 0xFF など UTF-8 では許されないエンコードを使った場合も「無効」となる。
2. エンコーディングは正しいが、ユニコード空間に文字が定義されてない番号も「無効」となる。 そのため 5バイトシーケンスと6バイトシーケンスは UTF-8 では定義されいるが、ユニコードとしては未使用なので「無効」である。

文字列照合順序(Collation)

文字照合の順序は言語と国によって大きく違い、様々なルールがある。 参考文献 の 1. を見て欲しい。

各国のルールを包括的に適用できるように、ロケールの文字列の比較は複数レベルに分けて実施する。 各レベルにおいて文字または文字コンビネーションに対して別々のマッピングテーブルを使うことができる。 最初はレベル 1 で比較を行い、そこで順序関係が決まらない場合には次のレベルに移ってゆくことになる。

L1 Base Charaters

まずレベル1は文字の飾りを外す「丸め」を行った後の基本文字で比較を行う。 大文字と小文字、アクセントの有無、ひらがなとカタナカの違いなどは無視され、同一基本文字となる。

これは全文字コードに対する変換テーブルが用意されており、文字コード毎の優先度が数値で書かれていると考えればよい。 内部的に変換を行った文字列に対して先頭から(forward)比較して行き大小関係を決める。

全ての文字が一致していれば、次の L2 で決めることになる。

L2 Accents

レベル2ではアクセントの有無が区別される。 e < é、o < ô のように順序関係が定義される。

このレベルで重要なのは一部の言語、例えばフランス語の場合、アクセント記号の比較は文字列の最後から先頭に行うことである(backward)。 これを Backward Accent Ordering と呼ぶ。 Normal Accent Ordering との違いを表にまとめる。

Backward accent ordering のような処理を可能にするために、POSIX の Locale ファイルの仕様上は各レベルに以下のルールを設定可能である。 設定可能なルールは 3 種類ある。

• forward - 文字列を先頭から最後に比較する。
• backward - 文字列を最後から先頭に比較する。
• position - これは L4 Punctuation で説明する。

レベル1 は forward であった。

L3 Case/Variants

レベル3では大文字・小文字の比較される。 大文字が先か、小文字が先かはロケールによる。

Variant とは、例えばひらながとカタカナや "あ" と "ぁ" の違いなどがこのレベルで比較可能なように定義されている。

L4 Punctuation

レベル4の Punctuation は句読法と訳すが、次のような機能である。 例えば L1 〜 L3 までで : や , を比較時に無視(IGNORE)する文字と指定しておくと、woman, without her main, is nothing と woman: without her, main is nothing の二つのセンテンスを同一と判断させることができる。 その上でこのレベルで初めて : や , を区別することにする。

実際に en_US のロケールで strcoll("abc", "ab c") < 0 だが、strcoll("abd", "ab c") > 0 になる。 L1 の段階ではスペースの抜いて比較するため、後者は "abd" と "abc" の比較が行われて "d" > "c" と判断される。 一方、前者は L3 までの比較で一致と判断され、L4 で空白文字の有無により決着することになる。

このレベルを利用する場合のルールとして position が使われる。 position は文字列を先頭から最後に比較するが、無視しない文字と無視する文字をそれぞれ分けて整列して比較する。

Llast Identical

レベル4の後にも必要であれば適当にレベルを足すことができるが、最終的に言語や習慣では同一だがバイト列として異なる文字列に対して強制的にケリをつけるレベルである。 文字コードの並び順などで大小比較を行う。

例えばスウェーデン語の v と w は辞書順では同じ並びだが、v < w のように順序をつけてしまう。

ライブラリ実装

以上のような collation に基づいて POSIX Locale や GLIBC の strcoll() や strxfrm() は実装されている。

• GLIBC は Llast の Identical の比較を行わない。strcoll() が一致したら、必要に応じて strcmp() などでバイト列としての一致の確認を追加で行う必要がある。 実際に PostgreSQL はロケール文字列の比較を GLIBC の strcoll() を使うが、strcoll() の返り値が 0 の場合、その後に memcmp() で比較を行っている。
• マルチレベルの比較は各レベルのルールが一致(全部 forward)の場合、全てのレベルを加味した変換テーブルを作れるので一度に変換を行うことができる。 日本語("ja_JP.utf8")はそれで、strxfrm() の入力 1 文字に対して、変換後の結果も 1 文字になる。
• 逆にレベル中に forward、backward、position が現れると、strxfrm() は入力 1 文字に対して、変換後の結果が複数文字にならざる得ない。

これまでの見地を踏まえて "en_US.utf8" での strxfrm() の変換結果を眺めるとルールが見えてくる。

上記から "en_US.utf8" は以下のように変換されているようだ。

• 変換後の文字列は 01 を区切り記号に 3 つまたは 4 つのパートに分かれている。
• 最初のパートは L1 相当のデータが元の文字列の順番に並ぶ。
• 2番目のパートは L2 相当のアクセントの有無を示すデータが元の文字列の順番とは逆に並ぶ。
• 3番目のパートは L3 相当の大文字・小文字の有無を示すデータが元の文字列の順番に並ぶ。
• 4番目のパートは文字列中に punctuation される文字が出現した時だけ設定される。

参考文献

1. UTS #10 | Unicode Collation Algorithm
2. ICU User Guide | Collation
3. The Open Group | The Open Group Base Spec. Issue 6 IEEE Std 1003.1, 2004 Edt.XBD 7. Locale

コメント