Usunąć zduplikowane linie parami?

16

Dzisiaj spotkałem się z tym przypadkiem użycia. Wydaje się prosta na pierwszy rzut oka, ale błahy wokół z sort, uniq, sedi awkujawnił, że to wcale trywialne.

Jak mogę usunąć wszystkie pary zduplikowanych linii? Innymi słowy, jeśli istnieje parzysta liczba duplikatów danego wiersza, usuń je wszystkie; jeśli jest nieparzysta liczba zduplikowanych linii, usuń wszystkie oprócz jednej. (Można założyć posortowane dane wejściowe.)

Preferowane jest czyste i eleganckie rozwiązanie.

Przykładowe dane wejściowe:

a
a
a
b
b
c
c
c
c
d
d
d
d
d
e

Przykładowe dane wyjściowe:

a
d
e
Dzika karta
źródło

Odpowiedzi:

6

sedOdpowiedź wypracowałem niedługo po tym, jak opublikowałem to pytanie; jak dotąd nikt inny nie korzystał sed:

sed '$!N;/^\(.*\)\n\1$/d;P;D'

Trochę zabawy z bardziej ogólnym problemem (co z usuwaniem linii w zestawach trzech? Lub czterech lub pięciu?) Zapewniło następujące rozszerzalne rozwiązanie:

sed -e ':top' -e '$!{/\n/!{N;b top' -e '};};/^\(.*\)\n\1$/d;P;D' temp

Rozszerzony, aby usunąć trzykrotnie linii:

sed -e ':top' -e '$!{/\n.*\n/!{N;b top' -e '};};/^\(.*\)\n\1\n\1$/d;P;D' temp

Lub usunąć quady z linii:

sed -e ':top' -e '$!{/\n.*\n.*\n/!{N;b top' -e '};};/^\(.*\)\n\1\n\1\n\1$/d;P;D' temp

sed ma dodatkową przewagę nad większością innych opcji, a mianowicie jego zdolność do prawdziwego działania w strumieniu, przy czym nie potrzeba więcej pamięci niż rzeczywista liczba wierszy do sprawdzenia pod kątem duplikatów.


Jak zauważył cuonglm w komentarzach , ustawienie języka na C jest konieczne, aby uniknąć błędów w prawidłowym usuwaniu wierszy zawierających znaki wielobajtowe. Tak więc powyższe polecenia stają się:

LC_ALL=C sed '$!N;/^\(.*\)\n\1$/d;P;D' temp
LC_ALL=C sed -e ':top' -e '$!{/\n/!{N;b top' -e '};};/^\(.*\)\n\1$/d;P;D' temp
LC_ALL=C sed -e ':top' -e '$!{/\n.*\n/!{N;b top' -e '};};/^\(.*\)\n\1\n\1$/d;P;D' temp
# Etc.
Dzika karta
źródło
2
@Wildcard: Możesz ustawić ustawienia regionalne na C, w przeciwnym razie w ustawieniach wielobajtowych niepoprawny znak w tych ustawieniach regionalnych spowoduje niepowodzenie polecenia.
cuonglm
4

Nie jest zbyt elegancki, ale jest tak prosty, jak mogę wymyślić:

uniq -c input | awk '{if ($1 % 2 == 1) { print substr($0, 9) }}'

Funkcja substr () po prostu przycina dane uniqwyjściowe. Będzie to działać, dopóki nie będzie więcej niż 9 999 999 duplikatów linii (w takim przypadku dane wyjściowe uniq mogą rozlewać się na ponad 9 znaków).

Jeff Schaller
źródło
Próbowałem uniq -c input | awk '{if ($1 %2 == 1) { print $2 } }'i wydawało się, że działa równie dobrze. Czy jest jakiś powód, dla którego substrwersja jest lepsza?
Joseph R.
1
@JosephR., Jeśli w wierszach jest jakaś spacja, wersja w twoim komentarzu zawiedzie.
Wildcard
To prawda. W takim razie czy pętla do drukowania pól $2nie $NFbyłaby bardziej niezawodna?
Joseph R.
@JosephR .: Dlaczego uważasz, że twoja alternatywa byłaby bardziej niezawodna? Możesz mieć trudności z poprawnym działaniem, gdy jest wiele kolejnych spacji; np foo   bar.
G-Man mówi „Przywróć Monikę”
@JosephR., Nie, ponieważ zmieniłoby / wyeliminowało ograniczanie białych znaków. uniq(przynajmniej w jądrach GNU) wydaje się, że niezawodnie używają dokładnie 9 znaków przed samym tekstem; Nie mogę tego nigdzie udokumentować i nie ma go w specyfikacji POSIX .
Wildcard
4

Spróbuj tego awkskryptu poniżej:

#!/usr/bin/awk -f
{
  if ((NR!=1) && (previous!=$0) && (count%2==1)) {
    print previous;
    count=0;
  }
  previous=$0;
  count++;
}
END {
  if (count%2==1) {
    print previous;
  }
}

Zakłada się, że lines.txtplik jest posortowany.

Test:

$ chmod +x script.awk
$ ./script.awk lines.txt
a
d
e
Jay Jargot
źródło
4

Z pcregrepdla danej próbki:

pcregrep -Mv '(.)\n\1$' file

lub bardziej ogólnie:

pcregrep -Mv '(^.*)\n\1$' file
jimmij
źródło
Czy na końcu nie powinno być kotwicy „końca linii”? W przeciwnym razie nie powiedzie się wiersz, który pasuje do wiersza przed nim inny niż znaki końcowe.
Wildcard
@Wildcard tak, to lepiej. poprawione, dzięki.
jimmij
Bardzo fajny! (+1)
JJoao,
4

Jeśli dane wejściowe są posortowane:

perl -0pe  'while(s/^(.*)\n\1\n//m){}'
JJoao
źródło
Masz tutaj błąd kotwiczenia. Spróbuj uruchomić go np., pineapple\napple\ncoconutA wynik to pinecoconut.
Wildcard
@Wildcard: dziękuję. Masz rację. Sprawdź, czy moja aktualizacja ma sens ...
JJoao
1
Tak. Zastanawiałem się, dlaczego uzywasz \nzamiast $biorąc pod uwagę /mmodyfikator, ale potem zdałem sobie sprawę, że za pomocą $byłoby zostawić pusty wiersz w miejsce usuniętych linii. Wygląda teraz dobrze; Usunąłem niepoprawną wersję, ponieważ po prostu dodała hałas. :)
Wildcard
@wildcard, dziękuję za redukcję hałasu ☺
JJoao
3

Lubię pythonto, na przykład z pythonwersją 2.7+

from itertools import groupby
with open('input') as f:
    for k, g in groupby(f):
            if len(list(g)) % 2:
                    print(k),
iruvar
źródło
2

Ponieważ zrozumiałem pytanie, które wybrałem awk, używając skrótu każdego rekordu, w tym przypadku zakładam, że RS = \ n, ale można to zmienić, aby rozważyć inne rodzaje aranżacji, można ustawić, aby rozważyć parzysta liczba powtórzeń zamiast nieparzystych z parametrem lub małym dialogiem. Każda linia jest używana jako skrót, a jej liczba jest zwiększana, na końcu pliku tablica jest skanowana i drukuje każdą parzystą liczbę rekordów. Podaję liczbę, aby sprawdzić, ale usunięcie [x] wystarczy, aby rozwiązać ten problem.

HTH

liczy kod

#!/usr/bin/nawk -f
{a[$0]++}
END{for (x in a) if (a[x]%2!=0) print x,a[x] }

Przykładowe dane:

a
One Sunny Day
a
a
b
my best friend
my best friend
b
c
c
c
One Sunny Day
c
d
my best friend
my best friend
d
d
d
One Sunny Day
d
e
x
k
j
my best friend
my best friend

Przykładowy przebieg:

countlines feed.txt
j 1
k 1
x 1
a 3
One Sunny Day 3
d 5
e 1
Moises Najar
źródło
To niezły kawałek awkkodu, ale niestety awktablice asocjacyjne wcale nie są uporządkowane, ani też nie zachowują porządku.
Wildcard
@Wildcard, zgadzam się z tobą, jeśli potrzebujesz kolejności wprowadzania, a nie kolejności sortowania, można ją zrealizować za pomocą dodatkowego klucza skrótu, zaletą tego jest to, że nie musisz sortować danych wejściowych, ponieważ kolejność sortowania można zrobić na końcu z mniejszą wydajnością;)
Moises Najar
@Wildcard, jeśli chcesz zachować zamówienie, proszę wspomnij o tym w pytaniu. Podejście to było również moją pierwszą myślą i nie wspominasz o kolejności poza stwierdzeniem, że możemy założyć, że plik jest posortowany. Oczywiście, jeśli plik jest posortowany, zawsze możesz przekazać wyniki tego rozwiązania sort.
terdon
@terdon, oczywiście masz rację; dane wyjściowe można po prostu posortować ponownie. Słuszna uwaga. Warto również zauważyć, że !=0wynika to z tego, w jaki sposób awkkonwertuje liczby na wartości prawda / fałsz, dzięki czemu można to zredukować doawk '{a[$0]++}END{for(x in a)if(a[x]%2)print x}'
Wildcard
1

Jeśli dane wejściowe są posortowane, co z tym awk:

awk '{ x[$0]++; if (prev != $0 && x[prev] % 2 == 1) { print prev; } prev = $0; } END { if (x[prev] % 2 == 1) print prev; }' sorted
taliezin
źródło
1

z perlem:

uniq -c file | perl -lne 'if (m(^\s*(\d+) (.*)$)) {print $2 if $1 % 2 == 1}'
xx4h
źródło
1

Używając konstrukcji powłoki,

uniq -c file | while read a b; do if (( $a & 1 == 1 )); then echo $b; fi done
Guido
źródło
1
To łamie się z wierszami rozpoczynającymi się lub kończącymi na białych znakach (lub więcej, ponieważ zapomniałeś zacytować $b).
Gilles „SO- przestań być zły”
1

Zabawna łamigłówka!

W Perlu:

#! /usr/bin/env perl

use strict;
use warnings;

my $prev;
while (<>) {
  $prev = $_, next unless defined $prev;  # prime the pump

  if ($prev ne $_) {
    print $prev;
    $prev = $_;                           # first half of a new pair
  }
  else {
    undef $prev;                          # discard and unprime the pump
  }
}

print $prev if defined $prev;             # possible trailing odd line

Szczegółowo w Haskell:

main :: IO ()
main = interact removePairs
  where removePairs = unlines . go . lines
        go [] = []
        go [a] = [a]
        go (a:b:rest)
          | a == b = go rest
          | otherwise = a : go (b:rest)

Tersely in Haskell:

import Data.List (group)
main = interact $ unlines . map head . filter (odd . length) . group . lines
Greg Bacon
źródło
0

wersja: Używam „ograniczników”, aby uprościć wewnętrzną pętlę (zakłada, że ​​pierwszy wiersz nie jest, __unlikely_beginning__i zakłada, że ​​tekst nie kończy się na linii: __unlikely_ending__i dodaj tę specjalną linię separatora na końcu wprowadzanych linii. algorytm może przyjąć zarówno:)

{ cat INPUTFILE_or_just_-  ; echo "__unlikely_ending__" ; } | awk '
  BEGIN {mem="__unlikely_beginning__"; occured=0; }  

    ($0 == mem)            { occured++ ; next } 

    ( occured%2 )           { print mem ;} 
                            { mem=$0; occured=1; }
'

Więc :

  • pamiętamy wzorzec, który obecnie obserwujemy, zwiększając go o jeden za każdym razem, gdy powtarza się. [a jeśli to się powtórzy, pomijamy kolejne 2 akcje, które mają miejsce w przypadku zmiany wzorca]
  • Gdy wzór ZMIENIA:
    • jeśli nie wielokrotność 2, drukujemy jedno wystąpienie zapamiętanego wzoru
    • i za każdym razem, gdy wzór się zmienił: nowy zapamiętany wzór jest bieżącym wzorem i widzieliśmy go tylko raz.
Olivier Dulac
źródło