Geometric data structures for multihierarchical XML tagging of manuscripts

Geometri data strutures for multihierarhial XML tagging of manusripts Jerzy W. Jaromzyk a ; 1 ,Neil Mo ore a ; 1 , a Deparment of Computer Siene, University of Kentuky, Lexington, KY, USA Abstrat This pap er shows an appliation of omputational geometry methods to the preparation of image-based digital library editions. We present a formalism for desribing non-hierarahial markup of manusripts in terms of oneand two-dimensional geometry. This formalism allows us to use geometri data strutures and algorithms to pro ess marked-up do uments. With this approah we an overome many well-known and inherently diÆult problems with non-hierarhial markup. We present algorithms based on segment trees and range-query strutures for p erforming a number of queries on markup struture. This appliation of omputational geometry data strutures to a new domain also provides insights into novel types of geometri op erations and queries. Some of these tehniques are urrently being used by researhers in the Researh Computing for Humanities pro jet, whih aims to pro due eletroni editions of seleted manusripts from the British Library. 1. Intro dution From a omputational geometry p oint of view, an old manusript, a folio (a sheet of writing material) and the sript (a text on the manusript page) have interesting features in one, two and three dimensions and all of them are imp ortant. Spatial deformations of the folio an be studied for restoration purp oses in three dimensions. Illuminations, damages, restorations, and paleographi features of individual letters an b e studied as two dimensional ob jets. The sript, a sequene of lines of text, an b e viewed as one dimensional as it follows visible or invisible rulings that guide the layout of the text [B94℄. In fat, onneting the image view of a manusript with its transript is typially the rst task. In this pap er we will disuss this linear asp et of folia and we will disuss geometri stru- tures that supp ort its tagging. Extensive tagging or markup is an often exruiating task in the preparation of eletroni editions of manusripts. The tagging pro ess results in a strutured desription of the doument's ontents, its features and attributes in a form that an b e Email addresses: jureks.uky.edu (Jerzy W. Jaromzyk), neils.uky.edu (Neil Mo ore). 1 This researh was supported in part by NSF ITR grant 0219924 used to view and eetively query the edition. The XML (eXtensible Markup Language) is a prevailing format used for desribing literary and artisti work for Digital Libraries. XML les desrib e wellhierarhial strutures (e.g., bo ok, volume, setion, page, line, word and harater) of the do ument and for that reason they an be viewed as rooted trees. Although it seems natural that most douments adhere to suh hierarhies, it is often not true in pratie. Even worse, this happ ens in the ontext of ultural heritage that urgently requires preservation: old and severely damaged manusripts. An image of a damaged folio from Alfred the Great's Old English translation of Bo ethius's Consolation of Philosophy is demonstrated in Figure 1. Words an span more than one line, damages or restorations an overlap words and parts of them. A rather simple ase is illustrated in Figure 2 where in the onvoluted tagging one word spans two lines; as suh, it is not well-formed XML. It has been long reognized that, in spite of its p opularity, XML suers from an inability to en- o de elements that are not in hierarhial relationships [RMD93℄. There are numerous approahes to address this problem alled the onurrent hierarhies problem; see, for example, [B95℄. Mostly these approahes are onerned with tagging tran20th EWCG Seville, Spain (2004) 20th Europ ean Workshop on Computational Geometry Fig. 1. An image of a damaged manusript page Fig. 2. Markup that is not hierarhial sripts (text-based do uments). In our task a manusript or an image of it is the primary soure for preparing an eletroni edition and we need to handle the onurrent hierarhies in geometri ontext of the image. This image-based approah is the most distinguishing aspet of our work. A geometri view of the problem allows us to engage many data strutures, in partiular multidimensional ones. In this paper, we will fo us on two of them: segment trees and a grid based data struture develop ed by Overmars for range queries (we will use it for line segments rather than p oints, though). We will analyze how these strutures supp ort a variety of queries that are essential in the ontext of editing and studying manusripts. There are several ontributions of this pap er. The rst is in applying omputational geometry to a new area. We will present a formalism for onurrent hierarhies that allows us to onnet geometri strutures with XML do uments. Sp eially, we will disuss a numb er of algorithms for querying the struture of a do ument, together with their asymptoti omplexities. 2. Denitions In this setion we desrib e a formalism for representing multihierarhial doument markup. This formalism allows us to onnet the struture of markup with a geometri representation; this allows us to use geometri data strutures and algorithms to pro ess tagged do uments. 2.1. Markup elements We represent a markup element as a tuple ( N ; A; ; ! ) where N is the element name, A (a map from strings to strings) the attributes, and  and ! are integers with 1    ! . The interval of a markup element e , written I( e ), is the losed interval [  ( e ) ; ! ( e )℄  N . Definition 2.1 Let e 1 and e 2 be two markup elements. We dene the relations: { e 1  e 2 if ! ( e 1 ) <  ( e 2 ) { e 1  e 2 if  ( e 1 )   ( e 2 ) and ! ( e 1 )  ! ( e 2 ) and I( e 1 ) 6 = I( e 2 ) . In this ase we say that e 1 is a desendant of e 2 , or equivalently that e 2 is an anestor of e 1 . We state without pro of the following theorems: Theorem 2.1 The relations  and  eah form a strit partial order. Theorem 2.2 Let e 1 and e 2 be two markup elements. Exatly one of the fol lowing holds: e 1  e 2 ; e 2  e 1 ; e 1  e 2 ; e 2  e 1 ; e 1 overlaps e 2 ; or I( e 1 ) = I( e 2 ) . 3. Hierarhies Definition 3.1 Let E be a nite set of markup elements. E is hierarhial if: { There is an element r 2 E , al led the root, suh that, for eah element e 2 E , e  r or e = r { No two elements of E overlap, and no distint elements of E share the same interval. Lemma 3.1 Let E be a hierarhial set of markup elements, and e 2 E . Then either e is the root and has no parents in E , or e is not the root and has exatly one parent in E . Marh 25-26, 2004 Seville (Spain) Theorem 3.1 Let E be a hierarhial set of markup elements. Let G be a graph on E suh that the edge ( e 1 ; e 2 ) is in G if e 1 is the parent of e 2 . G is a tree. This justies our use of the term \hierarhy". Beause hildren of the same parent annot be desendants of one another, by Theorem 2.2 they an b e ordered by  . The tree is therefore an ordered tree. 4. Data strutures and queries In this setion we desrib e two geometri data strutures and apply them to a number of ommon queries on do uments. A segment tree [BW80, PS85℄ is a dynami data struture to represent a set of segments. For insertions and deletions it is assumed that the endp oints b elong to the set of n p oints known in advane. The underlying struture is a balaned binary tree with leaves representing atomi segments. Eah node orresp onds to the union of the atomi segments ro oted in this no des. Intervals that b elong to the olletion represented in the segment tree are assoiated with no des of the tree and satisfy the following prop erty: a no de v stores s if the union of its atomi segments is ontained in s but the union of the atomi segments assoiated with the parent of v do not. Thanks to this prop erty eah segment is represented in at most O (log n ) no des. Insertions and deletions an b e p erformed in O (log n ) time. Also, in the same time one an ount the number of segments in the olletion that in- ludes a given query point. While segment trees are well-suited for some typ es of queries, there are other queries whih segment trees do not p erform as eÆiently. We use a rangequery struture to supp ort these queries. We treat a segment S = [ ; ! ℄ in U = [1 ; M ℄ as a point p ( S )=( ; ! ) in U 2 . We all this representation of (a olletion of ) segments a segment grid . Many prop erties of S then orresp ond to range prop erties of p ( S ) in the segment grid. For example, S  T if and only if p ( S ) lies to the lower right of p ( T ). We shall make use of general range queries of the form: nd all points lying in the (losed) retangle b ounded by ( a; b ) and ( ; d ). There exist a number of data strutures supp orting suh queries in a twodimensional grid. A number of these strutures are desrib ed in [O88℄; two are of partiular interest for our purp oses. Theorem 4.1 (Overmars) We an represent n points in U 2 (and thus n segments in U ) using O ( n log n ) spae in suh a way that range queries take O ( k + log log j U j ) time, where k is the number of results returned by the query. This data struture makes use of p erfet hashing, and is therefore slow to build. There is an alternative data struture with slightly worse query time, but signiantly better reation time: Theorem 4.2 (Overmars) We an represent n points in U 2 using O ( n log n ) spae in suh a way that range queries take O  k + p log j U j  time, where k is the number of returned results. This data struture an be built in O ( n log n ) time. Neither of the range-query data strutures permits eÆient insertion or deletion. For more information on these strutures, see [O88℄. 4.1. Desendant queries A ommon query on do uments is to nd all elements of a ertain typ e that are desendants of a given element e . For example, given a <page> element, one may wish to nd all <damage> elements ontained within that element, either diretly (as hildren) or indiretly. We an p erform this op eration by nding all desendants of e and reporting only those of the requested typ e. Reall from Denition 2.1 that the desendants of e are those elements whih b egin no earlier than e , end no later than e , and do not b oth b egin and end at the same p oint as e . In terms of the segment grid, p (I( x )) is a desendant of e if I( x ) 6 = I( e ) and p (I( x )) lies in the retangle b ounded by the p oints (  ( e ) ;  ( e )) and ( ! ( e ) ; ! ( e )). Using the data struture from Theorem 4.2, we an nd all suh p oints in O ( k + p log M ) time, where M is the do ument's maximum oset and k is the number of results. 4.2. Overlap queries Another useful query is: given an element e , nd all elements whih overlap e . If e 1 overlaps e 2 , e 1 ontains at least one of the endp oints of e 2 . Conversely, if e 1 ontains at least one endp oint of e 2 , either e 1 overlaps e 2 , e 1 = e 2 , e 1  e 2 , or e 2  e 1 . This suggests the following: Theorem 4.3 Let D be a doument ontaining the element e . Let k be the number of elements overlapping e , d the number of desendants of e , a the number of anestors of e , and M the maximum o- 20th Europ ean Workshop on Computational Geometry set of D . We an nd al l elements overlapping e in O ( k + d + a + log M ) time. We rst nd the sets B ( e ) and E ( e ) of all elements whose intervals ontain  ( e ) and ! ( e ), resp etively, using stabbing queries in a segment tree. B ( e ) ontains at most k + d + a + 1 elements, and likewise for E ( e ). The stabbing queries an therefore b e p erformed in time O ( k + d + a + log M ). We then iterate through the results, rep orting those whih atually overlap e . Testing whether a given segments overlaps e requires onstant time, so this step do es not inrease the omplexity.  We an improve on this b ound somewhat by making use of range queries. If e 1 overlaps e 2 , e 1 ontains exatly one endp oint of e 2 . In the segment grid, segments ontaining  ( e ) but not ! ( e ) lie in the retangle R  b ounded by the p oints (1 ;  ( e )) and (  ( e ) ; ! ( e )). Likewise, segments ontaining ! ( e ) but not  ( e ) lie in the retangle R ! b ounded by (  ( e ) ; ! ( e )) and ( ! ( e ) ; M ), where M is the maximum oset of the doument. While these retangles ontain all the elements whih overlap e , they do not ontain only suh elements. As with the stabbing queries desribed ab ove, the range queries also return e , and may return some anestors and desendants of e , so we must remove these from the result set. It is lear, however, that the retangles do not ontain any element x suh that x  e or e  x . Theorem 4.4 Let D be a doument ontaining the element e . Let k be the number of elements overlapping e , d the number of desendants of e , a the number of anestors of e , and M the maximum o- set of D . We an nd al l elements overlapping e in O ( k + d + a + p log M ) time. Eah range query returns at most k + d + a + 1 elements, and an therefore b e p erformed in time O ( k + d + a + p log M ). As with the stabbing query, we then iterate through the results of the range query, rep orting those elements whih overlap e ; again, this do es not aet the overall omplexity of the overlap query.  The running time of overlap queries an be improved still further if we impose additional restri- tions on the endpoints of elements: Theorem 4.5 Let D be a doument suh that no two elements share an endpoint in ommon, and let e be an element in D . If k is the number of elements overlapping e and M is the maximum oset of D , we an nd al l elements overlapping e in O ( k + p log M ) time. 5. Conlusion We have presented a formalism that onnets the realm of omputational geometry to algorithmi problems that we have faed in the marking up of image-based eletroni editions. As examples of geometri strutures we have disussed segment trees and range query strutures and have applied them to the well-reognized and inherently diÆult problem of non-hierarhial markup. Twodimensional asp ets of manusript marking, suh as marginalia, paleographi features and damages will involve additional geometri strutures. Aknowledgement The authors aknowledge a partial supp ort from the NSF ARCHway: Arhiteture for Researh in Computing for Humanities through Researh, Teahing and Learning pro jet. We are thankful to Kevin Kiernan, the Bo ethius Pro jet and the British Library Board for allowing us to use the image. We also thank our olleagues from the Researh Computing for Humanities Lab at the University of Kentuky for many useful disussions. Bibliography [B95℄ Barnard, D., et al. Hierarhial Eno ding of Text: Tehnial problem and SGML Solutions, Computers and the Humanities 29/3 (1995) 211-231. [BW80℄ Bentley, J. L., and D. Wo o d. An optimal worst-ase algorithm for reporting intersetions of retangles, IEEE Trans. on Computers C-29 (1980) 571-577. [B94℄ Brown, M. P. Understanding Il luminated Manusripts: a Guide to Tehnial Terms . London: The British Library, 1994. [KJDP03℄ Kiernan, K., J. W. Jaromzyk, A. Dekhtyar, D. C. Porter, et al. The ARCHway Pro jet: Arhiteture for Researh in Computing for Humanities through Researh, Teahing, and Learning. To b e published in Literary and Linguisti Computing , 2003. [O87℄ Overmars, Mark H. EÆient data strutures for range searhing on a grid, J. Algorithms 9 (1988) 254-275. [PS85℄ Preparata, F. P. and M. I. Shamos. Computational Geometry: an Introdution . New York: Springer-Verlag, 1985. [RMD93℄ Renear, A., E. Mylonas, and D. Durand. Rening our Notion of What Text Really Is: The Problem of Overlapping Hierarhies. In Researh in Humanities Computing , eds. N. Ide and S. Ho key. Oxford: Oxford Univeristy Press, 1993. [S99℄ Samet, H.. Multidimensional Data Strutures. In Algorithms and Theory of Computation Handbook , ed. M. J. Atallah. Bo a Raton: CRC Press, 1999. [XML-W3C℄ Bray, T., J. Paoli, C. M. Sp erb erg-MQueen, and E. Maler, eds. Extensible Markup Language (XML) 1.0, W3C Reommendation. http://www.w3.org/TR/2000 / REC-xml-20001006 . W3 Consortium, 2000.