On an Application of Relative Entropy
We show that in problems of authorship attribution and other linguistic applications, a Markov Chains approach is a more attractive technique than Lempel-Ziv based compression.
cmc.tex
% Group addresses by affiliation; use superscriptaddress for long
% author lists, or if there are many overlapping affiliations.
% For Phys. Rev. appearance, change preprint to twocolumn.
% Choose pra, prb, prc, prd, pre, prl, prstab, or rmp for journal
%  Add 'draft' option to mark overfull boxes with black boxes
%  Add 'showpacs' option to make PACS codes appear
%  Add 'showkeys' option to make keywords appear
\documentclass[aps,prl,twocolumn,showpacs,superscriptaddress]{revtex4}
%\documentclass[aps,prl,preprint,superscriptaddress]{revtex4}
%\documentclass[aps,prl,twocolumn,groupedaddress]{revtex4}

% You should use BibTeX and apsrev.bst for references
% Choosing a journal automatically selects the correct APS
% BibTeX style file (bst file), so only uncomment the line
% below if necessary.
%\bibliographystyle{apsrev}

\begin{document}

% Use the \preprint command to place your local institutional report
% number in the upper righthand corner of the title page in preprint mode.
% Multiple \preprint commands are allowed.
% Use the 'preprintnumbers' class option to override journal defaults
% to display numbers if necessary
%\preprint{}

%Title of paper
\title{On an Application of Relative Entropy}

% repeat the \author .. \affiliation  etc. as needed
% \email, \thanks, \homepage, \altaffiliation all apply to the current
% author. Explanatory text should go in the []'s, actual e-mail
% address or url should go in the {}'s for \email and \homepage.
% Please use the appropriate macro foreach each type of information

% \affiliation command applies to all authors since the last
% \affiliation command. The \affiliation command should follow the
% other information
% \affiliation can be followed by \email, \homepage, \thanks as well.
\author{Dmitry V. Khmelev}
\email{D.Khmelev@newton.cam.ac.uk}
%\homepage[]{Your web page}
%\thanks{}
\affiliation{Isaac Newton Institute for Mathematical Sciences, 20
  Clarkson Rd, Cambridge, CB3 0EH, U.K.}  
\affiliation{Heriot-Watt
  University, Edinburgh, U.K. and Moscow State University, Russia}

\author{William J. Teahan}
\email{wjt@informatics.bangor.ac.uk}
%\homepage[]{Your web page}
%\thanks{}
\affiliation{University of Wales, Bangor, Dean Street, Bangor, LL57 1UT, U.K.}

\date{\today}

\begin{abstract}
  We show that in problems of authorship attribution and other
  linguistic applications, a Markov Chains approach is a more attractive
  technique than Lempel-Ziv based compression.
\end{abstract}

% insert suggested PACS numbers in braces on next line
\pacs{89.70.+c, 01.20.+x, 05.20.-y, 05.45.Tp}
% insert suggested keywords - APS authors don't need to do this
%\keywords{}

%\maketitle must follow title, authors, abstract, \pacs, and \keywords
\maketitle

We wish to point out a number of inaccurate and misleading statements
that Benedetto {\em et al.} make in their paper titled ``Language
Trees and Zipping''\cite{Bene:2002}. First, they claim the technique
they used for construction of a language tree does not make use of any
a-priori information about the alphabet, but it does, both in the
alphabet chosen (Unicode) and in the set of languages they chose to
experiment with; second, they propound Lempel-Ziv (LZ, {\em gzip})
compression as being applicable to DNA analysis, where the usefulness
of LZ is quite doubtful; third, in practice their definition of
relative entropy and distance can yield negative values; fourth, the
classification performance of the method they use is significantly
worse than other entropy-based methods as has been noted in prior
work; and fifth, the classification speed is significantly worse as
well, which shows that its ``potentiality'' is questionable. We
elaborate on each of these points in more detail in the subsequent
paragraphs.

Notice that the ``Language Tree''(LT) diagram~\cite{Bene:2002} does not
include the Russian language (Slavic family of Indo-European family of
languages; 288 million speakers). Our computations show that once
Russian is included, it does not cluster with the other members of
the Slavic group. Obviously, certain Cyrillic alphabet based languages
were left out of the study~\cite{Bene:2002}, which ``improves''
results significantly and shows that a-priori information about
the alphabet is being taken advantage of to achieve the results outlined in
paper~\cite{Bene:2002}.

The LZ compressor makes few assumptions about the input string, but in
practice, we do have a-priori information that we can take advantage
of. Biologists widely use an amino acid {\em substitution matrix} (PAM250
or BLOSUM62) in search for {\em similar} biological
sequences~\cite{gusfield}. It is not at all clear how a substitution
matrix could be implemented with the LZ algorithm.  That is why
compression is not widely used for DNA analysis, although first trials
for its application go back to 1990~\cite{gusfield}.

The quantity $S_{\mathcal A\mathcal B}$~\cite{Bene:2002} defined as
``relative entropy'' in (1) and redefined as ``distance'' in (2) can
take negative values. Negative values indeed appeared in our study
which showed that the ``LT''\cite{Bene:2002} reflects
significantly the structure of Unicode or vice versa, and its
relevance to language classification should be supported additionally.

A traditional definition and estimates for (relative) entropy via $n$th
order Markov Chain {\em on letters}~\cite{Shannon,Yaglom,Kukush:2001}
always lead to a proper positive number. Markov Chains are also
traditional in text entropy analysis~\cite{Shannon,Yaglom},
compression~\cite{PPM}, authorship and subject
attribution~\cite{Teahan:2000,Khmelev:2000}.  In~\cite{Kukush:2001},
the classification performance of compression programs was compared
with the Markov Chain approach~\cite{Khmelev:2000}. 82 authors of
large enough texts ($\ge 10^5$ characters) were chosen. Afterwards 82
one-per-author texts were held out and used for control purposes.  The
classification algorithm~\cite{Kukush:2001} had to
determine the author of each control text among 82 alternatives. The
corresponding numbers of exact guesses for 15 compression programs and
Markov Chains are presented in the following list~\cite{Kukush:2001}:

Program(number of guesses): 7zip(39), arj(46), bsa(44), compress(12), dmc(36),
gzip(50), ha(47), huff(10), lzari(17), ppmd5(46), rar(58), rarw({\bf
  71}), rk(52); Markov Chain approach (see~\cite{Khmelev:2000}) {\bf
  69} guesses.

%\begin{center}
%  \footnotesize
%  \begin{tabular}{lcccccccc}
%    %\hline
%    Program   & 7zip& arj& bsa & bzip2 & compress & dmc& gzip &ha\\%[-0.5em]% \hline
%    Guesses   & 39  & 46 & 44  & 38    & 12       & 36 & 50   &47\\%[-0.5em]% \hline
%  \end{tabular}

%  \begin{tabular}{lccccccc}
%    %\hline
%    Program   & huff& lzari & lzss & ppmd5 & rar & rarw &rk\\%[-0.5em] %\hline
%    Guesses   & 10  & 17    & 14   & 46    & 58  & {\bf 71}   &52\\%[0.5em]%\hline
%    \multicolumn{8}{c}{Markov Chain approach (see~\cite{Khmelev:2000}):
%{\bf 69} guesses}%\\[-0.5em]
%  \end{tabular}
%\end{center}

Clearly, {\em gzip} is significantly outperformed by other compression
algorithms and the first order Markov chain model~\cite{Khmelev:2000}.
Notice also that in practical implementations, the {\em gzip}-based
approach~\cite{Bene:2002} is significantly slower than the first order Markov
chains method~\cite{Khmelev:2000}.

To sum up, in natural language processing (and, perhaps, in other
fields) the $n$th order Markov chain
models~\cite{Khmelev:2000,Teahan:2000} are more appropriate than
an LZ-approach~\cite{Bene:2002}.

% Create the reference section using BibTeX:
\bibliography{cmc}

\end{document}

cmc.bbl
\begin{thebibliography}{8}
\expandafter\ifx\csname natexlab\endcsname\relax\def\natexlab#1{#1}\fi
\expandafter\ifx\csname bibnamefont\endcsname\relax
  \def\bibnamefont#1{#1}\fi
\expandafter\ifx\csname bibfnamefont\endcsname\relax
  \def\bibfnamefont#1{#1}\fi
\expandafter\ifx\csname citenamefont\endcsname\relax
  \def\citenamefont#1{#1}\fi
\expandafter\ifx\csname url\endcsname\relax
  \def\url#1{\texttt{#1}}\fi
\expandafter\ifx\csname urlprefix\endcsname\relax\def\urlprefix{URL }\fi
\providecommand{\bibinfo}[2]{#2}
\providecommand{\eprint}[2][]{\url{#2}}

\bibitem[{\citenamefont{Benedetto et~al.}(2002)\citenamefont{Benedetto,
  Caglioti, and Loreto}}]{Bene:2002}
\bibinfo{author}{\bibfnamefont{D.}~\bibnamefont{Benedetto}},
  \bibinfo{author}{\bibfnamefont{E.}~\bibnamefont{Caglioti}}, \bibnamefont{and}
  \bibinfo{author}{\bibfnamefont{V.}~\bibnamefont{Loreto}},
  \bibinfo{journal}{Phys.\ Rev.\ Lett.} \textbf{\bibinfo{volume}{88}}
  (\bibinfo{year}{2002}).

\bibitem[{\citenamefont{Gusfield}(1997)}]{gusfield}
\bibinfo{author}{\bibfnamefont{D.}~\bibnamefont{Gusfield}},
  \emph{\bibinfo{title}{Algorithms on strings, trees, and sequences}}
  (\bibinfo{publisher}{Cambridge University Press},
  \bibinfo{address}{Cambridge}, \bibinfo{year}{1997}).

\bibitem[{\citenamefont{Shannon}(1948)}]{Shannon}
\bibinfo{author}{\bibfnamefont{C.}~\bibnamefont{Shannon}},
  \bibinfo{journal}{Bell Syst. Tech. J.} \textbf{\bibinfo{volume}{27}}
  (\bibinfo{year}{1948}).

\bibitem[{\citenamefont{Yaglom and Yaglom}(1983)}]{Yaglom}
\bibinfo{author}{\bibfnamefont{A.}~\bibnamefont{Yaglom}} \bibnamefont{and}
  \bibinfo{author}{\bibfnamefont{I.}~\bibnamefont{Yaglom}},
  \emph{\bibinfo{title}{Probability and Information}}
  (\bibinfo{publisher}{Reidel}, \bibinfo{address}{Boston},
  \bibinfo{year}{1983}).

\bibitem[{\citenamefont{Kukushkina et~al.}(2001)\citenamefont{Kukushkina,
  Polikarpov, and Khmelev}}]{Kukush:2001}
\bibinfo{author}{\bibfnamefont{O.}~\bibnamefont{Kukushkina}},
  \bibinfo{author}{\bibfnamefont{A.}~\bibnamefont{Polikarpov}},
  \bibnamefont{and} \bibinfo{author}{\bibfnamefont{D.}~\bibnamefont{Khmelev}},
  \bibinfo{journal}{Problems of Information Transmission}
  \textbf{\bibinfo{volume}{37}}, \bibinfo{pages}{172} (\bibinfo{year}{2001}).

\bibitem[{\citenamefont{Cleary and Witten}(1984)}]{PPM}
\bibinfo{author}{\bibfnamefont{J.~G.} \bibnamefont{Cleary}} \bibnamefont{and}
  \bibinfo{author}{\bibfnamefont{I.~H.} \bibnamefont{Witten}},
  \bibinfo{journal}{IEEE Trans. on Commun.} \textbf{\bibinfo{volume}{22}},
  \bibinfo{pages}{541} (\bibinfo{year}{1984}).

\bibitem[{\citenamefont{Teahan}(2000)}]{Teahan:2000}
\bibinfo{author}{\bibfnamefont{W.~J.} \bibnamefont{Teahan}},
  \bibinfo{journal}{Proceedings RIAO'2000} \textbf{\bibinfo{volume}{2}},
  \bibinfo{pages}{943} (\bibinfo{year}{2000}).

\bibitem[{\citenamefont{Khmelev}(2000)}]{Khmelev:2000}
\bibinfo{author}{\bibfnamefont{D.}~\bibnamefont{Khmelev}}, \bibinfo{journal}{J.
  of Quantitative Linguistics} \textbf{\bibinfo{volume}{7}},
  \bibinfo{pages}{201} (\bibinfo{year}{2000}).

\end{thebibliography}
