algorithm

LOUDS++(3): LOUDS++

LOUDS++*1の三回目。 今回は、LOUDSの改良版であるLOUDS++に関する部分。 LOUDS++ LOUDSでは、木をビット列として表現していた。 参照: tree-to-lbs (defvar *tree* '(:a (:b) (:c (:f) (:g (:i))) (:d) (:e (:h)))) (tree-to-lbs *tree*) --> #*10111100110…

LOUDS++(2): rankとselect

LOUDS++*1実装の続き。 前回はここ。今回は、この論文中に良く出てくるrankとselectという関数を自分なりに(= 間違っている可能性あり*2 )整理してみた。 rank, select rank及びselectは、前回作成したLBS(LOUDS bit-string)から、木のノード情報を取り出す…

LOUDS++(1)

『Enginnering the LOUDS Succinct Tree Representaion*』という論文に目を通し終わったので、(まだ理解はしていないが)これから実装に入る。現状での理解は次のような感じ。 Level-Order Unary Degree Sequenceの略 順序木の表現方法の一つ。静的構築。サイ…

マルチバイト文字列→ユニコード文字列

DoubleArray(トライの一種)を利用して、マルチバイト文字列をユニコード文字列にある程度自動的に変換する、という試み(?)。 ちゃんとした形に整理するほどの気力はないので、一応動く程度のソースコードと覚え書きを残しておくことにする。 やること&概要 …

配列スタック

配列を用いたスタック実装。 組み込みのlistを使ったスタックと比較したくて作成。 cl-igoでlistスタックを用いている箇所*1を、下記配列スタックで置換してみたが、特にメリットはなかった(逆に10%程度遅くなった。sbcl-1.0.34)。またどこかで使いたいこと…

コムソート

llvmのチュートリアルの続きを読もうと思ったら、今はドキュメント関連のページがエラーで見れなくなっていたので、代わりに前から少し気になっていたコムソートを実装してみることにする。 参考サイト: コムソート - Wikipedia(最終更新 2009年11月29日 (日…

ハフマン符号化 : 整理

長さ制限付きハフマン符号化に合わせて、普通の*1ハフマン符号化のソースコードも整理。 ### 最初にハフマン符号化本体のソースを載せて、次にその中で利用しているヒープ(順序キュー)の実装を載せる。 ハフマン符号ソース。 参照: nlet, ???-obj-??? ;;;;;;…

長さ制限付きハフマン符号化 : 整理

長さ制限付きのハフマン符号化のソースコードは、以前にも載せたが、結構無駄が多かったので書き直し。 ついでに、整理中に気づいたこと(間違っているかもしれない!)を注釈として残しておく。 ;;;;;;;;;;; ;;;; 構造体 (defstruct obj ; コスト値を持つオブ…

最適なハフマン符号化のために必要なビット長

メモ2。 各コードを符号化するのに最適なビット長は、(- (log (/ コードの出現数 コード総数)) 2)、で求めることができる。 そのため次のような関数で、入力データの最適なハフマン符号化のために必要なビット長が得られる。 ;; コードの出現頻度表を引数に…

符号化に最低限必要なビット長

長さ制限付きハフマン符号の整理中。 気づいたことメモ。 N個のコードを符号化するには、ビット長が最低(log N 2)*1は必要。 一番(最大の)ビット長が短くて済むのは、全てのコードを同じビット長でエンコードした場合。 いわゆる普通の文字表現(256文字を、8…

MTF : bzip2

BWTに続いて、MTF(Move To Front)。 BWTは、対象の列を、同じ値の要素が隣接する傾向がある列へと変換した。 MTFは、それらの隣接した要素を0(あるいは他の小さい整数)で置き換えるアルゴリズムらしい(不正確)。 BWT -> MTFの適用を経た列は、要素の多くが0…

BWT : bzip2

gzipに続いて、bzip2圧縮(もしかしたら解凍も)をcommon lisp(sbcl)で実装してみようと思う。まだ詳しく調べてないので不確かだが、bzip2では「入力データ -> BWT*1 -> MTF変換 -> ハフマン符号 -> 圧縮データ」のようなプロセスで圧縮を行っているようだ。今…

BWT : bzip2 : 修正版

前回書いたBWT関数はかなり非効率だったので、その修正版を作成した。 修正点は主に以下の三つ。 対象を文字列からバイト列に変更 列のローテートは実際には行わない。代わりに、各列の先頭位置を保持する変数を用意し、その値をずらすことで循環列を表現す…

gzip圧縮

gzip圧縮/解凍器作成の4。 ようやくgzip圧縮器の作成に着手。 gzipパッケージ 今回は、DEFLATEフォーマットに準拠したデータの作成/書き出し部分の実装が主となるが、それに取りかかる前にgzipファイル作成用のユーティリティパッケージを定義しておく。コ…

LZ77圧縮 -DEFLATE用-

gzip圧縮/解凍器作成の3。 軽く整理 gzipはデータの圧縮に(主に)DEFLATEアルゴリズム(or DEFLATE圧縮データフォーマット)を利用している DEFLATEでは以下のような方法でデータの圧縮が行われる 入力データをLZ77アルゴリズムで圧縮する 上記圧縮データをさ…

ハッシュトライ

最近ちょくちょくトライを使いたくなることがあるので、少しまとまったハッシュトライの実装を書いておく。 位置付け的には開発用。使用頻度が高いようなら、もう少しちゃんとしたものに書き直す。 ※ 2010/01/03: print-objectメソッド追加、common-prefix-s…

長さ制限つきのハフマン符号化(The Coin Collector's Problem)

冬休みの取り組みとして、ZIP*1圧縮/解凍器を作ってみることにした。 ZIPで使われている圧縮アルゴリズム(圧縮フォーマット?)は、DEFLATEアルゴリズムと云って、簡単に云えばLZ77とハフマン符号化を組み合わせたもののようだ。日本語版仕様(RFC1951) ハフマ…

Get a Rectangular Field

本業の方が忙しくて、なかなかまとまったことをする時間がないので、軽いものを一つ。「Get a Rectangular Field」というパズルのような問題を解いてみる。 問題の説明等はここを参照。 途中経過とかは全て飛ばして、とりあえず最初に思いついた解答(を若干…

形態素解析器(4)

形態素解析器の4。 今回は未知語処理+αを扱う。 前回までで作成した形態素解析器では、下の例のように未知語が"_"と表示されてしまうが、これをちゃんと"ocaml"と表示されるようにするのが今回の主たる目的。 ;; 未知語=単語辞書に登録されていない語は、"_…

形態素解析器(3)

形態素解析器作成の3。 前回、形態素解析のステップを大まかに二つに分けた。 入力テキストを形態素列に分割する。一般に、入力テキストは複数の形態素列に変換可能なので、その全てのパターンを列挙する それらの分割にコスト(優先順位)を付与する。コスト…

形態素解析器(2)

形態素解析器作成の2。前回で必要なデータの準備は終わったので、今回からは解析器の実装に入る。 この実装では、形態素解析はおおまかに次の二つの段階に分けられる。 入力テキストを形態素列に分割する。一般に、入力テキストは複数の形態素列に変換可能…

形態素解析器(1)

以前に「DoubleArrayと辞書があれば、形態素解析器は案外簡単にできるのではないか」というようなことを書いた。 試してみたところ、実際に結構簡単に(ほぼ)MeCab互換の形態素解析器ができたので、それを何回かに分けて載せていくことにする。 作るもの 未知…

比較回数の少ない二分木探索

今日、会社の同僚や先輩と、通常のものより比較回数が少なくてすむ二分木探索の実装方法や性能について、(以前見た or 書いた覚えはあるが忘れていたので)あれこれ話していた。 その結果、(一部は自分の中で)一応の結論を得たので、書いておく。 ※ 以下に書…

DoubleArray: ソート済みデータからの構築

近況 ここしばらくは、ひたすらC++でDoubleArrayの実装に取り組んでいる。もともとは、シンプルなものを一つ作って終わりにしようかと考えていたのだが、検索・挿入効率とかメモリ使用量(ファイルサイズ)とか大きい(千万程度)のキーセットに対して効率的な実…

BloomFilter

オンラインで読める『Real World Haskell』という本の目次を眺めていたら、BloomFilterという言葉を発見。 どうやらデータ構造の一種らしいが、聞いたことがなかったので調べてみた(Wikipediaで)。 結果、セット(集合)を表すためのデータ構造だということが…

DoubleArray(3-3): BASEとCHECK配列圧縮

以前DoubleArrayのTAIL圧縮を取り扱った時に参考にした『ダブル配列におけるキャッシュの効率化』*1という論文には、TAIL配列の他に、BASE配列とCHECK配列を圧縮する方法も載っていた*2。 それほど長くないので、該当個所を引用させてもらう。 ダブル配列は…

SuffixArrayがどんなものかを考えてみる。

SuffixArrayという言葉を最近知ったのだが、それが意味するところはいまいち分かっていない。 とりあえず、現状の認識としては以下のような感じ。※間違っている可能性が大いにあり TAIL配列を使うDoubleArrayに似ている。 転置インデックスを作成せずに可変…

JSONデコード: C++

数日前にcommon lispでJSONパーサを実装したが、そのC++版を書いてみた。実装的には、common lisp版とほとんど変わらないが、サロゲート・ペアに対応したり、エンコード関数も(おまけ程度)に作成したり、と若干以前よりは高機能になっている。ソースコードは…

DoubleArray(3-2): キーのサイズ縮小(or string型の利用)

今までのDoubleArrayの実装では、当然のように(vector (unsigned-byte 8))をキーとして利用してきた。文字列(キー)を扱う場合は、1byte(=8bit)を単位として扱うのが自然なので、悪くはない(むしろ良い?)とは思うのだが、2byte以上を単位として扱うのも、それ…

JSONデコード: トップダウン

JSONのパーサを作ってみた。 参考にしたのは、こことここ。 今回作成したのはトップダウン(再帰下降)型のパーサ。 ボトムアップ版もいつか作ってみたいという思いを込めて、タイトルに「トップダウン」と入れておく。 割合高速。 実装 ほぼJSONの仕様(?)通り…

DoubleArray(3-1): TAIL配列圧縮

DoubleArrayの3-1。 今回はTAIL配列の圧縮を行う。 参考にした(かな?)のは、次の論文: 『ダブル配列におけるキャッシュの効率化』*1。上の論文の中に「後方一致する接尾辞を併合することで、TAILを圧縮することができる」という記述があるが、今回はこの通り…

中置記法→前置・後置記法

コンパイラの本を流し読みしていたら、中置記法とか前置記法とか後置記法とかが出てきた。これらの記法間の変換処理(正確には中置記法から後置記法への変換)は、だいぶ前に実装しようとして挫折(?)したことがあったのだが、今日試してみたら、(適切なコード…

DoubleArray(2): 挿入速度改善

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用)

DoubleArrayでの実験用にハフマン符号化を実装。 ※ここの続きでもある ハフマン符号化は、本で良く目にしてはいたのだが、これまで実装したことはなかった。 実際にやってみると案外簡単で、大体以下の四ステップで実装できた。 1. 入力文字列中の各文字の出…

pairing heap

ちょっとヒープ(優先順位付きキュー)を使いたくなったので、実装。とりあえずは、実装が簡単な(かつ性能が良いらしい)pairing-heapを選択。一群の関数は、後で他のものに変更しやすいようにpackageにまとめておく。 ;;; package (defpackage :pairing-heap (…

DoubleArray(1)

しばらくDoubleArrayでいろいろ試してみようと思っているので、今日はそのベースとなるソースコード(+覚え書き)を掲載。 『An Efficient Implementation of Trie Structures』*1を参考に実装した。 前置き DoubleArrayの簡単(かつテキトウ)な説明。 Trieの実…

N-Queen(1)

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 …

リスト用のマージソート

リスト用のマージソートを書いて見た。・以下ソース(関数はどれも破壊的) ;;; 最速(?)のoptimize宣言 (defvar fastest '(optimize (debug 0) (speed 3) (safety 0))) ;;; 2つのlistのマージ (defun merge-list (lst1 lst2 <) (declare #.fastest (function <…