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

UPPER-BOUNDS ON THE PROBABILITY OF SEQUENCES EMITTED BY FINITE-STATE SOURCES AND ON THE REDUNDANCY OF THE lempel-ziv algorithm

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 1992年第1期38卷 66-72页

作者： PLOTNIK, E WEINBERGER, MJ ziv, J Department of Electrical Engineering Technion-Israel Institute of Technology Haifa Israel

An upper bound on the probability of a sequence drawn from a finite-state source is derived. The bound is given in terms of the number of phrases obtained by parsing the sequence according to the lempel-ziv (L-Z) incremental parsing rule, and is universal in the sense that it does not depend on the statistical parameters that characterize the source. This bound is used to derive an upper bound on the redundancy of the L-Z universal data compression algorithm applied to finite-state sources, that depends on the length N of the sequence, on the number K of states of the source, and, eventually, on the source entropy. A variation of the L-Z algorithm is presented, and an upper bound on its redundancy is derived for finite-state sources. A method to derive tighter implicit upper bounds on the redundancy of both algorithms is also given, and it is shown that for the proposed variation this bound is smaller than for the original L-Z algorithm, or every value of N and K.

关键词： DATA COMPRESSION UNIVERSAL CODING FINITE-STATE SOURCES lempel-ziv algorithm

来源：评论

学校读者我要写书评

暂无评论

EXACT ANALYSIS OF THE lempel-ziv algorithm FOR IID SOURCES

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 1993年第2期39卷 698-702页

作者： KAWABATA, T Department of Communications and Systems University of Electro-Communications Japan

A new analysis shows that, when we apply the lempel-ziv incremental parsing algorithm to an i.i.d., source with probabilities pi, i = 1, . . ., m, the expected length E\W(t)\ of the tth parsed segment W(t) is given by ( t/n ) SIGMA(n = 1)t (-1) n - 1 PI(l = 2)n (1 - SIGMA(i = 1)m p(i)l), with the null product being 1. It is also shown that lim(t --> infinity) E\W(t)\/logt = H(X)-1 for the same source with the entropy H(X). This gives a variable-to-fixed length (VF) scheme version of the ziv-lempel universal coding theorem.

关键词： lempel-ziv algorithm 1ST PASSAGE TIME FUNCTIONAL EQUATION PROBABILITY GENERATING FUNCTION VARIABLE-TO-FIXED LENGTH (VF) SOURCE CODING

来源：评论

学校读者我要写书评

暂无评论

Complexity analysis of precipitation using the lempel-ziv algorithm and a multi-scaling approach: a case study in Jilin province, China

引用

STOCHASTIC ENVIRONMENTAL RESEARCH AND RISK ASSESSMENT 2017年第7期31卷 1697-1707页

作者： Zhang, Qian Liang, Xiujuan Fang, Zhang Xiao, Changlai Jilin Univ Key Lab Groundwater Resources & Environm Minist Educ 2519 Jiefang St Changchun 130021 Jilin Peoples R China

Precipitation is an important part of the hydrologic cycle, and its complexity is closely related to surface runoff and changing groundwater dynamics, which in turn influences the accuracy of precipitation forecasts. In this study, we used the lempel-ziv algorithm (LZA) and a multi-scaling approach to assess precipitation complexity for 1958-2011 by analyzing time series data from 28 gauging stations located throughout Jilin province, China. The spatial distribution of normalized precipitation complexity was measured by LZA, a symbolic dynamics algorithm, and by a multi-scaling approach, which is described by fractals. In addition, the advantages and limitations of these two methods were investigated. The results indicate that both methods are applicable and consistent for calculating precipitation complexity, and that the degree of relief is a primary factor controlling precipitation complexity in the mountainous area;in the plain terrain, however, the prominent influencing factor is climate.

关键词： Complexity lempel-ziv algorithm Multi-scaling approach Precipitation

来源：评论

学校读者我要写书评

暂无评论

On certain pathwise properties of the sliding-window lempel-ziv algorithm

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2006年第12期52卷 5267-5283页

作者： Lastras-Montano, Luis Alfonso IBM Corp Thomas J Watson Res Ctr Yorktown Hts NY 10598 USA

We derive several almost-sure results related to the sliding-window lempel-ziv (SWLZ) algorithm. A principal result is a path-wise lower bound to the redundancy equal to 1/2h log(2) log(2) n(w)/log(2) n(w) in the main term, where n(w) is the sliding window size. This bound is off by a factor of two from the main term in the lower bound of A. J. Wyner and the work of Yang and Kieffer, which hold in the expected sense for the fixed-database lempel-ziv algorithm (FDLZ). Another aspect of the present work studies the asymptotic behavior of the ratio of the number of phrases to the length of the parsed string for any finite sliding Window size;in here we exploit the theory of asymptotic mean stationary processes of Gray and Kieffer and some results of Kieffer and Rahe. In all cases it is assumed that the source is stationary and that in the most restrictive case it is an irreducible and aperiodic Markov chain;some of the results hold for sources that have exponential rates for entropy and more generally for the ergodic setting.

关键词： asymptotic mean stationary ergodic theory lempel-ziv algorithm lossless source coding redundancy

来源：评论

学校读者我要写书评

暂无评论

Simple universal lossy data compression schemes derived from the lempel-ziv algorithm

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 1996年第1期42卷 239-245页

作者： Yang, EH Kieffer, JC UNIV MINNESOTA DEPT ELECT ENGN MINNEAPOLIS MN 55455 USA

Two universal lossy data compression schemes, one with fixed rate and the other with fixed distortion, are presented, based on the well-known lempel-ziv algorithm. In the case of fixed rate R, our universal lossy data compression scheme works as follows: first pick a codebook B-n consisting of all reproduction sequences of length n whose lempel-ziv codeword length is less than or equal to nR, and then use B1 to encode the entire source sequence n-block by n-block. This fixed-rate data compression scheme is universal in the sense that for any stationary, ergodic source or for any individual sequence, the sample distortion performance as n --> infinity is given almost surely by the distortion rate function. A similar result is shown in the context of fixed distortion lossy source coding.

关键词： universal lossy data compression lempel-ziv algorithm stationary sources individual sequences

来源：评论

学校读者我要写书评

暂无评论

Redundancy estimates for the lempel-ziv algorithm of data compression

引用

DISCRETE APPLIED MATHEMATICS 2004年第1-3期135卷 245-254页

作者： Potapov, VN SB RAS Sobolev Inst Math Novosibirsk 630090 Russia

The problem of non-distorting compression (or coding) of sequences of symbols is considered. For sequences of asymptotically zero empirical entropy, a modification of the lempel-ziv coding rule is offered whose coding cost is at most a finite number of times worse than the optimum. A combinatorial proof is offered for the well-known redundancy estimate of the lempel-ziv coding algorithm for sequences having a positive entropy. (C) 2002 Elsevier B.V. All rights reserved.

关键词： data compression lempel-ziv algorithm

来源：评论

学校读者我要写书评

暂无评论

The redundancy and distribution of the phrase lengths of the fixed-database lempel-ziv algorithm

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 1997年第5期43卷 1452-1464页

作者： Wyner, AJ Department of Statistics University of California Berkeley CA USA

The fixed-database version of the lempel-ziv algorithm closely resembles many versions that appear in practice, In this paper, we ascertain several key asymptotic properties of the algorithm as applied to sources with finite memory, First, we determine that for a dictionary of size n, the algorithm achieves a redundancy rho(n) = H log log n/log n + o (log log n/log n) where H is the entropy of the process, This is the first, nontrivial, lower bound on any lempel-ziv-type compression scheme, We then find the limiting distribution and all moments of the lengths of the phrases by comparing them to a random-walk-like variable with well-known behavior.

关键词： data compression lempel-ziv algorithm Stein's method string matching

来源：评论

学校读者我要写书评

暂无评论

On certain pathwise properties of the sliding-window lempel-ziv algorithm

On certain pathwise properties of the sliding-window Lempel-...

引用

IEEE International Symposium on Information Theory

作者： Lastras-Montano, Luis Alfonso IBM Corp Thomas J Watson Res Ctr Yorktown Hts NY 10598 USA

关键词： asymptotic mean stationary ergodic theory lempel-ziv algorithm lossless source coding redundancy

来源：评论

学校读者我要写书评

暂无评论

A note on lempel-ziv-Yokoo algorithm

引用

IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES 1996年第9期E79A卷 1460-1463页

作者： Kiyohara, J Kawabata, T Department of Communications and Systems University of Electro-Communications Chofu-shi 182 Japan

We study lempel-ziv-Yokoo algorithm [1,algorithm 4] for universal data compression. In this paper, we give a simpler implementation of lempel-ziv-Yokoo algorithm than the original one[l,algorithm 4] and show its asymp... 详细信息

关键词： source coding data compression lempel-ziv algorithm asymptotic optimality

来源：评论

学校读者我要写书评

暂无评论

Universal Slepian-Wolf Coding for Individual Sequences

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2025年第1期71卷 783-796页

作者： Merhav, Neri Tech Israel Inst Technol Viterbi Fac ECE IL-3200003 Haifa Israel

We establish a coding theorem and a matching converse theorem for separate encodings and joint decoding of individual sequences using finite-state machines. The achievable rate region is characterized in terms of the lempel-ziv (LZ) complexities, the conditional LZ complexities and the joint LZ complexity of the two source sequences. An important feature that is needed to this end, which may be interesting on its own right, is a certain asymptotic form of a chain rule for LZ complexities, which we establish in this work. The main emphasis in the achievability scheme is on the universal decoder and its properties. We then show that the achievable rate region is universally attainable by a modified version of Draper's universal incremental Slepian-Wolf (SW) coding scheme, provided that there exists a low-rate reliable feedback link.

关键词： Encoding Complexity theory Decoding Entropy Vectors Automata Source coding Hamming distances Viterbi algorithm Urban areas Slepian-Wolf coding lempel-ziv algorithm lempel-ziv complexity finite-state machines universal decoding

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：