Jak usunąć zduplikowane linie w pliku tekstowym?

Mój ogromny plik tekstowy (do 2 GiB) zawiera około 100 dokładnych duplikatów każdego wiersza w nim (w moim przypadku jest to bezużyteczne, ponieważ jest to tabela danych podobna do CSV).

To, czego potrzebuję, to usunięcie wszystkich powtórzeń, podczas gdy (najlepiej, ale można to poświęcić w celu znacznego zwiększenia wydajności) przy zachowaniu oryginalnej kolejności sekwencji. W rezultacie każda linia ma być unikalna. Jeśli było 100 równych wierszy (zwykle duplikaty są rozłożone w pliku i nie będą sąsiadami), pozostanie tylko jeden taki rodzaj.

Napisałem program w Scali (rozważ to Java, jeśli nie wiesz o Scali), aby to zaimplementować. Ale może są szybsze natywne narzędzia napisane w C, które mogą to zrobić szybciej?

AKTUALIZACJA: awk '!seen[$0]++' filenamerozwiązanie wydawało się działać dobrze dla mnie, dopóki pliki były w pobliżu 2 GiB lub mniejszych, ale teraz, gdy mam wyczyścić plik 8 GiB, to już nie działa. Wydaje się, że zabiera nieskończoność na komputerze Mac z 4 GiB RAM i 64-bitowym Windows 7 PC z 4 GiB RAM i 6 GiB swap po prostu kończy się pamięć. I nie czuję entuzjazmu, próbując tego na Linuksie z 4 GiB RAM biorąc pod uwagę to doświadczenie.

awkRozwiązanie widoczne na #bash (Freenode):

awk '!seen[$0]++' filename

Istnieje prosta (co nie jest oczywiste) metoda wykorzystująca standardowe narzędzia, które nie wymagają dużej pamięci poza uruchomieniem sort, która w większości implementacji ma określone optymalizacje dla dużych plików (dobry algorytm sortowania zewnętrznego). Zaletą tej metody jest to, że zapętla ona tylko wszystkie linie wewnątrz narzędzi specjalnego przeznaczenia, nigdy wewnątrz interpretowanych języków.

<input nl -b a -s : |           # number the lines
sort -t : -k 2 -u |             # sort and uniquify ignoring the line numbers
sort -t : -k 1n |               # sort according to the line numbers
cut -d : -f 2- >output          # remove the line numbers

Jeśli wszystkie wiersze zaczynają się od spacji, możesz zrezygnować z niektórych opcji:

<input nl | sort -k 2 -u | sort -k 1n | cut -f 2- >output

W przypadku dużej ilości duplikacji metoda, która wymaga tylko przechowywania pojedynczej kopii każdej linii w pamięci, działa lepiej. Po pewnym nakładzie interpretacyjnym istnieje bardzo zwięzły skrypt awk (już opublikowany przez enzotib ):

<input awk '!seen[$0]++'

Mniej zwięźle: !seen[$0] {print} {seen[$0] += 1}tzn. Wydrukuj bieżącą linię, jeśli jeszcze nie była widoczna, następnie zwiększ seenlicznik dla tej linii (niezainicjowane zmienne lub elementy tablicy mają wartość liczbową 0).

W przypadku długich linii można zaoszczędzić pamięć, przechowując tylko niepodlegającą fałszowaniu sumę kontrolną (np. Streszczenie kryptograficzne) każdej linii. Na przykład, używając SHA-1, potrzebujesz tylko 20 bajtów plus stały narzut na linię. Ale przetwarzanie danych jest raczej powolne; ta metoda wygra tylko wtedy, gdy masz szybki procesor (zwłaszcza taki ze sprzętowym akceleratorem do obliczania skrótów) i nie ma dużo pamięci w stosunku do wielkości pliku i wystarczająco długich linii. Żadne podstawowe narzędzie nie pozwala obliczyć sumy kontrolnej dla każdej linii; będziesz musiał ponieść koszty interpretacji Perla / Pythona / Ruby /… lub napisać dedykowany skompilowany program.

<input perl -MDigest::MD5 -ne '$seen{Digest::MD5::md5($_)}++ or print' >output

sort -u big-csv-file.csv > duplicates-removed.csv

Zauważ, że plik wyjściowy zostanie posortowany.

Zakładając, że możesz sobie pozwolić na zachowanie w pamięci nawet zduplikowanego pliku (jeśli twoje dane są rzeczywiście zduplikowane 100-krotnie, powinno to wynosić około 20MiB + narzut), możesz to zrobić bardzo łatwo za pomocą Perla.

$ perl -ne 'print unless $dup{$_}++;' input_file > output_file

To także zachowuje porządek.

Jeśli chcesz, możesz wyodrębnić liczbę wystąpień każdej linii z %dupskrótu, jako dodatkowy bonus.

Jeśli wolisz awk, to też powinno to zrobić (ta sama logika co wersja perla, to samo porządkowanie, te same dane zebrane w dupzmiennej):

$ awk '{if (++dup[$0] == 1) print $0;}' input_file > output_file

Ponieważ żadna inna odpowiedź nie zapewnia wsparcia w miejscu, oto jedna z nich:

gawk -i inplace '!a[$0]++' file

Możesz użyć uniq http://www.computerhope.com/unix/uuniq.htm

uniq zgłasza lub odfiltrowuje powtarzające się wiersze w pliku.

Wkładki Python One:

python -c "import sys; lines = sys.stdin.readlines(); print ''.join(sorted(set(lines)))" < InputFile

Żadna z odpowiedzi tutaj nie działała na moim komputerze Mac, więc napisałem prosty skrypt Pythona, który działa dla mnie. Ignoruję początkowe / końcowe białe znaki, a także nie obchodzi mnie zużycie pamięci.

import sys

inputfile = sys.argv[1]
outputfile = sys.argv[2]

with open(inputfile) as f:
    content = f.readlines()

content = [x.strip() for x in content]

my_list = list(set(content))

with open(outputfile, 'w') as output:
    for item in my_list:
        output.write("%s\n" % item)

Zapisz powyższe w pliku Unique.py i uruchom w ten sposób:

python unique.py inputfile.txt outputfile.txt

W przypadku bash 4 można zastosować rozwiązanie typu pure bash, które wykorzystuje tablice asocjacyjne . Oto przykład

unset llist; declare -A llist;
while read -r line; do
if [[ ${llist[$line]} ]]; then
  continue
else 
  printf '%s\n' "$line"
  llist[$line]="x"
fi
done < file.txt