Suffix Array - Qiita
これは「データ構造とアルゴリズム Advent Calendar 2018」9日目の記事です． はじめに Suffix array1 はよく知られたデータ構造のひとつです．1990年に提案2されて以来，その使われ方は多岐にわたります．本記事では，この suffix array の基本事項として， suffix array とは何か suffix array を全文索引として用いる方法 を紹介したいと思います． パターンマッチングと全文索引 パターンマッチング とは，文字列 $T$ から，パターンと呼ばれる文字列 $P$ を探す問題です．たとえば， $T =$ 麒麟鼬蝙蝠駱駝蝦蟇鼈樹懶鼠膃肭臍羆狒狒鰐麒麟猩猩鼠鼠鼠鼠鼠蟒蛇鼈鼬羆蜥蜴駱駝羆麒麟鼈鼬狒狒狒狒羆蝙蝠膃肭臍麒麟蝙蝠鼬蜥蜴鼬狒狒蝮樹懶鼬羆蝮膃肭臍麒麟羆駱駝蝙蝠蟒蛇狒狒蝙蝠樹懶鼈蜥蜴駱駝羆鼬羆樹懶犀鰐蝙蝠鼠狒狒蝦蟇鼬蜥蜴鼠蝮蝦蟇蜥蜴龍麒
20分でわかるPurely Functional Data Structures (PDF)
20分でわかる Purely Functional Data Structures k.inaba (http://www.kmonos.net/) Apr. 4, 2010 あらすじ イ ミ ュ ー タ ブ ル デ ー タ 構 造 は 遅 い Immutable Object だけで作るデータ構造 この本の 内 容を 全速力で 布教する お題：キュー (Queue) • FIFO (First-In First-Out) • pushBack(e) でデータeを入れる • popFront() で取り出せる • 入れた順に出てくる • 以上 破壊的キュー Immutable Object でない 打倒すべき目標 代 入 手続き型でよくある interface Queue<E> { void pushBack(E e); E popFront(); } よくある実装 1 2 3 ・ 4 ・
)
トライ (データ構造) - Wikipedia
"A", "to", "tea", "ted", "ten", "i", "in", "inn" というキー群によるトライ木 トライ木（英: trie）やプレフィックス木（英: prefix tree）とは、順序付き木の一種。あるノードの配下の全ノードは、自身に対応する文字列に共通するプレフィックス（接頭部）があり、ルート（根）には空の文字列が対応している。値は一般に全ノードに対応して存在するわけではなく、末端ノードや一部の中間ノードだけがキーに対応した値を格納している。2分探索木と異なり、各ノードに個々のキーが格納されるのではなく、木構造上のノードの位置とキーが対応している。 キーが文字列である連想配列の実装構造としても使われる。右図の例では、ノードを表す丸の中にキーが書かれ、連想される値がその下に書かれている。値が書かれていないノードはキー文字列の途中までにしか対応していない。各英単語
「モデル」とは何か，について考えていたことを，DSIRNLP(データ構造と情報検索と言語処理勉強会)で発表してきました - a lonely miner
先日， @overlast さんから，DSIRNLP(データ構造と情報検索と言語処理勉強会 )という会にお誘いを頂きまして，以前から考えていたことをちょこっとお話してきました．当日の様子は， @mamoruk さんが togetter にまとめてくださっていますので，そちらもご覧ください． 第5回 データ構造と情報検索と言語処理勉強会 #DSIRNLP - Togetterまとめ 私の発表スライドは slideshare に置いておきました．いくつか直したいところがあるので，そのうち差し替えるかも． いまさら聞けない “モデル” の話 @DSIRNLP#5 from Koji Matsuda 他の方々がものっそい最先端な話ばかりのなか，私一人だけがひどくぼんやりとした内容でたいへん恐縮でしたが，問題意識を共有するきっかけを頂けたことに感謝しています． そもそもこの話をしようと思ったきっかけ
中学生にもわかるウェーブレット行列 - アスペ日記
id:echizen_tm さんの記事「ウェーブレット木の効率的で簡単な実装 "The Wavelet Matrix"」から始まったウェーブレット行列ブームから半年以上が過ぎ、すでに枯れた技術として確立されつつある感があります。 …嘘です。 日本以外ではあんまり来ていません。 理由としては、やはりアルファベット圏では単語境界が明確であるため、こちらの記事で書かれているような「キーワード分割の難易度」といったことがあまり問題にならないということがあるかもしれません。 まあ、そういうわけで局所的に来ているウェーブレット行列ですが、日本語をはじめとする単語境界のない言語圏にとっては重要なネタであると思うため、解説記事を書き直して*1みようと思います。 ウェーブレット行列でできること 主となる操作は、文字列に対する 定数時間の rank() と select()*2 です。 rank() は、「文
素数ゼミとハッシュテーブル － ＠IT
「素数ゼミ」と呼ばれる一風変わったセミをご存じだろうか。記者は2005年に出版された『素数ゼミの謎』（吉村仁、文芸春秋）で知ったのだが、北米には13年または17年周期で大量発生するセミがいるという。素数ゼミたちは、きっちり決まった年数を地中で過ごしてから、成虫となって地表に出てくる。6種ほど知られている素数ゼミたちは、それぞれ決まった年に一斉に地表に出てきて、わずか数週間という短い夏を生殖活動に捧げて、一斉に死んでしまう。次に彼らの子どもたちが地表に出てくるのは13年とか17年後だ。この2008年の夏にも、アメリカの中南部で大量発生が予想されている。 1度に60億匹とか70億匹という単位で、限られた地域で発生するために、アメリカでは迷惑な存在としてしか見られていないようだが、素数ゼミは生物学者たちにとっては、非常に好奇心をくすぐられる研究対象のようだ。 吉村氏によれば、素数ゼミが素数年周期
はてなブログ | 無料ブログを作成しよう
トルコ水紀行 －前編 イスタンブール－ みなさんこんばんは、地図子です！8月は久しぶりに毎月更新にしようと思います。今までずっと名古屋について書いてきましたが、ワープして・・・ トルコについて書きたいと思います。 2024年6月に念願のトルコに行ってきました。いつからトルコに行きたかったかわから…
連想配列はトライでしょ的な話がでていたので入門記事を書いてみた - EchizenBlog-Zwei
なにやらDan Kogai氏の以下の記事が話題になっている様子。 404 Blog Not Found:Algorithm - 連想配列の実装としてのハッシュはオワコン? 連想配列(キーワードを投げると対応する値が返ってくるデータ構造)はハッシュテーブルで実装するのではなく、これからはトライ(trie)木を使うのがイケてる！(意訳)という内容だった。 連想配列にハッシュテーブルを使うのが良いか悪いかについては色々と意見があると思うので特にこの記事では触れない。 今回は連想配列として使えると話題のトライ木とはなんぞ、という入門的な記事にしようと思う。 トライ木が持つ機能 最初にトライが持つ以下の3つの機能について説明する。 - lookup - common-prefix-search - predictive-searchまずトライは連想配列として利用できる。つまりキーワードと値のペアを登
私のブックマーク ： 簡潔データ構造
田部井靖生（科学技術振興機構 ERATO湊離散構造処理系プロジェクト研究員) はじめに 近年、Web技術や計測技術の発展により言語やゲノムデータは大規模化しています。従来のデータ構造は大規模データを扱うにはサイズが大きくメモリに載らない、 しかし、圧縮するとランダムアクセスをすることができないという欠点があります。 簡潔データ構造とはデータを小さく保存かつ高速な操作が可能なデータ構造です。 近年、集合、文字列、木、グラフデータを扱うための簡潔データ構造が提案され注目を集めています。 私たちの身近なアプリケーションとして、Google日本語入力では簡潔木LOUDSの実装が使われ、実際に使われはじめています。 また、有志によるそれらを解説したサイトやライブラリなども利用可能になりつつあります。 そこで、このページでは簡潔データ構造を用いた研究開発のためのいろいろなリソースを紹介します。 解説記
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
