Although the Block Sorting compression scheme~\cite{BurWhe94} has
excellent performance and speed, its optimality was not analyzed
theoretically. The context sorting~\cite{Yokoo96} may be regarded as
an on-line version of the Block Sorting. Because it is asymptotically
optimal for any finite-order Markov source, the Block Sorting is also
asymptotically optimal if we encode consecutive $l$ symbols at a time
and if $l$ tends to infinity.
The Block Sorting uses the Burrows-Wheeler transformation (BWT) which
permutes an input string. The permutation is defined by lexicographic
order of contexts of symbols.
If we assume that
%the string is generated by a $k$-th order Markov source, that is,
symbol probability is defined by preceding $k$ symbols called context,
symbols whose contexts are the same are collected in consecutive
regions after the BWT.
%
Sadakane~\cite{Sada97c} proposed a variant of the Block Sorting
and it is asymptotically optimal for any finite-order Markov source
if permutation of symbols whose contexts are the same is random.
However, the variant encodes $l$ symbols as a block
and therefore it is not practical
%because of compression speed and required memory.
because $l$ is large.
%Consequently it is necessary to develop practical compression schemes.
%and analyze their compression ratio.
We propose two compression schemes
not using blocks but encoding symbols one by one
by using arithmetic codes.
The move-to-front transformation is not used.
The former encodes symbols by different codes defined by
symbol frequencies in contexts. It is asymptotically optimal for
$k$-th order Markov sources. However, it is available only
if the order $k$ of the source is already known.
%
The latter divides the permuted string into many parts and encodes
symbols using different arithmetic codes by the parts. Each part has
symbols whose contexts are the same. If the permutation is random, the
scheme is asymptotically optimal for any finite-order Markov source.
%As a result, we obtain a guide to design compression schemes which are
%easily implemented and theoretically have good performances.
The permutation in the BWT is not completely random.
For example, if three or more contexts are the same and they overlap
each other, symbols following them appear in the permuted string
in original order or its reversal. However, we conjecture that
the permuted string is memoryless and our schemes work.