0

Suppose I have 2 strings:

string1 = "home/lisa/Music/some_files/01.05 - Garden Ground.mp3"
string2 = "Music/Jim Smith/Unknown/(Deluxe Version/Garden Ground).mp3"
string4 = "Music/Jim Smith/Unknown/00 - Garden Ground.mp3"

Basically, I want to know if string 2 contains the same mp3 file as string 1. In the above example, you can see this is the case with Garden Ground.mp3. What's the best way to go about this? Should I try Levenshtein distance? I thought about doing a regular expression, but there's no guarantee string 2 will be formatted with parentheses in the exact same place every time. In fact, string 2 could look like string 4, for example.

|improve this question
  • 1
    First you probably want to tokenize this, e.g. string1 would become ['home', 'lisa', 'Music', 'some_files', '01.05', 'Garden Ground'] and then remove obviously irrelevant tokens that appear in the path such as "/home/XXX" and "Music/*". The tokens in the path components "Jim Smith/Unknown" might be related to the identity of the file. E.g. maybe someone put all of a certain artist or of an album in that folder. You could also weight some tokens as less important. e.g. "Unknown" is not as important as "Garden Ground". If you have a corpus you could weight the tokens automatically using tf-idf. – Brandin Mar 14 '15 at 9:06
  • How should a program compute something you cannot describe? Do you want to compare the basename? What is that slash in (Deluxe Version/Garden Ground).mp3? do you mean '\/` instead? – Aitch Mar 14 '15 at 10:50
  • @Aitch They're probably path delimiters. e.g. "Garden Ground).mp3" may be a file in a subdirectory which is called "(Deluxe Version". I think OP wants to know if the file "looks like it may be the same file based on what it is called and where it is stored in the filesystem" but you will need to define this concept precisely to get a solution. A more sensible approach would be to compare the CONTENTS of the files. If they are 1:1 you know they match. If their lengths are very different, you know they do not. Otherwise, you could use audio comparison techniques to see how similar they are. – Brandin Mar 14 '15 at 11:34
  • I don't know if the soundex phonetic algorithm is maybe what you are looking for? it's quite easy and you can compare if two strings are phonetical similar. Of course again applied to the basename. – Aitch Mar 14 '15 at 13:56
  • 1
    I'd ignore the filenames & try to see if I could find a way to directly compare the mp3 files themselves, if possible. You'd catch typos and renames that way. Getting a "fuzzy match" might be harder. – Dan Pichelman Mar 14 '15 at 16:13
1

I don't really think any existing algorithm is going to work in your case. In your case, you are not looking for similarity between strings, but if strings contain similar values. Levenstein distance is about similarity of strings, not if strings contain similar values.

In your case, the simplest algorithm would be (pseudocode).

  1. Get name of each file without directory (I'm assuming directory doesn't matter)
  2. Split each name into words based on predefined separators (' ', '-', ';', '.', etc.. you have to do some trial-and-error here to find the right separators)
  3. Compare how many words are same between two names (eg, in your case there are 2 same words between each of the files)
  4. If the count of same words exceeds some threshold, consider them same

The last step is obviously the hardest one. Figuring the threshold to minimize false positives and negatives is quite a challenge. The simplest is absolute threshold (eg. count >= 2 would match your case), but it might not be enough. Relative threshold (eg. count / totalWordsCount > 50%) might work, but it is harder to test and highly depends on what separators you pick.

|improve this answer

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.