In a programmer’s mind

A nice paper typography by Caro Wallis

Storing, managing and displaying characters should be easy. It seems like this is not the case yet.

Encodings are a way to store and recall sequence of symbols like a string in a binary format. For instance, the ASCII encoding map the sequence “abc” to the binary format of 0110 0001 0110 0010 0110 0011 so we can send it through a network link, store it in a file or save it in memory.

Encodings are absolutely needed. We would not be able to work with text in a computerized way without them. They pose a problem because they are misunderstood and misused.

Encoding problems are not rare. They are not uncommon. They are endemic. They are so present in my daily life that I do not even pay attention to them anymore. They are present in small software up to the multimillion projects.

Here is the latest example of this problem.

One of my Amazon Canada bill. They cannot correctly spell my name.

One of my Amazon US bill. They know how to spell my name.

Even Amazon has problems with encodings in different systems. No wonder is it a plague among other software too. Having a character out of English language symbol set in your name is a common way to spot this kind of problem.

In the Good Old Days, when computer had to run on quite limited space in terms of memory, storage and bandwith, there were many different encodings for different languages. In order to display or find out which symbols you could construct from a giving binary representation you had to know which encoding was used to encode them.

Nowadays, we have Unicode. Unicode is an attempt at mapping every known character symbol for every currently used languages. It even maps ancient and mostly instinct language symbols.

Unicode has many ways to encode its big table in a binary format. The common ones are UTF-8 and UTF-16. UTF-8 maximize compatibility with ASCII. A text containing strictly ASCII characters will have the same binary representation using the ASCII encoding or the UTF-8 encoding.

A common mistake is that the world lives in English. My recommendation is to take your next vacation week in a small town in Japan to find out if they live in English. Another common mistake is just plain not knowing that character symbols are encoded to binary format and decoded from binary format. I have known many programmers who did not know. I did not know before I had the same kind of problems that Amazon Canada currently have. Colleges and universities should teach this kind of stuff, but that is another discussion.

The most common mistake is going from one encoding to another without thinking about possible loss of precision. You cannot go from Unicode to ISO-8859-1 without possibly losing many characters in the process. Think about it. Unicode version 5.1 maps 100713 symbols while ISO-8859-1 maps 191 symbols. There is a big gap between these two.

Unicode is no silver bullet, but in doubt, you should use it. There is not many reasons why you should not use it. Applying it in every cases in every systems should be the norm.

A few weeks ago, I had to manage a some scenarios involving XML files. One of the problem I had was to compare some large XML files that had small content and schema changes.

My first attempt was to use a regular text diff tool like KDiff3. I did not get the result I wanted. Since my files contained whitespaces that were different in each file, I could not easily pinpoint where in my files were the meaningful differences.

For example, if you have these two XML files, where [TAB] is the tabulation character:

<client id="30" name="Georges">
 <phone>
  <number>
   555-555-5555
  </number>
 <phone>
 <phone />
</client>

<client name="Georges" id="30">
[TAB]<phone></phone>
[TAB]<phone>
[TAB][TAB]<number>
[TAB][TAB][TAB]555-555-5555
[TAB][TAB]</number>
[TAB]</phone>
</client>

They can be exactly the same XML file with the same meaning, but to a text diff utility, they can be quite different. Whitespaces, empty tags with or without an end tag, attributes order and tags order can all be problematic to find out the real differences in XML files with some simple tools.

I began searching for some real XML diff tools. I found a few commercial offerings including DeltaXML and a few open source projects including xmldiff and XMLUnit that could be of help.

The commercial products were pretty good. I had a hard time using the open source ones. They all had some problems that I could not get over with. I decided to build my own library to do what I wanted. I though it would be easy to build it.

I started with these goals in mind:

1. It should work fine on large streams using a read-only forward-only access interface.
2. It should support namespaces.
3. It should detect added, removed, renamed and moved actions for elements, attributes, namespaces and data.
4. It should be accessible as a library and as a command line tool.

The goals 2 and 4 were quite easy. Many XML interfaces support namespace these days and building a command line tool over a well defined library is a simple matter.

For the goals 1 and 3, it was another matter. There are many API interfaces to access an XML file in a read-only forward-only manner. I settled for pulldom with Python.

I began to draw my algorithm on a blank sheet of paper after creating some code to read the files. I often like to take a look back at where I am going on paper before investing more time coding. My first scenario was the most simple one, finding out if an element has been added or removed from either file.

After a few sketches, I found out it would be impossible to figure that simple case in a forward-only manner without storing some part of the file in memory and in the worst case, nearly storing the whole file in memory. That pretty much killed my first goal.

After, I choose to search the web for some tip on how to compare hierarchical structure like XML file using a random access. My new goal was to load both tree in memory and compare them. I found out many graduate papers on different algorithms to perform that kind of comparison, but there was nothing simple with them.

Finally, I choose not to build it. XML diff is hard and it is not for me. I will use the tools already available instead of building mine.