読者です 読者をやめる 読者になる 読者になる

きくらげ観察日記

好きなことを、適当に。

Algorithm

PFDSを読む: Binomial Heap

Binomial Heapとは、Binomial Treeというデータ構造を使って作られるヒープです。ここで、Binomial Treeとは、以下のようなデータ構造です。 rankが0であるBinomial Treeは、ただ1つのノードからなるシングルトン r > 0 について、rankがrであるBinomial Tre…

PFDSを読む: Weight-biased Leftist Heap

inkar-us-i.hatenablog.comこちらの記事でLeftist Heapの紹介をしましたが、今回はその亜種であるWeight-biased Leftist Heapを紹介します。 このデータ構造はほとんどLeftist Heapと同様ですが、rankのかわりに要素数が左に偏るようになります。すなわち、 …

PFDSを読む: Leftist Heapの実装

inkar-us-i.hatenablog.comこの記事ではLeftist Heapについて語るだけで終わっていたので、今回はバリバリ実装していきます。 その前に、Leftist Heapの定義のついてのおさらいをしておきましょう。 Leftist Heapとは、以下の性質をもつ二分木です。 根の部…

Leftist Heapの性質

Leftist Heapは、純粋関数型的にヒープを操作するために用いられるデータ構造です。Leftist Heapは要素が左に偏っている二分木として実装されます。 データ構造自体は以下のように単純に構成できます。 type 'a heap = | E | T of 'a * 'a heap * 'a heap た…

PFDSを読む: 二分木の改良

長年積んでたPFDSを読み始めることにしました。 積んでる間に邦訳が出たらしいのですが、とりあえず気にしない方針で。まずは単純な二分木 module type SET = sig type elt type set val empty : unit -> set val insert : elt -> set -> set val member : e…

Smith-Waterman法で配列の局所アラインメントを求める

今度は局所アラインメントを求めます。 前回の大域アラインメントと違って、今度は最も一致度の高い部分文字列を求めるアルゴリズムになります。 type alignment = char option list let maximums_by (key : 'a -> 'b) (lst : 'a list) : 'a list = let rec …

Needleman-Wunsch法により配列の大域アラインメントを求める

アラインメントとは、2つの配列s, tに欠損記号「-」を挿入して、出来る限り2つの一致度が高くなるように並べたものです。 例えば、2つの文字列"ABCD"と"ACDE"があったとき、これは1つめの文字列から'B'を削除して末尾に'E'を挿入たものだと考えるのが自然で…

Basic認証の方法を理解する

Basic認証は数あるHTTPの認証方法の中でも最も簡単なものです。認証方法は、ユーザー名とパスワードをコロンで繋いだものをbase64でエンコードし、Authorizationヘッダの値に"Basic (先ほど作った文字列)"をセットするだけです。アホみたいに簡単なので、不…