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
動的ダブル配列を実装してみた - Negative/Positive Thinking
はじめに 形態素解析器などで利用されている「ダブル配列(double array)」の勉強するため、実装をしてみた。 動作を確認するために書いただけなので重い。。。 ダブル配列とは 文字列の検索をO(1)で行えるTrie(トライ木)の効率的なデータ構造 2つの配列BASEとCHECKで木の遷移を表現する あるノードsにいるときに、次の文字がaだったとき、以下を満たす 次のノード : 現在のノード : ただし、N(a)は文字aを表す整数(内部コード) トライ木の遷移の(2次元)配列構造を圧縮したものに相当 2次元配列構造とは、縦をノード番号、横を文字にしたとき次のノード番号を保持する この構造では、かなり疎になる(無駄が多い)→圧縮！！！ コード 以下の論文の前半部分を参考に改良なしの動的ダブル配列を実装してみた http://ci.nii.ac.jp/naid/110002725995 追
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
