ハクビシンにもわかる全文検索 - Qiita
高速な全文検索アルゴリズムであるFM-indexについて解説する。理解しがたい点や間違っている点があれば是非コメントで指摘してほしい。 概要 FM-indexはリニアな文字列に対して検索をするアルゴリズムで、主に簡潔データ構造とBWT(およびLF mapping)という二つのアイデアから成り立っている。BWTはBurrows-Wheeler変換のことで、文字列を特殊な並び順に変換するという可逆関数である。BWTされた文字列を簡潔データ構造固有の操作をすることで、クエリ文字列の長さに比例した短い時間で文字列を探し出すのがFM-indexだ。 簡潔データ構造 簡潔データ構造に関してはFM-indexで必要となる二つの関数だけ説明して、詳細は次の機会に譲るとする。さて、二つの関数はともに文字列のある位置より前の部分に含まれている文字の数を数え上げるというものでrank()とrankLessTha
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++を公開しました - Yasuo Tabeiの日記
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や２０文字種のタンパク質など、文字種類数が少ない対象にはハミング距離
Oktavia - Web上、クライアントサイドの検索エンジン MOONGIFT
お、かなりパフォーマンスが高い！ サイト内検索を作る際にまず思いつくのがサーバサイド内での検索です。また公開情報であればGoogleの検索エンジンを使う手もあります。今回はそのどちらでもない第三の選択肢、JavaScriptによるクライアントサイドの検索エンジンです。 検索の難しさは何と言ってもインデックスの生成部分になるかと思います。良くあるのは分かち書きとn-gramだと思いますが、JavaScriptベースの検索エンジンではどちらも不向きです。そこでOktaviaではFM-Indexと言うアルゴリズムを使ってインデックスを生成しています。 何はともあれまずは体験してみましょう。 JSXのプロジェクトページにて使われています。右上にある検索ボックスに単語を入れてエンターキーを押しましょう。 クライアントサイドだけあって高速にレスポンスが返ってきます。一致した部分がハイライトされているの
Shibu's Diary: ブラウザ上で動く検索エンジンOktavia
渋日記@shibu.jp 渋川よしきの日記です。ソフトウェア開発とか、ライフハックを中心に記事を書いていきます。 HTML5アドベントカレンダー向けのエントリーです。ブラウザでできることがどんどん増えています。2013年に一部で熱狂的な話題となった本の高速文字列解析の世界 を読んで意識が高まったので、勢いにまかせてブラウザで動く検索エンジンを作ってみました。写真は著者の岡野原さんにお会いしたときにいただいたサインです。 ブラウザ上の検索エンジンと転置インデックスと東アジアの微妙な関係 全然調べていないので、歴史とかよくわからないのですが、僕が始めてブラウザ上で動く検索エンジンと出会ったのは、Sphinxです。SphinxはPythonで書かれたドキュメントツールです。ドキュメントツールというとJavaDocを始めとして各種あります。大きく、自然言語中心のもの(Texとか)と、APIリファレ
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
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
