| 講演名 | 2023-03-14 LZ78符号とそのバリエーションを用いた文法圧縮の構成 有村 光晴(湘南工科大), |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | KiefferとYangは，文法圧縮としてLempel-Ziv78 (LZ78)符号が文法圧縮の一種として実装できることを示している。しかし，そのバリエーションであるLempel-Ziv-Welch (LZW)符号やLemel-Ziv-Yokoo (LZY)符号については，これらを元にした文法圧縮アルゴリズムはこれまで示されていない．本稿では，LZW符号とLZY符号を用いて文法圧縮アルゴリズムを構築する．これにより，LZW符号とLZY符号には，文法圧縮としてLZ78符号には存在しない冗長性が存在することを示し，これを最適化することで符号化性能をLZ78符号と同程度まで改善できることを示す．特に，LZY法においては最適化によってLZ78法と全く同じ生成規則集合が構築されることを示す． |
| 抄録(英) | It is shown by Kieffer and Yang that Lempel-Ziv78 (LZ78) method can be implemented as a variation of grammar-based code. However, concerning Lempel-Ziv-Yokoo (LZY) method and Lempel-Ziv-Welch (LZW) method, which are variants of the LZ78 method, there exists no implementation of grammar-based code using these methods. In this paper, grammar-based codes using these Lempel-Ziv methods are implemented. It is shown that there is redundancy in LZW and LZY methods as grammar-based codes, which does not exist in LZ78 method, and these methods can be optimized to obtain the approximately the same coding performance as the LZ78 method. Especially, by implementing the LZ78 and LZY methods as grammar-based codes, it is shown that the LZY method constructs the same set of production rules as the LZ78 method. |
| キーワード(和) | 情報源符号化 / Lempel-Ziv法 / LZ78法 / LZW法 / LZY法 / 文法圧縮法 |
| キーワード(英) | Source Coding / Lempel-Ziv Method / LZ78 Method / LZW Method / LZY Method / Grammar-Based Coding |
| 資料番号 | IT2022-103,ISEC2022-82,WBS2022-100,RCC2022-100 |
| 発行日 | 2023-03-07 (IT, ISEC, WBS, RCC) |
| 研究会情報 | |
| 研究会 | RCC / ISEC / IT / WBS |
|---|---|
| 開催期間 | 2023/3/14(から2日開催) |
| 開催地（和） | 山口大学常盤キャンパス |
| 開催地（英） | |
| テーマ（和） | RCC・ISEC・IT・WBS合同研究会 |
| テーマ（英） | |
| 委員長氏名（和） | 東 俊一(名大) / 國廣 昇(筑波大学) / 小嶋 徹也(東京高専) / 庄納 崇(ウインドリバー) |
| 委員長氏名（英） | Shunichi Azuma(Nagoya Univ.) / Noboru Kunihiro(Tsukuba Univ.) / Tetsuya Kojima(Tokyo Kosen) / Takashi Shono(Wind River) |
| 副委員長氏名（和） | 小林 孝一(北大) / 石井 光治(香川大) / 四方 順司(横浜国大) / 花岡 悟一郎(産総研) / 野上 保之(岡山大学) / 石川 博康(日大) / 落合 秀樹(横浜国大) |
| 副委員長氏名（英） | Shunichi Azuma(Hokkaido Univ.) / Koji Ishii(Kagawa Univ.) / Junji Shikata(Yokohama National Univ.) / Goichiro Hanaoka(AIST) / Yasuyuki Nogami(Okayama Univ.) / Hiroyasu Ishikawa(Nihon Univ.) / Hideki Ochiai(Yokohama National Univ.) |
| 幹事氏名（和） | 加川 敏規(電中研) / 岡野 訓尚(立命館大) / 松田 隆宏(産総研) / 米山 一樹(茨城大) / 松田 哲直(埼玉大) / 眞田 亜紀子(長岡技科大) / 荒井 剛(岡山県立大) / 木下 雅之(千葉工大) |
| 幹事氏名（英） | Toshinori Kagawa(CRIEPI) / Kunihisa Okano(Ritsumeikan Univ.) / Takahiro Matsuda(AIST) / Kazuki Yoneyama(Ibaraki Univ.) / Tetsunao Matsuta(Saitamai Univ.) / Akiko Manada(Nagaoka Univ. of Tech.) / Tsuyoshi Arai(Okayama Prefectural Univ.) / Masayuki Kinoshita(Chiba Univ. of Tech.) |
| 幹事補佐氏名（和） | 単 麟(NICT) / 足立 亮介(山口大) / 花谷 嘉一(東芝) / 野崎 隆之(山口大) / 孫 冉(茨城大) / 陳 娜(奈良先端大) |
| 幹事補佐氏名（英） | SHAN LIN(NICT) / Ryosuke Adachi(Yamaguchi Univ.) / Yoshikazu Hanatani(Toshiba) / Takayuki Nozaki(Yamaguchi Univ.) / Sun Ran(Ibaraki Univ.) / Chen Na(NAIST) |
| 講演論文情報詳細 | |
| 申込み研究会 | Technical Committee on Reliable Communication and Control / Technical Committee on Information Security / Technical Committee on Information Theory / Technical Committee on Wideband System |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | LZ78符号とそのバリエーションを用いた文法圧縮の構成 |
| サブタイトル（和） | |
| タイトル（英） | Construction of Grammar-Based Codes Using the LZ78 Code and Its Variants |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 情報源符号化 / Source Coding |
| キーワード(2)（和/英） | Lempel-Ziv法 / Lempel-Ziv Method |
| キーワード(3)（和/英） | LZ78法 / LZ78 Method |
| キーワード(4)（和/英） | LZW法 / LZW Method |
| キーワード(5)（和/英） | LZY法 / LZY Method |
| キーワード(6)（和/英） | 文法圧縮法 / Grammar-Based Coding |
| 第 1 著者 氏名（和/英） | 有村 光晴 / Mitsuharu Arimura |
| 第 1 著者 所属（和/英） | 湘南工科大学(略称：湘南工科大) Shonan Institute of Technology(略称：Shonan Inst. Tech.) |
| 発表年月日 | 2023-03-14 |
| 資料番号 | IT2022-103,ISEC2022-82,WBS2022-100,RCC2022-100 |
| 巻番号（vol） | vol.122 |
| 号番号（no） | IT-427,ISEC-428,WBS-429,RCC-430 |
| ページ範囲 | pp.224-229(IT), pp.224-229(ISEC), pp.224-229(WBS), pp.224-229(RCC), |
| ページ数 | 6 |
| 発行日 | 2023-03-07 (IT, ISEC, WBS, RCC) |