2

我有一个从 iTunes API 上传的歌曲列表。其中一些是重复的，但不是完美的重复。例如，有人可能会说“All 4 u”与“All for you”，或者“Some song”与“some song feat. some other artist”

我希望能够识别重复项。计算所有对的 Levenshtein 距离的最佳方法是什么？这似乎太过分了。

我正在使用 Cocoa Touch 框架进行 iOS 编程，所以如果有人知道任何有帮助的库的话。

4

1 回答 1

3

为什么您认为计算 Levenshtein 距离过大？如果您坐下来用铅笔和纸列出清单，您会使用什么算法？

也就是说，Levenshtein 可能是必要的，但还不够。我将从规范化字符串开始。在某些情况下，字符串可能会以多种方式规范化，您需要同时执行这两种方式。规范化看起来像：

  • 转换为小写
  • 去掉任何前导数字，后跟标点符号（“1.”、“1 -”等）
  • 在“壮举”之后试探性地剥离任何东西。或“与”
    • 这是一个关于你的问题集的特殊知识的例子。你将不得不使用很多这样的特殊知识。
    • “暂时”意味着您可能应该保留字符串的剥离和非剥离版本
    • 请记住，包括“壮举”在内的东西。可能是混音，所以你必须小心假设重复。这当然适用于几乎所有的重复数据删除尝试。经常有多个版本。
  • 试扩展常用缩写（u=>you、4=>for、2=>two、w/=>with等）
  • 试探性地去掉括号中的任何内容
  • 去掉英文冠词（a, an, the）。甚至可能在第一次通过时去掉所有非常短的单词（3 个或更少的字符）。

做好这件事很复杂，需要大量的试验和错误。我过去做过很多联系人重复数据删除，还有一条建议：开始保守。很容易意外地重复重复数据太多。构建一个您手动删除重复数据的大列表，并在每次算法更改后进行测试、测试、测试。确保您的 UI 可以向用户呈现您不确定的任何内容，因为会有很多很多您无法确定的记录。（即使您手动操作也是如此。查看大量人工输入的标题并告诉我哪些是 100% 重复的，而无需听曲目。计算机在这方面不会比您做得更好.)

我不知道有任何公开可用的图书馆。很多人已经多次解决了这个问题（搜索“重复数据删除歌曲标题”或类似的东西）。但它通常是商业软件。

对此还有一条建议，因为这是一个巨大的 O(n^2) 或更糟的问题。寻找入桶机会。如果您可以先匹配艺术家，然后是专辑，然后是曲目，那么您可以在更短的时间内分而治之。

于 2013-03-04T17:18:53.720 回答