ICU: Unicodeでの文字列照合・ソート [C++]

(2018.10) 新規作成.

二つのUnicode文字列が「同一」かどうかは、正規化した上で単に code point を比較していけばいい。このページでは, Unicode文字列の大小を判定する方法について解説する.

ICU 60.2 on Fedora 28 Linux でテストした。

この記事は, こちらの「Javaがポンコツ」という記事に触発された。「Java 6 でIVSを比較すると何が起こるか」の記事の誤り(続編) - Cafe Babe Javaがいかにポンコツか力説。

文字列の並べ替え

文字の並べ替えではない。

文字列をソートする (並べ替える) のは, code point 列を単純に比較する方法では上手くいかない. 用途によってはそれで足りる場合もあるが。

次の順序で並んでほしい;

  1. abc
  2. ABC
  3. abd

あるいは;

  1. あーく
  2. ああく
  3. あーち

まず大文字・小文字、音引きと平仮名を区別せず大らかに並べ替え、次にその中で並べ直す。長音は直前の文字を参照する必要もある。

IVS

IVS (Ideographic Variation Sequence) は, ある Unicode code point に対してグリフを特定するコード列.

このページが詳しい;

対応アプリとフォントの組み合わせで、グリフを出し分けることができる。この例は, U+4E0E に続けて U+E0101 を付けている。

どの基底文字に対して異体字セレクタがあるかは、例えばこちら; AdobeJapan1 IVS異体字一覧

正規化でも異体字セレクタは失われない (当たり前。区別したいのだから.) が、文字列の照合、順序付けでは注意が必要。

ICU: Collatorクラス

ICU では, 照合順序の強度 (strength) を指定する。ルールベースの称号は Collatorクラスを使う。

文字列の照合は、ロケール依存になる。次のサンプルは, いくつかの文字列の組み合わせについて, 照合の強度を変えることで同一・異なるの判定がどのように変わるか、を示す。

IVS (Ideographic Variation Sequence) についても試した。Collator::IDENTICAL 以外では常に一致という判定になる。IVSは、Unicode の建前ではグリフを選ぶもので文字を選ぶものではないから、こうなる。

C++
[RAW]
  1. #include <stdio.h>
  2. #include <unicode/coll.h> // Collator
  3. #include <unicode/uclean.h> // u_cleanup()
  4. using namespace std;
  5. void compare_and_print( Collator* collator,
  6. const UnicodeString& s, const UnicodeString& t,
  7. icu::Collator::ECollationStrength strength )
  8. {
  9. UErrorCode errc = U_ZERO_ERROR;
  10. collator->setStrength( strength );
  11. // LESS = -1, EQUAL = 0, GREATER = +1
  12. UCollationResult r = collator->compare(s, t, errc);
  13. printf("%d ", r);
  14. }
  15. void compare_all_levels( Collator* collator,
  16. const UnicodeString& s, const UnicodeString& t )
  17. {
  18. compare_and_print(collator, s, t, icu::Collator::PRIMARY);
  19. compare_and_print(collator, s, t, icu::Collator::SECONDARY);
  20. compare_and_print(collator, s, t, icu::Collator::TERTIARY);
  21. compare_and_print(collator, s, t, icu::Collator::QUATERNARY);
  22. compare_and_print(collator, s, t, icu::Collator::IDENTICAL);
  23. printf("\n");
  24. }
  25. #define _(x) UnicodeString(x)
  26. int main()
  27. {
  28. UErrorCode errc = U_ZERO_ERROR;
  29. auto loc = Locale("ja", "JP");
  30. icu::Collator* collator = icu::Collator::createInstance(loc, errc);
  31. compare_all_levels(collator, _("ABC"), _("abc") ); // 大文字
  32. compare_all_levels(collator, _("a"), _("\u24d0") ); // 囲み文字
  33. compare_all_levels(collator, _("あーち"), _("ああち") ); // 長音
  34. compare_all_levels(collator, _("せんこく"), _("せんごく") ); // 濁音
  35. compare_all_levels(collator, _("きよう"), _("きょう") ); // 拗音
  36. compare_all_levels(collator, _("与太郎"), _("与\U000E0101太郎") ); // IVS
  37. delete collator;
  38. u_cleanup(); // 必須
  39. return 0;
  40. }

実行結果;

0 0 1 1 1 
0 0 -1 -1 -1 
0 0 -1 -1 -1 
0 -1 -1 -1 -1 
0 0 1 1 1 
0 0 0 0 -1 

濁音が SECONDARY で区別され始める。ほかは TERTIARY から。上述のように, IVS は IDENTICAL のみで区別される。

L1~L4 などアルゴリズムはここで定義されている; UTS #10: Unicode Collation Algorithm. デフォルト設定は DUCET (Default Unicode Collation Element Table) と呼ばれ, Unicode 10.0 のものはこちら; allkeys-10.0.0.txt

ソートキー

いちいち PRIMARY で同一だったら SECONDARY で比較して, ... というコードを書くのは大変だし, convenience method として greaterOrEqual() などが用意されているが、そもそも重そう。

そこで, ソートキーを出力して保存しておき, これで並べ替える手がある。ソートキーから元の文字列を復元することはできないので、元の文字列も保存する必要がある。

次のサンプルは, ソートキーを表示する。

C++
[RAW]
  1. #include <stdio.h>
  2. #include <array>
  3. #include <memory>
  4. #include <unicode/sortkey.h> // CollationKey
  5. #include <unicode/uclean.h> // u_cleanup()
  6. using namespace std;
  7. void dump(const unsigned char* ary, int len)
  8. {
  9. for (int i = 0; i < len; i++)
  10. printf("%02x ", ary[i]);
  11. printf("\n");
  12. }
  13. #define _(x) UnicodeString(x)
  14. void sort_key_test()
  15. {
  16. UErrorCode errc = U_ZERO_ERROR;
  17. auto loc = Locale("ja", "JP");
  18. unique_ptr<icu::Collator> collator(
  19. icu::Collator::createInstance(loc, errc));
  20. array<icu::CollationKey, 4> key;
  21. collator->getCollationKey(_("あーく"), key[0], errc);
  22. collator->getCollationKey(_("ああく"), key[1], errc);
  23. collator->getCollationKey(_("あーち"), key[2], errc);
  24. collator->getCollationKey(_("ああち"), key[3], errc);
  25. for (int i = 0; i < 4; i++) {
  26. int len;
  27. const unsigned char* p = key[i].getByteArray(len);
  28. dump(p, len);
  29. }
  30. }
  31. int main()
  32. {
  33. sort_key_test();
  34. u_cleanup(); // 必須
  35. return 0;
  36. }

実行結果:

5d 06 06 16 01 07 01 05 02 05 00 
5d 06 06 16 01 07 01 07 00 
5d 06 06 28 01 07 01 05 02 05 00 
5d 06 06 28 01 07 01 07 00 

このサンプルのなかで書いたとおりの順番になる。

ソートキーがICUのバージョンに対して安定かどうかは試していない。ICUのバージョンアップで異なる値になることは、十分にありそう。

そのほか

IVSは措いておくとして。

漢字について、包摂がだんだん厳しくなって、どんどん code point が割り当てられるようになっている。テキストの検索では、Unicode code point でも細かすぎ、もっと同一視して検索したいことも多い。

リンクだけ張っておく;