高速かつ省メモリで文字列を扱うデータ構造「wavelet tree」
はじめに 大規模なデータを扱うアプリケーションでは、速度とともに作業領域量も大きな問題となります。作業領域がメインメモリに収まらない場合、スワッピングが発生し、大幅な速度低下につながります。そのため近年、データ構造は高速なだけでなく、作業領域量が小さいことも求められています。今回紹介するのは2003年に提案されたデータ構造、wavelet tree（以下「WT」と表記）です。WTは圧縮索引やSuccinct Data Structureなど、データをコンパクトに表現する際に重要なデータ構造です。WTは文字列T[0...n-1]が与えられた時、次の2つの操作を定数時間でサポートします。 rank(p, c)――T[0...p]中のcの出現回数を返す select(i, c)――(i+1)番目のcの位置を返す WTの作業領域量は、文字列をそのまま保存した時の約2倍程度です。 対象読者 C++の
Data Structures for Text Sequences
Next: Introduction Data Structures for Text Sequences Charles Crowley University of New Mexico Abstract: The data structure used ot maintain the sequence of characters is an important part of a text editor. This paper investigates and evaluates the range of possible data structures for text sequences. The ADT interface to the text sequence component of a text editor is examined. Six common sequenc
Rabin Karp アルゴリズムでコード重複の検出 blog.bulknews.net
Rabin Karp アルゴリズムでコード重複の検出 YAPC::NA で会った Fotango の Norman Nunley がつくってる Algorithm::RabinKarp モジュールが面白げです。 Rabin Karp 文字列探索アルゴリズム (wikipedia) を使って文字列のハッシュ（ダイジェスト）をチェックし、同一の値を示す部分を重複しているとみなしてレポートしてくれます。つまり、プロジェクト内のコードのコピーペーストを検出するツールとして使えるというわけ。 ためしに Plagger で試してみた結果は rabin.txt のようになりました。プラグインの register_hook や CustomFeed での Feed オブジェクトの生成など、イディオム的に使う部分が大半になってしまっていますが、いくつか実際コピペで再利用しているコードが検出できています。 c
きまぐれ日記: Autolink: 前方最長一致ではなく最長キーワード優先一致を実現する
Hatena のキーワード置換アルゴリズムがTRIE ベースの手法に変更になったようです。以前に AC法でやる方法の記事を書いたのですが、それと似たことをやってるのでしょうか。 AC法のやり方は単純で、前方から最長一致でキーワードを見つけていきます。これまでは長いキーワードから順番に見つけていく方法(最長キーワード優先一致)だったそうですが、前方から見つけていく方法だと短いキーワードが優先される場合があります。 http://d.hatena.ne.jp/ita/20060119/p1 http://d.hatena.ne.jp/hatenadiary/20060119/1137667217 本文：あいうえおかきくけこさしすせそ KW1 いう KW2 うえおかき KW3 かきく KW4 きくけこさし という文でKW1-KW4のキーワードがマッチする場合、新しくなった方法では「いう」と「かき
はてなダイアリーキーワード抽出・リンクを高速化したい - higepon blog
きまぐれ日記:はてなキーワードを高速に付与という エントリーがとても気になる内容です。 はてなダイアリーの内部処理の中でも重めの処理である、キーワード抽出・リンクについて、高速化を試みるというとてもありがたい内容です。 高速化にはAC法という方法を使用しているようです。(恥ずかしながら全く知りませんでした。） AC法の肝はトライ (TRIE) という木構造を利用して、高速に前方一致検索が出来るところです。 トライの説明は高林さん（namazuの中の人）の説明がとても分かりやすくておすすめです。 要は一文字ごとにばらして、ツリーに格納しておいて、検索後のつづりの通りにツリーをたどるということらしいです。 トライの特徴は、辞書に登録されている項目の数がどんなに多くても、キーの長さに比例した時間で探索が行えるという点である。 実際に 日記で紹介されている hatenakeyword というツール
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
https://labs.cybozu.co.jp/blog/kazuho/archives/2006/04/summarize.php
Kubeflow Central Dashboard
