アスペ日記

情報系修士にもわかるLOUDS

「情報系修士にもわかるダブル配列」が好評だったので、二匹目のどじょうを狙って、「日本語入力を支える技術」でダブル配列と並べて解説されていた LOUDS についても書いてみる。

注意点。

• LOUDS は本質的に難しい。流し読みではまずわからない。
• ダブル配列の「ずらしてガッチャンコ」のようなわかりやすいキーワードはない。
• ここでは簡潔ビットベクターはブラックボックスとして扱い、中には踏み込まない。
• trie がどのようなものであるかは前回の記事の該当部分を参照。

以上を踏まえて、覚悟のある人は読んでください。

今回の記事は、「わかりやすい！」「これで LOUDS わかった！」というブコメ続出…ということにはなかなかならないと思う。ひとつひとつの数字が出てくるたびに、それが図や表でどこに対応するかを確認して、ゆっくり読んでください。

まず、LOUDS は trie の表現に使われているということで、今回も辞書に入れる単語を考える。

今回入れるのは、

an

i

of

one

our

out

ということにする。

すると、trie は次のようになる。今回、ノード番号は「幅優先」（根のほうから浅い順）でつける。

trie としては上のようになるのだが、LOUDS というのは基本的に「木構造」を扱うデータ構造だ。

なので、まずは基本となる LOUDS について考えるために、ラベルを取り去った裸の木を対象とする。木は次のようになる。

ここで、「木構造」というものの性質について復習をする。

木構造の性質の中で LOUDS を考える上で重要となるのは、「根以外のすべてのノードは一つだけ親を持つ」というもの。

ノードは、子を複数持つことはある。例えば、1番は 2番, 3番, 4番 という 3つのノードを子として持っている。また、子を持たないこともある。例えば、3番・5番・6番…は子を持たない。

しかし、親を持たないノードは（根である 1番以外は）ない。また、複数の親を持つノードもない。3番は 1番、6番は 4番、11番は 8番と、それぞれ 1つの親を持っている。この性質が後々効いてくる。

ここで、根が親を持たないということが例外になっているので、そのままだと後で扱いが面倒になる。そこで、根である 1番の上に、仮想的な「0番」を追加する。図は次のようになる。

追加した 0番は親を持たないが、これは元の木には存在しないものなので、操作する上で問題にはならない。

さてここで、LOUDS のキモとなる「LBS」というものを導入する。

これは、「0番を含めたすべてのノードについて順番に、それが持つ子の数だけの "1" を置き、それに続けて 1個の "0" を置いて作ったビット列」。

今回のツリーについては、次の表のようになる。

「親」の欄はわかりやすくするためのもので、実際のデータとしては持っていない。

左から見てみる。まず 0番は、1番という 1個の子を持つので、"1" を 1個置く。それに続けて、1個の "0" を置く。1番は、2番・3番・4番という 3個の子を持つので、"1" を 3個置く。それに続けて、1個の "0" を置く。2番は 5番という 1個の子を持つので、1個の "1" と 1個の "0" を置く。3番には子がないので、"1" を 0個置く、つまり置かない。1個の "0" だけを置く。

さて、この "1" は何を意味するか。

結論から言うと、この "1" というビットひとつひとつが、それぞれのノードが持つ子ひとつひとつを表している。例えば、1番ノードの 3つ目の子、つまり 4番ノードは、LBS の中で左から見て 5ビット目の "1"（1011 "1" 0100...）によって表される。もうひとつ例を挙げると、4番ノードの 2つ目の子、つまり 7番ノードは、左から見て 11ビット目にある "1" によって表されることになる。1番ノードは、0番の子として扱うため、左端の "1" になる。

どのビットがどのノードに対応するかを表にすると、次のようになる。

「子」というラベルの行が、対応するノード。「親」と同じく説明のためのものなので、実際のデータとしては持っていない。

ここで、次の 2つが成立する。

1. ある位置の "1" というビットによって表されるノードの番号は、その "1" が左から数えて何個目の "1" であるかと一致する。
2. ある位置の "1" というビットによって表されるノードの親ノードの番号は、その "1" の左に何個の "0" があるかと一致する。

まず 1 について、直感的に見てみる。上の表を再掲する。

この表を見ると、"1" は順番にノードに対応しているので、あるビットが LBSの中で何個目の "1" であるかということと、そのビットが表すノードの番号が一致していることがわかる。

次に、2 について。

表を再掲。

ある子から見た親のノード番号というのは、表の「親」の行にあるもの。例えば、ノード番号 7 の親は、「子」の行で 7 とある列の上を見ると 4 なのでノード番号 4。しかし、この「親」の行は実際のデータとしては持っていない。

ここで注目するのが、「それぞれの親は、ひとつずつ "0" というビットを 1つだけ最後に持っている」ということ。

例えば、「子」が 7 となっているところの上段に注目すると、それが親が 4番であるブロックに属していて、左には 0番・1番・2番・3番をそれぞれ親とするブロックがあることがわかる。そして、それら 1つずつ最後に "0" を持っているため、合計 4個の "0" があることになる。

つまり、「子」が 7 となっているところの "1" の左に何個の "0" があるかを調べて、4個あるということがわかると、親が 4番ノードであるということがわかるということだ。

また逆に、ビット列の中で 4つ目の "0" を探すと、それがちょうど 4番ノードを親とするブロック（表の中で、子が 6,7,8 となっているブロック）の始まりのすぐ左になる。どこからが 4番ノードを親とするブロックかを知りたければ、4つ目の "0" を探して、その 1ビット右を見ればいいということ。

（ここで、意図的に説明を飛ばしたところがある。「ある位置 x の左に何個の "0" があるかを速く調べる方法」や、「左から x 個目の "0" がどこにあるかを速く調べる方法」など。これはビット列に追加データを付属させた「簡潔ビットベクター」というもので実現できるのだが、ここではブラックボックスとして扱い、「そういう黒魔術がある」ということにしておく。ここに踏み込むとパンドラの箱を開けることになるので。そのうち独立した記事として解説するかもしれない）

さて、ビットを指し示すのには番号があったほうがいいので、表に 0 から始まるビット位置を追加する。それが次の表。

例によって、実際のデータとして持っているわけではない。

この表で見ると、例えば 7番ノードのビット位置は 10（上で書いた「左から見て 11ビット目」）にあることがわかる。

今後、それぞれのノードを指すのに、表の「子」に対応する「インデックス」、つまりビット位置を使うことにする。つまり、4番ノードはビット位置 4、7番ノードはビット位置 10、という風になる。

木構造のラベルとしてビット位置を使うと次のようになる。

元の木構造で「8番ノードの子は 10番と 11番」のように表されていたものは、ビット位置を使うと、「ビット位置 11のノードの子は、ビット位置 17 と 18 のノード」ということになる。元の木構造に仮想的に追加した 0番ノードはここでは出てこない。元の 1番ノードが、ビット位置 0 になる。

このように、ノードを示すのにはビット位置を使うことにする。ただ、元の「ノード番号」を使う場合もまだある。ノードを指定するにあたって、ノード番号で表す時は「○番（ノード）」、ビット位置で表す時は「ビット位置○（のノード）」と書くことにする。

この「ビット位置」のほうを使って、

• 子から見て、自分の親がどれかを取得する
• 親から見て、子の一覧を取得する

という 2つの操作を行いたい。

例えば、ビット位置 17 のノード（10番ノード）から見て、親がビット位置 11 のノード（8番ノード）であることがわかればいい。

また逆に、ビット位置 11 のノード（8番ノード）から見たら、子がビット位置 17, 18のノード（10, 11番ノード）であることを知りたい。

まず、ビット位置 17 のノードから見て、親がビット位置 11 のノードであることを知る方法から。

表を再掲。

表を見れば、ビット位置 17 のノード（10番ノード）は、親が 8番ノードであるブロックに属していることがわかる。

ただ、すでに書いたように、この「親」の行は解説のためのもので、実際のデータ構造では持っていない。

ここで、上で書いた「ある位置の "1" というビットによって表されるノードの親ノードの番号は、その "1" の左に何個の "0" があるかと一致する」ということを利用し、ビット位置 17 より左に何個 "0" があるかを数える。

数えてみると、"0" は 8個。親のノード番号は 8 ということ。

後は、8番ノードに対応するビット位置がわかればいい。

ここで今度は、「ある位置の "1" というビットによって表されるノードの番号は、その "1" が左から数えて何個目の "1" であるかと一致する」ということを利用する。

8番に対応するビットは、左から 8個目の "1"。インデックスでいうと 11。

こうやって、「ビット位置 17 のノードの親は、ビット位置 11 のノードである」ということがわかったことになる。

今度は逆に、ビット位置 11 のノード（8番ノード）から見て、子がビット位置 17, 18のノード（10, 11番ノード）であることを知る方法。

表を再掲。

ビット位置 11 のノードが 8番ノードであることは、インデックスで 11 となっている列の「子」の欄を見ればわかるが、やはり実際のデータ構造では持っていない。

そこで、ビット位置 11 の "1" が、左から見て何個目の "1" であるかを調べる。そうすると、8個目の "1" であるので、自分が 8番ノードであることがわかる。

そして、「親が 8番ノードであるブロック」を探すには、上で書いたように、「8個目の "0" を探して、そのすぐ右」を見ればいい。

8個目の "0" は、ビット位置 16。親が 7番であるブロックの一番最後。そこから 1つ右のビット位置 17 からが、親が 8番であるブロック。ビット位置 17 から始めて右に見ていって、"1" が続いている間は自分の子ということになる。つまり、ビット位置 17, 18 の 2つ。

これで、ビット位置 11 のノード（8番ノード）の子が、ビット位置 17, 18のノード（10, 11番ノード）であることがわかった。

ところで、「親が 1番ノード（根）であるブロック」の開始位置は、表を見てもわかるように、ビット位置 2 で、ノード番号は 2 になる。このことは後で使う。

ここまでで、木構造としての LOUDS の説明は終わり。ここから先は、trie として LOUDS を使う話。頭がいっぱいいっぱいになった人はいったん休んでください。

さて、元の trie の図を再掲。いったん休んだ人は、上の説明を読み直して復習してください。

これを見て気づくのは、「1 を除いたすべてのノードは、親から自分に来るエッジをひとつだけ持っていて、それにはラベルがついている」ということ。つまり、それぞれのノードが、自分に来るエッジについているラベルを覚えておけばいい。

次のような、ノード・ラベル対応表を用意する。

これで、trie として使うことができる。例として、この trie で "ous" という文字列が入っているか（実際は入っていない）を調べる手順を示す。実際のデータ構造に合わせて、LBS とインデックスだけの表を示す。ハードモードになるので注意。

1. 上で書いたように、根を親として持つブロックは、ビット位置 2 の 2番ノードから始まる。
2. ノード・ラベル対応表で、2番ノードに対応するラベルを調べる。それは "a" で、"ous" の 1文字目である "o" と一致しないので、次の子があるかどうか見る。
3. ビット位置 2 の次、ビット位置 3 を見る。"1" なので、子がまだ続いていることがわかる。次の子は、今見ていた 2番ノードの次、3番ノードである。
4. 3番ノードに対応するラベルは、対応表より "i"。"o" と一致しないので、次の子があるかどうか見る。
5. ビット位置 3 の次、ビット位置 4 を見る。"1" なので、子がまだある。次の子は、今見ていた 3番ノードの次、4番ノード。
6. 4番ノードに対応するラベルは、対応表より "o"。一致したので子に移動し、4番ノード/ビット位置 4 を今のノードとする。
7. 4番ノード/ビット位置 4 のノードを親として持つブロックを調べる。ノード番号が 4 なので、左から 4個目の "0" のすぐ右。ビット位置 9 からが、子のブロックということになる。
8. ビット位置 9 に対応するノード番号を調べる。何個目の "1" であるかを見ればいい。数えてみると 6個目なので、6番ノードということになる。
9. 6番ノードに対応するラベルは、対応表より "f"。"ous" の 2個目の文字である "u" より前なので、次の子があるかどうか見る。
10. ビット位置 9 の次、ビット位置 10 を見る。"1" なので、子がまだある。次の子は、6番ノードの次、7番ノード。
11. 7番ノードに対応するラベルは、対応表より "n"。"u" より前なので、次の子があるかどうか見る。
12. ビット位置 10 の次、ビット位置 11 を見る。"1" なので、子がまだある。次の子は、7番ノードの次、8番ノード。
13. 8番ノードに対応するラベルは、対応表より "u"。一致したので子に移動し、8番ノード/ビット位置 11 を今のノードとする。
14. 8番ノード/ビット位置 11 を親として持つブロックを調べる。ノード番号が 8 なので、左から 8個目の "0" のすぐ右。ビット位置 17 からが子のブロックということになる。
15. ビット位置 17 に対応するノード番号を調べる。何個目の "1" であるかを見ればいい。数えてみると 10個目なので、10番ノードということになる。
16. 10番ノードに対応するラベルは、対応表より "r"。"ous" の 3個目の文字である "s" より前なので、次の子があるかどうか見る。
17. ビット位置 17 の次、ビット位置 18 を見る。"1" なので、子がまだある。次の子は、10番ノードの次、11番ノード。
18. 11番ノードに対応するラベルは、対応表より "t"。"s" より後になってしまったので、検索失敗。

と、このように trie 検索ができる。

どのノードが単語終端になるかの情報は、例によってどこか（遷移ラベルとか）に 1 ビット紛れ込ませておくなりすればいい。

実際にこの手順をたどってもらえたらわかると思うが、例えば手順 15 で、ビット位置 17 に対応するノード番号を調べるために、そこの "1" が何個目の "1" かを調べるのは面倒くさい。位置が後ろになっていけばいくほど面倒になっていく。そういうわけで、どれだけ位置が後ろでも、あるビットが何個目のビットか、また何個目のビットがどこにあるかがすぐわかるデータ構造が必要で、それが「簡潔ビットベクター」ということ。

「位置 x の 0/1 のビットは何個目の 0/1 のビットか」を調べる関数は rank、「x 個目の 0/1 となるビットはどこの位置にあるか」を調べる関数は select と呼ばれる。

ところで、「日本語入力を支える技術」には、rank 関数の低速な実装例として次のような擬似コードが載っている。

def rank(B, pos, b)
    count = 0
    for i in 0 to pos-1
        if B[i] == b
            count += 1
    return count

これは、「位置 x より左に何個の 0/1 があるか」を調べることになり、「何個目か」より 1個少なくなる。この流儀の rank 関数もあるというが、後の説明との整合性を考えたら、3行目は

    for i in 0 to pos

が正しいのだろう。

Permalink | コメント(0) | トラックバック(0) | 16:37