首页> 外文OA文献 >Lempel-Ziv Compression in a Sliding Window
【2h】

Lempel-Ziv Compression in a Sliding Window

机译:Lempel-Ziv压缩在滑动窗口

代理获取
本网站仅为用户提供外文OA文献查询和代理获取服务,本网站没有原文。下单后我们将采用程序或人工为您竭诚获取高质量的原文,但由于OA文献来源多样且变更频繁,仍可能出现获取不到、文献不完整或与标题不符等情况,如果获取不到我们将提供退款服务。请知悉。

摘要

We present new algorithms for the sliding window Lempel-Ziv (LZ77) problem and the approximate rightmost LZ77 parsing problem. Our main result is a new and surprisingly simple algorithm that computes the sliding window LZ77 parse in O(w) space and either O(n) expected time or O(n log log w + z log logσ) deterministic time. Here, w is the window size, n is the size of the input string, z is the number of phrases in the parse, and σ is the size of the alphabet. This matches the space and time bounds of previous results while removing constant size restrictions on the alphabet size. To achieve our result, we combine a simple modification and augmentation of the suffix tree with periodicity properties of sliding windows. We also apply this new technique to obtain an algorithm for the approximate rightmost LZ77 problem that uses O(n(log z + loglogn)) time and O(n) space and produces a (1 + ϵ)-approximation of the rightmost parsing (any constant ϵ 0). While this does not improve the best known time-space trade-offs for exact rightmost parsing, our algorithm is significantly simpler and exposes a direct connection between sliding window parsing and the approximate rightmost matching problem.
机译:我们为滑动窗口Lempel-Ziv(LZ77)问题和近似最右边的LZ77解析问题提出了新算法。我们的主要结果是一种新的且出乎意料的简单算法,该算法计算O(w)空间中的滑动窗口LZ77解析以及O(n)预期时间或O(n log log w + z loglogσ)确定时间。这里,w是窗口大小,n是输入字符串的大小,z是解析中短语的数量,而σ是字母的大小。这与先前结果的空间和时间范围匹配,同时消除了对字母大小的恒定大小限制。为了获得我们的结果,我们将后缀树的简单修改和扩充与滑动窗口的周期性属性相结合。我们还应用这项新技术来获得近似最右LZ77问题的算法,该算法使用O(n(log z + loglogn))时间和O(n)空间并产生最右解析(1 + ϵ)逼近(任何常数ϵ> 0)。虽然这并不能改善最精确的最右边解析的最著名的时空折衷,但是我们的算法明显更简单,并且公开了滑动窗口解析和最右边的近似匹配问题之间的直接联系。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利

客服邮箱:kefu@zhangqiaokeyan.com

京公网安备:11010802029741号 ICP备案号:京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有
  • 客服微信

  • 服务号