0

我有一个 CSV 文件，其中包含不同行中的重复项目。

x1,y1
x2,y2
y1,x1
x3,y3

x1,y1包含和的两行y1,x1是匹配的，因为它们以不同的顺序包含相同的数据。

我需要您的帮助来找到一种算法来搜索 12MB 文件中的此类行。

4

5 回答 5

1

如果您可以在字段之间定义一些排序和相等关系，您可以存储一个规范化的表格并测试您的行是否相等。

例如，我们将对您的字段使用字符串比较，但在将它们小写之后。然后我们可以根据这个关系对部分进行排序，并通过嵌套哈希创建一个查找表：

use strict; use warnings;

my $cache; # A hash of hashes. Will be autovivified later.

while (<DATA>) {
  chomp;
  my @fields = split;

  # create the normalized representation by lowercasing and sorting the fields
  my @normalized_fields = sort map lc, @fields;

  # find or create the path in the lookup
  my $pointer = \$cache;
  $pointer = \${$pointer}->{$_} for @normalized_fields;

  # if this is an unknow value, make it known, and output the line
  unless (defined $$pointer) {
    $$pointer = 1; # set some defined value
    print "$_\n"; # emit the unique line
  }
}

__DATA__
X1 y1
X2 y2
Y1 x1
X3 y3

在此示例中，我使用标量1作为查找数据结构的值，但在更复杂的情况下，原始字段或行号可以存储在这里。出于示例的目的，我在这里使用了空格分隔的值，但您可以将 替换split为调用Text::CSV或其他内容。

这种散列方法具有亚线性空间复杂度和最坏情况线性空间复杂度。查找时间仅取决于记录中字段的数量（和大小），而不取决于记录的总数。

限制：所有记录必须具有相同数量的字段，否则一些较短的记录可能会被错误地视为“已看到”。为了规避这些问题，我们可以使用更复杂的节点：

  my $pointer = \$cache;
  $pointer = \$$pointer->[0]{$_} for @normalized_fields;

  unless (defined $$pointer->[1]) {
    $$pointer->[1] = 1; ...
  }

或为不存在的字段引入默认值（例如原始文件的分隔符）。这是一个带有 NUL 字符的示例：

 my $fields = 3;
 ...;
 die "record too long" if @fields > $fields;
 ...; # make normalized fields
 push @normalized_fields, ("\x00") x ($fields - @normalized_fields);
 ...; # do the lookup
于 2013-06-01T17:21:53.913 回答
1

很大程度上取决于找到重复行后您想了解的内容。这个程序使用一个简单的散列来列出那些等价的行的行号。

use strict;
use warnings;

my %data;

while (<DATA>) {
  chomp;
  my $key = join ',', sort map lc, split /,/;
  push @{$data{$key}}, $.;
}

foreach my $list (values %data) {
  next unless @$list > 1;
  print "Lines ", join(', ', @$list), " are equivalent\n";
}

__DATA__
x1,y1
x2,y2
y1,x1
x3,y3

输出

Lines 1, 3 are equivalent
于 2013-06-01T18:02:43.463 回答
0
  1. 制作两个哈希表A和B
  2. 一次一行地通过您的输入流式传输
  3. 对于第一行对xand y，使用一个作为键，另一个作为两个哈希表的值（例如，$A->{x} = y; $B->{y} = x;）
  4. 对于第二个和后续行对，测试第二个字段的值是否作为键存在，A或者B- 如果存在，则您有反向匹配 - 如果不存在，则重复步骤 3 中的添加过程以将其添加到哈希表
于 2013-06-01T17:23:16.653 回答
0

要在没有哈希表的情况下执行 amon 的答案版本，如果您的数据是数字，您可以：

  1. 逐行流过输入，按数字顺序对字段一和字段二进行排序
  2. sort在第一个和第二个字段上将结果通过管道传输到 UNIX
  3. 逐行流过排序的输出，检查当前行是否与前一行匹配（如果为真，则报告反向匹配）

与哈希表相比，这具有使用更少内存的优势，但可能需要更多时间来处理。

于 2013-06-01T17:31:35.010 回答
0

amon 已经提供了我会提供的答案，所以请享受这个糟糕的答案：

#! /usr/bin/perl
use common::sense;

my $re = qr/(?!)/;  # always fails

while (<DATA>) {
  warn "Found duplicate: $_" if $_ =~ $re;
  next unless /^(.*),(.*)$/;
  die "Unexpected input at line $.: $_" if "$1$2" =~ tr/,//;
  $re = qr/^\Q$2,$1\E$|$re/
}

__DATA__
x1,y1
x2,y2
y1,x1
x3,y3
于 2013-06-02T02:13:20.107 回答