TMBad::periodic< T > Struct Template Reference

Period analyzer. More...

#include <compression.hpp>

Public Member Functions
period	find_best_period (size_t start)
	Find the best period (highest compression degree) starting from a given index. More...
size_t	numrep_period (size_t start, size_t p)
	Find number period replicates. More...
bool	test_period (size_t start, size_t p)
	Test period one step ahead. More...

Public Attributes
size_t	max_period_size
	Test periods up to this size.
size_t	min_period_rep
	Ignore periods with too small replicator.

Detailed Description

template<class T>
struct TMBad::periodic< T >

Period analyzer.

Finds periodic patterns in sequences, e.g. the operation stack or the operator input sequence. The complexity is linear in the sequence length and in the maximum period size.

Example 1:

Periods with high degree of compression are selected. In the example below the period 1 2 1 2 3 with replicator 3 is preferred over 1 2 with replicator 2.

{1, 2, 1, 2, 3, 1, 2, 1, 2, 3, 1, 2, 1, 2, 3, 1, 1, 1}
begin: 0 size: 5 rep: 3
begin: 15 size: 1 rep: 3

Definition at line 41 of file compression.hpp.

Member Function Documentation

find_best_period()

template<class T>

period TMBad::periodic< T >::find_best_period ( size_t  start )

inline

Find the best period (highest compression degree) starting from a given index.

A period of size p with replicator r reduces the full vector representation p*r to just p, i.e. relative degree of compression is r. Starting form start we thus seek the period with highest replicator. The function tests all periods up to a specified max_period_size. Note that, once a period p with replicator r has been found, it is redundant to test periods shorter than p*r+1.

Definition at line 87 of file compression.hpp.

numrep_period()

template<class T>

size_t TMBad::periodic< T >::numrep_period ( size_t  start, size_t  p  )

inline

Find number period replicates.

Find number of consecutive period replicates starting from a given index start.

Definition at line 68 of file compression.hpp.

test_period()

template<class T>

bool TMBad::periodic< T >::test_period ( size_t  start, size_t  p  )

inline

Test period one step ahead.

Tests if all(x[i]==x[i+p]) where i = start + 0:(p-1).

Definition at line 56 of file compression.hpp.

---

The documentation for this struct was generated from the following file:

• compression.hpp