GNAT: A General Narrative Alignment Tool
Tanzir Pial Steven Skiena
Algorithmic sequence alignment identifies similar segments shared between
pairs of documents, and is fundamental to many NLP tasks. But it is difficult
to recognize similarities between distant versions of narratives such as
translations and retellings, particularly for summaries and abridgements which
are much shorter than the original novels.
  We develop a general approach to narrative alignment coupling the
Smith-Waterman algorithm from bioinformatics with modern text similarity
metrics. We show that the background of alignment scores fits a Gumbel
distribution, enabling us to define rigorous p-values on the significance of
any alignment. We apply and evaluate our general narrative alignment tool
(GNAT) on four distinct problem domains differing greatly in both the relative
and absolute length of documents, namely summary-to-book alignment, translated
book alignment, short story alignment, and plagiarism detection --
demonstrating the power and performance of our methods.