algorithm
BWTに続いて、MTF(Move To Front)。 BWTは、対象の列を、同じ値の要素が隣接する傾向がある列へと変換した。 MTFは、それらの隣接した要素を0(あるいは他の小さい整数)で置き換えるアルゴリズムらしい(不正確)。 BWT -> MTFの適用を経た列は、要素の多くが0…
gzipに続いて、bzip2圧縮(もしかしたら解凍も)をcommon lisp(sbcl)で実装してみようと思う。まだ詳しく調べてないので不確かだが、bzip2では「入力データ -> BWT*1 -> MTF変換 -> ハフマン符号 -> 圧縮データ」のようなプロセスで圧縮を行っているようだ。今…
前回書いたBWT関数はかなり非効率だったので、その修正版を作成した。 修正点は主に以下の三つ。 対象を文字列からバイト列に変更 列のローテートは実際には行わない。代わりに、各列の先頭位置を保持する変数を用意し、その値をずらすことで循環列を表現す…
gzip圧縮/解凍器作成の４。 ようやくgzip圧縮器の作成に着手。 gzipパッケージ 今回は、DEFLATEフォーマットに準拠したデータの作成/書き出し部分の実装が主となるが、それに取りかかる前にgzipファイル作成用のユーティリティパッケージを定義しておく。コ…
gzip圧縮/解凍器作成の３。 軽く整理 gzipはデータの圧縮に(主に)DEFLATEアルゴリズム(or DEFLATE圧縮データフォーマット)を利用している DEFLATEでは以下のような方法でデータの圧縮が行われる 入力データをLZ77アルゴリズムで圧縮する 上記圧縮データをさ…
最近ちょくちょくトライを使いたくなることがあるので、少しまとまったハッシュトライの実装を書いておく。 位置付け的には開発用。使用頻度が高いようなら、もう少しちゃんとしたものに書き直す。 ※ 2010/01/03: print-objectメソッド追加、common-prefix-s…
冬休みの取り組みとして、ZIP*1圧縮/解凍器を作ってみることにした。 ZIPで使われている圧縮アルゴリズム(圧縮フォーマット?)は、DEFLATEアルゴリズムと云って、簡単に云えばLZ77とハフマン符号化を組み合わせたもののようだ。日本語版仕様(RFC1951) ハフマ…
本業の方が忙しくて、なかなかまとまったことをする時間がないので、軽いものを一つ。「Get a Rectangular Field」というパズルのような問題を解いてみる。 問題の説明等はここを参照。 途中経過とかは全て飛ばして、とりあえず最初に思いついた解答(を若干…
形態素解析器の４。 今回は未知語処理+αを扱う。 前回までで作成した形態素解析器では、下の例のように未知語が"_"と表示されてしまうが、これをちゃんと"ocaml"と表示されるようにするのが今回の主たる目的。 ;; 未知語=単語辞書に登録されていない語は、"_…
形態素解析器作成の３。 前回、形態素解析のステップを大まかに二つに分けた。 入力テキストを形態素列に分割する。一般に、入力テキストは複数の形態素列に変換可能なので、その全てのパターンを列挙する それらの分割にコスト(優先順位)を付与する。コスト…
形態素解析器作成の２。前回で必要なデータの準備は終わったので、今回からは解析器の実装に入る。 この実装では、形態素解析はおおまかに次の二つの段階に分けられる。 入力テキストを形態素列に分割する。一般に、入力テキストは複数の形態素列に変換可能…
以前に「DoubleArrayと辞書があれば、形態素解析器は案外簡単にできるのではないか」というようなことを書いた。 試してみたところ、実際に結構簡単に(ほぼ)MeCab互換の形態素解析器ができたので、それを何回かに分けて載せていくことにする。 作るもの 未知…
今日、会社の同僚や先輩と、通常のものより比較回数が少なくてすむ二分木探索の実装方法や性能について、(以前見た or 書いた覚えはあるが忘れていたので)あれこれ話していた。 その結果、(一部は自分の中で)一応の結論を得たので、書いておく。 ※ 以下に書…
近況 ここしばらくは、ひたすらC++でDoubleArrayの実装に取り組んでいる。もともとは、シンプルなものを一つ作って終わりにしようかと考えていたのだが、検索・挿入効率とかメモリ使用量(ファイルサイズ)とか大きい(千万程度)のキーセットに対して効率的な実…
オンラインで読める『Real World Haskell』という本の目次を眺めていたら、BloomFilterという言葉を発見。 どうやらデータ構造の一種らしいが、聞いたことがなかったので調べてみた(Wikipediaで)。 結果、セット(集合)を表すためのデータ構造だということが…
以前DoubleArrayのTAIL圧縮を取り扱った時に参考にした『ダブル配列におけるキャッシュの効率化』*1という論文には、TAIL配列の他に、BASE配列とCHECK配列を圧縮する方法も載っていた*2。 それほど長くないので、該当個所を引用させてもらう。 ダブル配列は…
SuffixArrayという言葉を最近知ったのだが、それが意味するところはいまいち分かっていない。 とりあえず、現状の認識としては以下のような感じ。※間違っている可能性が大いにあり TAIL配列を使うDoubleArrayに似ている。 転置インデックスを作成せずに可変…
数日前にcommon lispでJSONパーサを実装したが、そのC++版を書いてみた。実装的には、common lisp版とほとんど変わらないが、サロゲート・ペアに対応したり、エンコード関数も(おまけ程度)に作成したり、と若干以前よりは高機能になっている。ソースコードは…
今までのDoubleArrayの実装では、当然のように(vector (unsigned-byte 8))をキーとして利用してきた。文字列(キー)を扱う場合は、1byte(=8bit)を単位として扱うのが自然なので、悪くはない(むしろ良い?)とは思うのだが、2byte以上を単位として扱うのも、それ…
JSONのパーサを作ってみた。 参考にしたのは、こことここ。 今回作成したのはトップダウン(再帰下降)型のパーサ。 ボトムアップ版もいつか作ってみたいという思いを込めて、タイトルに「トップダウン」と入れておく。 割合高速。 実装 ほぼJSONの仕様(?)通り…
DoubleArrayの3-1。 今回はTAIL配列の圧縮を行う。 参考にした(かな?)のは、次の論文: 『ダブル配列におけるキャッシュの効率化』*1。上の論文の中に「後方一致する接尾辞を併合することで、TAILを圧縮することができる」という記述があるが、今回はこの通り…
コンパイラの本を流し読みしていたら、中置記法とか前置記法とか後置記法とかが出てきた。これらの記法間の変換処理(正確には中置記法から後置記法への変換)は、だいぶ前に実装しようとして挫折(?)したことがあったのだが、今日試してみたら、(適切なコード…
DoubleArrayシリーズ(?)の続き。 今回は、insert関数の処理速度を改善する。 改善点 前回の実装では、insert関数の処理速度がもの凄く遅かったが、その原因はinsert関数の中(の関数の中)で呼び出されているx-check関数にある。 この関数は、簡単に云えば(要…
最近は少し忙しいので、気分転換を兼ねて簡単な関数を実装する。リストの破壊的なリバース。 以下、ソース。 参照: nlet (defun list-reverse! (lst) (nlet self ((lst lst) head) (if (endp lst) head (self #1=(cdr lst) (progn (setf #1# head) lst))))) …
DoubleArrayでの実験用にハフマン符号化を実装。 ※ここの続きでもある ハフマン符号化は、本で良く目にしてはいたのだが、これまで実装したことはなかった。 実際にやってみると案外簡単で、大体以下の四ステップで実装できた。 1. 入力文字列中の各文字の出…
ちょっとヒープ(優先順位付きキュー)を使いたくなったので、実装。とりあえずは、実装が簡単な(かつ性能が良いらしい)pairing-heapを選択。一群の関数は、後で他のものに変更しやすいようにpackageにまとめておく。 ;;; package (defpackage :pairing-heap (…
しばらくDoubleArrayでいろいろ試してみようと思っているので、今日はそのベースとなるソースコード(+覚え書き)を掲載。 『An Efficient Implementation of Trie Structures』*1を参考に実装した。 前置き DoubleArrayの簡単(かつテキトウ)な説明。 Trieの実…
N-Queen問題を、いくつかの方法で解いてみる。とりあえず、一番簡単・簡潔だと思うのは、次のコード。 参照: nlet-acc ;; row番目に新たなqueenを置けるかチェック (defun check (row queens &optional (r 1)) (or (null queens) (and (/= (car queens) row …
前回書いたマージソートを、ちょこちょこ修正。 まずは、安定なマージ関数を少しすっきりさせてみる。 (defmacro with-null-check ((var1 var2) &body body) `(cond ((null ,var1) ,var2) ((null ,var2) ,var1) (t ,@body))) ;; 多重評価の問題あり (defmacr…
昨日に引き続き、今日はクイックソートを書いてみる。一口にクイックソートと云っても、一番内部のループ(配列を二つに分割する処理)の実装方法にいろいろ変種があるので、とりあえず一番楽に実装できそうなものを思い出しつつ書いてみる。 (defun qsort (as …
