Lucene lecture at Pisa
Package: org.apache.lucene.analysis An Analyzer is a TokenStream factory. A TokenStream is an iterator over Tokens. input is a character iterator (Reader) A Token is tuple <text, type, start, length, positionIncrement> text (e.g., “pisa”). type (e.g., “word”, “sent”, “para”). start & length offsets, in characters (e.g, <5,4>) positionIncrement (normally 1) standard TokenStream implementations are
Cache-Oblivious データ構造入門 @DSIRNLP#5
Semi supervised, weakly-supervised, unsupervised, and active learning
B+Trees and why I love them, part I - Ayende @ Rahien
One of the things that I enjoy about learning new things is the way it changes the way I look at the stuff that I already knows. Reading the LMDB codebase, and implementing a persistent B+Tree has given me a new depth of understanding about how relational databases (and Esent, too), work. I am going to go back to level zero and assume that you have never heard about this. You probably know what a
DO++: 左傾赤黒木
漢字で書くと仰々しいが、赤黒木 (wikipedia) red-black tree (english wikipedia)という平衡二分木で最も多くつかわれているデータ構造の、改善版が出てたそうだ。 left-leaning red-black tree (pdf) 日本語に訳すと左傾赤黒木かな。簡単な漢字を並べている感じがしてしまう 赤黒木の詳細については、wikipediaなどをよんでもらうとして、これは更新時間が定数で更新箇所が局所的（これはマルチスレッドとかでロックする箇所をかなり細かい単位で、できるという強い利点もある）のだが、実装が結構面倒くさい。例えばC++ stl のmapとかの赤黒木の実装のstl_tree.h(google code search)は大変なことになっている（特にRb_tree_rebalance_for_eraseとか） 赤黒木というのは動的データ構造
RDBMSで使われるB木を学ぼう （1/3）－ ＠IT
第5回 RDBMSで使われるB木を学ぼう はやしつとむ アナハイムテクノロジー株式会社 2009/6/22 オブジェクト指向によって、アルゴリズムは隠ぺいされていることが多くなった。しかし、「用意されていない処理」が求められたときに対応できるだろうか（編集部） 第3回「AVL木で木構造を学ぼう」、第4回「もっとAVL木で木構造を学ぼう」と2回連続でAVL木について解説しました。 今回はAの後だからBというわけではありませんが、B木（B-Tree）を取り上げます。 B木の変種であるB+木やB*木は、OracleやPostgreSQL、Firebirdなどのリレーショナルデータベースでインデックスとして利用されている、メジャーな木構造です。 筆者はDelphi 2009でサンプルプログラムを作成していますが、Delphiをお持ちでない方は下記のURLからTurboDelphiをダウンロードして
LCP(Longest Common Prefix)を用いたSuffix Arrayの検索 - EchizenBlog-Zwei
Suffix Arrayは「インデックスの構築」と「キーワードの検索」からなる。それぞれ構築には文字列のsortが、検索には文字列の二分探索が必要になる。 以前にCompressed Suffix Arrayのライブラリtsubomiを実装したときにはsortについてはマルチキー・クイックソート(multikey-quicksort)というアルゴリズムを用いた。一方で二分探索については特に工夫をしていなかった。 さすがにこのまま放っておくのは気が引けたのでSuffix Array論文を読みなおしてみたらLCP(Longest Common Prefix)を用いた二分探索の方法が書いてあった。シンプルだが賢い方法だったのでメモしておく。これはすごい(というか今まで読み飛ばしてたことのほうが問題ですね。はい)。 さて。まずLCP(Longest Common Prefix)とは何かと言うとその
Compressed Permuterm Index: キーワード辞書検索のための多機能＆省メモリなデータ構造 - Preferred Networks Research & Development
はじめましてこんにちわ。 4月からPFIで働いているまるまる（丸山）です。最近のマイブームはスダチです。 リサーチブログの更新が再開されたので、私も流れに乗って初ブログを書いてみようと思います。 今回は社内の情報検索輪講で少し話題にあがったCompressed Permuterm Indexを紹介したいと思います。 Paolo Ferragina and Rossano Venturini. “The compressed permuterm index”, ACM Transactions on Algorithms 7(1): 10 (2010). [pdf] これを実装したので以下のgoogle codeに晒してみることにします。 http://code.google.com/p/cpi00/ 修正BSDライセンスです。ソースコードは好きにしてもらって構いませんが、完成度はまだまだな
情報検索ことはじめ〜教科書編〜 - シリコンの谷のゾンビ
2011-01-18追記 教科書編その2 にて2011年版のIR教科書を紹介しています 情報検索(IR)の勉強を本格的に始めて8ヶ月．大体どんな分野があって，どんなことを勉強すればいいのかわかってきた（と思う）．この気持ちを忘れないうちにメモしておこう．以下，若輩があーだこーだ言ってるだけなので，間違いや他に情報があれば，ぜひコメントをお願いします． # ここで述べている情報検索とは，コンピュータサイエンスの一分野としての情報検索です．図書館情報学の側面は一切扱っていません，あしからず． というわけでまず教科書編． 本腰を入れて勉強する場合，基礎づくりのためには教科書選びがいちばん重要だと思っている．自分の知っている限り，情報検索における教科書の選択肢はそれほど広くはない．以下に紹介する本は，情報検索を学ぶ上で「買い」の本．これらを読めば，最新の論文を読めるだけの土台はできるし，専門家と議
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
