优化Salesforce中Levenshtein距离算法

Question

我有一个名为customer的自定义对象，其中包含Customer_Name、Address_Line_1、Post_Code等字段。

我想遍历所有记录并比较Customer_Name的相似度（基于模糊搜索或Levenshtein距离）。如果相似性高于或低于一定阈值，则会更新自定义字段(Possible_Duplicate_Customer_ID__c)以标识可能重复的记录。

我已经成功实现了这个功能，但我遇到了两个问题：

1). 超出了Salesforce管理限制（太多的脚本语句：200001），可能是由于Levenshtein距离算法所需的循环过程太繁琐。 2). 同样，我提交的列表(newList)中包含了重复的ID。

    private static List<Customer__c> newList = new List<Customer__c>();

webService static Integer findDupes() {

    Integer returnCount = 0;
    Double cost = 0;
    Integer COST_THRESHOLD = 5;

    Map<id,Customer__c> cMap = new Map<id,Customer__c>([
        select ID, Name, Customer_Name__c, Possible_Duplicate_Customer_ID__c 
        from Customer__c 
    ]);

    List<Customer__c> custList1 = cMap.values();        
    List<Customer__c> custList2 = custList1.clone();

    for (Customer__c cust1 :custList1) {
        for (Customer__c cust2 :custList2) {
            cost = LevenshteinDistance.computeLevenshteinDistance(
                    cust1.Customer_Name__c, cust2.Customer_Name__c);
                if(cost<COST_THRESHOLD && cost != 0) {
                    Customer__c c = new Customer__c(
                        id = cust2.Id, 
                        Possible_Duplicate_Customer_ID__c = cust1.Name
                    );
                    newList.add(c);
                }
                System.debug(cost+' edits to transform '
                        +cust1.Customer_Name__c+' to '+cust2.Customer_Name__c);
        }
    }

    returnCount = newList.size();

    update newList;        
    return returnCount;
}

- cyorkston

---

也许可以看一下Levenshtein距离的可能改进。 - A T

Answer 1

你尝试过新的getLevenshteinDistance方法吗？它与String相关。

请参见我在这里提出的问题/方法。 我通过坚持仅返回同一国家具有相同邮政编码或城市的匹配项来减少初始匹配数量。

- Marc

---

不，我还没有……但去年我正在进行的一个项目中它会非常有用！ - cyorkston

Answer 2

我建议在类内运行代码，该类使用可批处理接口，这更适合处理大量数据。由于您的 Web 服务不需要输入即可工作，因此您可以按计划每小时运行批处理程序，通过标记记录来标记重复项，然后在 Web 服务中提取它们。当然，如果您需要实时处理，您将需要优化此循环。

至于更新列表中的重复 ID，您对更新使用 `cust2.Id` 应该已经考虑到了这一点，但您似乎没有保护自己，防止客户记录与自身进行比较！这应该可以解决问题：

for (Customer__c cust1 :custList1) {
    for (Customer__c cust2 :custList2) {
        if (cust1.Id == cust2.Id) {
            continue;
        }

- Matt Lacey

---

你还没有准备好处理超过两个对象副本。在Possible_Duplicate_Customer_ID__c中，你应该存储联系人的连接ID或创建联系人和联系人之间的联接对象。 - Łukasz Skrodzki

Answer 3

Lev距离是模糊匹配的好工具，但由于脚本语句限制，在Apex中基本上不可用。使用我找到的版本（从旧版Apex Lang改编而来），将“0123456789”与“0246803579”进行比较需要700多个脚本语句。将“实际资源使用与执行代码行数基本上没有关联”与“是的，但是让‘一些’高级开发人员感到恼火将允许我们在州长限制实施期间省去麻烦。” 进行比较需要 60,000个脚本语句。除非您只进行少量的小比较，或者已经以某种方式重写了Lev以使其更适合脚本语句友好型，否则很难在该平台上证明其合理性。

我开始在Apex中使用更便宜的代理来进行Lev，例如对于名称或简短单词比较的Soundex，或者花哨的动态SOQL“LIKE”语句。如果您正在尝试的内容可以转化为集合操作，那么在Apex中使用这些操作会给您带来很好的性价比，因为.contains仅会花费一个脚本执行。

如果您真的需要进行大量的Lev操作，您可能必须使用API或重写代码以使其变得更加紧凑。根据您的用例，还可以将计算推入浏览器中。

- jkraybill

---

你好，感谢您的回复。使用Batch Apex，州长限制从200k增加到100万个脚本语句。基于小批量上进行的比较，该过程似乎有效。如果满足某些条件，例如城镇数据存在但不相等，则我已决定跳过昂贵的Lev检查。 - cyorkston