研究

有向グラフの簡潔表現GLOUDS

ネタ元 Johannes Fischer, Daniel Peters: GLOUDS: Representing tree-like graphs. J. Discrete Algorithms 36: 39-49 (2016) 概要 木の簡潔データ構造LOUDSを拡張した有向グラフの簡潔データ構造GLOUDSを提案する in-edgeが2以上のノードをコピーして、グ…

gitよく使うコマンドメモ

git凄い,でもすぐ使い方忘れる.なのでメモ. 随時追加していく予定. 注意:gitよく分からないです.検索して使ったコマンドの履歴みたいなものなので正しい使い方じゃないかもしれないです. 基本 git branch:ブランチの種類と,現在のブランチの確認 gi…

リビジョン間のtexの差分をpdfで見る

あまりエレガントな方法ではないけども,個人的に我慢できるレベルの方法をメモする. 比較したいリビジョンをそれぞれclone git clone hoge.git old cd old git checkout hogerevision git clone hoge.git new cd new git checkout fugarevision 差分pdfを…

LZ77分解 3

LZ77分解 2 - kg86 Laboratory 前回までは接尾辞木を使ったアルゴリズムを紹介した.今回は接尾辞配列を使った計算アルゴリズムを紹介する.接尾辞木は全ての接尾辞を辞書順に並べた時の各接尾辞の開始位置の並びを保存した配列である.(今後SAと表記する)…

論文を書く時のお役立ちサイト

Create LaTeX tables online texのテーブルを見たまま編集できるサイト.コピペとかは出来ないが,セルの結合,分割などがとても便利. Springer Exemplar 英文が正しいかどうか考えるのにとても便利.英文を入力すると,その英文を使用した論文の件数を教え…

LZ77分解 2

LZ77分解 - kg86 Laboratory 前回の続きである.前回はLZ77分解の定義とその応用について説明した.今回はLZ77分解(圧縮)の計算方法について説明する. 接尾辞木を用いたLZ77分解(Algorithm KK) 接尾辞木とは,入力文字列の全ての接尾辞を格納した木構造で…

LZ77分解 1

LZ77分解とは1977年にZivとLempelによって提案された圧縮法である.彼らは翌年にも圧縮法を提案しており,そちらはLZ78分解と呼ばれる.LZ77とLZ78は違う圧縮法にも関わらず,どちらかを明記せずLZ圧縮と単純に呼ばれることがあるので注意して欲しい. 今日…

使えるアルゴリズムとデータ構造 1: Nearest Common Ancestor,Range Minimum Query

これまで様々なアルゴリズムとデータ構造が提案され,またより良い物へと改善されてきた.その中のいくつかは様々な問題に応用されるような汎用的なツールとなっている.そのようなアルゴリズムとデータ構造はとても頭の良い人が考えたもので,エレガントな…

Byte Pair Encodingの拡張

下の論文を読んだのでメモ Shirou Maruyama, Youhei Tanaka, Hiroshi Sakamoto, Masayuki Takeda: Context-Sensitive Grammar Transform: Compression and Pattern Matching. IEICE Transactions 93-D(2): 219-226 (2010) Byte Pair Encodingとは文法圧縮で…

STVF符号

VF符号はvariable length to fixed length codeの事で,可変長の文字列に固定長の符号を割当てる形式のこと.符号化は割当て領域(文字列)と符号語それぞれについて可変長にするか,固定長にするかで4パターンの符号化が考えられる. FV, VV符号は圧縮でき…