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

実行結果; 

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;
  8. void dump(const unsigned char* ary, int len)
  9. {
  10. for (int i = 0; i < len; i++)
  11. printf("%02x ", ary[i]);
  12. printf("\n");
  13. }
  15. #define _(x) UnicodeString(x)
  17. void sort_key_test()
  18. {
  19. UErrorCode errc = U_ZERO_ERROR;
  20. auto loc = Locale("ja", "JP");
  21. unique_ptr<icu::Collator> collator(
  22. icu::Collator::createInstance(loc, errc));
  24. array<icu::CollationKey, 4> key;
  25. collator->getCollationKey(_("あーく"), key[0], errc);
  26. collator->getCollationKey(_("ああく"), key[1], errc);
  27. collator->getCollationKey(_("あーち"), key[2], errc);
  28. collator->getCollationKey(_("ああち"), key[3], errc);
  29. for (int i = 0; i < 4; i++) {
  30. int len;
  31. const unsigned char* p = key[i].getByteArray(len);
  32. dump(p, len);
  33. }
  34. }
  36. int main()
  37. {
  38. sort_key_test();
  39. u_cleanup(); // 必須
  40. return 0;
  41. }

実行結果: 

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 でも細かすぎ、もっと同一視して検索したいことも多い。

リンクだけ張っておく;

  • 異体字同一視検索 | karak 「中日辞書 北辞郎」における異体字同一視。PHP によるコード例。
  • https://gist.github.com/scivola/bc61a59c47b72d446c1c リンク切れ
  • 異体字データベース 各種文献に記載されている異体字・関連字情報を収集・整理したもの. 素晴らしい。