数値列の圧縮に関するメモ書き。 サンプル数値列 要素が昇順に並んだ数値列があるとする。 (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…