Burrows–Wheeler transform: Difference between revisions

Content added Content deleted
m (→‎{{header|REXX}}: changed some comments and whitespace.)
Line 1,437: Line 1,437:
BWT: procedure expose ?.; parse arg y,,$ /*obtain the input; nullify $ string. */
BWT: procedure expose ?.; parse arg y,,$ /*obtain the input; nullify $ string. */
?.1= 'fd'x; ?.2= "fc"x /*assign the STX and ETX strings. */
?.1= 'fd'x; ?.2= "fc"x /*assign the STX and ETX strings. */
do i=1 for 2 /* [↓] check for invalid input string.*/
do i=1 for 2 /* [↓] check for invalid input string.*/
_= verify(y, ?.i, 'M'); if _==0 then iterate; er= '***error*** BWT: '
_= verify(y, ?.i, 'M'); if _==0 then iterate; er= '***error*** BWT: '
say er "invalid input: " y
say er "invalid input: " y
say er 'The input string contains an invalid character at position' _"."; exit 13
say er 'The input string contains an invalid character at position' _"."; exit _
end /*i*/ /* [↑] if error, perform a hard exit.*/
end /*i*/ /* [↑] if error, perform a hard exit.*/
y= ?.1 || y || ?.2 /*obtain the input; add a fence to it.*/
y= ?.1 || y || ?.2; L= length(y) /*get the input & add a fence; gel len.*/
L= length(y); m= L-1 /*get the length of new text; get L-1.*/
@.1= y; m= L - 1 /*define the first element of the table*/
@.1= y /*define the first element of the table*/
do j=2 for m; _= j-1 /*now, define the rest of the elements.*/
do j=2 for m; _= j-1 /*now, define the rest of the elements.*/
@.j= right(@._,1)left(@._,m) /*construct a table from the Y input.*/
@.j= right(@._,1)left(@._,m) /*construct a table from the Y input.*/
end /*j*/ /* [↑] each element: left & right part*/
end /*j*/ /* [↑] each element: left & right part*/
call cSort L /*invoke lexicographical sort for array*/
call cSort L /*invoke lexicographical sort for array*/
do k=1 for L /* [↓] construct the answer from array*/
do k=1 for L /* [↓] construct the answer from array*/
$=$ || right(@.k, 1) /*build the answer from each of ··· */
$= $ || right(@.k, 1) /*build the answer from each of ··· */
end /*k*/ /* ··· the array's right─most character*/
end /*k*/ /* ··· the array's right─most character*/
return $ /*return the constructed answer. */
return $ /*return the constructed answer. */