Fast k-best Sentence Compression
Abstract
A popular approach to sentence compression is to formulate the task as a
constrained optimization problem and solve it with integer linear programming (ILP)
tools. Unfortunately, dependence on ILP may make the compressor prohibitively slow,
and thus approximation techniques have been proposed which are often complex and
offer a moderate gain in speed. As an alternative solution, we introduce a novel
compression algorithm which generates k-best compressions relying on local deletion
decisions. Our algorithm is two orders of magnitude faster than a recent ILP-based
method while producing better compressions. Moreover, an extensive evaluation
demonstrates that the quality of compressions does not degrade much as we move from
single best to top-five results.
