common lisp
LOUDS++*1実装の続き。 前回はここ。今回は、この論文中に良く出てくるrankとselectという関数を自分なりに(= 間違っている可能性あり*2 )整理してみた。 rank, select rank及びselectは、前回作成したLBS(LOUDS bit-string)から、木のノード情報を取り出す…
『Enginnering the LOUDS Succinct Tree Representaion*』という論文に目を通し終わったので、(まだ理解はしていないが)これから実装に入る。現状での理解は次のような感じ。 Level-Order Unary Degree Sequenceの略 順序木の表現方法の一つ。静的構築。サイ…
charseq。 こことここで書いたことを実際に試しているライブラリ。 大体以下のようなことを目標としている。 部分文字列の作成が容易かつ低コスト 使用者はそれが部分文字列だということを意識せずに扱える 大抵のケース*1で効率的な文字列操作が行われる ※ …
BASE64のエンコード関数を使いたくなったので作成。 ;; 8byte整数を等価なビットリストに変換 ;; ex: 10 = #b00001010 => (0 0 0 0 1 0 1 0) (defun octet-to-bytes (octet) (loop FOR i FROM 7 DOWNTO 0 COLLECT (ldb (byte 1 i) octet))) ;; listがdivisor…
調べたメモ。 CLikiに登録されているライブラリは、(asdf-install:install ライブラリ名)でインストール可能 CLikiへの登録手順 CLikiのページに移動 「Create New Page」リンクをクリック ページの名前を聞かれるので、ライブラリ名を入力 => ページ編集画…
Javaは文字列(String型)がimmutable。 この仕様は、汎用的な文字列処理関数を書く場合の負担を軽減してくれていると思う。 対してcommon lispの文字列はmutable。 そのため(そのためか?)、common lispの文字列処理関数*1は、Javaに比べてインターフェース(?)…
今日は端末操作用のエスケープシーケンスを調べる機会があったので、その内の自分が良く使いそうな操作をcommon lispのパッケージとしてまとめておくことにする。 (defpackage ppterm (:use :common-lisp) (:export *colorset* color clear cursor)) (in-pac…
四月の半ばくらいからちょこちょこ作っていたバイト列とユニコード文字列の変換ライブラリがようやく完成*1。 名前: creole まとまった情報は上記リンク先のWikiに書く予定なので、ここでは簡単な使い方と計時結果だけを載せておく。 サンプル ;;; sbcl-1.0.…
funcallを省略するためのマクロ。 実際には使わなそうだけど、一応残しておく。 (defmacro fnlet (letargs &body body) `(macrolet ,(mapcar (lambda (letarg) (destructuring-bind (fn-name fn) (if (listp letarg) letarg `(,letarg ,letarg)) `(,fn-name …
DoubleArray(トライの一種)を利用して、マルチバイト文字列をユニコード文字列にある程度自動的に変換する、という試み(?)。 ちゃんとした形に整理するほどの気力はないので、一応動く程度のソースコードと覚え書きを残しておくことにする。 やること＆概要 …
common lispではハッシュが使い難い(と思う)。 その理由の一つは、リストのようにマッピング関数がない*1せいだと思うので、そのための関数を定義。 ユーティリティ関数っぽくいろいろ装飾。 ※ 宣言はsbcl(1.0.37)用に特化 (declaim (inline maphash-to-list…
;; sbcl-1.0.37, clisp-2.42, ClozureCL-1.4 > *print-case* > :UPCASE > :a > :A > :ａ > :Ａ > 'ａbｃdè > ＡBＣDÈ さすがユニコード対応。
配列を用いたスタック実装。 組み込みのlistを使ったスタックと比較したくて作成。 cl-igoでlistスタックを用いている箇所*1を、下記配列スタックで置換してみたが、特にメリットはなかった(逆に10%程度遅くなった。sbcl-1.0.34)。またどこかで使いたいこと…
common lispで開発していると、たまに式一つ分だけコメントアウトしたくなることがある。 そういった機能は標準ではないかと思っていたが、条件付き読み込み(?)を使えば似たようなことが出来ることに気がついた。 ;; (+ 20 30)をコメントアウト > (+ 10 #+c …
Javaで作成していた形態素解析器のCommon Lisp版も作成(cl-igo)。 バイナリ辞書はJavaで作成したものを使用するようにし、辞書の読み込み・形態素解析部分だけをcommon lispで実装した。 ユニコード文字列に対応している処理系なら、多分動くはず...。※ 確認…
llvmのチュートリアルの続きを読もうと思ったら、今はドキュメント関連のページがエラーで見れなくなっていたので、代わりに前から少し気になっていたコムソートを実装してみることにする。 参考サイト: コムソート - Wikipedia(最終更新 2009年11月29日 (日…
llvmのチュートリアルの続き。 今回はパースして得られた抽象構文木から、llvmの(llvm IRの?)コードを生成する。 概要? オリジナルのチュートリアルでは、コード生成にC++のビルダクラスが使われているが、common lisp用のそういったモジュールは用意されて…
llvmに関する基本的な(?)ドキュメントには一通り目を通した感じなので、次は『LLVM Tutorial』に沿って、Kaleidoscopeという言語を実装してみることにする。 上記チュートリアルでは実装言語として、C++及びOCamlが用いられていたが、自分はcommon lispが一…
equal等値なキーを扱えるようにしたcase。 主にstring型に対して適用することを想定。 ;; TODO: 重複キーのチェック(警告)をつけるべき (defmacro equal-case (expr &rest clauses) (let ((v (gensym))) `(let ((,v ,expr)) (cond ,@(stable-sort (mapcar (l…
JavaにはJavadocという有名なドキュメントコメントがある。 (実践しているかどうかは別として)関数その他にドキュメントをつけるという考えは良いと思う。 ただ、Javadocの場合、名前の通り(一定の規約に従った)コメントを使って(関数その他の)文書化を行っ…
パターンマッチがある関数型言語でよく見かける_変数*1をsbclでも使えないかと少し試してみた。 結局満足出来る結果は得られなかったが、作成したものの一部をメモして残しておく。 ;; 以下は、マクロ文字候補文字xが ;; シンボル名の一部として解釈できない…
Railsをやったことがある人ならお馴染みのeRuby(もどき)を、common lispで実装してみた。 所要時間およそ90分、行数はコメント込みで70行足らずという簡単なもの。 文法 eRubyの文法は次のように紹介されている(Wikipediaで)。 HTMLファイルの中に （もしく…
文字列の分割を行いたいけど、cl-ppcreパッケージをその(cl-ppcre:split関数の)ためだけに使用したくはなかったので、分割関数を作成した。 ;; 第一版: 平易 (defun split (delim seq &aux (len (length delim))) (declare (unmuffle-conditions compiler-no…
前回と重複するところがあるが、ftype型宣言の有用な使い方について書いておく。 関数の戻り値の型指定 ftype型宣言を使うと、関数の戻り値の型を指定することができる。 これが何故有用かと云うと、sbclは関数の戻り値の型が指定されている場合、それに基づ…
長さ制限付きハフマン符号化に合わせて、普通の*1ハフマン符号化のソースコードも整理。 ### 最初にハフマン符号化本体のソースを載せて、次にその中で利用しているヒープ(順序キュー)の実装を載せる。 ハフマン符号ソース。 参照: nlet, ???-obj-??? ;;;;;;…
長さ制限付きのハフマン符号化のソースコードは、以前にも載せたが、結構無駄が多かったので書き直し。 ついでに、整理中に気づいたこと(間違っているかもしれない!)を注釈として残しておく。 ;;;;;;;;;;; ;;;; 構造体 (defstruct obj ; コスト値を持つオブ…
メモ２。 各コードを符号化するのに最適なビット長は、(- (log (/ コードの出現数 コード総数)) 2)、で求めることができる。 そのため次のような関数で、入力データの最適なハフマン符号化のために必要なビット長が得られる。 ;; コードの出現頻度表を引数に…
BWTに続いて、MTF(Move To Front)。 BWTは、対象の列を、同じ値の要素が隣接する傾向がある列へと変換した。 MTFは、それらの隣接した要素を0(あるいは他の小さい整数)で置き換えるアルゴリズムらしい(不正確)。 BWT -> MTFの適用を経た列は、要素の多くが0…
gzipに続いて、bzip2圧縮(もしかしたら解凍も)をcommon lisp(sbcl)で実装してみようと思う。まだ詳しく調べてないので不確かだが、bzip2では「入力データ -> BWT*1 -> MTF変換 -> ハフマン符号 -> 圧縮データ」のようなプロセスで圧縮を行っているようだ。今…
前回書いたBWT関数はかなり非効率だったので、その修正版を作成した。 修正点は主に以下の三つ。 対象を文字列からバイト列に変更 列のローテートは実際には行わない。代わりに、各列の先頭位置を保持する変数を用意し、その値をずらすことで循環列を表現す…
