宇野毅明 の ホームページ
English English version is here 宇野 毅明 の ホームページ あなたは 人目のお客様です． このページは，国立情報学研究所准教授，宇野毅明の研究分野である，最適化とアルゴリズム、最近はデータマイニングとビッグデータ、データ解析に関する解説，私の研究内容と業績，最近の活動を紹介するページです． この分野の研究者の方を始めとして，いろいろな方に見てもらいたいと思い，それぞれの方々にあった，説明を用意しました．私の研究内容が知りたい方，論文をダウンロードしたい方，この研究分野に興味のある学生の方，あるいはこの分野の知識を利用したいと思っている研究者の方，また，コストダウンや，システムの高速化を行いたい企業の方々など，役に立つことがあると思いますので，ぜひ，立ち寄って，中をのぞいてみてください． なお本サイトの文章、図版は転載・引用はご自由に行って下さ
heap sortを使った上位ランキング取得プログラム - 遥かへのスピードランナー
Managing Gigabytes 4.6章で解説されているソートのプログラムを実装してみた。 検索エンジンなどでN個のデータの中から上位r個を取得したい場合、まずN個のデータからなるmax-heapを構成して、ルート（最大値）から順にr個をヒープから取り除くというアプローチが考えられる。しかしN>>rの場合、r個のデータからなるmin-heapを構成して、残りのN-r個のデータをheapのルート（最小値）と順次比較して、ルートよりも大きい場合はルートと入れ替えて、heapを再構成する、という手順を取った方がより計算量が少なくて済む、という話。 10万件のランダムな数値をスペース区切りで出力するプログラム #include <iostream> #include <stdlib.h> using namespace std; int main (int argc, char *argv[
The Stony Brook Algorithm Repository
This WWW page is intended to serve as a comprehensive collection of algorithm implementations for over seventy of the most fundamental problems in combinatorial algorithms. The problem taxonomy, implementations, and supporting material are all drawn from my book The Algorithm Design Manual. Since the practical person is more often looking for a program than an algorithm, we provide pointers to sol
Summary of MIT Introduction to Algorithms course
As you all may know, I watched and posted my lecture notes of the whole MIT Introduction to Algorithms course. In this post I want to summarize all the topics that were covered in the lectures and point out some of the most interesting things in them. Actually, before I wrote this article, I had started writing an article called "The coolest things that I learned from MIT's Introduction to Algorit
2009-10-29 - やた＠はてな日記 Succinct なトライの実験
実験の概要 Succinct な木構造を用いてトライを実装すると，コンパクトな辞書を構築できます．しかし，検索速度の面では，その他のデータ構造に劣るという欠点を持ちます．そこで，いくつかのトライを C++ で実装し，ちょっとした性能テストをしてみました．今回のテストで実装したトライは，以下のとおりです． BasicTrie 各ノードに「一つ目の子ノードの ID」，「兄弟ノードが存在するか」，「ラベル」を持たせたトライ 兄弟ノードが隣接するように配置 探索時，子ノードを線形探索して移動先を決定 TernaryTrie BasicTrie の各ノードに「子ノードの数」を加えたトライ 探索時，子ノードを二分探索して移動先を決定 DaTrie ダブル配列によるトライ 探索時，ラベルにより移動先を一意に決定 SuccinctTrie 「一つ目の子ノードを左の子」，「兄弟ノードを右の子」とする二分木に
お手軽転置インデクスを用いた検索エンジン: (1) AND検索編 - シリコンの谷のゾンビ
突然Cでコードを書きたくなったので，なんちゃって転置インデクスを用いた検索プログラムを書いてみた． 転置インデクスとは，索引語と呼ばれる単語が出現する文書情報 (場合によっては位置情報も) を保持したデータ構造のことで，索引語と，それに対応する転置リストによって構成される． # 索引語 -> 転置リスト hoge -> 5: 1,2,3,4,5 fuga -> 3: 1,4,5 piyo -> 2: 4,5これは，hogeという単語が文書1,2,3,4,5に出現し，fugaという単語が文書1,4,5に出現し，piyoという単語が文書4,5に出現する情報を保持している．最初の5,3,2という数字はそれぞれ索引語がいくつの文書に出現したかという文書頻度 (document frequency; DF) を表している． 検索クエリhogeが入力された場合には，文書1,2,3,4,5を検索結果とし
アルゴリズム設計 講義資料 2005
Algorithm Design Course Materials 2013 Oct 7: Introduction and Computational Complexity Oct 15: Search Trees Oct 21: Combinatorial Optimization Oct 28: Heuristic Search Nov 5: Text Search Nov 11: Data Compression Nov 18: Memory Management Nov 25: Graph Algorithms 1/2 Dec 2: Graph Algorithms 2/2 Dec 9: Computational Geometry Dec 16: Concurrency Control Jan 15: Canceled Jan 20: Clustering Course Pro
類似画像検索システムを作ろう - 人工知能に関する断創録
C++版のOpenCVを使ってカラーヒストグラムを用いた類似画像検索を実験してみました。バッチ処理などのスクリプトはPythonを使ってますが、PerlでもRubyでも似たような感じでできます。 指定した画像と類似した画像を検索するシステムは類似画像検索システムと言います。GoogleやYahoo!のイメージ検索は、クエリにキーワードを入れてキーワードに関連した画像を検索しますが、類似画像検索ではクエリに画像を与えるのが特徴的です。この分野は、Content-Based Image Retrieval (CBIR)と呼ばれており、最新のサーベイ論文（Datta,2008）を読むと1990年代前半とけっこう昔から研究されてます。 最新の手法では、色、形状、テクスチャ、特徴点などさまざまな特徴量を用いて類似度を判定するそうですが、今回は、もっとも簡単な「色」を用いた類似画像検索を実験してみます
9月から新学期！ スタンフォード、MIT、バークレイのコンピュータサイエンス講座をYouTubeで受講しよう
日本では9月といえば2学期の始まりですが、米国では9月が新学期のスタート。留学したつもりで海外の大学で行われているコンピュータサイエンスの講座を受講するのはいかがでしょうか？ YouTubeは今年の3月から、大学が公開している講義の動画を集めた「YouTube - EDU」コーナーを開始しました。スタンフォード、ハーバード、マサチューセッツ工科大学（MIT）、カリフォルニア大学バークレイ校（UC Berkeley）、そのほか多くの大学の講座が無料で見られます。 内容はコンピュータサイエンスに限らず、政治、経済、著名人のオピニオンなどが幅広くカバーされています。 YouTube Eduには大量の講座が蓄積されているのですが、自分に興味のある講座を探してそれらを見るには、検索を繰り返したり授業ごとに分割された動画を順番に探したりと、少々手間がかかります。 そこで、ITエンジニアの方が見て役に立
ACM/ICPC国内予選突破の手引き
ACM/ICPCの2008年度の大会日程が公開されています。 国内予選は2008年7月4日，アジア地区予選会津大会は2008年10月25日～27日でホスト校は会津大学です。 参加登録締め切りは2008年6月20日です。 ここではACM/ICPC（ACM国際大学対抗プログラミングコンテスト: ACM International Collegiate Programming Contest）で 国内予選を突破するために必要な情報を載せています。 ACM/ICPC自体については2006年度の横浜大会のWebサイトなどを読んでください。 結局のところ，ACM/ICPCで良い成績を残すにはひたすら問題を解く練習をするしかありません。 ですが，出題される問題の多くはいくつかのカテゴリ，例えば探索問題やグラフ問題，あるいは幾何問題などに分類することができます。 つまり，「傾向と対策」が存在します。 本サ
Common Subsequence 解説
問題名：Common Subsequence (PKU) 出典：Southeastern Europe 2003 難易度：☆☆☆ 問題の種類：DP 解法：LCS (Longest Common Subsequence) 解答ソースコード： 1458-deq.cpp アルゴリズムの概略 DPの四天王（？），LCS (Longest Common Subsequence) そのままの問題です。 アジア地区予選など，通常はこれをひねった問題が出てきます。 LCSとは，二つの値の列（この問題では文字列）が与えられて，最長の共通部分列を見つける問題です。 部分列は連続している必要はありませんが，順序は変更してはいけません。 例えば X = "abcfbc", Y = "abfcab" であればLCSは "abfc" や "abcb" になります。 LCSは一般的に複数ありえますが，この問題ではその長
転置インデックスの圧縮 - tsubosakaの日記
Managing Gigabytes勉強会で転置インデックスの圧縮の話が出たので実際に圧縮を行った場合にどれくらいのサイズになるかを計測してみた。 利用したデータは英語版Wikidiaの全記事で 文書数 2,872,589 単語数 2,735,620 転置インデックスのポインタの数 397,603,176 ぐらいのサイズのデータです。 無圧縮の転置インデックスのフォーマットは 単語ID,文書数,文書1,....文書N, 単語ID,...で各項目4byteとなっており、1.5Gぐらいのサイズになっています。 これに対して各圧縮アルゴリズムを適用した結果は アルゴリズム 無圧縮 Variable Byte Code unary符号 γ符号 δ符号 Rice Coding pforDelta(仮) サイズ 1537MB 497MB 239475MB 474MB 407MB 367MB 455MB
Golomb coding - Wikipedia
This section needs additional citations for verification. Relevant discussion may be found on the talk page. Please help improve this article by adding citations to reliable sources in this section. Unsourced material may be challenged and removed. Find sources: "Golomb coding" – news · newspapers · books · scholar · JSTOR (October 2024) (Learn how and when to remove this message) Golomb coding is
B-tree and UB-tree - Scholarpedia
The B-tree is a dynamic high performance data structure to organize and manage large datasets which are stored on pseudorandom access devices like disks, (Bayer and McCreight 1972). The UB-tree is a multidimensional generalization of the B-tree. Invented in 1969, B-trees are still the prevailing data structure for indexes in relational databases and many file systems (Comer 1979), (Weikum and Voss
画像圧縮アルゴリズム (10) 算術符号化
Range Coder復号化処理による数直線の変化は、以下のようになります。 復号化の場合、数直線は常に0からRangeまでの範囲になります。符号が数直線上のどこに位置しているのかをチェックして、Rangeを復号化されたデータが持つ範囲に変換するところは、やはり算術符号化での処理と本質的に変わりありません。 処理方法は以上になりますが、ここでいくつかの問題を解決する必要があります。まず一つは、符号化と復号化での計算で使用している変数Range / Sizeが0になる可能性があるということで、このときはRangeを計算した結果が0になってしまうため、処理を続けることができなくなります。よってRangeの取り得る最小値は、データのサイズより大きくなければなりません。Range / Sizeが0になった場合、サンプル・プログラムでは単純にエラー終了しています。Rangeの最小値はサンプル・プログ
Canonical Huffman Code
Daisuke Okanohara (VZV05226@nifty.com) 2003/12/9 公開 2003/12/11 誤植、chc.zipのmain.cppを修正 2003/12/13 multidecodeを実装 main.cppもそれに伴い変更 Canonical Huffman Code (以下CHC）は、Huffman法と同様に、最小冗長符号をHuffman木を作成、保持することなく、表引きで、符号化、復号化できる符号法です。 CHCは突然現れたアルゴリズムではなく、1950年代にHuffman法が登場して以来（Huffman法は、Fano符号で有名なFanoが出した最終試験免除の課題を学生だったHuffmanが試験直前に解決して発明された）、表向きにしろ、そうでないにしろさまざまな改良が、実装面、理論面でも行われてきました。その変種はいろいろありますが、その中で最も
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
https://cise.ufl.edu/research/sparse/CSparse/
加藤 和彦 Kazuhiko KATO, Dr. Prof.
Laboratory for Algorithmics: Teaching (Japanese)
データ圧縮の基礎