B木 - naoyaのはてなダイアリー
昨年から続いているアルゴリズムイントロダクション輪講も、早いもので次は18章です。18章のテーマはB木(B Tree, Bツリー) です。B木はマルチウェイ平衡木(多分木による平衡木)で、データベースやファイルシステムなどでも良く使われる重要なデータ構造です。B木は一つの木の頂点にぶら下がる枝の本数の下限と上限を設けた上、常に平衡木であることを制約としたデータ構造になります。 輪講の予習がてら、B木を Python で実装してみました。ソースコードを最後に掲載します。以下は B木に関する考察です。 B木がなぜ重要なのか B木が重要なのは、B木(の変種であるB+木*1など)が二次記憶装置上で効率良く操作できるように設計されたデータ構造だからです。データベースを利用するウェブアプリケーションなど、二次記憶(ハードディスク)上の大量のデータを扱うソフトウェアを運用した経験がある方なら、いかにディ
セミナー資料公開「Extreme Search! 次世代検索エンジンSedueが実現する驚異のパフォーマンス」
2009年4月8日(水) 13:00〜15:30に開催されましたPreferred Infrastructureによる製品紹介セミナーの発表資料です。
2-8(岡野原)
６．テーマ概要 ITの急速な進化の中，ますますデータの効率的な保存方法，転送方法が必要とされている．そうした中，実際のデータの内容により自然に即した「単語」という塊を抽出して圧縮するという方法を開発するがこのプロジェクトの目的である．ここでいう単語というのは自然言語における単語ではなく，データの中で塊として見られるあらゆる形での単語を意味する．最終的には，これを用いた圧縮ソフトを開発するのが目的だが，ここでは，そのメインとなる単語抽出アルゴリズム (Word eXtraction，WX法) についての研究開発を行なう． 例えば，abracadabraというデータに対して，ここで開発するプログラムはabraという単語を抽出する．abraという単語を抽出する際に，文の実際的な意味はまったく利用せず，確率情報や，エントロピーなどを計算し，どれだけその単語が周りから「浮き出ているか」，「抽出す
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
