『Linear Suffix Array Construction by Almost Pure Induced-Sorting』*1という論文を参考にして、Induced-Sortingを用いたSuffixArrayの線形構築アルゴリズム(SA-IS)をCommon Lispで実装した。 以下、そのソースコードとメモ書き。 線形構築 汎用ソートア…

common lispではゼロ次元の配列が作れることを知った。 ;; dimentionsに空リストを渡して配列を作成するとゼロ次元配列となる (make-array '()) --> #0A0 (aref *) --> 0 (make-array '() :initial-element "string") --> #0A"string" (aref *) --> "string"…

前回のB木の実装中にはほとんど気にしていなかったけど、どうやらB木は挿入のみなら常にバランス状態を維持できるようになっているようだ(おそらく)。 今回はB木のバランス具合を確かめるために試したこと(+考えたこと)のメモ。 ※ いつもの通り正しくない可…

B木をWikipediaの記事*1を参考にしてcommon lispで実装してみた。 実装 実装コード。 コメント抜きで140行程度。 オンメモリ。最適化なし。 ※ 末尾に全部まとめた(+ コメント無し)のソースコード有り ;;;; パッケージ定義 (defpackage btree (:use :common-l…

Erlang -- External Term Formatを参考にして、Erlangの項(のバイナリ表現)とCommon Lispのオブジェクトを相互変換するライブラリを作成。 ・erlterm-0.0.1 ポートを用いた外部接続での利用を想定。 細かい作り込みや最適化はまだまだだけど、一応一通りの変…

倍精度浮動小数点数をIEEE754形式のビット表現(整数値)にエンコードする方法。 (defun encode-double-float (float) (declare (double-float float)) (multiple-value-bind (fraction exponent sign) (integer-decode-float float) (let ((code 0)) (setf (l…

LLVM Bitcode File Format — LLVM 3.4 documentationを読んでllvmのビットコードをデコード(パース)してみたので、そのメモ(あくまでも個人用メモ。用語とかは結構自分の好き勝手に書いているので、ちゃんと知りたい人はオリジナルのドキュメントを参照のこ…

前回はトライだったけど、今回はDAWGを構築。 Nをキーセットに含まれる文字の総数*1だとして、DAWGはトライと同様にO(N)で構築可能(多分間違っていないはず...)。 ただし、子ノード(サブトライ)が共有可能かどうかの判定が入るので、実際には一桁程度遅くな…

七月にやっていたDAWG(Direct Acyclic Word Graph)シリーズ(?)の続き。 結構長い間中断していて自分でも内容がうろ覚えなので、仕切り直してもう一度。 今回はDAWGの前段階として、ソート済み(かつ各行がユニーク)なファイルからトライを構築する。 DAWG 軽…

前回にErlangで作成したhashtrieをcommon lispに移植していたら、いつのまにかただのハッシュテーブルになっていた。 もともとはHAMTから始まったはずなのに...。ソースコード等: dict-0.0.1 実装 キー衝突時にAMTを使わないで、リンクリストを使うHAMT。 初…

「Sorting and Searching Strings」で説明されているマルチキークイックソートの実装。 詳細はリンク先を参照。 マルチキークイックソート 文字列の配列のソートが高速に行える URL("http://...")の配列のような接頭部分の重複率が高い文字列配列の場合でも…

クイックソートの内部ループには(自分が知っている限りでは)二種類あるな、とふと思ったので、思い出して書いてみた。 ;;; 補助マクロ/関数 ;; whileループ (defmacro while (exp &body body) `(loop WHILE ,exp DO (locally ,@body))) ;; 配列をシャッフル …

HAMT(Hash Array Mapped Trie) - sileの日記の続き。 前よりはちゃんとしたものを実装したので、それをうけての感想など。 作成物: hamt-0.2.0 前回からの相違点 基本的には『Ideal Hash Trees』*1に合わせた実装に修正*2。 変更点を挙げると、 HAMTのエント…

『Ideal Hash Trees』*1という論文を(必要なところだけ、だいたい)読み終わったので、そのメモ等。 概要 AMT(Array Mapped Trie)という基盤的なデータ構造を使って、ideal(nearly ideal)なHash Treesを作ろう、というような話。 AMTの応用例として、以下のよ…

シンボル補足を避けるためにたまに使う方法。 uninternされたシンボルとリードマクロのラベル付け/参照機能を併用。 ;; uninternされたシンボル ;; 印字名が同じでも実体は異なるので、衝突は起きない (eq '#:var '#:var) --> NIL ;; #n=および#n#構文を使え…

『Packrat Parsing: Simple, Powerful, Lazy, Linear Time』という論文の流し読みが終わったので、現状での理解を軽く書いておく。 概要 ※ 以下、テキトウな理解なので、間違っている可能性有り Packrat Parsingというパース手法。 再帰下降型の一種。 再帰…

前回の実装ではメモ化をハッシュテーブルを用いて実装していたが、それを論文*1に合わせて遅延実行を利用するものに修正。 こっちの方が(あらかじめ入力テキストの各位置に対して、遅延されたパーサ関数実行を用意しておく必要があるが)メモ化によって既に計…

スキップリスト(Wikipedia)を実装してみた。説明等は一切抜きでコードだけ。 (defpackage skiplist (:use :common-lisp) (:shadow :common-lisp get rem) (:export *p* make get rem)) (in-package :skiplist) ;;;;;;;;; ;;;; 宣言 (declaim (inline make-no…

テキストファイルの各行をバイト列として読み込むマクロを定義。 SBCL等のように文字列を内部的にユニコードとして表現している処理系では、テキストファイルを読み込む際、そのファイルが不正なバイト列を含んでいると読み込みに失敗することがあるので、そ…

しばらく(私的には)プログラミングから離れた生活が続いていたので、肩慣らしを兼ねてUNF(Unicode正規化ライブラリ)のcommon lisp版(cl-unf)を作成。いつものようにSBCLで作成し、SBCL向けに最適化されているが、UTF-32に対応しているなら、他の処理系でも一…

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

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

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

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

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

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