实际示例：在数据匹配时遇到的一些典型挑战
实体解析是确定数据集中的两个或多个记录是否指向同一个现实世界实体（通常是人或公司）的过程。乍一看，实体解析可能看起来是一个相对简单的任务：例如，给定一个人的两张照片，即使是一个小孩子也可以以相当高的准确度确定它们是否显示同一个人。计算机也是如此：可以轻松比较包含姓名、地址、电子邮件等属性的两个记录。然而，对这个主题的深入挖掘会变得越来越具有挑战性：需要评估各种匹配算法，处理数百万或数十亿条记录会导致二次复杂性，更不用说实时和数据删除的用例了。
模糊文本匹配
让我们首先来看看比较两个著名艺术家文森特·梵·高的记录 – 或者是梵·高吗？
第二个记录中有一些错误（除了出生在一个世纪后和电子邮件地址外）：名字拼写错误，出生日期混淆，邮政编码丢失，电子邮件地址略有不同。
那么我们该如何比较这些值呢？如果，假设这些名字是相同的，那么对这些值进行简单的字符串比较就足够了。由于情况并非如此，我们需要一些更高级的模糊匹配。有许多不同的用于基于文本的模糊匹配的算法，它们可以大致分为三组。语音算法专注于文本的发音相似程度。最著名的算法是Soundex和Metaphone，它们主要用于英语文本，但其他语言也存在类似的变体，如德语的科隆语音算法（Cologne Phonetic）。文本距离算法通常定义了一个文本需要改变多少字符才能达到另一个文本的目标。Levenshtein距离和汉明距离是该组中两个着名的算法。相似度算法，如余弦相似度或Jaccard系数，计算文本的结构相似度，并经常将相似度表示为百分比。
在本文中，我们将使用一种非常简单的方法，仅使用名称上的Levenshtein距离和城市的相等性。这个例子和所有后续的例子都将使用Go语言作为编程语言，并尽可能使用现有的库。将其转换为Python、Java或任何其他语言应该很简单。此外，它只会对名称属性进行匹配。添加更多属性甚至使其可配置不是本文的目的。
package mainimport ( "fmt" "github.com/hbollon/go-edlib")type Record struct { ID int Name string City string}func matches(a, b Record) bool { distance := edlib.LevenshteinDistance(a.Name, b.Name) return distance <= 3 && a.City == b.City}func main() { a := Record{ Name: "Vincent Van Gogh", City: "Paris", } b := Record{ Name: "Vince Van Gough", City: "Paris", } if matches(a, b) { fmt.Printf("%s和%s可能是同一个人\n", a.Name, b.Name) } else { fmt.Printf("%s和%s可能不是同一个人\n", a.Name, b.Name) }}在Go Playground中尝试：https://go.dev/play/p/IJtanpXEdyu
两个名字之间的Levensthein距离正好是3。这是因为第一个名字多了三个字符（第一个名字中的“en”和姓氏中的“u”）。请注意，这仅适用于特定的输入。然而，它远非完美。例如，“Joe Smith”和“Amy Smith”的Levenshtein距离也为3，但显然不是同一个人。将距离算法与语音算法结合起来可能会解决这个问题，但这超出了本文的范围。
当使用基于规则的方法而不是基于机器学习的方法时，选择适合您用例的能够产生最佳结果的算法是您业务成功的最关键因素。这是您应该花费大部分时间的地方。不幸的是，正如我们现在将要发现的那样，如果您决定自己开发实体解析引擎，将有大量其他事情会分散您的注意力，妨碍您优化这些规则。
天真的实体解析
现在我们知道了如何比较两条记录，我们需要找出所有彼此匹配的记录。最简单的方法是将每条记录与所有其他记录进行比较。为了说明这个例子，我们使用随机选择的姓名和城市。对于姓名，我们会强制产生最多三个错误（用x替换任意字符）。
var firstNames = [...]string{"Wade", "Dave", "Seth", "Ivan", "Riley", "Gilbert", "Jorge", "Dan", "Brian", "Roberto", "Daisy", "Deborah", "Isabel", "Stella", "Debra", "Berverly", "Vera", "Angela", "Lucy", "Lauren"}var lastNames = [...]string{"Smith", "Jones", "Williams", "Brown", "Taylor"}func randomName() string { fn := firstNames[rand.Intn(len(firstNames))] ln := lastNames[rand.Intn(len(lastNames))] name := []byte(fmt.Sprintf("%s %s", fn, ln)) errors := rand.Intn(4) for i := 0; i < errors; i++ { name[rand.Intn(len(name))] = 'x' } return string(name)}var cities = [...]string{"Paris", "Berlin", "New York", "Amsterdam", "Shanghai", "San Francisco", "Sydney", "Cape Town", "Brasilia", "Cairo"}func randomCity() string { return cities[rand.Intn(len(cities))]}func loadRecords(n int) []Record { records := make([]Record, n) for i := 0; i < n; i++ { records[i] = Record{ ID: i, Name: randomName(), City: randomCity(), } } return records}func compare(records []Record) (comparisons, matchCount int) { for _, a := range records { for _, b := range records { if a == b { continue // 不要与自己进行比较 } comparisons++ if matches(a, b) { fmt.Printf("%s 和 %s 可能是同一个人\n", a.Name, b.Name) matchCount++ } } } return comparisons, matchCount}func main() { records := loadRecords(100) comparisons, matchCount := compare(records) fmt.Printf("进行了 %d 次比较，找到了 %d 对匹配项\n", comparisons, matchCount)}在 Go Playground 中尝试：https://go.dev/play/p/ky80W_hk4S3
您应该会看到类似于以下的输出（如果对于随机生成的数据没有找到任何匹配项，则可能需要多次运行）：
Daisy Williams 和 Dave Williams 可能是同一个人Deborax Browx 和 Debra Brown 可能是同一个人Riley Brown 和 RxxeyxBrown 可能是同一个人Dan Willxams 和 Dave Williams 可能是同一个人进行了 9900 次比较，找到了 16 对匹配项如果您幸运的话，您还会得到类似于“Daisy”和“Dave”的不匹配项。这是因为我们使用了三个编辑距离，对于短姓名来说，这个编辑距离太高了。请随意改进此编辑距离。
从性能上来看，真正引起问题的是需要进行 9,900 次比较才能得到结果，因为将输入量翻倍将大致使所需比较次数增加四倍。对于 200 条记录，需要进行 39,800 次比较。对于仅有 100,000 条记录的小量数据，这意味着需要进行近 1000 亿次比较。无论您的系统有多大，随着数据量的增长，总会有一个点，系统将无法在可接受的时间内完成这个任务。
一个快速但几乎无用的优化方法是不需要对每个组合都进行两次比较。比较 A 和 B 或比较 B 和 A 不应该有什么区别。然而，这只会将所需的比较次数减少一半，由于二次增长，这是可以忽略的。
通过阻塞减少复杂性
如果我们看一下我们创建的规则，我们很容易注意到，如果城市不同，我们将永远无法找到匹配项。所有这些比较都是完全浪费的，应该予以防止。将您认为相似的记录放入一个共同的桶中，而将其他不相似的记录放入另一个桶中，在实体解析中被称为阻塞。由于我们想要使用城市作为我们的阻塞键，因此实现起来非常简单。
func block(records []Record) map[string][]Record { blocks := map[string][]Record{} for _, record := range records { blocks[record.City] = append(blocks[record.City], record) } return blocks}func main() { records := loadRecords(100) blocks := block(records) comparisons := 0 matchCount := 0 for _, blockRecords := range blocks { c, m := compare(blockRecords) comparisons += c matchCount += m } fmt.Printf("进行了%d次比较，找到了%d个匹配项\n", comparisons, matchCount)}在 Go Playground 中尝试: https://go.dev/play/p/1z_j0nhX-tU
结果现在是相同的，但是我们仅仅进行了大约十分之一的比较，因为我们有十个不同的城市。在真实的应用程序中，由于城市的差异性更大，这种效果将会更加显著。此外，每个块可以独立于其他块进行处理，例如在同一台或不同的服务器上并行处理。
找到合适的阻塞键本身可能是一个挑战。使用类似城市这样的属性可能导致分布不均匀，并且可能导致一个巨大的块（例如一个大城市）比其他所有块花费更长时间。或者城市包含了一个微小的拼写错误，不再被视为有效匹配。使用多个属性和/或使用音素键或 q-gram 作为阻塞键可以解决这些问题，但会增加软件的复杂性。
从匹配到实体
到目前为止，我们只能知道我们的记录是否匹配。对于非常基本的用例，这可能已经足够了。然而，在大多数情况下，您希望知道属于同一个实体的所有匹配项。这可以从简单的星状模式（A与B、C和D匹配）到链状模式（A与B匹配，B与C匹配，C与D匹配），再到非常复杂的图状模式。只要所有数据都适合单个服务器的内存中，这种称为传递性记录链接的操作就可以轻松实现。然而，在真实的应用程序中，这更具挑战性。
func compare(records []Record) (comparisons int, edges [][2]int) { for _, a := range records { for _, b := range records { if a == b { continue // 不要与自己进行比较 } comparisons++ if matches(a, b) { edges = append(edges, [2]int{a.ID, b.ID}) } } } return comparisons, edges}func connectedComponents(edges [][2]int) [][]int { components := map[int][]int{} nextIdx := 0 idx := map[int]int{} for _, edge := range edges { a := edge[0] b := edge[1] aIdx, aOk := idx[a] bIdx, bOk := idx[b] switch { case aOk && bOk && aIdx == bIdx: // 在同一个组件中 continue case aOk && bOk && aIdx != bIdx: // 合并两个组件 components[nextIdx] = append(components[aIdx], components[bIdx]...) delete(components, aIdx) delete(components, bIdx) for _, x := range components[nextIdx] { idx[x] = nextIdx } nextIdx++ case aOk && !bOk: // 将 b 添加到 a 的组件中 idx[b] = aIdx components[aIdx] = append(components[aIdx], b) case bOk && !aOk: // 将 a 添加到 b 的组件中 idx[a] = bIdx components[bIdx] = append(components[bIdx], a) default: // 创建包含 a 和 b 的新组件 idx[a] = nextIdx idx[b] = nextIdx components[nextIdx] = []int{a, b} nextIdx++ } } cc := make([][]int, len(components)) i := 0 for k := range components { cc[i] = components[k] i++ } return cc}func main() { records := loadRecords(100) blocks := block(records) comparisons := 0 edges := [][2]int{} for _, blockRecords := range blocks { c, e := compare(blockRecords) comparisons += c edges = append(edges, e...) } cc := connectedComponents(edges) fmt.Printf("进行了%d次比较，找到了%d个匹配项和%d个实体\n", comparisons, len(edges), len(cc)) for _, component := range cc { names := make([]string, len(component)) for i, id := range component { names[i] = records[id].Name } fmt.Printf("找到以下实体：%s 来自 %s\n", strings.Join(names, ", "), records[component[0]].City) }}在Go Playground中尝试：https://go.dev/play/p/vP3tzlzJ2LN
连接组件函数遍历所有边，要么创建新组件，将新ID添加到现有组件中，要么将两个组件合并为一个。结果看起来大致如下：
进行了1052次比较，找到了6个匹配项和2个实体从开罗找到了以下实体：伊凡·斯密斯、伊克森·史密斯、伊瓦克斯·斯密特从开普敦找到了以下实体：布莱恩·威廉姆斯、布莱恩·威廉姆斯保留这些边缘会给我们带来一些优势。我们可以使用它们来使生成的实体可理解和可解释，最好还能有一个漂亮的用户界面，显示实体记录之间的连接关系。或者在使用实时实体解析系统时，我们可以使用这些边缘来拆分实体，因为数据被移除了。或者在构建图神经网络（GNN）时使用它们，这样可以获得比仅仅使用记录更好的机器学习结果。
从边缘中可能出现的一个问题是存在大量非常相似的记录。例如，如果A与B匹配，B与C匹配，那么根据使用的规则，C也可能与A匹配。如果D、E、F等也与现有记录匹配，那么我们又回到了二次增长的问题，很快会导致边缘数量过多而无法处理。
还记得我们是如何构建阻塞桶的吗？惊喜！对于非常相似的数据，所有数据最终都会进入几个巨大的桶中，计算性能再次急剧下降——即使您按照之前的建议从多个属性创建桶。
这种非相同重复记录的典型示例是某人经常在同一家商店订购，但使用的是访客身份（抱歉，没有漂亮的客户ID）。这个人可能几乎总是使用相同的送货地址，并且大多能够正确输入自己的名字。因此，应以特殊方式处理这些记录，以确保系统性能稳定，但这是一个单独的话题。
在您对所获得的知识感到非常舒适并想要开始实施自己的解决方案之前，让我迅速粉碎您的梦想。我们还没有讨论如何在实时环境中执行任何操作的挑战。即使您认为自己不需要始终最新的实体（显而易见的好处），实时方法仍然具有进一步的价值：您不需要一遍又一遍地执行相同的计算，只需针对新数据执行即可。另一方面，实施起来则更加复杂。想要进行阻塞吗？将新记录与其所属的一个或多个桶的所有记录进行比较，但这可能需要一段时间，可能更适合被视为增量批处理。还有，直到最终完成之前，已经有大量新记录等待处理。想要使用连接组件计算实体吗？当然，将整个图形保留在内存中，只需添加新边缘即可。但不要忘记跟踪由于新记录而刚刚合并在一起的两个实体。
所以，您仍然愿意自己实现这个功能。而且您做出了（在这种情况下）明智的决定，不存储边缘，也不支持实时。所以您成功地运行了第一个实体解析批处理作业，并使用了所有的数据。这需要一些时间，但您每个月只需要执行一次，所以没问题。可能就在这时，您看到您的数据保护官员跑过来告诉您，由于一项GDPR投诉，您需要从数据集中删除一个人。所以您再次为一个被删除的实体运行整个批处理作业——耶。
结论
进行实体解析可能乍看起来相当简单，但它包含许多重要的技术挑战。其中一些可以简化和/或忽略，但其他挑战需要解决以获得良好的性能。
原文发表于https://tilores.io。