algorithm
HAMT(Hash Array Mapped Trie) - sileの日記の続き。 前よりはちゃんとしたものを実装したので、それをうけての感想など。 作成物: hamt-0.2.0 前回からの相違点 基本的には『Ideal Hash Trees』*1に合わせた実装に修正*2。 変更点を挙げると、 HAMTのエント…
『Ideal Hash Trees』*1という論文を(必要なところだけ、だいたい)読み終わったので、そのメモ等。 概要 AMT(Array Mapped Trie)という基盤的なデータ構造を使って、ideal(nearly ideal)なHash Treesを作ろう、というような話。 AMTの応用例として、以下のよ…
『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…
ham(0.0.2)。 Nグラムベースのベイジアンフィルタ。 必要な分だけ実装してサクッと終わらせたかったけど、いくつか試したことが出てきたのでもう少し続ける。 UTF-8以外の文字コード hamは0.0.1ではUTF-8にのみ対応し、その文字Nグラム(N〜Mグラム)*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への変換…
AC法(エイホ-コラシック法)というものを知ったのでDoubleArrayで試してみた。 概要 入力テキストから、辞書(= 文字列セット)に登録されている文字列を効率的に検索するための方法らしい*1。 詳細は、Wikipediaの『エイホ-コラシック法』の項目を参照。 自分…
各種アルゴリズムを試す際のベースとなるような(シンプルな)DoubleArrayが欲しくなったので作成した。 構成など 多分、DoubleArrayとしては一番単純な構成*1。 ※ 以下で云う"ノード"は、"ノードのインデックス"の略のような意味合い 静的構築 各キーを改行区…
LOUDS(LOUDS++)とは直接は関係ない。 八回目にLOUDS++に試したこと(+α)をdoarにも適用してみたので、その結果。 試したこと 以下の二つ。 どちらもデータサイズを縮小することを目的とした変更。 無分岐ノードの削除 八回目にLOUDS++のtrieで試したものと基…
試したいことが出てきたので、少し延長して八回目。 目的 今回の目的は六回目で作成したtrieをベースとし、検索速度を向上させること。 結果 最初に結果から載せる。 入力データや計測方法等は七回目のそれらに準拠。 データサイズ検索所要時間(秒) louds-tr…
七回目。多分最後。これまで作ってきたものを他のtrie実装と比較する。 比較対象 louds-trie: LOUDS++によるtrieの実装。五回目を参照 louds-trie-tail: LOUDS++によるtrie(TAIL配列/圧縮有)の実装。六回目を参照 doar-0.0.12: DoubleArray(TAIL配列/圧縮有)…
前回に作成したLOUDS(LOUDS++)を用いたtrieの改良を試みる。 改良案 前回のtrie実装は、まだまだ全然最適化されていないので、改良すべき(or できるであろう)箇所は結構沢山ある。 案として、例えば... bit-vectorの実装方法 ... 他の実装方法の方が効率的(…
四回目まででLOUDS(LOUDS++)の実装方法は分かったので、今回は応用編。 LOUDSを用いてtrieを実装する(というかtrieを実装したソースコードを載せる)。 作るもの 実際に作成するのは以下の二つのコマンド。 mklouds-trie: ソート済みテキストファイルから、LO…
以下のような内容のファイルがあるとする。 # ファイル名: sample.txt ※ この部分はファイルに含まれない ab abc abef 1 1248 126 13579 これは次のような構造を持つトライ木として考えることができる。※'_ROOT_'は仮想的なスーパールート 今回は、上のよう…
LOUDSの四回目。 selectおよびrankが効率的に行えるビット配列(bit-vector)の実装。 参考 一応参考にしたのは、次の二つの論文 『A Simple Optimal Representation for Balanced Parentheses』 『Compressed Prefix Sums』 ただし、良く分からないところや、…
LOUDS++*1の三回目。 今回は、LOUDSの改良版であるLOUDS++に関する部分。 LOUDS++ LOUDSでは、木をビット列として表現していた。 参照: tree-to-lbs (defvar *tree* '(:a (:b) (:c (:f) (:g (:i))) (:d) (:e (:h)))) (tree-to-lbs *tree*) --> #*10111100110…
LOUDS++*1実装の続き。 前回はここ。今回は、この論文中に良く出てくるrankとselectという関数を自分なりに(= 間違っている可能性あり*2 )整理してみた。 rank, select rank及びselectは、前回作成したLBS(LOUDS bit-string)から、木のノード情報を取り出す…
『Enginnering the LOUDS Succinct Tree Representaion*』という論文に目を通し終わったので、(まだ理解はしていないが)これから実装に入る。現状での理解は次のような感じ。 Level-Order Unary Degree Sequenceの略 順序木の表現方法の一つ。静的構築。サイ…
DoubleArray(トライの一種)を利用して、マルチバイト文字列をユニコード文字列にある程度自動的に変換する、という試み(?)。 ちゃんとした形に整理するほどの気力はないので、一応動く程度のソースコードと覚え書きを残しておくことにする。 やること＆概要 …
配列を用いたスタック実装。 組み込みのlistを使ったスタックと比較したくて作成。 cl-igoでlistスタックを用いている箇所*1を、下記配列スタックで置換してみたが、特にメリットはなかった(逆に10%程度遅くなった。sbcl-1.0.34)。またどこかで使いたいこと…
llvmのチュートリアルの続きを読もうと思ったら、今はドキュメント関連のページがエラーで見れなくなっていたので、代わりに前から少し気になっていたコムソートを実装してみることにする。 参考サイト: コムソート - Wikipedia(最終更新 2009年11月29日 (日…
長さ制限付きハフマン符号化に合わせて、普通の*1ハフマン符号化のソースコードも整理。 ### 最初にハフマン符号化本体のソースを載せて、次にその中で利用しているヒープ(順序キュー)の実装を載せる。 ハフマン符号ソース。 参照: nlet, ???-obj-??? ;;;;;;…
長さ制限付きのハフマン符号化のソースコードは、以前にも載せたが、結構無駄が多かったので書き直し。 ついでに、整理中に気づいたこと(間違っているかもしれない!)を注釈として残しておく。 ;;;;;;;;;;; ;;;; 構造体 (defstruct obj ; コスト値を持つオブ…
メモ２。 各コードを符号化するのに最適なビット長は、(- (log (/ コードの出現数 コード総数)) 2)、で求めることができる。 そのため次のような関数で、入力データの最適なハフマン符号化のために必要なビット長が得られる。 ;; コードの出現頻度表を引数に…
長さ制限付きハフマン符号の整理中。 気づいたことメモ。 N個のコードを符号化するには、ビット長が最低(log N 2)*1は必要。 一番(最大の)ビット長が短くて済むのは、全てのコードを同じビット長でエンコードした場合。 いわゆる普通の文字表現(256文字を、8…
