让Levenstein的Distance算法符合我的需求

Question

我在Levenstein距离算法上遇到了一些麻烦.

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

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

然后我突然从我的一个供应商处获得了一个清单B,其中包含产品名称和每种产品的新价格.这可能每年发生一次以上,所以我想开发软件来手动完成工作.

问题是这个供应商不是很擅长一致性.所以他时不时地对名字做一些小改动,这意味着我不能做一个简单的字符串比较.

我已经实现了距离算法,但它并不真正符合我的需求. - 还是!

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

American Crew Anti Dandruff洗发露250毫升

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

美国船员抗头皮屑250毫升.

距离为10.

问题

我还遇到了一个名为的产品

美国船员3合1洗发水450毫升.

这是错误的匹配

American Crew Daily Shampoo 450 ml.

而不是我的

美国船员3合1 450毫升.

我明白为什么!但我不确定如何从这里改变算法.

有任何想法吗？

顺便说一句,我对算法并不是很好,但我相信某种称量可以帮助我在这里.

编辑:

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

Answer 1

一种方法是使用多种方法来搜索并对每种方法应用权重。我假设你有一些类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. American Crew 3 合 1 450 毫升
• American Crew 三合一洗发水 450 毫升
  1. American Crew 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()