runiq

该项目提供了一种高效的方法（在时间和空间上）从文本输入中过滤重复条目（行）。该项目是从 neek 发展而来，但优化了速度和内存。根据您的数据和您希望在速度和内存使用之间进行的权衡，支持几种过滤选项。有关更详细的说明，请参阅相关的 博客文章。

安装

Runiq 将通过 Crates.io 提供，因此可以直接从那里安装。您可以使用 Runiq 作为命令行工具或直接通过程序化 API 使用它。

如果您希望将 Runiq 作为命令行工具安装，您可以在终端中使用简单的单行命令进行安装

# install as a binary
$ cargo install runiq

如果您希望将其用作库，您可以将其添加到您的 Cargo.toml 中，作为您应用程序的依赖项

[dependencies]
runiq = { version = "2.0", default-features = false }

您应该禁用默认功能，因为它包含一些依赖项，这些依赖项是 CLI 用例所必需的。当禁用这些功能时，这些依赖项不会包含在您的应用程序中。

示例

以下是使用 Runiq CLI 从输入文本中过滤重复内容的几个示例。

$ cat << EOF >> input.txt
this is a unique line
this is a duplicate line
this is another unique line
this is a duplicate line
this is a duplicate line
EOF

$ cat input.txt
this is a unique line
this is a duplicate line
this is another unique line
this is a duplicate line
this is a duplicate line

$ runiq input.txt
this is a unique line
this is a duplicate line
this is another unique line

有关程序化 API 的示例，请参阅 示例。

过滤器

Runiq 包含几个“过滤器”，这些过滤器控制了唯一性的验证方式。每个过滤器都有不同的用例，并且以不同的方式表现出色。

• 快速
  • 快速 过滤器的工作方式与 naive 过滤器相同，只是预先对值进行了哈希处理。
  • 这比 naive 的内存开销要低得多，并且吞吐量相当。
  • 根据您的输入长度，吞吐量实际上可能比 naive 更快。
• 简单
  • 《naive》过滤器使用基本的《Set》实现来判定唯一性。
  • 在保证准确性的同时，提供了相当好的吞吐量。
  • 由于所有输入都被存储，内存需求与输入大小呈线性关系。
• 排序
  • 《sorted》过滤器与标准的《uniq》工具作用类似，只检测连续重复项。
  • 资源消耗极低，内存开销非常小。
  • 显然需要输入值是有序的。
• 紧凑
  • 《compact》过滤器（嘿）使用缩放Bloom过滤器来判定唯一性。
  • 由于结构小巧，性能非常快，内存开销最小。
  • 不再保证完美准确；可能会有极少数的误报。
  • 最适合用于文件统计，尽管对于数百万条记录来说，仍然接近完美。
  • 下面比较中提供了关于此过滤器准确性的注意事项。

比较

为了获取《runiq》与其他过滤唯一值方法的一些粗略比较，我们可以使用一些样本数据。这些数据是通过Jen使用相应目录中提供的模板生成的。您可以根据自己的用例创建模板以获得更好的比较。

首先，我们将使用basic模板生成一个包含2500万个JSON文档的样本数据集。在这个规模下，模板将导致大约20%的重复率（在文件中随机分布）。请注意，对于较长的输入，您可以调整模板内部的《rp》值来引起字段的重复。

$ jen templates/basic.tera -l 25000000 > 25000000.jsonl

File Size:     1,913,658,811 (~1.9 GB)
Total Count:      25,000,000
Unique Count:     19,832,571
Dup Offset:        5,167,429
Dup Rate:             20.67%

然后，我们可以将这些样本数据集通过《runiq》的各种过滤器以及一些其他工具来运行，以评估我们的表现。这些数字不是用来竞争的。它们只是我在测试改进时的一个参考点。其他工具可能更适合您的数据形状。

为了进行另一次比较，我们将使用1000万个JSON文档的样本重复这些测试（是第一次测试的4倍）。在这种情况下，重复率将上升到大约55%，使用相同的模板

$ jen templates/basic.tera -l 100000000 > 100000000.jsonl

File Size:     7,654,658,706 (~7.7 GB)
Total Count:     100,000,000
Unique Count:     44,305,712
Dup Offset:       55,694,288
Dup Rate:             55.69%

所有这些数字都是在工具输出写入/dev/null的情况下得到的。其中一些工具（包括《runiq》）有标志来计数/报告而不是打印输出；这些用例将始终比上面的数字快得多。

还值得注意的是，在上述情况下，compact 过滤器给出的精度；在我的两个测试集中，结果与其他过滤器类型的结果相同，表明 compact 过滤器通常对相当大量的输入相当准确（尽管并非总是如此）。