情報系修士にもわかるダブル配列 - アスペ日記
最近話題の「日本語入力を支える技術」を途中まで読んだ。 3章がものすごく気合いが入っている。 trie（トライ）というデータ構造の2つの実装、「ダブル配列」と「LOUDS」について詳しく説明がされている。 ダブル配列については、ぼくは以前論文を読んで勉強しようとしたのだが、その時は難しくてあきらめた覚えがある。しかし、この本の説明を読むことで理解ができた。 ありがたい。 感銘を受けたので、この本を教材に友達と2人勉強会をした。 この2人勉強会というのは、ぼくが復習を兼ねて友達に教えるというのがだいたいのスタイル。 しかし、いざやってみるといろいろと難しい。 次のようなところでひっかかるようだ。 例のサイズが小さく、イメージを喚起するのが難しい。 最初の図のノード番号と、最終的なダブル配列上の位置が異なるため、混乱する。 単語終端について言及がないので、どのノードが単語を表しているかがわから
第2回DSIRNLP勉強会に参加しました #dsirnlp - nokunoの日記
第2回 データ構造と情報検索と言語処理勉強会 #DSIRNLP - [PARTAKE] 自然言語処理はじめました by @phylloさん自然言語処理はじめました - Ngramを数え上げまくるDSIRNLPで発表させていただきました - Negative/Positive Thinking 自己紹介：Negative/Positive Thinking 今日の概要：いろんな方法でN-gram頻度を数える N-gramとは？ 隣り合うN個の塊のこと 単語n-gramや文字n-gramがある ナイーブな方法 ハッシュに入れて数える 問題：大規模テキストやNを大きくしたら？ N-gramの異なり数はNに対して指数的に爆発する 解決法：N-gramをメモリに保存しない！ Suffix Arrayを使った方法 入力文のSuffix Arrayを使った方法 メモリの節約になってる？：3*N+4byt
ALSIP 2011
Invited Talk Space-efficient representations of complex objects Rajeev Raman (University of Leicester, UK) In the last 10-15 years there has been a great increase in our understanding of space-efficient representations of ``simple'' objects such as trees and strings (or simple graph classes) but with increasingly more powerful operations, the objects we often wish to represent in real life are mor
話題の新技術、簡潔データ構造の入門用資料をまとめてみた - EchizenBlog-Zwei
最近私の周辺で簡潔データ構造に興味を持つ人が増えてきた。簡潔データ構造といえばGoogle日本語入力でも使われている話題の新技術。自然言語処理界隈で機械学習の次にブームになるのはこれだ！と個人的に思っている。 というわけで入門用の資料をまとめてみた。 簡潔データ構造では、すべての基礎である簡潔ビットベクトルがあって、その上に応用として簡潔木(LOUDSなど。Google日本語入力で利用されている)、簡潔文字列(ウェーブレット木など。FM-Indexに利用されている)がある。最近ではこれらより複雑なデータ構造に対する簡潔構造も研究されている。 ということをふまえて以下の資料を読むと良い。 Efficient dictionary and language model compression for input method editors Taku Kudo et al. Google日本語
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という感じで
LOUDSトライのライブラリの性能を比較してみた - EchizenBlog-Zwei
LOUDSは木構造を非常に小さなデータサイズで表現することができる簡潔データ構造の一種。とくに自然言語処理ではトライ木という木構造が重要で形態素解析や日本語入力(IME)など多くの場面で利用されている。 トライ木としてはdouble arrayが有名。LOUDSはdouble arrayより速度で劣る反面、データサイズを非常に小さく抑えることが可能である。このため近年、大規模データを扱うためのデータ構造として注目されている。 LOUDSを用いたトライ木には優れた実装がいくつかある。なかでも有名なものとして@s5yata氏によるmarisa-trieと@hillbig氏によるux-trieがある(ux-trieのクローンであるrx-trieはGoogleIMEで利用されている)。 今回はこれらのライブラリと、参考までに私の作ったerika-trieを使ってみて簡単に性能比較をしてみた。 評価
私のブックマーク ： 簡潔データ構造
田部井靖生（科学技術振興機構 ERATO湊離散構造処理系プロジェクト研究員) はじめに 近年、Web技術や計測技術の発展により言語やゲノムデータは大規模化しています。従来のデータ構造は大規模データを扱うにはサイズが大きくメモリに載らない、 しかし、圧縮するとランダムアクセスをすることができないという欠点があります。 簡潔データ構造とはデータを小さく保存かつ高速な操作が可能なデータ構造です。 近年、集合、文字列、木、グラフデータを扱うための簡潔データ構造が提案され注目を集めています。 私たちの身近なアプリケーションとして、Google日本語入力では簡潔木LOUDSの実装が使われ、実際に使われはじめています。 また、有志によるそれらを解説したサイトやライブラリなども利用可能になりつつあります。 そこで、このページでは簡潔データ構造を用いた研究開発のためのいろいろなリソースを紹介します。 解説記
人工知能学会誌 私のブックマークに簡潔データ構造という題で記事を書きました - Yasuo Tabeiの日記
人工知能学会誌の私のブックマークに簡潔データ構造という題で記事を書きました。私のブックマークは研究者が自らの研究をする中で普段使っているWeb上のリソースを公開するための記事です。今までいろいろな研究者が記事を書かれています。 http://www.ai-gakkai.or.jp/jsai/journal/mybookmark/ 幸いにも今回は、私が執筆の機会を頂くことができたので情報検索などでよく使われている簡潔データ構造のリソースについてまとめてみました。 http://www.ai-gakkai.or.jp/jsai/journal/mybookmark/26-6.html 記事を書いてみて思ったことは、ライブラリの充実により実際の場面で使いやすくなっていることと、多くのエンジニアや研究者がブログなどをつうじて記事を公開してくださっているおかげでこの分野が日本語で勉強しやすくなってい
簡潔データ構造超入門VI 〜これまでのまとめと集合の簡潔構造〜 - EchizenBlog-Zwei
今回は集合の簡潔構造について話をする。今回で簡潔構造の初歩的な話は一段落となるので、いままでの話をまとめつつ集合の簡潔構造とは？どういうことに使えるのか？という話をする。 集合の簡潔構造は大変重要で、ここを理解すれば簡潔構造の基礎はだいたいOKといえる。 前回までの記事： 簡潔データ構造超入門 〜つくって学ぶ簡潔ビットベクトル〜 - EchizenBlog-Zwei 簡潔データ構造超入門II 〜ちょっとだけ実用的な簡潔ビットベクトル〜 - EchizenBlog-Zwei 簡潔データ構造超入門III 〜簡潔ビットベクトルで転置インデックスを効率的に実装する〜 - EchizenBlog-Zwei 簡潔データ構造超入門IV 〜LOUDSというメモリ効率のよい木構造の話(準備編)〜 - EchizenBlog-Zwei 簡潔データ構造超入門V 〜LOUDSというメモリ効率のよい木構造の話(本編
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
定兼 邦彦 (Kunihiko Sadakane) - 簡潔データ構造講義資料 - researchmap