{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T11:29:08Z","timestamp":1750159748009,"version":"3.37.3"},"reference-count":24,"publisher":"Oxford University Press (OUP)","issue":"2","license":[{"start":{"date-parts":[[2021,10,14]],"date-time":"2021-10-14T00:00:00Z","timestamp":1634169600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/academic.oup.com\/journals\/pages\/open_access\/funder_policies\/chorus\/standard_publication_model"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2022,5,25]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>This article presents an approach to the collation problem of text witnesses which is correct for all distance functions and is applicable to the alignment of any types of tokens, be it letters, words, sentences, or paragraphs. In contrast to the existing approaches, which all are heuristics in nature, we specify a formal model in the form of an integer linear program (ILP) that formally describes the optimization problem. For a special case that usually occurs in practice, we then transfer the ILP into an efficient algorithm that optimally solves the alignment problem. In the second part of the article, we apply our approach to the alignment of paragraphs of text witnesses\u2014an alignment problem that has received little attention in the literature so far\u2014and compare the results of our approach, which we have called TSaligner, with those of CollateX.<\/jats:p>","DOI":"10.1093\/llc\/fqab058","type":"journal-article","created":{"date-parts":[[2021,5,28]],"date-time":"2021-05-28T19:19:35Z","timestamp":1622229575000},"page":"375-390","source":"Crossref","is-referenced-by-count":2,"title":["Putting collation of text witnesses on a formal basis"],"prefix":"10.1093","volume":"37","author":[{"given":"Janis","family":"D\u00e4hne","sequence":"first","affiliation":[{"name":"Institute for Computer Science, Martin Luther University Halle-Wittenberg , Halle, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marcus","family":"P\u00f6ckelmann","sequence":"additional","affiliation":[{"name":"Institute for Computer Science, Martin Luther University Halle-Wittenberg , Halle, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"J\u00f6rg","family":"Ritter","sequence":"additional","affiliation":[{"name":"Institute for Computer Science, Martin Luther University Halle-Wittenberg , Halle, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1461-7936","authenticated-orcid":false,"given":"Paul","family":"Molitor","sequence":"additional","affiliation":[{"name":"Institute for Computer Science, Martin Luther University Halle-Wittenberg , Halle, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2021,10,14]]},"reference":[{"issue":"1","key":"2022053116092969500_fqab058-B1","doi-asserted-by":"crossref","first-page":"29","DOI":"10.1515\/editio-2015-004","article-title":"Zum Einsatz digitaler Methoden bei der Erstellung und Nutzung genetischer Editionen gedruckter Texte mit verschiedenen Fassungen (in German)","volume":"29","author":"Bremer","year":"2015","journal-title":"Editio"},{"issue":"2","key":"2022053116092969500_fqab058-B2","doi-asserted-by":"crossref","first-page":"254","DOI":"10.1093\/llc\/fqz029","article-title":"FAST: Fast and accurate synoptic texts","volume":"35","author":"Brill","year":"2019","journal-title":"Digital Scholarship in the Humanities"},{"volume-title":"Introduction to Algorithms","year":"2009","author":"Cormen","key":"2022053116092969500_fqab058-B6"},{"year":"2020","key":"2022053116092969500_fqab058-B5"},{"key":"2022053116092969500_fqab058-B8","first-page":"254","volume-title":"Art and Error: Modern Textual Editing","author":"Dearing","year":"1970"},{"volume-title":"Supporting Digital Humanities: Answering the Unaskable,","year":"2011","author":"Dekker","key":"2022053116092969500_fqab058-B9"},{"issue":"3","key":"2022053116092969500_fqab058-B10","doi-asserted-by":"crossref","first-page":"452","DOI":"10.1093\/llc\/fqu007","article-title":"Computer-supported collation of modern manuscripts: CollateX and the Beckett Digital Manuscript Project","volume":"30","author":"Dekker","year":"2014","journal-title":"Digital Scholarship in the Humanities"},{"volume-title":"La Critique Des Textes et Son Automatisation","year":"1968","author":"Froger","key":"2022053116092969500_fqab058-B11"},{"first-page":"253","volume-title":"Kinder- und Haus-M\u00e4rchen, Band 1, 1. Auflage.","year":"1812","key":"2022053116092969500_fqab058-B3"},{"year":"1857","key":"2022053116092969500_fqab058-B4","first-page":"281"},{"volume-title":"Aus den Knabenzeit","year":"1852","author":"Gutzkow","key":"2022053116092969500_fqab058-B12"},{"volume-title":"Gesammelte Werke. 2. Ausgabe, 1. Serie, Band 1","year":"1873","author":"Gutzkow","key":"2022053116092969500_fqab058-B13"},{"key":"2022053116092969500_fqab058-B14","first-page":"247","volume-title":"Kleine Romane und Erz\u00e4hlungen","author":"Gutzkow","year":"1874"},{"key":"2022053116092969500_fqab058-B15","first-page":"1","volume-title":"Vergangene Tage","author":"Gutzkow","year":"1852"},{"issue":"22","key":"2022053116092969500_fqab058-B16","first-page":"10915","article-title":"Amino acid substitution matrices from protein blocks","volume":"89","author":"Henikoff","year":"1992"},{"issue":"142","key":"2022053116092969500_fqab058-B17","first-page":"547","article-title":"\u00c9tude comparative de la distribution florale dans une portion des Alpes et des Jura","volume":"37","author":"Jaccard","year":"1901","journal-title":"Bulletin de la Soci\u00e9t\u00e9 Vaudoise des Sciences Naturelles"},{"year":"2020","key":"2022053116092969500_fqab058-B18"},{"first-page":"957","year":"2015","author":"Kusner","key":"2022053116092969500_fqab058-B19"},{"issue":"8","key":"2022053116092969500_fqab058-B21","first-page":"707","article-title":"Binary codes capable of correcting deletions, insertions, and reversals","volume":"10","author":"Levenshtein","year":"1966","journal-title":"Soviet Physics Doklady"},{"first-page":"302","year":"2014","author":"Levy","key":"2022053116092969500_fqab058-B22"},{"year":"2013","author":"Mikolov","key":"2022053116092969500_fqab058-B23"},{"issue":"3","key":"2022053116092969500_fqab058-B24","doi-asserted-by":"crossref","first-page":"443","DOI":"10.1016\/0022-2836(70)90057-4","article-title":"A general method applicable to the search for similarities in the amino acid sequence of two proteins","volume":"48","author":"Needleman","year":"1970","journal-title":"Journal of Molecular Biology"},{"issue":"2","key":"2022053116092969500_fqab058-B25","first-page":"61","article-title":"From giant despair to a new heaven: The early years of automatic collation","volume":"62","author":"Nury","year":"2020","journal-title":"Information Technology"},{"year":"2020","key":"2022053116092969500_fqab058-B20"}],"container-title":["Digital Scholarship in the Humanities"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/dsh\/article-pdf\/37\/2\/375\/43842770\/fqab058.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/dsh\/article-pdf\/37\/2\/375\/43842770\/fqab058.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,5,31]],"date-time":"2022-05-31T16:23:49Z","timestamp":1654014229000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/dsh\/article\/37\/2\/375\/6397019"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,10,14]]},"references-count":24,"journal-issue":{"issue":"2","published-online":{"date-parts":[[2021,10,14]]},"published-print":{"date-parts":[[2022,5,25]]}},"URL":"https:\/\/doi.org\/10.1093\/llc\/fqab058","relation":{},"ISSN":["2055-7671","2055-768X"],"issn-type":[{"type":"print","value":"2055-7671"},{"type":"electronic","value":"2055-768X"}],"subject":[],"published-other":{"date-parts":[[2022,6,1]]},"published":{"date-parts":[[2021,10,14]]}}}