GNAT: A General Narrative Alignment Tool
Authors: Tanzir Pial
Steven Skiena
Venue: EMNLP 2023 Main (2023)
Keywords: Text Alignment
TL;DR: We develop a general approach to narrative text alignment coupling a bioinformatics sequence alignment algorithm with modern text similarity metrics.

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.

GNAT: A General Narrative Alignment Tool
Tanzir Pial, Steven Skiena Department of Computer Science, Stony Brook University, NY, USA (tpial, wtw.ssieeessstttttoeee stonybrook. edu
Abstract
collation task in textual criticism examines textual variations across different versions of a text through alignment (Yousef and Janicke, 2020). Text align- ment often deployed in literary research, e.g., analyzing how books are adapted for young adults (Sulzer et al., 2018), translated (Bassnett, 2013), and how the gender of the translator affects the translated work (Leonardi, 2007).
Algorithmic sequence alignment identifies sim- ilar segments shared between pairs of doc- uments, and is fundamental to many NLP tasks. But difficult to recognize similari- ties between distant versions of narratives such as translations and retellings, particularly for summaries and abridgements which are much shorter than the original novels.
However, sequence alignment in NLP research is largely done ad hoc basis, serving small parts of bigger projects by relying on hand-rolled tools. This is contrast to the field of bioinformat- ics, where the alignment of nucleotide and protein sequences plays a foundational role. Popular tools such as BLAST (Altschul et al., 1990) running on large sequence databases are used to identify even distant homologies (similarites) with rigorous sta- tistical measures of significance. Such tools facil- itate meaningful analyses over vast differences in scale, from short gene-to-gene comparisons full tenome-to-genomee alignment or gene-to-database searches.
We develop a general approach to narrative alignment coupling the Smith- Waterman algo- rithm from bioinformatics with modern text similarity metrics. We show that the back- ground of alignment scores fits a Gumbel dis- tribution, enabling values on the significance of any alignment. We apply and evaluate our general narrative alignment tool (GNAT) on four distinct prob- lem domains differing greatly both the rela- tive and absolute length of documents, namely summary-to to-bokk alignment, translated book alignment, short story alignment, and plagia- rism detection demonstrating the power and performance of our methods.
define rigorous p-
The overarching goal of our work is to extend the rigorous sequence analysis techniques from bioin- formatics to the world of narrative texts. Sequence alignment can be computed using the widely-used edit distance algorithm for Leveinshtein disance (Levenshtein al., 1966), which aligns texts by computing the minimum number of deletions. in- sertions, substitutions, and/or transpositions, How- ever, edit distance fails when applied to distant narrative texts that are semantically but not textu- ally similar, since neither character nor word-level changes capture the semantic meaning of the text. Consider comparing two independent translations of a particular novel, two different retellings of 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 what- ever matches we do happen to find.
1 Introduction
Algorithmic sequence alignment is a fundamen- tal task in string processing, which identifies sim- ilar text segments shared between pair of docu- ments. Sequence alignment is common operation in many NLP tasks, with representative applica- tions including identifying spelling (Dargis al., 2018) and OCR (Yalniz and Manmatha, 2011) er- rors in documents, quantifying post-publication edits in news article titles (Guo et al., 2022), and plagiarism detection (Potthast et al., 2013). Text alignment has been used to create datasets for text summarization tasks (Chaudhury et al., 2019), by loosely aligning summary paragraphs the chap- of original stories and documents. Textual criti- cism is the study of the transmission of text (Abbott
and Williams, 2014), typically for religious and his- torically significant texts such as the Bible. The

---

Heidi tra translated Stork (1915)
The World's Greatest Books
DC
DS
HT
NN
TC-
Heidi translated by Abbot (1916)
OC
DC OF MN DS
L.
MC
OM
TC.
BH
HT
Tales From Dickens
(a) Heidi Alignment by SW SBERT
(b) Aligning versions of Dickens' tales by SW + SBERT
Figure 1: Heat maps representing Smith- Waterman alignments in two distinct narrative domains. On left, different English translations of the novel Heidi are aligned: the bright main diagonal correctly indicates that they follow the same sequence of events. On right, different story collections of abridged novels are aligned: the disjoint diagonal patterns correctly identify different versions of the same novels (represented using acronyms) shared across the collections.
Aligning large text documents is a difficult task, for reasons beyond measuring distance in seman- tic space versus simple text-based edits. Often the proper interpretation consists of multiple local alignments instead one sequential global align- ment. For instance, consider a document that pla- giarizes disjoint parts of a second document a different order. While local sequence alignments are successfully used in the bioinformatics domain to align genome and protein sequences (Smith et al., 1981), they have been underutilized in NLP. A sec- ond 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 alignment exhibits meaningful measures of similarity?
Our major contributions' are follows:
Local Alignment Methods for Narrative Texts We develop and evaluate sequence align- ment methods for distant but semantically similar texts, and propose general method for computing statistical significance of text alignments in any domain. Specifically, we demonstrate that alignment scores of unre- lated pairs narrative texts are mell-modelled by a Gumbel distribution (Altschul and Gish, 1996). Fitting the parameters of this distribu- tion provides rigorous way quantify the significance of putative alignments.
Distance Metrics for Narrative Alignment We propose and evaluate five distinct distance metrics for the alignment of narrative docu- ments over a range of relative and absolute sizes. We demonstrate that neural similarity measures like SBERT generally outperform other metries, although the simpler and more efficient Jaccard similarity measure proves surprisingly competitive on task like identi- fying related pairs of book translations (0.94 AUC vs. 0.99 AUC for SBERT). However, we show that Jaccard similarity loses sensitivity over larger (chapter-scale) text blocks.
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.
'All codes datasets are available at https: / thub. con/ tanzirn///// monzir//alin wiwmaanggennttooooo tool2__ An assnciated web interface can be found at https:// www. www.alignext..cmmm com/

---

You can imagine Oliver's horror when he him thrust his hand into the old gentleman's 's pocket, draw out silk handkerchief and 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 ss He knew then that the Artful Dodger was pickpocket. Hc was so frightened that for a minute he lost his wits and ran off as fast as he could go. Just then the old
The Dodger and Charley Butes had taken Oliver out for walk, and after sauntering along, they suddenly pulled up short on Clerkenwell Green, at the sight of an old gentleman reading at bookstall. So intent was he over his book that he might have been sitting in an easy chair in his study. To Oliver's 's horror, the Dodger plunged his hand into the gentleman's 's pocket, drew out handkerchief, and handed it Bates. Then both boys ran away round the corner full speed/ Oliver, frightened at what he had seen, off, too: the old gentleman, at the same moment missing his bandkerchief, and seeing Oliver scudding concluded he was the thief, and gave chase, still holding his book 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.
gentleman found his handkerchief was gone and, seeing Oliver running away, shouted "Stop thief!" which frightened the poor boy even more and madé him run all the faster. Everybody joined the chase, and before he had gone far a burly fellow overtook Oliver and knocked him down, policeman was at hand and he dragged, more dead than alive, the police court, followed by the angry old gentleman.
Table I:
Excerpts from two distinct abridgements of Oliver Twist. The highlighted areas indicate pairs of segments aligned by our text alignment tool.
Performance Across Four Distinct Application Domains -oo prove the general applicability of GNAT, we evaluate it in four application scenarios with text of varying absolute and relative sizes:
SBERT (Fi = 0.67) substanially outper- form baselines of sequential alignments and a generative one-shot learner model (0.40 and 0.46, respectively).
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 Scction 5 before concluding with future directions for research in Section 6.
Sunmary-to--ooo alignment: Our align- ment methods successfully match the summary with the correct book from the set of candidates with 90.6% accuracy.
Translated book alignment: We have constructed a dataset of 36 foreign language books represented in Project Gutenberg by two independent, full- length translations into English. Our alignment methods achieve an AUC score of 0.99 in distinguishing duplicate book pairings from background pairs.
2 Related Work
Plagiarism detection: Experiments on the PAN-13 dataset (Potthast al., 2013) demonstrate the effectiveness of our alignment methods on a vastly different domain outside our primary area of in- terest. Our F1 score of 0.85 on the sum- mary obfuscation task substantially out- performs that of the top three teams in the associated competition (0.35, 0.46, and 0.61, respectively).
The literature on sequence alignment algorithms and applications is vast. Here we limit our dis- cussion to representative applications in NLP and bioinformatics, and prior work on measuring the statistical significance of alignments.
2.1 Algorithmic Sequence Alignment
Dynamic programming (DP) is a powerful tech- nique widely used in sequence alignment tasks, closely associated with dynamic time warping (DTW) (Müller, 2007). Everingham et al. (2006) and Park et al. (2010) used DTW to align script dialogues with subtitles. Thai et al. (2022) used the Beedleman-Wunster DP algorithm with an embedding- similarity measure to create pair- wise global alignments of English translations of the same foreign language book. Apart from DP,
Short story alignment: We conduct experiments on a manually annotated dataset of 150 pairs of related short stories (Aesop's fables), aligning sen- tences of independently written versions of the same underlying tale. Sentence- level Smith- Waterman alignments using

---

Naim et al. (2013) uses weighted A search for aligning multiple real-time caption sequences.
Smith al. (1981) modified the global Needleman- Wunstch algorithm (Needleman and Wunsch, 1970) to compute optimal local alignments and created the
2.2 Representative NIP Applications
(SW) algorithm. In this paper, we use the SW algorithm as our choice of align- ment method, but adapt it to the NLP domain.
Statistical Machine Translation (MT) (Lopez, 2008) and neural MT models (Bahdanau et al., 2014) learn to compute word alignments using large corpora of parallel texts. However, these models are limited to word-level alignment and face computational inefficiencies for longer texts (Udupa and Maji, 2006). Multiple works (Mota et al., 2016, 2019; Sun et al., 2007; Jeong and Titov, 2010) have proposed joint segmentation and alignment create better text segmentations via aligning segments sharing the same topic and hav- ing lexical cohesion. Paun (2021) uses Doc2Vec embeddings for alignment and creates monolingual parallel corpus.
These algorithms quadratic in both time and space complexity. Hirschberg (1975) and Myers and Miller (1988) brought down the space com- plexity of these algorithms to linear. Nevertheless, pairwise alignment between a query sequence and a vast database remains a computationally intensive task. Altschul et al. (1990) proposed faster but less accurate algorithm called BLAST for protein searches in database. We argue that with appro- priate similarity metries and modifications, these algorithms can be applied to narrative alignment.
2.4 Statistical Significance of Aliguments
By using text alignment tools to automate the alignment process, researchers can streamline their analyses and uncover new insights in a more effi- cient manner. For example, Janicki et al. (2022) performs large scale text alignment to find simi- lar verses from ~90,000 old Finnic poems by us- ing clustering algorithms based on cosine similar- ity of character bigram vectors. Janicki (2022) uses embeddings of texts and proposes optimiza- tions for simpler modified versions of the DP-based Needleman- wunnsthh algorithm.
For ungapped nucleotide alignments where a sin- gle alignment must be contiguous without gaps, Karlin and Altschul (1990) proposed an impor- tant method for computing the statistical signifi- cance of an alignment score. The distribution of scores of ungapped alignments between unrelated protein genome sequences follows an extreme- value type I distribution known as Gumbel distri- bution (Ortet and Bastien, 2010). For gapped align- ments, no such analytical method is available but many empirical studies have demonstrated that the gapped alignment scores also follow an extreme value distribution (Altschul and Gish, 1996). (Pear- son, 1998), (Ortet and Bastien, 2010). Altschul and Gish (1996) proposes method to estimate the statistical significance of gapped alignment scores empirically. We adapt and empirically evaluate these methods for computing the statistical signifi- cance of narrative alignments.
Pial ct al. (2023) extends the methods proposed for GNAT for book-to-film script alignment and do analysis on the scriptwriter's book-to-film adap- tation process from multiple perspectives such as faithfulness to original source. gender representa- tion, importance of dialogues.
Foltýnek et al. (2019) categorizes the extrinsic plagiarism detection approach as aligning text be- tween a pair of suspicious and source document, Potthast et al. (2013) notes that many plagiarism detection algorithms employ the geed-and-extent paradigm where seed position is first found using heuristics and then extended in both directions. Pla- giarism detection tools can align different types of text, including natural language document, source codes (Bowyer and Hall, 1999), and mathematical expressions (Meuschke et al.. 2017).
Methods for Alignment
Text alignment involves matching two text se- quences by aligning their smaller components, such as characters, words, sentences, paragraphs, or even larger segments like chapters. The best com- ponent size depends on the task and the user's 's in- tent. For example, aligning 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.
2.3 Sequence Alignment in Bioinformatics
DNA and protein sequence alignment have been extensively used in bioinformatics to discover evo- lutionary differences between different species.
Formally, we define text alignment as follows:

---

given text sequences X (æo, 21, .... I' 1) and Y (yo. Vi..... yn-1), we seek to identify set of alignments where an alignment a = (2i J Up: Mg) indicates that the text segment 2; to 2; corresponds to the text segment Up to Vq.
3.1 The Smith-Waternnn Waterman (SW) Algorithm
Here use the local alignment method proposed by Smith et al. (1981), defined by the recurrence relation (i.j) )) in Equation that attempts to find the maximal local alignment ending index and index j of the two sequences.
0.
0.5
3.0
1.5
2.0
2.5
3.0
3.5
4.0
Masiiru
Figure 2: The distribution of maximum SW alignment scores from 2.5 10 pairs unrelated books, where the red curve is the Gumbel distribution estimated from this data using maximum likelihood estimation (location # 1.29, scale 3 = 0.30).
[I - 1,j 1) -(X,)
H(i - 105-1,1)++ H(i.j 1eoi-1++0 + 0
H(i.)) max
(1)
been used in computing semantic overlap between summary and documents (Gao et al., 2020).
S(a, b) is a function for scoring the similarity be- tween components and and g is a linear gap penalty. However, we employ the more general affine gap penalty (Altschul, 1998) with different penalties for starting and extending gap the deletion of a narrative segment is often continu- ous, therefore extending an already started gap should be penalized less than introducing a new gap. The time complexity of the SW algorithm is (mm), where m and n are the lengths of the two sequences. We discuss how we obtain multiple local alignments based on the DP matrix created by SW in Apppendix A.
Jaccard: The Jaccard index treats text as a bag-of- words, and computes similarity using the multiset of words present in both text segments:
J(a,
(2)
a Ub
Jaccard has the caveat that it is not suitable for computing similarity between texts of different lengths. Diaz and Ouyang (2022) has used Jaccard index for text segmentation similarity scoring.
TF-IDF: The Term Frequency Inverse Document Frequency (TF-IDF) measures text similarity using the frequency of words weighted by the inverse of their presence in the texts, giving more weight to rare words. Here the set of documents is rep- resented by the concatenated set of text segments from both sequences. Chaudhury et al. (2019) uses TF-IDF to align summaries to stories.
3.2 Similarity Scoring Functions
The key factor that distinguishes aligning text se- quences from other types of sequences is how we define the similarity scoring function S(a, b) in Equation 1. An ideal textual similarity function must capture semantic similarity. This section de- scribes several similarity scoring functions as Sec- tion 5.2 evaluates their comparative performance. SBERT Embeddings: Reimers and Gurevych (2019) proposed SBERT to create semantically meaningful text embeddings that can be compared using cosine similarity. SBERT creates embed- dings of texts of length up to 512 tokens, which is roughly equivalent 400 words (Gao et al., 2021). Usually this limit works for all sentences and major- ity of paragraphs. For texts longer than 400 words, we chunk the text into segments of 400 words and do a mean pooling to create the embedding fol- lowing Sun et al. (2019). SBERT has previously
Glo Ve Mean Embedding: Following Arora et al. (2017), we represent a text by the average GloVe (Pennington et al., 2014) embeddings of all the words in the text, and compute cosine similarity. Hamming Distance: Given two text segments con- taining > words, we decompose the longer text into chunks of size n/m. The Hamming dis- tance h(...) .) is the fraction of chunks where chunk does not contain word from the shorter text. We then use - l(.,.) as the similarity score.
3.3 Unifying Similarity Scoring Functions
The diverse ranges and interpretations of similar- ity scores from different scoring functions make

---

Avg. sentences per book/summaryfable
Avg. of paragraphs per book/summaryffalle
Human
of pairs
Total # of words
Annotation
RelBook
36
6,56 Million
4668
1953.7
Classics Stories
14
146,9K
271.1
114.5
(Sjummary(B)onk
464
542K (S)
61.5 (S)
(S)
X
464
47.35 Million (B)
5166.1 (B)
1843 (B)
Fables
152
39K
7.1
Table 2: Statistics of the datasets employed in this study. For the Fables dataset, alignments between sentence pairs are manually annotated.
it challenging to compare alignment results. To unify these metrics, we generate distribution of similarity scores for large set of unrelated text components. We then calculate the similarity score between two text components, x and as follows:
segments than two fictional books by different au- thors. 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.
((z v) = (Z( u)) tha) x 2 1
(3)
4.1 Computing Statistical Significance
We propose a sampling- based method for comput- ing the statistical significance of alignment scores that can aid in computing thresholds for signifi- cance. Altschul and Gish (1996) hypothesizes that the gapped alignment scores of unrelated protein sequences follow an extreme value distribution of type specifically the Gumbel distribution. We argue that the same hypothesis holds for unrelated narrative texts sequences too and evaluate it here. Altschul and Gish (1996) defines the alignment score as the maximum value in the DP matrix com- puted by SW alignment. They estimate the proba- bility of getting an alignment score S > as:
where (.) is the logistic sigmoid function, (xx, y) is the z-score of the similarity between x and y. and the is threshold for a positive score. This conversion standardizes the range of values for all scoring functions to between -1 and 1. The th, threshold ensures that pairs with z-score less than (hg receive a negative similarity score, indicating possible lack of relatedness. This aligns with the requirements proposed by Dayhoff et al. (1978) for PAM matrices, one of the most widely used similarity metrics for protein sequence alignments which require the expected similarity score of two random unrelated components be negative so only related components get positive similarity score.
P(S 2 x) = exp(- Hop(-Kmac Kmne- -xx) (4)
The threshold value thg is crucial in distinguish- ing between similarity scores of semantically sim- ilar text pair from random text pair. We hypothe- size similarity scores between unrelated text units follow a normal distribution. To determine thg, we computed cosine similarities for 100M random paragraph pairs using SBERT embeddings. We use the fitted normal distribution (μ- 0.097, 0.099) presented in Figure 5 in the appendix to es- timate the probability of chance similarity score X, We set default minimum threshold of +3 z-score for SW alignment, resulting in a ~0.0015% prob- ability of positive score for unrelated paragraphs following the three-sigma rule (Pukelsheim, 1994).
Here and n are lengths of the random quences, while À and K are parameters that define the Gumbel distribution. The probability density function of the Gumbel distribution is:
1 (s+ee
fgumhel (x)
(5)
B
(K * m * n)/A and - To estimate distribution parameters for the literary domain, we pair 1000 unrelated books by unique authors and align all possible pairs using SW with SBERT similarity at the paragraph level. After excluding the pairs having no alignment we get distribution of size ~ 2.5 x 103.
where, 2 = 3 = log(K
4 Statistical Significance of Alignments
To simplify the estimation, we set m and to be the mean length of books in the dataset and do maximum likelihood estimation find the two un- known parameters K and X for fitting the Gumbel distribution. We present the distribution of align- ment scores and the associated Gumbel distribution
Determining the significance of a semantic text alignment critical aspect that is dependent on both the domain and the user's definition of signifi- cance. For instance, two essays on the same topic are expected to have more semantically similar text

---

in Figure 2. We observe that the fitted Gumbel dis- tribution closely follows the original distribution. We present p-values of some example alignments using the Gumbel distribution in Appendix B.
1.0
0.8
True Positive Rate
0.6
5 Experiments and Applications
5.1 Datasets
0.4
sbert (AUC 0.99)
glove (AUC 0.85)
We created four different datasets for experiments on narrative alignment tasks over different scales and applications. The properties of these datasets, discussed below, are summarized in Table 2:
0.2
jaccard (AUC 0.94)
tf idf (AUC 0.78)
hamming (AUC = 0.63)
0.0
0.0
0.2
0.4
0.6
0.8
1.0
False Positive Rate
RelBook Dataset: Project Gutenberg (Guten- berg, n.d.) tens of thousands of books that have been used in previous research in NLP (Rae et al., 2019). We manually selected set of 36 non- English books that have multiple English transla- tions in Project Gutenberg. We pair these transla- tions create set of 36 pairs of related books.
Figure 3: ROC curves distinguishing related and unre- lated pairs of books from alignment order correlation, for different similarity metries. SBERT is the best at identifying pairs of related books.
higher alignment scores than unrelated book pairs. We compute SW alignment for each related and unrelated book pair using the similarity metries dis- cussed in Section 3.2, and plot an ROC curve Figure to evaluate SW alignment performance for classifying relatedness.
Classics Stories Dataset: We extracted 14 story pairs from two books: Tales From Dickens by Hal- lie Erminic Rives, containing shorter adaptations of Dickens' classics for young readers, and The World's Greatest Books - Volume 03, containing selected abridged excerpts from Dickens' classics. Alignment of two abridged versions of Oliver Twist are shown Table
We observe that the SBERT embeddings have the highest AUC score of 0.99, with Jaccard com- ing close second with 0.94. The weaker perfor- mance of widely-used metrics such TF-IDF with AUC 0.78 shows the non-triviality of the task as well as the strengths of the SBERT embeddings. We discuss how we create the unrelated book pairs and present an additional experiment using this data in Appendix C.
Summary Book Dataset: We use summaries of over 2,000 classic novels from Masterplots (Magill, 1989). We intersected the Masterplots summaries with the set of books from Project Gutenberg, using titles, authors, and other metadata, to obtain a set of 464 pairs of books and summaries.
Fables Dataset: We curated seven different com- pilations of Aesop's 'ss Fables from Project Gutenberg, each containing independent 5-to-15 sentence ver- sions of the classic fables. From this we created a set of 150 story pairs, each comprising of two different versions of the same fable. Two human annotators also manually aligned corresponding sentence pairs for each fable-pair, where many-to- many mapping is allowed. We found 80.42% agreement and Cohen's 's Kappa score of 0.746, in- dicating a substantial agreement (Landis and Koch, 1977) between the two annotators. Appendix D details the annotation process.
5.3 Plagiarism Detection for PANI3 Dataset
The PANI3 plagiarism detection dataset (Potthast et al., 2013) contains 10,000 pairs of documents from the Clue 2009 corpus evenly split train- ing and test In each pair, text segments from the source document are inserted into the target document using automated obfuscation strategies, creating what are referred to as plagiarized cases. These cases can be identified through high-scoring local alignments of the two documents.
We use our alignment system at the sentence and paragraph level for this dataset and report the re- sults in Table 3. We identify the optimal z-threshold (h, for positive matches as discussed in the Sec- tion 3.3 using the training and run the system against the test set. We do no optimization of our system, except for the z-threshold search. Our out-of-thee-bo system demonstrated competitive
5.2 Comparison of Similarity Functions
In this experiment, explore the effectiveness of different similarity metries in distinguishing be- tween related and unrelated book pairs. We hy- pothesize that related pairs (RelBooks) should yield

---

No Obflascation
Random Obfuscation
Translation Obfuseation
Summary Obfuscation
Entire Corpus
precision
recall
F-1
precision
recall
F-1
precision
recall
F-1
precision
recall
F-1
precision
recall
F-1
Torrejón and (2013)
.91
.89
Leikei al. (2013)
.76
91
833
.66
779
.22
86
85
85
96
.30
46
X3
.81
.22
Suchomel (2013)
.81
.99
.67
.73
Sanchez-Perez (2014)
.83
98
90
91
86
88
88
.99
.88
39
.1
.58
88
88
.88
Altheneyan and Menai (2020)
.92
.85
.88
.89
Jaceard-SW
78
.39
.73
SBERT+SW
.91
.79 .84 .89 43
.58
.86
.66
-75
.93
.78
.85
.84
.7
.75
Table 3:
We report the performance of the top-3 teams in the plagiarism detection contest and recent state-of-the-art results, along with our text alignment tool on different subsets of the PAN-13 dataset (Potthast et al., 2013). The subsets created based on how the plagiarism was inserted in the query documents. We present a subset of the results for Altheneyan and Menai (2020), as they did not provide results for all subsets of the dataset individually. SBERT performs remarkably better than other methods on the Summary Obfuscation subset.
Unit
Percent Fidelity
Mean Rank
Worst Rank
Method
Precision
Recall
F1
Method
MRR
Size
Random
0.17
0,27
0.21
Jaccard
Sentence
78.2
1.84
0.85
Seq. Baseline
0.31
0.54
0.40
+ SW
Puragraph
77.7
2.36
0.84
41
ChatGPT
0.42
0.51
0.46
Chunk
21.4
6.36
0.35
18
SJ+carrdd
0.62
0.69
0.65
Sentence
85.8
1,42
0.91
29
SBERT + SW
SW+SBERT
0.63
0.71
0.67
Puragraph
88.4
1,36
0,93
36
Chunk
90.6
1.31
0.94
Table 5: Performance of GNAT vs. ChatGPT for the Fa- bles dataset. The test dataset consists of 2175 sentences for 120 fable pairs. Each sentence of the first fable of the pair is aligned with sentence of the second fable marked as unaligned.
Table 4: Performance of SBERT+SW and Jaccard+SW for different segmentation unit sizes for the BookSum- mary dataset. SBERT outperforms Jaccard for all unit sizes. SBERT shows better performance as summary sentences are aligned with larger units of the book. Per- cent fidelity denotes the fraction of cases where the related pair was ranked 1.
and other results showing that SBERT is more ef- fective in representing texts of different length for alignment than Jaccard.
performance against carefully-tuned approaches discussed by Potthast et al. (2013). Notably, our alignment method using SBERT embeddings out- performed other methods for detecting summary obfuscations, where the entire source document is summarized and placed at random position in the target document. This superior performance can be attributed to SBERT capturing semantic similarities between text chunks of varying lengths.
5.5 Generative One-shot Learner Comparison
Generative models have shown promising results for many in-context learning tasks, where the model generates outputs based on one or more input-output examples. To evaluate performance of ChatGPT, based on GPT 3.5 architecture, (OpenAI, 2023) for text alignment, we provide the model with example alignment prompt using the Fa- bles dataset and then query it. The details of the prompts is discussed in Appendix Table 8. The lim- itation on the text size that can be passed as prompt to a generative model prevents longer texts from being used for this experiment.
5.4 Book/Summary Alignment
Here evaluate the importance of segmentation size and the strength of different similarity met- rics in aligning texts of different lengths. For each summary in the book-summary dataset, we pick 49 unrelated books of similar length creating 49 un- related and related pairs for each summary. We then compute the aligmments, and rank the 50 pairs based on the maximum alignment score. We seg- ment the summaries into sentences and repeat the experiment for different choices of segmentation sizes for the book: sentences, paragraphs, book chunks. For book chunks, we segment the book into m equal chunks for a summary of length m. Table 4 reports the Mean Reciprocal Ranks (MRR)
We then compare the performance of ChatGPT and our tool in Table 5 against human annotation for the Fables dataset. Although ChatGPT outper- formed our twin baselines of random and equally- spaced sequential alignment, our aligmment method incorporating Jaccard and SBERT embeddings per- formed significantly better.
6 Conclusion
We have developed a tool for narrative text align- ment using the Smith- Waterman algorithm with dif-

---

ferent similarity metries, including methoooooggy measure the statistical significance of aligned text segments. GNAT can be applied to the pair- wise 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 sup- ported by embedding models akin to SBERT. For languages with limited resources, embedding mod- els can be trained following Reimers and Gurevych (2020), subsequently enabling the deployment of GNAT.
the text sequences are long and GPUs are unavail- able. This restricts users with limited computa- tional power from utilizing the full power of our tool. In such scenarios, using Jaccard as the choice of similarity metric will be ideal as Jaccard is the second strongest similarity metric supported by our tool and, it does not demand substantial compu- tational resources. To address this limitation, we plan to include smaller versions of embedding mod- els in the tool in the future that would require less resources.
Acknowledgments
The next important direction here involves ex- ploring how sequence database search tools like BLAST (Altschul al., 1990) 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 test- ing method performs for different granularity lev- els, especially for alignment at the word sentence level.
We would like thank the anonymous review- ers for their valuable feedback, Arshit Jain (Stony Brook University) for development of the associ- ated web tool, Dr. Naoya Inoue (Japan Advanced Institute of Science and Technology), Anshuman Funkwal, Pranave Sethuraj (Stony Brook Univer- sity) for creating the Summary-Bon Book dataset.
References
Craig S Abbott and William Proctor Williams. 2014. An introduction to bibliographical and textual studies. Modern Language Association.
Limitations
Alaa Saleh Altheneyan and Mohamed El Bachir Menai.
2020. Automatic plagiarism detection in obfuscated text. Pattern Analysis and Applications, 23(4):1627- 1650.
This paper documents the design and performance of a general narrative alignment tool, GNAT. Al- though we have presented experimental results to validate its utility in four different domains involv- ing texts with varying absolute and relative lengths, every tool has practical performance limits.
Stephen F Altschul. 1998. Generalized affine gap costs for protein sequence alignment. Proteins: Structure, Function, and Bioinformatics, 32(1)288-96.
As implemented, the Smith- Waterman algorithm uses running time and space (memory) which grows quadratically, as the product of the two text sizes. The recursive algorithmic approach of (Hirschberg, 1975) can reduce the memory require- ments to linear in the lengths of the texts, at the cost of constant-factor overhead in running time. Such methods would be preferred when aligning pairs of very long texts, although we have success- fully aligned all attempted pairs of books over the course of this study.
Stephen F Altschul and Warren Gish. 1996. Local align- ment statistics. In Methods in enzymology, volume 266, pages 460-480. Elsevier.
Stephen Altschul, Warren Gish, Webb Miller, Eu- gene W Myers, and David Lipman. 1990. Basic local alignment search tool. Journal of molecular biology, 215(3)4033410
Sanjeev Arora, Yingyu Liang, and Tengyu Ma. 2017. A simple but rough-to-beat baseline for sentence em- beddings. International conference on learning representations.
The primary motivation of this project originates from goal to create general purpose alignment tool that anyone can use out-of-the-box with mini- mal effort. Almost all of our experiments showed SBERT embeddings to be superior to the other metries. However creating SBERT embeddings is a computationally heavy task, especially when
Dzmitry Bahdanau, Kyunghyun Cho, and Yoshua Ben- gio. 2014. Neural machine translation by jointly learning to align and translate. arXiv preprint 1r09v:1409.0473.
Susan Bassnett. 2013. Translation studies. Routledge.
Kevin W Bowyer and Lawrence Hall. 1999. Experi- ence using" moss" to detect cheating on programming

---

assignments. In FIE '99 Frontiers Education. 29th Annual Frontiers in Education Conference. Design- ing the Future of Science and Engineering Education. Conference Proceedings (IEEE Cat. No. 99CH37011, volume 3. pages 13.3-18.10 IEEE.
Maciej Janicki, Kati Kallio, and Mari Sarv. 2022. Ex- ploring finnic written oral folk poetry through string similarity. Digital Scholarship in the Humaniries.
Maciej Michal Janicki. 2022. Optimizing the weighted sequence alignment algorithm for large-scale text similarity computation. In Proceedings of the 2nd International Workshop on Natural Language Pro- cessing for Digital Humanities. Association for Com- putational Linguistics (ACI.).
Atef Chaudhury, Makarand Tapaswi, Seung Wook Kim, and Sanja Fidler. 2019. The shmoop corpus: A dataset of stories with loosely aligned summaries. arXiv preprint urXiv:I912. 13082.
Roberts Dargis, 1lze Auziga, and Kristine Leväne- Petrova. 2018. The use of text alignment in semi- automatic error analysis; use case in the development of the corpus of the latvian language learners. In Pro- ceedings of the Eleventh International Conference on Language Resources and Evaluation (LREC 2018).
Minwoo Jeong and Ivan Titov. 2010. Multi-document topic segmentation. In Proceedings of the 19th ACM international conference on Information and knowl- edge management, pages 11 19119112 128.
Samuel Karlin and Stephen F Altschul. 1990. Methods for assessing the statistical significance of molecular sequence features by using general scoring schemes. Proceedings of the National Academy of Sciences, 67(6):2264-2266
M Dayhoff, R Schwartz, and B Orcutt. 1978. A model of evolutionary change proteins. Atlas of protein sequence and structure, 5:345-352.
Richard Landis and Gary Koch. 1977. The mea- surement of observer agreement for categorical data. biometrics, pages 159-174.
Gerardo Ocampo Diaz and Jessica Ouyang. 2022. An alignment-buud -assed approach to text segmentation sim- ilarity scoring. In Proceedings of the 26th Confer- ence on Computational Natural Language Learning (CoNLL.,, pages 374-383.
Kong Leilei. Qi Haoliang, D Cuixia, W Mingxing, and H Zhongyuan. 2013. Approaches for source retrieval and text alignment of plagiarism detection. Notebook for PAN CLEF 2013.
Mark Everingham, Josef Sivie, and Andrew Zisserman. 2006. "Hello! My name is... Buffy" -Automatic naming of characters in TV video. In Proceedings of British Machine Vision Conference, 2006, pages 899-908.
Vanessa Leonardi, 2007. Gender and ideology in trans- lation: do women and men translate differently?: A contrastive analysis from Italian into English, vol- ume 301. Peter Lang.
Tomášs Foltýnek, Norman Meuschke, and Bela Gipp. 2019. Academic plagiarism detection: a systematic literature review. ACM Computing Surveys (CSUR), 52(6):
Vladimir I Levenshtein et al. 1966. Binary codes capa- ble of correcting deletions, insertions, and reversals. In Soviel physics doklady, volume 10, pages 707-710. Soviet Union
Shang Gao, Mohammed Alawad, M Todd Young, John Gounley, Noah Schaefferkootteer Hong Jun Yoon, Xiao-Cheng Wu, Eric B Durbin, Jennifer Doherty, Antoinette Stroup, et al. 2021. Limitations of trans- formers on clinical text classification, IEEE journal of biomedical and health informatics, 25(9):3596 3607.
Adam Lopez. 2008 Statistical machine translation. ACM Computing Surveys (CSUR), 1-49)
Frank Northen Magill. 1989. Masterpieces of world literature. HarperCollins Publishers.
Norman Meuschke, Moritz Schubotz, Felix Hamborg, Tomas Skopal, and Bela Gipp. 2017. Analyzing mathematical content to detect academic plagiarism. In Proceedings of the 2017 ACM on Conference on In- formation and Knowledge Management, pages 221 1- 2214.
Yang Gao, Wei Zhao, and Steffen Eger. 2020. Supert: Towards new frontiers in unsupervised evaluation metrics for multi-document summarization. arXiv preprint arXiv:2005.0372.
Xingzhi Guo, Brian Kondracki, Nick Nikiforakis, and Steven Skiena. 2022. Verba volant, scripta volant: Understanding post- publiccbii title changes in news outlets. In Proceedings of the ACM Web Conference 2022, pages 588-598.
Pedro Mota, Maxine Eskenazi, and Luisa Coheur. 2016. Multi-document topic segmentation using bayesian estimation. 2016 IEEE Tenth International Confer- ence on Semantic Computing (ICSC), pages 443-447. IEEE.
Project Gutenberg. n.d. www www.guttenergg.org Ac- cessed: April 2022.
Pedro Mota. Maxine Eskenazi, and Luísa Coheur. 2019. Beamseg: A joint model for multi-document seg- mentation and topic identification. In Proceedings of the 23rd Conference on Computational Natural Language Learning (CoNLL.), pages 582-592.
Daniel S. Hirschberg. 1975. A linear space algo- rithm for computing maximal common subsequences. Communications of the ACM, 1816333.

---

Meinard Müller. 2007. Dynamic time warping, Infor- mation retrieval for music and motion, pages 69-88 84.
Jack W Rae, Anna Potapenko, Siddhant M Jayakumar, and Timothy P Lillicrap. 2019. Compressive trans- formers for long-range sequence modelling. arXiv preprint arXiv:191 1.100507.
Eugene W Myers and Webb Miller. 1988. Optimal alignments in linear space. Bioinformatics, 4(1):11- 17.
Nils Reimers and Iryna Gurevych. 2019, Sentence-bert, Sentence embeddings using siamese bert-network In Proceedings of the 2019 Conference Empirical Methods in Natural Language Processing. Associa- tion for Computational Linguistics.
Iftekhar Naim, Daniel Gildea, Walter S Lasecki, Jef- frey P Bigham, et al. 2013. Text alignment for real- time crowd captioning, In HLT-NAACL, pages 201- 210.
Nils Reimers and Iryna Gurevych. 2020. Mak- ing monolingual sentence embeddings multilin- gual using knowledge distillation. arXiv preprint arXiv:2004.09811
Saul Needleman and Christian D Wunsch, 1970. general method applicable to the search for simi- larities in the amino acid sequence of two proteins. Journal of molecular biology, 48(3):443
Miguel A Sanchez- Perez, Grigori Sidorov, and Alexan- der F Gelbukh. 2014. A winning approach to text alignment for text reuse detection at pan 2014. CLEF ( (Working Notes), 2014:1004-1011
OpenAl. 2023. ChatGPT (March 23 Version). OpenAL. Retrieved April 2, 2023, from https: / www. openai. com.
Philippe Ortet and Olivier Bastien. 2010. Where does the alignment score distribution shape come from? Evolutionary Bioinformatics, 6:570-
Temple F Smith, Michael S Waterman, et al. 1981. Iden- tification of common molecular subsequences. Jour- nol of molecular biology, 147(1):195-197.
Seung-Bo Park, Heung-Nam Kim, Hyunsik Kim, and Geun-Sik Jo. 2010. Exploiting script-subtitls align- ment to scene boundary dectection in movie. In 2010 IEEE International Symposium Multimedia, pages 49-56. IEEE.
Šimon Suchomel, Jan Kasprzak, Michal Brandejs, et al. 2013. Diverse queries and feature type selection for plagiarism discovery. Notebook for PAN at CLEF 2013.
Mark A Sulzer, Amanda Haertling Thein, and Renita R Schmidt. 2018 What is adapted in youth adapta- tions?: A critical comparative content analysis of military memoirs repackaged as young adult litera- ture. Journal of Language and Literacy Education, 14(1):nl.
Stefan Paun. 2021. Parallel text aligament and monolin- gual parallel corpus creation from philosophical texts for text simplification. In Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Student Research Workshop, pages 40-46, Online. Associa- tion for Computational Linguisties.
Bingjun Sun, Prasenjit Mitra, C Lee Giles, John Yen. and Hongyuan Zha. 2007. Topic segmentation with shared topic detection and alignment of multiple doc- uments. In Proceedings of the 30th annual interna- tional ACM SIGIR conference on Research and de- velopment in information retrieval, pages 199-206.
William R Pearson. 1998. Empirical statistical esti- mates for sequence similarity searches. Journal of molecular biology. 276(1):71-8)
Jeffrey Pennington, Richard Socher, and Christopher D Manning, 2014, Glove: Global vectors for word rep- resentation. In Proceedings of the 2014 conference on empirical methods in natural language processing (EMNLP), pages 1532-1543.
Chi Sun, Xipeng Qiu, Yige Xu, and Xuanjing Huang. 2019. How to fine-tune bert for text classification? In Chinese Computational Linguistics: 18th China National Conference, CCL 2019, Kumming, China, October 18 18-20, 2019, Proceedings 18, pages 194- 206. Springer.
Tanzir Pial, Shahreen Salim, Charuta Pethe, Allen Kim, and Steven Skiena. 2023. Analyzing film adaptation through narrative alignment. In Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing (EMNIPP 2023). Association for Computational Linguistics.
Katherine Thai, Marzena Karpinska. Kalpesh Krishna, Bill Ray, Moira Inghilleri, John Wieting, and Mohit lyyer. 2022. Exploring document-level literary ma- chine translation with parallel paragraphs from world literature. arXiv preprint arXiv:22 12..1550...
Martin Potthast, Matthias Hagen. Tim Gollub, Martin Tippmann, Johannes Kiesel, Paolo Rosso, Efstathios Stamatatos, and Benno Stein. 2013. Overview of the 5th international competition on plagiarism de- tection. In CLEF Conference on Multilingual and Multimodal Information Access Evaluation, pages 301-331. CELCT.
Diego A Rodríguez Torrejón and José Manuel Martín Ramos. 2013. Text alignment module in coremo 2.1 plagiarism detector. Proceedings of the Confer- ence and Labs of the Evaluation Forum and Work- shop 13).
Raghavendra Udupa and Hemanta K Maji. 2006. Com- putational complexity of statistical machine transla- tion. In 1ith Conference of the European Chapter of
Friedrich Pukelsheim. 1994. The three sigma rule. The American Statistician, 48(2):88-91.

---

the Association for Computational Linguistics, pages 25-32.
Ismet Zeki Yalniz and Raghavan Manmatha. 2011. fast alignment scheme for automatic oct evaluation of books. In 2011 International Conference Doc- ument Analysis and Recognition, pages 754-758. ITEE.
Tariq Yousef and Stefan Janicke. 2020. A survey of text
alignment visualization. IEEE transactions on visu- alization and computer graphics, 27(2):1149-116 149-1199.

---

Appendix
have fitted the parameters of the Gumbel distribu- tion using alignment data of 2.5 10 unrelated pairs of books using the methodology discussed in Section 4.
A Generating Multiple Local Alignments
The optimal Smith-Watermin Waterman alignment can be ob- tained by backtracing on the dynamic programming (DP) matrix, starting from the highest-scoring cell. To obtain the second-best local alignment, the ini- tially aligned segments must be removed and the SW alignment DP matrix must be recomputed. But this is an inefficient method yielding a complexity of (qq x m x n) to compute the best alignments. Instead, we adopt a greedy approach to com- pute the alignments, where we backtrace from the current highest-scoring cell (rh, oa) and terminate backtracing when we encounter cell (ri, q) which either has score of 0 or its row rł or column qi is already part of a previous alignment. Thus we get the alignment a = (Th, Ct, F1 + 1, + 1). Every row r such that 1 < r S. T' and every column c such that < c S Cj are marked as part of the current alignment. We then relaunch backtracing from the next highest-scoring cell. This method has computational complexity of (mm (m))))) as we sort all the cells once first. It yields the exact alignment for the best local alignment and approxi- mations for the rest of the alignments.
C Local Alignments Can Capture Global Order
In this experiment we aim to investigate two phe- nomena of interest:
How SW can pick up weak noise alignments even for unrelated pairs of texts. This strength- ens the case for doing the statistical signifi- cance testing discussed in Section 4.
The capability of SW to capture global order despite primarily operating at the local level, thereby showcasing its potential applicability in scenarios requiring global alignments.
SW produces local alignments which capture re- gions of strong similarity, but collection of mul- tiple local alignments are not necessarily sequen- tial. It quite possible that SW generates two alignments a (Iais Tajs Yaps Yog), and 6 (aps, Tbjs Mbpp Mog) where (I < ( > Hbp). We hypothesize that local alignments of related pairs of books follow a similar sequence of events, and hence should be generally sequential. Con- versely, alignments of unrelated book pairs should yield matches appearing in arbitrary order.
B P-values of Chance Alignment
We investigate the probability of chance alignment by conducting an experiment involving various translations of Captain Hatteras by Jules Verne and The Decameron by Giovanni Boccaccio. We can reasonably expect the likelihood of obtaining aligmments as strong as those observed by chance would exhibit an increasing trend across the follow- ing comparison scenarios in order:
To test this hypothesis, we perform an experi- ment using 50 pairs of independently translated books from the RelBooks and the Classics Stories dataset (discussed in Section 5.1), plus 50 artifi- cially constructed pairs where we pair one book from each pair in RelBooks and Classic Stories against random book of similar length as the book they were originally paired with. As an ex- ample, the translations of the French novel Around the World in Eighty Days and the German novel Siddhartha form an unrelated pair.
Translations of the same book by different translators.
Translation of different parts of the same book by the same translator.
We then align all 100 book pairs using SW, selecting the top 20 alignments with the highest scores for each of them, and then compute the cor- relation between I; and Up for these alignments. In Figure 4 we can observe that the unrelated pairs show weaker correlation than the related pairs. This clearly shows that SW can create some alignments for even unrelated text sequences, otherwise we would not have been able to extract the top 20 align- ments for those pairs, underscoring the necessity of conducting statistical significance testing..
Translation of different parts of the same book by different translators.
Unrelated books.
We observe this pattern as anticipated in Table 6. To estimate these probabilities corresponding to the p-values, we utilize the cumulative distribution function (CDF) of the Gumbel distribution. We

---

On the other hand, the high correlation values for majority of the related books demonstrate that SW can effectively capture the global sequence events presented in the same order across both books.
50
D Manual Annotation for Fables Dataset
Cumutartvv frequency
The Fables dataset encompasses collection of 150 fable pairs, comprising a total of 2175 sentences. Our annotation process involved the initial anno- tation of the entire dataset by a primary annotator. To enhance the reliability of the annotations, a sec- ond human annotator was engaged to annotate randomly selected subset, accounting for 20% of the original dataset. The second set of annotation allowed us to gauge the subjectivity of the anno- tations and the level of difficulty of the task for both humans and automated systems. During ex- perimentation, we only used the annotation of the primary annotator.
10-
-0.75
-0.50
-0.25
0.00
0.25
0.50
0.75
1.00
Cornelation
Figure SW creates multiple local alignments instead of single global aligmment, but the events in two lated books should typically maintain the sequential order. We measure sequential agreement the corre- lation of paragraph number of book/ and the number of the paragraph aligns book2. K-S test reveals that the correlation value for alignments of related and unrelated pairs follow different distributions with sta- tistically significant p-value 2.08 x 10-7, The effect size of the difference between the two distributions is calculated to be 1.19 using Cohen's 's d, indicating a large effect size.
The annotators were presented with the pairs of fables, segmented into sentences, juxtaposed side-by-side. They were instructed to align each sentence of the first fable with corresponding sentence from the second fable mark it as un- aligned. Notably, the first fable within each pair originated from the same book and typically fea- tured greater length compared to the fables from other books. The cumulative count of sentences in the first fable across all pairs amounted to 1369, while the second fable encompassed 806 sentences. The primary annotator aligned 769 sentences and marked the remaining 600 sentences unaligned. For computing metrics presented in Table 5, define aligned sentence pairs as positive examples and everything else as negative examples. Table 7 shows an example alignment created by the pri- mary annotator for one pair of fables.
Figure Distribution SBERT cosine similarity scores between 100 million random pairs of paragraphs (μ = 0.097, a 0.099), with the corresponding nor- mal distribution (red curve). The CDF of the normal distribution is used as proxy to estimate the probability of obtaining a similarity score X by chance.

---

Book1
Book2
Relation
P-value
Alignment Score
The Voyages and Adventures of Captain Hatteras (Translator: Osgond, J. R.)
The English at the North Pole
Same book, different translators
1.85 x 10
42.96
Part of the Adventures of Captain Hatteras (Translator: Anonymous, Gutenberg ID: 22759)
The Voyages Adventures Captain Hatteras (Translator: Osgood. J. R.)
The Field of Part of Adventures Captain Hatteras (Publisher: Routledge, G)
Same book, different translators
1.17 10
35.42
The Decameron Volume II (Translator: Rigg, J. M.)
The Decameron (Day 6 Day 10) (Translator: Flo- rio, J)
Same book, different translators
6.02 10"29
20.98
The Decameron Volume (Translator: Rigg, M.)
The Decameron (Day to Day S) (Translator: Florio,
Same book, different translators
2.94 x 10 25
17.01
The Decameron Volume (Translator: Rigg, J. M.)
The Decameron Volume (Translator: Rigg. M.)
Different parts of book, same translator
2.19 10
16.40
The Decameron Volume (Translator: Rigg. J. M.)
The Decameron (Day 6 to Day 10) (Translator: Flo- rio, J)
Different parts of same book, different translator
7.12 x 10
13.25
The English at North Pole Part Adventures of
The Field Part of Adventures Captain Hatteras (Publisher: Routledge, G)
Different purts of same bnok, possihly different translator
5.45 x 10
Captain Hatteras (Translator: Anonymous,
Gutenberg ID: 22759)
The Decameron Volume (Translator: Rigg, J. M.)
The English the North Pole
Unrelated books
1.18 10-1
1.92
Part of the Adventures of Captain Hatteras (Translator: Anonymous, Gutenberg ID: 22759)
The Decameron Volume II (Translator: Rigg. J. M.)
The Field of Ice Part II of the Adventures of Captain Hatteras (Publisher: Routledge, G)
Unrelated books
2.99 x 10
1.60
Table 6: The p-value for finding alignment by chance goes up the strength of relatedness between books decrease. The probabilities are calculated using the Gumbel distribution fitted using methodology discussed in Section 4. The null hypothesis this context is that the alignments come from unrelated text sequences.

---

Sentence
Fable
Alignment
Fable
Annotation
0
A Gnat flew over the meadow with much buzzing for so small a creature and settled
(0, 0)
A Gnat alighted on one of the horns of Bull, and remained sitting there for considerable time.
on the tip of one of the horns of Bull.
After he had rested short time, he made ready fly away.
1)
When it had rested sufficiently and about fly away, said the Bull, "Do you mind if go now?"
2 But before he left he begged the Bull's par- don for having used his horn for a resting place.
(2, -1)
The Bull merely raised his eyes and remarked, without interest, "It's all one to me; didn't notice when you came, and I shan't know when you away.
3
"You must be very glad have go now,"
(3,
"We may often be of more consequence eyes than in the eyes of our neighbours.
he said.
all same me," replicd the Bull.
(4,
5
"I did not even know you were there."
(5, 2)
6
We often of greater importance eyes than the eyes of neigh- bor. The smaller the mind the greater the conceit._
Table Example alignment created by human annotator for Aesop's 's fable "The Gnat and the Bull". The pair -1) in the third column denotes that the annotator decided to let sentence of Fable remain unaligned.

---

Prompt
Given two texts tl and f2 in the form of numbered list of sentenees, list the semantically similar sentence pairs using their numbers the form (i.j) where 0 <= i 7 and O <= < where the first sentence of the pair from tI and the second sentenee of the pair comes from 12. tl has 7 sentences and 12 has sentences, Do not include anything other than the list of pairs in your response.
0. A Boy was given permission to put his hand into pitcher get filberts.
1. But he took such great fistful that he could draw his hand again.
2. There he stood, unwilling give up single filbert and yet unable to get them all once.
3. Vexed and disappointed he hegan to cry.
"My boy," said mother, "be satisfied with half nuts you taken and you will easily get your hand out.
5. Then perhaps you may have some
filberts some other time."
6. _Do not attempt too much at once._.
0. A Boy put hand into jar Filberts, and grasped as many as could possibly hold.
But when he tried to pull out again, found couldn't 't do so, for the neck the jar was too small allow of
passage of so large a handfuul.
2. Unwilling to lose his nuts
unable to withdraw his hand. he burst into tears. 3. A hystander, who saw where the trouble lay, said him, "Come, my boy, don't so greedy: he content with half amount, and you'll IIlll be able to get your hand out without difficulty."
4. not attempt too much at once.
Output:
(0, 0)
(1, 1)
(2, 1)
(3, 2)
(4, 3)
(6, 4)
Given two texts (1 and (2 in the form of numbered list of sentences, list the semantically similar sentence pairs using their numbers in the form (i.j) where 0 <= i< and 0 <=j < where the first sentence of the pair comes from II and the second sentence of the pair comes from 12. tl has 5 sentences and 12 has 3 sentences. Do not include anything other than the list of pairs in your response.
11:
0. A Cock was busily scratching and scraping about to find something to cat for himself and his family, when he happened
to turn up a precious jewel that had been lost by its owner.
1. "Aha!" said the Cock.
2. "No doubt you very costly and he who lost you would give great deal to find you,
3. But for would choose single grain of barley before all the jewels in the world."
4. PPeecious things without value those who cannot prize them._.
12:
0. A Cock, scratching the ground for something to cat, turned up Jewel that had by chance been dropped there.
1. "Ho!" said he, fine thing you are, no doubt, and, had your owner found you, great would his joy have heen.
2. But for me! give single grain of before all the jewels in the world."
Output:
ChatGPT Response
GNAT
Human Annotation
(0, 0)
(0, 0)
1)
(1.0)
(1,
(2,
(2,
2)
(3, 2)
(3, 2)
(4, I)
Table 8: In the prompt, we provide an example input pair of fables and their corresponding alignment following which we instruct ChatGPT to create alignment for the next pair of fables. The human annotation keeps sentence of fable unaligned but ChatGPT incorrectly aligns it with sentence I of fable 2. In the prompt, the example alignment also has an instance where the gold alignment keeps sentence unaligned (sentence # 5). We allow GNAT to do many-to-many matching here by slightly modifying the recurrence in Equation I.


Reviews:
[{"review_id": "HqnXj0c3AK", "reviewer": "Reviewer_Abc9", "summary": "", "questions": "* how easy is it to extend this work to other languages, particularly languages with more complex \nand rich morphology? can you elaborate on generalizability to other languages?\n", "limitations": "", "rating": 4, "confidence": 3, "soundness": 4, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your detailed and favorable review. \n\nThe generalizability to other languages is indeed an interesting research direction we intend to explore in future. The two main components are the core alignment algorithm, Smith-Waterman (SW) in our case, and the similarity metric employed by SW. The core alignment algorithm can be applied to any language without any modification as we show how SW can work for both the bioinformatics and the NLP domain. \n\nThus the similarity metrics are the challenging part for alignment in other languages. The strongest metric we explored, SBERT embeddings, require a similar model for the specific language we want to align text from.  SBERT models for popular languages other than English are available in Huggingface (e.g., KR-SBERT-V40K-klueNLI-augSTS for Korean, sbert-cased-finnish-paraphrase for Finnish, etc). For languages with limited resources and no pre-trained models, \"Making Monolingual Sentence Embeddings Multilingual using Knowledge Distillation\" by Reimer and Gurevych can be an excellent starting point. This rationale also holds true for the GloVe Mean Embedding approach we employed.\n\nFor the other three metrics, a simple way can be to extract the root/stem of each individual word and compare them. We believe these should suffice for simple alignments.  We will try to add some small/qualitative experiments on this issue for the camera-ready version of the paper upon acceptance.\n\nTo summarize, applying GNAT for the most popular languages should be straight-forward when SBERT or similar embedding models are available. There are fairly simple ways for modifying the algorithm for applying it to morphologically rich languages with limited resources. but more experiments need to be performed to ascertain the degree of generalizability of GNAT as a tool for low-resource languages.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "* well written paper.\n* interesting problem applied to a number of domains/tasks \n* tools will be public\n* data will be public\n", "reasons_to_reject": "Hard to find a reason. Perhaps, it is unclear how well this work generalizes beyond English?", "questions_to_authors": "* how easy is it to extend this work to other languages, particularly languages with more complex \nand rich morphology? can you elaborate on generalizability to other languages?\n", "paper_topic_and_main_contributions": "The paper presents an extensive collection of experiments on the \nquestion of automatic text alignments for text pairs under different \ntask contexts.  The authors created annotated data for the different\ntasks an d compared a number of alignment techniques on them.\nThe tools and data will be public.", "excitement": 4, "reproducibility": 3, "ethical_concerns": "No", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"Missing_References": "N/A", "Typos_Grammar_Style_and_Presentation_Improvements": "Missing period:\n313  gap penalty However,  \n"}, "extra_text": {}}, {"review_id": "CZY9eEeGFy", "reviewer": "Reviewer_jEsz", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 3, "soundness": 4, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the favorable review. Even though no direct questions were given, we briefly address the point of GNAT requiring computational power. \n\nFor small texts, SBERT will be slightly slower on CPU but still can be worked with. For longer texts like classic books, we plan to keep embeddings stored on our side for the web tool lowering the burden on the user side. In any other case, Jaccard similarity always remains a strong candidate in low resource scenarios.   Indeed, we intend to provide for the costs of maintaining an online web server to support interested users experimenting with such computations using CPU, in addition to making the code available so the user can run on their end using GPU as needed.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "The paper can be accepted for the following reasons: the authors offer a tool that anyone can use without effort and evaluate it on the four different domains. The research lies on the intersection of bioinformatics and text similarity metrics from NLP. The title and abstract are correctly selected and written. The paper is correctly structured, easy to follow. Pictures and tables are relevant and clearly explained.", "reasons_to_reject": "GNAT requires a computational power; therefore, it may restrict users (especially when GPU unavailable) to use this tool. ", "questions_to_authors": "", "paper_topic_and_main_contributions": "There are exists different methods to identify similar segments between original documents, but it is difficult to find similarities between distant versions of narratives. The authors propose a tool for narrative text alignment based on the Smith-Waterman algorithm from bioinformatics with text similarity metrics called GNAT. \nGNAT is a general narrative alignment tool can be applied to compare texts to find similar segments for any domain. The authors do experiments on four problem domains such as summary-to-book alignment, translated book alignment, short story alignment, and plagiarism detection.", "excitement": 4, "reproducibility": 5, "ethical_concerns": "No", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "SwS3Pl0Cus", "reviewer": "Reviewer_ynEf", "summary": "", "questions": "Sect. 4.1 describes their sampling-based method for computing the statistical significance of algnments. To do that, they use a Gumbel distribution whose parameters were estimated empirically by pairing 1K unrelated books at the paragraph level. My question is: at what level this selection of granularities (books aligned a paragraph level) may influence the figures obtained if we are calculating the statistical significance of algning, for example, short texts at word or phrase level (i.e. completely different granularities). ", "limitations": "", "rating": 4, "confidence": 3, "soundness": 4, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your comprehensive review. \n\nWe have not yet done experiments with smaller granularity levels for the statistical significance testing, such as measuring statistical significance of alignment at the word level between short texts. In theory, our sampling based method should still work in this case, but we estimate that shorter texts probably will yield less statistical power to correctly recognize distant alignments. If the paper is accepted, we will add some experiments/discussion in the camera-ready version on how different granularity levels affect the sampling based method's applicability. We thank you for bringing up the point of granularity level for statistical significance testing as we think it is an interesting question to explore. \n\nWe agree with the presentation improvement suggestions provided by the reviewer. If the paper gets accepted, we will incorporate all the suggestions in the camera-ready version—and look forward to an additional page to do with!", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "Quite well-structured.\nWell-written and easy to read (although a little more space would be of great help to concatenate the text properly).\nNot novel by itself, but the authors apply existing concepts and techniques to a different context in a novel way.\nThe possibility of computing statistical significant scores for narrative alignment sounds great.\nWide evaluation experiments.", "reasons_to_reject": "I see no special reasons for it.\n", "questions_to_authors": "Sect. 4.1 describes their sampling-based method for computing the statistical significance of algnments. To do that, they use a Gumbel distribution whose parameters were estimated empirically by pairing 1K unrelated books at the paragraph level. My question is: at what level this selection of granularities (books aligned a paragraph level) may influence the figures obtained if we are calculating the statistical significance of algning, for example, short texts at word or phrase level (i.e. completely different granularities). ", "paper_topic_and_main_contributions": "The paper presents GNAT (for General Narrative Alignment Tool), a new algorithmic sequence alignment proposal for narrative alignment. The authors try to extend both the techniques (e.g. Smith-Waterman local alignment algorithm) and the rigour/formality of the sequence analysis techniques used in Bioinformatics (e.g. for gene-to-gene comparisons) to the case of general narrative texts. They have paid attention to the case of distant but semantically similar texts (e.g. translations), applicability when dealing not only with similar but dissimilar granularities (e.g. complete texts vs. summaries), also designing a methodology for computing the statistical significance of the text alignments obtained.\n\n\nTheir approach is empirically tested with 5 distinct distance metrics (cosine similarity on SBERT embeddings, Jaccard coefficient, TF-IDF, cosine similarity on GloVe Mean embeddings and Hamming Distance) on 4 distinct application domains (summary-to-book alignment, translated book alignment, plagiarism detection and short story alignment) and 4 datasets of different nature. In order to allow proper comparation between the results obtained with different scoring functions, a unification function is proposed.\n\n\nThe authors make a good and illustrative introduction to the task and its associated problems and defficiencies. \n\nThe Section \"Related Work\" is ok, since it covers the different aspects of this work as best as they can, taking into account the space limits they have to deal with. \n\nTheir major contributions are clearly stated, although their \"primary\" motivation, as stated in the Sect. \"Limitations\" is to create a general purpose alignment tool that anyone can use out-of-the-box with minimal effort.\n\nThe possibility of computing statistical significant scores on the resulting alignments is specially interesting. They propose a sampling-based method based on a Gumble distribution whose parameters were estimated empirically. \n\nThe results obtained are encouraging and seem to support the validity of their approach.  \n\nThe tool and the evaluation datasets they have used will be publicly released. ", "excitement": 4, "reproducibility": 3, "ethical_concerns": "No", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"Missing_References": "No missing references. In fact, the number of references is quite large, maybe a little too large.\n"}, "extra_text": {"Typos_Grammar_Style_and_Presentation_Improvements": "* Sect. 1 \"Introduction\" is too long and goes beyond a mere introduction to the paper. The autors should re-structure and split it (for instance, from l. 113 on)  \n* Figure 1 is not referenced in the text.\n* The same for Table 1.\n* Sect. 3.1, l.310: you have not previously explained in the textwhat function H is.\n* Sect. 3.1, l.313: missing point in \"gap penalty However\"\n* Sect. 4.1, l.449: \"gumbel\" --> \"Gumbel\"\n* Sect. 5.1, l.462-463: when introducing Project gutemberg, a footnote with its URL and last access date is enough, if not better. Don't add a bib. reference for it.\n* caption of Figure 3: \"corrleation\" -> \"correlation\"\n\n* Sect. \"References\": \n     - some missed uppercases here and there\n     - when using name initials (e.g. l.632, 683), you must homogeinize the use (or not) of .\n     - \"remains\" of old copy-pastes in l.642, 857"}}]

Author rebuttal:

Meta-review: The reviewers agree that the paper is sound and exciting. Several reviewers mention the paper's writing is easy to understand and the paper is generally well-written. The paper promises to release its tools and data, which will help other researchers reproduce and build upon this work. Reviewers generally do not find issues with the paper. There was one concern about computational requirements, but the authors addressed the concerns during the author response period.
Decision: Accept-Main