I must admit that I simply read the description and sent link.
You will need a database because you need to store records of the long and short URL.
Technically it's not the only option short of writing each apache rule for each URL or using a text file but do not recommend anything else except for database because of ease, security and speed.
Here are 7 free scripts that look very promising.
http://www.webresourcesdepot.com/7-open-source-and-free-url-shortener-scripts-to-create-your-own/This one was updated yesterday:
http://code.google.com/p/phurl/