トルコ旅行記 No.1 ~エフェス遺跡編~

12月に挙式を行い、その流れで年末までトルコに新婚旅行に行ってきました。冬はトルコ旅行のベストシーズンではないですが、かなり楽しめました。シーズンじゃないという理由で避けている人がいたらもったいないので、いろんな情報を書いておこうと思います…

統計処理の勉強メモ(4)

以下の本を読みました。手を動かしながら学ぶ ビジネスに活かすデータマイニング作者: 尾崎隆出版社/メーカー: 技術評論社発売日: 2014/08/22メディア: 単行本(ソフトカバー)この商品を含むブログ (2件) を見る元がブログであるためか、普段からブログを読…

統計処理の勉強メモ(3)

以下の本を読みました。データの見えざる手: ウエアラブルセンサが明かす人間・組織・社会の法則作者: 矢野和男出版社/メーカー: 草思社発売日: 2014/07/17メディア: 単行本この商品を含むブログ (2件) を見る読み物として非常におもしろいです。ビッグデー…

統計処理の勉強メモ(2)

以下の本を読みました。1億人のための統計解析 エクセルを最強の武器にする作者: 西内啓出版社/メーカー: 日経BP社発売日: 2014/03/20メディア: 単行本この商品を含むブログ (1件) を見るAmazonの評価はとても低いですが、私自身は良いなと思う部分もけっこ…

サーチアプリケーション

Solrは、3.Xの頃に調査したことがあったのですが、4.Xになってからは触れることがほとんどなく、なんか良くなったらしいということだけ聞こえてきていました。また、最近の世の中の事情もあって、構造化データと非構造化データを効率的に扱うことを考えると…

文法圧縮(6)

NLP

仕事上での悩みもあり、なかなかエンジンがかからない状態が続いており、新年からずっとダラダラしている。いまいちモチベーションが上がらないが、ずっとダラダラしていてもしょうがないので、簡単なことからいろいろとやり始めることとした。「遅くともや…

文法圧縮(5)

NLP

文法圧縮(Re-Pair)の構築部分については、線形時間で構築できるようになったが、文法圧縮部分の辞書をどう簡潔に保持するか?という問題が残っている。例えば、 abcabcabbという文字列に対して、Re-Pairを適用して、以下のような辞書(R)と圧縮文字列(C)が得…

Splunkを利用したテキストマイニングもどき

さて、前回の記事で、PerlからLTSV形式のフォーマットを扱う方法を書いた。http://rn.hatenablog.com/entry/2013/12/07/012621そのとき、自然言語処理の分野での適用をぼんやり考えていて、単語とか品詞とか簡単に集計できる仕組みがあると役立つかなと思っ…

Perlメモ(2)

Perlを触りだすと、自分のネイティブプログラミング言語は、Perlだなと実感します。ただ、Perlに限らず、プログラムは好きなので、9時~17時の労働で、プログラムだけ書いて適当に過ごせないものかと思うが、日本では難しいようだ。がんばるしかない。さて、…

Perlメモ(1)

最近、久しぶりにPerlを使ってみたが、UTF-8のデータの扱いで決定版みたいなのがネットではわからなかったので、いろいろと調べたことをメモしておく。PerlでのUTF-8のデータの処理のイメージとしては、Javaとかに近く、内部表現は、Unicodeで管理しているっ…

統計処理の勉強メモ(1)

しばらく統計処理を勉強するつもりなので、ページを立ち上げてみる。そうやって放置されているページがブログ内に散見されるが、あまり気にしない。ただ、文法圧縮だけは、年内に完備辞書のライブラリを完成させて一区切りつける予定である。ページの趣旨と…

文法圧縮(4)

前回、紹介した論文で、かなりざっくりとRe-Pairを実装してみた。An Online Algorithm for Lightweight Grammar-Based Compression. Shirou Maruyama, Algorithms 2012, 2012.バグもいっぱいあると思うし、後処理もさぼってはいるが、それなりに動く。 class…

文法圧縮(3)

NLP

落ち着いて作業できました。さて、前回、文法圧縮のRe-Pairを効率的に実装するのはなかなか難解だと書いたが、非常にシンプルに線形時間で実装できる論文を発見した。An Online Algorithm for Lightweight Grammar-Based Compression. Shirou Maruyama, Algo…

Wavelet TreeのTop-Kの改善

NLP

Wavelet Treeは強力なデータ構造ですが、ひとつどうしても気になる点があります。それは、Top-Kの列挙です。文字列本で紹介されているGreedyな方法は、結果がK件しか必要ないにもかかわらず、計算時間がけっこうかかります。他の操作は、最悪値の計算量が小…

文法圧縮(2)

NLP

休みは長かったけど、家の用事も多かったので、あまり論文を読むことができなかった。ただ、以前から少しずつ調査しているRe-Pairに関する論文を1本だけ読んだ。A fully linear-time approximation algorithm for grammar-based compression Hiroshi Sakamot…

犬島の旅

8/10から夏休みだったので、岡山県の犬島に行ってきました。関西からだと新幹線を使えば、日帰りで行けます。http://www.benesse-artsite.jp/inujima/ベネッセアートサイトの一部なようですね。いろいろ楽しめるものがいっぱいありました。場所は、岡山駅か…

Javaでのテスト

仕事上は、Cやったり、Javaやったりな生活ですが、家での開発は、Javaを使ってます。https://code.google.com/p/sbvj/テストには、主にJUnitとEclEmmaを使っているんですが、ネット上に情報がたくさんあるってわけではないんで、我流で使ってます。ふと、も…

Wavelet Treeをもう一度

NLP

文字列本のメインであるウェーブレット木をもう一度素直に見直すことにした。高速文字列解析の世界――データ圧縮・全文検索・テキストマイニング (確率と情報の科学)作者: 岡野原大輔出版社/メーカー: 岩波書店発売日: 2012/12/27メディア: 単行本購入: 15人 …

高速な文字列マッチング

NLP

最近は、簡潔データ構造を中心に調べたりしていたけど、文字列マッチングを考えた場合、別のアプローチもあります。そう、grepのような逐次文字列検索ですね。以下の解説がおもしろいです。http://www.i.kyushu-u.ac.jp/~takeda/papers/IPSJMagazineCPM.pdfC…

より良いタッキング

「→Pia-no-jaC←」は凄いっすね。やっぱ私の世代はスクエアっすわ。まぁ、今はまったくゲームをしないですが。連休はひたすらヨットをしてました。ただ、風が強かったのでキツかったです。まだまだ技術力が足りないなと認識しました。相変わらず、以下の本を…

高速文字列解析の"別"世界

NLP

1月に「高速文字列解析の世界」を購入してから半年が経ちました。以下、文字列本と呼びます。高速文字列解析の世界――データ圧縮・全文検索・テキストマイニング (確率と情報の科学)作者: 岡野原大輔出版社/メーカー: 岩波書店発売日: 2012/12/27メディア: 単…

省メモリなBWT(2)

NLP

頭文字D 5th Stageを見ていたら、何もせずに土曜日が終わりそうです。絵がだいぶ変わっているが、ノリは変わってないので満足です。さて、本題です。 以下の論文を読んだので、そのことについてちょっとだけ書いておきます。文字列検索における圧縮インデッ…

ムレムレ

最近、暑くなってきましたね。通勤だけで汗だくですわ。まぁ、そんな状況なんで、なんかもう僕の足の方もね。結構、ムレてきたなぁって感じてたんですよ。足だけちょっと他より暑いなぁって。んで、先日、家に帰って、愛犬にモフってしようと思ってね。愛犬…

文法圧縮(1)

NLP

ビットベクトルの完備辞書のさらなる圧縮のために、文法圧縮について調べている。かなり奥が深いようだ。自分のメモとして、調査したことをしばらく書いていく。Re-Pair(is the recursive replacements of all pairs)を応用した完備辞書を実装しようと思った…

Javaで簡潔ビットベクトル(38)

密なビットベクトル、疎なビットベクトル、偏りのあるビットベクトルのそれぞれに対して完備辞書をJavaで作って公開している。https://code.google.com/p/sbvj/今後、改良する点もあるかと思うが、現在の実装でrankとselectの性能を測定した結果を報告してお…

タイフェスティバル

5/18に大阪城公園で開催していたタイフェスティバルに行ってきた。天気も良く、たくさんの人がいました。http://www.thaifestival.net/event/2013/osaka.htmlタイには行ったことがなく、カンボジアに行く時にトランジットでタイの空港を利用しただけでした。…

省メモリなBWT

NLP

CSAやFM-Indexの構築時にボトルネックとなる省メモリなBWTの構築方法について調べた。実際、SAから構築する方法だとInduced Sortingを使うわけだが、最終的なCSAやFM-Indexの結果に比べてメモリを使いすぎる。これはちょっと嫌がられる。今はメモリが安いと…

統計リテラシー

GWの最終日に読み始めた「統計学が最強の学問である」を読み終える。統計学が最強の学問である作者: 西内啓出版社/メーカー: ダイヤモンド社発売日: 2013/01/25メディア: 単行本(ソフトカバー)購入: 11人 クリック: 209回この商品を含むブログ (47件) を見…

姿勢の大切さ

4日間、毎日、セーリングをしたわけですが、今回は、以下の本を事前に軽く読んで、正しいフォームを意識しました。ディンギー・セイリング Standard Book advance―基本フォームからレース戦術まで快速スキルを詳解作者: 佃昭二出版社/メーカー: BABジャパン…

通販は難しい・・・

5/3~5/6まで朝から晩までヨットをやるので、春の海に備えることにした。春の海はとても寒いので、暖かい服を買ってみた。一応、ヨットを始めて3年目なので、そろそろいいものを買ってみようと思ったのもある。いつものNorth Sailsで買うことにしたんだけど…

Javaで簡潔ビットベクトル(37)

簡潔ビットベクトルの圧縮タイプの実装を調べていて、以下の論文を読んだ。Re-Pair(さらっと文字列本に書いてあるよ)という文法圧縮を利用している。実際の実装は、4章にあります。場合によっては、RRRの実装よりも良いようだ。ただし、アクセス性能は良くな…

廃線ウォーキング

桜の名所ということだったので、3/30に旧福知山線の廃線を歩いてきました。 投稿するのにだいぶ時間がたったけどwww一応、JR的には入ってはいけないことになっているらしいので、入る場合は自己責任でお願いします。(ただ、ハイキングコースとしてかなり知ら…

Javaで簡潔ビットベクトル(36)

細かい改善ですが、シリアライズ可能にしました。 これで、簡潔ビットベクトルをファイルに保存することができます。 以下からダウンロードできます。https://code.google.com/p/sbvj/TRIEやウェーブレット木やFM-Indexで使おうと思うとファイルに保存したい…

Javaで簡潔ビットベクトル(35)

簡潔ビットベクトルの最新の論文を読んでみた。Space-Efficient, High-Performance Rank & Select Structures on Uncompressed Bit Sequences Dong Zhou, David G. Andersen, Michael Kaminsky, SEA'13, 2013.http://www.cs.cmu.edu/~dga/papers/zhou-sea201…

Javaで簡潔ビットベクトル(34)

Combined SamplingとRRRを結合してみた。以下にあります。https://code.google.com/p/sbvj/BuildTypeにCS_RRRを指定すると動きます。 t:63 s:63 × 32 = 2016 selectのサンプリング間隔:4096としました。性能は、以下ぐらいです。 CPU : Intel(R) Core(TM) i5…

Javaで簡潔ビットベクトル(33)

先日、RRRの完備辞書をリリースしましたが、ちょっと実装を間違えていたこともあり、性能がちゃんと出ていませんでした。修正したので、再度、アップロードします。https://code.google.com/p/sbvj/ざっくりとrankの性能を測定すると、以下ぐらいです。 Bitm…

Javaで簡潔ビットベクトル(32)

RRRの完備辞書を実装した。https://code.google.com/p/sbvj/境界付近は相変わらず怪しいかもしれないですが、ある程度は動くはずです。文字列本のp.52-54を参考にしつつ、以下の論文の方法で実装しました。Fast, Small, Simple Rank/Select on Bitmaps Gozal…

Javaで簡潔ビットベクトル(31)

疎なビットベクトルに対する完備辞書を利用できる場合について、さらに考えてみた。 メモしておく。こんな感じで、一文字だけUCS-2の範囲を超えた文字が存在すると、上位ビットのビットベクトルはかなり無駄なので、こういう時に疎なビットベクトルに対する…

Javaで簡潔ビットベクトル(30)

疎なビットベクトルに対する完備辞書が利用できるケースについて考えてみた。「複数の文書をまとめたFM-Index(CSAでもいいけど)からの文書IDの復元」で利用できると思う。複数の文書をまとめたFM-Indexから文書IDを復元する時は、以下のような感じになると思…

Javaで簡潔ビットベクトル(29)

疎なビットベクトルに対する完備辞書を作ってみました。以下で公開しています。https://code.google.com/p/sbvj/以下のようにして使えます。 public void test001() throws SuccinctBitVectorException { long sbvSize = 64; SuccinctBitVector sbv = new Su…

ビットシフト

個人的メモ。Javaのビットシフトで、 int i = 1 << 32として、iに0が入ると思っていましたが、1になるみたい。知らんかった。 0を取得したい場合は、 int i = (int) (1L << 32L);longでビットシフトして、intにキャストする。

Javaで簡潔ビットベクトル(28)

疎なビットベクトルのaccessとrankとselectをサポートしようとして、久しぶりに実装しようとしていたら、かなり追加しにくい感じになってたので、ソースをリファクタリングして、メソッドを整理しました。定数時間のselectですが、 0のみの定数時間(1は、log…

開発環境のバージョンアップ

会社でEclipseを久しぶりにダウンロードしようとしたらバージョンが4.2になってた。http://www.eclipse.org/downloads/だいぶ良くなってるみたいなんで、家のEclipse環境もバージョンアップしてみた。学生時代は、Emacsのみでプログミラングしてましたが、最…

FM-Indexで気になるところ

通勤の電車の中で漠然と脳内でN-gram IndexとFM-Indexを比べてて、気になるところをメモとして書いておく。 動的な更新が難しい。まぁ、これは研究が進めば解決されそうな気はするが、現在は難しそう。 基本、オンメモリで動作する。まぁ、N-gram Indexに比…

日帰り温泉

関西の日帰り温泉で定番の有馬温泉に行ってきた。http://www.arima-onsen.com/三宮駅からバスが出てるので、簡単に行ける。今回は、自分で車を運転して行きました。寒すぎたのであまり写真を撮れませんでした。あまり温泉街っぽいのが撮れてなくて残念です。…

FM-Index

BWTとウェーブレット行列を使って、FM-IndexをJavaで実装してみました。BWTのソースコードは以下にあります。ちょっとバグを見つけたので、気が向いたら直します。http://rn.hatenablog.com/entry/2013/02/16/115423ウェーブレット行列のソースコードは以下…

Wavelet Matrix

一部で大ブームのWavelet Matrix(ウェーブレット行列)をJavaで実装してみました。 以下を参考にしました。高速文字列解析の世界――データ圧縮・全文検索・テキストマイニング (確率と情報の科学)作者: 岡野原大輔出版社/メーカー: 岩波書店発売日: 2012/12/27…

BWTとInduced Sorting

BWT(Burrows Wheeler Transform)を行うプログラムをJavaで書いてみた。一応、Unicodeのサロゲートペアの範囲でも問題なく動くので、あらゆる言語に適応できる。BWTは、Suffix Arrayから定義に従って構築している。なので、実質的なメモリ使用量や構築時間は…

ノートPC

学生の時に買ったレッツノート(CF-W7)の保証期間(4年)が切れたので、調子が悪くなってきたら買い替えようと思っている。5年も使ったが、まだまだバリバリ動いているので、今すぐというわけではないが(ただ、バッテリーはだいぶヤバい)。もう自分の用途的にノ…

すごい久しぶりに

USJに行きました。寒かったです。車で行ったんですが、駐車場のスペースが削減されて、立体駐車場になっていました。その代わり、昔、駐車場だったスペースにハリポタランド(仮)が建設されてました。http://www.usj.co.jp/wwohp/release/いや~、めっちゃ期…