追加・削除をサポートしたレコード付きダブル配列の実装を公開 - ny23の日記
線形分類器のライブラリに同梱して公開した動的ダブル配列に削除機能と登録キー／値のダンプ機能を追加実装して，別パッケージとして公開した．標準的な静的ダブル配列のライブラリのインターフェスに加えて，追加，削除，登録キーのダンプを実装してある．自分では使わない共通接頭辞検索が派手にバグっていたのでついでに修正． 主な特徴は， 高速な追加: 整列したキーの追加は std::unordered_map*1の2倍速．ランダム順だと同程度． 高速な検索: ノードの探索に局所性があれば std::unordered_map の4倍速．なければ同程度． 高速な削除: 検索と同程度の時間で登録キーを削除可． 省メモリ: レコード込みで登録キーの3-4倍程度の消費メモリ．静的に構築したトライには負けるが std::unordered_map と同程度． 短いコード: ヘッダファイル一つで構成，500行程度． 4
ALSIP2011に参加して簡潔データ構造の話を聴いて来ました - EchizenBlog-Zwei
香川県高松市にて開催されたALSIP2011(Second Workshop on Algorithms for Large-Scale Information Processing in Knowledge Discovery)に参加してきた。 簡潔データ構造で有名なRajeev Raman先生、NIIの定兼先生、PFIの岡野原さんが招待講演をして下さるということで以前から注目していた。 招待講演に加えて興味深い10本の発表がありとても楽しめた。私の勉強不足もあって初めて知ることが非常に多く勉強になった。簡単に内容をメモしておく(理解不足のため間違ったことを書いていたらすみません)。 今回の会議で最も興味深かったのがgrammer-based compressionというもので、これは例えばX=ababという文字列があったときにX1=a,X2=b,X3=X1X2,X=X3X3という感じで
極大部分文字列 - アスペ日記
Twitter で「極大部分文字列を求めるいいライブラリないかなー」とつぶやいていたら id:tkng さんに esaxx という岡野原さんのライブラリを教えてもらった。 esaxx というライブラリ名なのに説明が"stxx is ..."で始まったり、説明がところどころおかしい*1のはご愛敬として(最初は Suffix Tree のライブラリになるはずだったんだろうか)、確かにこれは便利そう。 早速、付属の "enumSubString.cpp" というサンプルをコンパイルして使ってみる。文字列はベタに "abracadabra"。 n:12 alpha:256 node:5 0 2 4 abra 1 5 1 a 2 2 3 bra 3 2 2 ra 4 12 0あれ？ これは極大部分文字列ではなくて、Suffix Tree の内部ノードだ。 "abra"、"bra"、"ra" はそれぞ
P2Pの専門知識ゼロから独自DHTを実装評価するまでの学習方法と参考資料まとめ - 情報科学屋さんを目指す人のメモ（FC2ブログ版）
何かのやり方や、問題の解決方法をどんどんメモするブログ。そんな大学院生の活動「キャッシュ」に誰かがヒットしてくれることを祈って。 P2P、特にDHTの前提知識が無い状態から、オリジナルDHTアルゴリズムを実装・評価できるようになるまでの学習方法と参考資料をまとめました。 基本的なアルゴリズムの仕組みから、実装評価に用いるツールキットの使い方までを短期間で学習することが出来ます。 「P2Pに関する卒論を書こうと思っている人」や「P2Pアプリケーションの開発前に、アルゴリズムをテストしたい人」、「なんとなくP2Pアルゴリズムに興味が出た人」などにぴったりだと思います。また、研究室での後輩教育用資料にするのも良いと思います。実際に使いましたし。 ここで紹介する資料一覧は以下の通りです。 資料１：「ChordアルゴリズムによるDHT入門」 資料１ーオプション１：「DHTアルゴリズムSymphony
アルゴリズムの勉強のしかた - きしだのHatena
この記事で、アルゴリズムの勉強はアルゴリズムカタログを覚えることじゃないよということを書きました。 プログラムの理論とはなにか アルゴリズムの勉強というのは、スポーツで言えば腕立て伏せや走り込みみたいな基礎体力を養うようなもので、「ソートなんか実際に自分で書くことないだろう」とかいうのは「サッカーは腕つかわないのに腕立ていらないだろう」とか「野球で1kmも走ることなんかないのに長距離の走り込みいらないだろう」とか言うようなものです。 Twitterでアルゴリズムの勉強とはなにかと尋ねられて、「アルゴリズムの基本的なパターンを知って、それらの性質の分析のしかたをしって、いろいろなアルゴリズムでどのように応用されているか知って、自分が組むアルゴリズムの性質を判断できるようになることだと思います。 」と答えたのですが、じゃあ実際どういう本で勉強すればいいか、ぼくの知ってる本からまとめてみました。
簡潔データ構造超入門VI 〜これまでのまとめと集合の簡潔構造〜 - EchizenBlog-Zwei
今回は集合の簡潔構造について話をする。今回で簡潔構造の初歩的な話は一段落となるので、いままでの話をまとめつつ集合の簡潔構造とは？どういうことに使えるのか？という話をする。 集合の簡潔構造は大変重要で、ここを理解すれば簡潔構造の基礎はだいたいOKといえる。 前回までの記事： 簡潔データ構造超入門 〜つくって学ぶ簡潔ビットベクトル〜 - EchizenBlog-Zwei 簡潔データ構造超入門II 〜ちょっとだけ実用的な簡潔ビットベクトル〜 - EchizenBlog-Zwei 簡潔データ構造超入門III 〜簡潔ビットベクトルで転置インデックスを効率的に実装する〜 - EchizenBlog-Zwei 簡潔データ構造超入門IV 〜LOUDSというメモリ効率のよい木構造の話(準備編)〜 - EchizenBlog-Zwei 簡潔データ構造超入門V 〜LOUDSというメモリ効率のよい木構造の話(本編
LOUDSトライのライブラリの性能を比較してみた - EchizenBlog-Zwei
LOUDSは木構造を非常に小さなデータサイズで表現することができる簡潔データ構造の一種。とくに自然言語処理ではトライ木という木構造が重要で形態素解析や日本語入力(IME)など多くの場面で利用されている。 トライ木としてはdouble arrayが有名。LOUDSはdouble arrayより速度で劣る反面、データサイズを非常に小さく抑えることが可能である。このため近年、大規模データを扱うためのデータ構造として注目されている。 LOUDSを用いたトライ木には優れた実装がいくつかある。なかでも有名なものとして@s5yata氏によるmarisa-trieと@hillbig氏によるux-trieがある(ux-trieのクローンであるrx-trieはGoogleIMEで利用されている)。 今回はこれらのライブラリと、参考までに私の作ったerika-trieを使ってみて簡単に性能比較をしてみた。 評価
(続)LOUDSトライのライブラリの性能を比較してみた - EchizenBlog-Zwei
LOUDSトライを比較した記事を書いたところ@overlast氏からwikipediaタイトルのような偏りの少ないデータでも評価してはどうか、という賢明なアドバイスを頂いたので試してみた。 LOUDSトライのライブラリの性能を比較してみた - EchizenBlog-Zwei http://dumps.wikimedia.org/jawiki/latest/ からwikipediaタイトルを取得した。 $$ wc -l jawiki-latest-all-titles-in-ns0 1231018 jawiki-latest-all-titles-in-ns0約123万件ある。これを用いてトライを作成すると以下のようなデータサイズとなった。 元データ : 26960268 byte marisa-trie : 7,199,728 byte ux-trie : 10,364,932 byte
LCP(Longest Common Prefix)を用いたSuffix Arrayの検索 - EchizenBlog-Zwei
Suffix Arrayは「インデックスの構築」と「キーワードの検索」からなる。それぞれ構築には文字列のsortが、検索には文字列の二分探索が必要になる。 以前にCompressed Suffix Arrayのライブラリtsubomiを実装したときにはsortについてはマルチキー・クイックソート(multikey-quicksort)というアルゴリズムを用いた。一方で二分探索については特に工夫をしていなかった。 さすがにこのまま放っておくのは気が引けたのでSuffix Array論文を読みなおしてみたらLCP(Longest Common Prefix)を用いた二分探索の方法が書いてあった。シンプルだが賢い方法だったのでメモしておく。これはすごい(というか今まで読み飛ばしてたことのほうが問題ですね。はい)。 さて。まずLCP(Longest Common Prefix)とは何かと言うとその
簡潔データ構造(Succinct Data Structure)で最初に読むと良さそうな論文 - EchizenBlog-Zwei
最近、簡潔データ構造(Succinct Data Structure)まわりの論文を色々読んでいる。その中で良さそうなものをいくつかピックアップしてみた。まだ調査中なので他に良いものがあったら教えてもらえると嬉しいです。 (1) Space-efficient Static Trees and Graphs(link) G. Jacobson; IEEE1989 まずはLOUDS論文。簡潔データ構造の元祖なので最初に読むと良さげ。 (2) Succinct Indexable Dictionaries with Applications to Encoding k-ary Trees and Multisets(link) R. Raman, V. Raman, and S. S. Rao; SODA2002 簡潔ビットベクトルは通常n+o(n)なんだけど、これをnH0+o(n)にしたよ、
DSIRNLP#1で発表しました「TRIEにトライ！〜今日からはじめるTRIE入門〜」 - EchizenBlog-Zwei
昨日開催された「第1回 データ構造と情報検索と言語処理勉強会(DSIRNLP)」に発表者として参加しました。主催者の@overlastさん、発表者の皆さん、ボランティアの皆さん、会場を提供してくださったミクシィさん、そして発表を聞いてくださった皆さん。どうもありがとうございました。 また発表スライドについては@overlastさん、@uchumikさん、@machyさん、@nokunoさんにチェックして頂きました。特に@uchumikさん、@machyさんより頂いた意見のおかげでスライドの質が向上しました。ありがとうございました。 発表スライド： (scribdのembedがうまくいかなかったので暫定的にリンクおいておきます) TRIEにトライ！〜今日からはじめるTRIE入門〜 本記事では質疑応答でフォローしきれなかった部分を中心に、私の発表の補足的なものを書いて行きます。 会のまとめ的な
海風に揺れる一輪のTRIEライブラリ erikaを作ってみたよ - EchizenBlog-Zwei
注意：この記事の内容は古いものです。 最新版のerika-trieは erika-trie(実用版)とキーワード抽出ツールerika_extractを作ったよ - EchizenBlog-Zwei うっかり手が滑って自分で☆つけてしまいましたが自画自賛してるわけではないです・・・。 をご参照ください。 最近TRIE(トライ)に対する興味が高まってきたので勉強のためにライブラリを作っていた。一応完成したので公開しておく。普通のTRIEとLOUDSによるTRIEの二つを実装した。 名前はerika。もしくはerika-trie。以前作ったCompressed Suffix Arrayのライブラリがtsubomiだったので、今回はerikaにした。コードはGoogleCodeのtsubomiと同じところにおいてある。というかtsubomiの付属品状態。開発はlinuxで行ったが特に環境に依存した
【書籍】Programming Interview Exposed - nokunoの日記
というわけで書籍「Programming Interview Exposed」を3章まで読んだので紹介したいと思います。題名は直訳すると「プログラミング面接晒し」。著者らが就職活動で経験したプログラミング課題の解説をするという生々しい内容です。英語圏のテクノロジー企業ではプログラミング課題を行なうのが一般的なので、プログラマーとして就職するということはどういうことか？という疑問にプログラミング課題の説明を通して答えてくれます。 第1章ではプログラマーとしてやっていくために必要な一般的な事項が説明されています。このあたり、自分の就活のときに読みたかったなあ。 自己分析 得意なプログラムはフロントエンドかバックエンドか？ ユーザーインターフェースデザインは得意か？ デバッグやテストは得意か？ プログラマーを続けてたいのか、いずれはマネージャを目指すのか？ 大企業かベンチャーか？ オープンソース
ux... - ny23の日記
ux-trie（簡潔データ構造のトライで，tail を実装してさらに tail 自体もトライ化して圧縮する）のバグが直ったようなので，トライのサイズや検索性能を調べているのだけど，長い tail を持つようなデータだと，トライのサイズが tx 比で 1/2 近くまで小さくなる一方，検索は（辞書順だと）tx 比で倍程度遅くなるようだ（tail を圧縮しないと tx よりトライのサイズが大きくなる）．これぐらい極端だと，かえって潔い感じかもしれない．トライ（ダブル配列，簡潔データ構造）と STL コンテナ - ny23の日記に ux を加えて再実験したものは以下の通り． ====================================================================== Wikipedia-en 記事タイトル | Build | Search | Sea
レコード付き動的ダブル配列の実装も公開 - ny23の日記
以前トライ（ダブル配列，簡潔データ構造）と STL コンテナ - ny23の日記で比較に使った自作のレコード付き動的ダブル配列 (dda) の実装も公開．以下の論文のアルゴリズムを実装したもの． 矢田晋, 田村雅浩, 森田和宏, 泓田正雄, 青江順一．ダブル配列による動的辞書の構成と評価, 情報処理学会第71回全国大会, 1-263-1-264頁, 2009年3月. レコード付き動的ダブル配列 - ny23の日記から始まり，レコード付き動的ダブル配列 - ny23の日記, レコード付き動的ダブル配列 - ny23の日記, レコード付き動的ダブル配列 - ny23の日記 と二週間かかって書いた僅か360行の c++ ヘッダファイル．動的ダブル配列は上の分類器の学習手法で素性の重みの管理に使っているので，学習手法の実装に同梱した．std::tr1::unordered_map ベースのトライに
トライ（ダブル配列，簡潔データ構造）と STL コンテナ - ny23の日記
以前実装した構築速度重視の動的ダブル配列 (表中 dda) の構築速度を Darts, darts-clone (0.32g beta5, 0.32e5), DASTrie (1.0), doar (0.0.10)，簡潔データ構造を利用したトライ (tx 0.16) ，STL コンテナ (std::map, std::tr1::unordered_map) 辺りと比べてみた．キー集合としては，中規模で疎な集合（Wikipedia 英語版記事タイトル）と小規模で密な集合（郵便番号辞書）を用いた． ====================================================================== Wikipedia-en 記事タイトル | Build | Search | Search* | Size [bytes] =================
レコード付き動的ダブル配列 - ny23の日記
ブロック管理の詳細を、ダブル配列の世界的権威の某氏に昨日伺ったので実装し直し。400行近くなってしまった。デバッグ中。体調微妙なので深刻なバグを作り込んでないか心配。 [追記] ブロックの連結リストが壊れるバグを修正してデバッグ完了。ランダム順追加でも50秒程度(辞書順だと20秒)とかなり高速にバイナリのダブル配列を構築できるようになった。動的ダブル配列の実装もこれで一段落か。370行。後二三日最適化したら、予定していた用途に使ってみよう・・・ [追記] 遷移節点集合や，ブロック内未使用要素リストをソートしないようにして高速化。343行。float の値を格納できるようにして，予定した用途に使ってみたら、ハッシュベースのトライを使う場合に比べて，実行速度は約2倍となった。これだけ速ければまあ満足だ。苦労したかいがあったというところ。ダブル配列万歳。 [追記] ところで，値をダブル配列に保存
marisa-trieを使ってみた - nokunoの日記
id:s-yata さんの新作trieライブラリが公開されていたので使ってみました。環境はMac OS Xです。やた＠はてな日記 marisa-trie - Project Hosting on Google Code インストール普通にGoogle Codeからダウンロードしてインストールします。 $ wget http://marisa-trie.googlecode.com/files/marisa-0.0.1.tar.gz $ tar xfz marisa-0.0.1.tar.gz $ cd marisa-0.0.1/ $ ./configure $ make $ sudo make install 動作確認Wikipedia N-gram（nokunoの日記）よりbigramを格納し、marisa-predictによって前方一致検索を行いました。 $ cat bigram.txt
トライ（ダブル配列，簡潔データ構造）と STL コンテナの比較（最新版） - ny23の日記
[2011/11/30 更新; std::(unordered_)map でメモリ使用量を見積もる - ny23の日記に従い，STL コンテナのメモリ使用量を計測] [2011/02/21 更新: marisa-trie 0.1.3; 発表資料（Prefix/Patricia Trie の入れ子による辞書圧縮） - やた＠はてな日記 にてこの記事の実験結果を引用されているので，以後原則更新しないこととする．なお，marisa-trie は 検索時間が短くなりました - やた＠はてな日記 にあるように，marisa-0.2.0-beta3 以降ではさらに検索が速くなっています．] [2011/02/18 更新: marisa-trie の仕様変更に伴い，追記の記述を整合性が取れるよう変更; 最新版では未確認] id:s-yata さんが marisa-trie を公開されたので，例によってベ
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
乱択アルゴリズム紹介(Bloom Filter) - Preferred Networks Research & Development
