Suchen Sie nach Zeichenfolgen, die nicht in einem Repository angezeigt werden

354
Chris

Problem: Ich habe ein mittelgroßes Repository (1000 Dateien, Hunderttausende Zeilen).

Ich habe eine Textdatei mit ~ 5000 Zeilen.

Ich muss die Zeilen in der Textdatei finden, die NICHT im Repository an anderer Stelle erscheinen.

Gibt es ein Werkzeug oder eine clevere Art, grep zu verwenden, das diese Antwort effizient findet?

Danke für jede Hilfe

0
"Ich muss die Zeilen in der Textdatei finden, die an keiner anderen Stelle im Repository erscheinen." Sprechen wir über ganze Zeilen oder Fragmente im Repository? Nehmen wir an, es gibt eine Zeile "foobar" in Ihrer Textdatei und eine Zeile "foobar baz" im Repository. Ist das ein Auftritt? Oder sollte nur die exakte Zeile "foobar" berücksichtigt werden? Kamil Maciorowski vor 7 Jahren 1
Fragmente, die Zeilen, die ich zu finden versuche, könnten Teil einer beliebigen Zeile im Quellcode sein. Chris vor 7 Jahren 0

1 Antwort auf die Frage

0
Kamil Maciorowski

Die Lösung wurde in bashUbuntu 16.04.2 LTS entwickelt.

Der Algorithmus

Dieser Abschnitt ist pädagogisch. Sie finden das gesamte Skript am Ende meiner Antwort.

Machen Sie zuerst eine Kopie Ihrer Textdatei. Das ist wichtig, die Datei, mit der wir arbeiten werden, wird überschrieben und es gibt einen Grund dafür. Passen Sie die Variablen an Ihren Fall an:

patterns="/path/to/your/text/copy" repository="/path/to/your/repository/"

Sie benötigen einige temporäre Dateien.

tmpf1=`mktemp` tmpf2=`mktemp`

Mit dem nächsten Befehl werden alle Muster (also fast alle, die zusammen gelesen werden), die im Repository erscheinen, in der ersten temporären Datei gespeichert. Siehe man grep, um den Befehl zu entschlüsseln. Entscheiden Sie auch, ob Sie die -iOption zu hinzufügen müssen grep. Die erste uniqist optional und wird verwendet, um die Daten, zu denen Daten übertragen werden, vorläufig zu reduzieren sort.

grep -rhoIFf "$patterns" "$repository" | uniq | sort | uniq | tee "$tmpf1" | wc -l

Wenn der obige Befehl gedruckt wird 0, ist die $patternsDatei, unabhängig von den unten aufgeführten Fallstricken, sicher das endgültige Ergebnis, und Sie sollten nur die temporären Dateien entfernen.

Es gibt Fallen mit grep, Sie werden gleich damit fertig werden. Es ist gut zu wissen, was sie sind.

  1. Wenn foobarund fooals Muster vorhanden sind, foobarstimmt das Repository foobarnur überein .
  2. Wenn foobarund barbazals Muster vorhanden sind, foobarbazstimmt das Repository foobarnur überein .
  3. Wenn foobarbazund barals Muster vorhanden sind, foobarbazstimmt das Repository foobarbaznur überein .

Aufgrund dieser Fallstricke $tmpf1dürfen nicht alle Muster enthalten sein, die tatsächlich im Repository erscheinen (dh sie dürfen nicht barbazaus der zweiten Fallstricke enthalten sein).

Jetzt müssen Sie alle Zeilen auswählen $patterns, die angeblich nicht im Repository gefunden wurden. Beachten Sie, dass Sie daher ganze Zeilen anpassen müssen -x.

grep -vxFf "$tmpf1" "$patterns" > "$tmpf2"

In diesem Moment $tmpf2wäre das endgültige Ergebnis, aber aufgrund dieser Fallstricke kann es zu viele Zeilen geben (zB barbazaus der zweiten Fallstricke). Der Trick ist, $tmpf2als neue Pattern-Datei zu verwenden und den Vorgang zu wiederholen! Aufrufen:

cp "$tmpf2" "$patterns"

dann geh zum ersten grep. Wiederholen Sie diesen Vorgang, bis Sie 0von wcdort kommen. Wie gesagt, wenn zurückgegeben 0wird, ist Ihr Ergebnis in $patterns.

Entfernen Sie am Ende die temporären Dateien:

rm "$tmpf1" "$tmpf2"

Effizienz

Ich habe 200k Textdateien, 4.5M Zeilen, 300 MiB insgesamt. Hierbei handelt es sich um HTML-Dokumente mit einfachen Kopfzeilen und Formatierungen, die im Wesentlichen aus reinem englischen Text bestehen. Ich nahm 3k der gebräuchlichsten englischen Wörter als Muster und fügte ein paar Zeilen Mumbo-Jumbo hinzu.

Zuerst grepdauerte es ein paar Minuten, um die Daten von der Festplatte auszulesen und zu arbeiten, dann etwa zwei Minuten sort. Jede nachfolgende Iteration war jedoch eine Frage von Sekunden, dank der Zwischenspeicherung und der $patternsimmer geringeren Anzahl.

Meine Hardware ist Core i7 und 8 GB RAM. Ihre Muster und Dateien können sich erheblich unterscheiden und die Ausführungszeit beeinflussen. Ich denke, es gibt eine Chance, dass Sie die Aufgabe in wenigen Minuten erledigen werden.

Das Skript

Dies ist die Implementierung des obigen Algorithmus. Eine weitere Funktion ist: Es entnimmt Muster stdin, druckt das Ergebnis aus stdout. In diesem Fall müssen Sie Ihre Textdatei nicht kopieren. Das Skript ist nicht narrensicher.

Speichern Sie den folgenden Code als findUnused.shdann chmod a+x findUnused.sh.

#!/bin/bash  patterns=`mktemp` cat > "$patterns" repository="$1" tmpf1=`mktemp` tmpf2=`mktemp`  while [ `grep -rhoIFf "$patterns" "$repository" | uniq | sort | uniq | tee "$tmpf1" | wc -l` -ne 0 ] do grep -vxFf "$tmpf1" "$patterns" > "$tmpf2" cp "$tmpf2" "$patterns" done cat "$patterns" rm "$patterns" "$tmpf1" "$tmpf2"

Verwendung (Hinweis: Es gibt Weiterleitungen):

./findUnused.sh "/path/to/your/repository/" < "/path/to/your/text/file" > "/path/to/store/the/result"

Verwandte Probleme