はじめに
先日、ちょっとした飲み会で、知り合いに、ダブルアレイのことを聞かれました。ダブルアレイはインデックスされた文字列を取り出せるのかと。
確かに、よく見る記事には
- 基本構造
- 検索方法
- 構築方法
- 高速検索の性質
あたりは書かれておりますが、Leaf ノードから Root にたどってインデックスされた文字列を取り出す話はあまりありません。
元論文:An Efficient Digital Search Algorithm by Using a Doble-Array Strcuture
にもざっと見たところ説明がないような気がしました。
基本的なダブルアレイの説明はすっ飛ばしますが、
簡単な説明だけ。
- ダブルアレイはトライ木の実装の一つ。
- トライ木とは、ノードにラベルのついたtree構造で、テキスト辞書などに使われる
- ダブルアレイとはトライ木を、二つの値の配列で表現し、ラベルの値から子ノードの位置が計算できるように実装されている。そのため検索が非常に高速である
サンプルデータ
ここでは、ラベル(文字)と文字コードの対応を {NUL}=0, 'a'=1, 'b'=2, 'c'=3 とします。
また、インデックスに a, ac, b, ba の文字列を格納し、それぞれ文字列が指すデータへのオフセットを DataOffset(x) とします。
これをダブルアレイのメモリイメージにすると以下になります。
| Address | Base | Check | comment |
|---|---|---|---|
| 0 | 0 | 0 | Rootノード |
| 1 | 3 | 0 | aのノード、Address3 が a の子ノードの先頭 |
| 2 | 4 | 0 | bのノード、Adresss4 が b の子ノードの先頭 |
| 3 | -DataOffset(a) | 1 | a{NUL} のノード |
| 4 | -DataOffset(b) | 2 | b{NUL} のノード |
| 5 | -DataOffset(ba) | 2 | ba のノード |
| 6 | -DataOffset(ac) | 1 | ac のノード |
この構造で、ba を検索するには、root ノードのAddress 0から始めて
Base(0 + 'b') = Base(2) = 4 を取得します。また、Check(0 + 'b') = 0 なので到達可能。
次に a を検索します。
Base(Base(0 + 'b') + 'a') = Base(4 + 'a') = Base(5) となり、データへのオフセット -DataOffset(ba) を取得し、負数なのでデータオフセットとして処理をします。
また、Check(Base(0 + 'b') + 'a') = Check(4 + 'a') = Check(5) = 2 これは、親ノードの "b" のアドレスと等しいので到達可能です。
気をつけてほしいのが、check には親ノードのアドレスを持たせているところです。
では、Leaf から辿ってみましょう
Leafノードのアドレス 5 から、ラベルを取得しながら、root にたどっていきましょう。
Check(5) = 2は親ノードのアドレスです。Base(2) = 4 が、親ノードから見た子ノードの先頭を表します。したがって、子ノードの先頭アドレスから、Leaf ノードのアドレスを引けば、Leaf ノードの文字コードが取得できます。
つまり、(5 - 4) = 1 となり、最後の文字の 'a' の文字コードを取得できました。
すなわち (NodeAddress - Base(Check(NodeAddress))) を計算することで、NodeAddress の文字コードが取得できることになります。
次に、一つ親のノードのアドレスが 2 だとわかったので、(2 - Base(Check(2))) = 2 となり、'b' の文字コードが取得できました。
その次は、Check(2) が 0 で、ルートに到達したので終わりです。
サンプルコードで表すと、以下のような感じでしょうか。
std::string GetStringFromLeafNode(int nodeId)
{
std::string keyString;
while (nodeId != 0) {
int ch = nodeId - Base(Check(nodeId));
keyString += ch;
nodeId = Check(nodeId);
}
std::reverse(keyString.begin(), keyString.end());
return keyString;
}
使い道
日本語辞書のように、読みから漢字、漢字から読みの両方を引けるようにしたいときに、読みには漢字インデックスの終端ノードアドレス、漢字には、読みインデックスの終端ノードアドレスを入れることで、文字列データを別の場所に保存する必要がなくなります。
まとめ
- ダブルアレイで、ノードのアドレスから、そのノードに対応するインデックスされた文字列を取得する方法を示した。