Year: 2007

The Internet has a lot of tamil song lyrics in English. Finding them is not easy, though. Two problems. The lyrics are fragmented: there’s no one site to search them. And Google doesn’t help. It doesn’t know that alaipaayudhe, alaipaayuthe and alaipayuthey are the same word.

This is similar to the problem I faced with tamil audio. The solution, as before, is to make an index, and provide a search interface that is tolerant of English spellings of Tamil words. But I want to go a step further. Is it possible to display these lyrics in Tamil?

My Tamil Transliterator does a lousy job of this. Though it’s tolerant of mistakes, it’s ignorant of spelling and grammer. So,

kanda nal muthalai kathal peruguthadi

… becomes…

kanda nal muthalai kathal peruguthadi

… when in fact we want…

kanda naaL muthalaay kaathal peruguthadi

(If you’re viewing this on an RSS reader, check my post to see what I mean.)

I need an automated Tamil spelling corrector. Reading Peter Norvig’s “How to Write a Spelling Corrector” and actually having understood it, I gave spelling correction in Tamil a shot.

Norvig’s approach, in simple terms, is this:

1. Get a dictionary
2. Tweak the word you want to check (add a letter, delete one, swap 2 letters, etc.)
3. Pick all tweaks that get you to a valid word on the dictionary
4. Choose the most likely correction (most common correct word, adjusted for the probability of that mistake happening)

Making a dictionary is easy. I just need lots of Tamil literature, and then I pick out words from it. For now, I’m just using the texts in Project Madurai.

Tweaking the word to check is easy. Norvig’s article has a working code example.

Picking valid tweaks is easy. Just check against the dictionary.

The tough part is choosing the likely correction. For each valid word, I need the probability of having made this particular error.

Let’s take an example. I’ve spelt kathal. A list of valid tweaks to this word include: kal, kol, kadal, kanal, and kaadhal. For each of these, I need to figure out how often the valid tweaks occur, and the probability that I typed kathal when I really meant one of these tweaks. This is what such a calculation would look like:

Tweak	Frequency	Probability of typing kathal	Product
kal	1	0.04	0.04
kol	4	0.02	0.08
kadal	10	0.1	1.0
kanal	1	0.01	0.01
kaadhal	6	0.25	1.50

Once we have this, we can see that kaadhal is the right one — it has the maximum value (1.50) in the last column, where we multiply the frequency and the probability.

(You probably realise how small my dictionary is, looking at the frequencies. Well, that’s how big Project Madurai is. But increasing the size of a dictionary is a trivial problem.)

Anyway, getting the frequency is easy. How do I get the probabilities, though? That’s what I’m working on right now.

I often need to extract words out of sentences. It’s one of the things I used to build the Statistically Improbable Phrases for Calvin and Hobbes. But splitting a sentence into words isn’t as easy as you think.

Think about it. What is a word?

Something that has spaces around it? OK, let’s start with the simplest way to get words: split by spaces. Consider this piece:

"I'd look at McDonald's," he said.
"They sell over 3,000,000 burgers a day -- at $1.50 each."
High-fat foods were the rage. For e.g., margins in fries
were over 50%... and (except for R&M & Dyana [sic]) everyone
was at ~30% net margin; growing at 25% too!

Splitting this by spaces (consider new lines, tabs, etc as spaces too.), we get the following:

"I'd
look
at
McDonald's,"
...

Now, some of these like “I’d” are words. But “McDonald’s” isn’t. I mean, there’s a full-stop and a double-quotes at the end. Clearly we need to remove the punctuation as well. But, if we do that, I'd becomes Id. So we need to be careful about which punctuation to remove. Let’s take a closer look.

The following punctuation marks are clear word separators: spaces, the exclamation mark, the question mark, semicolon, brackets of any kind, and double-quotes (not single quotes). No word has these in the middle. If we use these as separators, our list of words is better, but we still have some words with punctuation:

McDonald's,
e.g.,
High-fat
R&M
...

The issue is, these punctuation marks are ambiguous word separators: comma, hyphen, single-quote, ampersand, period and slash. These usually separate words, but there are exceptions:

Comma

Not inside numbers: 3,000,000.

Hyphen

Not for hyphenated words: High-fat.

Single-quote

Not for possessives: McDonald’s. Not for joint words: I’d.

Ampersand

Not for abbreviations: R&M

Period

Not for abbreviations: O.K. Not for URLs: www.s-anand.net

Slash

Not for fractions: 3/4. Not for URLs: google.com/search

Colon is ambiguous too. In normal English usage, it would be a separator. But URLs like http://www.s-anand.net/ use these characters, and it doesn’t make sense to separate them.

So here are my current rules for splitting a sentence into words. (It’s a Perl regular expression. Don’t worry. Cooper’s Law: If you do not understand a particular word in a piece of technical writing, ignore it. The piece will make perfect sense without it.)

# Split by clear word separators
/       [\s \! \? \;\(\)\[\]\{\}\<\> " ]
 
# ... by COMMA, unless it has numbers on both sides: 3,000,000
|       (?<=\D) ,
|       , (?=\D)
 
# ... by FULL-STOP, SINGLE-QUOTE, HYPHEN, AMPERSAND, unless it has a letter on both sides
|       (?<=\W) [\.\-\&]
|       [\.\-\&] (?=\W)
 
# ... by QUOTE, unless it follows a letter (e.g. McDonald's, Holmes')
|       (?<=\W) [']
 
# ... by SLASH, if it has spaces on at least one side. (URLs shouldn't be split)
|       \s \/
|       \/ \s
 
# ... by COLON, unless it's a URL or a time (11:30am for e.g.)
|       \:(?!\/\/|\d)
/x;

This doesn’t even scratch the surface of the issue, though. Here are some issues:

• Lots of files split words into two at the end of a line. How do we handle that?
• How do we handle incorrect punctuation? For instance, if someone types “done.Yet,” without leaving a space after the full-stop, I’ll think it’s an abbreviation.
• What about other separators? Like the ± symbol or the £ symbol for instance.
• What about other languages?!

And you thought it was easy!

In some of the Web projects I’m working on, I have a choice of many small files vs few big files to download.

There are conflicting arguments. I’ve read that many small files are better, because you can choose to use only the required files, and they’ll be cached across the site. (These are typically CSS or Javascript files.) On the other hand, a single large file takes less time to download than the sum on many small files, because there’s less latency. (Latency is more important than bandwidth these days.)

I ran some tests, and the answer is rather easy. The graph below shows the average time taken to download a file of size 1KB – 100KB.

The X-axis is the size of the file. The Y-axis is the number of milliseconds taken to download the file, averaged over 10 attempts on my home computer. (I did the same thing at work and at a client site. The results are similar.)

The key thing is, it’s not linear. Larger files take less time. Specifically:

• A file twice as big only takes 30% longer to load.
• Breaking a file into two parts takes 54% longer to load.

These days, it looks like few big files are better.

To give you an example: my home page had the following components:

	Size (KB)	Load time (ms)
HTML	25	680
CSS	4	340
Javascript	6	400
Total	35	1420

The total time for these 3 files would be about 1.4 seconds. Instead, if I put them all on one file…

	Size (KB)	Load time (ms)
All-in-one	35	770

The combined file takes only 0.77 seconds — half the download time for split files. It’s a compelling argument to put all your CSS and Javascript (images, too, if possible) into a single page.

But what if people visit multiple pages on my site, and lose the benefit of caching? Not really. The benefit of caching is small. By having a single file, I have 770 – 680 = 90 ms additional time for each HTML to load. But I don’t have to load the CSS and Javascript individually, which takes 740 seconds. The breakeven is about 740 / 90 = 8 page visits.

So, on average, if people, visit more than 8 pages in my site, it’s worth breaking up the CSS and Javascript. But the average for my site is only 2 pages per person. (It’s a skewed distribution. Most, from Google, just visit one page. Few, from bookmarks, visit several pages. On average, it’s just over 2.) I’d argue that unless you’re using an external Javascript / CSS library (prototype, etc.) or people view many pages each visit, you’re better of having a single HTML+Javascript+CSS file.