トライと STL コンテナの比較（トライ（ダブル配列，簡潔データ構造）と STL コンテナ - ny23の日記）を見て，Darts clone の構築時間は長すぎると思ったので，各キーに関連付ける値を指定しないときは，DAWG を経由しないでダブル配列を構築するように改良…

gcc 4.2.1 / 4.0.1 では，標準のヘッダで定義されているマクロ LINK_MAX と名前がぶつかってコンパイルできないことを n-yo さんに教えていただいたので，その部分だけを修正しました． Darts clone 0.32 e4 -> e5 LINK_MAX を UNIT_LINK_MAX に変更しました…

ダブル配列のライブラリ Darts clone 0.32g に関する資料を一通り書き上げることができました．データ構造や構築方法の説明が書いてあり，一部のアレゲな人にとっては役に立つ情報かもしれません． Darts clone 0.32g の解説 - やた＠はてな日記 はじめに - …

言語処理学会のチュートリアルで紹介されていた符号 PFOR に関する（とおぼしき）文献です．最近は物忘れがひどいのでメモついでにリンクを貼っておきます． Performance of compressed inverted list caching in search engines Jiangong Zhang, Xiaohui Lo…

味噌煮込みうどん，ごちそうさまでした．

情報処理学会第 72 回全国大会での発表に使用したスライドをアップロードしました．内容を簡単に説明すると，順序木に対する簡潔表現 6 種類とノードの配置順序 2 種類の組み合わせを試して，どれが良いのかを調べたというものです．実験において Google N-g…

一応，今日から参加しています．でも，今朝になって忘れ物に気づいたおかげで，出発前にいらぬ苦労をすることになり，とても疲れました． 本日学んだこと 荷物の確認はお早めに． そんなことは分かっているはずなのですが…．やってしまうわけです． RDB とス…

Taiju 0.0.3 のアーカイブをアップロードしました． http://code.google.com/p/taiju/ 右側にある Featured downloads にリンクがあります． Wiki の更新予定 PodsTrieBuilder TrieBase TrieConverterBase 追記（2010-03-07）：Wiki を更新しました．でも，…

Visual C++ 2008 でエラー・警告が出ないように修正しました．http://code.google.com/p/darts-clone/ 変更点 std::fopen() -> ::fopen_s() ::stdcerr -> std::cerr キャストを追加 関数内部で使っていない引数を名前なしに変更 追記（2010-03-17）：std::sw…

情報処理学会 第 72 回 全国大会にて発表をする予定なのでスライドを作成中です．発表の内容は，少し前に公開した taiju（大規模トライ用ライブラリの公開（ソースコードのみ） - やた＠はてな日記）についてです．発表時間が 15 分なので，まず全体の概要を…

ダブル配列に関する基礎的な知識だけでなく，実装段階でおこなわれている改良についても触れているので，かなり長くなってしまいました．でも，十分に説明できていない情報がまだあります．時間を見つけて TeX で書き直しておこうとは考えているので，分かり…

トライをダブル配列で表現する Darts では，文字列の集合から一息に辞書を構築することができます．しかし，DAWG をダブル配列で表現する Darts clone では，最初に DAWG を構築し，その DAWG をダブル配列に変換するという手順が必要になるため，Darts と比…

トライをダブル配列で表現する Darts に対して，Darts clone は，基礎のデータ構造として Directed Acyclic Word Graph (DAWG) というグラフ構造を採用し，DAWG をダブル配列で表現するようになっています．

Darts はダブル配列を構築するためのライブラリであり，ダブル配列はトライという木構造を表現するためのデータ構造です．以下のサイトに解説があるので，ここでは概要のみを述べます． トライとダブル配列の解説 Double-Array Articles

Darts clone は，ダブル配列（Double-array）の有名なライブラリである Darts のクローンとして開発したライブラリです．Darts clone 0.32g は，TAIL を用いないという点が Darts と共通しているものの，ダブル配列の各要素を 4 bytes で表現したり，トライ…