二バイトコード(UTF-16)を用いてDoubleArrayを構築する際のトライ探索方法 - sileのブログ
これまではDoubleArrayを構築する際には、ソースとなるトライのノードを深さ優先順で探索しDoubleArrayへと変換していた。 トライのキーセットとなる文字列のエンコーディングがUTF-8等の一バイトコード(?)の場合は深さ優先順探索でも特に問題はないが、UTF-16等の二バイトコード文字列に同様の探索順を採用すると、最終的な配列(DoubleArray)中に占める空き要素(未使用要素)の数が多くなる、という問題がある。※ 少なくとも自分の経験上は。 優先順位探索 二バイトコード文字列をキーとする場合は深さ優先ではなく、各ノードの子ノードの数の多い順にトライを探索(+DoubleArrayに変換)した方が、サイズ効率が良くなる(ように思う)。 以下は、深さ優先探索と子ノード多い順探索でのDoubleArrayのサイズの違い。 ※ DoubleArray構築にはjada-0.1.3
SA-IS: SuffixArray線形構築 - sileのブログ
『Linear Suffix Array Construction by Almost Pure Induced-Sorting』*1という論文を参考にして、Induced-Sortingを用いたSuffixArrayの線形構築アルゴリズム(SA-IS)をCommon Lispで実装した。 以下、そのソースコードとメモ書き。 線形構築 汎用ソートアルゴリズムと今回実装したSA-ISアルゴリズムでのSuffixArray構築時間の簡単な比較。 百文字〜一千万文字の文字数のテキストを入力として与えて、その構築時間を計測。 百文字千文字一万文字十万文字百万文字一千万文字 汎用ソート*20.000 sec0.002 sec0.023 sec0.358 sec5.604 sec94.196 sec SA-IS0.031 sec0.120 sec0.135 sec0.335 sec2.580 sec2
Igo: JavaScriptで形態素解析 - sileのブログ
Igo: GoogleAppEngineで形態素解析サーバで用意したサーバ(※追加修正あり。後述)を使って形態素解析を行うJavaScriptを書いてみた。 制限 結構制限が多い。 対応がUTF-8のみ レスポンスのJSONに含まれる文字列内のASCII以外の文字を16進数表記(\uXXXX)にエスケープすればEUC-JPやShift_JISでも大丈夫だった(2010/10/20) JSONPを使ってサーバと通信しているため、一回のリクエストテキストの最大長が制限される 具体的に何文字まで可能かは使用ブラウザとGoogleAppEngineの制限に左右される(数百文字なら大丈夫?) (詳しくは知らないけど)解析サーバがGoogleAppEngineの使用制限を越えたら当然使えなくなる 形態素解析JavaScript 形態素解析を行うJavaScript関数群。 やっていることは、ほとんどi
HAMT(Hash Array Mapped Trie) - sileのブログ
『Ideal Hash Trees』*1という論文を(必要なところだけ、だいたい)読み終わったので、そのメモ等。 概要 AMT(Array Mapped Trie)という基盤的なデータ構造を使って、ideal(nearly ideal)なHash Treesを作ろう、というような話。 AMTの応用例として、以下のようなものが説明されている。 Hash Array Mapped Trie(HAMT) ハッシュマップ 各種操作がO(1) ハッシュテーブルの初期サイズを(あまり)気にする必要がない 要素が増えた場合のリサイズのコストが小さい*2 リサイズ不要な実装も可能だがその場合はO(log N)に。※ Nは要素数。今回の実装はこっち。 成功検索時、キーの比較は一回しか生じない ただし、キーのハッシュ値の計算処理は(異なるハッシュ関数で)複数回行われることがある。 Clojureの組み込みのハ
Micterの単語分割部の高速化を試してみた結果 - sileのブログ
tkngさんが作成したMicterという単語分割器の分割部を高速化できるような気がしたので試してみた。 そのメモ。 試した結果のソース一式はmimicという名前でgithubに保存しておくことにする*1。 結果 まず、結果から*2。 # 分割対象のテキスト(のサイズ) $ ls -lh /tmp/test.data -rw-r--r-- 1 user user 41M 2010-07-05 22:48 /tmp/test.data # MeCab $ time mecab -Owakati /tmp/test.data > /dev/null real 0m10.843s # 10秒 user 0m10.777s sys 0m0.068s # Micter $ ls -lh micter.model -rw-r--r-- 1 user user 1.8M 2010-07-06 08:30
ユニコード正規化 - sileのブログ
ユニコード正規化のcommon lispによる実装*1。 ※ common lisp処理系としては、SBCL等のユニコード(UTF-32)対応のものを想定 参照 実装に際して参考にさせてもらったサイト。 ・UAX #15: Unicode Normalization Forms ・Unicode正規化 正規化に必要なデータ。 ・UnicodeData.txt: 各ユニコード文字の属性定義表 ・CompositionExclusions.txt: 正規合成時に除外する文字の一覧表 概要 ユニコード正規化の概要。 ※ 自分用の(不正確な)メモでしかないので、ちゃんと知りたい人は他のサイトを参照のこと ユニコードの正規化の形式は四種類。 NFD、NFC、NFKD、NFKC。 NFは、Normalization Form(正規化形式)の略。 Dは、Decomposition(分解)の略。 Cは、C
LC_ALL環境変数とsortコマンド - sileのブログ
自分の環境では、sortコマンドを実行する時にLC_ALL環境変数に'C'をセットするかしないかで、処理終了までの時間が著しく変わる。 # 約40万行のデータ > wc -l words 392126 words # 入っているのはUTF-8の日本語(IPA辞書を利用) > head words やぼったい やぼったし やぼったから やぼったかろ やぼったかっ # 普通のソート > time sort words > /dev/null real 0m37.158s user 0m37.098s sys 0m0.056s # LC_ALL=Cでのソート > time LC_ALL=C sort words > /dev/null real 0m0.293s user 0m0.284s sys 0m0.008s ロケールを考慮してソートするかどうかの違いだと思うが(LC_ALL=Cの場合は、
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
