The themes Human Compact and Clearlooks Compact have been quite a success, and I got several requests to make a tutorial on how to create such a compact theme.

UPDATE: Human Compact Theme for Ubuntu 8.10 (Intrepid Ibex) is available!

Well, it is a bit difficult to create a step-by-step tutorial, but I will try anyways. Prepare to fiddle around with your configuration and try it out several times until you get the desired results.

1. All your Gnome themes are located under /usr/share/themes. Find the theme of which you want to create a compact one, and copy it into your home directory with e.g.

   cp -r /usr/share/themes/Human ~/.themes/Human-Compact

2. If there is a file index.theme, open it and change all the names (e.g. add “Compact” where appropriate). This file is necessary if you want to directly choose the theme from the Appearance Preferences; if it is not available you have to choose a theme and select “customize” to select the compact controls for it.
3. Now to the fiddling part. Open gtk-2.0/gtkrc, and change lots of thickness and width settings… When you do this, always check how your changes work visibly, e.g. if the application still have usable borders etc. To help with the fiddling, I have added a diff of the Human vs. the Compact theme, you might be able to reuse some of the settings there.
4. Once you are satisfied with your theme, you can create a .tar.bz2 distribution for backup or to be used by others, e.g. with this command:

   cd ~/.themes
   tar cjvf ~/Human-Compact.tar.bz2 Human-Compact

5. That’s it. Have fun with your theme!

Read more

I recently got a nice new camera that can shoot HDTV videos, and the only way to show off the awesome quality to the world is by creating flash videos by myself. Here is an example:

I use Ubuntu, so this tutorial won’t work on Windows. I have encoded the video into the H.264 format, left the original resolution at 848 x 480, and the framerate at 30 Hz. I use constant quality setting because then the video look very good even when the camera moves quickly, and it uses less bitrate when not needed. The disadvantage is that the required bitrate is uneven, so make sure youre buffer is large enough before you start playing.

Here is how to do this:

1. Encode your video with mencoder (click to install). It has to be x264 for video (0 or 1 bframes), and faac for audio.
2. Convert the result into an mp4 using mp4creator (click to install), as described here.
3. Now you have an mp4 file that can be played with JW player. Download it, have a look at the readme.html, and follow the example described there.
4. The player requires 20 pixels in height, so add this to the SWFObject creation.

I have written a small ruby script to convert any movie to a MP4 file. The first parameter is the input file, second parameter is the framerate. Save this file as e.g. convert2mp4.rb.
Read more

This sunday I was on a fabulous via ferrata (german translation is “Klettersteig”). Here is a video of it:

The via feretta is called Teufelsteig which translates to devli’s steep road.

Walking through difficult terrain, close to the peak

A view around to nearby peaks and chines

Finally, after about 4 hours hiking and climbing, we have reached the peak of 1822m and enjoy the view

On 29th August, we went on a cool mountain biking trip around the Damberg. Here is a map of the famous Damberg Kriterium. It is about 43 km, and 850 meters in altitude (bikemap overestimates 1040m). It was a fun trip, thanks for Jürgen (who was NOT the organizer) for organizing this! Here is the route:

I got a brand new Panasonic Lumix DMC-TZ5, which is an absolutely excellent compact camera. It can record HDTV 16:9 videos, so I did what obviously everybody should do: mount it on a cycling helmet. The construction seems adventurous: I use the camera’s, one cut-off mini tripod, one rubber band, my cycling helmet, the camera’s wristband as a safety backup, and a healthy dose of good faith. That’s it! The whole construct may look a bit fragile, but simplicity is the key; it is actually very sturdy, because of the simple design there is almost nothing that can go wrong. The camera position is excellent too. Jürgen has made a really cool remix of the videos:

If you want the the videos in all their length and glory, I have encoded the clips with very high quality for your maximum viewing pleasure. You need a fast computer, an up-to-date flash player, and a fast internet connection (press play and then pause to start caching the whole clip if the connection is too slow.).

Read more

Today I have got some sourcecode for you. There is a little programming challenge named The Self-Documenting Code Contest that is quite fun, they try to find the cleanest and easiest to read code for this task:

Write a program that generates all two-word anagrams of the string “documenting”. Here’s a word list you might want to use: wordlist.zip.

When you’re done, send the results to selfdocumenting@hotmail.com.

Good luck!

So this caught my interest and i wrote a little entry in Ruby that is 23 lines long with whitespace and very nice to read. But I won’t show you this code until the contest is over, and this is not the reason for this post. The reason is, that the nice version takes about 2 seconds, and somebody else has coded a Python solution that takes only 1 second (I have no idea what his code looks like). This post is about a fast anagram finding algorithm, and how I developed this algorithm. The final result takes about 0.11 seconds.

Algorithm

The most basic algorithm has two phases:

1. Read in the file
2. Build all combinations of two words and compare the letter count with the query.

Building the combinations is usually done with two nested loops and takes O(n^2) runtime. This is slow, so I have added another step in between:

Idea #1: Filter out Candidate Words

The second step is really slow, but it would be a lot faster if it has to handle less words. So I wrote a little filtering step that lets only words through which are made out of the same letters as the query word.

For example when the query is documenting, the word men or go and even too are extracted, even if the number of letters might not match. But that’s not important, what is important is that the number of possible words are reduced a lot, and so the next phase is faster.

Idea #2: Use a Commutative Hashing Function

String comparisons are slow. To common way to find out if the strings coming with tuned is an anagram of the word documenting is to sort the letters and make a comparison, like this:

irb(main):003:0> "documenting".unpack("c*").sort.pack("c*")
=> "cdegimnnotu"
irb(main):004:0> ("coming" + "tuned").unpack("c*").sort.pack("c*")
=> "cdegimnnotu"

The strings are equal, so we have a match. But this comparison is terribly slow! What’s worse, the computations have to be redone for each match. It would be much better to just compare hash values, and find a hash function to quickly check if we might have a match, and only do the string comparison when the hash check matches. The hash has to be good enough that we don’t have too much false positives (hashes are equal but the real comparisons not) to get a speed advantage. So why not just sum up all the letters bytes?

irb(main):005:0> "documenting".sum
=> 1181
irb(main):006:0> "coming".sum + "tuned".sum
=> 1181

Ruby’s String#sum does exactly this. we can now precalculate the sum for each word, and to find a match we just add the two hashes and compare the result to the query’s hash:

irb(main):007:0> query="documenting"; first="coming"; second="tuned"
=> "tuned"
irb(main):008:0> first.sum + second.sum == query.sum
=> true

When this very quick check returns true, we have to do the string comparison to be absolutely sure it is a match. This considerably speeds up the whole program, but it is still O(n^2).

Idea #3: Reformulate Problem

Now here comes the trickiest and coolest part. Since Idea #2 the slowest part is matching the numbers, with still quadratic complexity. But the hard task is not anagram finding any more, we have reduced it to finding two hashes that combined have the same hash as the query. We can reformulate this problem into something completely detached from the anagram problem:

Given a list of numbers, find all combination of two numbers that add up to a given number

When we concentrate on just this problem and ignore the rest, we might come up with a better way of doing things.

I came up with a fast solution, described below. Somebody posted a better solution that is both faster and simpler, if you want just this final solution skip ahead to Idea #4 as the following description is outdated.

It clearly looks stupid to just try all combinations to add the numbers.
So lets sort them first. Quicksort is fast, especially with numbers, so no worries here. Now consider a list of numbers like this example:

1   3   7   10   10   12   17   20   22   23   24   24   25   26   30

Find all the combinations of two number that add up to 27. They are

• 1 + 26 = 27
• 3 + 24 = 27
• 7 + 20 = 27
• 10 + 17 = 27
• 10 + 17 = 27 (a second time)

You can detect a pattern here: the first number always increases, the second number always decreases! We can now formulate an algorithm for this:

We can have two pointers to the array, one starting from the left side, the other starting from the right side. When the numbers behind the pointers add up to a bigger result than the query (e.g. 1 + 30 = 31), we decrease the right pointer to find a smaller combination (1 + 26 = 27). When the sums are too small (1 + 25 = 26), we move the left pointer to the right (3 + 25 = 28).

This way we walk through the whole array in O(n) time and the sum of the pointers is always kept as close the the desired result as possible. When the pointers meet each other, we can stop the whole process or otherwise we would just reverse the words.

This algorithm gets a bit more complicated when you consider that we might have lots of numbers in it that are equal, whenever this happens you have to fall back into an O(n^2) matching algorithm for just this section.

Idea #4: Use Hash directly

UPDATE Scrap the implementation in idea #3. A blog post here from a reader of this article posted a way to do this really in O(n), without any sorting which is O(n*log(n)). The idea is to use a hashmap that maps from the hash key of the word to its matches:

M = {}
S = the target sum
for each element e in the list
      if M[S-e] exists? (e,S-e) is a pair
      add e to the M

Just use a Hashmap that maps from the cummulative hash of a word to a list of words that have the same hash. Whenever a new word is added, get the list of words that is stored under query.sum - current_word.sum. When the hashes are the same we just have to create a list of all the matches under this key, and check each of the matches sequentially for equality. This is just normal hash collision handling through a linked list. That’s very simple and works like a charm.

I have revised the code, it got both simpler and faster. That’s a win-win situation, wohoo!

The Sourcecode

I hope the code is understandable now with the above explanation. If you have any questions or ideas, please share them here!

#!/usr/bin/ruby

# created by Martin Ankerl http://martin.ankerl.com/

class String
	# creates an array of characters
	def letters
		unpack("c*")
	end
end

class Array
	# converts an array of letters back into a String
	def word
		pack("c*")
	end
end

query = "documenting"
query_letters_sorted = query.letters.sort
txt = File.read('wordlist.txt').downcase

# to quickly check if a letter is part of the query word
used_letters = Array.new(256, nil)
query_letters_sorted.each do |letter|
	used_letters[letter] = true
end

# Maps from cummulative hash of a word to a list of words that have this hash code.
hashToWords = Hash.new do |hash, key|
	hash[key] = Array.new
end

query_hash = query.sum

prev = 0
txt_size = txt.size
separator = 10
idx = txt.index(separator, prev)
while prev < txt_size

	letter_idx = prev

	# no need to check end of word because it is \n
	# which is not part of the word anyways
	while used_letters[txt[letter_idx]]
		letter_idx += 1
	end

	# ignore word if the above quick check fails
	if letter_idx == idx
		word = txt[prev, idx-prev]

		# check all key matches
		key = word.sum
		hashToWords[query_hash - key].each do |other_word|
			if (word.letters + other_word.letters).sort == query_letters_sorted
				puts "#{word} #{other_word}"
				puts "#{other_word} #{word}"
			end
		end

		# insert word
		hashToWords[key] << word
	end

	prev = idx + 1

	# no need to check end of file because we have to end with new line
	idx = txt.index(separator, prev)
end

When you rewrite the algorithm in C++ or Java or Python I am sure it will be faster than this one. But this is not the point of this post. The point is, “The Best Optimizer is between Your Ears” (Michael Abrash, Graphics Programming Black Book).

Have fun!