

 This page uses content from Wikipedia. The original article was at Burrows–Wheeler_transform. The list of authors can be seen in the page history. As with Rosetta Code, the text of Wikipedia is available under the GNU FDL. (See links for details on variance)



The Burrows–Wheeler transform (BWT, also called block-sorting compression) rearranges a character string into runs of similar characters.

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.

More importantly, the transformation is reversible, without needing to store any additional data.

The BWT is thus a "free" method of improving the efficiency of text compression algorithms, costing only some extra computation.



Source: Burrows–Wheeler transform

import algorithm
from sequtils import repeat
import strutils except repeat
 
const
  Stx = '\2'
  Etx = '\3'
 
#---------------------------------------------------------------------------------------------------
 
func bwTransform*(s: string): string =
  ## Apply Burrows–Wheeler transform to input string.
 
  doAssert(Stx notin s and Etx notin s, "Input string cannot contain STX and ETX characters")
 
  let s = Stx & s & Etx  # Add start and end of text marker.
 
  # Build the table of rotated strings and sort it.
  var table = newSeqOfCap[string](s.len)
  for i in 0..s.high:
    table.add(s[i + 1..^1] & s[0..i])
  table.sort()
 
  # Extract last column of the table.
  for item in table:
    result.add(item[^1])
 
#---------------------------------------------------------------------------------------------------
 
func invBwTransform*(r: string): string =
  ## Apply inverse Burrows–Wheeler transform.
 
  # Build table.
  var table = repeat("", r.len)
  for _ in 1..r.len:
    for i in 0..<r.len:
      table[i] = r[i] & table[i]
    table.sort()
 
  # Find the correct row (ending in ETX).
  var idx = 0
  while not table[idx].endsWith(Etx):
    inc idx
  result = table[idx][1..^2]
 
 
#———————————————————————————————————————————————————————————————————————————————————————————————————
 
when isMainModule:
 
  proc displaybleString(s: string): string =
    ## Build a displayable string from a string containing STX and ETX characters.
 
    s.multiReplace(("\2", "¹"), ("\3", "²"))
 
  for text in ["banana",
               "appellee",
               "dogwood",
               "TO BE OR NOT TO BE OR WANT TO BE OR NOT?",
               "SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES"]:
    let transformed = text.bwTransform()
    let invTransformed = transformed.invBwTransform()
 
    echo ""
    echo "Original text:                ", text
    echo "After transformation:         ", transformed.displaybleString()
    echo "After inverse transformation: ", invTransformed