For filtering duplicates, you need only to remember what elements you already have written to the file. You don't need Tie::File, just a loop that uses a hash to remember what lines with what keys have already been written to the file. If memory is still scarce, you can tie that hash to disk:

open my $in, '<', $infile
    or die "Couldn't open '$infile': $!";
open my $out, '>', $outfile
    or die "Couldn't create '$outfile': $!";

my %seen;
while (<$in>) {
    my $key = $in; # change this to whatever key generation you need
    if (! $seen{ $key }++) {
        print $out $in;
    };
};
[download]

Thanks, this is starting to look a lot simpler than I imagined.

So I could just do


$in =~ /^([^\t]*\t[^\t]*)/;
$key = $1;
[download]

and that would take care of doing the filtering based on the first two columns instead of the whole line, right?
But the %seen hash would hold the first two columns of all the unique lines in the file, which could be about 1GB. I'm not sure what you mean by tying the hash to disk, could you elaborate? Although I guess I'll have to test how much memory this takes up in reality and whether or not it causes a problem.

On a different note, I'm having a bit of trouble comprehending the code. First of all, I don't get why you need a hash, not just an array. What's the use of the key-value pairs here? Or is it just that it's easier to see if a certain element is present in a hash than doing a similar lookup in an array?
And what exactly does the ++ in if (! $seen{ $key }++) do? Add a new record to the %seen hash?

See tie and DB_File. A tie'd hash simply moves the storage of the hash onto disk, at the (rather huge) cost of access speed.

A hash is a data structure optimized for fast lookup by a key value. An array can only look up data fast by its index, and the array assumes that all index values are sequential. You haven't told us whether that's the case, so I'm using a hash.

For the "postfix increment" operator ("++"), see perlop. It is basically $seen{ $key } = $seen{ $key } + 1, except shorter.

If the data's tab delimited, you could split your incoming line on tabs

my @w = split(/\t/,$_);
[download]

and then build a key out of the first two fields and use that as your hash key

if ( !$seen{$w[0].$w[1]}++ ) {
[download]

Alex / talexb / Toronto

"Groklaw is the open-source mentality applied to legal research" ~ Linus Torvalds

Now, as far as I can tell, the best way to do things like this in large files is Tie::File, which loads files into a pseudo-array and helps do operations like this without loading the entire file to memory.

The basic means of reading from a file (read, readline) do not read the entire file into memory, so that aspect of Tie::File is not special. What you are doing by using Tie::File is wasting time and memory for features you don't even need.

I'm not sure if the foreach my $list( sort( @lists ) ){ line means that I will get alphabetically sorted output at the end, but I suspect it does, which wouldn't be ideal.

sort @tied would cause all of the file to be loaded into memory so it can be passed to sort. Thankfully, you're not passing the tied array there, but that probably means you are doing remove_duplicate_from_array(@tied).

remove_duplicate_from_array(@tied) would cause all of the file to be loaded into memory so it can be placed in @_. Then the first thing you do in remove_duplicate_from_array is to create a copy of @_

ouch.

The basic means of reading from a file (read, readline) do not read the entire file into memory, so that aspect of Tie::File is not special.

Well, I know that, and while (<FILE>) is what I use most of the time. I just thought that wouldn't work for this purpose without sorting the file alphabetically first. Corion's solution cleared that up, so the Tie::File idea went out the window after the first post in the thread.
Just for the record, here's the code I ended up with, including some reporting:


open (ALIGNED, "<:encoding(UTF-8)", "${filename}.txt") or die "Can't o
+pen aligned file for reading: $!";
open (ALIGNED_MOD, ">:encoding(UTF-8)", "${filename}_mod.txt") or die 
+"Can't open file for writing: $!";

if ($delete_dupes eq "y") {

    my %seen;        # hash that contains uique records (hash lookups 
+are faster than array lookups)
    my $key;        # key to be put in hash
    while (<ALIGNED>) {
        /^([^\t]*\t[^\t]*)/;    # only watch first two fields
        chomp ($key = $1);        # only watch first two fields
        print ALIGNED_MOD $_ if (! $seen{ $key }++); # add to hash, an
+d if new, print to file
    }

    my $unfiltered_number = $.;
    my $filtered_number = keys %seen;
    print "\n\n-------------------------------------------------";
    print "\n\nSegment numbers before and after filtering out dupes: $
+unfiltered_number -> $filtered_number\n";
    print LOG "\nFiltered out dupes: $unfiltered_number -> $filtered_n
+umber";

    undef %seen; # free up memory

    close ALIGNED;
    close ALIGNED_MOD;
    rename ("${filename}_mod.txt", "${filename}.txt") or die "Can't re
+name file: $!";
}
[download]

I just thought that wouldn't work for this purpose without sorting the file alphabetically first.

That makes no sense. If you can't do it by reading the file a line at a time using <>, what makes you think you can do it by reading the file a line at a time using Tie::File. Conversely, if you can do it by reading a line at a time using Tie::File, you can do it by reading a line at a time using <>.

The following should be fast, it allows arbitrary large files, and it preserves order:

perl -ne'print "$.\t$_"' input.txt \
   | sort -k 2 \
   | uniq -f 1 \
   | sort \
   | cut -f 2- \
   > output.txt
[download]

• Prefix each line with its original line number,
• sort (ignoring the prefixed line number) to group duplicates,
• remove duplicates (ignoring the prefixed line number),
• restore the original order, and finally
• remove the prefixed line number.

I also found array-based dupe stripping solutions.....

C:\Documents and Settings\franciscor>perl -
use List::MoreUtils qw(uniq);
my @list = qw(3 1 2 1 3 4 1 5 1 6 8 1 2 1 2 7 1 1 2 3 4 6 1);
my @unique = uniq(@list);
print "@unique";
__END__
3 1 2 4 5 6 8 7
[download]

Thanks, that's pretty elegant, but it filters on the whole record, not the first two fields as I need it to, so I'll stick with the solution suggested by Corion.

Besides the using techniques already mentioned I'd reduce the data by extracting e. g. the md4 checksum of the relevant columns. Byte offset and length of each line also go into this intermediate file.

The intermediate file gets the opposite treatment to list all but one of the duplicates in a group. The extracted information is used to overwrite duplicate lines in the original 1 GB file e. g. with spaces using seek() for positioning. This is the computer analogon to crossing lines out on paper with a ruler and pen.

A trivial pipe filter is then applied to skip the overwritten lines when feeding the result to the next application.

The command line approach is also worth checking out on GNU tools:  sort -u -t "\t" -k1,2 -S 100M -o out.file

Thanks, that sounds convincing.
It's way over my head, though, and I don't think the advantages are worth the effort here.
I need this to work on very large files "just in case", with 1GB being on the extreme upper end of what I expect it'll need to handle. Most of the time, it will be crunching much smaller files with well under 50,000 records.