Aus LinuxUser 01/2016

Unscharfe Suche in Texten mit Agrep

© JanMiks, 123RF

Besser finden

Das kleine Werkzeug Agrep erweitert die Möglichkeiten beim Durchstöbern von Texten um die unscharfe Suche.

Den Konsolenbefehl Grep, der es erlaubt, Zeichenketten und Muster in Textdateien aufzufinden, kennt wohl jeder Linux-Anwender, der sich schon einmal mit der Kommandozeile beschäftigt hat. Weniger bekannt sind seine Varianten: egrep BegriffDatei(en) entspricht exakt dem Aufruf grep -e BegriffDatei(en), wobei das Tool den Begriff als erweiterten regulären Ausdruck interpretiert. Dagegen interpretiert fgrep als Äquivalent zu grep -f alle Komponenten in Begriff als normale Zeichen und ignoriert deren mögliche Regex-Bedeutung. Dadurch arbeitet es etwas schneller als ein „nacktes“ Grep, was sich vor allem beim Durchsuchen großer Datenmengen bemerkbar macht. Der dritte im Bunde, rgrep, arbeitet sich wie grep -r rekursiv durch Ordnerstrukturen, was ihn nicht gerade zum Geschwindigkeitswunder macht.

Eines aber haben alle gemeinsam: Sie finden nur direkte Treffer für Begriff, eine Suche nach ähnlichen Begriffen klappt nur beim entsprechenden Design eines passenden Regex. Sehen wir uns als Beispiel einige Zeichenketten an, die dem String „grep“ ähneln: „gerp“ etwa unterscheidet sich durch das Vertauschen zweier Buchstaben von „grep“, bei „grap“ oder „grip“ gibt es eine Buchstabenersetzung, und „egrep“ enthält eine Hinzufügung.

Um solche Abweichungen mathematisch exakt zu erfassen, definierte 1965 der russische Mathematiker Wladimir Iossifowitsch Lewenstein die nach ihm benannte Levenshtein-Distanz [1]. Die auch Editierdistanz genannte Größe verwendet als Maßgabe die minimale Anzahl von Einfüge-, Lösch- und Ersetzungsoperationen für das Umwandeln einer Zeichenkette in eine andere [2]. Gewichtet man die algorithmischen „Kosten“ der notwendigen Operationen, gelangt man zur gewichteten Levenshtein-Distanz („Weighted Levenshtein Distance“, WLD). Ein Auswerten der Levenshtein-Distanz ermöglicht unter anderem, ähnliche Wörter zu finden, Schreibfehler auszugleichen und generell kleinere Wortabweichungen festzustellen und gegebenenfalls zu ignorieren.

Agrep

Die Grep-Variante Agrep setzt die durch den Levenshtein-Algorithmus bereitgestellten Verfahren um, um Zeichenketten oder Muster in Textdateien zu finden. Dabei kann sie im Gegensatz zu Grep nur relativ einfache Muster interpretieren, findet dafür aber auch ähnliche Begriffe. Obendrein arbeitet Agrep oft schneller als das Original.

Ursprünglich wurde Agrep [3] für ein Index-System namens Glimpse [4] – eine Art Vorgänger heutiger Desktop-Suchmaschinen – an der University of Arizona entwickelt. Heute kommt Glimpse kaum noch zum Einsatz; auf dem Desktop haben Recoll [5] oder ähnliche, wesentlich leistungsfähigere Programme seine Funktion übernommen. Die Syntax von Agrep lehnt sich eng an jener von Grep an und gehorcht folgendem Schema:

$ agrep  [Optionen] Muster [Datei] ...

Derzeit gibt es unter Linux zwei Versionen von Agrep: Die klassische Variante aus der Glimpse-Suite [6] und eine neuere, die auf der TRE-Library basiert [7]. Erstere arbeitet oft schneller, kommt aber nicht mit Unicode-Zeichen und anderen Multibyte-Kodierungen zurecht [8]. Deswegen liefern die meisten Distributionen inzwischen die TRE-Variante des Programms aus. Die beiden Versionen unterscheiden sich nicht nur hinsichtlich der Leistungsfähigkeit, sondern auch bei den Optionen (siehe Tabelle „Agrep-Optionen“).

Welche Variante von Agrep Sie verwenden hängt von dem Einsatzzweck und der Verfügbarkeit ab. Immer wenn es um die Verarbeitung von UNICODE-Zeichen geht, kommen Sie um die TRE-Variante nicht herum. Da diese normalerweise deutlich mehr Ressourcen und Rechenzeit als die klassische Variante benötigt, gibt es aber gute Gründe diese ebenfalls einzusetzen.

Agrep-Optionen

Funktion TRE-Agrep Glimpse-Agrep
definiert Muster; sinnvoll bei Mustern, die mit „-“ anfangen -e Muster
Inhalt der angegebenen Datei als Muster verwenden -f Dateiname
Schreibweise ignorieren -i -i
Schreibweise nicht ignorieren -i0
Schreibweise ignorieren, Ziffern mit Ziffern, Buchstaben mit Buchstaben ersetzen -i#
keine Sonderzeichen im Muster auswerten -k -k
Muster beschreibt ein ganzes Wort -w -w
Muster beschreibt eine ganze Zeile -w
rekursive Bearbeitung -r
Details einstellen (voreingestellt: jeweils 1)
„Kosten“ für das Löschen von Zeichen -DWert -DWert
„Kosten“ für das Einfügen von Zeichen -IWert -IWert
„Kosten“ für das Ersetzen von Zeichen -SWert -SWert
maximale „Kosten“ für einen Treffer -EWert -EWert
maximale zulässige Fehlerzahl für Treffer (unabhängig von den Kosten) -#Zahl -Zahl
Ausgaben steuern
„Kosten“ für den Treffer anzeigen -s
Treffer mit geringsten Kosten anzeigen(1) -B -B
Prompt bei -B unterdrücken -y
Treffer farbig hervorheben --color
Trefferzahl anzeigen -c -c
Treffer ohne Dateinamen anzeigen -h -h
Treffer mit Dateinamen anzeigen -H -G
statt Treffer nur Dateinamen mit Treffern anzeigen -l -l
immer Dateinamen mit Treffern anzeigen -A
Treffer nummerieren -n -n
keine Ausgaben -q(2) -s
Anzeige der Position des ersten Zeichens eines Treffers(3) --show-position -b
Ausgabe von Zeilenumbrüchen hinter statt vor dem Treffer -M
Zeilenumbruchzeichen -d Muster(4)
nur Zeilen ohne Treffer zeigen -v -v
zusätzliche Angaben ausgeben -VZiffer
(1) erfordert die doppelte Zeit (zwei Durchläufe) und funktioniert nicht bei Eingaben via STDIN
(2) Exit mit Returncode 0 bei einem Treffer
(3) wichtig beim Entwickeln von Mustern
(4) voreingestellt \n

Praxis

Im Prinzip nutzen Sie Agrep analog zum Standardbefehl Grep und durchsuchen damit beliebige Datenströme – also sowohl Daten aus Dateien als auch aus dem STDIN-Kanal (Listing 1). Wie Grep liest auch Agrep die Ströme Record für Record ein und durchsucht sie. Was einen solchen Record bildet, darüber entscheidet das Trennzeichen. In der Voreinstellung handelt es sich dabei um einen Zeilenumbruch (\n). Das bedeutet, dass Agrep jede Zeile als Record betrachtet und die durch -e Muster vereinbarten Muster darauf anwendet.

Listing 1

$ agrep-tre --col -s -E1 -I 2 Tst *
wizard.pdf:1:stream
wizard.pdf:1:endstream

Es gibt aber auch eine Reihe signifikanter Unterschiede zwischen (GNU-)Grep und den Agrep-Varianten. Viele Optionen des normalen Grep-Befehls kennen Letztere nicht, etwa jene für die Kontextsteuerung bei den Ausgaben (Optionen -A, -B, -C) oder In- respektive Exclude-Optionen wie bei den regulären Ausdrücken.

Besondere Aufmerksamkeit verdient die Option -d Muster zum Trennen der Records. Sie wirkt nicht in allen Fällen so, wie man es erwartet. Legen Sie beispielsweise -d ' ' fest, sollten eigentlich Leerzeichen die Records begrenzen, was aber nicht in allen Fällen gelingt. Bei solchen Problemen mit den Record-Grenzen helfen die Optionen --color, --show-position, -n (TRE-Variante), -b, -n und -V (klassische Variante) aufzuklären, was das Problem war.

Obendrein existiert in Form des Tools tr („translate“) ein relativ einfacher Workaround für derartige Probleme. Mit dem einfachen Befehl umbrechen Sie Datenströme schnell und zuverlässig in Zeilen. Die Syntax von Tr gestaltet sich recht einfach:

DIESEN ARTIKEL ALS PDF KAUFEN
EXPRESS-KAUF ALS PDFUmfang: 4 HeftseitenPreis €0,99
(inkl. 19% MwSt.)
KAUFEN
LinuxUser 01/2016 KAUFEN
EINZELNE AUSGABE Print-Ausgaben Digitale Ausgaben
ABONNEMENTS Print-Abos Digitales Abo
TABLET & SMARTPHONE APPS
Deutschland

Hinterlasse einen Kommentar

  E-Mail Benachrichtigung  
Benachrichtige mich zu: