2013年6月30日日曜日

「高速文字列解析の世界」を読むのに参考にした資料


　現時点では、ビッグデータではなく、サンプリングされたデータを扱っているのですが、「大規模」データであることには違いなく、それらを如何に高速に処理するかに頭を悩ませています。

　この本は、その悩みを解決する助けになりました。
　実際には、いくらかの前提知識が必要ですし、対象とする問題や開発環境も考慮しなければなりませんでした。

　部分的な調整しかできていませんが、それでも、当初は致命的とも思われた実行速度を、何とか現実的な速度まで持てくることができました。


　以下に、この本を読む際に参考にしたページ、各種実装関連のページなどへのリンクを（備忘録も兼ねて）記しておきます。
　なお、「参考にした」ページですので、必ずしも本書にて解説されている項目とは限りません。

　※実装コードの項目に記載したライセンスは調査時のものですし、未確認・未記載のものもあります。利用に際しては、それぞれ確認が必要です。


■全般

『大規模文字列解析の理論と実際』(pdf)　［岡野原大輔］
2010/06/14　情報論的学習理論と機械学習研究会 (IBISML) @東京大学

■ウェーブレット行列



■FM-INDEX

FM-index++を公開しました　［tb_yasuの日記］
2010-12-30

fmindex-plus-plus
旧バージョン
新バージョン
C++による実装
最終更新：2013/04/03

FM-Index　［気ままなブログ］
Javaによる実装
2013-02-24

■SA-IS（Suffix Array - Induced Sorting）




SAIS
C/C++、Java、C# による実装
MIT/X11 license.
最終更新：2010/09/17

Suffix Array を作る - SA-IS の実装　［ビームの報告書］
C++による実装
MIT LICENSE
最終更新：2011/08/19


■SuffixArray：Multikey Quicksort
接尾辞配列 (suffix array)　［Algorithms with Python］
Larsson Sadakane 法 / マルチキークイックソート
Pythonによる実装＆解説
最終更新：2007

Suffix Array (Larsson-Sadakane)　［Spaghetti Source］
Suffix Array を O(n (log n)^2) 時間で構成するアルゴリズム
multikey quicksort ではなく，ただの quicksort を用いている
C++による実装
最終更新：2007/12/11

String Sort Library
Multikey Quicksort
C/C++による実装
利用や再配布などに関する制限はありません．
最終更新：2007/12/20

Bloggerからトラックバックが飛ばせないということを今回知りました。
リンク先の皆様、ご容赦ください。
時刻:
ラベル: , ,

2013年6月25日火曜日

Twitter分析：2013年コンフェデ杯での選手別Tweet計測

2013年コンフェデ杯での出場選手別のTweet数を計測しました。
例によってTwitterStreamingAPIでの1%Tweetを用いています。
検索条件は、検索文字列は名字のみ、期間はキックオフの1.5時間前から5時間分です。


■予選3試合での出場選手ごとTweet合計
　予選3試合のTweet数を合計して順位付けしました。
　上位3名（本田、香川、岡崎）が飛び抜けています。
　以下、3試合前出場した選手が横並びで、１～2試合出場の選手が続きます。


■2013年6月16日(日) 対ブラジル戦（4:00キックオフ）　2:30-7:30
　3:00に全体的なピークがあります。おそらくスタメン発表がらみだと思われます。

■2013年6月20日(木) 対イタリア戦（7:00キックオフ）　 5:30-10:30
　この試合だけ時間帯が違います。
　平日にも関わらず昼間の時間だったため、Tweet数の目盛りが6倍程度になっています。

■2013年6月23日(日) 対メキシコ戦（4:00キックオフ）　2:30-7:30
　深夜帯の試合に加えて、既に予選敗退が決まっていたこともあり、結果のみを確認した人が多かったようです。

第1試合と第3試合は時間が深夜帯だったため、全体のTweet数が少ないので、全数調査との乖離があるかもしれません。
第2試合は、妥当な結果が出ていると思います。


時刻:
ラベル: , ,

2013年6月22日土曜日

ビッグデータとサンプリングデータ：『ワールドカップアジア最終予選 日本×オーストラリア』での比較調査

　「ビッグデータ」という言葉は世間に定着してきていると言っていいでしょう。バズワードと呼ぶかどうかはここでは言及しませんし、重要ではありません。
　その一方、統計との関係性から、「ビッグデータありき」という姿勢に疑問を呈している記事もあります。

そこで、自然言語処理（というか文字列検索）での「全数データ」と「サンプリングデータ」の結果を比較して、どのような違いが出てくるかを調査してみました。

対象データとして次を見つけたので、これを全数データと見なします。
（最新の試合でないのが残念ですがご容赦ください）
サンプリングデータは過去と同様にTwitterAPIのストリーミングデータ（全Tweetの1%）を使います。
集計期間および検索条件は、元記事に記載されているものを原則そのまま使用します。（#fjaという記載がありますが、これは#jfaのタイポと思われるので、これだけは「#jfa」を使用）
細部については元記事を参照して下さい。

結果を以下に掲載します


１．出場した全14選手の名字検索でのランキング
　ほとんど同じですが、本調査では5位の長友と8位の内田がより上位になる結果となりました。
　（下記表は元記事の順位のままに、投稿件数のみを本調査のものを記載しました）


２．本田選手、香川選手、川島選手の投稿数推移
　元記事同様、本田選手のみ右側の目盛りを参照してください。
　本調査では18時～19時台で多めの数値が出ていますが、それ以降は同じ傾向が確認できます。


３．オーストラリア戦での投稿数の推移
　同じ傾向が見られます。

４．松木氏、ゴン中山氏、セルジオ越後氏の投稿数グラフ
　同じ傾向が見られます。（ゴン中山が多めに取られてる？）

５．松木氏の投稿数推移グラフ
　全体の傾向（ピーク位置）が同じことが確認できます。


６．「渋谷」「道頓堀」の投稿数推移
　渋谷のピーク位置がずれましたが、全体の傾向はほぼとれています。


元記事で示したかった情報とほとんど同様の結果がサンプリングデータでも示すことができたと思いますがいかがでしょうか。

「定性的な傾向はサンプリングデータ（今回は1%）でもほぼ取得できる。ただし、精度的には劣る場合がある」と言うことを認識した上で使用するのであれば、十分役に立つのではないでしょうか。


（2013/6/26）タイトルを変更しました

時刻:
ラベル: , ,

2013年6月18日火曜日

クラウドソーシング（クローズアップ現代）を見て

番組サイト：クローズアップ現代「企業も働き方も激変～クラウドソーシング」

自然言語処理の様な仕事にクラウドソーシングを適用をできるか考えながら見ていました。
番組中で紹介されていたのは、予想していた通り、企画やデザインなどでした。また、おそらくは仕様の確定したプログラミングの下請けなどの仕事もあるかもしれません。

現実のプログラミングの現場では、
　　「限られた条件の中で如何にして要求仕様を実現するか」
という問題が大きく、これを解決するために利用できる可能性もあります。

しかし、自然言語処理の製品を作る場合には、それに加えて、より深刻な問題として
　　「実現方法が分からない」
あるいは
　　「実現可能であるかどうか分からない」
　　「解決不能な問題かもしれない」
というような局面に遭遇することがあります。単純な時間やマンパワーの投入では解決しません。

これらに対応可能な人材が、クラウドソーシングに登録する状況は考えにくいですし、もしいたとしても直面している問題に対応できる人材かどうかを判断することができないような気がします。

でも、クラウドソーシング自体が広く普及し、普通の働き方になっていく未来も考えられないわけではありません。その場合にはまた違った判断になるでしょう。

日本で今後どのようにクラウドソーシングが広まっていくか、興味深く見守っていきたいと思います。


P.S.
上記の問題の対策は、簡単に言えば、近似値に落とし込む、別手法を試してみるなどしますが、個別の製品ごとにアプローチは異なるので、様々な知識・経験が必要です。さらにその対策すらも同じ問題に陥る場合があります。そして、繰り返しながら、現実的な解決策を探っていきます。


時刻:
ラベル:

2013年6月17日月曜日

ブログ再開します

本業との兼ね合いがあり、大人の事情でブログの更新を停止していました。（ブログを続けて食えなくなったら本末転倒なので）

状況が落ち着いてきたこともあり、大人の事情に抵触しない範囲でブログの更新を再開したいと思います。

今週は準備期間として、来週くらいから本格的に再開する予定です。

なお、ブログ更新を停止していた2年間について言えば、とりあえず、自然言語処理で食っていけていました。

時刻:
ラベル:
登録: 投稿 (Atom)