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

ユニコード正規化

ユニコード正規化のcommon lispによる実装*1。 ※ common lisp処理系としては、SBCL等のユニコード(UTF-32)対応のものを想定 参照 実装に際して参考にさせてもらったサイト。 ・UAX #15: Unicode Normalization Forms ・Unicode正規化 正規化に必要なデータ。…

DAWG(4-2): MPHF

四回目の中盤。 最小完全ハッシュ関数(Minimal Perfect Hash Function, MPHF)。 『Simple and Space-Efficient Minimal Perfect Hash Functions』*1の理解が進んだので、前回よりも整理されたコードを載せる。 作成方法概要 論文中の最小完全ハッシュ関数の…

DAWG(4-1): 完全ハッシュ関数

四回目の前半。 DAWGのキーに一意なIDをマッピングするための最小完全ハッシュ関数を実装。 ※ ただし今回実装分は、"最小"のつかないただの完全ハッシュ関数まで 参考元 『Simple and Space-Efficient Minimal Perfect Hash Functions』*1を参考にした。 た…

DAWG(2): ID付け

最初に前回作成したtrie2dawg関数を使って、DAWGとして表現した場合の(トライに比べての)ノード数節約効果を見てみる。 # データ準備 # IPADICに登録されている単語を使用 $ export LC_ALL=C $ cut mecab-ipadic-2.7.0-20070801/*.csv -d',' -f1 | nkf -w | …

DAWG

そろそろトライとかDoubleArrayとかから少し離れたいけど、DAWG(Directed acyclic word graph)というものを知ってしまったので、(多分)もう少しだけ続ける。 DAWG DAWGが何かというと、トライの共通する部分木をまとめたものらしい。 トライからDAWGへの変換…

Micterの単語分割部の高速化を試してみた結果

tkngさんが作成したMicterという単語分割器の分割部を高速化できるような気がしたので試してみた。 そのメモ。試した結果のソース一式はmimicという名前でgithubに保存しておくことにする*1。 結果 まず、結果から*2。 # 分割対象のテキスト(のサイズ) $ ls …

キュー

FIFOのキュー。 これもたまに使いたくなるので、実装(の一つ)をメモしておく。 (declaim (inline make-queue enqueue dequeue queue-empty-p queue-to-list)) (defun make-queue (&optional initial-contents) (declare (optimize (speed 3) (safety 0))) (l…

LOUDS++(4): bit-vector

LOUDSの四回目。 selectおよびrankが効率的に行えるビット配列(bit-vector)の実装。 参考 一応参考にしたのは、次の二つの論文 『A Simple Optimal Representation for Balanced Parentheses』 『Compressed Prefix Sums』 ただし、良く分からないところや、…

リストの反転

以前に書いたリストを破壊的に反転する関数を少し書き直してみた。 まずは、以前に書いた関数。 参照: nlet (defun list-reverse! (lst) (nlet self ((lst lst) head) (if (endp lst) head (self #1=(cdr lst) (progn (setf #1# head) lst))))) 定義は短いが…

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の略 順序木の表現方法の一つ。静的構築。サイ…

charseq

charseq。 こことここで書いたことを実際に試しているライブラリ。 大体以下のようなことを目標としている。 部分文字列の作成が容易かつ低コスト 使用者はそれが部分文字列だということを意識せずに扱える 大抵のケース*1で効率的な文字列操作が行われる ※ …

BASE64

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…

(asdf-install:install ライブラリ名)でインストール可能にする方法

調べたメモ。 CLikiに登録されているライブラリは、(asdf-install:install ライブラリ名)でインストール可能 CLikiへの登録手順 CLikiのページに移動 「Create New Page」リンクをクリック ページの名前を聞かれるので、ライブラリ名を入力 => ページ編集画…

common lispで文字列処理用の関数を書くときの難点

Javaは文字列(String型)がimmutable。 この仕様は、汎用的な文字列処理関数を書く場合の負担を軽減してくれていると思う。 対してcommon lispの文字列はmutable。 そのため(そのためか?)、common lispの文字列処理関数*1は、Javaに比べてインターフェース(?)…

端末操作

今日は端末操作用のエスケープシーケンスを調べる機会があったので、その内の自分が良く使いそうな操作をcommon lispのパッケージとしてまとめておくことにする。 (defpackage ppterm (:use :common-lisp) (:export *colorset* color clear cursor)) (in-pac…

creole : 文字列/バイト列変換

四月の半ばくらいからちょこちょこ作っていたバイト列とユニコード文字列の変換ライブラリがようやく完成*1。 名前: creole まとまった情報は上記リンク先のWikiに書く予定なので、ここでは簡単な使い方と計時結果だけを載せておく。 サンプル ;;; sbcl-1.0.…

fnlet

funcallを省略するためのマクロ。 実際には使わなそうだけど、一応残しておく。 (defmacro fnlet (letargs &body body) `(macrolet ,(mapcar (lambda (letarg) (destructuring-bind (fn-name fn) (if (listp letarg) letarg `(,letarg ,letarg)) `(,fn-name …

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

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

maphash-to-list

common lispではハッシュが使い難い(と思う)。 その理由の一つは、リストのようにマッピング関数がない*1せいだと思うので、そのための関数を定義。 ユーティリティ関数っぽくいろいろ装飾。 ※ 宣言はsbcl(1.0.37)用に特化 (declaim (inline maphash-to-list…

:a

;; sbcl-1.0.37, clisp-2.42, ClozureCL-1.4 > *print-case* > :UPCASE > :a > :A > :a > :A > 'abcdè > ABCDÈ さすがユニコード対応。

配列スタック

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

式一つ分のコメントアウト

common lispで開発していると、たまに式一つ分だけコメントアウトしたくなることがある。 そういった機能は標準ではないかと思っていたが、条件付き読み込み(?)を使えば似たようなことが出来ることに気がついた。 ;; (+ 20 30)をコメントアウト > (+ 10 #+c …

Igo : Common Lisp版

Javaで作成していた形態素解析器のCommon Lisp版も作成(cl-igo)。 バイナリ辞書はJavaで作成したものを使用するようにし、辞書の読み込み・形態素解析部分だけをcommon lispで実装した。 ユニコード文字列に対応している処理系なら、多分動くはず...。※ 確認…

コムソート

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

llvm : tutorial : code generation

llvmのチュートリアルの続き。 今回はパースして得られた抽象構文木から、llvmの(llvm IRの?)コードを生成する。 概要? オリジナルのチュートリアルでは、コード生成にC++のビルダクラスが使われているが、common lisp用のそういったモジュールは用意されて…

llvm : tutorial : lexer,parser

llvmに関する基本的な(?)ドキュメントには一通り目を通した感じなので、次は『LLVM Tutorial』に沿って、Kaleidoscopeという言語を実装してみることにする。 上記チュートリアルでは実装言語として、C++及びOCamlが用いられていたが、自分はcommon lispが一…

equal-case

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が ;; シンボル名の一部として解釈できない…

eLisp : Embedded Lisp

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型宣言(sbcl) : 戻り値の型指定

前回と重複するところがあるが、ftype型宣言の有用な使い方について書いておく。 関数の戻り値の型指定 ftype型宣言を使うと、関数の戻り値の型を指定することができる。 これが何故有用かと云うと、sbclは関数の戻り値の型が指定されている場合、それに基づ…

ハフマン符号化 : 整理

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

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

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

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

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

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

アナフォリックマクロとpacakge(2)

半年くらい前に書いた「アナフォリックマクロとpacakge」の続き。この方法だとダメなケースを発見したので、その改善策(?)を考えてみる。 以前の方法 以前の方法は、アナフォリックマクロの定義と使用が別パッケージに分かれる場合に、アナフォリック変数の…

ftype型宣言(sbcl)

ftype型宣言。 あまり使われているのを見ない気がするが、これを使うと「型宣言なしでは遅いけど、宣言をつけるとコードが汚くなる」というような問題を解決できる時があるので、少し書いておく。以下はsbcl(1.0.34)での挙動。 準備 ;; 処理速度を最優先 (de…

gzip圧縮 - 計時

冬休みに作成したgzip圧縮器を整理*1して、パッケージにまとめた。 ・deflate(0.1.0) ※ 依存: common-utils 以下は簡単な計時など。 比較対象は、gzipコマンドとcommon lispのsalza2パッケージ。 # gzip > time gzip -c /path/to/file > file.gz ;; salza2 (…

gzip圧縮

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

ビットストリーム -DEFLATE用-

RFC1951のDEFLATE圧縮データフォーマットを実装するために作成したビットストリーム。 DEFLATEを実装するのに当面必要な関数だけが定義してあり、インターフェースは適当。 ;;;;;;;;;;;;;;; ;;;; パッケージ (defpackage :bit-stream (:use :common-lisp) (:…

LZ77圧縮 -DEFLATE用-

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

非圧縮gzipファイル作成

冬休み(中に終わらせたい)の取り組み、gzip圧縮/解凍器作成の2。 前回は、RFC 1951(日本語訳)で定義されているDEFLATEフォーマットに準拠したデータを作成するのに必要な符号長の制限付きのハフマン符号化アルゴリズムを実装した。 今回はDEFLATEに関する残…

ハッシュトライ

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

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

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

find-min/find-max

列の要素にキー関数を適用して、その結果が最大(or 最小)となる要素を返す、という関数。 loopマクロのmin/max辺りでやってくれるかなと思ったが、無理そうなので自作した。 マクロをふんだんに使用。 (defmacro find-xxx-helper (empty? first loop compare…