Path: csiph.com!v102.xanadu-bbs.net!xanadu-bbs.net!feeder.erje.net!eu.feeder.erje.net!fu-berlin.de!uni-berlin.de!individual.net!not-for-mail From: Hans-Peter Diettrich Newsgroups: comp.compression Subject: Detecting repetitions Date: Sat, 30 Aug 2014 06:13:36 +0200 Lines: 16 Message-ID: Mime-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-15; format=flowed Content-Transfer-Encoding: 7bit X-Trace: individual.net Q4YEH3wn/d2zFjv0pUkp/wMXpPFTEJuH/XLPTQS8ocqPsZhPhV Cancel-Lock: sha1:c07jskqpw8N9Jx7vOaNYGggj2ic= User-Agent: Thunderbird 2.0.0.21 (Windows/20090302) Xref: csiph.com comp.compression:2541 For an special use case I need kind of an RLE encoding. It should catch the smallest repeated sequences (be non-greedy). Runtime efficiency is important, compression not (can leave big blocks uncompressed). And it must work on bit level (2 input symbols only). Eventually a starting point can be provided, from which a backwards search for repetitions can start, and the algorithm then may stop before reaching the very beginning of the data. I'm not familiar with compression algorithms, so all hints are appreciated. For the curious: this is an attempt to compress the output of a Turing machine (Busy Beaver), for further analysis of the behaviour (halting, endless looping...) of such machines. I want to continue the work of Rado et al., but based on my own data structures and basic procedures. DoDi