Oktaviaとは何か？ — Oktavia
OktaviaはJavaScriptで書かれた全文検索エンジンです。ブラウザとnode.js上で動作します。 プロジェクトのゴールは、 Sphinx のHTML出力用の、代替の検索エンジンを作ることです。 SphinxはPythonで書かれた素晴らしいドキュメントツールです。このツールはシンプルなフォーマット(reStructuredText)のテキストを読み込み、HTMLやPDFなどのさまざまなフォーマットに変換します。このツールはプログラミング言語のリファレンスマニュアルやソフトウェアの使用方法の説明、ライブラリやAPIのドキュメントなどでよく使われています。 SphinxのHTMLジェネレータにはシンプルな組み込みの検索エンジンが搭載されています。Sphinxで作成されたHTMLドキュメントには検索窓がついており、ドキュメント全体を検索できるようになっています。これはJavaScri
ハクビシンにもわかる全文検索 - Qiita
高速な全文検索アルゴリズムであるFM-indexについて解説する。理解しがたい点や間違っている点があれば是非コメントで指摘してほしい。 概要 FM-indexはリニアな文字列に対して検索をするアルゴリズムで、主に簡潔データ構造とBWT(およびLF mapping)という二つのアイデアから成り立っている。BWTはBurrows-Wheeler変換のことで、文字列を特殊な並び順に変換するという可逆関数である。BWTされた文字列を簡潔データ構造固有の操作をすることで、クエリ文字列の長さに比例した短い時間で文字列を探し出すのがFM-indexだ。 簡潔データ構造 簡潔データ構造に関してはFM-indexで必要となる二つの関数だけ説明して、詳細は次の機会に譲るとする。さて、二つの関数はともに文字列のある位置より前の部分に含まれている文字の数を数え上げるというものでrank()とrankLessTha
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による全文検索
2. • 文書から文字列を検索する方法は2通りに分類できる A. 前処理が不要な方法 (力任せな方法, KMP法, BM法) B. 前処理が必要な方法 (転置インデックス, 接尾辞配列) • Bは前処理の時間が必要なかわりに, 同じ文書から何回も検索する場合はAよりも高速 • FM-IndexはBに分類される方法で, 文書の長さに依存しない時間で検索できる 4. 前処理１：接尾辞配列の構築 0 mississippi$ 1 ississippi$ 2 ssissippi$ 3 sissippi$ 4 issippi$ 5 ssippi$ 6 sippi$ 7 ippi$ 8 ppi$ 9 pi$ 10 i$ 11 $ 11 $ 10 i$ 7 ippi$ 4 issippi$ 1 ississippi$ 0 mississippi$ 9 pi$ 8 ppi$ 6 sippi$ 3 siss
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
