% This is LLNCS.DEM the demonstration file of
% the LaTeX macro package from Springer-Verlag
% for Lecture Notes in Computer Science, version 1.1
\documentstyle{llncs}
%
\begin{document}

\title{An Efficient Algorithm for Japanese Sentence Compaction Based on 
       Phrase Importance and Inter-phrase Dependency}

\author{Rei Oguro\inst{1}, Kazuhiko Ozeki\inst{1}, 
Yujie Zhang\inst{2}, and Kazuyuki Takagi\inst{1}}

\institute{The University of Electro-Communications, Chofu, Tokyo
182-8585, Japan
\and
ATR Spoken Language Translation Research Laboratories,\\
Seika-cho, Kyoto 619-0288, Japan\\
{\tt \{rei,ozeki,takagi\}@ice.uec.ac.jp, yujie.zhang@slt.atr.co.jp}}

\maketitle

\begin{abstract}
This paper describes an efficient algorithm for Japanese sentence
compaction. First, a measure of grammatical goodness of phrase
sequences is defined on the basis of a Japanese dependency grammar. Also 
a measure of topical importance of phrase sequences is given.
Then the problem of sentence compaction is formulated as an
optimization problem 
of selecting a subsequence of phrases from the original sentence 
 that maximizes the sum of the grammatical goodness and the topical 
importance. A recurrence equation is derived by using the principle 
of dynamic programming, which is then translated into an algorithm 
to solve the problem. The algorithm 
is of polynomial-time with respect to the original sentence length. 
Finally, an example of sentence compaction is presented.
\end{abstract}
%
\section{Introduction}
%
With the rapid increase of electronic publications, text summarization 
is becoming an important technical area in recent years\cite{okumura}. 
Most widely 
used methods for text summarization are based on the idea of extracting 
important sentences from the whole text according to some criterion. 
However, in some applications such as on-line generation of TV 
closed-captions, it is sometimes necessary to shorten each sentence as it 
comes in. Requirements for such sentence compaction are:
\begin{itemize} 
\item[1)] Shortened sentences retain the original information as much as 
    possible.
\item[2)] Shortened sentences are grammatically correct and natural. 
\item[3)] The compaction rate is adjustable to meet the specification
of the summarization system. 
\item[4)] The computational load is small, and the computation can
proceed without having to wait for the end of the input sentence. 
\end{itemize}
Several methods for Japanese sentence compaction have been proposed
\cite{wakao,katoh,hori,mikami}. 
None of them, however, satisfies all the requirements above. In this 
paper, the sentence compaction problem is formulated as an optimization 
problem of selecting a subsequence of phrases from the original 
sentence that maximizes the sum of  grammatical goodness and 
 topical importance. The grammatical goodness is defined on the
basis of a Japanese dependency grammar. Then a  recurrence 
equation is derived by using the principle of dynamic programming. 
This equation is easily translated into an algorithm, which 
is expected to satisfy all of the requirements 1) - 4). Finally, an 
example is presented to demonstrate how a sentence is shortened
depending on the specified length.
%
\section{Problem Formulation}
%
Let $w_{0} w_{1} \cdots w_{M-1}$ be a Japanese sentence represented as a
sequence of phrases, where a phrase is a syntactic unit called
``bunsetsu'' in Japanese, consisting of a content word with or without
being followed by a string of function morphemes such as particles and 
auxiliary verbs. The problem of sentence compaction here is to select a 
``good'' subsequence of phrases from the original sentence. In order 
to formulate this problem, a measure of goodness of a phrase sequence 
must be defined.
The structure of a Japanese sentence can be viewed from a dependency 
grammatical point; it can be described by specifying which phrase 
modifies which phrase in a wide sense. 
 Thus, a dependency structure on 
a subsequence $w_{k_{0}} w_{k_{1}} \cdots w_{k_{l-1}}$ of the original
sentence can be represented by a mapping
\begin{equation}
c: \{k_{0}, k_{1}, \ldots , k_{l-2}\} \longrightarrow
 \{k_{1}, k_{2}, \ldots , k_{l-1}\}
\end{equation}
such that $w_{c(m)}$ is the phrase modified by $w_{m}$\ \ 
$(m \in  \{k_{0}, k_{1}, \ldots , k_{l-2}\})$. 
For a normal Japanese sentence, this mapping must satisfy
\begin{itemize}
\item[a)] $m< c(m)$\ \ $(m \in  \{k_{0}, k_{1}, \ldots , k_{l-2}\})$, 
\item[b)] if $m< n$ then $c(n)\leq c(m)$\ \ 
$(m, n \in  \{k_{0}, k_{1}, \ldots , k_{l-2}\})$. 
\end{itemize}
The condition a) comes from the fact that modification always occurs 
from left to right in Japanese. The condition b) requires that two
pairs of phrases 
in modification relation do not cross with each other. 

  Let $p(m, n)$ be a function that represents the strength of
inter-phrase dependency between $w_{m}$ and $w_{n}$, or 
the degree of validity for $w_{m}$ to modify $w_{n}$. Then the
grammatical goodness of the phrase sequence $w_{k_{0}} w_{k_{1}}
 \cdots w_{k_{l-1}}$
can be measured by $\max_{c} \sum_{i=0}^{l-2}
p(k_{i}, c(k_{i}))$, where $c$ runs over all the dependency structures 
on the phrase sequence. Let $q(m)$ be another 
function to represent the topical importance of $w_{m}$. Then the 
topical importance of the phrase sequence
can be measured by $\sum_{i=0}^{l-1} q(k_{i})$. The total goodness of 
the phrase sequence $w_{k_{0}} w_{k_{1}} \cdots w_{k_{l-1}}$ is
defined as the sum of the grammatical goodness 
and the topical importance:
\begin{equation}
  g(k_{0}, k_{1}, \ldots ,k_{l-1})\stackrel{\triangle}{=}
  \left \{
   \begin{tabular}{l}
    $q(k_{0})$,\ \ if $l= 1$;\\
    $\max_{c} \sum_{i=0}^{l-2} p(k_{i}, c(k_{i})) + \sum_{i=0}^{l-1}
     q(k_{i})$,\ \ otherwise.
   \end{tabular}
  \right .
\end{equation}
  Now the problem of sentence compaction is formulated as follows:

\noindent
{\bf Problem}\ \ \ 
For a given sentence $w_{0} w_{1}\cdots w_{M-1}$ represented as a
sequence of phrases, 
find its subsequence $w_{k_{0}} w_{k_{1}} \cdots w_{k_{N-1}}$ of
a specified length $N$ that maximizes the function
$g(k_{0}, k_{1}, \ldots ,k_{N-1})$.

%
\section{Recurrence Equation}
%
To solve the problem above, its partial solutions and the 
relationship among them are considered. 
Let $f(m, n, l)$ be the maximum value of 
$g(k_{0}, k_{1}, \ldots ,k_{l-1})$ over all the subsequences of 
phrases of length $l$, starting with $w_{m}$ and ending with 
$w_{n}$ $(1 \leq l\leq n-m+1)$:
\begin{equation}
  f(m, n, l)\stackrel{\triangle}{=}
  \max_{m= k_{0}< k_{1}< \ldots < k_{l-1}= n}
  g(k_{0}, k_{1}, \ldots ,k_{l-1})
\end{equation}
Then it is shown that $f(m, n, l)$  satisfies 
the following recurrence equation:
  \begin{enumerate}
  \item for $m= n$ (only $l=1$ is allowed):
    \begin{equation}
      f(m, n, l)= q(m)
    \end{equation}
  \item for $m< n$ ($2\leq l \leq n-m+1$):
    \begin{enumerate}
      \item for $l= 2$:
        \begin{equation}
           f(m, n, l)= f(m, m, 1) + f(n, n, 1) + p(m, n)
           \label{equation:l2}
        \end{equation}
      \item for $l= 3$:
        \begin{equation}
         f(m, n, l)= \max
         \left \{
         \begin{tabular}{l}
         $f(m, m, 1)+\max_{m< m^{\prime}< n} \{f(m^{\prime}, n, 2)\}
         + p(m, n)$;\\
                    \\
         $\max_{m< n^{\prime}< n} \{f(m, n^{\prime}, 2)
          + p(n^{\prime}, n)\} + f(n, n, 1)$
        \end{tabular}
        \right .
        \label{equation:l3}
        \end{equation}
    \item for $l \geq 4$:
    \begin{eqnarray}
      \lefteqn{f(m, n, l)} \nonumber \\
      &=& \max
      \left \{
      \begin{tabular}{l}
        $f(m, m, 1)+\max_{m< m^{\prime}\leq n-l+2} \{f(m^{\prime}, n, l-1)\}
         + p(m, n)$;\\
                    \\
        $ \max_{2\leq l^{\prime} \leq l-2,
          \ m+l^{\prime}-1\leq n^{\prime}< m^{\prime}
          \leq n-l+l^{\prime}+1}$\\
        \hspace*{20mm} $\{f(m, n^{\prime},l^{\prime})
         + f(m^{\prime}, n, l-l^{\prime})
         + p(n^{\prime}, n)\}$;\\
                               \\
        $\max_{m+l-2\leq n^{\prime}< n} \{f(m, n^{\prime}, l-1)
        + p(n^{\prime}, n)\}
         + f(n, n, 1)$
      \end{tabular}
      \right .
      \label{equation:back}
    \end{eqnarray}
    \end{enumerate}
  \end{enumerate}

This recurrence equation can be proved by noting that maximization
of $g(k_{0}, k_{1}, \ldots ,k_{l-1})$ with respect to
 $(k_{0}, k_{1}, \ldots ,k_{l-1})$ subject to
 $m=k_{0}< k_{1}< \ldots <k_{l-1}=n$ is equivalent to maximization
of $g(k_{0}, k_{1}, \ldots ,k_{l-1})$ with respect to
 $(l^{\prime}$, $m^{\prime}, n^{\prime}$, $k_{0}, k_{1}, \ldots
,k_{l^{\prime}-1}$, $k_{l^{\prime}}, k_{l^{\prime}+1}, \ldots ,k_{l-1})$ 
subject to
$1\leq l^{\prime}\leq l-1$, $m\leq n^{\prime}<m^{\prime}\leq n$,
$m=k_{0}< k_{1}< \ldots < k_{l^{\prime}-1}=n^{\prime}$,
$m^{\prime}=k_{l^{\prime}}< k_{l^{\prime}+1}< \ldots < k_{l-1}=n$.

%
\section{Algorithm}
%
\subsection{Tabular Computation}
The above recurrence equation can be directly translated into an
algorithm as shown in Fig.\ref{figure:1}. 
Because there is a large freedom in the 
order of computation, this is one of many versions of 
the translation that yield the same result. Actual computation is carried
out by using a table to store the computed value of $f(m, n, l)$,
which is looked up in later computation steps.

\begin{figure}
\hspace*{24mm}{\bf for} $n:= 0$ {\bf to} $M-1$ {\bf do}\\
  \hspace*{26mm}{\bf begin}\\
  \hspace*{28mm}{\bf for} $m:= n$ {\bf downto} 0 {\bf do}\\
  \hspace*{30mm}{\bf begin}\ {\bf if}($m= n$) {\bf then} $f(m, m, 1):= q(m);$\\
  \hspace*{32mm}{\bf else}\\
  \hspace*{34mm}{\bf begin}\\
  \hspace*{36mm}{\bf for} $l:= 2$ {\bf to} $n-m+1$ {\bf do}\\
  \hspace*{38mm}{\bf begin}\\ 
  \hspace*{40mm}{\bf if}($l= 2$) {\bf then} $f(m, n, l):=$\ 
                                           Eq.(\ref{equation:l2});\\
  \hspace*{40mm}{\bf else if}($l= 3$) {\bf then} $f(m, n, l):=$\ 
                                           Eq.(\ref{equation:l3});\\
  \hspace*{40mm}{\bf else} $f(m, n, l):=$\ Eq.(\ref{equation:back});\\
  \hspace*{38mm}{\bf end;}\\
  \hspace*{34mm}{\bf end;}\\
  \hspace*{30mm}{\bf end;}\\
\hspace*{26mm}{\bf end;}
\caption{Algorithm for recursive computation of $f(m, n, l)$.}
\label{figure:1}
\end{figure}

The time-complexity of this algorithm is of
$O(M^{6})$, where M is the length of the original sentence. Although $O(M^6)$ 
might seem to be large, there is no computational difficulty for practical 
values of M. In fact, the algorithm, coded in C, completes the computation 
for $M= 40$ within 1 sec on UltraSPARC-IIi (270MHz).

\subsection{Back-Trace}
In order to recover the optimum phrase sequence, it is necessary 
to keep the record of the values of variables, for back-pointers, 
that attain the maximum in the recurrence equation.
 Three tables are used for the purpose: 
$bp[m, n, l].lp$, $bp[m, n, l].np$, and $bp[m, n, l].mp$.
In the middle case of
Eq.(\ref{equation:back}), for example, the back-pointers are set as
$bp[m, n, l].lp:= l^{\prime}$, $bp[m, n, l].np:= n^{\prime}$,
 and $bp[m, n, l].mp$ $:= m^{\prime}$, where $l^{\prime}$, $n^{\prime}$,
and $m^{\prime}$ are the values of those variables that attain the 
maximum.
The back-trace proceeds in the following way. 
First, the optimum starting phrase and ending phrase are sought 
for a specified length $N$:
\begin{equation}
(m_{0}, n_{0}):= \mbox{argmax}_{m, n} f(m, n, N).
\end{equation}
Starting with $(m_{0}, n_{0})$ as the initial value, the function
 in Fig.\ref{figure:2} performs a back-trace to give the
final solution
\begin{equation}
 solution:= out(m_{0}, n_{0}, N).
\end{equation}

\begin{figure}
{\hspace*{28mm}\bf function}\ $out(m, n, l)$: char string\\
     \hspace*{31mm}{\bf begin}\\
     \hspace*{34mm}{\bf if} ($m=n$) {\bf then} $out:= $``$w_{m}$'';\\
     \hspace*{34mm}{\bf else}\\
     \hspace*{34mm}{\bf begin}\\
     \hspace*{37mm}$l^{\prime}:= bp[m, n, l].lp$;\\
     \hspace*{37mm}$n^{\prime}:= bp[m, n, l].np$;\\
     \hspace*{37mm}$m^{\prime}:= bp[m, n, l].mp$;\\
     \hspace*{37mm}$out:=out(m, n^{\prime},l^{\prime})
          \oplus out(m^{\prime}, n, l-l^{\prime})$;\\
     \hspace*{34mm}{\bf end}; \\  
     \hspace*{31mm}{\bf end}.
\caption{Back-trace function. The sign $\oplus$ denotes concatenation of
 two character strings.}
\label{figure:2}
\end{figure}

%
\section{Example of Sentence Compaction} 
An example of sentence compaction is presented in Table \ref{table:1}
 to show how a sentence is shortened accoding to the specified length.
The value of $q(m)$ was defined based on the part-of-speech 
of the content word in $w_{m}$. The value of $p(m, n)$ was defined
on the basis of the 
morphological information about $w_{m}$ and $w_{n}$, and also the
inter-phrase distance between 
$w_{m}$ and $w_{n}$ in the original sentence\cite{zhang}. As is seen
 in Table \ref{table:1},
 all the shortened sentences are natural and make sense, retaining important 
information in the original sentence to the extent the length is
allowed.

\noindent
{\bf Original Sentence} ($M= 9$):\ 
mata$^{(1)}$ ({\it also})\ \  sodeya$^{(2)}$ ({\it sleeve and})\ \ 
sodekuchi$^{(3)}$ ({\it end of sleeve})\ \ 
pokettoguchinadoga$^{(4)}$ ({\it opening of pocket})\ \ 
aburayogorede$^{(5)}$ ({\it by oil dirt})\ \ 
henshokuwo$^{(6)}$ ({\it discolor})\ \ 
 okosu$^{(7)}$ ({\it be caused})\ \ kotomo$^{(8)}$ ({\it cases})\ \ 
arimasu$^{(9)}$ ({\it happen}).\\
({\it Also some cases may happen that the sleeves, the end of sleeves, and 
the opening of pockets are discolored by oil dirt.}) 

\begin{table}
\caption{Example of sentence compaction. Phrases are represented by
their numbers in the original sentence.
 $N$ denotes the specified length of the shortened sentence.}
\begin{center} 
\begin{tabular}{c|ccccccccc} \hline \hline
Length $N$ &    \multicolumn{9}{c}{Shortened Sentence}\\ \hline 
8 &     & (2) & (3) & (4) & (5) & (6) & (7) & (8) & (9)\\ 
7 &     & (2) & (3) & (4) &     & (6) & (7) & (8) & (9)\\ 
6 &     & (2) & (3) & (4) &     & (6) & (7) & (8) &    \\ 
5 &     & (2) & (3) & (4) &     & (6) & (7) &     &    \\ 
4 &     &     & (3) & (4) &     & (6) & (7) &     &    \\ 
3 &     &     &     &     &     & (6) & (7) & (8) &    \\
2 &     &     &     &     &     & (6) & (7) &     &    \\  \hline
\end{tabular}
\end{center}
\label{table:1}
\end{table}

%
\section{Concluding Remarks}
%
The Japanese sentence compaction problem was formulated as an optimization 
problem, and an efficient algorithm was derived. Because the computation 
proceeds input-synchronously, it is suited for on-line sentence compaction. 
The algorithm can also output the dependency structure (parse tree) of   
a shortened sentence in a manner similar to the one described in
\cite{ozeki}.

The values of $q(m)$ and $p(m, n)$ adopted in the example are only tentative. 
Therefore our future work includes:
\begin{itemize}
\item[1)] Establishing a method to give the appropriate values of
$q(m)$ and $p(m, n)$. 
\item[2)] Finding an optimal weighting balance between the topical importance 
    and the grammatical goodness.
\item[3)] Carrying out a large scale evaluation of this method. 
\end{itemize}

\begin{thebibliography}{1}
\bibitem {okumura}
Okumura, M., Nanba, H.:
Automated text summarization: A survey.
Journal of Natural Language Processing {\bf 6}(6)(1999) 1--26.

\bibitem {wakao}
Wakao, T., Ehara, T., Shirai, K.:
Summarization methods used for captions in TV news programs. 
Technical Report of Information Processing Society of Japan,
97-NL-122-13 (1997) 83--89.

\bibitem {katoh}
Katoh, N., Uratani, N.:
A new approach to acquiring linguistic knowledge for
locally summarizing Japanese news sentences.
Journal of Natural Language Processing
{\bf 6}(7) (1999) 73--92. 

\bibitem {hori}
Hori, C., Furui, S.:
Automatic speech summarization based on word
significance and linguistic likelihood.
Technical Report of Information Processing Society of 
Japan,
99-SLP-29-18 (1999) 103--108.

\bibitem {mikami}
Mikami, M., Masuyama, S., Nakagawa, S.:
A summarization method by reducing redundancy of each 
sentence for making captions of newscasting.
Journal of Natural Language Processing
{\bf 6}(6) (1999) 65--81.  

\bibitem {zhang}
Zhang, Y., Ozeki, K.:
Dependency analysis of Japanese sentences using the
statistical property of dependency distance between
phrases.
Journal of Natural Language Processing
{\bf 4}(2) (1997) 3--19.

\bibitem {ozeki}
Ozeki, K.:
A multi-stage decision algorithm to select optimum
bunsetsu sequences based on degree of
kakariuke-dependency.
IEICE Transactions
{\bf J70-D}(3) (1987) 601--609.

\end{thebibliography}
\end{document}
