O(N) 時間のランダムアクセスのための空間効率の良いSLPエンコーディング

文字列 T のための直線プログラム (SLP) G は、T のみを生成する文脈自由文法 (CFG) であり、T の圧縮表現と見なすことができます。本論文では、G を n N + (n + n') (n+) + 4n - 2n' + o (n) ビットでエンコードする方法を示し、最悪の場合 O(N + p - q) 時間で Tp . q を抽出するランダムアクセスクエリをサポートします。ここで N は T の長さ、はアルファベットの大きさ、n は G の変数の数、n' n は G の DAG 表現における対称重心パスの数です。