Performing Accurate String Comparisons In Python

I'm currently working on a website for a music company, which includes a full blown web application that will be accessible to members and assist in music distribution.

In order to make this happen, I have to be able to organize the tracks by genre. But keep in mind, this is a music company... they won't have anything but a huge library of music, so doing it manually is simply out of the question. Here's the other problem: Not all mp3s have ID3 tags (the tags that cause track details to appear on your player's display), and those that do may or may not fit in perfectly with your pre-defined items.

I wrote this in Python, so I wanted to share how I worked around this problem with calculating string similarity, rather than attempting to match strings or perform complex regular expressions to produce a possibly mediocre result.
I'll be honest: so far this method has worked on almost 100% of the songs we've seen within the company.

For calculating string similarity, the best solution I've found uses the Levenshtein distance (http://en.wikipedia.org/wiki/Levenshtein_distance) metric. This is available as a Python library at http://pypi.python.org/pypi/python-Levenshtein/0.10.2. Extract and install (python setup.py install). I'm also using the Mutagen library for processing mp3s and ID3 tags (http://code.google.com/p/mutagen/).

Ok, so let's say I have three genres that I want to use: Hip Hop, Dance, and Rock. These are the three genres offered, so we can expect that every track will closely fit one of these genres. If a track doesn't match nicely, we'll either chuck it off to a default genre (say, Hip Hop) or sent it to a Miscellaneous genre category. For this tutorial, we'll send them to Miscellanous.

Start by including the necessary libraries:

from mutagen.mp3 import EasyMP3
from Levenshtein import ratio
from glob import glob
import os

This will give you the EasyMP3 class, which really is easy to work with, and the ratio function from Levenshtein. The ratio function will return a number between 0 and 1 that represents the similarity between two strings. It's also very easy to work with. The glob function gives you the ability to list the contents of a directory using wildcards. The os library should already be quite familiar to Python users.

Now, I'm sure there are many approaches you can take here, but I'm going to show you what I decided to go with. It works, and it works quickly (which is important when you're talking about thousands and thousands of mp3s). Begin by building a comparison dictionary. This will contain each genre as a key, and an array of possible matches as a value (in all caps... I'll get to why later). Note that I'm shooting for readability here, not performance.

matchDict = {
    "Hip Hop" : [
        "HIP HOP",
        "RAP",
        "CHRISTIAN HIP HOP",
        "GOSPEL RAP",
        "GANGSTA RAP",
        "OLD SCHOOL RAP",
        "CRUNK"
    ],
    "Dance" : [
        "DANCE",
        "TRANCE",
        "HOUSE",
        "TECHNO",
        "ELECTRONIC",
        "TRIBAL",
        "PROGRESSIVE"
    ],
    "Rock": [
        "ROCK",
        "METAL",
        "ALTERNATIVE",
        "CLASSIC ROCK",
        "HEAVY",
        "CHRISTIAN ROCK",
        "GRUNGE"
    ]
}

I won't get into what should go where, or any philosophical debate on how hip hop isn't rap or whatever. We have three categories, and all songs for this exercise should fit into one of these. Now, let's grab all our mp3s:

baseDir = "/music/staging"

tracks = []

for (parent, child, files) in os.walk(baseDir):
    if child:
        for directory in child:
            [tracks.append(mp3file) for mp3file in glob("{0}/{1}/*.mp3".format(parent, directory))]

So what's this code doing? First, it's setting a base directory in baseDir. This should be the parent directory that contains all of the mp3 files you're looking to grab. Next, we're creating an empty array named tracks. This will hold all of the paths to the mp3 files within baseDir. Finally, the for loop uses os.walk() to step through each subdirectory in baseDir and perform an action. The function returns sets of tuples containing the parent directory as parent, any subdirectories as an array (_child_), and any files as an array (_files_).

If the child array contains any elements, we simply iterate through that array and process each subdirectory. In the last line, we are adding mp3file (an mp3 file) to the tracks array that we created earlier for each result returned from the glob() function (which basically returns an array of matching files within a directory).

Check the tracks variable: It should now be populated with all the mp3 files found within baseDir. If you want to check and make sure (and you're on Linux), run:

Command line:

find /music/staging -name '*.mp3' | wc -l

Python:

len(tracks)

Both commands should return the same number. Now, on to the string comparisons! Let's build a dictionary that will hold all of our organized files:

organizer = {
    "Hip Hop" : [],
    "Dance" : [],
    "Rock" : [],
    "Misc" : [],
    "Untagged" : []
}

As we iterate through each of our mp3 files in tracks, we'll want to organize them into this organizer dictionary, so that once we're done we can have a variable that has all of the mp3 files organized where we want them. Note that we also have an "untagged" key in here. This is where we'll put any mp3 files that don't have ID3 tags, or at least don't have the "genre" ID3 tag.

Let's now build the meat of the code:

for mp3 in tracks:
    tags = EasyMP3(mp3)
    bestMatch = ""
    maxRatio = 0
    try:
        gTag = str(tags['genre'])
    except KeyError:
        organizer['Untagged'].append(mp3)
        continue

    for genre in matchDict:
        ratios = [ratio(gTag.upper(), matchString) for matchString in matchDict[genre]]
        for r in ratios:
            if r > maxRatio:
                maxRatio = r
                bestMatch = genre

        if maxRatio > 0.4:
            organizer[bestMatch].append(mp3)
        else:
            organizer['Misc'].append(mp3)

Let's start from the top. We begin by iterating through the tracks variable (which we populated earlier). For each mp3 file, create an EasyMP3 object. This is okay, because even if the mp3 file doesn't have ID3 tags, EasyMP3 will still provide you with a blank dictionary that you can populate yourself. bestMatch will be used later to update the genre we think matches best. maxRatio will give us a running "best match" of our string comparisons. In the "try" block, we attempt to read the "genre" ID3 tag from the mp3 file, and convert it to a string (important, because the tags are always stored as a Unicode list, which will throw us off later). If the mp3 file doesn't have the "genre" ID3 tag, then we'll get a KeyErrorexception. We can catch that, toss the mp3 file into the "Untagged" array within our organizer variable, and move on to the next item in the for loop.

If the "genre" ID3 tag does exist, then we move on to the good stuff: string matching. We iterate through our matchDict dictionary (that was the one we populated with possible matches for each genre), and although we didn't call the keys() method for this dictionary, Python knows that this is what we want to do. Next, we use the ratio method of the Levenshtein module to compare gTag.upper() and matchString. Note that we called the upper() method on our genre tag, because the Levenshtein module treats string as case sensitive. Converting this tag to uppercase effectively eliminates this impediment and compares the tag more accurately to our already-uppercase strings in matchDict. See? I have a means to the madness.

Once we get a list of ratios to work with for the current genre in the loop, we then iterate through that array (I told you earlier I was shooting for readability, not performance). Since our initial value for maxRatio was 0, the first ratio we encounter will almost certainly be greater thanmaxRatio. If we encounter a ratio of 0.13, maxRatio will then be set to 0.13. At the same time, bestMatch will be set to the current genre in the loop, which at first may be 'Hip Hop'. As the loop continues through the other genres, we may run into a higher ratio again, which will setmaxRatio accordingly and also change bestMatch to a new genre. This is how we end up with our best match.

The last part of the code looks at whether maxRatio is set to at least 0.4. It's really up to you what number you'd consider, but through trial and error I've found this to be a good threshold. After all, people can write anything they want into an mp3 file's ID3 tags, so you really have to account for the possibilities. Remember that the "genre" ID3 tag can read something like "classic-hip-hop", if whoever set the tags just felt like it that day. So, if the maxRatio variable meets our minimum threshold of 0.4, we go ahead and add the mp3 file to our organizer variable, using thebestMatch variable as the key. Note that this only works because the keys in the matchDict dictionary are exactly the same as their counterparts in the organizer dictionary. Keep this in mind when coding your own applications.

And that's it! The organizer variable should have all of your tracks separated neatly by genre. If you don't care about mp3 files, then I hope I've at least shown you a good way to perform string matching against a known set of possibilities. Share this post with any Python fans you think might like it! I appreciate any feedback!

Tweet