The Stasi puzzle

The former East Germany Ministry of State Security, better known by its acronym Stasi, spied on citizens for more than 40 years and kept documents of everything in thousands of files, ranging from interrogation transcripts and intercepted mail to internal documents on espionage and business connections with the West. But after the fall of the Berlin Wall, Stasi staff tried to destroy as many of those documents as possible, and what they couldn't destroy with shredders, they did by hand.

What they left behind were more than 15,000 sacks full of an estimated 600 million pieces of torn documents. Five years after the Wall fell, 40 employees of the German agency in charge of salvaging the documents opened the first bags and began piecing the fragments together by hand. Their contents are of immense importance for understanding how the East German regime functioned.

No clues

Today, 12 people continue to sort through the fragments - piecing together some of the destroyed documents. "I take a pile of papers in which I see some similarities, and then I try to put the pieces of the puzzle together," said Ines Splettstoesser. "Sometimes you're lucky and the documents were only torn only in half."

Splettstoesser and three of her colleagues are at a huge table full of document fragments on the third floor of the former Stasi headquarters in Berlin-Lichtenberg. The pieces that match are glued together and archived. The employees have no clue what the finished page will look like. They don't even know if all the missing pieces are in the same sack.

Depending on the sack, there have been times when an employee spent a couple of years sorting through a sack without finding all the necessary pieces," said Joachim Häußler, one of the project's managers.

Sophisticated algorithms

Piecing together the Stasi puzzle has been going on for 18 years, and it could still take several more decades to produce any significant results if the effort continues by hand. A new technology, however, could help speed up the process.

In 2007, the German government commissioned the Berliner Fraunhofer Institute for Production Systems and Design Technology (IPK) to develop a computer system equipped with scanners and based on pattern-recognition algorithms to quickly piece together torn documents. The system, known as the "ePuzzler," has been in operation since the beginning of the year.

Thousands of fragments, many of which are not much bigger than a two-euro coin (about the size of a US quarter), are spread out between two protective films on the scanner's glass plate in the institute's screening room. A scanner takes in both sides at the same time. Seconds later, all the snippets appear on the screen on the wall. Once digitized, they can now be analyzed by the software.

"We calculate a number of features from each snippet, especially the distinguishing ones," said Petram Nickolay, who heads the project at the Fraunhofer Institute. The system, he added, is able to distinguish colors, type of paper and shape. It also determines whether the document was written by hand or machine. "The system searches for snippets that have as many common features as possible," he said.

Still some adjustments necessary

Most of the major development work on the ePuzzler is done, and the system is busy compiling pages for the archive. But before it can be rolled out on a large scale, it must first be put to the test sorting through 400 sacks. For a large-scale implementation, Fraunhofer Institute researchers said they still need to improve the performance of the scanners and find a way to automatically clean, straighten and place the snippets on the scanner. These tasks currently require too many people.

Some manual work will still be necessary in the future despite the ePuzzler. People will be needed to decided what should be reconstructed and assist when the computer system runs into problems.

The software, notes Nickolay, could find other applications as well. "We have been asked to test the software on piecing together fragments of paintings and shredded financial documents," he said.