AA_123rf-10037094_JanMiks-123RF.jpg

© JanMiks, 123RF

Unscharfe Suche in Texten mit Agrep

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 Begriff Datei(en) entspricht exakt dem Aufruf grep -e Begriff Datei(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:

$ tr Optionen Suchzeichen Ersatzzeichen

Um beispielsweise Leerzeichen in Zeilenumbrüche umzuwandeln, verwenden Sie das Kommando tr ' ' '\n'. Sie können auch mehrere Suchzeichen vereinbaren, die Tr gegen das oder die Ersatzzeichen austauscht (Listing 2). Der Vorteil dieser Variante: Da Agrep mit den gut funktionierenden Zeilenumbrüchen als Record-Grenzen arbeitet, entsprechen die Ergebnisse anschließend den Erwartungen.

Listing 2

$ echo "Hello World" | tr "A-Za-z" "a-zA-Z"
hELLO wORLD

Diesen Artikel als PDF kaufen

Express-Kauf als PDF

Umfang: 4 Heftseiten

Preis € 0,99
(inkl. 19% MwSt.)

LinuxCommunity kaufen

Einzelne Ausgabe
 
Abonnements
 
TABLET & SMARTPHONE APPS
Bald erhältlich
Get it on Google Play

Deutschland

Ähnliche Artikel

  • Wörter offline suchen und übersetzen
    Ding kombiniert als leistungsstarkes Frontend die Wörterbuch-Suche, einen Thesaurus und das Übersetzen vom Deutschen ins Englische und umgekehrt.
  • Die Bash, das unbekannte Wesen
    Es gibt neben den Pipes noch verschiedene andere Verfahren, um mehrere Shell-Befehle miteinander zu verbinden bzw. sie parallel auszuführen. Die wichtigsten Methoden werden in dieser Folge der Bash-Serie vorgestellt.
  • Gut gefiltert
    Zu den häufigsten Aufgaben bei der Arbeit am Rechner zählt das Durchstöbern von Texten nach Suchmustern. Icgrep bietet hier eine moderne, parallel arbeitende und Unicode-fähige Alternative zum klassischen Grep.
  • Wörterbücher und Textdateien durchsuchen mit grafischem Frontend
    Beim Lesen eines englischen Texts fällt oft das wichtigste Wort nicht ein. Praktisch, wenn eine Software es einfach auf Mausklick übersetzt. Das Programm Ding durchsucht dazu Wörterbücher, kommt aber auch mit anderen Textdateien zurecht.
  • Suche in komprimierten Dateien und Archiven
    Über die Kommandozeile flink in komprimierten Dateien und Archiven zu suchen, spart viel Zeit. Die richtigen Tools dazu bringt praktisch jedes Linux-System von Haus aus mit.
Kommentare

Infos zur Publikation

LU 04/2017: SPEZIAL-DISTRIBUTIONEN

Digitale Ausgabe: Preis € 5,95
(inkl. 19% MwSt.)

LinuxUser erscheint monatlich und kostet 5,95 Euro (mit DVD 8,50 Euro). Weitere Infos zum Heft finden Sie auf der Homepage.

Das Jahresabo kostet ab 86,70 Euro. Details dazu finden Sie im Computec-Shop. Im Probeabo erhalten Sie zudem drei Ausgaben zum reduzierten Preis.

Bei Google Play finden Sie digitale Ausgaben für Tablet & Smartphone.

HINWEIS ZU PAYPAL: Die Zahlung ist ohne eigenes Paypal-Konto ganz einfach per Kreditkarte oder Lastschrift möglich!

Aktuelle Fragen

WLAN lässt sich nicht einrichten
Werner Hahn, 21.03.2017 14:16, 0 Antworten
Dell Latitude E6510, Ubuntu 16.4, Kabelbox von Telecolumbus. Nach Anklicken des Doppelpfeiles (o...
"Mit Gwenview importieren" funktioniert seit openSuse 42.2 nicht mehr
Wimpy *, 20.03.2017 13:34, 2 Antworten
Bisher konnte ich von Digitalkamera oder SD-Karte oder USB-Stick Fotos mit Gwenview importieren....
Ich habe eine awk Aufgabe und bekomme es nicht so Recht hin
Dennis Hamacher, 10.03.2017 18:27, 1 Antworten
Ich hoffe Ihr könnt mir dabei helfen oder mir zeigen wie der Befehl richtig geschrieben wird. Ich...
Unter Linux Open Suse Leap 42.1 einen Windows Boot/ ISO USB Stick erstellen...
Tim Koetsier, 07.03.2017 15:26, 1 Antworten
Hallo, weiß jemand wie ich oben genanntes Vorhaben in die Tat umsetzen kann ? Wäre echt dankba...
Druckertreiber installieren OpenSuse42.1
Tim Koetsier, 07.03.2017 15:22, 1 Antworten
hallo, kann mir BITTE jemand helfen ich verzweifel so langsam. Habe einen Super Toner von Canon...