www.youtube.com 去年のはじめに高速文字列本を買ったのですが、アルゴリズムを眺めるだけで実装はしていませんでした。特にウェーブレット行列は実装が大変そうにしか見えなくて敬遠していたのですが、ICPCの夏合宿で @hirokazu1020 さんに「あれはアイデアさえ理解していれば実装するのは簡単だよ」という旨のことを言われたので、学校のプログラミングの演習の自由課題としてウェーブレット行列とFM-indexを実装してみました。 制作物はブラウザ上で動く青空文庫のインクリメンタル検索です。C++で書いたFM-indexをboost-pythonを使ってPythonから呼び出せるようにし、Flaskを使ってブラウザからのリクエストに応答するような仕組みにしてみました。アルゴリズムの本質的なところは全て自分で書こう！というモチベーションで始めたのですが、SA-ISが難しくてsais.
antipop.fm - Index
第10話 Webサイトを作ること 2017年は、日本におけるTwitterブームの開始からちょうど10年。短いテキストを思いついたその場で投稿できる便利さもいいけど、そろそろまとまりのあるコンテンツを提供するWebサイトがくるね、というお話。 第9話 採用目的 新卒採用シーズンということで、採用についてのメッセージをラップにしたためました。 第8話 べつの言葉で 明けましておめでとうございます。新年ということで「外国語の勉強をするぞ！」という抱負を述べたので、それに関連して、複数言語を使用するということについて話しました。 第7話 あんちぽ忘年会 年の瀬も迫ってきた昨今ですが、毎年恒例のあんちぽ忘年会を行いました。本日はその模様を実況中継しています。 第6話 阿部薫の時代 日本における伝説的なフリージャズミュージシャンの阿部薫とその時代について、あんちぽくん自身の受容体験を交えながらお話し
wat-arrayでラクラク実装☆FM-Indexの作り方 - EchizenBlog-Zwei
というわけで大変便利なライブラリwat-arrayを使ってFM-Indexを簡単に実装してみるよ。本格的なライブラリは既にFM-Index++という良いものがあるので、本記事では仕組みの解説を目的とする。 参考資料: FM-index++を公開しました - tb_yasuの日記 An alphabet-friendly FM-index (P. Ferragina, G. Manzini, V. Makinen, G. Navarro, 2004) なお、本記事では前回の記事で実装した(ってほどでもないけど)text2bwt()とLF()を使っている。 話題のwat-arrayを使ってBurrows-Wheeler変換(BWT)してみた - EchizenBlog-Zwei 今回もテキストとしてmississippi#を使う。まずテキストから任意のキーの出現回数を得る関数get_rows(
FM-indexのC++による実装 FM-index++を公開しました。 http://code.google.com/p/fmindex-plus-plus/ FM-index[1〜4]とは、圧縮全文索引の一種でO(n)時間とO(nlgσ)メモリー(n:テキスト長、σ:文字種類数)で構築することができます。最近では、テキスト処理ばかりでなくゲノム検索[5]など、いろいろなところで応用されています。今回は、クエリーに対する検索操作の内、exact検索、ハミング距離による検索、編集距離による検索の３つを実装しました。それぞれの計算時間は、qがクエリーの長さとすると、exact検索がO(q)時間、 ハミング距離による検索がO(q^σ)時間、編集距離による検索がO((q \times q)^σ)時間です。よって、４文字種のDNAや２０文字種のタンパク質など、文字種類数が少ない対象にはハミング距離
FM-Index - 気ままなブログ
BWTとウェーブレット行列を使って、FM-IndexをJavaで実装してみました。 BWTのソースコードは以下にあります。ちょっとバグを見つけたので、気が向いたら直します。 http://rn.hatenablog.com/entry/2013/02/16/115423 ウェーブレット行列のソースコードは以下にあります。 http://rn.hatenablog.com/entry/2013/02/23/222314 FM-Indexは、圧縮全文索引であり、テキストを圧縮して保持しながら、全文検索を実現することができます。Compressed Suffix Array(CSA)よりも高速と言われているデータ構造です。FM-Indexは、ざっくり以下のようなことができます。 元のテキストを完全に復元することができる(self index) 任意のキーワードが出現する位置と数をキーワードの文字
簡潔データ構造を使った全文検索アルゴリズム、FM-Indexのライブラリを作りました - EchizenBlog-Zwei
先日公開したウェーブレット木のライブラリshellinfordにFM-Indexの機能を追加した。 まだ基本的な機能しか実装していないけれど、とりいそぎ公開しておく。おいおい機能は追加していく予定。 shellinford - shellinford: succinct document retrieval library - Google Project Hosting An alphabet-friendly FM-index P. Ferragina, G. Manzini, V. Makinen, G. Navarro, 2004 ちなみにウェーブレット木はちょっと高速化したので一つ前の記事のパフォーマンス測定結果が改善されて rank_wavelet_tree: 14.71s select_wavelet_tree: 460.34sとなった。これについては機会があったら記事を書く
Shibu's Diary: [JSX][FM-index]httpstatus コマンドで、HTTP のステータスコードをすばやくしらべる!
渋日記@shibu.jp 渋川よしきの日記です。ソフトウェア開発とか、ライフハックを中心に記事を書いていきます。 一般的な Web Programmer ならば、HTTP Status code はすべて暗記していると聞きました。 しかし、僕は初心者なので、なかなか覚えきれていないので、HTTPのステータスコードをさがすのに便利なツールを用意しました。httpstatusです。インストールはJSX(npm install jsx)とgitが使える環境で: $ git clone https://github.com/shibukawa/oktavia $ cd oktavia $ make です。使い方はコマンドの後ろに検索ワードを書けばいいのですが、Googleの検索と同じようなクエリーも少しだけサポートしています。本当はダブルクオーテーションでくくるとそのフレーズを完全に含む検索もいれ
FM-index - Wikipedia
In computer science, an FM-index is a compressed full-text substring index based on the Burrows–Wheeler transform, with some similarities to the suffix array. It was created by Paolo Ferragina and Giovanni Manzini,[1] who describe it as an opportunistic data structure as it allows compression of the input text while still permitting fast substring queries. The name stands for Full-text index in Mi
FM-indexによる全文検索
docstringとは、コード内に書くドキュメントです。 docstringを書いておくことによってクラスや関数の役割を伝えることができます。 初心者の方や、分析でPythonを使ってる方たちにはあまり馴染みがないかもしれません。 メンテナンスしやすいコードを書くための1つの術として、 今回はdocstringについて - どんなことを書くべきなのか - どんな書き方があるのか - どんな情報を埋め込めるのか ということをお話したいと思います。
ウェーブレット行列(Wavelet Matrix)を用いたFM-Indexを実装しました - EchizenBlog-Zwei
話題のウェーブレット行列(Wavelet Matrix)を自作のFM-Indexライブラリ、shellinfordに組み込んでみた。 ウェーブレット行列はウェーブレット木と互換性があるので、ウェーブレット木の代表的な適用例であるFM-Indexでも当然利用可能。 というわけでとりいそぎソースを公開しておく。構築部分がやっつけで書いたので構築時にやたらメモリ食う。良い方法を見つけたら修正する予定。効率化しました(Aug.15, 2012)。 構築後の検索は効率が良い(はず)。ウェーブレット木版との比較は気が向いたらやるかも。 https://code.google.com/p/shellinford/
Run-Length FM-Index - koki
FM-index は検索対象のテキストから予め索引を構築しておくことで，テキストに含まれる任意のパターン文字列の個数を数えるクエリ$ \mathrm{count} を，テキストのサイズに依らず高速に実行できるデータ構造です．加えて，suffix array や inverse suffix array の一部を追加で保持しておくことで，パターンの位置の列挙 $ \mathrm{locate}やテキストの復元 $ \mathrm{extract}といったクエリを高速に実行することができます（自己索引）． 主要な応用としてゲノム解析（例：HISAT2）などが挙げられます．身近なところでは，arXiv をコーパスとした高速な英文コロケーション検索を提供する Hyper Collocation でも用いられています（解説）． FM-Index に関しては，高速文字列解析の世界 や 簡潔データ構造
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
ウェーブレット行列とFM-indexで全文検索を書いてみた - くじらにっき++
FM-index++を公開しました - Yasuo Tabeiの日記