Year: 2007

Click here to search for Hindi songs.
This is an article on how I wrote the search engine.

I find it a nuisance to have to go to Raaga, search for a song, not find it, then go to MusicIndiaOnline, not find it, then go to Musicplug.in, and so on until Google.

So I got the list of songs from some of these sites, put it together in one place, and implemented a find-as-you-type.

Just go to s-anand.net/hindi and type a song or movie name.

Update: How I created this is a very long story, spanning over two years. And here it is.

---

Over the last 5 years, my MP3 collection had grown quite large. Most of these were from MP3 CDs I had bought, songs I’d downloaded, or songs I’d recorded. In any case, the file names were a mess. In early 2005, I decided to organise the collection and put them all into one big directory per language, and name the files in the format “Movie.Song.mp3”.

People think I’m crazy to use a single large directory. But I prefer one directory with 5,000 files to 1000 directories with 5 files for a simple reason. Searching in one directory is easier than in multiple directories. You can just sort everything by name, date modified, size, whatever. On the command prompt, you can type “DIR dil*.txt” to see all movies starting with “Dil”.

I chose the “Movie.Song.mp3” format because the movie name and the song name were really the only two things I knew about every song I had. I didn’t always know the music director, singers or year of the movie. And I placed “Movie” before “Song” because I often browse songs within a single movie, and it’s useful to sort by name in Windows Explorer and see all the songs in a movie. I’ve never had a need to sort by song name. If I wanted to find a song that started with, say, “pehla”, I’d just type “DIR *pehla*” on the Command Prompt. (As you might have guessed, I have a Command Prompt window always open.)

So, having very rationally organised my music collection, I was happy.

Soon the problem shifted to song discovery. I’d heard the familiar songs in my collection many times. Of the unfamiliar songs, but I didn’t know which to pick. I knew I liked some music directors more than others, and had a hunch I liked older songs. (My subsequent analysis of song preferences confirmed this.) But I didn’t know the year or music director for any of my songs.

Since Raaga had a decent collection of songs, along with the year and music director, I decided to download this information and tag my files with this information. There were two problems. Firstly, the data in Raaga needs to be parsed. I need to hunt through each file to find the year and music director. The second was worse: my song names were spelt differently from Raaga’s.

Step 1: download the HTML and parse it. Perl is pretty much the only programming language I know. I used Perl’s LWP library to download the movie index of Raaga. Each movie in the index always has the URL http://www.raaga.com/channels/hindi/movie/something.html. So I extracted these patterns and downloaded all these URLs as well. (Others have a recognisable pattern as well: http://www.musicindiaonline.com/music/hindi_bollywood/s/movie.some_number/, http://www.musicplug.in/songs.php?movieid=some_number, http://ww.smashits.com/music/hindi_film/songs/some_number, etc.)

You probably realise that I downloaded a fair bit of the entire Raaga.com site’s HTML. Actually, it’s not that big. The 800-odd files in the Hindi collection didn’t take more than 40MB of space, and a few hours to download. Here’s what the code looks like:

# Get the list of movies HTML file
my $index = get("http://www.raaga.com/channels/hindi/movies.asp");

# Extract the list of movies from that into a hash (movie, url pairs)
my %movie = ($index =~ m|<a href="/channels/hindi/movie/([^"]*).html" class="[^"]*">([^>]*)</a>|gsi);
 
# Loop through each movie
for my $file (keys %movie) {
  # Get the song HTML file
  my $html = get("http://www.raaga.com/channels/hindi/movie/$file.html");
 
  # Year is typically like this: Movie_Name (1983)
  my $year = ($html =~ m|<b>$movie{$file}\s+\((\d*)\)</b>|) ? $1 : "";
 
  # Music director always has the URL /channels/hindi/music/something
  my $md = ($html =~ m|<a href="http://www.raaga.com/channels/hindi/music/[^"]*" class="black">(.*?)</a>|) ? $1 : "";
  for (split /\n/, $html) {
 
    # Now get individual songs and rating. They always have an onClick="setList(something)"
    if (m|onClick="setList1\((\d*)\)[^>]*>(.*?)<\/a>.*?"http://images.raaga.com/.*?.gif" alt="RATING: ([\d\.]*)"|) {
    $song = $2;
    $rating = $3;
    print join("\t", $movie, $song, $year, $md, $rating), "\n";
  }
}

Incidentally, I’m showing you a simplifed version. I actually wrote the script in a way that I could resume where I left off. The ability to resume was probably the single most useful time-saver in the entire process.

Step 2: match the song names with those on my list. This is tricky. I hate doing it manually. So I developed a set of rules that could compare two spellings of a movie and decide if they were the same or not (see my earlier post on matching misspelt movie names). For Hindi songs and movies, here are my rules (in JavaScript):

w=w.toUpperCase();                      // Convert to upper case
w=w.replace(/\s+/, " ");                // All whitespaces = 1 space
w=w+" ";                                // Ensure there's a space after every word
w=w.replace(/W/g, "V");                 // V=W
w=w.replace(/Z/g, "J");                 // Z=J
w=w.replace(/PH/g, "F");                // PH=F
w=w.replace(/([KGCJTDPBS])H/g, "$1");   // Ignore H after most consonants
w=w.replace(/(.)\1/g, "$1");            // Ignore repeated letters
w=w.replace(/Y/g, "");                  // Ignore Y
w=w.replace(/([AEIOU])N /g, "$1");      // Ignore trailing N after vowel (hein, mein)
w=w.replace(/[AEIOU]/g, "");            // Ignore vowels
w=w.replace(/ /g, "");                  // Ignore spaces

These are the rules, incidentally, that I use in my Hindi quizzes. Even if you type in a different spelling, the rules above will match the correct answer.

I extended these programs over 2006 to cover MusicIndiaOnline, Musicplug.in and Smashits. (I’ve hit a point of diminishing returns, I think, so I’m not too keen on expanding this list.)

Now, with a database of song information, I needed a good media player to view this in. I’ve used several media players over time: WinAmp, Windows Media Player, RealPlayer, iTunes, and MediaMonkey. I’m a big WinAmp fan, but I’ve been forced to Media Monkey now. WinAmp has a 10 second delay before playing any song on my new laptop. MediaMonkey’s not bad, though. The lack of advanced filters is countered by the heavy programmability (I can use Javascript to update MP3 ID3 tags on MediaMonkey). Plus, I get all the WinAmp plugins. As for the other media players, I think they’re junk.

There are five things I want in a perfect media player:

1. Find as I type. I shouldn’t have to type the entire song, or press a “Go” button. I’ll just type. It should show all matches instantly. WinAmp does this, and that’s why I loved it. (Today, most media players can do this.)
2. Advanced filters. Instead of manually creating playlists, I’d rather create filters, like “Highly rated songs in the 2000s I haven’t heard recently”. (See How I listen to music.)
3. Enqueable playlists. When I click on a song, I don’t want my current song to be interrupted. Just play it next.
4. Global hotkeys. I want to pause the song when someone says something — without having to go to the application, search for the pause button, etc. WinAmp does this brilliantly with its global hotkeys.
5. Online and offline integration. I want to be able to search online collections, like Raaga. Unfortunately none of the media players can do this. They have their own collections (radio stations, really), but even these aren’t really searchable.

Since my favourite media players (WinAmp and MediaMonkey) lack only one of these features, I thought I might be able to build them in.

But no such luck. It was almost easier to build my own media player. So I started to build my two weeks ago. My hope was to cover as many of my favourite requirements, beginning with find as you type.

The key to find-as-you-type is speed. You can’t afford many calls back and forth between the browser and the server. Even if people have a fast connection, my server is not fast enough. (A good part of the reason why I use Google applications is speed. Google’s server is blazingly fast, and the design of their applications complements that.) To make find-as-you-type fast, ideally the entire database should be loaded. Then, as you type, I just need to check with the database in memory. But downloading an entire database takes ages! (My full music database is 7MB right now.)

Step 3: compress the database. Rathern than load the full 4MB, I managed to get the page to start after loading 100KB of data. First, I cut down less important fields. Most searches are for a song or movie, rarely for a year or music director. So I took only the movie and song names. That brought the data down to ~2MB.

I don’t need to repeat the movie name across songs. If I have something like this:

Movie1  Song1
Movie1  Song2
Movie1  Song3
Movie2  Song1
Movie2  Song2

I can store this instead as:

Movie1  Song1   Song2   Song3
Movie2  Song1   Song2

I can also eliminate duplicate names. This brings down the space requirements to ~500KB.

The next step was the clever one. I don’t need to load the full database before you start searching! It’s enough to load a reasonable subset, and let you start searching while the rest loads in the background. So my hindi song search engine loads about 100KB of the data from one Javascript file, lets you search, and in the background loads the 400KB Javascript file. As soon as that finishes loading, it displays results from that set as well. (The initial portion is really songs on Raaga. I figured it would represent a decent search set.)

Step 4: find-as-you-type. This is quite easy, actually. I send the onkeyup event to my search function.

<input id="inp" onkeyup="csearch()">

The csearch() function goes through all the songs, checks if there’s a match, and prints all those results.

// Create a case-insensitive regular expression
var re = new RegExp(search, "i");
for (var i in songs) {
  if (re.test(songs[i)) { str += songs[i]; }
}
library.innerHTML = str;

But that, unfortunately, takes ages to finish. If you implemented this as is, you would have to wait 1 – 1.5 seconds between each key stroke. So I made two modifications. Firstly, I restrict the number of results displayed to 100. When you start typing, (for example, you’d go ‘c’… ‘ch’… ‘chu’…) there are several songs early on that match the string, so I don’t have to search through the whole list. This speeds up the search for small strings.

When the search gets bigger, (‘chupke chu’… ‘chupke chupk’…), there aren’t 100 results. So the search has to cover the full list, and that takes 1-1.5 seconds between each keystroke. So I took another clever step. I broke the search into chunks of 5000 songs. That takes a fraction of a second. I search successive chunks of 5000 songs. If I find any results, I add them. Then I wait for a keystroke. If nothing happens, I continue searching the next 5000 after 50 milliseconds, and so on. If you press a key in the meantime, I stop searching for the original word, and start searching for the new word. This makes the application appear a lot faster.

There are ways I could make this even faster. For example, people type more often than delete. A typical sequence would be (‘chupke ch’… ‘chupke chu’… ‘chupke chupk’…) rather than the reverse. Backspace is not pressed very often. So, instead of re-searching the whole list, I could just search the already-searched list in such cases. But right now, the search works fast enough, so I’ll leave it at that.

The next step is advanced filters. I’m working on that right now. Hopefully you’ll see in a while.

My earlier list of statistically improbable phrases in Calvin and Hobbes is technically just a list of “Statistically Improbable Words”. I re-did the same analysis using phrases. Here are the top 20 statistically improbable phrases (2 – 4 words only):

baby sitter chocolate frosted sugar bombs comic books doing homework fearless spaceman spiff() good night hamster huey ice cream miss wormwood new year peanut butter really think slimy girls spaceman spiff stuffed tiger stupendous man sugar bombs susie derkins watch tv water balloon

That is, these are the 2-4 word phrases whose frequency in Calvin and Hobbes is substantially (at least 5 times) higher than in the other books I have.

While doing this, the single biggest problem that stumped me was: what is a word?

• Is “it’s” one word or two words?
• Is “six-year-old” one word or three words?
• How do I distinguish between abbreviations (g.r.o.s.s.) and full-stops without a space ( … homework.what’s a …)?
• Does a comma always split words? (It doesn’t in numbers, like “3,500”)

The other problem is, phrases with more words are more improbable. Right now, if a phrase occurs 5 times more frequently in Calvin and Hobbes than my other books, I include it. But three-letter words rarely occur that often, and four-letter words even less so. Maybe I should have a lower cutoff for longer phrases.

Anyway, this analysis is a crude first approximation. Clearly Amazon’s gotten much further with their system.