GNAT : A General Narrative Alignment Tool (2023)

Abstract: 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.

## introduction algorithmic sequence alignment is a fundamental task in string processing, which identifies similar text segments shared between a pair of documents. sequence alignment is a common operation in many nlp tasks, with representative applications including identifying spelling @xcite and ocr @xcite errors in documents, quantifying post-publication edits in news article titles @xcite , and plagiarism detection @xcite . text alignment has been used to create datasets for text summarization tasks @xcite , by loosely aligning summary paragraphs to the chapters of original stories and documents. textual criticism is the study of the transmission of text @xcite , typically for religious and historically significant texts such as the bible. the collation task in textual criticism examines textual variations across different versions of a text through alignment @xcite ). text alignment is often deployed in literary research, e.g., analyzing how books are adapted for young adults @xcite , translated @xcite , and how the gender of the translator affects the translated work @xcite . however, sequence alignment in nlp research is largely done on an ad hoc basis, serving small parts of bigger projects by relying on hand-rolled tools. this is in contrast to the field of bioinformatics, where the alignment of nucleotide and protein sequences plays a foundational role. popular tools such as blast @xcite running on large sequence databases are used to identify even distant homologies (similarites) with rigorous statistical measures of significance. such tools facilitate meaningful analyses over vast differences in scale, from short gene-to-gene comparisons to full genome-to-genome alignment or gene-to-database searches. the overarching goal of our work is to extend the rigorous sequence analysis techniques from bioinformatics to the world of narrative texts. sequence alignment can be computed using the widely-used edit distance algorithm for leveinshtein disance @xcite , which aligns texts by computing the minimum number of deletions, insertions, substitutions, and/or transpositions. however, edit distance fails when applied to distant narrative texts that are semantically but not textually similar, since neither character nor word-level changes capture the semantic meaning of the text. consider comparing two independent translations of a particular novel, or two different retellings of a classic fable. we anticipate very little in terms of long common text matches, even though the documents are semantically identical, and it is not obvious how to quantify the significance of whatever matches we do happen to find. aligning large text documents is a difficult task, for reasons beyond measuring distance in semantic space versus simple text-based edits. often the proper interpretation consists of multiple local alignments instead of one sequential global alignment. for instance, consider a document that plagiarizes disjoint parts of a second document in a different order. while local sequence alignments are successfully used in the bioinformatics domain to align genome and protein sequences @xcite , they have been underutilized in nlp. a second issue is scale mismatch: aligning a short book summary to an unabridged novel requires mapping single sentences to pages or even chapters of the larger text. a final concern is the statistical rigor of an alignment: every pair of completely unrelated texts has an optimal alignment, but how can we tell whether such an alignment exhibits meaningful measures of similarity? although text alignment is used in a nlp tasks across multiple domains, much of the existing work has been domain-specific or focused on global alignments. in this paper, we develop and evaluate a general purpose tool (gnat) for the efficient and accurate alignment of pairs of distant texts. we propose a method for adapting the classical smith-waterman (sw) local alignment algorithm with affine gap penalties for nlp tasks by employing multiple textual similarity scoring functions and perform comparative analysis. our major contributions 1 2 are as follows: the dodger and charley bates had taken oliver out for a walk, and after sauntering along, they suddenly pulled up short on clerkenwell green, at the sight of an old gentleman reading at a bookstall. so intent was he over his book that he might have been sitting in an easy chair in his study. to oliver's horror, the dodger plunged his hand into the gentleman's pocket, drew out a handkerchief, and handed it to bates. then both boys ran away round the corner at full speed. oliver, frightened at what he had seen, ran off, too; the old gentleman, at the same moment missing his handkerchief, and seeing oliver scudding off, concluded he was the thief, and gave chase, still holding his book in his hand. the cry of "stop thief!" was raised. oliver was knocked down, captured, and taken to the police-station by a constable. the magistrate was still sitting, and oliver would have been convicted there and then but for the arrival of the bookseller. you can imagine oliver's horror when he saw him thrust his hand into the old gentleman's pocket, draw out a silk handkerchief and run off at full speed. in an instant oliver understood the mystery of the handkerchiefs, the watches, the purses and the curious game he had learned at fagin's. he knew then that the artful dodger was a pickpocket. he was so frightened that for a minute he lost his wits and ran off as fast as he could go. just then the old gentleman found his handkerchief was gone and, seeing oliver running away, shouted "stop thief!" which frightened the poor boy even more and made him run all the faster. everybody joined the chase, and before he had gone far a burly fellow overtook oliver and knocked him down. a policeman was at hand and he was dragged, more dead than alive, to the police court, followed by the angry old gentleman. this paper is organized as follows. section 2 provides an overview of related works on sequence alignments in nlp and bioinformatics. section 3 formally defines the problem of text alignment and presents our alignment method with the different metrics for scoring textual similarities. section 4 details our method for computing the statistical significance of text alignments. we describe our experimental results in section 5 before concluding with future directions for research in section 6. ## related work the literature on sequence alignment algorithms and applications is vast. here we limit our discussion to representative applications in nlp and bioinformatics, and prior work on measuring the statistical significance of alignments. ## methods for alignment text alignment involves matching two text sequences by aligning their smaller components, such as characters, words, sentences, paragraphs, or even larger segments like chapters. the best component size depends on the task and the user's intent. for example, aligning a summary with a book requires comparing sentences from the summary with paragraphs or chapters, while aligning two book translations requires comparing paragraphs, pages, or larger units. formally, we define text alignment as follows: ## statistical significance of alignments determining the significance of a semantic text alignment is a critical aspect that is dependent on both the domain and the user's definition of significance. for instance, two essays on the same topic are expected to have more semantically similar text segments than two fictional books by different authors. we discuss how sw can produce weak noise alignments between unrelated texts in appendix c. significance testing can distinguish between real and noise alignments that occur by chance. ## conclusion we have developed a tool for narrative text alignment using the smith-waterman algorithm with dif-ferent similarity metrics, including a methodology to measure the statistical significance of aligned text segments. gnat can be applied to the pairwise comparison of texts from any domain with varying unit sizes for text segmentation. while our evaluations were confined to english documents, the applicability of gnat extends to languages supported by embedding models akin to sbert. for languages with limited resources, embedding models can be trained following @xcite , subsequently enabling the deployment of gnat. the next important direction here involves exploring how sequence database search tools like blast @xcite ) can be adapted for text search. one possible approach uses nearest neighbor search over embeddings in the database using parts of a query document to find seed positions for alignment, and then extends the alignments bidirectionally for faster heuristic searches. another research direction is analyzing how the sampling based statistical significance testing method performs for different granularity levels, especially for alignment at the word or sentence level.