12

我目前正在编写的核心数据应用程序有一个小问题。我有两个不同的模型，上下文和永久存储。一个用于我的应用数据，另一个用于与我相关的网站。

大多数时候，我将我的应用程序中的一条记录与另一个来源的另一条记录完全匹配。然而，有时我不得不回退到模糊字符串匹配来链接两条记录。我正在尝试匹配歌曲标题。我的本地标题可能是（编造的）"The French Idealist is in your pensée"，而远程歌曲标题可能是"01 - 10 - French idealist in in you're pensee, The (dub remix, feat. DJ Objective-C)"

我搜索堆栈溢出、谷歌、可可文档，但在这些情况下我找不到任何关于如何进行模糊匹配的明确答案。我的字符串可以以任何开头，有一堆特殊字符，通常以随机或被忽略的字符结尾。

Regexp 不行，NSPredicates 也不行，Soundex 不能很好地处理外国名称，也许 Levenshtein 还不够（或者会吗？）。

我在一组大约十几个潜在的比赛中寻找一个标题，但我不得不做这个操作很多。100% 的准确率不是目标。

我正在考虑删除被忽略的单词，提取关键字（在本例中为“french, Idealist, pensée”），将它们连接起来，然后使用 Levenshtein 距离（歌曲标题中的单词应该按相同的顺序排列）。

在我的特殊情况下，它会起作用吗？关于这个问题的行业标准是什么（我不可能是世界上唯一一个想要匹配略有不同的歌曲名称的人）Core Data、Cocoa 或 Objective-C 可以帮助我吗？

非常感谢。

4

3 回答 3

3

您希望您的搜索对变音符号不敏感，以匹配 pensée 中的 'é' 和 pensee 中的 'e'。您可以通过在属性后添加 [d] 来获得此信息。像这样： 

    NSPredicate *predicate = [NSPredicate predicateWithFormat:@"(songTitle like[cd] %@)", yourSongSubstring];
[cd] 中的“c”用于不区分大小写。

由于您的字符串可以在您正在搜索的字符串中以任何顺序出现，您可以标记您的搜索字符串 ([... componentsByString:@" "]) 然后创建一个谓词，如

    NSPredicate *predicate = [NSPredicate predicateWithFormat:@"(songTitle like[cd] %@) and (songTitle like[cd] %@)", songToken1, songToken2];
上面组合谓词的语法可能是关闭的，来自内存。

于 2009-05-19T21:00:46.550 回答
2

我相信您要在这里使用的工具是SearchKit。我这么说好像我只是让你的工作变得轻松......我没有，但它应该有你在这里取得成功所需的工具。LNC 仍然免费提供他们的SearchKit 播客（非常好）。

在这种情况下，每个轨道都是一个文档，您需要想出一个好方法来使用可用于查找它们的标识符来索引它们。然后，您可以使用元数据加载它们并搜索它们。也许将标题“放入”文档中将有助于此处使用相似性搜索 ( kSKSearchOptionFindSimilar)。这可能会或可能不会很好地工作。

您提出的问题是一个很好的问题，但它肯定没有行业标准，因为任何能够很好地解决这个问题的人（即每个主要搜索引擎）都将他们的算法保密。这是一个难题；没有人准备好给出他们的答案。

于 2009-05-19T21:36:13.077 回答
1

考虑q-grams，它是长度为 q 的子串（Gravano et al., 2001）。

对于两个字符串 s1 和 s2，您可以为 s1 的每个 q-gram 确定具有最小编辑距离的 s2 的相应 q-gram。然后添加所有这些距离，最终得到一个对单词和额外字符的排列非常稳健的度量。

通常，q 应该适合您的问题域（实验 q = 3、4、5...）。

于 2012-04-05T11:43:41.477 回答