Suffix Arrayメモ - Negative/Positive Thinking
はじめに Suffix Arrayあたりをちょっと調べてみたのでとりあえずメモ。 調べてみたら結構研究されていて全部まとめるのが面倒あとできちんと理解しておきたい。 Suffix Array(接尾辞配列)とは 文字列に対して、その文字列の接尾辞集合を辞書順ソートしたもの ここでの接尾辞集合は「abcd」という文字列の場合、以下の4つの接尾辞になる abcd bcd cd d これは各インデクスから最後までの部分文字列なので、元の文字列があればインデクスから部分文字列を得ることができる 与えられた文字列からある文字列が含まれるかどうかを検索したい場合、Suffix Arrayは辞書順に並んでいるので、2分探索することで高速に検索することができる 構築方法 普通のQuicksort 普通に文字列をソートする方法 QuicksortにO(n log n)、文字列比較にO(n)かかる Mamber
最近のtrieの話（xbwなど） - Preferred Networks Research & Development
ブログの更新がとまっていましたが、また少しずつ更新してきたいと思います。 今回はtrie（トライ）の最近の話をしたいと思います。 trieはキー集合を扱うためのデータ構造の一種です。例えば、単語集合からなる辞書であったり、クロールしたURL情報を扱ったり、最近だと、KVS（Key Value Store)のようにキーを介してデータを保存、読み込みをしたりと様々な場面で利用されます。 同じようにキー集合を格納するデータ構造としてハッシュを利用する方法があります。キーからハッシュ値を計算し、その場所に文字列へのポインタを格納しておくデータ構造です。ハッシュを利用した場合とtrieを利用した場合の一番の大きな違いは、trieの場合だと、ある文字列から始まるキーを全て列挙する、いわゆる接頭辞探索ができることです。例えば”te”で始まる文字列を網羅的に調べることができます。木をたどって、”te”の下
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
