Archive for the ‘Tech Stuff’ Category

Simple TRIE implementation

Tuesday, February 8th, 2011

Its been a long time since my last post. But I finally have some free time at least till march begins. Here is a simple implementation of the TRIE Data structure. Its not the compressed TRIE, but the real simple one (using arrays instead of lists). I have done some very simple tests on it. I am more curious to know what is the memory charge for this implementation on a really large DB of words maybe 3,00,000 or so. My next target will be to implement a compressed version of it and see the difference.

Meanwhile feel free to use this copy.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
/*
 * Trie.h
 *
 *  Created on: Feb 8, 2011
 *      Author: sameekbanerjee
 */
 
#ifndef TRIE_H_
#define TRIE_H_
 
struct trienode
{
	char value;
	trienode* children[26];
	bool end;
	trienode();
	trienode(char value_);
	virtual ~trienode();
};
/*
 * Really inefficient Implementation of Trie
 * But easy to use and understand
 */
class Trie
{
public:
	Trie();
	virtual ~Trie();
	void addword(const char* word);
	bool search(const char* word);
private:
	bool validate(const char* word);
	trienode root;
};
 
#endif /* TRIE_H_ */

The implementation follows:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
/*
 * Trie.cpp
 *
 *  Created on: Feb 8, 2011
 *      Author: sameekbanerjee
 */
 
#include "Trie.h"
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <cctype>
#include <cassert>
const unsigned int MAXLEN = 12;
/*
 * Implementation of trienode
 */
trienode::~trienode()
{
	for(int i=0; i<26;i++)
		delete children[i];
}
 
trienode::trienode():value(0),end(false)
{
	std::memset(children,0,sizeof(trienode*) * 26);
}
 
trienode::trienode(char value_):value(value_),end(false)
{
	std::memset(children,0,sizeof(trienode*) * 26);
}
 
/*
 * Implementation of TRIE
 */
Trie::Trie()
{
}
 
Trie::~Trie()
{
}
/*
 * Takes a word and adds it to the dictionary
 */
void Trie::addword(const char *word)
{
	if(!validate(word))
		return;
	const char *p=word;
	trienode *current=&root;
	while(*p)
	{
		char c=tolower(*p);
		unsigned int pos=c-'a';
		assert(pos<26);
		if(current->children[pos]==0)
		{
			current->children[pos]=new trienode(c);
		}
		current=current->children[pos];
		p++;
	}
	current->end=true;
}
/*
 * Take a word and searches in the dictionary
 * Returns true if it exists false otherwise
 */
bool Trie::search(const char *word)
{
	if(!validate(word))
		return false;
	bool flag=true;
	const char *p=word;
	trienode *current=&root;
	while(*p)
	{
		char c=tolower(*p);
		unsigned int pos=c-'a';
		assert (pos<26);
		if(current->children[pos]==0)
		{
			flag = false;
			break;
		}
		current=current->children[pos];
		p++;
	}
	if(flag)
	{
		if(current->end)
			return true;
	}
	return false;
}
 
bool Trie::validate(const char *word)
{
	if(strlen(word)>MAXLEN)
	{
		std::fprintf(stderr,"Maximum length of Word exceeds %d\n",MAXLEN);
		return false;
	}
	const char *p=word;
	while(*p)
	{
		if(!isalpha(*p))
		{
			std::fprintf(stderr,"Words should only contain alphabets\n");
			return false;
		}
		p++;
	}
	return true;
}

Or Download the project here. TRIE

A word of caution: This is only tested on GNU C++ compiler for mac. This should compile on all other GNU versions, but may require minor changes if you try to compile it on Visual studio.

Also I tried the new wp-syntax plug-in. It is supposed to be cool but I don’t see any syntax highlighting, only line numbers. It may be clashing with my theme. I have to dig in to it.

Tags: , , ,

Huffman Coding

Saturday, August 21st, 2010

Just got into coding in DS and Algorithms again. Here is my implementation of the huffman coding in C++. Pretty simple stuff if you make use of STL extensively. There are no comments and the classes are not properly written. If you want to learn more about Huffman Coding, visit here.

Download source code from here huffman.tar.gz.

Tags: , , ,

Installing RHEL Server release 5 (Tikanga) on Dell Optiplex 755

Monday, December 15th, 2008

Recently I tried installing Red Hat Enterprise Linux Server release 5 (Tikanga) on my Dell Optiplex 755 box. As i was expecting, i ran into quite a few problems. I was doing a media installation.

A.  Problem #1: During the booting from CD, it couldnt detect my HDD. Solution: Change SATA Operation to Legacy mode in the BIOS.

B. Problem #2 : After installation, my nic was not detected. Solution: Have to update driver for nic. Get it from here. Check if its the latest version. After downloading it, compile it……….umm…just follow what is written in the README file.

C. Problem #3 : Sound Drivers are not yet detected. Solution: Still searching for the ausio drivers. I’ll post it as soon as i find it.

Cheers!

Tags: , , , , , ,

Chrome!!

Tuesday, September 2nd, 2008

Google is launching the beta version of its brand new browser called CHROME. Seems interesting to me. I guess they wanted to start from scratch and develop a browser more suited for what Google wants to achieve. The storybook for Chrome is a pretty decent read. Check it out here. I am pretty eager to see where this goes.

Continuing on browsers… FireFox recently launched its 3.0.1 version.  I haven’t used it extensively yet. But seems that the Real-Player plug-in that you could use to download streaming videos (from YouTube, etc.) will not work in 3.0.1 . So if you want to use Real-player plug-in with FireFox 3.0.1 wait till Real introduces its own compatible version.

Why I dont like Dell

Friday, August 15th, 2008

About two weeks ago I ordered a laptop from Dell. A hefty price tag of 50k. Well I confirmed my order and then about 2 hrs later I got a call from my bank. “Sir, have you made 2 transactions from Dell, each of 50k each??” . “WTF?? No way! Only One.” I tried to answer frantically. “But we have already approved both the Transactions.” “Are you kidding me?” “Please call DELL immediately” “You don’t have to tell me that.”

By this time you must realize what kind of deep shit I am in. Well that mess took 4 days to resolve. I still don’t know if I am going to be billed for both the transactions. Any way after patiently waiting for 8 days (as told to me by the Sales Person), When the delivery day came, I was licking my fingers in anticipation. When I called Dell to confirm about it, guess what response I got….”Sir! due to unexpected part shortage we are forced to delay the shipment by 20 days. Please Adjust!!”. Dell Sales……You are full of raw sewage. I hope you choke and die on your filth. But wait till I get my Laptop. If I get any problem with the m/c I am coming to Bangalore to break the thing over your head. You big piece of Dog-Turd. If you are ordering from Dell, then confirm the date of delivery before booking. Those crooks lie through their teeth. Burn in Hell MFs.

Harman-Kardon Soundsticks II

Saturday, August 2nd, 2008

I bought a HK soundsticks II recently and I have got to say, I am blown away. First of all, It looks awesome and I thought that the hefty price tag, (Rs. 11k) is just because of the looks. But no son…. The sound is (if possible) even better. The online reviews were all positive about this product. I am really looking forward. The only bad thing about this is that there is that you can’t connect your headphone directly to the woofer, But if you are using a laptop, it doesn’t matter much. All in all I would say the price is on the higher side but well worth it (damn you Govt. of India….slash the duties so we can get it for cheap). Let hope mine lasts for at least a couple of years. Any Comments?

Wrapped in Python!

Tuesday, April 8th, 2008

Since the last month, I have been shifting my focus from PHP to Python. Its not like I myself found anything wrong with PHP. Its just that while having a conversation with a friend of mine, he mentioned the latest craze in the Web Application Framework area, Some odd sounding thing called Django. “Django?? That sounds like some-kind of Music!! What kind of idiot would name a serious application with that name?”, I said to myself. But somehow my friend ( a very persuasive individual), convinced me that Django is really worth looking into and its written in Python. So, here I come Django! To be entirely honest, before that I never actually saw a single line of code written in python in my entire Life. Took print of whole django-book. And started reading it in the nights. I cannot believe how simplistic their approach was. It turned out to be my bible. I put my plans on hold. Started learning Python. Python’s philosophy was again one of the best ones i have ever laid my eyes on. It seems like a human beings’ programming language. All other languages now seem to me designed by robots.

A little bit of trivia ” Python was Designed by Guido Van Rossum. And named after the Monty Python‘s Flying Circus sketch. So even though the logo looks like a python, It was never meant to be equated to the nasty reptilian.”

Also it Turns out the name Django is indeed related to music. The framework is apparently named after a famous jazz musician “Django” Reinhardt. Serious jazz enthusiasts, please don’t grind your teeth in anger. I was never a jazz fan and so never came upon the name of the great musician.

All in all, I would call the last few weeks very productive. I am feeling like a new convert. And more keen to learn more of Django and python. Already have developed a simple desktop application using wxPython. Looking for a good IDE to Djumpstart with Django. Anybody has any suggestions, feel free to comment. So far I have looked at Pydev, the Eclipse plug-in, maybe the django guyz will bless us with one in the near future. Until next time……alvida!!