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の『エイホ-コラシック法』の項目を参照。 自分…