library

マルチプロセスで使用可能なロックフリーキュー

タイトルの通り、マルチプロセスで使用可能なロックフリーのFIFOキューを実装したので、その簡単な紹介。 作成物 github: ipc-msgque (0.0.4) ロックフリーなFIFOキュー 再入可能 かつ SIGKILLに対して安全*1 C++ 共有メモリ(mmap)を使用 マルチプロセス(and…

ループ処理を関数型っぽく書いてみる(1)

今週は、common lispでループ処理を関数型っぽく、かつ効率良く実装できるかどうかを試していたので、その結果を載せておく。 結論から云えば、処理系の十分な最適化を期待できれば、関数型っぽく書いても、手続き型的に書いた場合と比肩しえる性能が得られ…

Gomokuの形態素解析部をScalaで実装してみた

ここ数日はScalaのコップ本を読んでいて、何かまとまったプログラムをScalaで書いてみたくなったのでGomoku(Java形態素解析器。ver0.0.6)をScalaで実装してみた*1。 ・github: scala-gomoku(ver0.0.1)以下、使用例とJava版/Scala版の簡単な比較メモ。 使用例…

erl-creole: ユニコード文字列とマルチバイト列の変換ライブラリ

少し必要になったのでErlangでユニコード文字列と各種エンコーディングのマルチバイト列(バイナリ)の相互変換を行うモジュールを作成した。 github: erl-creole-0.0.1 現状、対応しているエンコーディングは以下の通り*1: UTF-8, Shift_JIS, CP932, EUC-JP, …

文字列/バイト列用のハッシュ関数ライブラリ

A Hash Function for Hash Table Lookupに載っているハッシュ関数(Jenkins Hash)をCommon Lispで実装した。 github: jenkins-hash(0.0.2) 作成の主な動機は以下の二つ: SBCLにはバイト列用のハッシュ関数がない *1 一つのキーから複数のハッシュ値を得たい場…

cc-dict: ハッシュテーブル

ハッシュテーブルを実装してみた。 ・cc-dict-0.0.3 チェイン法を用いたハッシュテーブルで、リンクリスト(チェイン)のノードを割り当てる際に自前のアロケータを使っている点以外は、特に変わったところもないと思う。 ベンチマーク 一応、ベンチマークも取…

Sanmoku(0.0.5): 原型や読みの情報取得に対応

Sanmoku(0.0.4): 辞書データサイズ縮小のコメントにて要望があったのでSanmokuを形態素の原型や読みの情報取得に対応させてみた。 Sanmoku本体のインターフェースは以前の同様*1で、原型・読み・発音の取得を行うためのFeatureExクラス(sanmoku-feature-ex-x…

UNF-0.0.4: サイズ削減

今日は久しぶりにUNF(ユニコード正規化ライブラリ)に手を加えていた。 大きな変更点は、正規化用変換テーブルを実現していたTRIEをDAWGにしたこと。 もともとは正規分解と互換分解用に、内容がほぼ等しいTRIEを別々に持っていたので、それを一つDAWGにして共…

Sanmoku(0.0.4): 辞書データサイズ縮小

この一週間でSanmokuの辞書データサイズの縮小をいろいろ試していたので、その結果を載せておく。 現時点でのバージョンは 0.0.4。 やったこと 試した主なこと。 データ 内容 サイズ(Gomoku-0.0.4 => Sanmoku-0.0.4) 連接コストデータ(matrix.bin) 類似品詞…

Sanmoku: 省メモリな形態素解析器

GomokuをベースにしたSanmokuという形態素解析器を実装した。 Gomokuに比べて解析時に必要なメモリ量が少ないのと初期ロード時間が短いのが特徴。 将来的には解析精度を若干落として、辞書サイズ*1をさらに削減する可能性もあるけど、現状は解析結果はGomoku…

Igo-0.4.3の辞書引きにDAWGを試す

Igo-0.4.3: 若干のパフォーマンス向上 - sileの日記の続き。 Gomoku(0.0.4)では辞書引き部分*1にDAWGを使っているので、それもIgoに取り込んで処理速度の変化を図ってみた。 比較 諸々の条件は前回と同様。 今回は新たにIgoのDAWG版が加わる。 総処理時間(1)…

Igo-0.4.3: 若干のパフォーマンス向上

Gomoku(0.0.4)で得た知見の一部をIgo(0.4.3)に取り込んでみた。 形態素解析の部分が少し速くなっている。 比較 MeCab(0.98)、Gomoku(0.0.4)、Igo(0.4.2,0.4.3)の処理速度の比較*1。 以前とはマシンも変わっているので、全部計り直した。 計時には約80MBの日…

Igo: GAE版の辞書データ読み込み速度向上

igo-gaeを修正して、辞書データ読み込みを速度を向上させた。 ※ igo-gaeの現在のバージョンは0.0.2。 修正内容概要 オリジナルのIgoでは、データ読み込みにはnio系パッケージのjava.nio.channels.FileChannelとjava.nio.MappedByteBufferを使っていた。 // M…

Gomoku: 辞書込みの形態素解析器

IgoをベースにしてJARファイルに辞書データを同梱した形態素解析器を作成した。 名前は同系統のGomoku(ver 0.0.1)。 特徴 開発コンセプト(?)は「JARファイルのみで形態素解析」と「サイズを(比較的)小さく」の二点。 このJARファイル一つで形態素解析が行え…

DAWG2(3): cl-dawg

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

erlterm: Erlang項とCommon Lispオブジェクトの相互変換

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

dict: ハッシュテーブル

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

HAMT(もどき): Erlangへの応用

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

HAMT: 実装してみた感想等

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

UNF: Common Lisp版

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

jada: DoubleArray Trieライブラリ

必要になったのでJava版のDoubleArrayライブラリを作成。 何だか最近はDoubleArrayばっかり実装している気がする... ・jada-0.1.0 実装で試したことのメモ書きや計時はまた今度。 以下、概要等。 概要メモ Java DoubleArray Trie 静的に与えられたキーセット…

UNF : Unicode正規化ライブラリ

UNFという名前*1で、C++でUnicode正規化を行うライブラリを実装 (ver 0.0.1)。 ついでに、それを利用したRuby拡張ライブラリも作成。C++やRubyで使える、軽くて高速なUnicode正規化ライブラリは、一年以上前から欲しい(作りたい)と思っていたので、作り終え…

ham: 分類性能評価的なもの

hamの分類性能評価的なもの。 そんなに本格的なことは行わない。 hamでは、基本的に『Practical Common Lisp』にて説明されているスパムフィルタリングの方法(ベイジアンフィルタの一種)をそのまま使わせてもらっている。 このベイジアンフィルタによる分類…

ham: ベイジアンフィルタ

手軽に使える二値分類器*1が急遽必要になったので、ベイジアンフィルタを用いたものを実装。 ham-0.0.1 素性にはNグラムを採用。 対応文字コードはUTF-8のみ。 多分実用程度には高速。 分類性能評価的なことはこれから行う予定。 それらしいデータを用意しな…

DAWG(4-3): MPHFライブラリ

前回までで最小完全ハッシュ関数(MPHF)の実装方法(の一つ)が分かったので、C++から使いやすくするためにライブラリ(と云う程の規模ではないけど)としてまとめておいた。 ・mphf-0.0.1実装の大枠は、前回のcommon lisp版のものと同様なので略*1。 ハッシュ関…

charseq

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

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

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

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

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

Igo : Common Lisp版

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

終了

先週の日曜から取り組んでいたJavaでの形態素解析器の実装がひとまず終了。 完成物: Igoまだ、例外処理周りの整備とか、ドキュメント作成とかは残っているが、実装が大幅に修正されることはもうなさそう。 特徴 思いつく特徴を列挙。 Java ほぼMeCab互換 MeC…

gzip圧縮 - 計時

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

バイト列→文字列変換ライブラリ(sbcl)

前回の知見(文字コード変換関数をC++で用意する云々)を反映して、FFIを利用した、バイト列を文字列に変換するsbclのライブラリを作成した。 ・unsafe-conv(0.0.1) 対応している文字コードは、UTF-8、Shift_JIS、EUC-JPの三つ。UTF-8以外のC++の変換関数につ…

Shift_JIS: 全角→半角変換

Shift_JISの全角文字を半角文字に変換するrubyの拡張ライブラリを作成した。 中身は変換テーブル*1を用意してマッピングを行っているだけの単純なものだが、毎回一から作るのは若干面倒なので、まとめてここにおいておく(ruby/sjis_conv-0.1.0.tar.gz)。使え…

DoubleArray動的追加版計時(Mersenne Twister利用)

前に少しDoubleArrayの動的追加時(のx-check関数で空き領域を探す際)に乱数を使えば処理速度を大幅に改善できるのでは、というようなことを書いた。 この方法だとメモリ使用量は結構増える(まだ正確には把握していない)が、確かに処理速度は大きく向上する。…

DoubleArrayプロジェクト

SourceForgeにDoubleArrayのC++ライブラリ用のプロジェクトを作成した。 名前は、DOubleARrayでDoar。 とりあえず現状のソース*1とごく簡単なドキュメントが載せてある。まだまだ安定版には遠いけど...。 10月中には、主要な開発は終わらせたい...。 *1:動的…

iterateパッケージ

Wikipediaのcommon lispの項目を読んでいたら、iterateというパッケージの存在を知った。少し興味を引かれたのでマニュアルに(簡単に)目を通してみた。 名前の通り、繰り返し処理を行うためのパッケージで、立ち位置的にはloopマクロに近いようだ。 >(iter (…

JSONデコード: ruby

最近はJSONばっかりだが、一昨日書いたC++版のJSONパーサのrubyバインディングを作ってみた。ソースコードは(ruby用にいろいろ変更が加わっているが)今まで書いてきたJSONのそれと基本的には同じものなので割愛する。 インストール用のファイル一式はここに…

cl-html-parse

以前、中途半端にHTMLパーサを実装したが、htmlをS式に変換してくれるcl-html-parseというライブラリが既にあったようだ。 > (asdf-install:install :cl-html-parse) > (net.html.parser:parse-html "<html><head><title>title</title></head><body></body></html>") --> ((:HTML (:HEAD (:TITLE "title")) (:BODY)))

デーモン

以前に書いた『HTTPリクエストの中身を表示するだけのHTTPサーバ』を拡張して、デーモンサーバを作成する機会があったので、それをまとめてpackage化した。 プロセス(サーバ)をデーモン化すること自体は、以下のような処理で出来た。 (require :sb-posix) (d…

HTMLパーサ

HTMLパーサは、たまに使いたいと思うのだが、なかなか良さそうなのが見つからないので、自分で作ることにした。ソース: html2list(0.0.2) 行数は250行くらいで、依存packageはcommon-utils。 とりあえず、行儀良く(?)書かれているHTMLは、だいたいちゃんとパ…

HTTPクライアント作成

簡単なcommon lispのHTTPクライアントをHTTPの勉強を兼ねて作成。ソースコード(*.lisp)は、約170行程度。まだまだ十分な完成度とは云えないが、せっかくなので公開してみる。 これ、tiny-http(0.1.3)。※置き場は暫定 インストールが必要な依存packageは次の…