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のエント…
SBCLのマニュアル(ver 1.0.37)にも書いてあることだけど ... 。 通常は構造体のインスタンスを作成するとヒープ上にそのための領域が割り当てられる。 これには(おそらく)ヒープ割り当て＋GC処理のコストが伴うので、構造体としてまとめるよりも、その各フィ…
『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に対応しているなら、他の処理系でも一…
前回からだいぶ間が空いたけど、jadaで試したことのメモ。 二バイトコード Javaは文字を二バイトコード(UTF-16)で表現しているので、jadaで実装されたトライの各ノードで(遷移に)用いられるコード値の最大値も0xFFFFとなっている。 トライの遷移コードが一バ…
必要になったのでJava版のDoubleArrayライブラリを作成。 何だか最近はDoubleArrayばっかり実装している気がする... ・jada-0.1.0 実装で試したことのメモ書きや計時はまた今度。 以下、概要等。 概要メモ Java DoubleArray Trie 静的に与えられたキーセット…
現在は自分の主要開発言語の内の一つがcommon lispということもあり、エディタには基本的にEmacsを使っている。 ただ単純にエディタとしてはEmacsよりもvi(vim)の方が自分の好みにあってそうな気がする。※まともに使えていないので、気がするだけだけど... E…
UNFという名前*1で、C++でUnicode正規化を行うライブラリを実装 (ver 0.0.1)。 ついでに、それを利用したRuby拡張ライブラリも作成。C++やRubyで使える、軽くて高速なUnicode正規化ライブラリは、一年以上前から欲しい(作りたい)と思っていたので、作り終え…
ユニコード正規化のcommon lispによる実装*1。 ※ common lisp処理系としては、SBCL等のユニコード(UTF-32)対応のものを想定 参照 実装に際して参考にさせてもらったサイト。 ・UAX #15: Unicode Normalization Forms ・Unicode正規化 正規化に必要なデータ。…
ham(0.0.2)。 Nグラムベースのベイジアンフィルタ。 必要な分だけ実装してサクッと終わらせたかったけど、いくつか試したことが出てきたのでもう少し続ける。 UTF-8以外の文字コード hamは0.0.1ではUTF-8にのみ対応し、その文字Nグラム(N〜Mグラム)*1を素性…
hamの分類性能評価的なもの。 そんなに本格的なことは行わない。 hamでは、基本的に『Practical Common Lisp』にて説明されているスパムフィルタリングの方法(ベイジアンフィルタの一種)をそのまま使わせてもらっている。 このベイジアンフィルタによる分類…
手軽に使える二値分類器*1が急遽必要になったので、ベイジアンフィルタを用いたものを実装。 ham-0.0.1 素性にはNグラムを採用。 対応文字コードはUTF-8のみ。 多分実用程度には高速。 分類性能評価的なことはこれから行う予定。 それらしいデータを用意しな…
Nグラムを取り出すC++のクラスを作成したのでメモ。 UTF-8のみ対応。 /* * ファイル名: ngram.hh */ #ifndef TOKENIZER_NGRAM_HH #define TOKENIZER_NGRAM_HH #include <algorithm> #include <vector> #include <cstring> namespace Tokenizer { class Ngram { public: Ngram(unsigned mi</cstring></vector></algorithm>…
任意のコマンドをデーモンプロセスとして実行するようなコマンドが欲しかったので実装してみた。 /*** * ファイル名: daemonize.c * コンパイル: gcc -o daemonize daemonize * * 概要: * 引数で渡したコマンドをデーモンプロセスとして実行する。 * * 使い…
前回までで最小完全ハッシュ関数(MPHF)の実装方法(の一つ)が分かったので、C++から使いやすくするためにライブラリ(と云う程の規模ではないけど)としてまとめておいた。 ・mphf-0.0.1実装の大枠は、前回のcommon lisp版のものと同様なので略*1。 ハッシュ関…
四回目の中盤。 最小完全ハッシュ関数(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を参考にした。 た…
DAWGのキーに一意なIDをマッピングするために、前回考えた方法は、サイズ的に効率的に実装するのが無理そうなことが分かったので、別の方法に変更することに。 IDへのマッピング 方法概要。 DAWGはIDのことを考慮せずに普通に構築する キーのIDは、完全最小…
最初に前回作成した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 …
AC法(エイホ-コラシック法)というものを知ったのでDoubleArrayで試してみた。 概要 入力テキストから、辞書(= 文字列セット)に登録されている文字列を効率的に検索するための方法らしい*1。 詳細は、Wikipediaの『エイホ-コラシック法』の項目を参照。 自分…
