これまではDoubleArrayを構築する際には、ソースとなるトライのノードを深さ優先順で探索しDoubleArrayへと変換していた。 トライのキーセットとなる文字列のエンコーディングがUTF-8等の一バイトコード(?)の場合は深さ優先順探索でも特に問題はないが、UTF-…
Igoの時と同じように、Gomoku(0.0.4)とMeCab(0.98)の形態素解析速度を比較してみた。 計時結果 テキストには青空文庫より取得の夏目漱石の『こころ』(x256. 136M. UTF-8)を、辞書にはMeCabのサイトより入手可能なmecab-ipadic-2.7.0-20070801*1を使用。 総処…
昨日取り上げたGomokuがGoogle App Engine上で動くことを確認。 ただそれだけ。 昨日から若干修正したのでバージョンは0.0.3。 サンプルURL: ・形態素解析: http://gomoku-morp.appspot.com/ ・JavaScript: http://gomoku-morp.appspot.com/js-morp-sample.h…
IgoをベースにしてJARファイルに辞書データを同梱した形態素解析器を作成した。 名前は同系統のGomoku(ver 0.0.1)。 特徴 開発コンセプト(?)は「JARファイルのみで形態素解析」と「サイズを(比較的)小さく」の二点。 このJARファイル一つで形態素解析が行え…
数値列の圧縮に関するメモ書き。 サンプル数値列 要素が昇順に並んだ数値列があるとする。 (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を作ったも…
