3.3　实际应用

在给定的数据存储库中高效、准确地查找数据的能力对许多现实生活中的应用至关重要。根据你所选择的查找算法，你可能还需要先对数据进行排序。恰当地排序和选择查找算法将取决于数据的类型和规模以及你要求解的问题的性质。

让我们尝试使用本章介绍的算法来解决某国移民部门将一个新的申请人与其历史记录进行匹配的问题。当有人申请签证进入该国时，系统会尝试将申请人与现有的历史记录进行匹配。如果找到至少一个匹配项，则系统会进一步计算此人过去被批准或被拒绝的次数。另一方面，如果没有找到匹配的记录，系统会将申请人归类为新的申请人，并给其发一个新的识别码。在历史数据中查找、定位和识别一个人的能力对系统至关重要。这一信息很重要，因为如果某人在过去申请过，并且知道申请被拒绝了，那么这可能会对此人当前的申请产生负面影响。同样，如果某人的申请在过去被批准过，则该批准可能会增加此人当前申请获得批准的机会。通常情况下，历史数据库将有数百万行，因此我们需要一个精心设计的解决方案来匹配历史数据库中的新申请人。

假设数据库中的历史表如下所示：

在此表中，第一列Personal ID与历史数据库中每个唯一的申请人相关联。如果历史数据库中有3000万个唯一的申请人，那么将有3000万个唯一的Personal ID。每个Personal ID都在历史数据库系统中标识一个申请者。

第二列是Application ID，每个Application ID都标识了系统中唯一的申请。一个人可能在过去申请过不止一次，因此，这意味着在历史数据库中我们所拥有的不同的Application ID会比Personal ID多。如上表所示，John Doe只有一个Personal ID，却有两个Application ID。

上表只显示了历史数据集的一个样本。假设历史数据集有近100万行，其中包含了过去10年的申请人记录。新的申请人以平均每分钟约2个申请人的速度不断到来。对于每个申请人，我们需要完成以下工作：

• 为申请人发放新的Application ID。
• 查看历史数据库中是否有匹配的申请人。
• 如果找到了匹配的申请人，则使用历史数据库中找到的该申请人的Personal ID。我们还需要确定历史数据库中已批准或拒绝该申请人的次数。
• 如果没有找到匹配的申请人，那么我们需要为这个人发放新的Personal ID。

假设一个申请人带着以下凭证来到这里：

• First name: John
• Surname: Doe
• DOB: 2000-09-19

现在，我们如何设计一个查找成本低的高效应用呢？

在数据库中搜索新的申请人的一种策略可以设计如下：

• 按照DOB（出生日期）对历史数据库进行排序。
• 每次有申请人到达时，向申请人发放新的申请ID。
• 取出所有符合该出生日期的记录，这将是主要的查找过程。
• 在匹配的记录中，使用名字（First name）和姓氏（Surname）进行二次查找。
• 如果找到匹配的申请人，则用Personal ID来指代该申请人，计算该申请人被批准和拒绝的次数。
• 如果没有找到匹配项，则向该申请人发放新的Personal ID。

我们尝试选择合适的算法对历史数据库进行排序。我们可以放心地排除冒泡排序，因为数据量很大。希尔排序有更好的表现，但前提是列表已经部分排好序。因此，归并排序可能是对历史数据库进行排序的最佳选择。

当一个申请人到来时，我们需要在历史数据库中定位并查找这个人。由于数据已经进行了排序，因此可以使用插值查找或二分查找。由于是按照DOB（出生日期）进行排序的，申请人很可能会均匀分布，所以我们可以放心地使用插值查找。

我们先基于DOB（出生日期）进行查找，返回一组具有相同出生日期的申请人。现在，需要在具有相同出生日期的一小部分人中找到所需的人。由于我们已经成功地将数据缩小为一个小的子集，因此可以使用任何查找算法（包括线性查找）来查找申请人。请注意，我们在这里稍微简化了二次查找问题。如果找到多个匹配项，我们还需要通过汇总查找结果来计算被批准和拒绝的总数。

在现实世界中，由于名字和姓氏的拼写可能略有不同，因此在二次查找中需要使用某种模糊搜索算法来识别每个人。查找中可能需要使用某种距离算法来实现模糊查找，比如相似度超过规定阈值的数据点将被认为是同一个人。