匹配核心数据存储中的近似字符串

Question

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

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

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

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

我正在寻找一组大约十几场潜在比赛中的冠军，但我必须做很多这样的操作。 100% 准确率不是目标。

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

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

多谢。

Answer 1

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

    NSPredicate *predicate = [NSPredicate predicateWithFormat:@"(songTitle like[cd] %@)", yourSongSubstring];

The 'c' in [cd] is for case insensitivity.

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

    NSPredicate *predicate = [NSPredicate predicateWithFormat:@"(songTitle like[cd] %@) and (songTitle like[cd] %@)", songToken1, songToken2];

That syntax to combine predicates above may be off, going from memory.

Answer 2

我相信您想在这里使用的工具是 SearchKit。 我这么说就好像我刚刚让你的工作变得容易一样……我没有，但它应该拥有你在这里取得成功所需的工具。 LNC 仍在免费提供 SearchKit Podcast（非常好） 。

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

你问的问题是一个很好的问题，但肯定没有行业标准，因为任何能很好地解决这个问题的人（即每个主要搜索引擎）都会对其算法保密。 这是一个难题； 没有人愿意透露自己的答案。

Answer 3

考虑q-gram，它们是长度为 q 的子字符串 (Gravano 等人，2001）。

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

一般来说，q 应适应您的问题域（使用 q = 3, 4, 5... 进行实验）。