🐧 🚵🏼 🏆 Schnelle Dateisuche 💔 🔢 🚭

Von einem Übersetzer: Ich mache Sie auf eine Übersetzung eines sehr alten Artikels aufmerksam, der am 15. Januar 1983 veröffentlicht wurde. Trotz dieses beeindruckenden Alters erschien mir der Artikel interessant, und es ist möglich, dass er heute für jemanden nützlich sein wird. Übrigens wird auf diesen Artikel vom Hilfethema man locate (1) auf opennet.ru verwiesen: https://www.opennet.ru/man.shtml?topic=locate .

Zusammenfassung

Dieser Artikel beschreibt einen schnellen Dateisuchmechanismus unter UNIX. Es kombiniert zwei Datenkomprimierungsmethoden mit einer neuen Zeilensuchtechnik und wurde entwickelt, um schnell nach beliebigen Dateien zu suchen. Der in das Standard-Suchdienstprogramm integrierte Code durchsucht die zuvor erstellte Datenbank und wird täglich aktualisiert. Dies unterscheidet es von dem üblichen Mechanismus für die Suche nach Schlüsselübereinstimmungen mit Kandidaten, die im laufenden Betrieb aus einer verstreuten Verzeichnisstruktur (auf der Festplatte) generiert werden.

Die Dateipfaddatenbank ist eine inkrementell codierte, lexikografisch sortierte Liste (manchmal als "frontkomprimierte" Datei bezeichnet), die ebenfalls einer regulären bigramischen Codierung unterzogen wird, um eine effektive Komprimierung zu erzielen. Das Kompressionsverhältnis beträgt 5 zu 6 im Vergleich zur üblichen ASCII-Darstellung. Die Liste wird mit einer modifizierten linearen Suche gescannt, die speziell für die inkrementelle Codierung angepasst wurde, während die typische Zeit, die der Algorithmus benötigt, 40-50% weniger ist als bei einer regulären Suche.

Einführung

Das Finden von Dateien in einem Computersystem oder Computernetzwerk ist ein komplexer Prozess. UNIX-Benutzer können es auf verschiedene Arten implementieren, von der Bearbeitung der Befehle cd, ls und grep über spezielle Befehle, wie sie in Berkeley whereis und fleese entwickelt wurden, bis hin zum häufigeren Befehl find unix.

Leider ist Fleece (aus Berkeley) auf das Home-Verzeichnis beschränkt, und es kann nur an normalen Stellen nach Systemcode und Dokumentation gesucht werden.

Suche:

find / -name "*<filename>*" -print

Natürlich kann es nach beliebigen Dateien suchen, aber sehr langsam, da es einen rekursiven Abstieg im gesamten Dateisystem verwendet, der rücksichtslos auf der Festplatte verteilt ist. Die Ungeduld veranlasste uns, eine alternative Suche (in Bezug auf die Such- und Suchmethode) nach Pfaden zu Dateien zu entwickeln.

Vorberechnungen

Warum nicht einfach eine statische Liste aller Dateien im System erstellen und nach grep suchen? Ein typisches System mit 20.000 Dateien enthält 1.000 Blöcke mit Dateinamen, selbst wenn Sie / usr auf / u kürzen. Grep auf unserem entladenen PDP-11/70-System verarbeitet 30-40 Blöcke pro Sekunde und benötigt zum Scannen eine halbe Minute. Dies ist für einen häufig verwendeten Befehl nicht akzeptabel.

Wenn wir jedoch ein kleines Opfer bringen - die Unfähigkeit, nach Dateien zu suchen, die weniger als einen Tag alt sind, führt dies nicht zu großen Problemen, da derjenige, der eine solche Datei erstellt hat, wahrscheinlich in Reichweite ist oder die Datei möglicherweise noch nicht fertig ist verwenden. Ältere Dateien, die von anderen Benutzergruppen mit anderen Dateinamenskonventionen erstellt wurden, sind die wahrscheinlichsten Suchkandidaten.

Kompression

Um den Zugriff für Anwendungen zu beschleunigen, können Sie die Verwendung einer binären Suche oder einer Hash-Tabelle vorschlagen. Solche Schemata eignen sich jedoch nicht für Teilvergleiche, wenn wir nur an einem Teil des Namens interessiert sind. Die geordnete Datenkomprimierungstechnik, bekannt als inkrementelle Codierung, die für eine ähnliche Wörterbuchkomprimierungsaufgabe verwendet wurde, ist leicht zu implementieren [Morris / Thompson, 1974]. In diesem Fall wird das längste Präfix des vorherigen Namens berechnet. Zum Beispiel:

/usr/src
/usr/src/cmd/aardvark.c
/usr/src/cmd/armadillo.c
/usr/tmp/zoo

konvertiert zu

0/usr/src
8/cmd/aardvark.c
14armadillo.c
5tmp/zoo

Die Dekodierung ist einfach (Variablendeklarationen weggelassen)

fp = fopen(COMPRESSED_FILELIST, "r");
while((count = (getc(fp) & 0177)) != EOF) {
    for(p = path + count; (*p++ = getc(fp)) < 0200; )
        ; /*overlay old path with new*/
    ungetc(*--p, fp);
    *p-- = NULL;
    if(math(path, name) == YES)
        puts(path);
}

wo Mathematik ist eine Funktion, die bestimmt , ob Name String enthalten ist in dem Pfad - String .

Da die codierte Liste etwa fünfmal kürzer als die nicht codierte ist und die Dekodierung sehr einfach ist, wird das Programm drei- bis viermal schneller ausgeführt als grep in der Textdatei.

Noch schneller

Dieser Ansatz ist bereits nützlich, lässt jedoch Raum für weitere Verbesserungen. (Hinweis: Dieser Code wird im Dienstprogramm find verwendet. Es ist nicht erforderlich, UNIX mit einem anderen Befehl [und einer Manpage] zu belasten, wenn wir ein vorhandenes ähnliches Programm verbessern können. Glücklicherweise gibt es keinen Suchaufruf mit zwei Argumenten, und wir können die Lücke ohne Verschönerung füllen ::

find name

Beachten Sie, dass der obige Code weiterhin die entpackte Liste durchsucht, wenn auch im Speicher, nicht auf der Festplatte. Dies kann vermieden werden, indem ein String mit einem Teilstring in der entgegengesetzten Richtung verglichen wird. Lassen Sie namend Punkt bis zum letzten Zeichen des Strings Namen und ersetzt Mathe mit:

for(s = p, cutoff = path + count; s > cutoff; s--) {
    if(*s == namend) { /*quick first char check*/
        for(p = namend - 1, q = s - 1; *p != NULL; p--, q--)
            if(*q != *p)
                break;
        if(*p == NULL) {
            puts(path);
            break;
        }
    }
}

Dies ist anhand von drei Fällen leichter zu verstehen. Befindet sich der Teilstring vollständig rechts vom Cutoff , wird der Vergleich erfolgreich beendet. Wenn sie sich überlappen, wird der Cutoff "weich" und der Vergleich wird fortgesetzt. Wenn der Teilstring vollständig links vom Cutoff liegt , wird eine Übereinstimmung für die vorherigen Zeilen angezeigt, was bedeutet, dass wir diese Suche nicht durchführen können! Technisch gesehen kann der Cutoff unmittelbar nach Abschluss des Vergleichs auf den Pfad portiert werden . Diese Bedingung ist oben weggelassen.

Zweistufige Ausrüstung

Sie können vermeiden, die Suche zu verlangsamen, die durch die Verarbeitung von Suchmusterzeichen verursacht wird . Dabei verarbeiten wir den Teil des Namens, der keine Metazeichen enthält, und verwenden die langsamere rekursive Funktion amath inside find . Also,

puts(path)

wird

if(globchars == NO | amatch(path, name))
    puts(path);

Dabei wird Globchars gesetzt, wenn der Name Metazeichen enthält. Ein Beispiel für die Verwendung eines Suchmusters für einen einfachen man- Befehl :

vtroff -man 'find '*man*'"$1"'.[1-9]

Weitere Verbesserungen

Der Produktionscode des Dienstprogramms find erhöht das Komprimierungsverhältnis um weitere 20 bis 25%, indem die gebräuchlichsten zweistelligen Kombinationen durch nicht druckbare ASCII-Codes ersetzt werden. ".c" und ".P" sind besonders häufig.

Andere Algorithmen, die andere Kompromisse zwischen Zeit und Datengröße implementieren, wie der Huffman-Algorithmus [Reghbati, 1981], sehen nicht vielversprechend aus: Sie ersetzen lediglich das E / A-Leistungslimit durch das Leistungslimit.

Es können sublineare Boyer-Moore-Suchmethoden [Boyer, 1977] oder Makromodellmethoden [Storer / Szymanski, 1982] verwendet werden.

Abschließend sei angemerkt, dass wir in wenigen Sekunden 19.000 Dateinamen mit 180 Blöcken und einem C-Code gescannt haben, der auf zwei Seiten passt.

Verweise

Boyer, RS Ein schneller String-Suchalgorithmus, Commun. ACM. 10, Oktober 1977.
Morris, R. und Thompson, K. Websters Zweiter auf dem Kopf einer Stecknadel, unveröffentlichtes technisches Memo, Bell Laboratories, Murray Hill, NY, 1974.
Reghbati, HK Ein Überblick über Datenkomprimierungstechniken, Computer, Vol. 14, Nr. 4, April 1981.
Storer, JA und Szymanski, TG Data Compression via Textual Substitution, J. ACM. 29, No. 4. Oktober 1982.

Schnelle Dateisuche