ugrep indexer
v1.0.0
Das Dienstprogramm ugrep-indexer indiziert Dateien rekursiv, um das rekursive Grepping zu beschleunigen.
Auch der Inhalt von Archiven und komprimierten Dateien wird indiziert, wenn dies mit einer Befehlszeilenoption angegeben wird. Dadurch entfällt die Suche, wenn keiner ihrer Inhalte mit den angegebenen Mustern übereinstimmt.
ugrep ist ein grep-kompatibler schneller Dateisucher, der die indexbasierte Suche unterstützt. Die indexbasierte Suche kann auf langsamen Dateisystemen und wenn das Dateisystem-Caching ineffektiv ist, erheblich schneller sein: Wenn das Dateisystem auf einem durchsuchten Laufwerk nicht im RAM zwischengespeichert ist, also „kalt“ ist, beschleunigt die Indizierung die Suche. Es durchsucht nur die Dateien, die möglicherweise einem angegebenen Regex-Muster entsprechen, indem ein Index der Datei verwendet wird. Dieser Index ermöglicht eine schnelle Überprüfung, ob eine mögliche Übereinstimmung vorliegt, sodass wir nicht alle Dateien durchsuchen müssen.
Die indizierte Suche mit ugrep ist sicher und überspringt niemals aktualisierte Dateien, die jetzt möglicherweise übereinstimmen. Wenn nach der Indizierung Dateien und Verzeichnisse hinzugefügt oder geändert werden, werden bei der Suche immer diese am Dateisystem vorgenommenen Hinzufügungen und Änderungen durchsucht, indem die Zeitstempel der Dateien und Verzeichnisse mit dem Zeitstempel der Indizierung verglichen werden.
Wenn nach der Indizierung viele Dateien hinzugefügt oder geändert werden, möchten wir möglicherweise eine Neuindizierung durchführen, um die Indizes auf den neuesten Stand zu bringen. Die Neuindizierung erfolgt inkrementell und dauert daher nicht so lange wie der anfängliche Indexierungsprozess.
Ein typisches, aber kleines Beispiel für eine indexbasierte Suche, zum Beispiel im ugrep v3.12.6-Repository auf einem separaten Laufwerk:
$ cd drive/ugrep
$ ugrep-indexer -I
12247077 bytes scanned and indexed with 19% noise on average
1317 files indexed in 28 directories
28 new directories indexed
1317 new files indexed
0 modified files indexed
0 deleted files removed from indexes
128 binary files ignored with --ignore-binary
0 symbolic links skipped
0 devices skipped
5605227 bytes indexing storage increase at 4256 bytes/file
Die normale Suche in einem kalten Dateisystem ohne Indizierung dauert 1,02 Sekunden, nachdem das drive ausgehängt und erneut gemountet wurde, um den FS-Cache zu leeren und die Auswirkungen der Indizierung aufzuzeichnen:
$ ugrep -I -l 'std::chrono' --stats
src/ugrep.cpp
Searched 1317 files in 28 directories in 1.02 seconds with 8 threads: 1 matching (0.07593%)
Ripgrep 13.0.0 benötigt mit 1,18 Sekunden länger für die gleiche Kaltsuche (Ripgrep überspringt standardmäßig Binärdateien, daher ist die Option -I nicht angegeben):
$ time rg -l 'std::chrono'
src/ugrep.cpp
1.18 real 0.01 user 0.06 sys
Im Gegensatz dazu dauert die Suche in einem kalten Dateisystem mit ugrep bei der Indizierung nur 0,0487 Sekunden, was 21-mal schneller ist, nachdem drive ausgehängt und erneut gemountet wurde, um den FS-Cache zu leeren und den Effekt der Indizierung aufzuzeichnen:
$ ugrep --index -I -l 'std::chrono' --stats
src/ugrep.cpp
Searched 1317 files in 28 directories in 0.0487 seconds with 8 threads: 1 matching (0.07593%)
Skipped 1316 of 1317 files with non-matching indexes
Es gibt immer eine gewisse Abweichung in der verstrichenen Zeit, wobei 0,0487 Sekunden die beste Zeit von vier Suchläufen waren, die einen Suchzeitbereich von 0,0487 (21-fache Beschleunigung) bis 0,0983 Sekunden (10-fache Beschleunigung) ergaben.
Die Geschwindigkeitssteigerung kann im Vergleich zu dieser kleinen Demo im Allgemeinen deutlich höher ausfallen, abhängig von mehreren Faktoren, der Größe der indizierten Dateien, der Lesegeschwindigkeit des Dateisystems und der Annahme, dass die meisten Dateien kalt sind.
Der von mir entworfene Indexierungsalgorithmus ist nachweislich monoton : Eine höhere Genauigkeit garantiert eine höhere Suchleistung durch Reduzierung der Falsch-Positiv-Rate, erhöht aber auch den Speicheraufwand für den Index. Ebenso verringert eine geringere Genauigkeit die Suchleistung, verringert aber auch den Indexspeicheraufwand. Deshalb habe ich meinen Indexer einen monotonen Indexer genannt.
Wenn der Dateispeicherplatz knapp ist, können wir den Speicheraufwand für den Index verringern, indem wir eine geringere Indizierungsgenauigkeit festlegen.
Durch die Indizierung des Beispiels von oben mit Stufe 0 (Option -0 ) wird der Speicheraufwand für die Indizierung um das 8,6-fache reduziert, von 4256 Byte pro Datei auf mickrige 490 Byte pro Datei:
12247077 bytes scanned and indexed with 42% noise on average
1317 files indexed in 28 directories
0 new directories indexed
1317 new files indexed
0 modified files indexed
0 deleted files removed from indexes
128 binary files ignored with --ignore-binary
0 symbolic links skipped
0 devices skipped
646123 bytes indexing storage increase at 490 bytes/file
Die indizierte Suche ist in diesem Beispiel immer noch um das 12-fache schneller als die nicht indizierte Suche, wobei tatsächlich 16 Dateien durchsucht wurden (15 Fehlalarme):
Searched 1317 files in 28 directories in 0.0722 seconds with 8 threads: 1 matching (0.07593%)
Skipped 1301 of 1317 files with non-matching indexes
Regex-Muster, die komplexer sind als in diesem Beispiel, können naturgemäß eine höhere Falsch-Positiv-Rate aufweisen, d. h. die Rate der Dateien, die als möglicherweise übereinstimmend angesehen werden, obwohl dies nicht der Fall ist. Eine höhere Falsch-Positiv-Rate kann die Suchgeschwindigkeit verringern, wenn die Rate groß genug ist, um wirkungsvoll zu sein.
Die folgende Tabelle zeigt, wie sich die Indizierungsgenauigkeit auf den Indizierungsspeicher und den durchschnittlichen Lärm pro indizierter Datei auswirkt. Die Spalten ganz rechts zeigen die Suchgeschwindigkeit und die Falsch-Positiv-Rate für ugrep --index -I -l 'std::chrono' :
| gem. | Indexspeicher (KB) | durchschnittlicher Lärm | Fehlalarme | Suchzeit(en) |
|---|---|---|---|---|
-0 | 631 | 42 % | 15 | 0,0722 |
-1 | 1276 | 39 % | 1 | 0,0506 |
-2 | 1576 | 36 % | 0 | 0,0487 |
-3 | 2692 | 31 % | 0 | unch |
-4 | 2966 | 28 % | 0 | unch |
-5 | 4953 | 23 % | 0 | unch |
-6 | 5474 | 19 % | 0 | unch |
-7 | 9513 | 15 % | 0 | unch |
-8 | 10889 | 11 % | 0 | unch |
-9 | 13388 | 7 % | 0 | unch |
Wenn der angegebene reguläre Ausdruck mit vielen weiteren möglichen Mustern übereinstimmt, beispielsweise mit der Suche ugrep --index -I -l '(todo|TODO)[: ]' , dann beobachten wir möglicherweise eine höhere Rate falsch positiver Ergebnisse unter den 1317 durchsuchten Dateien. was zu etwas längeren Suchzeiten führt:
| gem. | Fehlalarme | Suchzeit(en) |
|---|---|---|
-0 | 189 | 0,292 |
-1 | 69 | 0,122 |
-2 | 43 | 0,103 |
-3 | 19 | 0,101 |
-4 | 16 | 0,097 |
-5 | 2 | 0,096 |
-6 | 1 | unch |
-7 | 0 | unch |
-8 | 0 | unch |
-9 | 0 | unch |
Genauigkeit -4 ist die Standardeinstellung (von -5 zuvor in älteren Versionen), die bei der Suche mit Regex-Mustern mittlerer Komplexität sehr gut funktioniert.
Ein Wort der Vorsicht. Die Überprüfung der Indizes verursacht immer einen kleinen Aufwand. Dies bedeutet, dass die Indizierung die Suche natürlich nicht unbedingt beschleunigt, wenn alle Dateien bereits im RAM zwischengespeichert sind, weil Dateien kürzlich durchsucht oder gelesen wurden. In diesem Fall ist eine nicht indizierte Suche möglicherweise schneller. Darüber hinaus hat eine indexbasierte Suche eine längere Startzeit. Diese Startzeit erhöht sich, wenn Unicode-Zeichenklassen und Platzhalter verwendet werden, die in Hash-Tabellen konvertiert werden müssen.
Zusammenfassend lässt sich sagen, dass die indexbasierte Suche am effektivsten ist, wenn viele kalte Dateien durchsucht werden und wenn Regex-Muster nicht allzu sehr übereinstimmen, d. h. wir möchten die Verwendung unbegrenzter Wiederholungen * und + und die Verwendung von Unicode-Zeichenklassen einschränken, wenn möglich. Dies verkürzt die Startzeit von ugrep und begrenzt die Rate falsch positiver Musterübereinstimmungen (siehe auch Fragen und Antworten unten).
Rekursiv und inkrementell alle nicht-binären Dateien indizieren, die den Fortschritt anzeigen:
ugrep-indexer -I -v
Indizieren Sie rekursiv und inkrementell alle nicht-binären Dateien, einschließlich nicht-binärer Dateien, die in Archiven und komprimierten Dateien gespeichert sind, und zeigen Sie den Fortschritt an:
ugrep-indexer -z -I -v
Indizieren Sie inkrementell alle nicht-binären Dateien, einschließlich Archiven und komprimierten Dateien, zeigen Sie den Fortschritt an, folgen Sie symbolischen Links zu Dateien (aber nicht zu Verzeichnissen), indizieren Sie jedoch keine Dateien und Verzeichnisse, die den Globs in .gitignore entsprechen:
ugrep-indexer -z -I -v -S -X
Erzwingen Sie die Neuindizierung aller nicht-binären Dateien, einschließlich Archiven und komprimierten Dateien, folgen Sie symbolischen Links zu Dateien (aber nicht zu Verzeichnissen), indizieren Sie jedoch keine Dateien und Verzeichnisse, die den Globs in .gitignore entsprechen:
ugrep-indexer -f -z -I -v -S -X
Das Gleiche, aber reduzieren Sie den Speicher der Indexdatei auf ein Minimum, indem Sie die Indexierungsgenauigkeit von 5 (Standard) auf 0 verringern:
ugrep-indexer -f -0 -z -I -v -S -X
Erhöhen Sie die Suchleistung, indem Sie die Indexierungsgenauigkeit von 5 (Standard) auf 7 erhöhen, allerdings auf Kosten größerer Indexdateien:
ugrep-indexer -f7zIvSX
Löschen Sie rekursiv alle versteckten ._UG#_Store -Indexdateien, um den Verzeichnisbaum wieder in den nicht indizierten Zustand zu versetzen:
ugrep-indexer -d
Konfigurieren und kompilieren mit:
./build.sh
Falls gewünscht, aber nicht erforderlich, installieren Sie mit:
sudo make install
Fügen Sie eine Option zum Erstellen einer Indexdatei hinzu, z. B. explizit für ugrep angegeben. Dies könnte die Geschwindigkeit der indizierten Suche weiter verbessern, wenn sich die Indexdatei in einem schnellen Dateisystem befindet. Andernfalls ist keine große Verbesserung oder gar eine mögliche Verlangsamung zu erwarten, da eine einzelne Indexdatei nicht gleichzeitig durchsucht werden kann und mehr Indexeinträge überprüft werden, wenn tatsächlich Verzeichnisse übersprungen werden (wobei auch deren Indizes übersprungen werden). Experimente werden es zeigen. Ein entscheidender Vorbehalt dieses Ansatzes besteht darin, dass die indexbasierte Suche mit ugrep --index nicht mehr sicher ist: Neue und geänderte Dateien, die noch nicht indiziert sind, werden nicht durchsucht.
Jeder N-Gramm-Bloom-Filter verfügt über eine eigene „Bit-Ebene“ in der Hash-Tabelle, um Hash-Konflikte zu vermeiden. Beispielsweise teilen sich 2-Gramm-Blöcke keine Bits mit 3-Gramm-Blöcken. Dadurch wird sichergestellt, dass es nie zu Fehlalarmen mit fälschlicherweise übereinstimmenden Zeichen kommt, die eigentlich nicht Teil des Musters sind. Allerdings ist der 1-Gramm-Bitraum (einzelnes Zeichen) klein (höchstens 256 Bit). Daher verschwenden wir einige Bits, wenn die Hash-Tabellen größer sind. Ein möglicher Ansatz zur Reduzierung von Verschwendung besteht darin, 1 Gramm mit 2 Gramm zu kombinieren, um den gleichen Bitraum zu teilen. Dies ist einfach, wenn wir davon ausgehen, dass ein 1-Gramm einem 2-Gramm entspricht und das zweite Zeichen auf (NUL) gesetzt ist. Mit einem zweiten 2-Gramm-Hash, der auf einer anderen Hash-Methode basiert, können wir die Falsch-Positiv-Rate senken. Oder wir können die „Bit-Ebenen“ von 8 auf 9 erweitern, um 9 Gramm zu speichern. Dadurch wird die Indexierungsgenauigkeit für längere Muster (9 oder länger) ohne zusätzliche Kosten erhöht. Andererseits kann diese Änderung zu mehr Fehlalarmen führen, wenn fälschlicherweise Zeichen gefunden werden, die nicht Teil des Musters sind. wir verlieren den Vorteil einer perfekten 1-Gramm-Genauigkeit.
Durch die Indizierung wird jedem indizierten Verzeichnis eine versteckte Indexdatei ._UG#_Store hinzugefügt. Indizierte Dateien werden vom ugrep-indexer gescannt (nie geändert!), um Indexdateien zu generieren.
Die Größe der Indexdateien hängt von der angegebenen Genauigkeit ab, wobei -0 der niedrigste Wert (kleine Indexdateien) und -9 der höchste Wert (große Indexdateien) ist. Die Standardgenauigkeit beträgt -4 . Weitere Informationen zum Einfluss der Genauigkeit auf die Indizierungsgröße im Vergleich zur Suchgeschwindigkeit finden Sie in der nächsten Frage.
Die Indizierung folgt niemals symbolischen Links zu Verzeichnissen , da sich symbolisch verknüpfte Verzeichnisse an einer beliebigen Stelle in einem Dateisystem oder in einem anderen Dateisystem befinden können, wo wir keine Indexdateien hinzufügen möchten. Sie können weiterhin symbolische Links zu Dateien mit der ugrep-indexer-Option -S indizieren.
Option -v ( --verbose ) zeigt den Indizierungsfortschritt und das „Rauschen“ jeder indizierten Datei an. Rauschen ist ein Maß für die Entropie oder Zufälligkeit der Eingabe. Ein höherer Rauschpegel bedeutet, dass die Indizierung den Inhalt einer Datei weniger genau darstellte. Beispielsweise lässt sich eine große Datei mit zufälligen Daten nur schwer genau indizieren und weist ein hohes Maß an Rauschen auf.
Die Komplexität der Indizierung hängt linear von der Größe einer bestimmten zu indizierenden Datei ab. In der Praxis handelt es sich nicht um einen schnellen Prozess, nicht um eine so schnelle Suche, und es kann einige Zeit dauern, bis ein vollständiger Indexierungsdurchlauf über einen großen Verzeichnisbaum abgeschlossen ist. Wenn die Indizierung abgeschlossen ist, zeigt ugrep-indexer die Ergebnisse der Indizierung an. Die Gesamtgröße der hinzugefügten Indizes und das durchschnittliche Indizierungsrauschen werden ebenfalls angegeben.
Das Scannen einer Datei zur Indizierung führt zu einer 64 KB großen Indizierungs-Hashes-Tabelle. Anschließend halbiert der ugrep-Indexer die Tabelle mit bitweiser Bitkomprimierung, solange die Zielgenauigkeit nicht überschritten wird. Die Halbierung wird dadurch ermöglicht, dass die Tabelle Hashes für 8 Fenster an Offsets vom Beginn des Musters codiert, was den 8 Bits pro Index-Hashing-Tabellenzelle entspricht. Durch die Kombination der beiden Tabellenhälften können einige Bits von Eins auf Null umgedreht werden, was zu einer falsch positiven Übereinstimmung führen kann. Dies beweist die Monotonie des Indexers. Ein Null-Bit-Hashwert weist auf eine mögliche Übereinstimmung hin.
Der ugrep-indexer erkennt „Binärdateien“, die mit der ugrep-indexer-Option -I ( --ignore-binary ) ignoriert und nicht indiziert werden können. Dies ist nützlich, wenn Sie mit der ugrep-Option -I ( --ignore-binary ) suchen, um Binärdateien zu ignorieren, was ein typisches Szenario ist.
Der ugrep-indexer befolgt .gitignore-Dateiausschlüsse, wenn er mit der Option -X ( --ignore-files ) angegeben wird. Ignorierte Dateien und Verzeichnisse werden nicht indiziert, um Speicherplatz im Dateisystem zu sparen. Dies funktioniert gut, wenn Sie mit der ugrep-Option --ignore-files nach Dateien suchen.
Die Indizierung kann beispielsweise mit STRG-C abgebrochen werden, was nicht zu einem Verlust der Suchfähigkeit mit ugrep führt, sondern dazu führt, dass die Verzeichnisstruktur nur teilweise indiziert bleibt.
Die Option -c prüft Indizes auf veraltete Referenzen und nicht indizierte Dateien und Verzeichnisse.
Indizes werden mit der ugrep-indexer-Option -d gelöscht.
Der ugrep-indexer wurde ausgiebig getestet, indem die Suchergebnisse ugrep --index mit den „langsamen“, nicht indizierten Suchergebnissen ugrep für Tausende von Dateien mit Tausenden zufälligen Suchmustern verglichen wurden.
Die indizierte Suche funktioniert mit allen ugrep-Optionen außer mit der Option -v ( --invert-match ), --filter , -P ( --perl-regexp ) und -Z ( --fuzzy ). Die Option -c ( --count ) mit --index legt automatisch --min-count=1 fest, um alle Dateien mit null Übereinstimmungen zu überspringen.
Wenn nach der Indizierung Dateien oder Verzeichnisse aktualisiert, hinzugefügt oder gelöscht wurden, durchsucht ugrep --index diese Dateien und Verzeichnisse immer, wenn sie im rekursiven Suchpfad vorhanden sind. Sie können ugrep-indexer erneut ausführen, um alle Indizes schrittweise zu aktualisieren.
Regex-Muster werden intern von ugrep mit der Option --index in eine Form von Hash-Tabellen für bis zu den ersten 16 Bytes der angegebenen Regex-Muster konvertiert, möglicherweise kürzer, um die Erstellungszeit zu verkürzen, wenn Regex-Muster komplex sind. Daher sind die ersten 8 bis 16 Zeichen eines zu durchsuchenden Regex-Musters am kritischsten und sollten nicht zu viele übereinstimmen, um sogenannte falsch positive Übereinstimmungen zu begrenzen, die die Suche verlangsamen können.
In ugrep wird ein Regex-Muster in einen DFA konvertiert. Auf dem DFA wird ein indexierender Hash-Finite-Automaton (HFA) aufgebaut, um Hash-Tabellen kompakt als Zustandsübergänge mit beschrifteten Kanten darzustellen. Dieser HFA besteht aus bis zu acht Schichten, die jeweils um ein Byte verschoben sind, um das nächste 8-Byte-Fenster über dem Muster darzustellen. Jede HFA-Schicht codiert Index-Hashes für diesen Teil des Musters. Die gewählte Index-Hash-Funktion ist „additiv“, was bedeutet, dass das nächste Byte hinzugefügt wird, wenn mit dem vorherigen Hash gehasht wird. Dies ist sehr wichtig, da es den HFA-Bauaufwand erheblich reduziert. Wir können jetzt gekennzeichnete HFA-Übergänge zu Zuständen als mehrere Kanten mit 16-Bit-Hash-Wertbereichen kodieren, anstatt als Satz einzelner Kanten mit jeweils einem einzelnen Hash-Wert. Zu diesem Zweck verwende ich meine Bibliothek mit offenen Bereichen reflex::ORanges<T> abgeleitet von std::set<T> .
Nachfolgend wird eine sehr einfache einzelne String-Funktion maybe_match() mit der Primzahl-61-Index-Hash-Funktion gezeigt, um die indexbasierte Suche nach einem einzelnen String zu demonstrieren:
// prime 61 hashing
uint16_t indexhash(uint16_t h, uint8_t b, size_t size)
{
return ((h << 6) - h - h - h + b) & (size - 1);
}
// return possible match of string given array of hashes of size <= 64K (power of two)
bool maybe_match(const char *string, uint8_t *hashes, size_t size)
{
size_t len = strlen(string); // practically we can and should limit len to e.g. 15 or 16
for (const char *window = string; len > 0; ++window, --len)
{
uint16_t h = window[0] & (size - 1);
if (hashes[h] & 0x01)
return false
size_t k, n = len < 8 ? len : 8;
for (k = 1; k < n; ++k)
{
h = indexhash(h, window[k], size);
if (hashes[h] & (1 << k))
return false;
}
}
return true;
}
Der Prime-61-Hash wurde unter vielen anderen möglichen Hashing-Funktionen mithilfe eines realistischen Versuchsaufbaus ausgewählt. Eine Kandidaten-Hashing-Funktion wurde getestet, indem ein zufällig ausgewähltes Wort aus einer 100 MB großen Wikipedia-Datei wiederholt gesucht wurde. Das Wort wurde mit einem, zwei oder drei zufälligen Buchstaben mutiert. Diese Mutation wird überprüft, um sicherzustellen, dass sie keinem tatsächlich gültigen Wort in der Wikipedia-Datei entspricht. Dann wurde die Falsch-Positiv-Rate immer dann aufgezeichnet, wenn ein mutiertes Wort mit der Datei übereinstimmte. Eine Hash-Funktion mit einer minimalen Falsch-Positiv-Rate sollte insgesamt ein guter Kandidat sein.
Durch die Verwendung eines Fensters von 8 (oder kürzer, abhängig von der Musterlänge) ist die Falsch-Positiv-Rate im Vergleich zu Standard-Bloom-Filtern geringer. Genauer gesagt werden N²- Hash-Funktionen anstelle von N in einem Bloom-Filter verwendet. Bei kürzeren Mustern ist N oft zu klein, um falsch positive Ergebnisse zu begrenzen. Daher ist N² wirksamer. Außerdem wird jedes Muster aus einer Übereinstimmung zurückgewiesen, bei dem ein Zeichen irgendwo in den ersten 8 Bytes des Musters vorhanden ist und nirgendwo in einer indizierten Datei tatsächlich vorkommt, wohingegen ein Standard-Bloom-Filter möglicherweise eine falsch positive Übereinstimmung aufweist. Darüber hinaus ermöglicht die Bitadressierung zur Indizierung der Hash-Tabelle eine effiziente Tabellenkomprimierung.
Die Indizierung ist eine Form der verlustbehafteten Komprimierung. Je höher die Indizierungsgenauigkeit, desto schneller sollte die Suchleistung von ugrep sein, da mehr Dateien übersprungen werden, die nicht übereinstimmen. Eine höhere Genauigkeit reduziert das Rauschen (weniger Verluste). Ein hoher Rauschpegel führt dazu, dass ugrep manchmal nach indizierten Dateien sucht, die nicht übereinstimmen. Wir nennen diese „falsch-positiven Übereinstimmungen“. Eine höhere Genauigkeit erfordert größere Indexdateien. Normalerweise erwarten wir im Durchschnitt 4 KB oder weniger Indexierungsspeicher pro Datei. Das Minimum beträgt 128 Byte Indexspeicher pro Datei, ohne den Dateinamen und einen 4-Byte-Indexheader. Für sehr große, verrauschte Dateien beträgt der Maximalwert 64 KB Speicherplatz pro Datei.
Beim Durchsuchen indizierter Dateien mit ugrep --index --stats zeigt die Option --stats die Suchstatistiken an, nachdem die indizierungsbasierte Suche abgeschlossen ist. Wenn viele Dateien aufgrund von Indizierungsrauschen (z. B. Fehlalarmen) nicht von der Suche ausgeschlossen werden, trägt eine höhere Genauigkeit dazu bei, die Effektivität der Indizierung zu erhöhen, was die Suche beschleunigen kann.
UTF-16- und UTF-32-Dateien werden ebenfalls indiziert. Der Indexer behandelt sie als UTF-8, nachdem er sie zur Indexierung intern in UTF-8 konvertiert hat.
Durch das Archivieren (zip/tar/pax/cpio) und Komprimieren von Dateien wird Speicherplatz gespart. Andererseits ist das Durchsuchen von Archiven und komprimierten Dateien viel langsamer als das Durchsuchen normaler Dateien. Das Indizieren von Archiven und komprimierten Dateien mit ugrep-indexer -z -I und das Durchsuchen mit ugrep -z -I --index PATTERN beschleunigt die Suche, wenn also Archive und komprimierte Dateien übersprungen werden. Andererseits werden die Anforderungen an den Festplattenspeicher durch die Hinzufügung von Indexdateieinträgen für Archive und komprimierte Dateien steigen. Beachten Sie, dass die Option -I diese Binärdateien ignoriert, wenn Archive und komprimierte Dateien Binärdateien enthalten.
Der Startaufwand von ugrep --index zum Erstellen von Indexierungs-Hash-Tabellen hängt von den Regex-Mustern ab. Wenn ein Regex-Muster sehr „freizügig“ ist, also mit vielen möglichen Mustern übereinstimmt, erhöht sich die Startzeit von ugrep --index zum Berechnen von Hash-Tabellen erheblich. Dies kann passieren, wenn große Unicode-Zeichenklassen und Platzhalter verwendet werden, insbesondere bei den unbegrenzten * und + -Wiederholungen. Um herauszufinden, wie sich die Startzeit erhöht, verwenden Sie die Option ugrep --index -r PATTERN /dev/null --stats=vm um /dev/null mit Ihrem PATTERN zu durchsuchen.
Indexdateien sollten einen sehr hohen Informationsgehalt haben, und das ist bei diesem neuen Indexierungsalgorithmus für ugrep der Fall, den ich entworfen und implementiert habe. Je dichter eine Indexdatei ist, desto kompakter stellt sie die Originaldateidaten dar. Das macht es schwierig oder unmöglich, Indexdateien zu komprimieren. Dies ist auch ein guter Indikator dafür, wie effektiv eine Indexdatei in der Praxis sein wird.
