大規模グラフ処理フレームワーク Pregel のオープンソース実装 Bagel とか - Standard ML of Yukkuri
ref: http://portal.acm.org/citation.cfm?id=1582723大規模グラフ処理フレームワーク Pregel の論文を読み, BSP (Bulk Synchronous Parallel) モデルで実装したいグラフのアルゴリズムがいくつかあったのでオープンソース実装を探してみた. GoldenOrb, Phoebus, HAMA (汎用的なBSP model), そして Bagel などいくつかの実装があるようで, GoldenOrb は Java, Phoebus は Erlang で実装されており, Bagel は Scala で書かれている. Bagel は Spark 上で動くシンプルな実装 (たったの 150 行程度) で, 大規模なタスクに対してもスケールする運用が可能に思えたので Bagel を使ってみることにした. (Phoebus は
LIBLINEARを用いた機械学習入門(単語分割)
このページでは機械学習のツール(LIBLINEAR)を利用して、実際に分類問題を解くにはどういう手順を経るかということについて解説します。つまり、Kytea(京都テキスト解析ツールキット)における簡易版の単語分割モデルを作ってみようということです。 なお今回はプログラミング言語としてRubyを用いますが、Rubyの知識がなくても実装ができるように解説するよう心がけます。また、必要以上に細かく書いてあるかもしれませんが、不要な方は適宜読み飛ばして下さい。 細かい説明はすっとばしてやり方を見る 機械学習って？ 朱鷺の杜Wiki 「機械学習」がわかりやすいかと思います。 ひとことで言うと、「訓練データを与えてそこから機械に問題の解き方を学んでもらい、別の問題を解いてもらうこと」です。 教師あり学習・教師なし学習 機械学習は大きく「教師あり」と「教師なし」に分かれます。 「教師あり学習」とは
Python でグラフ・(疎)行列計算するためのライブラリを紹介するよ - 武蔵野日記
PageRank とか HITS といったリンク解析ではグラフの計算が頻発するのだが、Python でそのあたり書くときの話をまとめてみる。グラフは行列で表現できる(ノード×ノード次元の行列 A を考えて、ノード i からノード j にエッジがあるとき、A[i,j] に値を入れておけばよい。無向グラフのときは A[i,j] = A[j,i] なので対称行列になる)ので、要は行列を手軽に扱えるライブラリの紹介である。 実は Python の行列演算ライブラリはどれも lapack/blas を内部的に呼んでいるので、C/C++ 等と比較してもそんなに遅くない。それどころか、自動的に並列化できるところは並列化してくれたりするので、まれに C より速いこともあるらしい。特に巨大なグラフを作る場合、ほとんどの処理は C などで書かれた関数に飛ぶので、速度的な問題は無視してもいいくらいである(逆に、
rxを読んだメモ - 射撃しつつ前転 改
rxはGoogle日本語入力（Mozc）でも使われているTrieのライブラリである。LOUDSというツリーを表す簡潔データ構造を使ってTrieを実現している。第2回自然言語処理勉強会@東京に行ってきて、そういえばrxは読んでなかったなと思ったので、ちょっとだけ読んでみた。あくまでもメモ書きである。絵があると100倍ぐらいわかりやすくなる気がするけどメモなので絵は描きません。 読んだのは現在公開されている最新版であるrx-1.0rc4。 rxというのとrbxという2つの機能がある。rxが実現しているのはあくまでもtrieで、値的なものとしてはノードIDしか取れない。rbxはノードIDのような整数から、任意の長さのバイト列を引っ張ってくるためのライブラリ。普通の配列は当たり前だが要素が固定長であるので、要素が可変長であるというところがrbxの大きな特徴である。 rxでのエッジに対する文字割り当
Gomoku: MeCabと形態素解析速度比較 - sileのブログ
Igoの時と同じように、Gomoku(0.0.4)とMeCab(0.98)の形態素解析速度を比較してみた。 計時結果 テキストには青空文庫より取得の夏目漱石の『こころ』(x256. 136M. UTF-8)を、辞書にはMeCabのサイトより入手可能なmecab-ipadic-2.7.0-20070801*1を使用。 総処理時間(1)行読み込み時間(2)1 - 2 MeCab34.781s0.134s34.647s Gomoku33.313s0.989s32.324s 例によって適当な比較なので何とも云えないけど、今回測った限りではMeCabよりも速くなっている*2 *3。 計時用のプログラム MeCabの計時に用いたプログラム: /** * ファイル名: mec.cc * コンパイル: g++ -O3 -omec mec.cc `mecab-config --libs` * 計時方法: t
Gomoku: 辞書込みの形態素解析器 - sileのブログ
IgoをベースにしてJARファイルに辞書データを同梱した形態素解析器を作成した。 名前は同系統のGomoku(ver 0.0.1)。 特徴 開発コンセプト(?)は「JARファイルのみで形態素解析」と「サイズを(比較的)小さく」の二点。 このJARファイル一つで形態素解析が行える(外部の辞書データ不要)、という点が最大の特徴。 ただし、その分辞書のカスタマイズ性には乏しい。 ※ 辞書を変更する場合はjarファイルごと取り替える必要がある その他の特徴を列挙: 辞書データサイズがIgoより小さい 辞書込みJARファイルのサイズは4MB程度。解凍時は10MB程度*1。※ Igoは辞書サイズは40MB程度 辞書のデータサイズを節約するために、形態素の素性から品詞以外の情報を除外 そのため原型や読み等の情報を解析結果から得ることは不可能 (デフォルトの)辞書にはIPADIC(mecab-ipadic
新しいトライのライブラリを公開しました - やた＠はてな日記
概要 トライのライブラリを公開しました．ドキュメントはまったく用意できていませんが，とりあえず使えます．（追記 2011-01-09）ドキュメントを追加しました． http://code.google.com/p/marisa-trie/ ドキュメント ベンチマーク 使い方 インタフェース ツール インストール ビルド・インストールの方法は configure と make です．以下のようにすればインストールできます． ./configure make make check sudo make install インストールせずに試したいという方は，make install を省略して，tools/ 内部のツールを使うなり，lib/marisa/trie.h を見て使い方を確認するなりしてください．インストールせずにライブラリを利用するには，lib/ 以下のヘッダすべてと lib/libm
wat-arrayを使った2次元探索プログラム - tsubosakaの日記
岡野原氏の作成したwavelet木を使った高速配列処理ライブラリwat-arrayを利用して、2次元探索のプログラムを書いてみた。 なお、自分はwavelet木のアルゴリズムについては全く分かってないですが、wat-arrayでは配列に対して、操作を行うインターフェイスがしっかり与えられているのでそれを見ながら作りました。 問題定義 2次元座標の集合P={(x,y)}が与えられる。Queryとして(xs,xe,ys,ye)が与えられたときにPの中でxs <= x < x, ys <= y < yeを満たす点の数を答えるというものを考える。 なお、Pの内容は途中で変化したりすることはないものとする(変更が加わった場合は一から作り直す)。 インターフェースとしては次のようになる、2次元座標の表現にはpairを用いることにする。 namespace wat2DSearch{ typedef st
2010-01-28
SVMとかを自前で作ったのかインストールがめちゃくちゃ簡単になったcabochaがあると聞いたので入れてみた。 http://chasen.org/~taku/blog/archives/2008/01/cabocha_060_pre.html 前準備 いれたもの mecab http://sourceforge.net/projects/mecab/files/mecab/0.98/mecab-0.98.tar.gz/download ipadic http://sourceforge.net/projects/mecab/files/mecab-ipadic/2.7.0-20070801/mecab-ipadic-2.7.0-20070801.tar.gz/download CRF++ http://sourceforge.net/projects/crfpp/files/crfpp/
新年のごあいさつ 今年の課題 | 国立国会図書館-National Diet Library
新年おめでとうございます。 世界の情勢は変化のスピードを増しています。複雑化した国政課題に対応するために、本年は国内外の調査研究機関・研究者との連携を強化することを通じて、国立国会図書館の特色ある調査を一層充実させていきたいと考えております。 また、本年は電子出版・流通、電子図書館化の流れがいよいよ本格化する年であると存じます。国立国会図書館における最大の課題の１つは、現在運用しているOPAC検索を含んだ図書館業務システムを全く新しいシステムに入れかえ、来年１月から運用開始することであります。幸い準備やテストは順調に進んでおり、新しい時代の要求にこたえる情報探索システムを提供するなど、利用者の皆様今年の課題にご満足いただけるものになると思っております。 もう１つは電子納本制度の法制化であります。電子出版物が増加して来ている中で、これを本格的に収集・保存・活用するために国立国会図書館法を改正
オープンソースのTrieライブラリまとめ - nokunoの日記
最近、趣味で開発しているStaKKのためにTrieライブラリを書いているのですが、参考にするためオープンソースのTrieライブラリについて調べました。簡潔データ構造を用いたものが中心です。 @hillbig氏によるもの tx LOUDSによる圧縮でメモリ使用量を削減したTrieライブラリ。 関連記事：Tx: Succinct Trie Data Structure Engineering the LOUDS Succinct Tree Representation - 射撃しつつ前転ux txの改良版。tailの圧縮によりtxの1/2くらいのサイズになるらしい。要チェック。 関連記事：ux... - ny23の日記id:s-yata 氏によるもの taiju LOUDSを含む簡潔データ構造を用いた大規模Trieライブラリ。sumire-triesインメモリの簡潔データ構造を実装した大規模T
神戸新聞｜阪神・北摂｜ぬいぐるみ、図書館にお泊まり 翌日写真に 宝塚
子どもたちがお気に入りのぬいぐるみを一晩、図書館に預けると、翌日、夜の図書館でぬいぐるみが冒険している様子を撮影した写真がもらえる‐。こんなイベントが「ぬいぐるみの図書館のおとまり会」と銘打って１１日夕から翌１２日にかけて、宝塚市立西図書館（同市小林２）で開かれる。（上杉順子） 子どもたちに本に興味を持たせよう‐と米国で取り組まれている催しで、最近、日本に紹介された。国内での実施はまだ珍しいという。 「国民読書年」を記念した企画の一環。本の読み聞かせ会にお気に入りのぬいぐるみを持ってきてもらい、子どもたちは終了後、ぬいぐるみを置いて帰る。その後、図書館職員が館内のさまざまな場所でぬいぐるみが遊んでいる写真を撮り、翌日、迎えに来た子どもたちに、その写真や、ぬいぐるみが読んで気に入ったという設定の絵本を貸し出す‐という趣向。 米国では、簡単で安全な上、子どもが非常に喜ぶ‐と、各地で催されている
Fm-index version 2
FM-Index Version 2 Paolo Ferragina and Rossano Venturini Dipartimento di Informatica, University of Pisa, Italy The present software offers a new implementation of the compressed full-text index data structure, called FM-index. The FM-index was proposed by Paolo Ferragina and Giovanni Manzini in [FOCS '00]. An implementation of the FM-index (vers. 1.0) was presented in [SODA '01]. This data struct
CSAを使った全文検索ライブラリtsubomiを公開してみる - EchizenBlog-Zwei
しばらく前から作っていた全文検索ライブラリtsubomiを公開しておく。 本ライブラリは接尾辞配列(Suffix Array)というアルゴリズムを使っていて、入力として与えたキーワードを含む行をテキストデータから探して、その行と出現位置を取得できる。さらに圧縮接尾辞配列(Compressed Suffix Array)による圧縮もサポートしているのでインデックスサイズを小さく抑えることができる。 本ライブラリは検索のためのAPIのほかに、インデックス作成、圧縮、検索を行うツールが付属している。ツールを使うだけでも、ある程度のことができる。 以下、簡単に紹介。 tsubomiはGoogleCodeでコードを管理している。詳細は下記URLを参照。 http://code.google.com/p/tsubomi/ コード管理にはsubversionを使っているので $$ svn checkou
行列分解ライブラリredsvdを公開しました - DO++
大規模疎行列向けの行列分解ライブラリredsvdを公開しました． redsvd 大規模疎行列向けの特異値分解や主成分分析，固有値分解を行うライブラリredsvdを公開しました． 修正BSDライセンスで公開しており，コマンドラインから使える他，C++ライブラリが用意されています． 例えば，行と列数がそれぞれ10万，非零の要素が1000万からなる疎行列に対する上位20位までの特異値分解を約2秒で処理します． 特異値分解とか，使っている技術の詳細とか応用事例を以下に簡単に紹介しましたので，興味のある方は参考にしてください． 特異値分解とは まず行列を適当に復習します．行列Xの転置をX^tと表すことにします．またIを単位行列とし，Oを全ての成分が0である零行列とします．また，行列XX^t=IであるようなXを直交行列と呼びます．Xが直交行列の時，Xvはベクトルvを長さを変えずに回転させます．ここでは
定兼 邦彦 (Kunihiko Sadakane) - 圧縮接尾辞配列ライブラリ - researchmap
文字列を圧縮したまま検索するライブラリです． 文字列の一部を高速に復元することもできます． 圧縮接尾辞配列ライブラリ (2010-08-10版) Direct BWT construction External Memory BWT construction http://code.google.com/p/csalib/ にもあります． 注意: dbwt100717.zipにはバグがありました．Ubuntuでは動かない可能性が高いです． dbwt100730.zipを使ってください． 索引とは，本の索引と同じ意味で，検索を高速に行うためのデータのことです． ただし，本の索引では代表的な言葉のみが登録されていますが，このライブラリの索引は 任意の語が検索できるようになっています． このライブラリの索引は自己索引 (self-index) と呼ばれるもので，索引自体に 元のファイルの情報を全
米Google、高速・低メモリ消費の正規表現ライブラリ「RE2」を公開 | OSDN Magazine
米Googleは3月11日、正規表現ライブラリ「RE2」を発表した。動作が高速で「スレッドフレンドリー」な点が特徴。従来のバックトラック型正規表現ライブラリの代替として開発を進めていく。 Googleによると、同社はCode SearchやSawzallといったインフラやアプリケーションで正規表現を利用しているが、バックトラックアルゴリズムを利用した従来の正規表現実装では入力データに対し処理時間が指数的に増加することが問題となっていた。また、固定サイズのスタックを持つC++のマルチスレッドプログラムの場合、従来の正規表現実装ではスタックを使い切ってスタックオーバーフローを発生させることがあったという。これらを解決するために独自の正規表現エンジンを開発したとのこと。 RE2はどのような入力や正規表現に対しても一定の小さいメモリ量で動作するように開発されているのが特徴。オートマトン理論の下、処
Não Aqui! » SimString (類似文字列検索ライブラリ) 1.0 released
SimStringという類似文字列検索ライブラリをBSDライセンスでリリースしました．類似文字列検索とは，文字列集合（データベース）の中から，クエリ文字列と似ているものを見つけ出す処理です．コンピュータは，正確に一致する文字列を探すのは得意ですが，表記揺れに出くわすと，途端に対応できなくなります．例えば，「スパゲティ」に対して，レストラン情報などを返すサービスにおいて，「スパゲッティ」や「スパゲティー」などの表記揺れが検索クエリに与えられると，通常のデータベースでは情報を提示することが出来ません．類似文字列検索を用いると，表記揺れが検索クエリに与えられても，「スパゲティ」という既知語を代替クエリとして提案したり，「スパゲティ」の情報をダイレクトに引き出すことができるようになります． 似てる語を探す技術って，文字列処理の基本中の基本で，自然言語処理では当たり前のように使われていてもおかしくな
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Googleの並列ログ解析向け言語「Sawzall」が公開されたので使ってみた | Preferred Research Blog
Google Code Archive - Long-term storage for Google Code Project Hosting.