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)とは何かと言うとその
情報系の国際会議の採択率 - ny23の日記
ちょっとした理由*1で某国際会議のポスターセッションの採択率を調べた過程で，副産物として情報系の国際会議の採択率を各分野の研究者がまとめたサイトがいくつか見つかったので，メモしておく． Artificial Intelligence: Conference Acceptance Ratio Statistics – Adaptive Toolbox Linguistics: ACL Member Portal | The Association for Computational Linguistics Member Portal Software Engineering: Software Engineering Conferences (Statistics) Networking: Networking Conferences Statistics (http://ppadala.n
『MPJoin を使った類似データ抽出 ―アルゴリズムシリーズ 1―』
Hattori です。以前書いた記事の冒頭 で、”今度はシリーズで何かエントリを書きたい ! ”と軽いノリで一文を表記しておいたら、ホントにやることになりました。 弊社のエンジニア組織の特徴のひとつに、手を上げる・声を上げると、『じゃ、やってよ。』というノリで返ってくるという事が挙げられるのですが、今回もその例に漏れなったわけですね・・・。シクシク・・・。 というわけで、何を書こうかなぁって話しなんですが・・・。私の場合アルゴリズム系の話しかできそうにないので、毎回ポツポツとマイナーで極一部の人にしかウケないテーマを紹介して行こうと思います。 で、初回の今回は SimilarityJoin 関連のアルゴリズムで "MPJoin" というやつを紹介したいと思います。 ■ Similarity Join とは何ぞや？ まず最初に SimilarityJoin [1] の定義なんですが、ざっくり
『MaxentSets を使った芸能人推薦 ―アルゴリズムシリーズ 2―』
度々登場させて頂いております hattori です。 ボスからのお達しで2回目のネタを書くことになりました。( 前回のネタはこちら ) 聞く所によると3ヶ月に一回くらいのペースで本シリーズ？を書かねばならないのですが、1年後に果たして書くネタが残っているか、、、若干微妙な感じです。汗。 さて本日のテーマですが、" Set Expansionを利用した芸能人推薦の方法 " を紹介しようと思います。これは以前、株式会社 mixi 様との合同勉強会で発表した内容の補足的な話になっていまして、以下の発表スライドを先に斜め読みして頂けますと以降の話が分かり易いかと思います。 ■ Set Expansion とは何ぞや？ Set Expansion とは 『 SEEDとなる部分セットを拡張・補完して、より完全なセット集合を作る 』 というタスクの事です。若干分かりに難いのですが、より平易に言うと 『
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
