文章基本信息
- 标题：正規言語上のAbstract Numeration Systemの文字列圧縮への応用
- 本地全文：下载
- 作者：新屋 良磨
- 期刊名称：コンピュータ ソフトウェア
- 印刷版ISSN：0289-6540
- 出版年度：2013
- 卷号：30
- 期号：3
- 页码：3_163-3_179
- DOI：10.11309/jssst.30.3_163
- 出版社：Japan Society for Software Science and Technology
- 摘要：
Abstract Numeration System ( ANS )は自然数と言語を一対一に対応づける記数法( Numeration System )である．本論文では，正規言語 L について， L に属する文字列 w の L 上のANSでの数 – w の L 内での順番の計算によって圧縮を定義する．さらに，ANSによる圧縮では: (1) (無限集合である)正規言語 L から平均圧縮率を計算可能．(2) 圧縮対象の文字列長に対し準線形時間で圧縮可能．(3) 圧縮対象文字列 w を分割して並列に圧縮可能等の良い性質を持つことを示す．本論文において，特に断らない限り任意長整数の乗算が定数時間で計算可能な一様コストモデルを仮定するが，乗算にコストがかかる場合での議論や解決策の提案も行う．
