相关联

一个用于处理混乱数据的巧妙暴力关联器

版权所有 2019-2023 Larry Hastings

概述

相关联 是一个数据分析库。它旨在在两个表示相同信息但格式不同的数据集之间找到匹配项。它的目标是告诉您“第一个数据集中的值 A 与第二个数据集中的值 B 是匹配的”。

要使用 相关联，您需要输入两个包含（不透明）值及其关联元数据信息的数据集。 相关联 使用元数据在两个数据集之间找到匹配项，使用独特的评分启发式方法对这些匹配项进行排序，并返回这些匹配项。

快速入门

此代码

    import correlate

    c = correlate.Correlator()
    a, b = c.datasets

    greg, carol, tony, steve = "greg carol tony steve".split()
    Greg, Carol, Tony, Steve = "Greg Carol Tony Steve".split()

    a.set("this", greg)
    a.set("is", greg)
    a.set("Greg", greg, weight=5)
    a.set_keys("Carol over here".split(), carol)
    a.set_keys("My name is Tony".split(), tony)
    a.set_keys("Hi I'm Steve".split(), steve, weight=2)

    b.set_keys("gosh my name is Greg".split(), Greg)
    b.set_keys("Carol is my name".split() , Carol)
    b.set_keys("Pretty sure I'm still Tony".split(), Tony)
    b.set_keys("I'm Steve".split(), Steve)

    result = c.correlate()
    for match in result.matches:
        print(f"{match.score:1.3f} {match.value_a:>5} -> {match.value_b}")

产生此输出

5.750  greg -> Greg
3.800 steve -> Steve
1.286 carol -> Carol
1.222  tony -> Tony

真实示例

我喜欢的一个播客。我使用RSS源以1990年代的方式下载MP3文件。但RSS源中的元数据是垃圾——节目标题不一致，节目编号几乎全部缺失。

这个播客在其网站上还有一个节目列表。这些数据 非常好，包括干净的节目编号。并且很容易抓取。但仍然不完美。两个节目列表并不完全相同，即使两个列表中都有的节目有时也会重新排序。

显然，我想从RSS源中获取MP3文件，并将其与从网站抓取的干净元数据匹配起来。这让我得到了两者之最佳。

但是这个特定播客的集数超过七百集！手动匹配这些集数将会是一项巨大的工作。我们每周都会有一集新的播客。有时他们还会添加回旧的播客，或者更新旧播客的元数据——这些改变会打乱任何手动构建的排序。我将来可能还想听这个网站上的不止一个播客！所以我真的不想手动做所有这些。

幸运的是，在对两个数据集应用了一点点智能之后，关联做得非常完美。

为什么关联工作得如此之好

关联的灵感来源于这样一个洞察：两个数据集中唯一的键可能是非常好的匹配。比如说，键"egyptian"在一个数据集中映射到值A1，在另一个数据集中映射到值B1——并且它只映射到这两个值。在这种情况下，A1和B1可能是一致的。

这导致了一个良性循环。比如说，单词"nickel"在两个数据集中都映射到两个值：分别是A1和A2，以及B1和B2。我们有两种方式来匹配这四个值

A1->B1 and A2->B2
or
A1->B2 and A2->B1

但是键"egyptian"已经告诉我们A1和B1是一个好的匹配。由于我们已经匹配了这些，这就排除了第二种选择。我们唯一剩下的选择就是匹配A2 -> B2。基于"egyptian"选择一个好的匹配帮助我们排除了多余的选项，并基于"nickel"做出一个好的选择。

简而言之，关联利用了键的相对唯一性。

开始使用关联

要求

关联需要Python 3.6或更高版本。它没有其他依赖。

如果您想运行关联测试套件，您需要安装rapidfuzz包。（rapidfuzz是一个模糊字符串匹配库。它与fuzzywuzzy非常相似，除了rapidfuzz是MIT许可的，而fuzzywuzzy是GPL许可的。）

高级概念模型

要使用关联关联两个数据集，您首先创建一个correlate.Correlator对象。此对象包含两个成员dataset_a和dataset_b；这些表示您想要关联的两个数据集。

您在每个数据集中填充键和值。

一个值是（几乎）任何Python对象。每个值都应该代表您数据集中的一个值。关联不会检查您的值——它们对关联来说是完全透明的。

一个键是一个Python对象，它代表关于值的某些元数据。键“映射”到值；关联检查键，使用两个数据集中匹配的键来匹配它们之间的值。

键通常是字符串——例如，某部电影、电视剧、歌曲或书的标题中的单个单词。但是键不一定是字符串。许多Python数据类型的实例可以用作键；它们只需要是可哈希的。

一旦您用数据填充了correlate.Correlator对象，您就调用它的correlate()方法。这会计算匹配项。它返回一个包含这些匹配项的correlate.CorrelateResult，以及两个数据集中未匹配的对象列表。

匹配项作为correlator.CorrelatorMatch对象的列表返回。每个对象包含三个成员

• value_a，指向来自dataset_a的对象的引用，
• value_b，指向来自dataset_b的对象的引用，
• 以及一个浮点数score。

每个CorrelatorMatch对象都告诉您correlator认为这个value_a映射到这个value_b。分数是一种数学上的置信水平——它是您提供给关联的键和其他元数据的直接结果。匹配项列表按score排序——分数越高，代表匹配的置信度越高。

这是基础知识。但correlate支持一些非常复杂的行为。

• 在将键映射到值时，您可以指定一个可选的权重，它表示该键的相对重要性。默认权重是1。更高的分数表示更高的重要性；权重为2告诉correlate，该键映射到该值的显著性是其他的一半。（权重是键到值映射的特定属性——映射键到值图中的“边”）。
• 键可以映射到多个值。每个映射可以有自己的权重。
• 如果两个数据集都是有序的，则这种顺序可以影响匹配分数。correlate称此为排名。排名是值的属性，而不是键的属性。
• 键可以是“模糊”的，这意味着两个键可以部分匹配，而不是二元的是/否。在correlate中的模糊键必须继承自一个名为correlate.FuzzyKey的自定义抽象基类。

示例代码和infer_mv

correlate附带了一些示例代码供您阅读。希望它能帮助您了解使用correlate的感觉。请查看tests和utilities目录中的脚本。

特别是，utilities中包含一个名为infer_mv的脚本。infer_mv接受一个源目录和要重命名的一组文件和目录，并生成从前者到后者的映射。换句话说，当您运行它时，您是在说：“这里有源目录和一组要重命名的文件和目录。对于要重命名的列表中的每个文件，在源目录中找到与之最相似的文件名，并重命名该文件，使其与源目录中的另一个文件名完全相同。”（如果您要求infer_mv重命名目录，它将递归地重命名该目录中的所有文件和目录。）

例如，如果您已经将文件重命名为您喜欢的样子，但后来从某处得到了一个新副本，只需将现有目录作为“源目录”和新鲜副本作为“文件”运行infer_mv。infer_mv将找出如何重命名新鲜文件，使其具有您喜欢的文件名。

请注意，infer_mv实际上并不执行重命名操作！相反，infer_mv打印出一个shell脚本，如果执行该脚本，则会执行重命名。为什么？在提交之前检查correlate的输出始终是一个好主意。

我这样使用infer_mv

% infer_mv ../old_path *
# look at output, if it's all fine run
% infer_mv ../old_path * | sh

或者，您可以将infer_mv的输出重定向到文件，然后编辑文件，然后执行它。或者别的什么！不管什么对你来说有效！

术语和要求

值

值是表示您的两个数据集中个别元素的Python对象。correlate不检查值，并且对它们的要求很少。以下是值的规则

• 值必须支持==。
• 值比较必须是自反的、对称的、传递的和一致的。以下所有示例中，a、b和c代表值
  • 自反的：值必须始终与自身比较相等。a == a必须评估为True。
  • 对称的：如果a == b为True，则b == a也必须为True。
  • 传递的：如果a == b为True，并且b == c为True，则a == c也必须为True。
  • 一致的：如果a == b为True，则它必须始终为True，如果a == b为False，则它必须始终为False。

键

键是Python对象，用于在两个数据集之间查找匹配项。如果一个键在dataset_a和dataset_b中映射到相同的值，那么这两个值可能是一个很好的匹配。

键必须遵守所有与值相同的规则。此外，键必须是可哈希的。这又反过来要求键必须是不可变的。

精确键

“精确”键是correlate称为任何非“模糊”键的键。字符串、整数、浮点数、复数、datetime对象等都可以用作correlate键，还有许多其他类型的实例。

在考虑匹配时，精确键是二元的——要么它们是完全匹配，要么它们完全不匹配。要处理非精确匹配，您必须使用“模糊”键。

模糊键

“模糊”键是支持执行“模糊”比较的特殊协议的键——比较的结果可以表示不完美或部分匹配。

从技术上讲，一个correlate“模糊”键是correlate.FuzzyKey子类的实例。如果一个键是那个基类的子类的实例，它就是一个“模糊”键，如果不是，它就是一个“精确”键。

模糊键必须遵循上面提到的键的规则。此外，您模糊键的类型也必须遵守与键相同的规则；它们必须是可哈希的，必须支持==，并且它们的比较必须是自反的、对称的、传递的和一致的。

此外，模糊键必须支持一个名为compare的方法，其签名如下：self.compare(other)。参数other将是同一类型的另一个模糊键。您的compare函数应返回一个介于（包括）0和1之间的数字，表示self与other的匹配程度。如果compare返回1，则表示这是一个完美的匹配，两个值是相同的；如果返回0，则表示这是一个完美的不匹配，告诉correlate这两个键没有任何共同点。

correlate要求compare也遵守键之间比较所需的四个数学约束。在下述规则中，a和b是同一类型的模糊键。compare必须符合这四个熟悉的规则

• 自反性： a.compare(a)必须返回1（或1.0）。
• 对称性： 如果a.compare(b)返回x，则b.compare(a)也必须返回x。
• 传递性： 如果a.compare(b)返回x，且b.compare(c)返回x，则a.compare(c)也必须返回x。
• 一致性： 如果a.compare(b)返回x，则它必须始终返回x。

重要的是要注意：两种不同类型的模糊键自动被认为是不同的。correlate甚至不会费心调用compare()来比较它们——它自动将比较的模糊得分设置为0。这对于子类也是正确的；如果您声明了class MyFuzzyNumber(correlate.FuzzyKey)和class MyFuzzyInteger(MyFuzzyNumber)，correlate永远不会将MyFuzzyNumber和MyFuzzyInteger的实例进行比较——它自动假设它们没有任何共同点。

（内部上，correlate将不同类型的模糊键分离开来存储。这是一个至关重要的优化！)

另外，correlate 还可以可选地从未实际调用 a.compare(a)。也就是说，如果完全相同的键在 dataset_a 和 dataset_b 中都映射到某个值，correlate 被允许跳过调用 compare()，而是自动分配一个模糊分数 1。 (目前，如果出现这种情况，它会调用 a.compare(a)，但在开发过程中的某些时候并不总是这样。)

最后，需要注意的是，模糊键比精确键要慢得多。如果你可以完全使用精确键来表示你的问题，你应该这样做！这将使运行速度更快。你可以通过以详细模式运行 tests/ytjd.test.py（使用 -v）来获得速度差异的感觉。在我的电脑上，使用相同语料库但切换到模糊键的测试大约慢 12倍。

API

Correlator(default_weight=1)

关联器类。 default_weight 是在没有指定显式权重时将键映射到值时使用的权重。

Correlator.dataset_a

Correlator.dataset_b

代表你想要关联的两个数据集的 Correlator.Dataset 对象实例。最初为空。

Correlator.datasets

包含两个数据集的列表：[dataset_a, dataset_b]

Correlator.correlate(*, minimum_score=0, score_ratio_bonus=1, ranking=BestRanking, ranking_bonus=0, ranking_factor=0, reuse_a=False, reuse_b=False)

关联两个数据集。返回一个 correlate.CorrelatorResult 对象。

minimum_score 是匹配的最小允许分数。它必须大于或等于 0。

score_ratio_bonus 指定了基于这两个值之间实际计算出的分数与最大可能分数之比的奖励权重。有关更多信息，请参阅 分数比例奖励 部分。

ranking 指定 correlate 应使用的排名计算方法。默认值 BestRanking 表示 correlate 将尝试所有方法并选择所有匹配项中累积分数最高的方法。其他值包括 AbsoluteRanking 和 RelativeRanking。

ranking_bonus 指定基于两个值在它们各自数据集中的位置接近程度的奖励权重，该位置由它们的排名指定。两个值在它们各自数据集中的位置越接近，ranking_bonus 赋予的百分比就越高。

ranking_factor 指定将基本分数乘以两个值在它们各自数据集中的接近程度。如果你使用 ranking_factor=0.4，则匹配将仅自动保留其原始分数的 60%；剩余的 40% 中的某些百分比将根据两个值的接近程度重新分配。

（你无法在同一个关联中使用非零的 ranking_bonus 和非零的 ranking_factor。最多选择一个！)

有关所有这些排名相关参数的更多信息，请参阅本文件的 排名 部分。

reuse_a 允许 dataset_a 中的值与 dataset_b 中的多个值匹配。 reuse_b 与此相同，但用于匹配 dataset_a 的 dataset_b 中的值。如果你将这两个重用标志都设置为 True，则返回的 correlate.CorrelatorResult.matches 列表将包含 所有可能的匹配。

Correlator.print_datasets()

以人类可读的形式打印两个数据集。使用 self.print 打印，默认为 print。

Correlate.Dataset()

表示数据集的对象的类。行为类似于只写字典。

Correlator.Dataset.set(key, value, weight=default_weight)

添加新的关联。

你可以使用 Dataset[key] = value 作为 Dataset.set(key, value) 的快捷方式。

Correlator.Dataset.set_keys(keys, value, weight=default_weight)

将多个键映射到单个值，所有键使用相同的权重。《code》keys《/code》必须是一个包含键的可迭代对象。

Correlator.Dataset.value(value, *, ranking=None)

为值附加额外的元数据。目前仅支持一种元数据：《code》ranking《/code》。

《code》ranking《/code》表示值在数据集中的位置，如果数据集是有序的。《code》ranking《/code》应该是一个表示排名的整数；如果这个值在数据集中是第19个，你应该提供《code》ranking=19《/code》。

Correlator.Dataset.clear(default_weight=1, *, id=None)

清除数据集。将其重新初始化为空状态。你可以选择更改数据集的默认权重和其id。

CorrelatorResult()

这是由《code》Correlator.correlate()《/code》返回的对象的类。包含四个成员

• 《code》matches《/code》，一个《code》CorrelatorMatch()《/code》对象的列表，按分数从高到低排序
• 《code》unmatched_a《/code》，来自《code》dataset_a《/code》的未匹配值的集合
• 《code》unmatched_b《/code》，来自《code》dataset_b《/code》的未匹配值的集合
• 《code》statistics《/code》，一个包含关于相关性的可读统计信息的字典

CorrelatorResult.normalize(high=None, low=None)

标准化《code》matches《/code》中的分数。当使用默认值调用《code》normalize()《/code》时，它会调整每个分数，使它们落在《code》(0, 1]《/code》的范围内。如果未指定《code》high《/code》，则默认为《code》matches《/code》中的最高分数。如果未指定《code》low《/code》，则默认为用于相关性的《code》minimum_score《/code》。

CorrelatorMatch()

这是由《code》Correlator.correlate()《/code》制作的单个匹配表示的对象的类。包含三个成员

• 《code》value_a《/code》，来自《code`dataset_a`《/code`的值。
• 《code》value_b《/code`，来自《code`dataset_b`《/code`的值。
• 《code`score《/code`，表示这个匹配的置信度。分数越高，置信度越高。分数没有预定义的内在含义；它们是所有输入到《strong`correlate《/strong`的结果。

Correlator.str_to_keys(s)

这是一个便利函数。使用合理的方法将字符串《code`s`》转换为字符串键的列表。将字符串转换为小写，将一些常见的标点符号转换为空格，然后在空白边界处拆分字符串。返回一个字符串列表。

从 Correlate 获取良好的结果

不幸的是，你并不总是可以期望每次都使用《strong`correlate《/strong`得到完美的结果。你通常至少需要稍微调整一下。在本质上，《strong`correlate《/strong`是一种启发式方法，而不是精确技术。在使用它之前，通常需要对其进行一些调整，才能产生你想要的结果。

排名

当然，使用《strong`correlate《/strong`的第一步是插入你的数据。我强烈建议你在可能的情况下添加排名信息。

如果两个数据集是有序的，并且等效项应该在每个数据集中大致出现在相同的位置，排名信息可以显著提高匹配质量。要使用排名信息，你应尽可能为每个数据集中的每个值设置《code`ranking`，并在运行《code`correlate()`《/code`时指定《code`ranking_bonus`》或《code`ranking_factor`》。你使用哪个取决于你对数据集排序的信心程度。如果你认为你的排名信息相当准确，你应该使用《code`ranking_factor`》，这会对匹配产生更强的影响。如果你对数据集的排序没有多少信心，选择《code`ranking_bonus`》，这只会提供一点推动。

排名还可以显著提高关联速度。如果有很多得分相同的匹配项，这将为“匹配锅炉”（见下文）带来大量工作，而且这会迅速变得昂贵。即使排名信息的一个轻微推动也能帮助区分得分，从而带来显著的加速。

最低得分

一旦您已输入所有数据，您应运行关联，以排序顺序打印出结果，并将最佳匹配项放在顶部，然后滚动到最底部，看看最差5%或10%的匹配项是什么样子。

如果您的所有匹配项实际上都已经完美匹配——恭喜！您已经从关联中获得了良好的结果，您可以停止阅读这里。但如果不那么幸运，您还有更多工作要做。

清理关联输出的第一步通常是停止其制作不良匹配，通过设置minimum_score。

当您有不良匹配时，通常是因为两个数据集之间没有完美映射。如果在dataset_a中有一个值在dataset_b中没有良好的匹配，那么，关联实际上并没有一种方式知道这一点。因此，它可能无论如何都会将该值匹配到某个值。

从这种方式来看：关联的目标是在两个数据集之间找到匹配项。如果它已经制作了所有可能的好匹配，并且每个数据集中只剩下一个项目，而且它们有任何共同之处，关联会出于绝望将这两个值匹配在一起。

然而！这些不良匹配通常得分非常低。所以所有这些低分的坏匹配都聚集在底部。可能会出现一个拐点，得分显著下降，匹配从好变坏。

这就是minimum_score的作用。minimum_score告诉关联匹配的最低允许得分。当底部有一堆不良匹配时，您只需将minimum_score设置在最高不良匹配和最低良好匹配之间——看看！不再有不良匹配！在不良匹配中使用的值将移动到unused_a和unused_b，这几乎肯定是它们正确的位置。

（技术上讲，minimum_score实际上并不是最低得分。它比最低允许得分略低。也就是说，为了使匹配被认为是可行的，其得分必须大于minimum_score。在Python 3.9+中，您可以用以下方式表达这个概念

actual_minimum_score = math.nextafter(minimum.score, math.inf)

minimum_score的默认值是0，这意味着关联将保留任何得分正的匹配项。）

不幸的是，很难提前预测设置minimum_score的值。它的值实际上取决于您的数据集——您有多少个键，匹配有多好，您使用了什么权重，一切。运行关联、查看输出、找到相关性变差的地方并设置最低得分要直接得多。对于大型数据集，通常得分会有一个突然的明显下降，与关联制作不良匹配相关。这使得它变得很容易：设置最低得分，以保持最后一个良好匹配并忘记其余部分。但无法提前预测那个分数是多少——每个数据集都不同，它实际上是您键和权重的涌现属性，因此您必须为每次运行的关联正确校准它。

（有时在底部的不良匹配中会有一些好的匹配。当这种情况发生时，第一步通常是先修复它，这样不良的匹配就会全部聚集在底部。我无法提供任何通用的建议。我能提出的只是开始实验。改变你的键，调整你的权重，再次运行相关性，看看会发生什么。通常当我这样做时，我会意识到我可以做些什么来改善我输入到correlate的数据，并且我可以从外部解决这个问题。）

权重

如果你仍然没有得到你想要的结果，你应该考虑的下一个调整是增加提供明确信号的键的权重。如果你正在比较的数据集与每个值相关联某种唯一标识符——比如一个剧集号，或发布日期——你应该尝试给这些键一个更重的权重。这样的高权重键可以帮助correlate立即聚焦到最佳匹配。

这取决于你，权重要是多少；我有时会为超级重要的键使用高达5的权重，这意味着这个单个键的权重相当于5个正常键。请注意，在dataset_a和dataset_b中的映射上使用5的权重意味着，如果这些键匹配，它们将有一个基础得分25分！如果该键在每个数据集中只出现一次，那么几乎肯定会导致匹配。

但使用权重可以是双刃剑。如果你的数据中有错误，高权重的不良数据会放大这些错误。一个错误的高权重键出现在错误的价值上可能会提高不良匹配的得分超过正确的匹配。这可能会导致恶性循环——如果价值A1应该与价值B1匹配，但它被映射到价值B43上，这意味着B1可能也会出现不匹配。这剥夺了另一个值正确的匹配。以此类推。

关于权重的最后一点。键的权重不会影响其在匹配中的需求性，它只会影响该匹配的得分。考虑以下涉及加权模糊键的情景

FA1 and FA2 are fuzzy keys in dataset_a
FB is a fuzzy key in dataset_b
VA1 and VA2 are values in dataset_a

dataset_a.set(FA1, VA1, weight=1)
dataset_a.set(FA2, VA2, weight=5)

FA1.compare(FB) == 0.4
FA2.compare(FB) == 0.2

如果correlate必须在以下两个匹配中选择，它将更喜欢哪一个？它会更喜欢FA1->FB，因为correlate在考虑匹配时不考虑权重。它总是更喜欢具有更高无权重得分的匹配。匹配FA2到FB确实会得到更高的最终得分，一旦考虑到权重。但这并不使它成为一个更好的匹配。

理解这一点最好的方法：权重并不使匹配质量更高，它们只是在真实情况下使匹配更有趣。

过于常见的键

同样，如果有超级常见的键不会帮助相关性，考虑丢弃它们，甚至不要将它们作为数据输入。映射到数据集中大多数或所有值的键添加很少的清晰度，并且主要只是使correlate变慢。我通常会丢弃“The”这个词，以及播客或节目的名称。（在比较文件名时，我也可能会丢弃文件扩展名。）

然而，通常保留它们并不会造成伤害，偶尔也可能是有帮助的！correlate的工作方式是，它将一个键到值的多个映射视为不同的事情——如果你将键"The"映射到值两次，correlate会理解这些是两个单独的映射。并且如果每个数据集中只有一个值有两个"The"映射，这确实是一个非常强烈的信号。所以这完全取决于你。丢弃大量冗余的键是一种速度优化，但它不应该影响你匹配的质量。

请注意，当与精确键匹配时，现在的相关（correlate）功能非常高效。对于大多数人来说，冗余或常见键的额外运行时间成本可能微不足道，不值得额外开发时间或维护成本。它们确实只提供了少量信号——但它们在内存或CPU时间上的运行成本也相对较小。在这个阶段，对大多数人来说，几乎不值得费这个功夫。

（但这里有一个考虑两种世界之最佳的理论方法：对于非常常见的键，考虑丢弃第一个实例。我承认我还没有亲自尝试过这个实验。）

检查您的输入

和往常一样，确保您的代码做您打算做的事情是有帮助的。我多次犯了一个错误，就是我用来向相关（correlate）提供数据集的机制；例如，我偶尔将单词的各个字符作为键输入，而不是将单词本身作为键。例如，而不是输入单个键"booze"，我偶尔输入了五个键'b'、'o'、'o'、'z'和'e'。然而，相关（correlate）算法工作得很好，它仍然做得非常好！（虽然速度慢了很多。）

我已经学会了使用调试器或使用Correlator.print_datasets()来双重检查我输入的映射和权重。确保您给相关（correlate）提供了正确的数据可以使它不仅更加准确，还可能使其运行得更快！

规范化字符串

当从现实世界的来源使用字符串作为键时，我建议您规范化这些字符串：将字符串转换为小写，删除大多数或所有标点符号，并在单词边界处将字符串拆分为单个键。在现实世界中，标点和大小写可能都不一致，所以丢弃这些可以有助于消除这些不一致性。相关（correlate）提供了一个名为correlate.str_to_keys()的实用函数来完成这项工作。但您可以使用任何您喜欢的字符串规范化方法。

您还可以考虑将字符串内部化。在我的有限实验中，这提供了一些小但可测量的速度提升。

锐化模糊键

如果您使用模糊键，请确保您已经锐化您的模糊键。模糊字符串匹配库有一个坏习惯，就是将不太相似的字符串评分得与几乎完全相同的字符串相差无几。如果您将未修改的数据提供给相关（correlate），这种“所有东西看起来都差不多”的观点将反映在您的结果中，导致中等匹配。

一般来说，您想要将模糊匹配推向极端。两种好的技术：

• 为模糊匹配指定一个最低分数，并将低于该最低分数的任何模糊分数替换为0。
  • 可能将剩余的范围重新映射到整个范围。例如，如果您的最低分数是0.6，您是否简单地返回从0.6到1的值？或者是否使用(fuzzy_score - 0.6) / (1 - 0.6)将分数拉伸到整个范围？您可能需要尝试两种方法，以找到适合您的方法。
• 将模糊分数乘以自身。平方或甚至立方模糊分数将保留高分数并降低低分数。然而，请注意，模糊键匹配的评分算法已经对模糊分数进行了立方。在大多数情况下，额外的分数自乘可能是多余的。

这些分数是什么意思？

您在结果中看到的分数与您提供给相关（correlate）的数据直接相关。分数实际上只有您赋予它们的意义那么多或少。

如果您不喜欢相关（correlate）分数不可预测的性质，可以考虑在您的Correlate结果对象上调用normalize()。这将按照以下方式规范化分数：最高分数将调整为1.0，minimum_score将调整为0.0，其他所有分数将在这两个值之间进行线性调整。

数学上

score = the original score for this match
highest_score = highest score of any match
minimum_score = the minimum_score passed in to correlate()
delta = highest_score - minimum_score
normalized_score = (score - minimum_score) / delta

算法和代码的实现说明

如果实现难以解释，那就不是一个好主意。 —— 来自Tim Peters的《Python之禅》

以下是一个详尽（且令人筋疲力尽！）的章节，关于 correlate 的实现。这部分内容部分是为了后人，部分是因为我喜欢阅读他人项目中的这类内容，但主要是为了在三年后修复bug时更容易重新熟悉代码。

高级概述

correlate 的核心是一个暴力算法。在计算机科学家看来，这是一个 O(n²) 算法。

correlate 计算所有可能的“匹配”——即把 dataset_a 中的每个值与 dataset_b 中的每个值进行映射，这两个值具有共同的键。对于精确键，它使用集合交集来忽略没有共同点的值对，丢弃已知分数为0的早期匹配。遗憾的是，它不能对模糊键这样做，这也是为什么模糊键通常会显著减慢 correlate 的速度。

对于两个值之间匹配的每个键，correlate 计算一个分数。然后，它将这些分数相加，计算“匹配”的最终累积分数，它可能会根据各种奖金和因素进行修改。然后，它按顺序遍历这些分数，从最高分数开始。对于两个值都没有在匹配中使用过的每个匹配，它将其视为“匹配”并添加到输出中。（这假设 reuse_a 和 reuse_b 都为 False。此外，这有点过于简化；请参阅下文的 匹配锅炉 部分。）

一个重要的细节：correlate 力求达到 100% 的确定性。在Python程序中，随机性可能会在边缘悄悄出现；例如，如果您曾经遍历过字典，您将看到的键的顺序将因运行而异。 correlate 消除了它所能找到的所有随机性的来源。据我所知：给定完全相同的输入，它每次都会以相同的顺序执行相同的操作并产生相同的结果。

与 correlate 算法的工作方式相关的有多个概念，我将在以下子节中逐个详细解释。

correlate 的六次遍历和 Big-O 复杂度

单个 correlate 相关性在其数据上执行六次遍历。以下是这些遍历的高级概述，随后是对这些遍历的新术语和技术细节的深入探讨。

遍历 1

遍历两个数据集并计算“精简”数据。

复杂度： O(n)

遍历 2

遍历所有键并计算所有可能具有非零分数的匹配的排序列表。（该列表表示一个匹配，由每个数据集的值列表中的索引对组成。）此遍历还执行所有模糊键比较并缓存其结果。

复杂度： O(n²)，对于模糊键比较步骤。对于具有大量模糊键的 correlate 运行，这通常是运行速度最慢的部分。如果您的 correlate 主要使用精确键，这一部分将会很快，因为所有 O(n²) 的工作都在 C 代码中完成（集合交集和排序）。

遍历 3

对于每个具有非零分数的匹配，计算匹配所有模糊键的子总计。我们需要将这些总计中的一些相加以计算模糊键匹配的最终分数。

复杂度： O(n²)

遍历 4

对于每个具有非零分数的匹配

• 计算匹配所有精确键的分数，
• 完成模糊键匹配分数的最终计算，
• 计算奖金（score_ratio_bonus、排名），
• 并将结果按排名存储。

每个匹配的分数现在已最终确定。

复杂度： O(n²)

遍历 5

对于正在使用的每种排名方法，使用“匹配锅炉”和“贪婪算法”计算最终成功的匹配列表。

复杂度： O(n log n)（近似）

通过 6

选择得分最高的排名方法，计算 unseen_a 和 unseen_b，然后在返回之前将 "indexes" 替换为其实际值。

复杂度： O(n)

因此，整体相关函数的 Big-O 表示为 O(n²)。相关函数中最慢的部分是处理大量的模糊键；如果你主要使用精确键，你的相关函数运行将会更快。

通过检查 CorrelatorResult 对象的 statistic 成员，你可以看到 correlate 在每个这些遍历中花费了多少时间。这是一个将遍历的字符串描述映射到秒数的字典。遍历 2 处理精确键和模糊键的子遍历是分开的，遍历 5 的 "match boiler" 阶段也是如此。

轮次

如果你按以下方式调用 correlate

c = correlate.Correlator()
o = object()
c.dataset_a.set('a', o)
c.dataset_a.set('a', o)

则键 'a' 真正映射到值 o 两次，这两次映射可以有不同的权重。从技术上讲，正确考虑这种方式是认为在数据集图中，从同一个键到同一个值的两个边。另一种考虑方式是将重复键视为两个不同的键——相同，但以某种方式不同。

(如果有帮助，你也可以将其视为像两个目录中同名文件的两个文件。它们有相同的 filename，但它们不是同一个 file。)

correlate 将这些多个映射的组称为 rounds。一个 "round" 包含了 N 次重复的所有键。轮次 0 包含每个键，轮次 1 包含重复两次的所有键的第二次实例，轮次 2 包含重复三次的所有键的第三次实例，依此类推。轮次是按值划分的，轮次的数量与数据集中任何单个键到任何特定值的最大重复映射数相同。

自然，精确键和模糊键使用不同的方法来确定是否是 "相同的键"。从技术上讲，这两种类型的键都使用 == 来确定等价性。然而，模糊键没有实现自定义的 __eq__，因此 Python 使用其默认机制来确定等价性，这实际上就是 is 操作符。因此：精确键是相同的，如果 == 说它们是相同的，而且在实践中，模糊键只有在它们是相同对象的情况下才被认为是相同的。

(当然，你可以在编写自己的模糊子类时实现自己的 __eq__。但我不知道你为什么要费这个劲。)

考虑以下示例

c = correlate.Correlator()
o = object()
c.dataset_a.set('a', o, weight=1)
c.dataset_a.set('a', o, weight=3)
c.dataset_a.set('a', o, weight=5)
c.dataset_a.set('b', o)
c.dataset_a.set('b', o)
c.dataset_a.set('c', o)

o2 = object()
c.dataset_b.set('d', o2)
c.dataset_b.set('d', o2)
c.dataset_b.set('e', o2)
c.dataset_b.set('f', o2)

这里，dataset_a 中的值 o 将有三轮

• 轮次 0 将包含键 {'a', 'b', 'c'}。
• 轮次 1 将包含键 {'a', 'b'}。
• 轮次 2 将只包含一个键，{'a'}。

并且 dataset_b 中的 o2 只有两个轮次

• 轮次 0 将包含键 {'d', 'e', 'f'}。
• 轮次 1 将只包含一个键，{'d'}。

在概念上，轮次 0 的 "a" 与轮次 1 的 "a" 是不同的键，依此类推。

对于精确键，轮次是直接逐个匹配的；dataset_a 中一个值的轮次 0 精确键与 dataset_b 中一个值的轮次 0 精确键匹配，轮次 1 在 dataset_a 中匹配轮次 1 在 dataset_b 中，依此类推。如果其中一侧的轮次提前用完，则停止；如果你计算轮次的交集，并且它们没有共同点，则停止。

一个不变的性质：每个后续轮次都是之前轮次的子集。轮次 N+1 中的键集合必须是轮次 N 中的键集合的子集。（尽管不一定是严格的子集。）

关于权重呢？权重越高，排序就越靠后。在 N-1 轮中键 k 的权重必须大于或等于在 N 轮中的权重。在上面的例子中，第 0 轮的 'a' 权重为 5，第 1 轮为 3，第 2 轮为 1。（插入顺序无关紧要，correlate 会自动按添加的冗余映射对权重进行排序。）

因此，第 0 轮总是包含映射到特定值的所有精确键，以及每个映射的最高权重。

轮次肯定有助于找到最佳匹配。如果键 "The" 一次映射到大多数值，那并不特别有趣，也不会对分数产生很大影响。但如果每个数据集中只有一个值被 "The" 映射了两次，那确实是一个强烈的信号！correlate 在注意这种独特性并将其纳入评分方面做得非常好。

简化数据

correlate 数据集以设计用于消除冗余并易于修改的格式存储数据。但此表示法不便于执行实际的关联。因此，第一步（“Pass 1”）是将数据重新处理为“简化”格式。这是一个仅限内部使用的实现细节，实际上，数据在每个关联结束时都会被丢弃。作为最终用户，您永远不会处理它。这里只记录下来，以防您需要了解 correlate 的实现。

这种简化数据表示法是一个重要的优化。它大大加快了计算两个值之间的匹配速度。并且与所有匹配工作相比，仅花费一点开销。考虑一下：如果您有 dataset_a 和 dataset_b 中的 600 个值，correlate 将重新计算 1,200 个简化数据集。但随后将在多达 360,000 次比较中使用它！在方便的格式中预计算数据可以节省大量时间。

随着实现的更改，简化数据的格式也会更改。由于它是一个仅限内部使用的细节，因此大部分在这里没有记录。如果您需要更多信息，您只需阅读代码即可。在代码中搜索单词 streamlined。

评分公式和分数守恒

对于它考虑的每个匹配项，correlate 计算两个数据集中每个值映射到的键的交集，然后根据每个键匹配项计算一个分数。这个评分公式是 correlate 的核心，而且它是一个关键的洞见——没有它，correlate 的效果将远远不如现在。

在抽象层面，它看起来是这样的

for value_a in dataset_a:
    for value_b in dataset_b:
        subtotal_score = 0
        for key_a, weight_a that maps to value_a:
            for key_b, weight_b that maps to value_b:
                score = value of key_a compared to key_b
                cumulative_a = the sum of all scores resulting from key_a mapping to any value in dataset_b
                cumulative_b = the sum of all scores resulting from key_b mapping to any value in dataset_a
                score_ratio_a = score / cumulative_a
                score_ratio_b = score / cumulative_b
                unweighted_score = score * score_ratio_a * score_ratio_b
                score_a = weight_a * unweighted_score_a
                score_b = weight_b * unweighted_score_b
                final_score = score_a * score_b
                subtotal_score += final_score

在继续之前，有两个注意事项

• key_a 和 key_b 必须总是按 轮次，出于许多原因，其中最不重要的是我们在计算 final_score 时使用它们的权重。

• subtotal_score 可能还会根据是否使用了 score_ratio_bonus 和排名进行调整。我们稍后将会讨论这一点。

此公式是 correlate 计算表示“独特性”的数学表示的方法。一个键在数据集中映射到的值越少，它得分的就越高。在每个数据集中仅映射一次的键比在每个数据集中映射两次的键得分高 4 倍。

这个评分公式具有一种我称之为“分数守恒”的优良数学属性。在数据集中添加到某一轮次的每个键都会将所有可能匹配的总累积分数增加1；当将键映射到多个值时，将这些分数平均分配给这些值。例如，如果键x在dataset_a中映射到三个值，在dataset_b中映射到四个值，那么这些可能的匹配项每个只获得该键分数的1/12，而所有匹配项的最终累积分数只会增加1/12。因此，键总是将1加到所有可能匹配项的总分数上，但只有当它实际传达的信号量时，才会增加实际的最终分数。

此外，现在你知道为什么重复的键可以如此有趣。它们为每一轮增加1分，但这个分数只被分配到它们在这一轮次中映射的值的数量上！由于在随后的轮次中一个键的使用越来越少，那些能够进入后续轮次的少数键的得分可能会比早期轮次高得多，这使得它们成为一个更有意义的信号。

匹配和精确键的评分

精确键的“简化”数据格式如下

exact_rounds[index][round] = (set(d), d)

也就是说，它是按“索引”（代表值）索引的，然后是按轮次编号。这提供了一个包含将键映射到权重的字典的元组，以及仅包含键的set()。correlate使用set.intersection()（非常快！）来找出两个值在那一轮次中具有的共同精确键的集合。这个结果集合的长度是那一轮次的基数累积分数，尽管这个数字在计算score_ratio_bonus时仅直接有用。

尽管在抽象意义上，correlate为精确键和模糊键使用相同的评分公式，但在实践中，精确键之间的匹配评分要简单得多。让我们根据精确键对上面的“抽象”评分算法进行修改。这让我们在几个地方优化算法，使其更快！

首先，对于精确键，自然它们要么完全匹配，要么不匹配。如果它们完全匹配，它们是相同的Python值。因此，key_a和key_b必须完全相同。因此，从概念上讲，我们可以交换它们。让我们稍微改写一下“评分公式”方程

cumulative_a = the sum of all scores between key_b and all keys in dataset_b
cumulative_b = the sum of all scores between key_a and all keys in dataset_a

我们所改变的就是：我们交换了key_a和key_b。（为什么？这会有帮助。嘿，继续读。）

现在考虑：精确键的score总是1或0。当两个键完全相同时，它是1，否则是0。如果匹配的基数score是0，那么final_score将是0，我们可以跳过所有这些。所以，我们只在score是1时计算final_score，即键完全相同的时候。

由于score仅用作乘数，我们可以丢弃它。

cumulative_a和cumulative_b也容易计算。它们只是该键在相关数据集中映射到任何值的次数，在该轮次。这些计数是预先计算并存储在“简化”数据中的。

因此，最终：如果你进行替换，并取消常数score因子，精确键的final_score可以这样计算

final_score = (weight_a * weight_b) / (cumulative_a * cumulative_b)

我们可以将其重新排列为

final_score = (weight_a / cumulative_b) * (weight_b / cumulative_a)

当我们为dataset_a预先计算简化数据时，我们知道weight_a，并且我们可以计算cumulative_b，因为它只使用dataset_a中的项。因此，我们可以预先计算这些项，使得最终的数学计算更简单

# when computing the streamlined data
precomputed_a = weight_a / cumulative_b
precomputed_b = weight_b / cumulative_a

# ...

# when computing the score for a matching exact key
final_score = precomputed_a * precomputed_b

这要简单得多！这些优化使correlate变得更快。

模糊键

让我给你讲一个精彩的睡前故事。从前，有一个叫做“关联”的小东西，它又小又可爱。但那个版本只支持精确的键。当模糊键完全实现，功能完善，并且运行得很好时，“关联”变得更加复杂，也更加“实用”。这是因为模糊键引入了许多复杂的行为，导致了与精确键相比根本不会出现的棘手情况。

考虑以下示例

你的两个数据集代表了农场列表。两个数据集都列出了动物，但可能包含通用的信息（“马”）或具体的细节（“克莱德代尔”）。你创建了一个名为《AnimalKey》的模糊键子类，可以处理这些匹配；AnimalKey("Horse/Clydesdale")匹配AnimalKey("Horse")，尽管分数小于1，因为它不是完美匹配。

相同的农场，Farm X，出现在两个数据集中。

• 在dataset_a中，键AnimalKey("Horse")映射到Farm X两次。

• 在dataset_b中，键AnimalKey("Horse/Clydesdale")和AnimalKey("Horse/Shetland Pony")映射到Farm X。

问题：是否应该将dataset_a中的某个“Horse”键与dataset_b中的“Horse/Clydesdale”匹配，并且另一个“Horse”键应该与“Horse/Shetland Pony”匹配？

当然应该这样做！但考虑一下后果：我们刚刚将dataset_a中的第二轮的键与dataset_b中的第一轮的键匹配。这是不可能使用精确键实现的！

用于模糊键的评分在概念上与精确键的评分相同，包括“轮次”的概念。在实践中，模糊键评分要复杂得多；我在精确键的描述中省略了一些乘数，因为它们总是1，还有一些对于精确键容易计算的事情，我们必须以困难的方式为模糊键计算。（如果你感兴趣，文档的末尾有一个关于“关联”中模糊键评分历史的完整部分。）

此外，数据集中的单个值可以有多个同一类型的模糊键，这意味着现在我们可以在一个数据集中有多个键与另一个数据集中的同一键竞争。在上面的农场和马的例子中，《关联》需要将来自dataset_a的AnimalKey("Horse/Clydesdale")和AnimalKey("Horse/Shetland Pony")与来自dataset_b的AnimalKey("Horse")进行比较。

但是《关联》不会将一个键生成的所有可能的模糊分数相加；在计算最终分数时，一个模糊键只与另一个模糊键匹配。如果模糊键FA1和FA2在dataset_a中映射到值VA，并且模糊键FB在dataset_b中映射到值VB，那么《关联》将考虑FA1 -> FB以及FA2 -> FB，并且只保留分数最高的匹配。匹配“消耗”了两个键（每个数据集中的一个），它们不能再被匹配。（再次强调：当我这里说“键”时，我指的是“这一轮的键”。）这一面的反面：未匹配的键没有被“消耗”。我们该如何处理它？上面的马和农场的例子清楚地表明：未消耗的模糊键应该被回收——在后续的轮次中重复使用。

因此，精确键使用非常精确的“轮次”，而模糊键则需要更动态的方法。确切地说，第N轮未使用的键在概念上“存活”到第N+1轮。这正是上述关于农场和马匹的例子所展示的；在第0轮，如果dataset_a中的"Horse/Clysedale"与dataset_b中的"Horse"匹配，dataset_a中的"Horse/Shetland Pony"将无法匹配，并存活下来，进入第1轮。这也使得评分变得更加复杂。（有关更多信息，请查看测试套件。有一个回归测试可以测试这种行为。）

经过多次重写，我发现计算模糊匹配最快的方法是：对于两个值共有的每个模糊类型，计算所有可能匹配的模糊键之间的所有可能匹配，即使跨轮次混合。然后对匹配进行排序，优先考虑高分而不是低分，优先考虑低轮次的匹配而不是高轮次的匹配。

模糊键的简化数据看起来是这样的

fuzzy_types[index][type] = [
                           [(key1, weight, round#0),  (key1, weight, round#1), ...],
                           [(key2, weight, round#0),  (key2, weight, round#1), ...],
                           ]

也就是说，它们通过索引（值的表示）索引，然后通过模糊类型索引。这会得到一系列列表。每个内部列表是包含元组的列表，其中

(key, weight, round_number)

其中key在列表的所有条目中总是相同的，而round_number总是与该元组在该列表中的索引相同。

在计算模糊键之间的匹配时，相关函数会取两个列表并对其执行嵌套的for循环。由于键不会改变，它只需要查找一次模糊得分。如果模糊得分大于0，它将匹配存储在数组中。

完成模糊键匹配后，它将匹配数组进行排序，然后使用“匹配锅炉”将其缩减，以确保每个轮次的键最多匹配一次。（“匹配锅炉”将在稍后讨论；现在只需假设它是一个能够正确执行的魔法函数。尽管我必须确保它对这种方法非常稳定。）

对这些模糊键匹配进行排序很棘手。它们不仅仅是按分数排序；我们还要确保在更高轮次中使用该键的匹配之前，总是先消耗较早轮次的模糊键匹配。因此，我们使用一个特殊的sort_by元组作为排序键，如下计算

key_a, weight_a, round_a = fuzzy_types_a[index_a][type]...
key_b, weight_b, round_b = fuzzy_types_b[index_b][type]...
fuzzy_score = key_a.compare(key_b)
lowest_round_number  = min(round_a, round_b)
highest_round_number = max(round_a, round_b)
sort_by = (fuzzy_score, -lowest_round_number, -highest_round_number)

-lowest_round_number技巧是非常巧妙的。这使得我们可以按最高值最后排序，这正是“匹配锅炉”想要的。但是取反意味着较低的轮次号现在是较高的数值，这使得我们可以优先考虑轮次较低的键。

就抽象评分公式而言，score是模糊得分，由调用compare()方法返回。而cumulative_a是所有使用key_a的模糊score得分的总和。

评分比率奖金

使用score_ratio_bonus计算一个“奖金”分数。它是为将dataset_a中的值映射到dataset_b中的值而计算的。这个奖金是在评分之前计算的最后一个东西之一。

奖金的计算如下

value_a = a value from dataset_a
value_b = a value from dataset_b
actual_a = total actual score for all keys that map to value_a in dataset_a
actual_b = total actual score for all keys that map to value_b in dataset_b
possible_a = total possible score for all keys that map to value_a in dataset_a
possible_b = total possible score for all keys that map to value_b in dataset_b
bonus_weight = score_ratio_bonus * (actual_a + actual_b) / (possible_a + possible_b)

使用score_ratio_bonus计算的这个奖金解决了当映射到一个值的键集合是同一数据集中另一个不同值映射的键集合的子集时的歧义。匹配的键比例越高，这个奖金就越大。

考虑以下示例

c = correlate.Correlator()
c.dataset_a.set('breakin', X)

c.dataset_b.set('breakin', Y)
c.dataset_b.set_keys(['breakin', '2', 'electric', 'boogaloo'], Z)

哪个匹配更好，是 X→Y 还是 X→Z？在 correlate 的早期版本中，这两种匹配得到了完全相同的分数。因此，哪个匹配会被 correlate 选择纯粹是运气问题。score_ratio_bonus 解除了这种歧义。它给予 X→Y 的奖励比 X→Z 更大，因为 X 和 Y 之间的匹配键的百分比比 X 和 Z 之间的匹配键的百分比更高。这个小推动通常就足以让 correlate 解除这些情况并选择正确的匹配。

有两点需要注意。首先，当我提到“键”时，这是另一种情况，在这种情况下，同一个键映射到相同的值被认为是两个不同的键。在上面的 Round 子部分中给出的例子中，其中 value_a 是 o，value_b 是 o2，则 possible_a 将是 6，而 possible_b 将是 4。

其次，用于计算 actual 和 possible 的分数是 未加权 的。如果两个模糊键之间的匹配产生了模糊分数 0.3，则将 0.3 添加到 actual_a 和 actual_b，但每个模糊键分别将 1.0 添加到 possible_a 和 possible_b。在计算 score_ratio_bonus 时始终忽略权重，就像在比较匹配时忽略权重一样。

选择保留哪些匹配：贪婪算法和匹配锅炉

这里有一个问题，以抽象形式呈现：如果你被呈现一个名为 matches 的匹配对象列表，其中每个匹配对象 M 有三个属性 value_a、value_b 和 score，你会如何计算 matches 的一个最优子集，使得

• 每个 value_a 和 value_b 的离散值只出现一次，并且
• score 属性的总和最大化？

找到完美最优解需要计算所有可能的匹配集，然后计算该集合的累积分数，然后选择具有最高分数的集合。不幸的是，该算法是 O(nⁿ)，这非常昂贵，以至于我们甚至无法考虑它。（您可能希望在太阳变成红巨星之前获得 correlate 的结果。）

相反，correlate 使用一个相对便宜的“贪婪”算法来计算子集。它不保证产生最优子集，但在实际应用中它似乎在真实世界数据上产生最优结果。

以下是 correlate “贪婪”算法的简要描述

• 按分数从高到低排序 matches。
• 对于 matches 中的每个匹配 M
  • 如果 value_a 尚未匹配，
  • 并且 value_b 也尚未匹配，
    • 将 M 作为良好匹配保留，
    • 并记住 value_a 已被匹配，
    • 并记住 value_b 已被匹配。

排序使用 Python 的内置排序（Timsort），所以它是 O(n log n)。它在 C 中实现，所以相当快。循环是 O(n)。

然而！在 correlate 的后期开发中，我意识到存在一个角落案例，其中贪婪算法不太可能产生最优结果。幸运的是，这个修复相对简单，而且修复并没有使 correlate 在一般情况下变慢。

让我们从问题开始，一个棘手的角落案例。如果列表中的两个匹配都是可行的，并且它们有 相同的 分数，并且它们有 value_a 或 value_b 的共同点，这将是不确定的，贪婪算法将选择哪个匹配。但是选择错误的匹配可能会在实践中导致得分低于最优。

以下是一个具体的例子

• dataset_a 包含模糊键 fka1 和 fka2。
• dataset_b 包含模糊键 fkbH 和 fkbL。任何包含 fkbH 的匹配的分数都高于任何包含 fkbL 的匹配。（H 代表高分数，L 代表低分数。）
• 匹配项fka1->fkbH和fka2->fkbH具有相同的分数。
• 匹配项fka1->fkbL的分数低于fka2->fkbL。

如果correlate选择了fka2->fkbL来与fka1->fkbL相关联，那么所有匹配项的累积分数会更高。由于在correlate中的分数是匹配质量的指标，因此累积分数越高，表示匹配质量越高。因此，我们应该尽可能最大化累积分数。

但是，贪婪算法只有在先前选择了fka1->fkbH的情况下才能选择得分更高的第二个匹配项。而且，它没有保证会这样做！如果列表中的两个项目具有相同的分数，那么贪婪算法会选择哪个就不确定了。

为了正确处理这种情况，它需要向前看并进行实验。这就是为什么我写了所谓的“匹配锅炉”，简称“锅炉”。锅炉采用混合方法。默认情况下，当匹配项的分数是唯一的，它使用“贪婪”算法。但如果它遇到一组具有匹配分数的项目，其中任何项目都有共同的value_a或value_b，它将递归运行一个实验，依次选择这些匹配项。它从每个递归实验中计算分数，并保留分数最高的那个。

（如果有两个或更多实验具有相同的分数，它将保留第一个具有该分数的实验--但是，由于“匹配锅炉”的输入是一个列表，按照最高分数从大到小排序，技术上它是列表中产生高分数实验的最后一个条目。）

有了“匹配锅炉”，即使在这些罕见的不确定情况下，correlate似乎也能产生最优结果。

我老实说，不确定“匹配锅炉”的大O表示法是什么。最坏的情况可能是O(n log n)，其中log n部分代表递归。在这种情况下，每个匹配项都具有相同的分数，并且它们都通过具有共同的value_a和value_b相互连接。我仍然认为“匹配锅炉”不会像O(n²)那样糟糕。问题是，迟早递归步骤会将“连接项目”的“组”减半（见下一节）。它保证不会对每个项目递归。所以我认为这大约将递归步骤的数量减少到log n，在病理最坏的情况下，你永远不会在现实世界的数据中看到这种情况。

廉价递归和“分组器”

但是等等！这还更复杂！

与其他算法相比，“匹配锅炉”的递归步骤相当昂贵。它确实在每个步骤都减少了问题的域，所以它保证会完成--总有一天。但是，如果我们不小心，它将执行很多昂贵且冗余的计算。因此，需要对匹配锅炉的递归步骤进行一些优化，主要与具有相同分数的匹配项组有关。

第一步是分析这些匹配项，并将它们“连接组”分离出来。一个“连接组”是一组匹配对象，其中每个对象与组中的另一个对象具有共同的value_a或value_b。这些是相关的，因为选择这些组中的匹配项之一将至少从该组中删除一个其他值，因为那个value_a或value_b现在是“已使用”的，因此所有剩余的匹配使用这些值的匹配项都将被丢弃。

这里有一个例子可能有助于说明。假设你有这六个连续的匹配项，它们都具有相同的分数

match[1]: value_a = A1, value_b = B1
match[2]: value_a = A1, value_b = B2
match[3]: value_a = A2, value_b = B1
match[4]: value_a = A3, value_b = B2
match[5]: value_a = A10, value_b = B10
match[6]: value_a = A10, value_b = B11

这将会分为两个“连通组”：匹配1-4将属于第一个组，而匹配5-6将属于第二个组。第一个组中的每个匹配都有一个成员（value_a或value_b）与其他第一个组中的至少一个匹配有共同点；第二个组中的每个匹配至少有一个成员与其他第二个组中的匹配有共同点。因此，第一个组中的每个匹配都是“连通”的；如果你将它们放在一个图中，每个匹配都可以从该组中的其他任何匹配“到达”，即使它们不是直接相连的。例如，match[4]与match[1]没有共同成员，但它们都与match[2]有共同成员。但是第一个组中的所有匹配都与第二个组中的任何匹配没有共同成员（反之亦然）。

有一个名为grouper()的实用函数用于计算这些连通组。（grouper()仅处理reuse_a == reuse_b == False的情况；还有其他实现来处理其他可能的情况，例如grouper_reuse_a()。）

第二步是取那些“连通组”，对于只包含一个匹配对象的每个组，“立即”保留它。我们已经知道我们会保留这些，而且先做这个会更便宜。

现在，只剩下的大小为2或更大的连通组，第三步是递归遍历这些连通组中最小的一个的每个值。为什么是最小的？因为它更便宜。假设列表中剩下50个匹配项。在顶部有6个得分相同的匹配对象。有两个组：一个长度为2，另一个长度为4。

一个重要的认识是，当我们使用这些值进行实验并递归时，我们仍然必须检查我们之前没有丢弃的所有剩余匹配项。通过循环和递归执行的操作数量，大约是 N • M，其中 N 是len(group)，M 是len(matches - group)。所以哪个操作更少

• 2 x 48，还是
• 4 x 46？

显然是第一个！通过递归到较小的组，我们执行的操作更少。

（在这里有进一步优化的理论机会：当递归时，如果有多个长度为2或更大的连通组，将我们没有消耗的组列表传递给递归步骤。这将节省递归调用重新计算连通组的计算。在实践中我想这种情况很少发生，所以处理它会导致一些永远不会执行的if分支。此外，这比看起来要复杂一些，因为在你将其传递下去之前，你需要对你要检查的组重新使用grouper()，因为它可能会将其分成两个组。在实践中，这不会加快任何人的相关速度，而且会让代码更复杂。所以让我们跳过它。代码在这些罕见情况下已经足够正确了。）

匹配锅炉用于模糊键评分重用

当我的第一个版本的“匹配锅炉”完成时，我意识到我可以将其用于降低所有模糊键匹配。模糊键匹配已经使用了与匹配相同的“贪婪”算法，我意识到这里也存在相同的边缘情况。

我的第一次尝试相当复杂，因为“匹配锅炉”本身并不理解轮次。我添加了一个回调，每次它保留一个匹配都会调用它，并传入匹配的键。由于这些键现在“被消耗”，我会使用这些键从后续的轮次（如果有的话）中注入新的匹配。这可以工作，但代码很复杂。

后来当我添加了递归步骤时，情况变得更加复杂！我必须保存和恢复所有从哪个回合消耗了哪些模糊键的状态。我最终将它构建成MatchBoiler子类的功能，这也是为什么MatchBoiler在递归时会克隆自己的原因。这使得代码更简洁，但仍然有些笨拙且速度有点慢。

使用sort_by元组进行后续重写是一大胜利：它简化了代码，让我可以移除回调，让匹配锅炉隐式地处理所有回合而不真正理解它们，并且它甚至稍微快一点！

但是，这正是为什么锅炉必须非常稳定的原因。早期的匹配锅炉版本假设它可以在任何时候对输入数组进行排序。但是传入的数组是按分数排序的，然后按回合编号排序——最高分数最重要，最低回合编号其次。数组按最高分数排序，然后是最低回合编号，最后排序。在递归时，匹配锅炉必须优先考虑其输入中产生相同分数的最后条目——否则，它可能会意外地在一个较早的回合消耗一个键之前，先从一个较晚的回合消耗该键。

我不想教会锅炉理解这个sort_by元组。幸运的是，我没有必要这样做。确保锅炉非常稳定的工作量并不大，一旦这一点成立，它就总是产生正确的结果。（更不用说……更快！）

匹配锅炉的理论缺陷

即使有“匹配锅炉”，你仍然可以构造出一些场景，其中correlate将产生可以说是次优的结果。锅炉只尝试匹配分数相同的实验。但是贪婪算法可能会找到局部最大值，导致它错过全局最大值。

如果A和B是dataset_a中的值，而X和Y是dataset_b中的值，且匹配具有以下分数

A->X == 10
A->Y == 9
B->X == 8
B->Y == 1

在这种情况下，锅炉将选择A->X，这意味着它只剩下B->Y。总分：11。但如果是选择了A->Y，那么它可以选择B->X，总分将是17！太棒了！

这是否更好？你的第一反应可能是“当然！”。但在这种抽象的、假设的情景中，很难确定。我的意思是，是的，这是一个更好的分数。但这是否是一个更好的匹配？这是用户想要的输出吗？谁知道——这个情景本来就是一个完全的假设。

我怀疑这并不是实践中真正的问题。确保correlate能够处理具有相同分数的项目的模糊场景已经“锦上添花”，考虑到现实世界数据中这种情况很少发生。而现实数据会以这种方式表现吗？为什么A对X和Y的分数如此之高，而B对X的分数很高，但对Y的分数很低？如果B是X的好匹配，而X是A的好匹配，且A是Y的好匹配，那么，在现实世界数据中，传递性会表明B是Y的好匹配。这个假设情景越看越不切实际，不太可能出现在现实生活中。

我认为“匹配锅炉”会失败的这个病态场景并不现实。我想出的唯一解决方法是代价高昂的O(nⁿ)算法。这根本不值得。所以，放松！正如我们所说，Python中的YAGNI（不要过早优化）。

排名

排名信息可以大有帮助。如果 dataset_a 中的某个值接近开头，并且值的顺序很重要，那么我们应该优先将其匹配到 dataset_b 中接近开头的值。当数据集有序时，将 dataset_a 中的第一个值与 dataset_b 中的最后一个值相匹配可能是一个糟糕的匹配。

从概念上讲，它的工作方式如下：在评分匹配时，测量两个值之间的距离，并让这个距离影响分数。两个值之间的距离越近，得到的分数就越高。

但是，您如何计算这个距离？排名数字的含义是什么？相关 支持对排名的三种可能解释

• 绝对排名，
• 相对排名，和
• 反转绝对排名。

这三种方法在比较排名数字的方式上有所不同，如下所示

• 绝对排名 假设排名数字在两个数据集中都是相同的。ranking=5 在 dataset_a 中与 dataset_b 中的 ranking=5 完美匹配。当您的数据集都相对完整时，这很有效；如果它们的大小不同，可能一个或两个都是在开头或结尾被截断的。
• 相对排名 假设两个数据集代表相同的数据范围，并使用值的排名与该数据集中最高排名的比例来计算其相对位置。如果我们在一个特定数据集中看到的最高排名是 ranking=150，那么设置为 ranking=12 的值被计算为从开头到结尾的 8%。这两个数据集都按相同方式计算这个百分比，两个值之间的距离是这两个百分比之间的距离。如果您的数据集中的一个或两个是稀疏的，这很有效。
• 反转绝对 类似于 绝对，但开始于 末尾 而不是 开头。想想看 绝对 排名：它是在比较数据集开头到特定值的距离。那么，反转绝对 使用的是从数据集 末尾 到特定值的距离。考虑一下：如果 dataset_a 包含 100 个值，而 dataset_b 只包含 15 个值，但它们与 dataset_a 的最后 15 个值匹配，那么 绝对 或 相对 都不是很好的匹配。您想要的应该是 反转绝对。

这里有一个更具体的例子来说明这些方法是如何工作的。假设 dataset_a 有 101 项，排名从 0 到 100，dataset_b 有 801 项，排名从 0 到 800，我们在 dataset_a 中有一个 ranking=50 的值。

• 使用 绝对 排名，dataset_b 中最接近的值将是 ranking=50。这两个值都在第一个（最低排名）值之后 50 个元素。
• 使用 相对 排名，dataset_b 中最接近的值将是 ranking=400。这两个值都在它们各自数据集中排名的中间。
• 使用 反转绝对 排名，dataset_b 中最接近的值将是 ranking=750。这两个值都在最后一个（最高排名）值之前 50 个元素。

那么 相关 使用的是哪一种？可以通过向 correlate() 函数的 ranking 参数提供不同的值来配置它。默认情况下，它使用“最佳”排名。“最佳”排名意味着 相关 使用 所有 方法计算分数，并选择得分最高的一个。您可以通过提供不同的 ranking 值来覆盖此设置，但这通常是不必要的。（从理论上讲，使用仅一种排名方法应该更快。不幸的是，这还没有被优化，因此使用仅一种排名目前并不能加快速度。）

排名是计算匹配分数的最后一步。至于排名如何影响分数，这取决于您是否使用 ranking_bonus 或 ranking_factor。

两种方法都以这四个计算开始

semifinal_scores_sum = sum of all "semifinal" scores above
ranking_a = the ranking value computed for value_a
ranking_b = the ranking value computed for value_b
ranking_score = 1 - abs(ranking_a - ranking_b)

排名奖金然后按场比赛计算，如下所示

bonus = ranking_score * ranking_bonus
final_score = semifinal_scores_sum + bonus

排名因子也是按场比赛计算的，如下所示

unranked_portion = (1 - ranking_factor) * semifinal_scores_sum
ranked_portion = ranking_factor * semifinal_scores_sum * ranking_score
final_score = unranked_portion + ranked_portion

（如果你两者都不使用，比赛的有效最终得分实际上是半决赛得分总和。）

显然，必须在两个数据集中的两个值上设置排名，才能正确计算排名得分。如果没有在考虑比赛的两个值上设置，则关联仍然会像平常一样应用排名奖金或排名因子，但会跳过最初的四个计算，仅使用0的排名得分。

最终随机主题

调试

当所有其他方法都失败时...接下来怎么办？

关联可以选择性地产生大量的调试输出。主要功能是显示它测试的每个匹配，以及该匹配的得分，包括沿途的每个步骤。这种日志输出很快就会变得非常大；即使是600x600元素的比较也会产生数兆字节的输出。

不幸的是，产生这么多的调试输出会带来可衡量的性能损失——即使你关闭了日志记录！它主要是在计算日志中的“f-strings”，但调用日志函数肯定也增加了开销。

我的解决方案：默认情况下，每个调试打印语句都是注释掉的。关联附带一个名为debug.py的自定义脚本预处理器，可以通过取消注释和重新注释调试代码来切换调试状态。

它是如何知道要取消注释哪些行的？仅包含日志的代码的每一行都以特殊标记“#debug”结尾。

要开启此日志记录，在包含关联的__init__.py脚本的同一目录中运行debug.py脚本。每次运行它时，它都会切换（取消注释/重新注释）调试打印语句。请注意，关联中的调试功能需要Python 3.8或更高版本，因为它经常使用3.8所喜爱的“f-strings”中的“等于号”语法。

默认情况下，日志会发送到标准输出。如果你想覆盖发送位置，编写自己的print函数，并在调用correlate()之前将其分配给Correlator对象。

日志的格式尚未记录，并且可能会更改。祝你好运！你主要想做的就是找出你想要比较的dataset_a和dataset_b中值的“索引”，然后搜索“ (index_a) x (index_b) ”。例如，如果你想要的匹配是dataset_a中索引35的值和dataset_b中索引51的值之间的匹配，则在日志中搜索“ 35 x 51 ”。（前导和尾随空格意味着你的搜索将跳过，例如，“235 x 514”。）

未成功的工作的替代模糊评分方法

我发现模糊评分背后的数学有些令人惊讶。如果你将公式简化为其构成因素，你会注意到其中一个因素是模糊得分的立方。为什么是立方？

最简单的答案：那是第一个似乎正常工作的方法。要真正理解为什么，你需要了解关联中模糊评分的历史——我最初尝试的所有那些没有成功的方法。

最初，模糊匹配的得分只是模糊分数乘以权重和其他修饰因子。这始终是一个愚蠢的想法；这意味着模糊匹配对得分的贡献远远超过了它们应该有的程度。这在你缩小到最后10%或20%的匹配时尤其如此，此时精确键贡献的分数已经大大减少。这种方法持续了很长时间，从现在看来，这令人尴尬；我自以为模糊键天生比精确键更有趣，因此这种比较的重要性是合适的。

一旦我意识到这一点有多么愚蠢，显然的方法是将它们与精确键以相同的方式评分——将模糊分数除以每个数据集中可能匹配的键数的乘积。这显然是错误的。在“YTJD”测试中，每个值都有一个或多个模糊键，具体取决于测试：每个值始终有一个模糊日期键，根据测试，它可能还有一个模糊标题键和一个/或模糊集数键。因此，第一个数据集中的812个值中的每个值都有一个模糊类型键，第二个数据集中的724个值也是如此。即使我们得到了完美的模糊匹配，模糊匹配的最大分数现在也是1.0 / (812 * 724)，即0.0000017。因此，我们现在遇到了相反的问题：即使是一个完美的模糊匹配，对最终得分的影响几乎可以忽略不计。

经过一段时间的思考，我意识到，精确键的分数实际上并没有按两个数据集中的键的数量来分，而是被除以每个数据集中该键可能贡献的总分数。因此，他们应该除以涉及这两个键的所有匹配的累积模糊分数。这个公式看起来像fuzzy_score / (sum_of_fuzzy_scores_for_key_in_A * sum_of_fuzzy_scores_for_key_in_B)。

这个公式离正确答案很近！但这个公式有一个明显的新问题。假设在你的整个相关性中，dataset_a只有一个模糊键映射到单个值，并且dataset_a也只有一个模糊键，它也只映射到单个值。假设从匹配这两个键得到的模糊分数是0.000001——一个极其糟糕的匹配。让我们将这些数字代入我们的公式，好吗！我们得到0.000001 / (0.000001 * 0.000001)，即1000000.0。一百万！这太疯狂了！我们把一个绝对糟糕的模糊匹配的分数吹捧到一个不合理的水平。显然，这也是不正确的。

这导致我们得到了真正有效的公式。这里的洞见是，相同的公式需要对精确键同样有效。如果你用这个公式计算每个fuzzy_score都是1（或0）的情况，它会产生与精确键公式相同的结果。所以，最终的技巧是我们可以在需要的地方乘以fuzzy_score，因为乘以1不会改变任何东西。这意味着得到的公式仍然与精确键评分公式一致。而有效的是我们乘以fuzzy_score三次的公式！

以下是用来计算模糊匹配得分的公式，简化后忽略权重和四舍五入

value_a = a value from dataset_a
value_b = a value from dataset_b
key_a = a fuzzy key in dataset_a that maps to value_a
key_b = a fuzzy key in dataset_b that maps to value_b
fuzzy_score = the result of key_a.compare(key_b)
cumulative_a = the cumulative score of all matches between key_a and every fuzzy key of the same type in dataset_b
cumulative_b = the cumulative score of all matches between key_b and every fuzzy key of the same type in dataset_a
score_ratio_a = fuzzy_score / cumulative_a
score_ratio_b = fuzzy_score / cumulative_b
unweighted_score = fuzzy_score * score_ratio_a * score_ratio_b

真正的技巧在于认识到score_ratio_a代表什么。实际上，它代表了此模糊匹配对于key_a的贡献与在dataset_a中所有成功匹配中key_a的所有模糊匹配的总和之间的比例。

为什么关联不使用Gale-Shapley算法

一个朋友问我，问题correlate解决的是否与稳定匹配问题同构

https://zh.wikipedia.org/wiki/稳定匹配问题

因为如果是这样，我就可以使用Gale-Shapley算法

https://zh.wikipedia.org/wiki/Gale%E2%80%93Shapley算法

我考虑这个问题很久了，我不认为问题 相关 解决可以完美映射到稳定匹配问题上。 相关 解决的是一个更简单、不同且更难的问题。

1. 更简单，
2. 不同，
3. 更难。

对于既适用于Gale-Shapley也适用于 相关 的输入，我断言这两个算法将返回相同的结果，但 相关 将更快。

（这不是我轻易提出的论断！Gale和Shapley都是杰出的数学家——他们每人独立获得了 冯·诺伊曼 奖！——Gale-Shapley算法既奇妙又优雅。只是 相关 可以采取Gale-Shapley无法采取的捷径，因为 相关 解决的是一个更简单的问题。）

在所有以下示例中，A、B和C是dataset_a中的值，而X、Y和Z是dataset_b中的值。表达式A: XY表示"A比Y更喜欢X"。表达式A:X=1.5表示"当匹配A和X时，他们的得分是1.5"。当我说到Gale-Shapley时，dataset_a代表"男性"，而dataset_b代表"女性"，这意味着A是男性而X是女性。当我们需要谈论匹配本身时，我们将它们称为P和Q。

它为什么更简单？

稳定匹配问题只需要一个局部排序，其中任何数据集中的任何值的偏好与任何其他值的排序是互斥的。但 相关 使用一个绝对的"分数"--一个数字--来计算这些偏好，而这个分数是对称的；如果A:X=1.5，那么X:A=1.5也是如此。

在相关的维基百科页面上

https://zh.wikipedia.org/wiki/稳定匹配格

我们找到了一个经典的复杂稳定匹配问题示例

A: YXZ
B: ZYX
C: XZY

X: BAC
Y: CBA
Z: ACB

Gale-Shapley能够轻松处理这种情况。相关 能吗？答案是...这个约束条件安排在 相关 中根本不可能发生，因为 相关 使用分数来建立其偏好，而分数是对称的。有九种可能的配对与这六个值。不可能为这九种配对中的每一个分配一个唯一的分数，使得每个值的偏好与这些约束相匹配。

（是的，我非常确定。我不仅自己解决了这个问题，我还编写了一个尝试所有可能组合的暴力程序。在362,880次尝试后，我宣布没有可能的解决方案。）

它有什么不同？

一个小差别：Gale-Shapley指定两个集合的大小必须相等；相关 允许两个集合的大小不同。但是将Gale-Shapley扩展以处理这一点并不是什么大问题。只需将算法扩展到说，如果两个数据集的大小不等，则在必要时交换数据集，使"男性"成为较大的群体。然后，如果你有一个未匹配的"男性"，他遍历所有"女性"并且没有人与他交换，他仍然未匹配。

第二件事：Gale-Shapley要求每个数据集中的每个值对其他数据集中的每个值都表达一个严格的有序偏好。但在 相关 中，两个匹配可以具有相同的分数。

考虑这个 相关 问题的表述

A:X=100
A:Y=1

B:X=100
B:Y=2

如最初声明的Gale-Shapley无法解决这个问题，因为X对A或B都没有偏好--它对两者都一样喜欢。扩展Gale-Shapley以处理这个问题并不难；在它对两个偏好相同的情况下，让它任意选择一个。例如，如果X对A和B同样偏好，对第一个询问的人说"也许"，然后让它为你决定你更喜欢A还是B。

它有什么更难？

这是真正的问题。

相关度使用数值分数来权衡每次匹配的优点，并试图最大化所有匹配的累积分数。Gale-Shapley的目标相对简单——任何稳定的匹配都是可接受的。可能存在多个稳定的匹配；Gale-Shapley认为它们都是同样好的。

在实践中，如果将原始的Gale-Shapley算法应用于包含匹配数值分数的输入数据集，它会返回累积分数最高的匹配集。我在思考这个问题时，无法提出它不会这样做的情况。问题在于数据集中有两个匹配具有相同的分数——原始的Gale-Shapley算法不允许这种情况。

确保在这种情况下相关度返回最高的累积分数，需要在“匹配锅炉”中添加复杂的递归步骤。我们可能需要对Gale-Shapley进行类似的修改，给它添加一个递归步骤。Gale-Shapley已经是O(n²)；我认为修改后的版本将是O(n² log n)。但是，像相关度一样，这种情况在现实数据中不太可能发生。无论如何，适用于所有相关度输入的修改版Gale-Shapley肯定比相关度现有或所需的花费要高。

将Gale-Shapley映射到相关度贪心算法

再次强调，相关度和Gale-Shapley的有效输入集并不完全相同，但有很多重叠。这两个算法都可以处理以下输入：

• 我们可以为男A和女X之间的每次匹配分配一个数值分数，
• 涉及任何特定男A的每次匹配都有一个独特的分数，
• 同样，对于每一位女X，
• 而且男性数量和女性数量完全相同。

我断言，对于这些相互可接受的输入，这两个算法会产生相同的结果。以下是一个非正式的手势证明。

首先，由于Gale-Shapley无法处理对两个匹配同等偏好的情况，我们只会考虑所有匹配都具有唯一分数的数据集。这使我们能够放弃匹配锅炉的“递归步骤”，所以我们只需要比较简单的“贪心算法”。（再次强调：这个“贪心算法”比Gale-Shapley便宜得多，但正如我将要展示的，它足以解决我们面临的简单问题域。）

因此，让我们在我们的数据集上运行Gale-Shapley。并且每次我们执行操作时，我们都会将其写入一个列表——我们写下“男A向女X提出请求”，以及她的回复是可能还是不。

注意这个列表中的两点

• 首先，操作的顺序在这个列表中很重要。如果你改变特定男人请求特定女人的顺序，那么随之而来的可能和不的回复模式也会改变。

• 其次，每位女人最后说的可能实际上是是。

所以，让我们从匹配列表中逆序迭代，并在我们看到任何特定女人回复可能的第一次，将该答案改为是。

接下来：观察我们可以交换任何两个相邻的操作——但有一个重要的前提。我们必须保持以下不变性：对于每一位女人X，对于在X说是之后发生的任何包含X的操作，X必须说不。

因此，如果有两个相邻的操作P和Q，其中P目前是第一个，我们想将它们交换，使Q是第一个，并且如果以下条件都成立

• 在P和Q中询问的是同一位女人X。
• 在Q中，女人X说可能或是。
• 在P中，女人X说可能。

那么我们可以在将 P 和 Q 交换的情况下，只有在将 P 中 X 的响应改为 否 时才成立。

现在我们可以重新排序所有的操作，让我们按分数对操作进行排序，分数最高的排在前面。我们称分数最高的操作为 P，并说它匹配了男人 A 和女人 X。

我们现在知道以下都是正确的

• X 是 A 的首选。这是因为 P 是得分最高的匹配。因此，A 将首先询问 X。
• A 也是 X 的首选，因为 P 是得分最高的匹配。因此，X 一定会说 是。

由于第一个操作 P 被保证是 是，这意味着涉及 A 或 X 的后续操作都必须是 否。

我们现在遍历列表以找到涉及男人 B 和女人 Y 的操作 Q。我们定义 Q 为第一个满足以下条件的操作

• Q != P，因此 Q 在我们按顺序排列的操作列表中在 P 之后，
• B != A，并且
• Y != X.

根据定义，Q 也必须是 是，因为 B 和 Y 现在是对方的首选，因为 A 和 X 已不可用于匹配。如果在 P 和 Q 之间有任何操作，这些操作涉及 A 或 X。因此，它们必须是 否。因此，Q 代表了 B 和 Y 剩余的最高偏好。

请注意，整个列表看起来像这样。每个 是 都是这对男女中他们第一次没有被与已经对其他人说过 是 的女人或男人（分别）配对的操作。

这个操作列表现在在很大程度上类似于“贪婪”算法执行的操作。它按分数对匹配进行排序，然后遍历排序后的列表。对于每个男人 A 和女人 X，如果 A 或 X 还没有被匹配，它就会匹配 A 和 X 并记住他们已经被匹配。

可能操作列表中会有一些小的变化；任何涉及任何男人或任何女人 在 他们被匹配为 是 之后的操作都是多余的。因此，你可以随意添加或删除它们，而不会影响结果。

版本历史

1.1

添加了一种新的排名方法！前两种是 AbsoluteRanking 和 RelativeRanking，这个新的第三种是 ReversedAbsoluteRanking。

1.0

没有代码更改。但 correlate 已经稳定并运行了一段时间……现在是时候将其标记为 1.0。

0.8.3

对 print_datasets() 进行了轻微的修复。 print_datasets() 按顺序打印出每个值的键。但这也意味着排序键，如果你有不同类型的键，尝试使用 < 或 > 比较它们可能会抛出 ValueError。因此，现在 print_datasets() 会按类型将键分开，并分别对每个键列表进行排序和打印。

数据集 API 允许你设置没有键映射到的值。（你可以调用 dataset.value() 并传递一个你从未传递给 set() 或 set_keys() 的值。） correlate() 以前只是断言每个值至少有一个键；现在它将抛出一个包含打印每个值的字符串的 ValueError。（如果有很多，这可能是不易读的！但宁可信其有，不可信其无。）

0.8.2

修复了 infer_mv。它的工作方式相同，但它打印出的注释现在得到了很大的改进。特别是，它有一个错误，它会报告每个匹配的相同分数——最低排名匹配的分数——而不是每个匹配的正确分数。

没有其他更改；correlate 算法与 0.8.1 版本相同。

0.8.1

已修复与Python 3.6的兼容性问题。我只需要移除一些地方使用的等于符号在f字符串中。

0.8

手动调优优化的结果：现在correlate版本0.8比版本0.7快了惊人的19.5%——比版本0.5快了27.3%！

统计数据已得到改进，包括一些有用的计时信息。这实际上展示了模糊键有多慢。

(要亲自查看，请运行python3 tests/ytjd.test.py -v，并使用相同的语料库比较最快和最慢的测试。在我的电脑上，没有使用模糊键的测试比使用模糊键的测试快了12倍。）

0.7

对精确和模糊键路径进行了谨慎的微优化，使correlate的速度提高了高达7.5%！

MatchBoiler的稳定性得到了进一步的提升。它现在应该始终

• 返回与matches中出现的顺序相同的results，并且
• 在两个或更多项产生相同的累积分数时，优先选择最后一个等效项。

0.6.1

修复了重大但罕见的错误：如果有多个组的“连接”匹配对象具有相同的分数，且长度大于1，则匹配锅炉只会保留最小的一个——其余的都被意外丢弃。（match_boiler_2_test()已添加到tests/regression_test.py以检查此问题。）

0.6

在“模糊煮沸”中实现了大幅的性能提升！对模糊匹配的巧妙排序，以及MatchBoiler稳定性（如“稳定排序”）的改进，允许使用未修改的锅炉处理模糊匹配。这使得可以移除FuzzyMatchBoiler和MatchBoiler.filter()回调机制。

MatchBoiler的轻微性能提升：在递归时，找到具有相同分数的最小连接匹配组，并且只递归检查这些组中的每个，而不是所有可能的具有相同分数的连接匹配。

已移除key_reuse_penalty_factor。在correlate的早期阶段，它不理解轮次；如果你将相同的键映射到相同的值两次，它只会记住一个映射，即具有最高权重的映射。后来我添加了轮次，但它们似乎没有增加多少信号。我认为重复的键没有意义。因此，我添加了key_reuse_penalty_factor。这让你可以降低它们提供的信号，以防它添加的噪声比实际有用的信号多。直到我意识到第0轮的key->value和第1轮的key->value在概念上是两个不同的键，我才真正理解相同的键映射到相同的值的重复映射应该如何工作。一旦轮次为评分公式维护了不同的keys / scores计数，不同轮次的重复键就变得非常有用。我现在认为key_reuse_penalty_factor是愚蠢的，且毫无用处，所以我已经移除了它。如果你认为key_reuse_penalty_factor有用，请与我联系并告诉我原因！或者，默默地将其预先乘入你的权重。

累积效应：模糊匹配煮沸速度提高高达30%，在大量使用模糊键的YTJD测试中提高高达5%。匹配煮沸也稍微快了一些。

0.5.1

错误修复版本。在原始版本中，如果一个匹配项在模糊键之间（具有正分数）没有匹配项，它将忽略其精确键的权重，并仅使用原始精确分数。

0.5

初始公开发布。