Balisage Paper: Methodology for the construction of multi-structured documents

TexMECS

Instead of using existing languages, new syntaxes can be defined. MECS (Multi-Element Code System) [Huitfeldt1998] was the first language to allow overlapping of structures. TexMECS [Huitfeldt2003], based on MECS, is much more expressive. It allows us to define complex structures where an element can have multiple parents. The MECS model is expressive enough to answer the classic problems raised by multi-structured documents, but is too complex in order to satisfy the genericity criterion. Moreover, it does not come with query mechanisms.

LMNL

LMNL (Layered Markup and aNnotation Language) [Tennison2002] defines a specific syntax based on a notion of interval that allows the encoding of multiple structures with overlapping elements. This is only a syntactic solution that does not propose query mechanisms. As for the previous solution, since the structures are encoded inside a single document, change in data or structures is possible. These two solutions are quite complex and not compatible with the XML tools and remained at an experimental stage.

Annotation graphs

Annotation graphs [Maeda2002] has been developed in order to model linguistics phenomena (phonetic, prosody, morphology, syntax, ...). If we consider these domains as distinct structures, then annotation graphs are a valid solution to the multi-structured documents problem. As shown on Figure 2, the same textual fragment can be annotated by elements from different structures.

Figure 2

Annotation Graph

Nodes granularity is the word, or even the character if necessary. Labels on edges indicate the structure (eg S2:M for the words, S1:L for the lines). Since structures share the same graph, their update is not a problem. Moreover, a minimal query language has been developed for this kind of graph [Bird2000]. The underlying model being a graph, it is expressive enough to answer the multi-structured documents problem. But, strongly oriented toward linguistic, it lacks genericity.

RDF graphs

The RDF (Resource Description Framework) graph formalism is able to represent multi-structured documents [Tummarello2005]. This method is similar to the previous one, but relies on a generic graph model. Standard query tools for RDF graphs (eg SPARQL) can be used, but complex queries can be difficult to formulate. Although RDF is serializable in XML, the use of standard XML tools is problematic because they work on tree structures. Finally, change management is possible since structures and data share the same graph.

MuLaX

MuLaX [Hilbert2005] is the adaptation of the SGML CONCUR option to the XML formalism. This is a documentary format that allows to unify XML documents sharing the same content in a single document. In order to differentiate annotations levels, the tags are prefixed by a structure identifier. This solution lacks genericity since a specific editor is needed in order to interpret the produced documents. As for the CONCUR option, changes in structures or data are possible since there is one single document. No query operators has been defined, but the authors explain that it should be possible to build path expressions similar to those found in XPath.

GODDAG

[Sperberg-McQueen2000] presents a solution based on the GODDAGs (General Order Descendant Directed Acyclic Graph) to represent multi-structured documents. This graph model is a solution to the overlapping hierarchies problem. In order to query those documents, the author developed an XPath extension. This extension takes into account new kinds of relations between elements of distinct structures. This model cannot manage generic relations between structures. It is possible to import (or export) from (or to) the XML formalism. With this model it is possible to manage change in structures.

MCT

The MCT (Multi-Colored Trees) model [Jagadish2004] is an extension of the XML model that allows us to represent multiple trees sharing the same content. It relies on the tree coloring technique. A color is associated with each tree. A node may have multiple colors: the color of the main tree to which it belongs and colors for other trees. Figure 3 illustrates this model with an example of manuscript transcription. We see that three of the units nodes share two colors: one for the semantic structure and another one for the physical structure.

Figure 3

Colored Trees

The navigation in the multihierarchy is possible by means of the multicolored nodes. To navigate between colors, the authors extend the notion of step in XPath. An extension of XQuery is also proposed for the creation of nodes. Concerning updates, the authors explain that the extension of a language such as XUpdate is possible by using the XPath extension that they propose. The underlying model is neither expressive nor generic enough since it imposes an isomorphism of data segments (data segments must be of the same type: word, character, etc.).

MSXD

MSXD (Multi-Structured XML Documents) [Bruno2006] is a representation model for multi-structured documents that comes along with an XQuery extension. It allows users to annotate the structures. Moreover a draft of a multi-structured documents schema is introduced. However the need to define a large number of relations between structures makes the model difficult to use. Furthermore, it is not possible to manage changes in data or structures.

Delay Nodes

Jacques LeMaître [LeMaitre2006] proposed to add a new type of node to the XDM model on which are based XPath and XQuery. Those nodes are a virtual representation as an XQuery query of some of the child nodes of their parent node (see Figure 4). The underlying multi-structured documents model is very similar to the one of Multi Colored Trees (see Figure 5) where documents are considered as a set of XML trees. But no XPath or XQuery extensions are necessary in order to navigate inside these structures. However, with this approach, it is not possible to reach the parents of a delay node but only to navigate among the descendants.

Figure 4

Delay nodes

Figure 5

Delay nodes underlying MSD model

MonetDB/XQuery

MonetDB/Xquery is a XML SGBD. It has an extension [Alink2006] for managing multi-structured documents thanks to the stand-off markup technique. Optimized query operators has been developed, but no model is truly defined, only an informal description is proposed (as for the TEI solutions).

MSDM, MultiX

MSDM [Chatti2007] is a model used for the representation of multi-structured documents written by N.Chatti. An instance of this model, called MultiX, is expressed in the XML formalism. It belongs to the category of stand-off markup solutions where content is isolated in a base structure, and documentary structures are built by references to the base structure.

In this model, a document is a graph D composed of:

Moreover, ∀ j ∈ J, there is a relationship Rj that associates each node of DSj with a subset of BS ; for each leaf of DSj this subset must be non empty. Figure 6 illustrates each element of the model.

Figure 6

Illustration of the MSDM model

Finally, it should be noted that only nodes from the base structure have an associated content and depend on the data types (text, movies, etc.). In the case of textual data, a string of characters, called fragment, is associated with each node of the base structure.

Illustration

For clarity, and since we know the field, we use an example taken from critical electronic edition of manuscripts. We suppose that for the transcription of a manuscript the researchers have on hand the elements defined by the TEI. From the previous example: pages, region of interest and equations have been correctly tagged until a region overlaps two pages (see dotted edges of Figure 8).

Figure 8

Restructuring is necessary (a paragraph overlaps two pages)

It is then necessary to distinguish two structures. The creation of a new structure is a purely formal operation (see Figure 9) consisting in the transformation of a graph into two trees.

Figure 9

Automatic restructuring (two structures are distinguished)

Functions for restructuring

We now describe the functions that perform these restructuring operations. We are using the Haskell pure and statically typed functional programming language [PeytonJones2002]. As a pure language, Haskell keeps side effects under the control of a class of type constructor called Monad, in practice this allows us to ensure that a valid document will always be transformed into a valid document. Since our methodology introduces numerous document transformations, this property is very interesting. All the necessary notions for the understanding of the code will be provided. But not all functions definitions will be given. Moreover the main purpose of showing these functions is to give a proof of the feasibility of our methodology.

We need two helper functions, if' for boolean conditions and add for the addition of a new element at the end of a Map. A Map a b is a structure of elements of type b indexed by element of type a. From the signature of if' we learn that the function takes three arguments, the first argument being a Boolean value. if' True is a two arguments function that evaluates its first argument (the second argument will never be evaluated), while if' False is a two arguments function that evaluates its second argument (the first argument will never be evaluated).

-- This is a comment
-- A function is described by its type signature: the list of the types of its
-- arguments and of thereturned value separated by the symbol: '->'.
-- For example, the addIntegers function would have the signature:
addIntegers :: Int -> Int -> Int
-- and the definition:
addIntegers a b = a + b
-- Moreover, functions are curried, so (addInteger 2) is a function of type:
(addInteger 2) :: Int -> Int
-- Finally, we will:
--   * use some primitive types :
--       - Bool (with the only two constructors True and False)
--       - Int
--   * use the list constructor:
--     [Int] is the type of a list of values of type Int
--   * define data types:
data Interval = Interval {
  start :: Int
  ,end  :: Int
}
-- now Interval is a function (also called a constructor) of type:
Interval :: Int -> Int -> Interval
-- start is a function of type:
start :: Interval -> Int
-- end is a function of type:
end :: Interval -> Int

--   * define shortcuts for existing types:
type Tags = [Tags]
-- Tags is now a synonym for [Tags] (list of Tags)

if' :: Bool -> a -> a -> a
if' True x _ = x
if' False _ y = y

add :: a -> Map Int a -> Map Int a

We first define our main data types. A Tag is composed of an identifier and a list of attributes. We also have a data structure associating each tag identifier with a name and a list of default attributes. A Taggee is the application of a Tag to an interval of characters of the studied text. A Structure is a named map of taggees. A Document is the association of a text and a map of structures.

data Interval = Interval {
  start :: Int
  ,end :: Int
}

data Taggee = Taggee {
  tag :: Tag
  ,interval :: Interval
}

data Structure = Structure {
  name :: String
  ,taggees :: Map Int Taggee
}

type TagId = Int

data Tag = Tag {
  tagId :: TagId
  ,atts :: Map Int String
}

type Tags = [Tag]

type Text = String

data Doc = Doc {
  text :: Text
  ,structures :: Map Int Structure
}

We also need functions for simple interval algebra.

overlaps   :: Interval -> Interval -> Bool
isIncluded :: Interval -> Interval -> Bool
includes i1 i2 = isIncluded i2 i1
inside     :: Int -> Interval -> Bool
ilength    :: Interval -> Int
isort :: Interval -> Interval -> (Interval,Interval)

-- The exclusive OR of interval overlapping :
overlapExclusion :: Interval -> Interval -> (Interval,Interval)

-- less than:
ilt i1 i2 = (end i1) < (start i2)
-- greater than :
igt i1 i2 = (start i1) > (end i2)

-- shifting an interval:
ioffset :: Interval -> Int -> Interval
startBefore :: Interval -> Interval -> Bool
equals :: Interval -> Interval -> Bool
isPrefixOf :: Interval -> Interval -> Bool
isSuffixOf :: Interval -> Interval -> Bool

The addTag function tries to add a tag to a structure, if the addition does not imply overlapping then the modified structure is returned, else a pair of structures is returned: the first structure is the original one except that every instances of the added tag have been transfered to the second structure. In a similar way, the $delTag$ function removes the instance of a given tag from a selected interval and may imply overlapping thus the type signature.

-- partition the map according to a predicate:
partition :: Ord k => (a -> Bool ) -> Map k a -> (Map k a, Map k a)
elems     :: Map k a -> [a]

-- function application:
$ :: (a -> b) -> a -> b
-- function composition:
. :: (b -> c) -> (a -> b) -> a -> c

-- map f xs is the list obtained by applying f to each element of xs:
-- map f [x1,x2,...,xn] == [f x1, f x2, ..., f xn]
map   :: (a -> b) -> [a] -> [b]
-- foldl, applied to a binary operator, a starting value, and a list, reduces
-- the list using the binary operator, from left to right:
-- foldl f z [x1,x2,...,xn] == f (f (f (f z x1) x2) ...) xn
foldl :: (a -> b -> a) -> a -> [b] -> a

-- The Either type represents values with two
-- possibilities: a value of type Either a b is
-- either Left a or Right b

addTag :: Taggee -> Structure -> Either (Structure,Structure) Structure
addTag t (Structure n s) =
let (s1,s2) = partition ( ( (tagId $ tag t)== ) . tagId . tag ) s in
if' ( foldl (||) False $ map (overlaps (interval t) . interval) $ elems s )
    ( Left  ( Structure n $ add t s1, Structure n s2 ) )
    ( Right ( Structure n $ add t s ) )

delTag :: Interval -> TagId -> Structure -> Either (Structure,Structure) Structure

Finally, the user must be able to add or remove textual data. This is the purpose of the addText and delText functions.

-- split a list in two:
splitAt :: Int -> [a] -> ([a], [a])

fst  	  :: (a, b) -> a
snd  	  :: (a, b) -> b

addText :: Int -> String -> Doc -> Doc
addText i s d =
 let t    = text d
    split = splitAt (i-1) t
    t'    = fst split ++ s ++ snd split
    sts   = structures d
    sts'  = map ( addCharInS i (length s) ) sts
    in Doc t' sts'

addCharInS :: Int -> Int -> Structure -> Structure
addCharInS i size (Structure n s) =
 Structure n $ map ( \t ->
  if' ( i `inside` (interval t) )
      t{interval = Interval (start $ interval t) $
                            (end $ interval t) + size}
      t ) s

delText :: Int -> Int -> Doc -> Doc

Illustration

The automatic restructuring introduced above can be the occasion for a user to make modeling choices. For example, he can ask for the creation of a new mathematical structure for the equations and rename the structures (see Figure 10).

Figure 10

Intervention of a user (Three structures are named and distinguished)

Functions for user integration

moveTag is the main function offered to the user for reacting to the automatic restructuring, it allows him to move all the instances of a tag from one structure to another. The function may fail if it introduces overlapping hierarchies.

-- case analysis for the Either type
either :: (a -> c) -> (b -> c) -> Either a b -> c

-- the constant function
const :: a -> b -> a

-- foldr, applied to a binary operator, a starting value, and a list, reduces
-- the list using the binary operator, from right to left:
-- foldr f z [x1,x2,...,xn] == f x1 (f x2 (... (f xn z)))
foldr :: (a -> b -> b) -> b -> [a] -> b

moveTag :: TagId -> Structure -> Structure -> Maybe (Structure, Structure)

moveTag id s1 s2 =
 let (ts',ts'') = partition ( (==id) . tagId . tag ) ( taggees s1 )
     f :: Taggee -> Either (Structure, Structure) Structure ->
          Either (Structure, Structure) Structure
     f t ( Right s )       = addTag t s
     f t ( Left (s1, s2) ) = Left (s1, s2) in

 if' ( null ts' || null ts'' ) Nothing $
 either ( const Nothing )
        ( Just . (,) ( Structure (name s1) ts' ) ) $
        foldr f (Right s2) $ elems ts''

Illustration

We imagine three users who create documents containing mathematical notations. For each of them, a mathematical structure emerged from their operations of annotation (as described in the previous sections). Users 1 and 2 have already decided to merge their tag hierarchies. The tag hierarchies are given below:

Users 1 and 2	User 3
theorem statement proof lemma statement proof cocycle cobordism	proposition proof operators cohomology cocycle

If these two hierarchies were detected as similar enough, each user would be proposed to ask the other users the authorization to merge their hierarchies. Thus, communities of users appear, centered on their annotation practices. In this previous example, users seem to work on the same kind of documents, but the perspective of user 3 may be formal logic whereas users 1 and 2 refer to a more traditional vocabulary for the description of proofs. Since the tips the users receive while annotating a document come from the hierarchy of tags associated with the current structure, once the merge is accepted, the users may align their annotation vocabularies or at least question their practices.

Functions for promoting users interactions

We define a new data type (TagStruct) in order to link each tag used for the annotation of a document with its possible descendants. Thus, while a user is annotating a document we can give him hints about the next tag to choose, based on this new structure and its current position in the text. We also update the Structure data type to link to the corresponding implied tag structure. For this linking to be possible, we maintain a map (of type TagStructs) of the implied tag structures.

type TagStruct = Map TagId [TagId]
type TagStructId = Int
type TagStructs = Map TagStructId TagStruct

data Structure = Structure {
  name :: String
  ,taggees :: Map Int Taggee
  ,tagStructId :: TagStructId
} deriving (Show)

We have to modify the addTag function in order to update the linked structures of tags:

addTag :: Taggee -> Structure -> TagStructs -> Either (Structure,Structure, TagStructs) (Structure, TagStructs)
addTag t (Structure n s tagStructId) tagStructs =
  let tId = tagId $ tag t
      (s1,s2) = partition ( (tId==) . tagId . tag ) s
      s' = Structure n (add t s) tagStructId
      (tagStructIdS2, newTagStructs) = addTagStruct tagStructs in
  if' (
        foldl (||) False $
        map (overlaps (interval t) . interval) $
        elems s
      )
      (
        Left ( Structure n (add t s1) tagStructId,
               Structure "" s2 tagStructIdS2,
               delTagFromTagStruct tId tagStructId newTagStructs )
      ) $
      Right ( s', addTagToTagStruct tId (parentId t s') tagStructId tagStructs )

addTagStruct :: TagStructs -> (TagStructId, TagStructs)

delTagFromTagStruct :: TagId -> TagStructId -> TagStructs -> TagStructs

addTagToTagStruct :: TagId -> Maybe TagId -> TagStructId -> TagStructs -> TagStructs

parentId :: Taggee -> Structure -> Maybe TagId
parentId t s = maybe Nothing (Just . tagId . tag) $ parent t s

parent :: Taggee -> Structure -> Maybe Taggee

Note that Haskell is a pure functional programming language and as such does not allow side effects. That is why, in the previous functions when we had to manage some kind of shared data structure of type TagStructs, we passed it between functions by the way of an extra parameter. Haskell has a data type design pattern called monad that offers a much nicer solution, but we kept with the basics so that the link between the two previous sections remained obvious.

We finally have to compute the distance between every pair of implied tag structures. We choose a very straightforward editing distance equals to the number of "add" and "delete" operations needed to transform one set of tags into another. It does not take into account the structure of the tags and has for only purpose to guide the user towards other possibly similar tagging practices. In our current implementation, the distances computation is a daily batch process.

type Recommendations = Map TagStructId (Map TagStructId Int)

distance :: TagStruct -> TagStruct -> Int
distance ts1 ts2 =
  let k1 = keys ts1
      k2 = keys ts2
      intersize = length $ intersect k1 k2 in
  (length k1 - intersize) + (length k2 - intersize)

distances :: TagStructs -> Recommendations
distances tss = mapWithKey (\k ts -> map (distance ts) $ delete k tss) tss