In markup languages and the digital humanities, overlap occurs when a document has two or more structures that interact in a non-hierarchical manner. A document with overlapping markup cannot be represented as a tree. This is also known as concurrent markup. Overlap happens, for instance, in poetry, where there may be a metrical structure of feet and lines; a linguistic structure of sentences and quotations; and a physical structure of volumes and pages and editorial annotations.
The problem of non-hierarchical structures in documents has been recognised since 1988; resolving it against the dominant paradigm of text as a single hierarchy (an ordered hierarchy of content objects or OHCO) was initially thought to be merely a technical issue, but has, in fact, proven much more difficult. In 2008, Jeni Tennison identified markup overlap as "the main remaining problem area for markup technologists". Markup overlap continues to be a primary issue in the digital study of theological texts in 2019, and is a major reason for the field retaining specialised markup formats—the Open Scripture Information Standard and the Theological Markup Language—rather than the inter-operable Text Encoding Initiative-based formats common to the rest of the digital humanities.
Properties and types
A distinction exists between schemes that allow non-contiguous overlap, and those that allow only contiguous overlap. Often, 'markup overlap' strictly means the latter. Contiguous overlap can always be represented as a linear document with milestones (typically co-indexed start- and end-markers), without the need for fragmenting a (logical) component into multiple physical ones. Non-contiguous overlap may require document fragmentation. Another distinction in overlapping markup schemes is whether elements can overlap with other elements of the same kind (self-overlap).
A scheme may have a privileged hierarchy. Some XML-based schemes, for example, represent one hierarchy directly in the XML document tree, and represent other, overlapping, structures by another means; these are said to be non-privileged.
Schmidt (2012) identifies a tripartite classification of instances of overlap: 1. "Variation of content and structure", 2. "Overlay of multiple perspectives or markup sets", and 3. "Overlap of individual start and end tags within a single markup perspective"; additionally, some apparent instances of overlap are in fact schema definition problems, which can be resolved hierarchically. He contends that type 1 is best resolved by a system of multiple documents external to the markup, but types 2 and 3 require dealing with internally.
Approaches and implementations
DeRose (2004, Evaluation criteria) identifies several criteria for judging solutions to the overlap problem:
- readability and maintainability,
- tool support and compatibility with XML,
- possible validation schemes, and
- ease of processing.
Tag soup is, strictly speaking, not overlapping markup—it is malformed HTML, which is a non-overlapping language, and may be ill-defined. Some web browsers attempted to represent overlapping start and end tags with non-hierarchical Document Object Models (DOM), but this was not standardised across all browsers and was incompatible with the innately hierarchical nature of the DOM. HTML5 defines how processors should deal with such mis-nested markup in the HTML syntax and turn it into a single hierarchy. With XHTML and SGML-based HTML, however, mis-nested markup is a strict error and makes processing by standards-compliant systems impossible. The HTML standard defines a paragraph concept which can cause overlap with other elements and can be non-contiguous.
SGML, which early versions of HTML were based on, has a feature called CONCUR that allows multiple independent hierarchies to co-exist without privileging any. DTD validation is only defined for each individual hierarchy with CONCUR. Validation across hierarchies is not defined by the standard. CONCUR cannot support self-overlap, and it interacts poorly with some of SGML's abbreviatory features. This feature has been poorly supported by tools and has seen very little actual use; using CONCUR to represent document overlap was not a recommended use case, according to a commentary by the standard's editor.
Within hierarchical languages
There are several approaches to representing overlap in a non-overlapping language. The Text Encoding Initiative, as an XML-based markup scheme, cannot directly represent overlapping markup. All four of the below approaches are suggested. The Open Scripture Information Standard is another XML-based scheme, designed to mark up the Bible. It uses empty milestone elements to encode non-privileged components.
To illustrate these approaches, marking up the sentences and lines of a fragment of Richard III by William Shakespeare will be used as a running example. Where there is a privileged hierarchy, the lines will be used.
Multiple documents can each provide different internally consistent hierarchies. The advantage of this approach is that each document is simple and can be processed with existing tools, but requires maintenance of redundant content and it can be difficult to cross-reference between different views. With multiple documents, the overlap can be analysed with data comparison and delta encoding techniques, and, in an XML context, specific XML tree differencing algorithms are available.
Schmidt (2012, 3.5 Variation) recommends this approach for encoding multiple variants of a single text and to accept the duplication of the parts which do not vary, rather than attempting to create a structure that represents all of the variation present; further, he suggests that this alignment be performed automatically, and that misalignment is rare in practice.
Example, with lines marked up:
<line>I, by attorney, bless thee from thy mother,</line> <line>Who prays continually for Richmond's good.</line> <line>So much for that.—The silent hours steal on,</line> <line>And flaky darkness breaks within the east.</line>
With sentences marked up:
<sentence>I, by attorney, bless thee from thy mother, Who prays continually for Richmond's good.</sentence> <sentence>So much for that.</sentence><sentence>—The silent hours steal on, And flaky darkness breaks within the east.</sentence>
Milestones are empty elements that mark the beginning and end of a component. These can be used to embed a non-privileged structure within a hierarchical language, and can only represent contiguous overlap. Existing tools will also not understand the meaning of the milestone elements and so cannot easily process or validate the non-privileged structure. The markup being near the content is an advantage for maintainability and readability. CLIX (DeRose 2004) is an example of such an approach.
<line><sentence-start />I, by attorney, bless thee from thy mother,</line> <line>Who prays continually for Richmond's good.<sentence-end /></line> <line><sentence-start />So much for that.<sentence-end /><sentence-start />—The silent hours steal on,</line> <line>And flaky darkness breaks within the east.<sentence-end /></line>
Punctuation and spaces have been identified as a type of milestone-style 'crypto-overlap' or 'pseudo-markup', as the boundaries of words, clauses, sentences and the like do not necessarily align with the formal markup boundaries hierarchically.
Joins are pointers within a privileged hierarchy to other components of the privileged hierarchy, which may be used to reconstruct a non-privileged component akin to following a linked list. A single non-privileged element is segmented into several partial elements within the privileged hierarchy; the partial elements themselves do not represent a single unit in the non-privileged hierarchy, which can be misleading and make processing difficult. While this approach can support some discontiguous structures, it is not able to re-order elements. A slightly different approach can, however, express re-ordering by expressing the join away from the content, at the cost of directness and maintainability.
Join-based representations can introduce the possibility of cycles between elements; detecting and rejecting these adds complexity to implementations.
<line><sentence id="a">I, by attorney, bless thee from thy mother,</sentence></line> <line><sentence continues="a">Who prays continually for Richmond's good.</sentence></line> <line><sentence id="b">So much for that.</sentence><sentence id="c">—The silent hours steal on,</sentence></line> <line><sentence continues="c">And flaky darkness breaks within the east.</sentence></line>
Stand-off markup is similar to using joins, except that there is no privileged hierarchy: each part of the document is given a label (or might be referred to by an offset), and the document is constructed by pointing to the content from markup that 'stands off' from the content (possibly in an entirely different file), and might contain no content itself. The TEI guidelines identify the unity of the elements as a primary advantage of stand-off markup over joins, in addition to the ability to produce and distribute the annotations separately from the text, possibly even by different authors applying markup to a read-only document, allowing collaborative approaches to markup by a divide and conquer strategy.
Validation of stand-off markup is very challenging. In addition, maintenance may be a problem, though Eggert & Schmidt report that separating markup and text can result in overall simplification and increased maintainability.
<span id="a">I, by attorney, bless thee from thy mother,</span> <span id="b">Who prays continually for Richmond's good.</span> <span id="c">So much for that.</span><span id="d">—The silent hours steal on,</span> <span id="e">And flaky darkness breaks within the east.</span> ... <line contents="a" /> <line contents="b" /> <line contents="c d" /> <line contents="e" /> <sentence contents="a b" /> <sentence contents="c" /> <sentence contents="d e" />
Another approach is to design an entirely new markup language. These forego the tool support in existing languages for a less complicated semantic model and more convenient syntax.
- LMNL is a non-hierarchical markup language first described in 2002 by Jeni Tennison and Wendell Piez, annotating ranges of a document with properties and allowing self-overlap. CLIX, which originally stood for 'Canonical LMNL In XML', provides a method for representing any LMNL document in a milestone-style XML document. It also has another XML serialisation, xLMNL.
- MECS was developed by the University of Bergen's Wittgenstein Archive. However, it had several problems: it allowed some non-sensical documents of overlapping elements, it could not support self-overlap, and it did not have the capacity to define a DTD-like grammar. The theory of General Ordered-Descendant Directed Acyclic Graphs (GODDAGs), while not strictly a markup language itself, is a general data model for non-hierarchical markup. Restricted GODDAGs were designed specifically to match the semantics of MECS; general GODDAGs may be non-contiguous and need a more powerful language. TexMECS is a successor to MECS, which has a formal grammar and is designed to represent every GODDAG and nothing that is not a GODDAG.
- XCONCUR (previously MuLaX) is a melding-together of XML and SGML's CONCUR, and also contains a validation language, XCONCUR-CL, and a SAX-like API.
- Marinelli, Vitali and Zacchiroli provide algorithms to convert between restricted GODDAGs, ECLIX, LMNL, parallel documents in XML, contiguous stand-off markup and TexMECS.
Rather than grounding markup information in a tree, standoff XML employs a data model based on directed graphs. As an alternative to traditional markup, such graph-based data models can be represented with formalisms originally developed for generalised directed multigraphs, most notably the Resource Description Framework (RDF). EARMARK is an early RDF/OWL representation that encompasses GODDAGs.
RDF provides different linearisations, including an XML format that can be modeled to mirror conventional standoff XML, and a linearization that lets RDF be expressed in XML attributes (RDFa). But while it is semantically equivalent to standoff XML, it does not require special-purpose technology for storing, parsing and querying. Multiple interlinked RDF files representing a document or a corpus may constitute an example of Linguistic Linked Open Data.
Eggert & Schmidt describe encoding a corpus (the Charles Harpur Critical Archive) using 'multi-version documents' (MVD) to represent the variant versions of documents and as a means of indicating additions, deletions and revisions using a tactical combination of multiple documents and stand-off ranges within an underlying graph-based model. MVD is presented as an application file format, requiring specialised tools to view or edit.
- Text Encoding Initiative.
- DeRose 2004, The problem types.
- Piez 2014.
- Renear, Mylonas & Durand 1993.
- Tennison 2008.
- MoChridhe 2019.
- Hickson 2002.
- Sivonen 2003.
- HTML, § 8.2.8 An introduction to error handling and strange cases in the parser.
- Sperberg-McQueen & Huitfeldt 2000, 2.1. Non-SGML Notations.
- HTML, § 18.104.22.168 Paragraphs.
- Sperberg-McQueen & Huitfeldt 2000, 2.2. CONCUR.
- DeRose 2004, SGML CONCUR.
- Di Iorio, Peroni & Vitali 2009.
- Text Encoding Initiative, § 20 Non-hierarchical Structures.
- Durusau 2006.
- Text Encoding Initiative, § 20.1 Multiple Encodings of the Same Information.
- Schmidt 2009.
- La Fontaine 2016.
- Schmidt 2012, 4.1 Automating Variation.
- Text Encoding Initiative, § 20.2 Boundary Marking with Empty Elements.
- Sperberg-McQueen & Huitfeldt 2000, 2.4. Milestones.
- DeRose 2004, TEI-style milestones.
- Birnbaum & Thorsen 2015.
- Haentjens Dekker & Birnbaum 2017.
- Text Encoding Initiative, § 20.3 Fragmentation and Reconstitution of Virtual Elements.
- DeRose 2004, Segmentation.
- Sperberg-McQueen & Huitfeldt 2000, 2.5. Fragmentation.
- DeRose 2004, Joins.
- Text Encoding Initiative, § 20.4 Stand-off Markup.
- Schmidt 2012, 4.2 Markup Outside the Text.
- Sperberg-McQueen & Huitfeldt 2000, 2.6. Standoff Markup.
- DeRose 2004.
- Eggert & Schmidt 2019, Conclusion.
- DeRose 2004, CLIX and LMNL.
- Piez 2012.
- Sperberg-McQueen & Huitfeldt 2000, 2.7. MECS.
- Sperberg-McQueen & Huitfeldt 2000.
- Huitfeldt & Sperberg-McQueen 2003.
- Hilbert, Schonefeld & Witt 2005.
- Witt et al. 2007.
- Schonefeld 2008.
- Marinelli, Vitali & Zacchiroli 2008.
- Ide & Suderman 2007.
- Cassidy 2010.
- Chiarcos 2012.
- Eggert & Schmidt 2019.
- Birnbaum, David J; Thorsen, Elise (2015). Markup and meter: Using XML tools to teach a computer to think about versification. Balisage: The Markup Conference 2015. Montréal. doi:10.4242/BalisageVol15.Birnbaum01.
- Cassidy, Steve (2010). An RDF realisation of LAF in the DADA annotation server (PDF). Proceedings of ISA-5. Hong Kong. CiteSeerX 10.1.1.454.9146.
- Chiarcos, Christian (2012). POWLA: Modeling linguistic corpora in OWL/DL (PDF). Proceedings of the 9th Extended Semantic Web Conference (ESWC 2012, Heraklion, Crete; LNCS 7295). pp. 225–239. doi:10.1007/978-3-642-30284-8_22. Retrieved 2016-05-24.
- DeRose, Steven (2004). Markup Overlap: A Review and a Horse. Extreme Markup Languages 2004. Montréal. CiteSeerX 10.1.1.108.9959. Retrieved 2014-10-14.
- Di Iorio, Angelo; Peroni, Silvio; Vitali, Fabio (August 2009). Towards markup support for full GODDAGs and beyond: the EARMARK approach. Balisage: The Markup Conference 2009. Montréal. doi:10.4242/BalisageVol3.Peroni01.
- Eggert, Paul; Schmidt, Desmond A (2019). "The Charles Harpur Critical Archive: A History and Technical Report". International Journal of Digital Humanities. 1 (1). Retrieved 2019-03-25.
- Haentjens Dekker, Ronald; Birnbaum, David J (2017). It's more than just overlap: Text As Graph. Balisage: The Markup Conference 2017. Montréal. doi:10.4242/BalisageVol19.Dekker01.
- Durusau, Patrick (2006). OSIS Users Manual (OSIS Schema 2.1.1) (PDF). Archived from the original (PDF) on 2014-10-23. Retrieved 2014-10-14.
- Ian Hickson (2002-11-21). "Tag Soup: How UAs handle <x> <y> </x> </y>". Retrieved 2017-11-05.
- Hilbert, Mirco; Schonefeld, Oliver; Witt, Andreas (2005). Making CONCUR work. Extreme Markup Languages 2005. Montréal. CiteSeerX 10.1.1.104.634. Retrieved 2014-10-14.
- Huitfeldt, Claus; Sperberg-McQueen, C M (2003). "TexMECS: An experimental markup meta-language for complex documents". Archived from the original on 2017-02-27. Retrieved 2014-10-14.
- La Fontaine, Robin (2016). Representing Overlapping Hierarchy as Change in XML. Balisage: The Markup Conference 2016. Montréal. doi:10.4242/BalisageVol17.LaFontaine01.
- Marinelli, Paolo; Vitali, Fabio; Zacchiroli, Stefano (January 2008). "Towards the unification of formats for overlapping markup" (PDF). New Review of Hypermedia and Multimedia. 14 (1): 57–94. CiteSeerX 10.1.1.383.1636. doi:10.1080/13614560802316145. ISSN 1361-4568. Retrieved 2014-10-14.
- MoChridhe, Race J (2019-04-24). "Twenty Years of Theological Markup Languages: A Retro- and Prospective". Theological Librarianship. 12 (1). doi:10.31046/tl.v12i1.523. ISSN 1937-8904. Retrieved 2019-07-15.
- Piez, Wendell (August 2012). Luminescent: parsing LMNL by XSLT upconversion. Balisage: The Markup Conference 2012. Montréal. doi:10.4242/BalisageVol8.Piez01. Retrieved 2014-10-14.
- Piez, Wendell (2014). Hierarchies within range space: From LMNL to OHCO. Balisage: The Markup Conference 2014. Montréal. doi:10.4242/BalisageVol13.Piez01.
- Renear, Allen; Mylonas, Elli; Durand, David (1993-01-06). "Refining our Notion of What Text Really Is: The Problem of Overlapping Hierarchies". CiteSeerX 10.1.1.172.9017. hdl:2142/9407. Retrieved 2016-10-02.
- Schonefeld, Oliver (August 2008). A Simple API for XCONCUR: Processing concurrent markup using an event-centric API. Balisage: The Markup Conference 2008. Montréal. doi:10.4242/BalisageVol1.Schonefeld01. Retrieved 2014-10-14.
- Sperberg-McQueen, C M; Huitfeldt, Claus (2000). "GODDAG: A Data Structure for Overlapping Hierarchies". Lecture Notes in Computer Science. 2023 (2023): 139–160. doi:10.1007/978-3-540-39916-2_12. ISBN 978-3-540-21070-2. Retrieved 2014-10-14.
- Schmidt, Desmond (2009). Merging Multi-Version Texts: a General Solution to the Overlap Problem. Balisage: The Markup Conference 2009. Montréal. doi:10.4242/BalisageVol3.Schmidt01.
- Schmidt, Desmond (2012). "The role of markup in the digital humanities". Historical Social Research. 27 (3): 125–146. doi:10.12759/hsr.37.2012.3.125-146.
- Henri Sivonen (2003-08-16). "Tag Soup: How Mac IE 5 and Safari handle <x> <y> </x> </y>". Retrieved 2017-11-05.
- Ide, Nancy; Suderman, Keith (2007). GrAF: A graph-based format for linguistic annotations (PDF). Proceedings of the First Linguistic Annotation Workshop (LAW-2007, Prague, Czech Republic). pp. 1–8. CiteSeerX 10.1.1.146.4543.
- Tennison, Jenni (2008-12-06). "Overlap, Containment and Dominance". Retrieved 2016-10-02.
- Witt, Andreas; Schonefeld, Oliver; Rehm, Georg; Khoo, Jonathan; Evang, Kilian (2007). On the Lossless Transformation of Single-File, Multi-Layer Annotations into Multi-Rooted Trees. Extreme Markup Languages 2007. Montréal. Retrieved 2014-10-14.
- Text Encoding Initiative Consortium (16 September 2014). "Guidelines for Electronic Text Encoding and Interchange" (5 ed.). Retrieved 2014-10-14.
- WHATWG. "HTML Living Standard". Retrieved 2019-03-25.