

 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

 
#!/bin/ksh
 
# Burrows–Wheeler transform
 
#	# Variables:
#
export LC_COLLATE=POSIX
 
STX=\^		# start marker
ETX=\|		# end marker
 
typeset -a str
str[0]='BANANA'
str[1]='appellee'
str[2]='dogwood'
str[3]='TO BE OR NOT TO BE OR WANT TO BE OR NOT?'
str[4]='SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES'
str[5]='|ABC^'
 
#	# Functions:
#
 
#	# Function _bwt(str, arr, lc) - sort all circular shifts of arr, return last col
#
function _bwt {
	typeset _str ; _str="$1"
	typeset _arr ; nameref _arr="$2"
	typeset _lastcol ; nameref _lastcol="$3"
	typeset _i _j _newstr ; integer _i _j
 
	[[ ${_str} == *+("$STX"|"$ETX")* ]] && return 1
 
	_str="$STX${_str}$ETX"
	for ((_i=0; _i<${#_str}; _i++)); do
		_newstr=${_str:${#_str}-1:1}
		for ((_j=0; _j<${#_str}-1; _j++)); do
			_newstr+=${_str:${_j}:1}
		done
		_arr+=( "${_newstr}" )
		_str="${_newstr}"
	done
 
	set -sA arr		# Sort arr
 
	for ((_i=0; _i<${#_arr[*]}; _i++)); do
		_lastcol+=${_arr[_i]:${#_arr[_i]}-1:1}
	done
}
 
#	# Function _ibwt(str) - inverse bwt
#
function _ibwt {
	typeset _str ; _str="$1"
	typeset _arr _vec _ret _i ; typeset -a _arr _vec ; integer _i
 
	_intovec "${_str}" _vec
	for ((_i=1; _i<${#_str}; _i++)); do
		_intoarr _vec _arr
		set -sA _arr
	done
 
	for ((_i=0; _i<${#arr[*]}; _i++)); do
		[[ "${arr[_i]}" == ${STX}*${ETX} ]] && echo "${arr[_i]}" && return
	done
}
 
#	# Function _intovec(str, vec) - trans str into vec[]
#
function _intovec {
	typeset _str ; _str="$1"
	typeset _vec ; nameref _vec="$2"
	typeset _i ; integer _i
 
	for ((_i=0; _i<${#_str}; _i++)); do
		_vec+=( "${_str:${_i}:1}" )
	done
}
 
#	# Function _intoarr(i, vec, arr) - insert vec into arr
#
function _intoarr {
	typeset _vec ; nameref _vec="$1"
	typeset _arr ; nameref _arr="$2"
	typeset _j ; integer _j
 
	for ((_j=0; _j<${#_vec[*]}; _j++)); do
		_arr="${_vec[_j]}${_arr[_j]}"
	done
}
 
 ######
# main #
 ######
 
for ((i=0; i<${#str[*]}; i++)); do
	unset arr lastcol result ; typeset -a arr
 
	print -- "${str[i]}"
	_bwt "${str[i]}" arr lastcol
	(( $? )) && print "ERROR: string cannot contain $STX or $ETX" && continue
 
	print -- "${lastcol}"
	result=$(_ibwt "${lastcol}")
	print -- "${result}"
	echo
done
 