VRRPってなにもの?
どうも、こんばんは!
最近ブログの更新頻度が低くなってます。😂
問題ばっかり解いてるせいか、書くことがない🤔
本日は、応用情報H29年春の午後問題「ネットワーク」について、知らない用語が出てきたので整理したいと思います。
用語は以下2つです。
- ICMPリダイレクト
- VRRP(Virtual Router Redundancy Protocol)
ICMPリダイレクト
まず,下図のようなネットワークがあったとします。
端末Aは以下のパケットを送ろうとしています。
宛先IP:192.168.2.10
端末Aのルーティングテーブルには,宛先IPが所属するネットワーク宛てに該当するレコードがないためデフォルトゲートウェイにパケットを送信します。
つまりパケットはルータAに送信されます。
宛先「192.168.2.10」は「192.168.2.0/24」ネットワークに属しているため,ルータAはパケットをネクストホップである「192.168.1.2」のルータBに送信します。
と同時に
ルータAは端末Aに対して「192.168.2.0/24」ネットワーク宛てのパケットはルータBが適切なゲートウェイですよーと教えてあげます。
これがICMPリダイレクトです!!
これを受信した端末Aのルーティングテーブルは以下のように一時的に更新されます。
以降の「192.168.2.0/24」ネットワーク宛てのパケットはリダイレクトルートであるルータBに送信されます。
VRRP(Virtual Router Redundancy Protocol)
これはズバリ、デフォルトゲートウェイを冗長化するためのプロトコルです。
では,どのようにして冗長化しているのか。
それは複数のゲートウェイを仮想的に1つのゲートウェイに見せることで,冗長化しています。
ストレージの仮想化と原理的には同じですね。
具体的にどのようにして1台のゲートウェイに見せているのかは以下の図で説明します。
図の例では,ルータA,Bを用いて冗長化を行なっています。
まず,2台のうちマスタールータとバックアップルータを決定します。
これは,「VRRP priority」という優先度を設定し,値の高い方がマスターとなります。
パケット処理はマスタールータが行います。
続いて,「VRRP group」により冗長化するルータのグループングを設定し,そのグループで「仮想IPアドレス」,「仮想MACアドレス」を設定します。
この仮想IPアドレス,仮想MACアドレスがこのプロトコルのミソです。
もしもマスタルータに障害が発生し,バックアップルータが処理を引き継いだとします。
このとき,外部の端末はデフォルトゲートウェイなどの設定の変更は必要ありません。
今まで通り仮想IPアドレス,仮想MACアドレス宛てにパケット送信することが可能です。
そして,マスタールータが「アドバタイズメント」というパケットをバックアップルータに送信することでマスタルータの死活監視を行います。
バックアップルータがこのパケットを一定時間以内に受信できない場合,マスタルータがダウンしたとみなし,バックアップルータがマスタールータに切り替わりパケット転送処理を行います。
また,よく似たプロトコルにHSRP(Hot Standby Router Protocol)があります。
このプロトコルとVRRPとの違いとしては,仮想IPアドレス設定の点にあります。
VRRPでは仮想IPアドレスにマスタルータの物理IPアドレスを指定することができます。
また,普通はそのように設定するらしいです。
一方で,HSRPでは仮想IPアドレスには物理IPアドレスとは別のアドレスを指定しなければいけません。
とまあ、このような違いがあります。
というわけで今日はこの辺で終わりたいと思います。
最後まで読んでいただきありがとうございます。
それではまた👋
等価交換について
久しぶりにブログ更新します。
最近「鋼の錬金術師」のアニメ版1期目を一気見していたり、研究室の飲み会やらでブログ放置しておりました。
鋼錬1期はアニメのオリジナル要素が強い印象だったので、見るのを敬遠してきたのですが、とても面白かったです。
色々考えさせられましたね。
特に等価交換は成り立たないっていう主張が響きましたね。以下引用。
エド「等価交換だ。馬鹿なことを続けてきたリバウンドだろ」
ダンテ
「等価交換。まだそんな子供の理屈を信じてるの?」
エド「理屈じゃない。錬金術は、いや、この世界の原則だ。
あんただってそう言ってたじゃないか。何かを得るためには同等の代価が必要になる」
ダンテ「子供に限って言うものよ。
何でも平等にしろとか、それじゃあ不公平だとか。
でもね、等価交換なんて無いわ。
何かを得るためには代価が必要、だったら逆に、代価を払えば必ず何かを得られるのね」
エド「そうさ、だから人はその代価を払うために努力する」
ダンテ「でも変ねえ。だって、同じ代価を払っても、同じものが得られるとは限らないわ」
エド「それは」
ダンテ「国家錬金術試験てあったわよね。
それに通るために、何人もが勉強に時間を費やす、それは代価。
でも実際に通るのはほんの一握り。
そもそも錬金術は同じように学んでもその実力には大きな差が生まれる。
そして人の命も平等ではない。そのままじゃ、赤ん坊は死ぬわね」(赤ちゃん人質)
エド「やめろ」
ダンテ「本当に簡単に殺すことができる。
なら、その子はただ死ぬだけに生まれてきたの。その子は努力して日々必死に生きるための代価を払っている。でも、それで得られるのは死、だけ。
一方で、人を殺しても生き延びている者はいるわ。
どんなに生きるための努力をしても、人は死ぬときには死ぬ。
なんの努力もせず、富や権力に恵まれて一生幸福に過ごす者に比べれば、随分と不公平ね。この世は随分と残酷ね。それ故に美しいともいえるけれど」
エド「詭弁はやめろっ」
ダンテ「等価交換というのは、弱者が自分を慰める言い訳なのよ。
代価を支払えば自分はもっと幸せになれるはずなのに」
引用元:アニメ「鋼の錬金術師」一期 セリフ抜き出し | *日本猫の日記*
何かを代償にしたからといって、同等の代価が得られるとは限らないんですね。
いや、厳密には人によって見返りには差があるといった感じでしょうか。
勉強に割く時間が同じでも、覚えが早い人や理解力がある人と比べると結果は異なってきます。同じ時間を割いているのに。
考えてみれば当たり前かもしれません。
例えば、AさんとBさんに全く同じ時間、同じテキストで一緒に勉強したとしても、テストの点数や正誤問題が全く同じとは限らないでしょう。
あとは予測できないような外部要因も大きく関わってくるんですね。
まとめると、結果というのは「パーソナル」な要素と「外部要因」にも左右されるために等価交換は成り立たないのですね。納得。
鋼錬の話は以上です。笑
今日は応用情報のH29秋の午後問題を解きました。
特に解説するような難しい問題はありませんでした。
ただただ文章理解力が問われている気が・・・
なので、ここからは作業ログを残すだけになります。
見なくて大丈夫です。笑
プログラミング
ナップザック問題
手順
- 容量制限の表を作成
- <容量制限> - <各種の品物容量>(目的の容量制限値から各種品物の容量制限を引く)
- 1の表中から2の結果に当てはまる最大価値合計を取得
- <目的の価値合計> = <3で取得した最大価値合計> - <2で選択した品物の価値>
TIL/knapsack_problem.rb at master · k12si/TIL · GitHub
データベース
E-R図の関連の見分け方
- エンティティ間で一方の主キーが他方の外部キーである場合「主キー側 → 外部キー側」が成り立つ
- エンティティ間の親子関係に着目「親 → 子」が成り立つ
SQL文
- USINGはJOIN句において,連結する2つの表中に同じ列名が存在するとき,ONの代わりに使用できる。(USING 列名)
- クエリ作成では必要な情報を出力するために,主キーと外部キーの流れに着目する
参考:
応用情報午後試験を6割目指せ! 平成29年度秋 午後問6 データベース - YouTube
以上です。
アマゾンダッシュボタンで勤怠管理
どうも、こんばんは。
アマゾンダッシュボタンを利用した,Google Spread Sheetでの勤怠管理アプリができました!🙌
動作風景は以下のような感じです。
ボタン一個で,出勤のエンドポイントしか叩けていないので,出力も出勤時間のみです。
ボタン一つで,出勤と退勤のエンドポイントの切り分けしたいけど・・・どうしよう🤔
退勤用にボタン買おうかな笑(Dashボタン,エンタプライズ用なら今でも売っているみたいです)
さて,動作手順は以下のとおりです。
- Dashボタン押下
- DashボタンはDHCPサーバにIPアドレスを要求
- DHCPサーバはDashボタンにIPアドレス付与
- DashボタンはLAN内にARPリクエストを送信
- MacがARPリクエストを受け取り,MACアドレスがDashボタンのものと一致している場合API Gatewayのエンドポイントにアクセス
- API GatewayをトリガーにLambdaが発火
- Lambda上でGSSのAPIを用いてシートに日付と時刻を出力
ざっとこんな感じです。
4について詳しく説明します。
まず,ARPというのは
IPアドレスに対応するMACアドレス発見するプロトコルです。
これがわかったところで
なぜ,DashボタンがARPリクエストを送信するかについてですが
DashボタンはIPアドレスが付与されたあと,本当にそのIPアドレスをLAN内の他端末が利用していないか確認します。(DHCPを信用していないみたいですね)
そのためにLANにARPリクエストを送信し,IPアドレスに紐づくMACアドレスが存在しないことを確認します。
あとは比較的,APIやクラウド環境に頼り切った実装となっています笑
改めて,クラウドサービスの便利さを感じました!!
クラウド神だ!!!😙
というわけで,今日はこの辺で👋
GoogleのAPI認証奮闘記
みなさん、こんばんは。
先日から作成していた,「Dashボタンで出勤管理」がエンドポイントで叩けるところまでいけました。
までが完成した感じです。
先日の記事段階では、Lambda上でGoogleのAPIを叩けない状態だったのですが、解決しました。
APIを叩けなかった理由としては
そもそも、以下の記事で掲載した「認証の手順」の認識に誤りがあったからです。
今日は
についてお話ししていこうと思います。
「認証の手順」について
まず,アプリケーション(クライント)がGoogleのAPIを利用するには認証が必要です。
これはアクセストークンを取得するためです。
先日の記事で述べたようにGoogleのAPIを利用するにはアクセストークンが必要です。
そしてそのトークンはOAuthという認可サーバに発行してもらわないといけません。
ここまでは、先日述べた通り正しいと思います。
しかし,ここから認識の誤りがありました。
それは,OAuthによるアクセストークンの発行方法は2種類存在するといった点です。
それが以下です。
- ユーザによる承認方式
- サービスアカウント方式
上の方式名はわかりやすいように勝手につけました。
順番に図で見ていきます。
ユーザによる承認方式
全体像は,前回の図からごっそりサービスアカウント部分を取り除き,yamlファイルを追加した形となります。
前回記事で紹介したクイックスタートはこちらの方式を採用していました。
事前にダウンロードする「credentials.json」はGoogle側で自動作成されたものです。
以下の情報が含まれています。
このクライアントは今回の方式ではユーザによって一時的に承認され,GoogleAPIを利用可能であるため,クライアントIDなどはGoogle側で自動で作成された適当なものとなっている。
認証手順としては上記図の番号通りに遷移していきます。
ポイントとなるのは,以下2点です。
まず1点目について,この方式でAPIを利用するにはユーザによる手動での同意が必要になってきます。
そのため,今回のようなLambda上では動かせませんでした。
さらに2点目ですが,この方式ではアクセストークンの有効期限があります。
アクセストークンを利用し続けるには,yamlファイル中に定義された「refresh_token」にアクセスし,期限の延長が必要になります。
(これをしとけば,初めの一回の同意のみでAPIを利用できそう)
この方式はだいたいこんな感じです。手動での同意が必要という部分が重要ですね。
サービスアカウント方式
こちらの全体像は以下のようになります。
ポイントとしては以下2点です。
まず1点目について。
GoogleAPIを利用するには,ここの理解がとても重要でした。
書いてある通りなんですが,サービスアカウントとはアプリケーション用に作成するGoogleアカウントのようなものです。
この解釈は2点目にもつながってくるのですが,アプリケーションそのものがユーザのような認識なので,ユーザによる同意も必要なくなってきます。
アプリケーションのみでアクセストークンの発行までを自己完結してくれます。
故に,今回のようなLambda環境でAPIを実行したい場合はこちらの認証方式を採用すべきでした。
事前にアプリケーションの実行環境に置いておくJSONファイルの中身は,credentials.jsonとは異なり,詳細なクライアント情報が保持されています。
肝心のサービスアカウント自体は,事前にユーザが作成しておきます。その際,そのサービスアカウントに付与する権限(IAM)も設定します。
そして,今回でいうとスプレッドシートアプリ側の管理者にもサービスアカウントを追加しておかないといけません。(このとき,本当にアカウントみたいな扱いだなと感じました。)
認証方式については以上です。
以下に参考にしたリンクを掲載しておきます。
- RubyでGoogle Calendarをサービスアカウントから操作する - Qiita
- [保存版・初心者向け]AWS LambdaからGoogleカレンダーの予定を取得するのを世界一丁寧に解説 - Qiita
- Google APIを使用するための設定(認証情報の登録) 第2回 - プログラミングノート
- AWS LambdaからGoogle APIを呼び出す - Sanwa Systems Tech Blog
実際にAPIを叩けるまでに行ったこと(Lambda + API Gateway)
まず,行ったことは以下です。
- 認証情報の作成 & サービスアカウントの作成
- Google Spread Sheet の編集権限にサービスアカウントを追加
- 退勤処理の関数作成
- S3に出勤,退勤,apiクライアントファイルを挙げる
- Lambda作成
- API Gateway作成
1,2に関しては上記でも触れたので省略します。
3に関してはソースコードを掲載しますので参考にしていただけたらと思います。
取り上げたいのは4 ~ 6です。
まず,4に関してですが,前記事でも述べていたように
Lambdaにアップロードできるファイルサイズには制限があります。
しかし,S3を経由すればファイルサイズが大きくてもアップロード可能となるために行っています。
5でLambdaを作成したのですが,注意する点としては以下です。
- Lambdaでは呼び出す関数に`event`と`context`を引数に持たせる(必須かどうかは不明だが,指定しないと動かなかった)
- 時刻を日本に合わせるため,環境変数を設定
気をつけるべき点としては上記くらいで,本当に簡単に動かすことができました。
6についても,Lambdaを作成した際,Lambda発火のトリガーを簡単に指定することができます。
1分もしないうちにLambda起動のためのエンドポイントの生成が完了しました。(すごい!!)
しかし,作成したAPI Gatewayのセキュリティを現状オープンにしているため後々変更しようと思っています。(今度はAWSのAPI認証とかの話になってきそう😱)
結果
実際に出力された結果が以下です。
最後のレコード行が,実際に作成したエンドポイントを叩いて出力されている部分です。
最後にソースコードは以下に掲載しています。
TIL/dash_button/attendance_manager at master · k12si/TIL · GitHub
あとは,以前作成したDashボタンでSlack通知のSlackWebhookをエンドポイントにすればできそうです🙌
長くなりましたが,この辺で今日は終わりにします!👋
最後まで読んでいただきありがとうございました!🙇♂️
Lambdaの容量制限
こんばんは。1日サボったら、更新がめちゃくちゃ久しぶりな感じがします。
これだけの頻度で更新していると、1日サボっただけで罪悪感がすごいんですよね。・・・いい傾向だ🤪笑
さて、今日は以下2つのことを行いました。
- 応用情報 H30春午後(DB,組み込みシステム)
- Dashボタンで勤怠管理システム開発
それぞれ学んだことを書いていきます。
応用情報
DB
今回のデータベースも難しかったです。特にSQLクエリを書かせる問題が鬼畜すぎました。
その中で、参考書などに乗っていなかったデータ操作言語が2つ出てきたので載せておきたいと思います。
どちらも表を結合する役割があります。
❶SELECT <列1> FROM <表1> INNER JOIN <表2> ON <結合条件>
これは「表1中の列1を取得した上で,結合条件に従って表2からも値を取得し1つの表にする」です。
例えば,以下ような2つの表があったとします。
社員テーブル
ID | 社員名 | 部署ID |
---|---|---|
1 | Aさん | 1 |
2 | Bさん | 2 |
3 | Cさん | 1 |
4 | Dさん | 4 |
部署テーブル
ID | 部署名 |
---|---|
1 | 営業部 |
2 | 経理部 |
3 | 開発部 |
このとき
SELECT * FROM <社員> INNER JOIN <部署> ON <社員.部署ID = 部署.ID>
を実行すると、結果は以下のようになります。
ID | 社員名 | 部署ID | ID | 部署名 |
---|---|---|---|---|
1 | Aさん | 1 | 1 | 営業部 |
3 | Cさん | 1 | 1 | 営業部 |
2 | Bさん | 2 | 2 | 経理部 |
重要なポイントは以下です。
- ベースとなる表は<表1>(FROMで指定されている表が出力)
- 結合の対象がいないベース表中のレコードは削除
❷SELECT <列1> FROM <表1> LEFT(RIGHT) OUTER JOIN <表2> ON <結合条件>
こちらも基本動作は上記と同じです。
ただし,
- LEFTを指定した場合,ベース表は<表1>
- RIGHTを指定した場合,ベース表は<表2>
- 結合の対象がいないベース表中のレコードも残す
例えば,前述と同じように以下を実行すると図のようになります。
SELECT * FROM <社員> LEFT OUTER JOIN <部署> ON <社員.部署ID = 部署.ID>
ID | 社員名 | 部署ID | ID | 部署名 |
---|---|---|---|---|
1 | Aさん | 1 | 1 | 営業部 |
2 | Bさん | 2 | 2 | 経理部 |
3 | Cさん | 1 | 1 | 営業部 |
4 | Dさん | 4 | null | null |
以下のブラウザ環境でSQLを実行できるサイトがよかったです。
初めにデータ定義も行わないといけないので,適当なテンプレ載せときます。(自分用)
これらの説明は以下のサイトを参考にさせていただきました。すごくわかりやすかったので,上記でわかりずらかった方はこちら見ていただきたいです。
SQL素人でも分かるテーブル結合(inner joinとouter join) - Qiita
組み込みシステム
文章問題って感じで,特に書くことない(点数はボロボロでした)😇
Dashボタンで勤怠管理システム開発
はい。やっとタイトルに書いてあることに触れるためにのスタートラインに立ちました。笑
ここからは,前回記事の続きです!
やったことは以下です。
厳密にはLambda上で動かすを行っている段階で,rubyで利用するGoogleAPIのファイルをLambda場にアップロードしようとしました。
すると,10MByte以上は上げれないと・・・。
しかしS3に一旦zipを保存したらあげることができました!
コード編集できないけど,関数の実行はできるみたいです!!ってことにこのブログを書いてて気づきました笑
ジャパニーズでめっちゃわかりやすく書いてくれてた。笑
エラー出ているので,またLambda上で動かせたら報告します。
(アクセストークンの認証とかであんまり上手く行く気がしない😰)
最後にスプレットシート出力のスクリプトを書いていて詰まったことを書きます。
スプレットシートに日時を出力
GoogleのAPIを利用するときに,いつも詰まるのがアクセストークンの取得です。
正直何をしているのかさっぱりです。
OAuthやらサービスアカウントやらIAMやらcredentials.jsonやら環境変数やら。。
「何してんの!?(^ω^)」って感じです。
しかし,クイックスタートで上記のような認証を何も考えず,すぐにAPI使えちゃいました。
以下のメソッドでレコードに追加できました!
Method: spreadsheets.values.append | Sheets API | Google Developers
Rubyコードでパラメータの渡し方が載っていなかったので,載せておきます。
さて,これでシートに追加されると思ったのですが,以下のエラーが出ました。
forbidden: Request had insufficient authentication scopes. (Google::Apis::ClientError)
はい、出た。
権限エラーだ。🤯🤯
結論から言いますと,自分のコードのAPIでのスコープがリードオンリーになってたことが原因でした。
そうとは思わず,上記で書いたような用語を調べていて,ざっくりですが理解できたのでメモとして最後に残しておきます。
まず,OAuthとは認可サーバです。
アプリケーションなどのクライアントがAPIをリクエストするためのアクセストークンを発行しています。
以下にGoogleAPIを利用するまでの流れを図で示す。(実際に行ったわけではないので誤りがあるかもです🙇♂️)
サービスアカウントとはアプリケーションなどのクライアント用に,アクセストークンを発行するためのアカウントである。
IAMとはアカウントに付与する権限のこと。
また,サービスアカウントでアクセストークンを発行するために必要となってくるのが,credentials.jsonなどのファイルである。(などと付けたのはJSONファイル以外の形式で,サービスアカウントキーを取得する方法があるため)
このファイルを持って,OAuth認証を行う事で,アクセストークンが記述されているYAMLファイルが取得できる。
以上です。
なお,OAuthに関して以下のサイトがとてもわかりやすかったです。
書いていてもまだまだ腑に落ちない部分が多く,完全に理解して書いているわけではないです。🙇♂️😂
また調べてわかり次第,編集したいと思います。
しかし、エラーの原因がこういった事では全くないということに2時間調べてわかりました。
最後にスコープ範囲をリードオンリーから編集許可に変更し,実際にスプレットシートに出力した結果を貼っておきます。
ソースコードも貼っておきます。
まだ作成段階なので,途中でリンク切れするかもです。
TIL/going_work_time.rb at master · k12si/TIL · GitHub
それでは,今日はこの辺で👋
DNS難しい。。
今日も応用情報技術者試験でわからなかったことをメモしていこうと思います。
今回は、最終的に疑問で終わるのでわかる方コメントいただけたら幸いです。
今日はH30春の午後の「アルゴリズム」と「ネットワーク」を解きました。
アルゴリズム(ナイト巡回問題)
アルゴリズム「ナイト巡回問題」というもので結構簡単でした。
解いてて思ったのですが、アルゴリズムは字面だけで追っていてはダメだなと思いました。
今回、文章を読みながらアクティビティ図?のようなものを書いて理解していったのですが、問題の理解が劇的に違いました。
さらに設問を解く際、文章を読み直すことが圧倒的に減ったので、今度からはアクティビティ図を記述して解くことを心がけます。
以下が実際の図になります。
自分用の作業ログとして掲載しているので、見なくて大丈夫です笑
簡単そうだったのでプログラムも作成してみました。
TIL/night_patrol_problem.rb at master · k12si/TIL · GitHub
問題を解いていた時は「移動順序を取り消す」というプログラム部分がどんな役割をしているのかわかりませんでした。(ここ問題読んでいる前提で話します。🙇♂️)
しかしコードを書いていて、とてもよくできているなと感じました。
プログラムは再帰を用いて巡回のパターンを総当たりで探しています。
この時、同じ盤面を上書きしているので、1パターンを試したら、分岐点以降の盤面に上書きした移動順序を「0」に戻さないといけません。
ネットワーク
DNSについて問われる問題でした。
DNSはレコードの種類など全く覚えていなかったので、いい勉強になりました。
さて、問題を解いていて、最後の設問にクラウド型のWAFを用いてwebサーバを公開するといった流れがありました。
その時のリクエストの流れがよくわかりませんでした。
クラウド型のWAFのFQDN(ドメイン名)は以下の通りです。
` waf-asha.example1.ne.jp `
WAF導入前のシステム構成は以下です。
また、マスタDNSサーバのゾーンファイルは以下のようになっています。
文章中で述べられているリクエストの流れとしては以下です。
- Webサイトの利用者は,始めにWAFサービスのFQDNであるwaf-aha.example1.ne.jpにアクセスする。
- WAFサービスで通信パケットが検査される。
- パケットに問題がないとき,そのパケットがA社のWebサイトに転送される。
このとき、利用者はWAF導入前のアクセス方法同様` w3.example.co.jp `でwebサイトにアクセスできるようにしたい。
そのために、マスタDNSサーバのゾーンファイルに以下のようなCNAMEレコードを追加しました。
さて、やっと本題なんですが笑😂
このアーキテクチャにおけるクライアントのリクエストの流れがわからない!!
厳密に言うと、CNAMEでクライアントに` waf-asha.example1.ne.jp `を返した後、クライアントのリクエストはWAF経由でもう一度マスタDNSサーバに行くのかどうかがわからない。
そしてもっというと、本来以下のように定義されていたレコードのownerフィールド(w3)はCNAMEを設定したために変更しないといけない。
このownerフィールドは何になるんだろう?🤔🤔
この段階ではわからないのかな??🤔🤔🤯
一応自分の中でイメージしているリクエストの流れを図にしておきます。
とりあえず、問題は解けたから・・・・いいか・・。
ざっくりしていて、コメントしづらいかもですが、わかる方いればコメントいただけたら幸いです。🙇♂️
それでは今日はこの辺で👋
ウェーブレット木修正
こんばんは。
前回、
上記の記事で、ウェーブレット木について記述しました。
その後友人から、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
です。自分用の備忘録として載せときます。
それでは今日はこの辺で👋