检索结果-内蒙古大学图书馆

Multidimensional incremental parsing for universal source coding

IEEE TRANSACTIONS ON IMAGE PROCESSING 2008年第10期17卷 1837-1848页

作者： Bae, Soo Hyun Juang, Biing-Hwang Georgia Inst Technol Sch Elect & Comp Engn Ctr Signal & Image Proc Atlanta GA 30332 USA

A multidimensional incremental parsing algorithm (MDIP) for multidimensional discrete sources, as a generalization of the Lempel-Ziv coding algorithm, is investigated. It consists of three essential component schemes, maximum decimation matching, hierarchical structure of multidimensional source coding, and dictionary augmentation. As a counterpart of the longest match search in the Lempel-Ziv algorithm, two classes of maximum decimation matching are studied. Also, an underlying behavior of the dictionary augmentation scheme for estimating the source statistics is examined. For an m-dimensional source, m augmentative patches are appended into the dictionary at each coding epoch, thus requiring the transmission of a substantial amount of information to the decoder. The property of the hierarchical structure of the source coding algorithm resolves this issue by successively incorporating lower dimensional coding procedures in the scheme. In regard to universal lossy source coders, we propose two distortion functions, the local average distortion and the local minimax distortion with a set of threshold levels for each source symbol. For performance evaluation, we implemented three image compression algorithms based upon the MDIP;one is lossless and the others are lossy. The lossless image compression algorithm does not perform better than the Lempel-Ziv-Welch coding, but experimentally shows efficiency in capturing the source structure. The two lossy image compression algorithms are implemented using the two distortion functions, respectively. The algorithm based on the local average distortion is efficient at minimizing the signal distortion, but the images by the one with the local minimax distortion have a good perceptual fidelity among other compression algorithms. Our insights inspire future research on feature extraction of multidimensional discrete sources.

关键词： image compression incremental parsing Lempel-Ziv pattern matching universal source coding

来源：评论

学校读者我要写书评

暂无评论

A Parallel Two-Pass MDL Context Tree Algorithm for universal source coding

A Parallel Two-Pass MDL Context Tree Algorithm for Universal...

引用

IEEE International Symposium on Information Theory (ISIT)

作者： Krishnan, Nikhil Baron, Dror Mihcak, Mehmet Kivanc N Carolina State Univ Dept Elect & Comp Engn Raleigh NC 27695 USA

ISBN: (纸本)9781479951864

We present a novel lossless universal source coding algorithm that uses parallel computational units to increase the throughput. The length-N input sequence is partitioned into B blocks. Processing each block independently of the other blocks can accelerate the computation by a factor of B, but degrades the compression quality. Instead, our approach is to first estimate the minimum description length (MDL) source underlying the entire input, and then encode each of the B blocks in parallel based on the MDL source. With this two-pass approach, the compression loss incurred by using more parallel units is insignificant. Our algorithm is work-efficient, i.e., its computational complexity is O(N/B). Its redundancy is approximately B log(N/B) bits above Rissanen's lower bound on universal coding performance, with respect to any tree source whose maximal depth is at most log(N/B).

关键词： computational complexity data compression MDL parallel algorithms redundancy universal source coding work efficient algorithms

来源：评论

学校读者我要写书评

暂无评论

FIXED-RATE universal LOSSY source-coding AND RATES OF CONVERGENCE FOR MEMORYLESS sourceS

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 1995年第3期41卷 665-676页

作者： LINDER, T LUGOSI, G ZEGER, K TECH UNIV BUDAPEST FAC ELECT ENGN DEPT MATH BUDAPEST HUNGARY UNIV ILLINOIS DEPT ELECT & COMP ENGN COORDINATED SCI LAB URBANA IL 61801 USA

A fixed-rate universal lossy coding scheme is introduced for independent and identically distributed (i.i.d.) sources, It is shown for finite alphabet sources and arbitrary single letter distortion measures that as the sample size n grows the expected distortion obtained using this universal scheme converges to Shannon's distortion rate function D(R) at a rate O (log n/n). The scheme can be extended to universal quantization of real i.i.d sources subject to a squared error criterion, It is shown in this case that the per-letter distortion converges to D(R) at a rate O(root log n/n) both in expectation and almost surely for any real-valued bounded i.i.d. source.

关键词： universal source coding CONVERGENCE RATES VECTOR QUANTIZATION

来源：评论

学校读者我要写书评

暂无评论

universal Tree source coding Using Grammar-Based Compression

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2019年第10期65卷 6399-6413页

作者： Ganardi, Moses Hucke, Danny Lohrey, Markus Benkner, Louisa Seelbach Univ Siegen Dept Elect Engn & Comp Sci D-57076 Siegen Germany

The problem of universal source coding for binary trees is considered. Zhang, Yang, and Kieffer derived upper bounds on the average-case redundancy of codes based on directed acyclic graph (DAG) compression for binary tree sources with certain properties. In this paper, a natural class of binary tree sources is presented such that the demanded properties are fulfilled. Moreover, for both subclasses considered in the paper of Zhang, Yang, and Kieffer, their result is improved by deriving bounds on the maximal pointwise redundancy (or worst-case redundancy) instead of the average-case redundancy. Finally, using context-free tree grammars instead of DAGs, upper bounds on the maximal pointwise redundancy for certain binary tree sources are derived. This yields universal codes for new classes of binary tree sources.

关键词： Grammar-based compression minimal DAG representation binary trees universal source coding lossless compression

来源：评论

学校读者我要写书评

暂无评论

universal Tree source coding Using Grammar-Based Compression

Universal Tree Source Coding Using Grammar-Based Compression

引用

IEEE International Symposium on Information Theory (ISIT)

作者： Ganardi, Moses Hucke, Danny Lohrey, Markus Benkner, Louisa Seelbach Univ Siegen Dept Elect Engn & Comp Sci D-57076 Siegen Germany

关键词： Grammar-based compression minimal DAG representation binary trees universal source coding lossless compression

来源：评论

学校读者我要写书评

暂无评论

universal and succinct source coding of deep neural networks

Universal and succinct source coding of deep neural networks

引用

作者： Basu, Sourya University of Illinois – Urbana-Champaign

学位级别：硕士

Deep neural networks have shown incredible performance for inference tasks in a variety of domains. Unfortunately, most current deep networks are enormous cloud-based structures that require significant storage space, which limits scaling of deep learning as a service (DLaaS) and use for on-device intelligence. This work is concerned with finding universal lossless compressed representations of deep feedforward networks with synaptic weights drawn from discrete sets, and directly performing inference without full decompression. The basic insight that allows less rate than naive approaches is recognizing that the bipartite graph layers of feedforward networks have a kind of permutation invariance to the labeling of nodes, in terms of inferential operation. We provide efficient algorithms to dissipate this irrelevant uncertainty and then use arithmetic coding to nearly achieve the entropy bound in a universal manner. We also provide experimental results of our approach on several standard datasets.

关键词： Deep neural networks universal source coding

来源：评论

学校读者我要写书评

暂无评论

A universal Two-Dimensional source coding by Means of Subblock Enumeration

引用

IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES 2019年第2期E102A卷 440-449页

作者： Ota, Takahiro Morita, Hiroyoshi Manada, Akiko Nagano Prefectural Inst Technol Dept Comp & Syst Engn Ueda Nagano 3861211 Japan Univ Electrocommun Grad Sch Informat & Engn Dept Comp & Network Engn Chofu Tokyo 1828585 Japan Shonan Inst Technol Dept Informat Sci Fujisawa Kanagawa 2510046 Japan

The technique of lossless compression via substring enumeration (CSE) is a kind of enumerative code and uses a probabilistic model built from the circular string of an input source for encoding a one-dimensional (1D) source. CSE is applicable to two-dimensional (2D) sources, such as images, by dealing with a line of pixels of a 2D source as a symbol of an extended alphabet. At the initial step of CSE encoding process, we need to output the number of occurrences of all symbols of the extended alphabet, so that the time complexity increases exponentially when the size of source becomes large. To reduce computational time, we can rearrange pixels of a 2D source into a 1D source string along a space-filling curve like a Hilbert curve. However, information on adjacent cells in a 2D source may be lost in the conversion. To reduce the time complexity and compress a 2D source without converting to a 1D source, we propose a new CSE which can encode a 2D source in a block-by-block fashion instead of in a line-by-line fashion. The proposed algorithm uses the flat torus of an input 2D source as a probabilistic model instead of the circular string of the source. Moreover, we prove the asymptotic optimality of the proposed algorithm for 2D general sources.

关键词： compression via substring enumeration enumerative code universal source coding two-dimensional general source

来源：评论

学校读者我要写书评

暂无评论

universal Weak Variable-Length source coding on Countably Infinite Alphabets

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2020年第1期66卷 649-668页

作者： Silva, Jorge F. Piantanida, Pablo Univ Chile Informat & Decis Syst IDS Grp Santiago 4123 Chile Univ Paris Sud CNRS Cent Supelec L2S F-91190 Gif Sur Yvette France Univ Montreal Mila Montreal PQ H3T 1J4 Canada

Motivated from the fact that universal source coding on countably infinite alphabets (infinity-alphabets) is not feasible, this work introduces the notion of "almost lossless source coding". Analog to the weak variable-length source coding problem studied by Han (IEEE Trans. Inf. Theory, vol. 46, no. 4, pp. 1217-1226, Jul. 2000), almost lossless source coding aims at relaxing the lossless block-wise assumption to allow an average per-letter distortion that vanishes asymptotically as the block-length tends to infinity. In this setup, we show on one hand that Shannon entropy characterizes the minimum achievable rate (similarly to the case of finite alphabet sources) while on the other that almost lossless universal source coding becomes feasible for the family of finite-entropy stationary memoryless sources with infinity-alphabets. Furthermore, we study a stronger notion of almost lossless universality that demands uniform convergence of the average per-letter distortion to zero, where we establish a necessary and sufficient condition for the so-called family of "envelope distributions" to achieve it. Remarkably, this condition is the same necessary and sufficient condition needed for the existence of a strongly minimax (lossless) universal source code for the family of envelope distributions. Finally, we show that an almost lossless coding scheme offers faster rate of convergence for the (minimax) redundancy compared to the well-known information radius developed for the lossless case at the expense of tolerating a non-zero distortion that vanishes to zero as the block-length grows. This shows that even when lossless universality is feasible, an almost lossless scheme can offer different regimes on the rates of convergence of the (worst case) redundancy versus the (worst case) distortion.

关键词： universal source coding countably infinite alphabets (infinity-alphabets) weak source coding envelope distributions information radius (i-radius) metric entropy analysis

来源：评论

学校读者我要写书评

暂无评论

Asymptotics and Non-Asymptotics for universal Fixed-to-Variable source coding

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2017年第6期63卷 3757-3772页

作者： Kosut, Oliver Sankar, Lalitha Arizona State Univ Sch Elect Comp & Energy Engn Tempe AZ 85287 USA

universal fixed-to-variable lossless source coding for memoryless sources is studied in the finite blocklength and higher order asymptotic regimes. Optimal three-term fixed-error asymptotic expressions are derived for general fixed-to-variable codes and for prefix codes. It is shown that the non-prefix Type Size code, in which codeword lengths are chosen in ascending order of type class size, achieves the optimal third-order term, and outperforms classical two-stage codes. Converse results are proved making use of a result on the distribution of the empirical entropy and Laplace's approximation. Finally, the fixed-to-variable coding problem without a prefix constraint is shown to be essentially the same as the universal guessing problem.

关键词： Data compression universal source coding finite blocklength

来源：评论

学校读者我要写书评

暂无评论

Asymptotics and Non-Asymptotics for universal Fixed-to-Variable source coding

Asymptotics and Non-Asymptotics for Universal Fixed-to-Varia...

引用

IEEE International Symposium on Information Theory (ISIT)

作者： Kosut, Oliver Sankar, Lalitha Arizona State Univ Sch Elect Comp & Energy Engn Tempe AZ 85287 USA

关键词： Data compression universal source coding finite blocklength

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：