Meilleure façon de déterminer l'unicité et la répétition dans un fichier texte

Question

J'ai un fichier texte d'environ 20 millions de lignes. Chaque ligne a 25 caractères. J'estime qu'il y a probablement environ 200k-300k lignes uniques. Ce que je veux savoir, c'est exactement combien il y a de lignes uniques, et combien d'occurrences de chaque ligne il y a (je m'attends à ce que le résultat soit power-law-esque).

je pouvais faire ceci:

sort bigfile|uniq -c |sort -nr > uniqcounts 
wc -l uniqcounts 

mais qui est terriblement inefficace mémoire et sage temps.

Quelle est votre meilleure solution en ligne de commande pour résoudre ce problème?

Answer 1

J'ai tendance à pencher vers Perl lorsque j'ai des problèmes de traitement de texte comme celui-ci, d'autant plus que Perl est installé sur la plupart des systèmes Unix. (Vous pourriez probablement faire la même chose avec awk, ce qui est probablement un peu plus disponible.)

Quelque chose comme ça devrait faire l'affaire:

#!/usr/bin/perl 

while(<>) { 
    chomp; 
    $lines{$_}++; 
} 

print "Total unique lines: ", scalar(keys %lines), "\n"; 
foreach my $line (sort {$lines{$b} <=> $lines{$a}} keys %lines) { 
    printf "%6d %s\n", $lines{$line}, $line; 
} 

(Vous pouvez le faire comme une doublure, mais éclaté rend plus facile à lire.)

Cela nécessite la mémoire O (n) pour les clés de hachage, où n est le nombre de lignes uniques. L'efficacité d'exécution dépend de la recherche de hachage mais sera quelque part entre O (n) (si vous n'avez pas de collisions de hachage) et O (n * log n) (pour un arbre équilibré). Le tri final optionnel peut prendre O (n^2) dans le pire des cas et peut dominer le runtime si le nombre de lignes uniques est élevé.

Answer 2

Je ne suis pas sûr qu'il existe une meilleure solution que celle que vous avez affichée: O (n log (n) + n). La fineal "sort -nr" que vous mentionnez n'est pas strictement nécessaire étant donné l'énoncé du problème, mais rend la sortie plus facile à grok pour les humains.

Je serais très intéressé si quelqu'un pouvait trouver une solution plus rapide que celle-ci (en complexité). Bien sûr, écrire un programme spécial pour faire la même chose serait probablement plus rapide que d'utiliser tri et uniq.

Answer 3

Assurez-vous de le faire avant de tester votre solution sort et uniq:

export LC_ALL=C 

Ce serait bien si vous pouviez comparer et le temps de solution perl sage au moins.

Answer 4

Je suppose que le risque d'être considéré hors sujet et downvoted, mais je dois déclamer à ce sujet.

20 millions * 25 = 500000000 octets caractères (en supposant que vous ne voulez pas dire Unicode)

C'est à moins de 500 Mo de RAM. Ce n'est pas un nombre énorme pour un ordinateur moderne.

Ne vous plaignez pas de cette mémoire terriblement inefficace et du temps. La décision de stocker des données redondantes dans un fichier texte plat était inefficace et erronée.

Utilisez une base de données (sqlite par exemple) au lieu d'un fichier plat.

Utilisez une table comme

CREATE TABLE lines (line VARCHAR(25), occurences INTEGER) 

pour stocker des lignes uniques et leur apparition.

Si ce n'est pas votre application qui génère ce fichier texte, faites-en part aux développeurs!

Answer 5

Avec awk (utilisez nawk ou /usr/xpg4/bin/awk sur Solaris:

awk 'END { 
    for (k in _) 
    print k, _[k] 
    } 
{ _[$0]++ } 
' infile