Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.compression > #2541 > unrolled thread

Detecting repetitions

Back to article view | Back to comp.compression

Contents

  Detecting repetitions Hans-Peter Diettrich <DrDiettrich1@aol.com> - 2014-08-30 06:13 +0200
    Re: Detecting repetitions Hans-Peter Diettrich <DrDiettrich1@aol.com> - 2014-08-30 22:26 +0200
    Re: Detecting repetitions James Dow Allen <gmail@jamesdowallen.nospam> - 2014-08-31 03:29 +0000
      Re: Detecting repetitions Hans-Peter Diettrich <DrDiettrich1@aol.com> - 2014-08-31 09:57 +0200
    Re: Detecting repetitions glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2014-08-31 06:08 +0000
      Re: Detecting repetitions Hans-Peter Diettrich <DrDiettrich1@aol.com> - 2014-08-31 12:07 +0200
    Re: Detecting repetitions "Skybuck Flying" <skybuck2000@hotmail.com> - 2014-09-09 08:00 +0200

#2541 — Detecting repetitions

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

[toc] | [next] | [standalone]

#2542

Some more notes:

Given is an array of symbols (here: bits = boolean values).
Needed is a list of RLE blocks (pattern, repeatcount), nothing else.

The detected patterns should not contain repetitions, i.e. '110110' 
should result in pattern '110'. Some greedyness is required, of course, 
so that the pattern '110' is not separated again into 2*'1' and 1*'0'.

It can be assumed that the data contain (possibly large) repetitions of 
short patterns. If not, the data can be assumed as uncompressable - if 
that helps to increase analysis speed.

Preceding work assumes a fixed pattern size, e.g. 3 bits, throughout the 
whole input. I want to find out whether a variable (dynamic, 
adaptive...) pattern size will yield better results.

The blocks are assumed to be created by a loop in the automaton, 
replicating a pattern possibly very often before leaving that loop. 
That's why RLE seems to be the best choice for further processing.

The existence of such a loop can be detected in various ways (subject to 
current research), and when a loop is detected, the width of the block 
or contained pattern can be estimated either from the created output (by 
RLE analysis), or by performing another iteration of the loop and 
watching how far the automaton's head position has changed. This may 
allow for a direct determination of the RLE pattern, without further 
inspection of the output, but until then I want to know how to split 
given data into RLE blocks.

DoDi

[toc] | [prev] | [next] | [standalone]

#2544

Maybe I'm missing something basic about your requirements but, ignoring 
"edge cases" etc. a very simple algorithm would seem to work fine.

Step 1) Pass several bits as is, where "several" is set high enough to 
allay your concern about speed.

Step 2) Examine the most recent 2K bits for replication, where K is the 
largest permitted pattern. If no sufficiently long replicated pattern is 
found, goto Step1; otherwise, an M-length duplicated pattern is found, 
so goto Step3.

Step3) Look backwards through the already-passed bits to extend the 
replication if possible.

Step 4) Keep grabbing M bits, incrementing the replication count.  When 
replication fails, goto Step 1.

I think this pattern-matching will be the least of your worries, both 
for speed and for complexity.  Unless K > 11 or so, you can make Step 2 
run lickety-split with a 2^2K sized table of precomputed answers.

James Dow Allen

[toc] | [prev] | [next] | [standalone]

#2546

James Dow Allen schrieb:

> I think this pattern-matching will be the least of your worries, both 
> for speed and for complexity.  Unless K > 11 or so, you can make Step 2 
> run lickety-split with a 2^2K sized table of precomputed answers.

Hmm, a lookup table may be a good idea :-)

Provided that I organize my tape in bytes (8 bit/byte) instead of single 
boolean bytes (1 bit/byte), a list of shifted patterns will allow to 
scan huge portions for the end of the repetition. OTOH this approach 
will slow down in reading/writing single symbols (bits), so that I have 
to find the best overall solution...

DoDi

[toc] | [prev] | [next] | [standalone]

#2545

Hans-Peter Diettrich <DrDiettrich1@aol.com> wrote:

> 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.

How about Burrows-Wheeler transform based compression?

BWT is good at finding repetitions.

-- glen

[toc] | [prev] | [next] | [standalone]

#2547

glen herrmannsfeldt schrieb:

> How about Burrows-Wheeler transform based compression?

Sorting a portion of the data may reveal repetition candidates. Worth 
another thought...

DoDi

[toc] | [prev] | [next] | [standalone]

#2561

A bit whacky ;) (has hardly to do with compression but ok...)

Not sure if all data is available or if it's "coming in".

Anyway here is a simple idea:

1. Perform RLE as normal, then simple search for "smallest" length :)

Bye,
  Skybuck.

[toc] | [prev] | [standalone]

Back to top | Article view | comp.compression

csiph-web