Fuzzy Lookups

[BBands]

I have some CDs and have been archiving them on a PC. I wrote a Python
script that spans the archive and returns a list of its contents:
[[genre, artist, album, song]...]. I wanted to add a search function to
locate all the versions of a particular song. This is harder than you
might think. For example the Cajun "national anthem" is Jolie Blond,
but it can be spelled several different ways jolie, joli, blon, blond,
etc... In addition the various online services that provide song info
are riddled with typos, so an ordinary string match just doesn't get
you there. What is needed is a fuzzy string match and it turns out that
there is a very good one, the Levenshtein distance, which is the number
of inserts, deletions and substitutions needed to morph one string into
another. In my application I match the desired song title against all
song titles in my list and return the ones with the lowest Levenshtein
distances. This is remarkably, one might even say stunningly,
effective, easily finding all the version of Jolie Blon in the list.

I am using the following snippet (found on the web, proper attribution
unsure), which calculates the Levenshtein distance.

def distance(a,b):
c = {}
n = len(a); m = len(b)

for i in range(0,n+1):
c[i,0] = i
for j in range(0,m+1):
c[0,j] = j

for i in range(1,n+1):
for j in range(1,m+1):
x = c[i-1,j]+1
y = c[i,j-1]+1
if a[i-1] == b[j-1]:
z = c[i-1,j-1]
else:
z = c[i-1,j-1]+1
c[i,j] = min(x,y,z)
return c[n,m]

As mentioned above this works quite well and I am happy with it, but I
wonder if there is a more Pythonic way of doing this type of lookup?

jab

[name]

Gregory Piñero ha scritto:
:

If anyone would be kind enough to improve it I'd love to have these
features but I'm swamped this week!

- MD5 checking for find exact matches regardless of name
- Put each set of duplicates in its own subfolder.

Done? http://pyfdupes.sourceforge.net/

Bye,
luca

[name]

Gregory Piñero ha scritto:
:

If anyone would be kind enough to improve it I'd love to have these
features but I'm swamped this week!

- MD5 checking for find exact matches regardless of name
- Put each set of duplicates in its own subfolder.

Done? http://pyfdupes.sourceforge.net/

Bye,
luca

[Gregory Piñero]

Wow, that looks excellent. I'll definately try it out. I'm assuming
this is an existing project, e.g. you didn't write it after reading
this thread?

-Greg
On 2/9/06, name <na**@example.c om> wrote:

Gregory Piñero ha scritto:
:

If anyone would be kind enough to improve it I'd love to have these
features but I'm swamped this week!

- MD5 checking for find exact matches regardless of name
- Put each set of duplicates in its own subfolder.

Done? http://pyfdupes.sourceforge.net/

Bye,
luca

--
Gregory Piñero
Chief Innovation Officer
Blended Technologies
(www.blendedtechnologies.com)

[name]

Gregory Piñero ha scritto:

Wow, that looks excellent. I'll definately try it out. I'm assuming
this is an existing project, e.g. you didn't write it after reading
this thread?

Yes it is an existing projects of course ;)
Right now I've no time to improve it.
I hope that later this summer I will find
the time to make file management much easier on the
gui side and to split all the different algorithm in
external plugins so anyone can add it's own and compare
with the other already there. The main goal of my project
was primarly the interest for the "similarity search".

bye,
luca

[name]

Gregory Piñero ha scritto:

Wow, that looks excellent. I'll definately try it out. I'm assuming
this is an existing project, e.g. you didn't write it after reading
this thread?

Yes it is an existing projects of course ;)
Right now I've no time to improve it.
I hope that later this summer I will find
the time to make file management much easier on the
gui side and to split all the different algorithm in
external plugins so anyone can add it's own and compare
with the other already there. The main goal of my project
was primarly the interest for the "similarity search".

bye,
luca