数値列の圧縮に関するメモ書き。 サンプル数値列 要素が昇順に並んだ数値列があるとする。 (defvar *numbers* #(0 1 2 4 5 8 9 10 11 14)) 前準備: 差分列への変換 このような数値列を圧縮する場合は、その前準備として、もともとの数値列を各要素間の差分を…

以前にcommon lispで実装したSA-ISアルゴリズムを、C++でも実装したのでその計時結果など。 ソースコード(github): sais-0.0.1 計時 対象データには以下のサイズのテキストファイル群を使用。 $ ls sa.txt.* -rw-r--r-- 1 user user 10000 2010-12-23 19:25 …

以前に書いたSA-ISの記事(及びソースコード)には明確な間違いがあったので訂正しておく。 間違い 確か以前の記事では「入力文字列の各LMS部分文字列が互いにユニークなら、初めのinduced-sortを終えた段階でSuffixArrayが求まる」というようことを何箇所かで…

Erlang。 デフォルトでは、coverモジュールとsmerlモジュールの併用が不可能(おそらく)なので、その問題を解消するためのパッチを作成。 cover: コードカバレッジ計測用モジュール smerl: 「Simple Metaporgramming for Erlang」の略 Erlangでメタプログラミ…

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

CCLのdirectory関数を使ってディレクトリ一覧を取得する方法。 普通に(?)ワイルドカードでマッチさせようとしてもnilが返ってくる。 ;;;; ccl-1.5 ;; Ubuntuのルートディレクトリをリストしたい (directory "/*/") --> NIL マニュアルを見ると、CCLのdirecto…

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

MappedByteBuffer + InputStream: ファイルにマッピングされたランダムアクセス可能な入力ストリーム - sileの日記で作成したクラスの巨大ファイル対応版。 2GB以上のファイルでも扱うことが可能。 import java.io.IOException; import java.io.InputStream;…

表題の通り、ファイルにマッピングされておりかつランダムアクセス可能な入力ストリームクラス、のサンプル。 MappedByteBufferを読み込み専用モード(FileChannel.MapMode.READ_ONLY)で使っているので、同じファイルを複数プロセスでオープンした場合はメモ…

Javaはデフォルトでは入出力でビッグエンディアンを使用するけど、リトルエンディアン或いはその環境にネイティブのバイトオーダーを指定して操作を行ないたい時もある。 今回は出力ストリームのバイトーオーダーを制御する方法のメモ。 基本的にはByteBuffe…

sbcl(1.0.43)では、配列に対するsxhash関数は常に同じ値を返すようだ。 ;;;; sbcl-1.0.43 ;; 一次元配列 (sxhash #()) --> 518591303 (sxhash #(a 10 "sbcl")) --> 518591303 (sxhash (make-array 10 :adjustable t :fill-pointer 3)) --> 518591303 (sxhash…

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

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

LLVMのアセンブリ言語で構造体のサイズ(その構造体を表現するのに必要なバイト数)を取得する方法。 C言語のsizeof演算子のような構造体(或いは型一般)のサイズを取得する直接的な方法はなさそうだけど、対象となる構造体のポインタの値を利用して算出するこ…

いろいろ途中経過を省いてDAWGシリーズ(?)の最後。 common lisp用のライブラリにまとめました、という話。 ・cl-dawg-0.1.0 概要 DAWGのcommon lisp実装 ただしSBCL依存 DAWG構築時に利用しているハッシューテーブルでSBCLの拡張機能を使っているため 静的に…

以前にCommon Lispで実装したマルチキークイックソートをC++で書き直して、STLのstd::sortと速度を比較してみた。 使用データ Wikipediaの記事タイトル約500万行を使用。 データ作成方法などはここを参照。 $ wc -l wiki.title.500 5340378 wiki.title.500 $…

前回にソート済みファイルからDAWGを構築する際には、個々のノードのハッシュ値をO(1)で(簡単に)算出可能にするために、ノードにハッシュ値用のフィールドを持たせていた。 ;;;; 再掲 ;; DAWGのノード用の構造体 (defstruct node (label 0 :type octet) (sib…

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…

Igo: GoogleAppEngineで形態素解析サーバとIgo: JavaScriptで形態素解析で書いた内容を少し整理してgithubにソース一式を登録。 ・igo-gae現状は本当にただ必要な分だけを修正して、とりあえずGAE上で動かしているだけだけど、その内にもっとちゃんとしたも…

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

Igo: GoogleAppEngineで形態素解析サーバで用意したサーバ(※追加修正あり。後述)を使って形態素解析を行うJavaScriptを書いてみた。 制限 結構制限が多い。 対応がUTF-8のみ レスポンスのJSONに含まれる文字列内のASCII以外の文字を16進数表記(\uXXXX)にエス…

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

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

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

最近Erlang本を読んでいる関係もあってこことここで書いているHAMT(Hash Array Mapped Try)のErlangへの応用を試していた。 immutableでpersistentなハッシュマップをHAMTで効率的に実装できないかと。 その成果物: hashtrie-0.0.3 HAMT? hashtrieを作ったも…

IgoをGoogleAppEngine上で動かしてみた。 URL URLと仕様。 トップ: http://igo-morp.appspot.com/ 形態素解析: http://igo-morp.appspot.com/parse 'text'パラメータに入力テキスト*1をセットしてリクエスト(POST or GET)を投げると、形態素解析結果がUTF-8…

「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のエント…