2

好的，我看过很多关于模糊字符串匹配、Levenstein 距离、最长公共子字符串等的帖子。它们似乎都不完全适合我想做的事情。我正在从各种 Web 服务中提取产品结果，并且我可以从这些服务中构建产品名称的大列表。这些名称可能包括一堆变量垃圾。以下是来自 SearchUPC 的一些示例：

Apple 60W magsafe adapter L-shape with extension cord
Original Apple 60W Power Adapter (L-shaped Connector) for MacBook MC461LL/A with AC Extension Wall Cord (Bulk Packaging)
Current Apple MagSafe 60W Power Adapter for MacBook MC461LL/A with AC Extension Wall Cord (Bulk Packaging)
Apple 60W MagSafe Power Adapter - Apple Mac Accessories
Apple - MagSafe 60W Power Adapter for MacBook and 13\" MacBook Pro
MagSafe - power adapter - 60 Watt

等等我想做的是提取通用产品名称（在我的启发式人眼看来，这显然是Apple 60W MagSafe Power Adapter），但上述方法似乎都不太可能奏效。我的主要问题是我不知道要在字符串列表中搜索什么......起初，我想尝试最长的公共子字符串，但似乎这会失败，因为一堆字符串有一些东西订单，这可能会产生电源适配器的产品名称，这对用户来说并不是非常有用。

注意：从 SearchUPC API 返回的绝大多数Apply 60W MagSafe Power Adapter记录（这里大部分省略）确实包含文字字符串“ ”。

我在 Objective-C 中为 iOS 实现了这个，但我对算法的兴趣比实现更重要，所以任何语言都是可以接受的。

4

2 回答 2

1

如果您想比较字符串，但在更改子字符串的顺序方面需要比最长公共子字符串更健壮的东西，您可以研究一种称为字符串平铺的技术。简化，原理如下：

  1. 在两个字符串中找到最大的公共子字符串（大于最小长度）
  2. 从两个字符串中删除该子字符串
  3. 重复直到没有比你的最小长度更大的子字符串

在实践中，剩余（不匹配的）字符串部分与初始长度之间的比率是字符串匹配程度的一个很好的指标。并且该技术对子字符串的重新排序非常强大。您可以在此处找到 M. Wise 描述此技术的科学论文。我过去自己实现了该算法（这并不难），但显然免费的实现很容易获得（例如这里）。虽然我在各种模糊匹配场景中使用过该算法，但我不能保证我自己从未使用过的实现。

字符串平铺本身并不能解决寻找最大常见产品名称的问题，但在我看来，通过稍微修改算法，您可以做到这一点。您可能对计算匹配百分比的兴趣不如对保留相似部分的兴趣？

正如之前的海报所说，这种模糊匹配几乎总是需要某种手动验证，因为误报和漏报都是不可避免的。

于 2013-05-18T23:37:03.923 回答
0

听起来你的方法需要有两个方面。一个应该是相互匹配的记录。另一部分是从那些匹配的记录中提取“规范名称”。在您的情况下，它是一种产品，但概念相同。我不确定您将如何将匹配记录组与标准化产品名称相关联，但我建议您尝试从记录中提取重要信息并尝试将其与 Internet 上的某些资源进行匹配。例如，对于您的示例，也许您将您的数据与苹果产品列表进行比较。或者你可以尝试让一个机器人抓取谷歌并拉出最高结果来尝试和关联。归根结底，归根结底，如果您的文本真的很脏，则需要进行一些人工干预。我的意思是你可以为匹配设置一个阈值，不匹配，并需要审查。祝你好运。

于 2013-05-02T15:47:10.347 回答