Wednesday, 10 January 2007

Buy your own replicator

Every time I was watching StarTrek, I longed for that replicator machine. Such a machine would make a lot of trips to the annoying and crowded supermarkets unnecessary. Other people must have thought the same way; meet the Freeform Fabricator [echo] or "fabber".

Well, it isn't exactly a matter replicator, but it is a form replicator. While the technology isn't exactly new, this is a desktop version, a 3D printer of some sort that anyone can use. Combine it with a 3D scanner and with the sharing power of today's Internet, and you have (at least) downloadable art, children's toys, kitchenware, presents for women, simple tools, anything. One could even use it to duplicate keys, no matter how complex :)

I am waiting for this concept to grow and become more accessible, but I think it will quickly become a trend, like microwave or teflon.

Tuesday, 9 January 2007

Super fast string distance algorithm: Sift2

Update!! Read the Sift3 post. It is an even better algorithm.


A while ago I wrote a little algorithm that tried to cope with the large amount of time that the Levenshtein edit-distance algorithm took to compare two strings. It was a really funny algorithm, but it was fast enough to show me the similarity between strings that, after all, should have been either very similar or different.

Meanwhile I started thinking if I could improve on it. I was sure I could, because it wasn't very scientific, it was empirical. And finally I did it. This is the Sift2 algorithm, along with an SQL server function that can make one million string comparisons in 2.5 minutes. Compared with Levenshtein, Sift2 performs 10 to 25 times faster and it is four times faster than Sift.

The concept:
  • Starting from the beginning of both words, compare the letters on the same position.
  • If the same, move forward, else search the letter from the first word in the next maxOffset letters in the second word and viceversa.
  • Offset the words according to the closest found letter, add 1 to distance
  • Repeat until one of the words ends
  • Add to the calculated distance half of the length of string remained unparsed from the other word
That's it! Here is the code:


C# Code (double click to show/hide)




T-SQL code (double click to show/hide)



You can find a nice OOP Javascript implementation at IT BASE.

Performance:
The algorithm seems to be working fine for letter insertions, typos, letter inversions and such. It gives slightly different values than Levenshtein when big words are inverted. When a lot of letters are inverted, the difference from Levenshtein increases. Example: abcdefghijkl vs. badcfehgjilk (every two letters inverted) results in 0.42 similarity in Levenshtein and 0.08 in Sift2. But let's face it, the two words are really different.

Update:
I've optimised the algorithm a little and also changed the formula so that it matches the Levenshtein distance as close as possible. The basic idea remains the same, but now the average error from Levenshtein (calculated or real company name and address data) is only 3%.
Some people saw the goto line and immediately laughed. Well, I tried replacing it with a break and a subtraction and even removed the subtraction altogether (thus maiming the algorithm) and the goto implementation was still the fastest. So I will continue to use goto, as it is more efficient.

Request:
I have seen a lot of people actually searched on Google and got here. I would really really really like some comments, links to implementations or whatever... It's my baby after all. Thanks!

Sunday, 7 January 2007

I killed my first person tonight

It was going to be an easy job. Get in, do something, get out. It wasn't much, the reasons for doing it were rather more intellectual than financial. I was making a point, kind of like Robin Hood. But she was there. The thing was done, she could see it. She wasn't in a position to stop me. She looked at me, sized me up, found me lacking. Something was terribly ugly on her face when she howled and threw herself at me, shouting all the time. It was like I have offended her on a personal level, like she wouldn't take defeat, one that was obvious at the time we've met.

So I did it. In fear, panic more likely, with all my power, I stabbed her with the screwdriver I've used to get in. I did it once, twice, three times. I didn't believe that it was so easy to stick something that long in a human being so easily, through clothes, skin, meat... She looked at me, with annoyed surprize, my screwdriver dripping blood, her official looking shirt dirtied by three horrible red dots, she looked at me for the longest of moments, her face showing angry disaproval, hateful disgust.

Then she attacked again, with renewed force, in silence, which actually made her even scarier, like a demon from hell. Her face contorted by unmistakeable hate, she pushed me with all her strength, trying to claw at my eyes. All I could do is let me be pushed, holding her arms, trying to defend myself, until I reached a stair rail with my back. We couldn't go any further and starting from a mischievous thing, the simplest of things, I was fighting for my life with a witch which I've just stabbed, but didn't die. So I tried to throw her down the stair case, three floors down, which I am sure would have killed her.

But she clang to me, she knew she would fall, but instead of thinking of saving her life, she pulled at me, trying to make me fall with her. She wanted me hurt, dead, she wanted to avenge something terribly ugly from her own life, which, I am sure now, had nothing to do with me personally. She was scarred, long before I got there, with my bloody Johnson screwdriver. But right then, the only thing I could think about was I was going to die. But I didn't. Somehow I landed safely on a stair underneath, while the hag took the plunge.

She didn't die, though. Clinging to me has slowed her fall, so now she was sprawled on the floor downstairs, mumbling something, her legs in an awkard position. I went to her, partly because I wanted to get out, and I had to use the stairs, partly because I wanted to see her, to see what I have done, my brain in shock, yet sickly curios about the bloody mess I have caused.

She was clearly dying, her face wasn't wrinkled in hate anymore, she looked... peaceful. But she was alive and she looked at me with something resembling love or something similar. All her scars were gone in that moment and her thoughts, or what had remained of them after hitting the floor with her head, weren't evil anymore. There was no anger on her face and that made her look, well, beautiful. She was about 50, maybe more, but she looked like someone good at heart, like an innocent child.

So I did the only thing I could have. I kneeled next to her, I took her head in my hands, conforted her for a moment, telling her it will not hurt for long, then I snapped her neck. It isn't so easy as in the movies, I had to try several times, making this more of a mess than it already was. When I heard the snap, like in a chicken's neck, I turned her head in the other way, just to make sure that she was dead, not paralysed or feeling pain in any way.

Of course, That wouldn't have made it all better, I have done all of that, and I knew it, and my soul was crying and a huge depression engulfed me, like I had killed a part of me. And I also knew that no one would have waited for her home. She was this spiteful angry hateful person that no one liked, that stayed at the work place during the night because there was nothing waiting for her outside. I was sure that the members of her family would feel partly relieved that she was dead. And the only person that saw her beautiful, the only person that saw, even for the briefest moments, beyond that wall of negative emotions, was the man that had killed her.

At the time, struggling with all my strength to break that woman's neck, I had wished that I was more efficient in stabbing her, less panicked, maybe sticking her in the heart, killing her instantly, but now I know I was meant to see that beautiful face, that it couldn't go any other way, that I was meant to see that face looking at me, with an innocent sadness, for the rest of my life.

Saturday, 6 January 2007

What is love funny animation!

I've stumbled upon this dugg link that shows a very cool animation. I am reproducing it here, because of annoying commercials on that site.

Also, if you have an iPad or some other device that doesn't support Flash, you're out of luck.

I am reproducing here two larger collections of What is Love thematic song remakes :) They're kind of funny.



Friday, 5 January 2007

Oh no! Saddam again?

Well, I just had to say something about the video of Saddam Hussein's execution. But I'll try to be brief and focus on only two things: the censorship applied to the official video and the US comments.
First, the big row shouldn't be about Saddam at all. Whatever he did, why he did it and how harsh a punishment he deserves is an internal Iraqi affair, and their... democratic history... leaves to be desired. It's not like they know how to behave in a dignified manner, anyway. No, the problem is the censorship on the official video. Somehow, they realised that how they did the whole thing was wrong. They got it! It was wrong. But, in their typical governmental greed, they removed the sound, clipped the video, and spun the story as they could to actually make them look good.
The second issue, the US government made a statement that said they would have done everything in a different way and that it all boils down to the inexperience of the Iraqi government. But they were referring to the leaked video! So what they actually said, publicly, is that they had more experience in limiting media access and manipulating public opinion. Which, of course, they do, but that's besides the point.
Both these situations show only one thing: shamelessness, the lack of shame, on the part of any government. It's beyond 'power corrupts', it's all about the corrupted seeking power and getting it, wrapped in a nice 'democratic' package.

There is no statistic that I know of that calculates the percentage of "media leaks" in situations like this or Abu Ghraib, etc. In other words, a formula that could estimate the actual number of cases based on the number that were recorded on tape and made it to the public. But my guess is it's similar to fossiles. Only a small fraction of dead animals fossilise in order for archeologists to find them. Such leaks show a trend, rather than exceptions. They also help "them" to become more "experienced".

Wednesday, 3 January 2007

Tuesday, 2 January 2007

The Embedding, by Ian Watson

Ian Watson
Reviews

I've first started reading this book with aprehension, it seemed to involve weird and useless experiments, a heavy language or writing style, socialist concepts and a lot of bull. After a while, however, it started to become interesting. The concepts were refined, the gray areas explained, aliens appeared... it seemed to gather pace. After reading 90% of it I was looking forward for the grand finale. Which was nothing but a big and sloppy hiss.

The whole idea of the book revolves around the nature of reality and our perception of it. It starts from three different points of view and it seems to have a very good foundation to build on. It does present some concepts that might have value, but in the end, it fails miserably. I guess the author was unable to carry everything through or he just got bored with it.

But do bear in mind that it's his first novel, written in 1973, and he won the Apollo Prix in 1975 with it.