ウェーブレット木修正
こんばんは。
前回、
上記の記事で、ウェーブレット木について記述しました。
その後友人から、log2の対数をとる際、整数じゃない時どうなるのかと聞かれ、
「・・・確かにどうなるんだろう。ちゃんと計算できるのかな。」となりました笑
つまり、文字の種類が2のn乗で表せない場合、木のバランスは崩れるため、文字数のカウントをうまくできるのかということです。
そこで、文字の種類を5種類（「CTCGAGAGTAW」｜Wを1文字加えました。）にして試してみると、結果は以下のようになりました。
「A」、「W」の文字の出現数がおかしなことになってる🤭
前回ソースコードは以下のサイトから拝借させていただきました。
ちゃんと動作したので、そのままあげさせていただいていたのですが、
今回ちゃんとソースコードを読んでみます。
コードは以下2つの関数から成り立っています。
- ウェーブレット木を構築
- 文字出現数のカウント
よく調べていくと、「ウェーブレット木の構築」が4種類の文字用に作成されていました。
冗長的に作成するために修正する点としては以下です。
- 文字の種類計算時、小数点以下を切り捨てている
- 子ノードが「0」,「1」どちらで振り分けられたか、という判定を直前のchild値のみで判断している
- 位置ビットの調整が4種類しか考慮していない
今回は、文字の種類が何種でも対応可能なウェーブレット木を作成していこうと思います。
完成形となる木構造はこちら。
修正点について、以下のように修正しました。
- 小数点以下切り上げ
- childに過去の「0」,「1」も保持し、マスクする
- 位置ビットをDEPTHとdepthを利用し冗長的に表現
以下になぜ、childに過去の「0」,「1」を持たせるのかについての理由を図で説明します。
修正した結果はこちら。
木構造もちゃんと上のイメージ通りになっています！！
木のバランスが取れていなくても、文字種に着目して探索を行うため問題なく出現数をカウントできました。
ウェーブレット木は単に「二分木構造」というだけで、「完全二分木」ではないという点がわかっていなかったです。
なので、文字の出現数をカウントするアルゴリズム自体には修正する点はありません。
つまり、文字が何種類だろうと、ウェーブレット木の考え方で十分探索できます。
最後に以下に修正したソースコードを掲載しておきます。
TIL/h30a_ap_pm3.rb at master · k12si/TIL · GitHub
ついでにrubyを書いていて、|=が何をしているのかわかりませんでした。
色々試してわかりました。
これは右辺と左辺のビット列のORを取とり、左辺の変数に再度代入しています。
key = 1としたとき
key |= 1 であれば key = 1
key |= 2 であれば key = 3
key = 2としたとき
key |= 1 であれば key = 3
key |= 3 であれば key = 3
key = 4としたとき
key |= 3 であれば key = 7
です。自分用の備忘録として載せときます。
それでは今日はこの辺で👋
