Die Lösung wurde in bash
Ubuntu 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 -i
Option zu hinzufügen müssen grep
. Die erste uniq
ist 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 $patterns
Datei, 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.
- Wenn
foobar
undfoo
als Muster vorhanden sind,foobar
stimmt das Repositoryfoobar
nur überein . - Wenn
foobar
undbarbaz
als Muster vorhanden sind,foobarbaz
stimmt das Repositoryfoobar
nur überein . - Wenn
foobarbaz
undbar
als Muster vorhanden sind,foobarbaz
stimmt das Repositoryfoobarbaz
nur überein .
Aufgrund dieser Fallstricke $tmpf1
dürfen nicht alle Muster enthalten sein, die tatsächlich im Repository erscheinen (dh sie dürfen nicht barbaz
aus 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 $tmpf2
wäre das endgültige Ergebnis, aber aufgrund dieser Fallstricke kann es zu viele Zeilen geben (zB barbaz
aus der zweiten Fallstricke). Der Trick ist, $tmpf2
als 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 0
von wc
dort kommen. Wie gesagt, wenn zurückgegeben 0
wird, 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 grep
dauerte 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 $patterns
immer 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.sh
dann 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"