ed_join

这是 Xiao 等人于 2008 年提出的 Ed-join 算法在 Rust 编程语言中的实现。与原始论文相比，有两个主要的差异

1. 在这个实现中，我使用了并行迭代器而不是使用单个线程来匹配字符串。
2. 在实际匹配之前，我创建了一个倒排索引，而论文中是在线生成倒排索引。

在一个配备 Intel i7-8700k 和 32 GB RAM 的系统上，程序在一个包含 100,000 行的文件上进行了自我匹配，耗时 35 分钟，tau = 5。请注意，此算法在匹配长记录方面表现出色，而上述测试文件中的行相当短。

还有一个更快的算法称为 PassJoin，我将在未来实现它。它分别对短字符串和长字符串使用不同的启发式算法。在相同的上述测试文件上的性能比上述快 30 多倍。因此，这个 crate 作为一个 Ed-join 算法的示例实现，而不是现实场景的解决方案。

尽管如此，当输入文件不是太大，或者当阈值 tau 不太大时，此算法的性能仍然相当快。例如，对于 100,000 行的测试文件，当 tau = 5 时，有超过 878,000 个匹配的记录对。但是当 tau = 2 时，只有 136,000 个匹配对，并且匹配只需大约 3 分钟。

安装

要将此 crate 作为依赖项添加，请将其添加到您的 Cargo.toml 或执行 cargo add ed_join。

此 crate 还附带一个二进制文件 ed-join，可以使用 cargo install ed_join --features cli 安装。

参考

• 肖，川，王伟，林学民。 "Ed-join：具有编辑距离约束的相似性连接的有效算法。" VLDB Endowment 1.1（2008）：933-944。

许可证：Apache-2.0 AND MIT