7

我在使用 Levenstein 距离算法时遇到了一些问题。

我正在使用 Levensteins 距离算法将产品名称与产品名称列表进行比较，以找到最接近的匹配项。但是，我需要稍微调整一下。我正在使用来自dotnetperls.com的示例。

假设我有一个来自我自己的数据库的 2000 个产品名称的列表 A。我自己销售所有这些产品。

然后突然间，我从我的一个供应商那里得到了一份清单 B，上面有产品名称和每种产品的新价格。这可能每年发生不止一次，所以我想开发软件来手动完成这项工作。

问题是这家供应商不太擅长一致性。所以他时不时地对名称进行一些小改动，这意味着我无法进行简单的字符串比较。

我已经实现了距离算法，但它并不真正适合我的需求。- 然而！

在浏览我的供应商列表时，我遇到了一个名为

American Crew 去屑洗发水 250 毫升

该产品与我自己的产品成功匹配，称为

美国船员去头屑 250 毫升。

距离为 10。

问题

我还遇到了一个产品，叫做

American Crew 三合一洗发水 450 毫升。

哪个被错误地匹配

American Crew 每日洗发水 450 毫升。

而不是我的

American Crew 3 in 1 450 毫升。

我明白为什么！但我不确定我应该如何从这里更改算法。

有任何想法吗？

顺便说一句，我不太擅长算法，但我相信某种称重会对我有所帮助。

编辑：

计算时间并不是一个真正的问题。即使需要十个小时才能完成，它仍然比手动完成要好得多：P

4

4 回答 4

3

一种方法是使用多种方法来搜索并对它们中的每一个应用权重。我假设你有一些Item至少有一个字符串Name属性的类：

double levWeight = 1.0;   // adjust these weights as you see fit
double matchWeight = 1.0;

// add whatever to here you'd like
var splitOn = new[] { ' ', '!', '"', '#', '$', '%', '&', '\'', '(', ')', '-' };
Func<string, string[]> split = 
    s => s.Split(splitOn, StringSplitOptions.RemoveEmptyEntries);

var matches =
    from xx in mine
    let xp = split(xx.Name)
    select new {
        Item = xx,
        Matches =
           (from yy in theirs
            let yp = split(yy.Name)

            /* found how many name components match */
            let mm = xp.Intersect(yp, StringComparer.OrdinalIgnoreCase).Count()

            /* find the Levenshtein distance of the two names */
            let ld = LevDist(xx, yy)

            /* weight our two criteria */
            let ww = (matchWeight * mm) + (levWeight / ld)

            /* should match on at least ONE name component */
            where mm > 0
            orderby ww descending
            select yy)
    };

当针对您拥有的数据语料库运行时，我会收到以下输出：

  • American Crew 去屑洗发水 250 毫升
    1. American Crew 去屑 250 毫升
    2. American Crew 每日洗发水 450 毫升
    3. 美国船员 3 合 1 450 毫升
  • American Crew 三合一洗发水 450 ml
    1. 美国船员 3 合 1 450 毫升
    2. American Crew 每日洗发水 450 毫升
    3. American Crew 去屑 250 毫升

如果您有更多标准，您只需将它们添加到查询中（与其他let子句内联）并对其结果应用一些权重。

其他可能的应用是“以相同顺序命名组件”：

let or = xp.Zip(yp, (a,b) => String.Compare(a, b, true))
           .TakeWhile(c => c == 0)
           .Count()
于 2012-11-01T14:59:40.397 回答
1

您可以将 Levensthein 与不带 -、空格、点的第二遍以及计算精确相似词的第三遍以及基于产品名称中第一个不同单词的第四遍结合起来吗？

也许你可以看看神经网络？创建培训数据库需要很长时间，但它也可能是一个答案（或答案的一部分）。

于 2012-11-01T14:11:03.080 回答
1

您需要插入一些关于数据的外部知识。例如，在您展示的案例中，“洗发水”一词并没有提供有关产品的信息（即，它没有添加关于两种产品是否相似的有用信息）。如果您从数据中删除了“洗发水”一词，则该方法会起作用。

因此，您可以做的一件事是通过计算搜索非常频繁（出现在许多单词中）的单词，然后从您的数据中删除，因为它们可能对您的问题没有信息。然后运行算法。

第二个小调整是使用您对字符“-”的了解。这个字符可以被认为类似于空格字符' '。因此，在运行您的算法之前，将任何 '-' 替换为 ' '。

通过这种方式，您不必更改算法，但仍然可以使用您对问题的了解（我知道您希望避免更改算法）。

最后，您可能需要考虑更剧烈的变化，例如不使用 Levenstein 距离或比较整个单词。您不显示您的数据集，但如果差异在少量字符（例如错字）中，您当前使用的形式中的 Levenstein 距离将是最好的。

于 2012-11-01T15:10:22.637 回答
0

该算法不会给你一个匹配，而是一个距离。因此，在您的问题场景中，您应该比较从两个不同句子中获得的距离，最低距离更好，但仍然没有确定的匹配。我想最好的解决方案是根据算法向用户展示您认为会匹配的不同产品名称。然后用户可以做出最终选择。但是，如果您不介意偶尔出现不匹配，那么您就走上了正确的道路。只需为您仍然认为匹配的距离选择一个数字，但这会给您带来很多误报。

于 2012-11-01T14:19:29.407 回答