サクサク読めて、アプリ限定の機能も多数!
トップへ戻る
TGS2024
echizen-tm.hatenadiary.org
ちょっと興味があったので調べてみた。 全文検索には主に転置インデックス(Inverted Index)によるものと接尾辞配列(Suffix Array)/接尾辞木(Suffix Tree)によるものがある。 前者は効率的にデータを扱えるものの、キーワード単位でしかインデックスを付けられないので形態素解析するなどして検索対象のテキストからキーワードを取り出す必要がある。 後者は任意のクエリにマッチすることができるもののデータサイズが大きくなりがちであることと検索結果となる文書にスコア付けができないなどの問題がある。 最近ではSuffix Array/Treeによる全文検索に対して簡潔データ構造(Succinct Data Structure)を導入してデータサイズを小さくしたり、スコアをもたせる方法が提案されたりと何かと話題が多い。 Suffix Array/Treeが持つ文書検索の機能は、
なにやらDan Kogai氏の以下の記事が話題になっている様子。 404 Blog Not Found:Algorithm - 連想配列の実装としてのハッシュはオワコン? 連想配列(キーワードを投げると対応する値が返ってくるデータ構造)はハッシュテーブルで実装するのではなく、これからはトライ(trie)木を使うのがイケてる!(意訳)という内容だった。 連想配列にハッシュテーブルを使うのが良いか悪いかについては色々と意見があると思うので特にこの記事では触れない。 今回は連想配列として使えると話題のトライ木とはなんぞ、という入門的な記事にしようと思う。 トライ木が持つ機能 最初にトライが持つ以下の3つの機能について説明する。 - lookup - common-prefix-search - predictive-searchまずトライは連想配列として利用できる。つまりキーワードと値のペアを登
ウェーブレット木を習得したので忘れないうちにメモ。 参考: 高速かつ省メモリで文字列を扱うデータ構造「wavelet tree」 まずウェーブレット木の目的は文字列に対してrank()、select()を可能にすること。select()はrank()の逆関数で二分探索によって実装できるので、以下rank()についてのみ考える。 rank(pos, 1)はビットベクトルに対して定義される関数で、先頭のpos個で1のビットの個数を数えるというもの。rank(pos, 0)なら0のビットを数える。例えば ビットベクトル:10110010 rank(1,1) = 1 rank(5,1) = 3 rank(2,1) = 1 rank(6,1) = 3 rank(3,1) = 2 rank(7,1) = 4 rank(4,1) = 3 rank(8,1) = 4となる。で、この操作を文字列に拡張したい
テキストデータの言語的な特徴を知りたい場合、そのデータを使ってNgram統計を取ることがよくある。Ngram統計というのはテキスト中の連続したN文字それぞれが何回出現したかの統計をとること。 といわれてもピンとこない人もいるかも知れない。実例を見るのが早いので当ブログの昨年12月の記事タイトルを使ってNgram統計を取ってみる。 まず記事タイトルを一行一列でテキストファイルに書き出す。 $$ cat blog-title.txt 「PIANO OPERA FINAL FANTASY I/II/III」がとても気になる そっくりヒロインなラノベ「おおコウスケよ、えらべないとはなさけない!」を読みました PSP「探偵オペラ ミルキィホームズ1.5」第5話(最終話)だよ? 簡潔ビットベクトル性能評価実験のソースコード(rx-trie編) 簡潔ビットベクトル性能評価実験のソースコード(ux-tri
ux-trieで使われている簡潔ビットベクトルの評価実験に用いたソースコードをおいておきます。 簡潔ビットベクトル構築用コード(ux_make.cc) #include "rsDic.hpp" #include <iostream> using namespace std; using namespace ux; int main(int argc, char **argv) { try { BitVec bv; if (argc < 1) { cerr << "USAGE: ux_make < infile > bvfile" << endl; } uint64_t n = 0; uint64_t pos = 0; while (cin >> n) { while (pos < n) { pos++; bv.push_back(0); } pos++; bv.push_back(1);
レコメンデーションというのはamazonとかで見かける「XXXを買った人はYYYも買っていますよ」というサービスのこと。最近ではレコメンデーションは珍しいものではなく多くのサービスで導入されている。 またレコメンデーションを実現するレコメンデーションエンジンを開発している企業もわりと多くて検索すると結構たくさん出てくる。 「レコメンデーションエンジン」でぐぐった結果 そんなレコメンデーションエンジンだが作るのはそれほど大変ではない。というか情報検索の基礎知識があれば誰でも作れる。ので作り方の解説をしてみるよ。 レコメンデーションは何を与えると何が返ってくるの? まずはレコメンデーションの入出力の話。入力としては「ユーザ」もしくは「アイテム」というものが考えられる。「ユーザ」というのはレコメンデーションを利用しているユーザのこと。「アイテム」というのはレコメンデーションの対象となるもので例え
DSIRNLP#1に続いて今回の#2も発表の場をいただきました。今回は簡潔データ構造、とくに最も基本的なデータ構造である簡潔ビットベクトルについて発表しました。@overlastさん、@kimurasさん、@rindai87さんをはじめ関係者、参加者の皆様どうもありがとうございました。 twitterでも紹介しましたが発表資料リンクを置いておきます。 発表資料:作ろう!簡潔ビットベクトル 第2回 データ構造と情報検索と言語処理勉強会 #DSIRNLP - [PARTAKE] DSIRNLP#1で発表しました「TRIEにトライ!〜今日からはじめるTRIE入門〜」 - EchizenBlog-Zwei なお質疑では以下のようなものがありました。 ・popcountを使った二分探索をするときのpopcount値はいつ持っておくの? =>直前の64bit毎の線形探索時に使ったものを残しておいて使い
最近私の周辺で簡潔データ構造に興味を持つ人が増えてきた。簡潔データ構造といえばGoogle日本語入力でも使われている話題の新技術。自然言語処理界隈で機械学習の次にブームになるのはこれだ!と個人的に思っている。 というわけで入門用の資料をまとめてみた。 簡潔データ構造では、すべての基礎である簡潔ビットベクトルがあって、その上に応用として簡潔木(LOUDSなど。Google日本語入力で利用されている)、簡潔文字列(ウェーブレット木など。FM-Indexに利用されている)がある。最近ではこれらより複雑なデータ構造に対する簡潔構造も研究されている。 ということをふまえて以下の資料を読むと良い。 Efficient dictionary and language model compression for input method editors Taku Kudo et al. Google日本語
機械学習の3大有名手法といえばSVM、CRF、LDAではないだろうか(と勝手に思っている)。 SVM(Support Vector Machine)については以前記事を書いたので今回はCRF(Conditional Random Fields)について書いてみたい。 機械学習超入門IV 〜SVM(サポートベクターマシン)だって30分で作れちゃう☆〜 - EchizenBlog-Zwei といっても今回はさくっと読んでもらうのを目的にしているので手法の具体的な解説は行わない。具体的な部分は@uchumik氏の資料がとても詳しい。 uchiumi log: 間違ってるかもしれないCRFの説明 また、実装方法については高村本(言語処理のための機械学習入門)がとても詳しい。 さて、具体的な解説をしないなら何をするの?ということだが、今回はそもそもCRFとは何かという話をする。過去の経験上この、そも
@overlastさん経由でオライリー・ジャパンの伊藤様より「入門ソーシャルデータ」を献本して頂きました。どうもありがとうございました。気になっていた本だったのでとても嬉しいです。 というわけで紹介記事を。 まず、本書は翻訳本なので翻訳の質が気になるところ。これについては@overlastさんや@nokunoさん、@mizuno_takaakiさんなど実力のある方が監訳されているので心配ないと思う。 さて。 本書はタイトルの通り、ソーシャルデータを扱って面白い事をしたい人のための本。でもソーシャルデータに限らずwebのデータを使ったサービスを作りたい人は読むとよさそう。 以前、自然言語処理を活用したwebサービスを作るときに参考になる書籍を5冊紹介したのだが、これもそこに加えてもいいかもしれない。 自然言語処理を活用したwebサービスをつくるときに参考になる5冊の書籍 - EchizenB
香川県高松市にて開催された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という感じで
自然言語処理の優秀なエンジニア各位にオススメ本を聞くと大抵FSNLP(Foundations of Statistical Natiral Language Processing)という答えが返ってくる。またブログ等でFSNLPを絶賛している方も多い。 私は自然言語処理は長尾本で満足してしまっていたのでFSNLPは読んでいなかったのだけれど、長尾本は現在入手困難ということもあって入手しやすい自然言語処理の教科書があるといいなと思っていたのでFSNLPを読んでみた。 その結果。自然言語処理の教科書はもう全部FSNLP一冊でいいんじゃないかな。という結論に至ったので全力でFSNLPを推薦する記事を書くことにした。 参考: [を]FSNLP @ytoさん 自然言語処理の定番の教科書まとめ - 生駒日記 @mamorukさん Perl で自然言語処理 @overlastさん ざっと読んでみてFSN
SPIREは文字列処理や情報検索に関する発表が行われる国際会議。今年も10/17から10/21にかけてイタリアでSPIRE2011が開催された。 SPIREで発表された論文については例年Springerからまとめた書籍が発売される。が、無料で済ませられるならそれに越したことはない。というわけでSPIRE2011の論文でweb公開されているものをリストアップしてみた。 SPIRE 2011 | October 17-21, 2011 - Pisa, Tuscany, Italy Tuesday, Oct 18, 2011 Cross-lingual Text Fragment Alignment using Divergence from Randomness (link) Sirvan Yahyaei, Marco Bonzanini and Thomas Roelleke. Spaced
検索エンジンの転置インデックスなどデータ列を小さいデータサイズで持たせたい、という状況がある。こういう場合圧縮符号を使うのが一般的でunary符号やgamma符号、delta符号など様々な種類がある。 圧縮符号の中でイチオシなのがvertical code(vcode)。これは岡野原(@hillbig)氏によって提案された圧縮符号で単純な仕組みでdelta符号並の性能を誇っている。 本記事ではvcodeのポイントを絞って30分でわかるように解説してみる。 vcodeは本棚に本を並べる作業を連想すると理解しやすい。本棚は予め高さが決まっているので全ての本が入るような本棚を用意する。つまり というようなものを想像する。 この本棚は8冊の本が並んでいるが左から5冊目の本が他よりも背が高い。このため5冊目の本に合わせて背の高い本棚が必要になる。だが他の本は5冊目の本ほどに背が高くないので、5冊目が
先日「自然言語処理を活用したwebサービスをつくるときに参考になる5冊の書籍」というタイトルで本を紹介したら評判が良かった。本記事では最初の一冊である「珠玉のプログラミング」のコラム1を読みつつチュートリアル的な記事を書いてみる。 自然言語処理を活用したwebサービスをつくるときに参考になる5冊の書籍 - EchizenBlog-Zwei さて、早速コラム1「真珠貝を開いて」を読み始めると著者が「ディスク上でのソートをしたい」という質問を受けたという話が書いてある。ここで、開発のお仕事をしている人はなんとなく想像が付くと思うのだが実は質問者は「ディスク上でのソートをしたい」わけではない。 フレンドリーな会話に潜むトラップ!? 「1.1 フレンドリーな会話」を読むと書いてあるように質問者は「メモリがほとんど使えない状況で重複のない数値データをソート」したかったのだ。そして質問者は思考の末「デ
自然言語処理を活用したwebサービス開発に関わって5年以上経った。いい機会なのでこれまでを振り返って役に立ったと思う5冊をメモしておく。 1.珠玉のプログラミング―本質を見抜いたアルゴリズムとデータ構造 まずはこれ。有名な本なので知っている人も多いと思う。簡単に説明するとちょっと前に「フェルミ推定」という名前で流行ったような、データから必要な数値を概算する方法や、問題が起きたときに問題点がどこにあるのか?最小の労力で解決するにはどこをいじればよいのか?などが書いてある。「webサービスで自然言語処理だ!」というと無限に夢が広がりがちなので、どういうデータが使えるのか、それをどういう形にもっていけばイケてるサービスになるのか、それはどのくらいの期間で実現できるか、ということを考える必要がある。そういうわけで本書は真っ先に読むべき一冊なのでは(余談だけれど、以前M << Nなデータに対してO(
自然言語処理は大学時代からやっていたのだが、恥ずかしながらテキストマイニングについてはよくわかっていなかった。@shima__shima先生から「テキストマイニングを使う技術/作る技術」を紹介していただいたので読んでみた(紹介していただき、ありがとうございました)。 本書によるとテキストマイニングは厳密な定義はないものの、テキストデータから抽出されたデータを用いたデータマイニングを指すらしい。 で、従来のデータマイニングであれば数値データからそのままマイニングすればいいけれどテキストデータは自然言語で書かれていてそのままでは使えないので自然言語処理(NLP)を用いてマイニングで使うデータを抽出するよ。ということらしい。なんとなくNLPの中にテキストマイニングがあるのかと思っていたのだが、テキストデータとデータマイニングの橋渡しをする技術としてNLPを使っている、というのが正しいのかも。 本
機械学習(というかカーネル)の論文を読んでいると突然ヒルベルト空間とかでてきて混乱する。 そんなの知らんわ!と言ってWikipediaを調べると距離空間とかバナッハ空間とかいろいろ出てきてさらに分けがわからなくなる。 で。結局、位相空間というのがそれらの最も基本的なやつだということがわかるのだが、肝心の位相空間がなんなのかわからない。位相構造の入っている空間とか説明があるが、そもそも位相構造とかよくわからなくて調べていると開集合がなんちゃらかんちゃらでもういいやという気分になる。 そういうわけで位相空間には苦手意識があったのだが、本書をざっと見てみたら一気に見通しが良くなった。これはいけてる本だと思ったのでメモ。 本書は最初の章でユークリッド幾何と位相幾何の違いを解説してくれていて、位相的な性質というのがあることで高校数学で習う「最大値・最小値の定理」「中間値の定理」が成り立っているという
簡潔データ構造のサーベイ論文を探していたら良さそうなのを見つけたのでメモ。 Data Structures for Efficient String Algorithms Johannes Fischer; 2007 文字列検索に関する論文で、RMQs(Range Minimum Queries, 範囲内の最小要素を探す)や簡潔データ構造を用いて効率的なSuffix Arrayを実装するよ、という話みたい(RMQsがメインで簡潔データ構造については利用するほうがメインで実装についてはあまり書いてない様子)。 それぞれの技術についてどの論文を当たればよいかがきちんと書いてあるのでサーベイ論文としても価値がある気がする。 RMQsはSuffix Arrayを高速に検索する際の予備データ構造であるLCP Arrayに利用されている。アリ本にも出てきていて気になっていた技術なのでこれを機にしっかり勉強
LOUDSは木構造を非常に小さなデータサイズで表現することができる簡潔データ構造の一種。とくに自然言語処理ではトライ木という木構造が重要で形態素解析や日本語入力(IME)など多くの場面で利用されている。 トライ木としてはdouble arrayが有名。LOUDSはdouble arrayより速度で劣る反面、データサイズを非常に小さく抑えることが可能である。このため近年、大規模データを扱うためのデータ構造として注目されている。 LOUDSを用いたトライ木には優れた実装がいくつかある。なかでも有名なものとして@s5yata氏によるmarisa-trieと@hillbig氏によるux-trieがある(ux-trieのクローンであるrx-trieはGoogleIMEで利用されている)。 今回はこれらのライブラリと、参考までに私の作ったerika-trieを使ってみて簡単に性能比較をしてみた。 評価
今回は集合の簡潔構造について話をする。今回で簡潔構造の初歩的な話は一段落となるので、いままでの話をまとめつつ集合の簡潔構造とは?どういうことに使えるのか?という話をする。 集合の簡潔構造は大変重要で、ここを理解すれば簡潔構造の基礎はだいたいOKといえる。 前回までの記事: 簡潔データ構造超入門 〜つくって学ぶ簡潔ビットベクトル〜 - EchizenBlog-Zwei 簡潔データ構造超入門II 〜ちょっとだけ実用的な簡潔ビットベクトル〜 - EchizenBlog-Zwei 簡潔データ構造超入門III 〜簡潔ビットベクトルで転置インデックスを効率的に実装する〜 - EchizenBlog-Zwei 簡潔データ構造超入門IV 〜LOUDSというメモリ効率のよい木構造の話(準備編)〜 - EchizenBlog-Zwei 簡潔データ構造超入門V 〜LOUDSというメモリ効率のよい木構造の話(本編
先日まで勉強のためにerika-trieというLOUDSを用いたトライ木を作っていた。ある程度考えがまとまったので実用版を作り始めた。 erika-trie(実用版)はmarisa-trieやtx/ux/rx等と同等の操作を備えたトライ木。またerika-trieを用いてテキストからキーワードを高速に抽出するためのツールerika_extractが付属している。 DSIRNLP#1で発表しました「TRIEにトライ!〜今日からはじめるTRIE入門〜」 - EchizenBlog-Zwei 海風に揺れる一輪のTRIEライブラリ erikaを作ってみたよ - EchizenBlog-Zwei erika-trie: succinct trie library - Google Project Hosting はじめに。なんとなくツールをerika-trieにしたのだが、意味のない名前というのもア
前回に引き続きLOUDSという簡潔木の話。前回準備したunaryの簡潔ビットベクトルを使って親ノード、子ノードへのアクセスが効率的に可能な木構造であるLOUDSの話をする。 前回までの記事: 簡潔データ構造超入門 〜つくって学ぶ簡潔ビットベクトル〜 - EchizenBlog-Zwei 簡潔データ構造超入門II 〜ちょっとだけ実用的な簡潔ビットベクトル〜 - EchizenBlog-Zwei 簡潔データ構造超入門III 〜簡潔ビットベクトルで転置インデックスを効率的に実装する〜 - EchizenBlog-Zwei 簡潔データ構造超入門IV 〜LOUDSというメモリ効率のよい木構造の話(準備編)〜 - EchizenBlog-Zwei さて、LOUDS(Level Order Unary Degree Sequence、ラウズ)は木構造を表すデータ構造のひとつ。データサイズを小さく抑えつつ
同じ分野の論文ばかり読んでいると視野が狭くなるので専門外の分野の論文も積極的に読んでいきたい。とはいえ未知の分野だとどの論文から読めばいいのかわからず困ることも。そんなときにこれまで試して役に立ったことをメモしてみた。 1.調べる論文は英語に絞る これは日本人の論文が良くないということではなく日本人の論文も含め優れた論文は国際会議(つまり英語)でも発表されているから。英語が苦手でも頑張って英語論文を読んだほうが質のよい論文に出会う確率が高い。 2.関連ありそうな単語を検索して意味を調べる まずはひたすら検索タイム。最初は漠然とした言葉でしか検索できなくても調べたい分野の用語は頻出するはずなので、だんだん知るべき用語がわかってくる。英語の単語がわからない場合も調べていれば日本語/英語を併記してくれているものがでてくるはず。あとは頻出語の意味を分かる範囲でざっと調べておく。余談だけれど技術系の
今回はLOUDS(Level Order Unary Degree Sequence, ラウズ)というデータ構造の話。LOUDSは木構造の簡潔データ構造版、簡潔木と呼ばれているものの一種。 簡潔木には他にBP(Balanced Parentheses)やDFUDS(Depth First Unary Degree Sequence)というものがある。BPやDFUDSは部分木の大きさを効率的に計算できるという利点がある。実際は各ノードから親ノード、子ノードへのアクセスが効率的に出来れば十分な場合も多いので、そういう場合はLOUDSが活躍する。 今回はそんなLOUDSのお話の準備編。LOUDSに必要なデータ構造を用意するところまで。 前回までの記事: 簡潔データ構造超入門 〜つくって学ぶ簡潔ビットベクトル〜 - EchizenBlog-Zwei 簡潔データ構造超入門II 〜ちょっとだけ実用的な
前回までで簡潔ビットベクトルというデータ構造を実装した。簡潔ビットベクトルとは普通のビット列に少しの追加データを持たせることでrank/selectという2つの操作が可能にしたもの。そしてrank/selectとはそれぞれ以下の操作のこと。 rank(x) : x番目のビット以前(xの位置を含む)の立っているビットの数 select(i): i番目に立っているビットの位置今回は簡潔ビットベクトルを利用して転置インデックスを効率的に実装してみる。 前回までの記事: 簡潔データ構造超入門 〜つくって学ぶ簡潔ビットベクトル〜 - EchizenBlog-Zwei 簡潔データ構造超入門II 〜ちょっとだけ実用的な簡潔ビットベクトル〜 - EchizenBlog-Zwei 転置インデックスとは検索エンジンに用いられるインデックスで apple 1, 3 orange 1, 2, 4, 6のように各単
@tkngさんが日本語入力の記事を書いたということで注目していたWEB+DB PRESS vol.64をげっとしましたよ。 WEB+DB PRESS vol.64に日本語入力の記事を書いたよ - 射撃しつつ前転 この特集記事は3つの章から構成されている。 第1章 日本語入力システム入門 第2章 かな漢字変換器の実装 第3章 変換速度と変換精度の向上第1章は普通の読み物なので安心して読める。日本語入力の基礎がばっちりわかるすばらしい内容。第2章はStructured Perceptron(+ Viterbiアルゴリズム)でかな漢字変換の実装例を具体的に紹介している。そして第3章では辞書引きにトライ(Double Array)を用いて速度を向上させ、Structured PerceptronをStructured SVMにすることで精度を向上させる話が書いてある。 日本語入力に限らずこの特集で
簡潔データ構造(Succinct Data Structure)の魅力を紹介する本シリーズ。前回の記事では疎ベクトルを簡潔データ構造を使って効率的に実装する方法を紹介した。 前回の実装ではビットベクトルのサイズの上限が256だった。今回はこれを拡張して任意の大きさを扱える簡潔ビットベクトルの実装例を紹介する。 また前回はrank()を定数時間で実現する方法を紹介した。今回はこれを使ってselect()を二分探索(O(logN))で実装する。 以上の2つの改善によってビットベクトルのサイズに制限がなくrank()/select()の双方を備えた、実用性のある簡潔ビットベクトルが実現できる。 前回の記事: 簡潔データ構造超入門 〜つくって学ぶ簡潔ビットベクトル〜 - EchizenBlog-Zwei サイズに制限のないビットベクトルは前回実装した簡潔ビットベクトルのsbvクラスを用いて実装する
簡潔データ構造は各種操作を高速に保ったままでデータサイズを情報理論的な下限近くまで圧縮できる。大規模データを扱うことの多くなってきた現在、特に注目を集めている技術である(※個人的な見解です)。 しかし有用性とは裏腹にまとまった教科書等がないこともあり入門者に対して敷居が高いようにも感じられる。そこで本記事では簡潔データ構造の基本であるビットベクトルに対する簡潔構造の実装方法をC/C++のコードを交えて解説してみる。 ビットベクトルに対する簡潔構造は、単純には疎ベクトルを表現するのに利用することができる。よって本記事でも簡潔ビットベクトルを実装し、疎ベクトルを実現してみようと思う。 今回は疎ベクトルとして値がint(4byte)の256次元のベクトルを考える。ただし疎ベクトルなので256次元のうちいくつかの次元にしか値が入っていないものを仮定する。例えば v[5] = 10 v[100] =
次のページ
このページを最初にブックマークしてみませんか?
『EchizenBlog-Zwei』の新着エントリーを見る
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く