0
$\begingroup$

I have 10 millions of filenames and I need to determine whether filename corresponds to some movie or video game. For this I initially thought to compare filenames using Levenshtein distance with imdb list ftp://ftp.funet.fi/pub/mirrors/ftp.imdb.com/pub/ but it turns out that direct compassion requires $O(nm)$ where n is number of filenames and m is number of items in imdb database, both of which in millions range. I think there should be a way to organize imdb list in some tree like suffix structure to speed up comparisons to something like $O(n \log m)$. Any other advices and ideas are very much appreciated, too.

$\endgroup$
1
$\begingroup$

This blog post discusses and contains code for the use of tries (prefix trees) for fast Levenshtein distance computations.: http://stevehanov.ca/blog/index.php?id=114

If reducing space complexity is also a concern, read the follow-up post too: http://stevehanov.ca/blog/index.php?id=115

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

Examples of the filenames would be helpful to answer the question. If the filenames are such that you can know how many words are in the name, then you can only search for the movie names with the same number of word.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ The filenames like the regular ones you can see of bittorent sites and such (Minecraft 1.7.2 Cracked,Homefront (2013) DVDRip XviD-MAX, and so on ). I guess piracy is main source of files for my users. $\endgroup$ – Moonwalker Feb 4 '14 at 15:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.