すぴすらのろぐ

読んだもののメモとかポエムとか

辞書式順序とユーザ定義型

トライ木(Trie)というデータ構造がある。トライ木についてはWikipedia (ja)Wikipedia (en)を参照。

トライ木の特徴

トライ木はMap(やSet)インターフェイスを持つCollection/Containerとして使うことができる。

トライ木が比較処理ベースの木構造と異なる特徴の一つは、キーの挿入や探索の際の計算コストが挿入済のキー数に依存しないところ*1。 対して比較処理ベースの木構造における挿入や探索のコストは、挿入済のキー数の対数に比例した計算コストがかかるので、キー数が多くなるとトライ木が有利になる。

トライ木と比較処理ベースの木構造の違いはがどこからくるのかを感覚的に言うと、トライ木は挿入されるキーの位置がキーの値の絶対的な位置により決まるのに対し、比較処理ベースの木構造は(他のキーとの)相対的な位置により決まるから、と言える。

トライ木には欠点もあり、データ構造のフットプリントが大きくなりがちな点と、キーの分布がスパースだったりするとさらにメモリの利用効率が落ちる点等がある。

トライ木はまた、Orderd-Mapインターフェイスを持つCollection/Containerとしても使うことができる。 これには条件があり、トライ木における「文字」集合に全順序があり、キーの順序が文字の辞書式順序に一致する場合に限る。

辞書式順序

辞書式順序は、順序集合が与えられたときその要素からなるシーケンス間に順序を与える一つの方法である。 Wikipedia (ja)Wikipedia (en)

一つの方法と書いたけど、納得しやすい自然な順序だと思う。

Collection/Containerクラスとユーザ定義型

プログラミング言語のMap Collection/Containerクラスや、データベースのインデックスは、通常、ユーザ定義型に対して開放されている。 その場合、ユーザ定義型に以下のような比較インターフェイス(二項演算)の実装を要求する。

  • equal: 2つの値が等しいなら真を、そうでないなら偽を返す

Ordered Mapであれば、さらに以下のようなインターフェイスの実装を要求する。

  • less-than(またはmore-than): 左辺の値のほうが小さいなら真、そうでないなら偽を返す (または、memcmp関数のように、左辺のほうが小さい、等しい、左辺のほうが大きい、それぞれに対応して、負、0、正を返す関数かもしれない。)

ここから透けて見えるのは、そのCollectionクラスやインデックスの実装は比較処理ベースの木構造であって、トライ木やその亜種ではないということだ。

トライ木とユーザ定義型

抽象的なデータ構造としてのトライ木は、その「文字」集合に対して何の制約もないが、トライ木の一つの実装で任意のユーザ定義型をカバーする状況を考えて、以降では「文字」を0x00~0xFFの256通りの値を持つものとし、その「文字列」(バイト列/オクテット列)を扱うトライ木を考える。

あるユーザ定義型のMapデータ構造としてトライ木を使うためには、そのユーザ定義型の値がある条件を満たすバイト列として表現されうる必要がある。 2つの値をv1とv2、対応するバイト列表現をそれぞれb1、b2とすると

  • v1 = v2 ならば、かつその時に限り、b1 = b2

またあるユーザ定義型のOrdered-Mapデータ構造としてトライ木を使うためには、そのユーザ定義型が以下の条件を満たすバイト列として表現されうる必要がある。

  • v1 < v2 ならば、かつその時に限り、b1 < b2
  • v1 = v2 ならば、かつその時に限り、b1 = b2
  • v1 > v2 ならば、かつその時に限り、b1 > b2

バイト列の比較は、以下のような実装によって定義できる

r = memcmp(b1, b2, min(length(b1), length(b2));
if( r == 0 ) {
  if( length(b1) < length(b2) ) {
    return -1;
  }
  else {
    return 1;
  }
}
else {
  return r;
}

上記のような条件を満たすバイト列表現のことを、ここではmemcmp compatible representationと呼ぶことにする。*2

memcmp compatible representationへの変換1:同値関係

この表現が満たすべき条件の一つ目(同値関係)を満たすような変換や表現は簡単な気がするが、注意点がある。

一つは、そのユーザ定義型の値が等しいとみなせるにもかかわらず、そのNative表現*3が異なる可能性があることである。 例えば、符号付整数型が1の補数表現で実装されている場合で、かつ-0+0を同一視したい場合や、指数表記の1e+110e+0を同一視したい場合などがある。

上記の問題を回避するため、ユーザ定義型の値は正規化(canonicalize)する必要がある。*4

もう一つは、そのユーザ定義型の実装におけるパディングビット/バイトの存在で、これは取り除く必要がある。

memcmp compatible representationへの変換2:大小関係

条件の2つ目(大小関係)を満たすような変換は一筋縄ではいかなさそうである。 そもそも、そのような表現が存在するか?という疑問があったが、存在することは確かだ。*5

組込み型の整数型や浮動少数点数型については比較的簡単であるがユーザ定義型については、世間にどのような比較可能なユーザ定義型があるかわからないので何とも言えない。

ユーザ定義型が、組み込み型に対して値の範囲を制限するようなタイプなら簡単で、元の組込み型に対する表現をそのまま使えばよい。*6

ユーザ定義型が、複数の組み込み型からなる複合型の場合は、順序がどう定義されるのかによる。 そのユーザ定義型のless-than関数が、例えば以下のような複合型の各要素をある順序で順に比較していくような形式ならば、これはある種の辞書式順序とみなせるので、変換は簡単である。

if( v1.c1 != v2.c1 ) {
  return v1.c1 < v2.c1 ;
}
else if( v1.c2 != v2.c2 ) {
  return v1.c2 < v2.c2 ;
}
else {
  return v1.c3 < v2.c3 ;
}

上記の例の場合は、ユーザ定義型の要素c1を変換したバイト列、要素c2を変換したバイト列、要素c3を変換したバイト列を連結すればよい。

文字列型のmemcmp compatible representation

ここでいう文字列型は、プログラミング言語やデータベースにおけるstring型のことで、トライ木における「文字列」とは関係がない。

文字列型の順序付けにはCollationという概念があり、私はよく知らないしできればか関わりたくないのであるが、日本人にとってマルチバイト文字が重要なようにCollationが重要な世界もあるのかもしれない。

Collationについてはこちらが詳しいが、C言語には、ロケールに応じてmemcmp compatible representationに変換する、strxfrmという関数が用意されている(すばらしい)ので、これを使いましょう。 (ただロケールによってはとても長くなるらしい。)

まとめ

何が言いたかったかというと、トライ木やその亜種がデータ構造の主役になり切れないのは、ユーザ定義型に対して閉じている(と思われていた)からではないかと思ったため。

本投稿は、トライ木をユーザ定義型に対してオープンにすることが可能で、かつ(よほど凝った順序でない限り)変換関数の実装も容易ではないか、ということを示したかった。

*1:実装によっては比較処理を用いるトライ木もありうる

*2:この表現や、この表現への変換にすでに名前がついていたり、ほかに良い名前があれば教えてほしい

*3:変換前のユーザ定義型の値の表現(通常はこちらもバイト列)

*4:canonicalという表現は、XML SchemaのDatatypesから拝借した

*5:任意の有限な順序集合がが与えられたとき、その集合Aから、1~|A|の範囲の整数の集合への順序を保存する写像全単射)が存在する。その整数をceiling( log256|A| )桁のBig Endianな2進数表現に変換すれば、memcmp compatible representationになる

*6:もっとコンパクトな表現にできる可能性もある