Module: TraceVisualization

Defined in:

lib/trace_visualization/bwt.rb,
lib/trace_visualization.rb,
lib/trace_visualization/utils.rb,
lib/trace_visualization/mapping.rb,
lib/trace_visualization/reorder.rb,
lib/trace_visualization/version.rb,
lib/trace_visualization/generators.rb,
lib/trace_visualization/repetitions.rb,
lib/trace_visualization/suffix_array.rb,
lib/trace_visualization/data/repetition.rb,
lib/trace_visualization/repetitions_psy.rb,
lib/trace_visualization/repetitions_context.rb,
lib/trace_visualization/longest_common_prefix.rb,
lib/trace_visualization/repetitions_concatenation.rb,
lib/trace_visualization/repetitions_incrementation.rb

Overview

The Burrows–Wheeler transform (BWT, also called block-sorting compression), is an algorithm used in data compression techniques such as bzip2. When a character string is transformed by the BWT, none of its characters change value. The transformation permutes the order of the characters. If the original string had several substrings that occurred often, then the transformed string will have several places where a single character is repeated multiple times in a row. This is useful for compression, since it tends to be easy to compress a string that has runs of repeated characters by techniques such as move-to-front transform and run-length encoding.

The transform is done by sorting all rotations of the text in lexicographic order, then taking the last column. For example, the text “^BANANA|” is transformed into “BNN^AA|A”.

Defined Under Namespace

Modules: BurrowsWheelerTransform, Data, Generators, LongestCommonPrefix, Mapping, Reorder, Repetitions, RepetitionsConcatenation, RepetitionsIncrementation, SuffixArray, Utils

Constant Summary

TERMINATION_CHAR =

Should be ‘greater’ of all possible chars in the lexicographical order

'$'

FORBIDDEN_CHARS =

/\n/

VERSION =

"0.0.1"