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