Comment puis-je supprimer des lignes non uniques d'un gros fichier avec Perl?

Question

Suppression de données en double à l'aide de Perl appelée à l'intérieur via un fichier de commandes dans Windows Une fenêtre DOS dans Windows appelée via un fichier de commandes. Un fichier de commandes appelle le script Perl qui exécute les actions. J'ai le fichier batch. Le script de code dans lequel j'ai des données dupliquées est supprimé tant que le fichier de données n'est pas trop volumineux. Le problème qui nécessite une résolution concerne les fichiers de données plus volumineux (2 Go ou plus). Avec cette taille de fichier, une erreur de mémoire se produit lors du chargement du fichier complet dans un tableau pour la suppression des données en double. L'erreur de mémoire se produit dans le sous-programme à: -

@contents_of_the_file = <INFILE>; 

(Procédé complètement différent est acceptable tant qu'elle permet de résoudre ce problème, s'il vous plaît suggérer). Le sous-programme est: -

sub remove_duplicate_data_and_file 
{ 
open(INFILE,"<" . $output_working_directory . $output_working_filename) or dienice ("Can't open $output_working_filename : INFILE :$!"); 
    if ($test ne "YES") 
    { 
    flock(INFILE,1); 
    } 
    @contents_of_the_file = <INFILE>; 
    if ($test ne "YES") 
    { 
    flock(INFILE,8); 
    } 
close (INFILE); 
### TEST print "$#contents_of_the_file\n\n"; 
@unique_contents_of_the_file= grep(!$unique_contents_of_the_file{$_}++, @contents_of_the_file); 

open(OUTFILE,">" . $output_restore_split_filename) or dienice ("Can't open $output_restore_split_filename : OUTFILE :$!"); 
if ($test ne "YES") 
    { 
    flock(OUTFILE,1); 
    } 
for($element_number=0;$element_number<=$#unique_contents_of_the_file;$element_number++) 
    { 
    print OUTFILE "$unique_contents_of_the_file[$element_number]\n"; 
    } 
if ($test ne "YES") 
    { 
    flock(OUTFILE,8); 
    } 
} 

Answer 1

Vous stockez inutilement une copie complète du fichier original dans @contents_of_the_file et - si la quantité de duplication est faible par rapport à la taille du fichier - près de deux autres copies complètes en %unique_contents_of_the_file et @unique_contents_of_the_file. Comme noté ire_and_curses, vous pouvez réduire les besoins de stockage en effectuant deux passages sur les données: (1) analyser le fichier, en stockant des informations sur les numéros de ligne des lignes non dupliquées; et (2) traiter à nouveau le fichier pour écrire des non-dups ​​dans le fichier de sortie.

Voici une illustration. Je ne sais pas si j'ai choisi le meilleur module pour la fonction de hachage (Digest::MD5); peut-être que d'autres commenteront cela.Notez également le formulaire à 3 arguments de open() que vous devriez utiliser.

use strict; 
use warnings; 

use Digest::MD5 qw(md5); 

my (%seen, %keep_line_nums); 
my $in_file = 'data.dat'; 
my $out_file = 'data_no_dups.dat'; 

open (my $in_handle, '<', $in_file) or die $!; 
open (my $out_handle, '>', $out_file) or die $!; 

while (defined(my $line = <$in_handle>)){ 
    my $hashed_line = md5($line); 
    $keep_line_nums{$.} = 1 unless $seen{$hashed_line}; 
    $seen{$hashed_line} = 1; 
} 

seek $in_handle, 0, 0; 
$. = 0; 
while (defined(my $line = <$in_handle>)){ 
    print $out_handle $line if $keep_line_nums{$.}; 
}  

close $in_handle; 
close $out_handle; 

Answer 2

Perl fait des choses héroïques avec de gros fichiers, mais 2 Go peut être une limitation de DOS/Windows.

De combien de RAM disposez-vous?

Si votre système d'exploitation ne se plaint pas, il peut être préférable de lire le fichier une ligne à la fois et d'écrire immédiatement en sortie.

Je pense à quelque chose en utilisant l'opérateur de diamant < > mais je suis réticent à suggérer du code parce que dans les occasions où j'ai posté du code, j'ai offensé un gourou Perl sur SO.

Je préfère ne pas prendre le risque. J'espère que la cavalerie Perl arrivera bientôt.

En attendant, here's un lien.

Answer 3

Vous devriez être capable de le faire efficacement en utilisant le hachage. Vous n'avez pas besoin de stocker les données à partir des lignes, identifiez simplement celles qui sont les mêmes. Donc ...

• Ne pas slurp - Lire une ligne à la fois.
• Hachez la ligne.
• Stockez la représentation de ligne hachée en tant que clé dans un hachage Perl de listes. Stockez le numéro de ligne comme première valeur de la liste.
• Si la clé existe déjà, ajoutez le numéro de ligne en double à la liste correspondant à cette valeur.

A la fin de ce processus, vous aurez une structure de données identifiant toutes les lignes dupliquées. Vous pouvez ensuite effectuer un second passage dans le fichier pour supprimer ces doublons.

Answer 4

Dans la "méthode complètement différente" catégorie, si vous avez des commandes Unix (par exemple Cygwin):

cat infile | sort | uniq > outfile 

Cela devrait travailler - pas besoin de Perl du tout - qui peut, ou ne peut pas, résoudre votre problème de mémoire. Cependant, vous perdrez la commande de l'infile (comme le fichier sortant sera maintenant trié).

EDIT: Une solution alternative qui est mieux en mesure de traiter des fichiers volumineux peuvent être en utilisant l'algorithme suivant:

1. ligne par ligne Lire INFILE
2. Hash chaque ligne à un petit hachage (par exemple un hachage # mod 10)
3. Append chaque ligne dans un fichier unique au numéro de hachage (par exemple tmp-1 à tmp-10)
4. Fermer INFILE
5. Ouvrir et trier chaque tmp- # dans un nouveau fichier triétmp- #
6. Mergesort triétmp- [1-10] (c.-à-d. ouvrez tous les 10 fichiers et lisez-les simultanément), en ignorant les doublons et en écrivant chaque itération dans le fichier de sortie final

Ce sera plus sûr, pour les fichiers de très grande taille, que de faire du slurping.

Pièces 2 & 3 pourraient être modifiés à un aléatoire # au lieu d'un numéro de hachage mod 10.

est ici un script BigSort qui peut aider (bien que je ne l'ai pas testé):

# BigSort 
# 
# sort big file 
# 
# $1 input file 
# $2 output file 
# 
# equ sort -t";" -k 1,1 $1 > $2 

BigSort() 
{ 
if [ -s $1 ]; then 
    rm $1.split.* > /dev/null 2>&1 
    split -l 2500 -a 5 $1 $1.split. 
    rm $1.sort > /dev/null 2>&1 
    touch $1.sort1 
    for FILE in `ls $1.split.*` 
    do 
    echo "sort $FILE" 
    sort -t";" -k 1,1 $FILE > $FILE.sort 
    sort -m -t";" -k 1,1 $1.sort1 $FILE.sort > $1.sort2 
    mv $1.sort2 $1.sort1 
    done 
    mv $1.sort1 $2 
    rm $1.split.* > /dev/null 2>&1 
else 
    # work for empty file ! 
    cp $1 $2 
fi 
} 

Answer 5

Eh bien, vous pouvez utiliser le mode de remplacement en ligne de la ligne de commande perl.

perl -i~ -ne 'print unless $seen{$_}++' uberbigfilename 

Answer 6

Voici une solution qui fonctionne quelle que soit la taille du fichier. Mais il n'utilise pas la RAM exclusivement, donc c'est plus lent qu'une solution basée sur la RAM. Vous pouvez également spécifier la quantité de RAM que vous voulez que cette chose utilise.

La solution utilise un fichier temporaire que le programme traite comme une base de données avec SQLite.

#!/usr/bin/perl 

use DBI; 
use Digest::SHA 'sha1_base64'; 
use Modern::Perl; 

my $input= shift; 
my $temp= 'unique.tmp'; 
my $cache_size_in_mb= 100; 
unlink $temp if -f $temp; 
my $cx= DBI->connect("dbi:SQLite:dbname=$temp"); 
$cx->do("PRAGMA cache_size = " . $cache_size_in_mb * 1000); 
$cx->do("create table x (id varchar(86) primary key, line int unique)"); 
my $find= $cx->prepare("select line from x where id = ?"); 
my $list= $cx->prepare("select line from x order by line"); 
my $insert= $cx->prepare("insert into x (id, line) values(?, ?)"); 
open(FILE, $input) or die $!; 
my ($line_number, $next_line_number, $line, $sha)= 1; 
while($line= <FILE>) { 
    $line=~ s/\s+$//s; 
    $sha= sha1_base64($line); 
    unless($cx->selectrow_array($find, undef, $sha)) { 
    $insert->execute($sha, $line_number)} 
    $line_number++; 
} 
seek FILE, 0, 0; 
$list->execute; 
$line_number= 1; 
$next_line_number= $list->fetchrow_array; 
while($line= <FILE>) { 
    $line=~ s/\s+$//s; 
    if($next_line_number == $line_number) { 
    say $line; 
    $next_line_number= $list->fetchrow_array; 
    last unless $next_line_number; 
    } 
    $line_number++; 
} 
close FILE;