adam farquhar

During the past couple of weeks, there have been some thoughtful and well-informed discussions about Fido, Droid, Pronom, and file format identification in the comment stream of this blog.  They make interesting reading.

In a recent comment, Shaun Zevin raises some points about the algorithmic complexity of the Droid and Fido pattern matching.

From the algorithmic perspective, DROID should be faster than FIDO.The Boyer-Moore-Horspool algorithm used by DROID has a linear O(N) complexity in average where N is the length of the examined string i.e. the identified file.

Perhaps my one dubious claim to insight in this matter is that I took a course with Boyer and Moore entitled ‘Recursion and Induction’ while a PhD student at the University of Texas at Austin.  In addition to being excellent and influential scientists, they were also superb teachers.

Sean’s observation is pretty close to my understanding, but the algorithmic claims are about the worst-case behaviour.  That is, the worst-case behaviour for the Boyer-Moore-Horspool (BMH) algorithm on a restricted subset of regular expressions is linear, whereas the worst-case behaviour for matching full regular expressions is exponential.

One way to think about the worst-case behaviour is to imagine a demon that comes up with the most evil possible pattern and the nastiest possible input.  In the case of the BMH pattern language and algorithm, the worst the demon can do is force the algorithm to take time that is linear in the size of the input.  In the case of full regular expressions, the demon can do much worse and make the algorithm take time exponential in the size of the input – and this can be a very long time!

In our case, however, we do not have a demon. We have the angelic Pronom, who restricts patterns to the restricted subset that the BMH algorithm can handle.  These patterns do not appear to elicit the worst-case behaviour from the regular expression matcher.

Furthermore, the regular expression implementation has been highly optimised over many years. In contrast, the core Droid matching code has barely changed since version 2. In the case of the Python implementation, for example, the regular expression matcher is written in C.  This means that the coefficient will be much lower for the regular expression module.  In addition, because the regular expression language can require expensive matching, the implementations do some special casing.  For all I know, it checks to see if the pattern is in the subset that BMH handles, and uses the BMH algorithm in that case!

Sean also points to what looks like a great alternate implementation of the regular expression matching engine that has some excellent performance characteristics.  It is fairly new – and I bet that if it is perceived as stable and efficient, it will be integrated into Python, re-implemented in Java, become widely available, and be used in Fido 2!

…version 38 of a DROID signature file has 44 variable position byte sequences which are killing DROID performance. ..

Sean notes that the Pronom signatures are not highly tuned and that the ‘variable’ signatures that may apply anywhere in the file kill performance.  This is absolutely the case.  As I previously highlighted, content is king here.  As a community, we need to put some real effort into improving and extending the signature set.

Another problem is that PRONOM signatures are clearly underoptimized. … ID 40 from DROID signature file. It has a fixed position byte sequence with 1024 maximum offset which is unique in PRONOM and is 45 bytes long. 3C21444F43545950452068746D6C205055424C494320222D2F2F5733432F2F445444205848544D4C20312E31

This appears to be the pattern for fmt/103, or XHTML.  The Fido regular expression that corresponds to the byte sequence is:

.{0,1024}\\<\\!DOCTYPE\\ html\\ PUBLIC\\ \\”\\-\\/\\/W3C\\/\\/DTD\\ XHTML\\ 1\\.1

Sean points out that there is another pattern for this same signature.  The Fido pattern for it is:

<html\\ xmlns\\=\\”http\\:\\/\\/www\\.w3\\.org\\/1999\\/xhtml\\”.*\\<title\\>.*\\<\\/title\\>

He suggests that the second pattern is not needed.  I must say that the two wild-cards – matching any number of bytes –before <title> and up to the following </title> – can make this pattern pretty inefficient in some cases.  I’ve not seen this one as a problem in practice, but the underlying point is spot-on.  We need to review the signatures and tune them.  Some others, such as the signature for fmt/134 are much more expensive.

It is also essential for us to gather a rich document corpus for regression testing and benchmarking.  The Planets project made a start in this direction, but there is much more work to be done.  The OPF has some excellent ideas here – and we’ll be hearing more about them soon.

I’m not at the OPF Hackathon this week in the Netherlands, and I’ll admit to being slightly envious of those who are!  The idea behind the Hackathon is to bring practioners and developers together for some intense exchange of goals and ideas, collect use cases, show each other tools and approaches, and do some quality coding.

We are fortunate to have some very clever and very skilled people in the OPF community who care deeply about digital preservation – and like getting things done.  I’m really pleased that so many of them were able to come together for this event, and am looking forward to hearing about and seeing the results.

This is an exciting step on the journey to building up a vital effective digital preservation community at the OPF.

Content is King.  The key to a good file format registry is not software; it’s not user interface; it’s not governance. The key is content, content, content.  We will all win if we have a registry whose content is usable, accurate, and comprehensive.

I have a challenge for developers in the digital preservation community: can we build a file format registry without building any new software systems at all? 

Let’s take Pronom as an exemplar.  Pronom consists of about 700 small XML documents with some cross references.  There is a modest community of people who may look at them and point out errors (bugs) or omissions (new features).  Some of these may even email in corrections.   Of course, not every member of the community is trusted to make changes to the underlying data!  There is a special subset of community members that validate these changes and actually commit them.

How often do these changes occur?  I don’t think any of us know precisely, but I’ll suggest with confidence that it will be less than once a second.  Actually, I bet it will average less than once a week.

How much format data is there?  I don’t know precisely, but the entire current Pronom XML  data fits into a single zip file of 680KB.  I would be willing to bet that an active community will not grow this by more than a factor of 100 over the next few years – so I’ll estimate much less than 700MB.  Today’s size and rate of change would be comfortably handled via email! I receive many larger documents each day.  It certainly does not require a complex database.

So let’s consider this profile. There is a community that consists of a few committers, tens of active members, and perhaps hundreds of end users.  They have a process to manage patches and releases.  The community maintains a few thousand objects constituting a few megabytes.  

Does this sound like a process and structure that we are familiar with? To me, this sounds like any of hundreds of modest open-source community-driven software development projects.   Is this bad news?  Do they have to invest hundreds of thousands of euros to setup a special infrastructure to manage all of this complicated stuff and distribute their data?   Well, no!  The infrastructure is already there.  It is well established; there are many providers; and it is mostly free.  Most importantly, it lets communities get on with their real work.

My second challenge to the developers in the digital preservation community is this:  Suppose that you had two weeks to set up a functional file format registry, could you do it?  Could you manage some directories full of XML and also generate some HTML files (or just use a style sheet)? Would you really need to write a single line of code? And the really big question: could you take the second week off?

Someone else can do the hard work while you are on vacation!  Specifying good signatures for common file formats would be a great next step.

Let’s think radically.  Let’s make our problems so easy that it’s almost embarrassing to solve them!

A couple of people have asked me if my experiments with Pronom and Fido would have been easier if Pronom had been available as RDF or LinkedData.  The short answer to this question is ‘no’.  Let me explain why.

Parsing the Pronom XML is actually very easy.  The schema is straightforward and easy to understand.  Having an entire format specification in one XML document ensured that I didn’t miss any bits – and it made exploring and understanding the underlying conceptual model very easy.  I didn’t need the parts; I only wanted the whole.  In addition, the whole is quite small.  At the moment, all of Pronom can be contained in about 730 XML documents – less than 700KB in a Zip file.  This is smaller than the PDF report that documents the signature syntax and algorithm. 

There are two trivial changes that could be made to Pronom and Droid that would have made the exercise much easier.

1. Provide access to the Droid Signature file via a simple HTTP request.  Doing this would make it easier to fetch by hand or automatically.  It is hidden behind a web services interface, which requires several extra layers of technology and no discernable benefit. 
2. Provide access to the Pronom XML documents via a single simple HTTP request, returning them as a Zip file.  Alternatively, a single page listing all of the format identifiers or URLs would be almost as good.

If the Droid signature information or Pronom format information had been available as LinkedData, I would have had easier access than using web services.  That would have been a small improvement.  It would have been harder, however, to retrieve all of the relevant parts and assemble them back together again.  It would also have been much harder to understand how all of the parts worked together and, ironically, it would have been much harder to understand the underlying conceptual model.

The LinkedData approach would be a much better fit if the Pronom information was larger (thousands of formats), or changed more rapidly (daily or weekly).  It might also be a reasonable fit for combining format information from multiple sources.   I do love LinkedData, but not for every job.

Last time, I discussed Pronom and Droid. We had a quick look at the compiled (nearly unreadable) pattern information that the Droid signature file holds and the uncompiled (but still hard to read) representation that is stored in Pronom.

In this post, I’ll run through the Pronom pattern language, show how to get access to the XML documents for all of the Pronom file formats, and look at some of the properties of the full set of existing patterns. Then we’ll be able to ask and answer a key question: Is there a simpler way to represent the Pronom patterns and match them against files?

It turns out that many file formats can be identified by looking at a few bytes at the very beginning, and sometimes a few at the end. For example, a PDF starts %PDF with and ends with %EOF (almost). The first four bytes of a Zip file are the ascii codes for the letters P and K followed by a 3 and a 4. Some formats can be identified by looking for characters somewhere around the front or end. For example, an Office Open XML file is a Zip file that has a particular content; you can recognise them by the characters [Content_Types.xml] starting at the 30th byte. Some types are even harder to reliably recognise. For example, there are probably billions of ‘csv’ files, but it is hard to specify a rule to recognise them reliably. Other types may require looking for special sequences of characters somewhere in the middle of the file. We can think of these patterns as signatures for each file format.

In order to identify the formats of files, Pronom provides signatures expressed in a special pattern language. I was interested in the set of signatures that Pronom holds and that Droid uses. My problem is that each one is defined on a separate web page on the Pronom site – and there is not easy-to-access list of all of the pages.

Just using the web site didn’t help me very much. Pages for the formats are accessible via search and result in URLs such as http://www.nationalarchives.gov.uk/PRONOM/Format/proFormatSearch.aspx?status=detailReport&id=613. This is not very satisfactory because the id is the Pronom internal ID – it is not the PUID (persistent unique identifier) that provides a global identifier for the format – and there is no list of the Pronom internal IDs. The visible links to formats have this same form.

When I first used Droid, however, I noticed two things. First, I observed that there was a preference for a PUID URL pattern – http://www.nationalarchives.gov.uk/pronom/. Second, in the Pronom report, there was a link from each file format PUID to the web site, such as http://www.nationalarchives.gov.uk/pronom/fmt/11. This is helpful for Droid users, because they can easily find out more about the format. Now I felt that I was closer to my goal. I could use the Droid signature file to extract a list of all of the PUIDS, and use the URL pattern to identify and fetch all of the web pages. Of course, I didn’t really want the web pages, I wanted the XML so that I could analyse and manipulate the information more easily. At this point, I made a lucky guess! I typed ‘.xml’ at the end of the URL and, like magic, the XML file appeared. The magic incantation was: http://www.nationalarchives.gov.uk/pronom/fmt/11.xml. The development team at TNA is really to be praised for providing this style of access to the XML directly.

At this point I was ready to get started, and with a couple of shell script incantations, I had retrieved all 731 XML documents. The following shell script is all that I needed (I’ll explain it below).

 1 base="http://www.nationalarchives.gov.uk/pronom/"
 2 re='PUID=\"(fmt|x-fmt)/([0-9]+)\"'
 3
 4 while read line; do
 5    if [[ $line =~ $re ]] ;	then
 6	 puid=${BASH_REMATCH[1]}/${BASH_REMATCH[2]}
 7	 fname=xml/puid.${BASH_REMATCH[1]}.${BASH_REMATCH[2]}.xml
 8	 wget -T5 -O $fname $base$puid.xml
 9    fi
10 done < droid-signature_v39.xml

Explanation:

1. ‘base’ is the URL pattern from the Droid options.
2. ‘re’ is a simple regular expression that will match all of the PUIDS in the signature file. They look like PUID=”fmt/11” or PUID=”x-fmt/91”. The parentheses save a portion of the match, so that we can access them using the special Bash shell variable BASH_REMATCH.
3. The loop reads each line in turn.
4. The [[ $line=~$re ]] matches the line against the regular expression. I was really pleased to discover how easy this was to do in the Bash shell.
5. With the match, we can reconstruct the PUID from its two parts.
6. And create a filename to place the result in called, for example, xml/puid.fmt.11.xml.
7. The real is done by ‘wget’. This is an amazing command-line tool for working with web content. It gets the contents of our URL and outputs it to $fname. The ‘-T5’ specifies a timeout of 5 seconds. If there is a problem fetching one URL, we timeout and try the next one.
8. The funny ‘done < droid-signature_v39.xml’ simply sends the contents of the file as input to the loop statement, which ends with ‘done’.

After running this script, I had 731 XML files and was ready to take a closer look at the Pronom signatures. I had several questions: (1) How many of the formats had signature patterns; (2) How many signature patterns were there altogether; (3) How many different pattern were used; (4) Which features of the Pronom pattern language were actually used; (5) would it be possible to automatically convert the Pronom patterns into a more widely used pattern language, such as the regular expression language used in Python, Java, and other common programming languages.

I started out using basic shell script tools like grep, moved on to XML tools like the amazing xmlstarlet, and ended up parsing the XML in Python as I got deeper in my explorations. To summarize the results:

1. There are 208 Formats with InternalSignatures.
2. There are 244 InternalSignatures. Some formats have more than one signature – that is there is more than one approach to identifying instances of the format.
3. There are 351 ByteSequences. There are a fair number of InternalSignatures with more than one ByteSequence – what Pronom calls a pattern. For example, some will have a pattern to match the beginning of a file, and another to match the end.
4. We’ll come back to this later, but none of the unusual features of the pattern language were actually used.
5. From my initial review, it seemed entirely plausible to convert the Pronom patterns into much more widely used regular expression patterns.

The following passage assumes basic knowledge of regular expressions. There are many good on-line tutorials. Regular expressions are an important tool in any digital preservation expert’s toolkit. Adrian Brown’s document (http://www.nationalarchives.gov.uk/aboutapps/fileformat/pdf/automatic_format_identification.pdf) clearly defines the features of the Pronom pattern language. It turns out that they can all be translated easily into a typical regular expression language (I use the Python regular expression syntax, but the subset used here is equivalent to the Posix standard). In fact, they define a subset of the regular expression language. The following translation table shows the Pronom feature, the regular expression feature, and some comments.

The table covers all of the Pronom pattern languages features that are actually used. There are two other features defined, but unused. These include [!a], which could be translated as [^a] and [!abc] which could be implemented as (?!abc). In addition, there is an indirect offset feature is not used.

There is one additional wrinkle to consider. Pronom uses byte codes, whereas the regular expression language uses characters – while providing a way to specify byte codes. A byte code can be represented in hexadecimal with a \x prefix. For example, the hex code 30 can be represented as either a space, or \x30. There are several characters that have special meaning in the regular expression language. If they are preceded by a backslash, then they lose their special meaning. For example, ‘.’ matches any character, so to match the dot in ‘1.0’, the regular expression is ‘1\.0’. Examples include:

This table shows a few examples of the Pronom byte codes and regular expression patterns. All of these patterns are fairly hard to read, but I think that most humans will find the regular expressions easier to read than the byte sequences – even with the backslashes.

There are two surprises in this little set of examples. One is too specific – it will fail to match perfectly good instances, and another is too general – it will match non instances.

I noticed the first when Droid failed to recognise some of my PDFs. Upon inspection, I found that it was because they ended with \n\r, rather than \r\n. Many of the Pronom patterns for PDF variants or related formats actually end with the sequence (0A|0D|0D0A|0A0D) – which covers all of the needed cases.

The ODF signature has an obvious flaw. The ‘*’ between ‘base’ and ‘office’ means that there can be any number of intervening bytes. This means that the string ‘office:version=1.0’ could actually be present in any Zip item name or even in the content portion of any Zip item that was stored uncompressed. On top of that, it can make recognising ODF files much less efficient – instead of scanning the first 50 bytes, one may have to look all the way through to the end of the file.

These are not huge problems, but they are associated with rather ordinary formats. How can we be sure that a signature is both accurate and efficient?

I believe that the choice of pattern language is important. Preservation specialists must be able to determine if a pattern is wrong and correct it. I believe that this is nearly impossible with current the Pronom byte signatures. The regular expressions are still hard to read, but there are many more people who can follow and validate them – and many more tools that can be used to work with them.

At this point in my exploration, I was getting very curious. I had learned that it was easy to fetch all of the Pronom XML files. Moreover, I had concluded that it would be very easy to convert the Pronom byte signatures into a well known regular expression language – and that this made the signatures much easier to read and understand. Now I wondered: would it really be easy to use the regular expressions to identify the formats of digital objects – and what would the performance of such an approach be like?

In the next post, I’ll fill you in on some of the missing details, such as the relationships between formats and signatures. I’ll describe a simple implementation of a file format identification tool using regular expressions, and I’ll show some startling performance results.