Sortierte Datei effizient durchsuchen

12

Ich habe eine große Datei mit einer Zeichenfolge in jeder Zeile. Ich möchte schnell feststellen können, ob sich eine Zeichenfolge in der Datei befindet. Idealerweise würde dies unter Verwendung eines binären Chop-Algorithmus erfolgen.

Einige Googler enthüllten den lookBefehl mit dem -bFlag, das verspricht, alle Zeichenfolgen, die mit einem bestimmten Präfix beginnen, mithilfe eines binären Suchalgorithmus zu lokalisieren und auszugeben. Leider scheint es nicht richtig zu funktionieren und gibt Null-Ergebnisse für Zeichenfolgen zurück, von denen ich weiß, dass sie in der Datei enthalten sind (sie werden von der entsprechenden grepSuche ordnungsgemäß zurückgegeben ).

Kennt jemand ein anderes Dienstprogramm oder eine andere Strategie, um diese Datei effizient zu durchsuchen?

Matt
quelle
Die oberste Antwort besagt die falsche Sortierung: Tatsache ist, dass Sie sortieren müssen mit: LC_COLLATE = C sort -d, damit der lookBefehl korrekt funktioniert, da look das Gebietsschema zu ignorieren scheint und nur C wie das hartcodierte Sortieren verwendet, habe ich auch einen Fehler geöffnet wegen dieses verwirrenden Verhaltens: bugzilla.kernel.org/show_bug.cgi?id=198011
Sur3
look -bfehlgeschlagen für mich mit einem Fehler File too large. Ich denke, es wird versucht, das Ganze in Erinnerung zu behalten.
Brian Minton

Antworten:

9

Es gibt einen wesentlichen Unterschied zwischen grepund look:

Sofern nicht ausdrücklich anders angegeben, grepwerden Muster sogar irgendwo innerhalb der Zeilen gefunden. Für lookdie Manpage heißt es:

Look - Anzeigezeilen , beginnend mit einer bestimmten Zeichenfolge

Ich benutze es nicht looksehr oft, aber es hat bei einem trivialen Beispiel, das ich gerade ausprobiert habe, gut funktioniert.

Klaus-Dieter Warzecha
quelle
1
Die Datei, die ich durchsuchen muss, enthält ungefähr 110.000.000 Zeilen. Wenn ich das tue egrep "^TEST" sortedlist.txt | wc -l , bekomme ich 41.289 Ergebnisse. Die entsprechenden lookBefehle look -b TEST sortedlist.txt | wc -lliefern jedoch nur 1995 Ergebnisse. Ich frage mich fast, ob es einen Fehler gibt look.
Matt
1
@Matt Möglicherweise lookwerden andere Sortiereinstellungen verwendet als das Programm, mit dem Sie die Datei sortiert haben.
Kasperd
4

Vielleicht eine etwas späte Antwort:

Sgrep wird Ihnen helfen.

Sgrep (sortiertes grep) durchsucht sortierte Eingabedateien nach Zeilen, die einem Suchschlüssel entsprechen, und gibt die übereinstimmenden Zeilen aus. Bei der Suche nach großen Dateien ist sgrep viel schneller als herkömmliches Unix-Grep, jedoch mit erheblichen Einschränkungen.

  • Alle Eingabedateien müssen nach regulären Dateien sortiert sein.
  • Der Sortierschlüssel muss am Zeilenanfang beginnen.
  • Der Suchschlüssel stimmt nur am Zeilenanfang überein.
  • Keine Unterstützung für reguläre Ausdrücke.

Sie können die Quelle hier herunterladen: https://sourceforge.net/projects/sgrep/?source=typ_redirect

und die Dokumente hier: http://sgrep.sourceforge.net/

Ein anderer Weg:

Ich weiß nicht, wie groß die Datei ist. Vielleicht sollten Sie es parallel versuchen:

/programming/9066609/fastest-possible-grep

Ich grep immer mit Dateien, deren Größe> 100 GB ist, es funktioniert gut.

Speicherbox
quelle
2
Ist das nicht schon in askubuntu.com/a/701237/158442 ?
Muru
Ja, ich fülle den Download-Link aus ...
Memorybox
Wenn das alles ist, sollten Sie diesen Beitrag bearbeiten , anstatt eine neue Antwort zu veröffentlichen.
Muru
Dieser Beitrag wird empfohlen: sudo apt-get install sgrep Um sgrep zu erhalten, ist der sgrep in den Buntu-Repositories nicht wirklich dieser sgrep, ich bin mir nicht sicher, ob es dasselbe ist.
Memorybox
0

Sie könnten die Datei in Stücke zerlegen und dann genau das Stück greifen, das Sie wollten:

for line in $(cat /usr/share/dict/american-english | tr '[:upper:]' '[:lower:]' | sort | uniq)
do
    prefix=$(echo $line | md5sum - | cut -c 1-2)
    mkdir -p $prefix
    echo $line | gzip >> $prefix/subwords
done

dann würde die Suche so aussehen:

    prefix=$(echo $word | md5sum - | cut -c 1-2)
    zgrep -m 1 -w word $prefix/subwords

Dies macht zwei Dinge:

  1. komprimierte Dateien lesen und schreiben. Es ist im Allgemeinen schneller, die CPU (sehr schnell) anstelle der Festplatte (sehr langsam) zu laden.
  2. Hash-Dinge, um eine ungefähr gleichmäßige Verteilung zu erhalten, können Sie einen kürzeren oder längeren Hash verwenden, um die Größe jedes Stücks zu verringern (ich würde jedoch empfehlen, verschachtelte Unterverzeichnisse zu verwenden, wenn Sie dies tun).
Joe
quelle
0

sgrep könnte für Sie arbeiten:

sudo apt-get install sgrep
sgrep -l '"needle"' haystack.txt

Auf der Projektseite http://sgrep.sourceforge.net/ heißt es:

Sgrep verwendet einen binären Suchalgorithmus, der sehr schnell ist, jedoch sortierte Eingaben erfordert.

Zum Einfügen gibt es jedoch meiner Meinung nach keine bessere Lösung als die Verwendung einer Datenbank: /programming/10658380/shell-one-liner-to-add-a-line-to-a-sorted-file/ 33859372 # 33859372

Ciro Santilli 新疆 改造 中心 法轮功 六四 事件
quelle
3
Das sgrepin den Ubuntu-Repositories ist eigentlich dieses sgrep , das entworfen wurde, um "eine Datei nach einem strukturierten Muster zu durchsuchen" und nichts mit der binären Suche zu tun hat.
ingomueller.net
0

Wenn Sie es wirklich schnell wollen (O (1) schnell), können Sie ein Hash-Set erstellen, in das Sie schauen können. Ich konnte keine Implementierung finden, mit der ich einen vorgefertigten Hash-Satz in einer Datei speichern und prüfen konnte, ohne die gesamte Datei in den Speicher lesen zu müssen, also habe ich meinen eigenen gerollt .

Erstellen Sie das Hash-Set ( -b/ --build):

./hashset.py --build string-list.txt strings.pyhashset

Prüfen Sie den Hash-Satz ( -p/ --probe):

./hashset.py --probe strings.pyhashset \
    'Is this string in my string list?' 'What about this one?'

… Oder mit einer Zeichenfolge zum Nachschlagen der Standardeingabe:

printf '%s\n' 'Is this string in my string list?' 'What about this one?' |
./hashset.py --probe strings.pyhashset

Sie können die Ausgabe von --probemit der Option -q/ --quietberuhigen, wenn Sie nur am Exit-Status interessiert sind:

if ./hashset.py --quiet --probe strings.pyhashset ...; then
    echo 'Found'
else
    echo 'Not found'
fi

Weitere Optionen finden Sie in der Verwendungsbeschreibung, auf die über die Option -h/ --helpoder die zugehörige READMEDatei zugegriffen werden kann.

David Foerster
quelle