reguläre Ausdrücke

Mengen

Wiederholungen

regular expression

sets

repetition

greedy repetition

non-greedy repetition

Reguläre Ausdrücke

Reguläre Ausdrücke: sind Beschreibungen für Textmuster
Syntax und Semantik: weitgehend standardisiert, Notation mittels Metazeichen
Verbreitung: in vielen Anwendungen und Programmiersprachen zum Suchen, Ersetzen oder Extrahieren von Zeichenketten – auch in Textverarbeitungsprogrammen.
sed und egrep
: akzeptieren reguläre Ausdrücke als Suchmuster
Tutorium: Richter, H., Reguläre Ausdrücke, Leibniz Rechenzentrum BAdW.
man pages: über Reguläre Ausdrücke etwa bei re_format
Lea Verou: Vortrag über reguläre Ausdrücke auf der o'reilly fluent conference.
Web-crawler (indexer): als Anwendungsbeispiel

Suchen im Web

// --- Web-crawler (indexer) Pseudo-Code

Endlosschleife:

Webseite von Webadresse laden
Text extrahieren und normieren
Neue Daten für Webadresse in Datenbank ablegen
Neue Webadresse aus Webseite entnehmen → weiter bei Endlosschleife

Quiz: Normalisierung etwa bei Suche per google?

Suchen in Daten

Dateneingabe: Rohdaten lesen, Daten extrahieren (scrape) und normieren, an Datenserver abgeben
Big Data: erhaltene Daten aufbereitet ablegen, ankommende Suchanfragen mittels spezieller Algorithmen (iterativ) auf Datenbestand abbilden – etwa für kontextuelles Suchen
Suchen: ankommende Suchanfragen aufbereitet an Datenserver übergeben, erhaltene Antworten passend formatiert an KundInnen zurücksenden

Web-crawler: Daten extrahieren

Rohdaten (HTML-Snippet): <p class="ui-state-highlight">
Übung: Muster mit <kbd class="ui-state-error">*</kbd> oder <KBD>?</KBD> ohne Kontext sind selten nützlich: <kbd>c*</kbd> bzw. <kbd>c?</kbd> passen auch zur leeren Zeichenkette – am Anfang jeder Zeichenkette enthalten!
</p>
Extrahierte Daten: übung muster mit oder ohne kontext sind selten nützlich bzw passen auch zur leeren Zeichenkette am anfang jeder enthalten
Algorithmus?: Wie sehen die notwendigen Arbeitsschritte aus?

Reguläre Ausdrücke

Reguläre Ausdrücke (regular expressions, regexp, regex): sind eine Beschreibungssprache für Textmuster – Notation mittels Zeichenliteralen und Metazeichen.
Zeichenliterale: stehen genau für sich selbst: Buchstaben, Ziffern, @, !, ...
Metazeichen: ^ $ . * + ? [ ] ( ) { } | \
Maskierung: Verwendung von Metazeichen als normale Zeichen ausschließlich durch vorgestelltes \
Maskierung auf der Kommandozeile: notwendig für alle regulären Ausdrücke mit Metazeichen
Entsprechung (match): Eine Zeichenkette und ein Muster passen zusammen, wenn die Zeichenkette ein Teilstück enthält, das genau dem Muster entspricht.
Präzision: Genauigkeit (specificity) für optimale Entsprechungen – zu wenige?
Empfindlichkeit (sensitivity) findet alle Entsprechungen – zu viele?
Die Länge regulärer Ausdrücke wächst mit zunehmender Genauigkeit.

RegExplorer Quiz

Maskierung nur zulässig in Mustern!

Zeichenkette	passende(s) Muster
Hallo
a5@3//2
`^`
&
`...`
`**+?`
`(`Hallo`)`
wer da`?`
`\`
`\|\|\|`
`{\`/`}`

Verhältnis der Länge der obigen Zeichenketten und passender Muster?

RegExplorer Zeichenmengen

Notation wie bei Shell-Globs mit den Metazeichen: [ ] ^ –

Menge	entspricht
`[`abc`]`	`a` oder `b` oder `c`
`[^`abc`]`	Komplement von `[abc]`: jedes Zeichen außer `a` oder `b` oder `c`
`[`a`-`z`]`	Bereich: alle kleinen Buchstaben
`[`a`-`zA`-`Z0`-`9`]`	Bereiche: alle alphanumerischen Zeichen
`•`	jedes Zeichen außer Zeilenumbruch (vordefiniert)

Mengen beschreiben zulässige Inhalte für genau eine Zeichenposition.

Muster	Zeichenkette	Beschreibung bzw. Entsprechung
`a.b`	123a5bd
	123a\\bd
	123a\bd
`a[0-9]b`	a12b
	@@@@@a1b??1b1b1b
		alle kleinen deutschen Buchstaben
		alle großen deutschen Buchstaben
`a[^g-z]b`	rra%bfff

Ein regulärer Ausdruck für fünf aufeinanderfolgende deutsche Buchstaben?

RegExplorer Wiederholungen [repetitions]

werden definiert durch nachgestellte Operatoren gebildet mit { , und }

Operator	Bedeutung	Beispiel
`{n,m}`	mindestens n, höchstens m	`YR[0-9]{2,5}abc`
`{n,}`	n oder mehr	`abc{2,}`
`{n}`	genau n	`1234[abc]{3}`
`?`	`{0,1}` : optional	`[+-]?`
`+`	`{1,}` : mindestens eines	`[+-]?[0-9]+`
*``**	`{0,}` : beliebig viele, auch keines	`<[^>]*>`

Wiederholungsoperatoren binden stärker als die Konkatenation – das Nebeneinanderschreiben. abc+ bedeutet ab gefolgt von mindestens einem c, nicht Wiederholungen von abc insgesamt.

Die Operatoren *, +, {n,m}, {n,} suchen maximal lange Übereinstimmungen ab der ersten Position, die eine Übereinstimmung lieferte (greedy).

Muster	Zeichenketten	Übereinstimmung
`<.*>`	<a href="#top">zum Anfang</a>
`<[^>]*>`	<a href="#top">zum Anfang</a>
`[+-]?[0-9]+`	a0-424242424999

Shell-Globs und Reguläre Ausdrücke

Zeichen	Shell-Globs	RegExp
`*`
`?`
`+`
`[...]`
`[^...]`
`.`
`{ }`

Quiz
# shell glob
# alle Namen in /bin/ mit einer Dezimalziffer am Ende
# shell glob
# alle Namen im Arbeitsverzeichnis mit einem `c` an dritter Stelle
# regexp
# `ab` gefolgt von optionaler Dezimalziffer
# regexp
# `a`, später ein `?`, später eine natürliche Zahl

sed sed + egrep

Reguläre Ausdrücke als Suchparameter
`egrep`	# fgrep mit extended regular expressions
`sed`	# mit Option `-E` (Linux kennt auch `-r`)

Befehl	Bedeutung
`egrep` Hallo	Suche nach allen Zeilen, die
`egrep "a.*b"`	Suche nach allen Zeilen, die
`sed -E "s/a{2,4}/`@`/g"`	`a{2,4}` durch `@` ersetzen
`sed -r "s/<[^>]*>//g"`	HTML-Tags durch Leerzeichen ersetzen
	alle ganzen Zahlen finden
	alle ganzen Zahlen durch `num` ersetzen.
	Wiederholungsperatoren `{n,m}` suchen

[H][e][l][l][o]

Hinweise zum Umgang mit regulären Ausdrücken.

Einfach halten: Ausdrücke so einfach wie möglich halten – A statt [A] oder \A
Schrittweise entwickeln: Nicht sofort lange Ausdrücke formulieren – schrittweise verfeinern mit häufigen Tests – auch manuell auf der Kommandozeile.
Testen auch mit: RegExplorer

RegExplorer Praktische Übungen ...

Zahlenbereich von 100 bis 999 in regulären Ausdruck abbilden und testen.

Gleitkommazahlen der Form 11,131 oder 1,234 mit nichtleeren Ziffernfolgen vor und nach dem Komma in regulären Ausdruck abbilden und testen. Können Sie führende Nullen überlesen?

MAC-Adressen der Form hh:hh:hh:hh:hh:hh mit Hexadezimalziffern h mit einem regulären Ausdruck beschreiben und testen. Hexadezimalziffern sind die Dezimalziffern ergänzt durch [A-Fa-f].

Exakte Übereinstimmung von Zeichenkette und regulärem Ausdruck bestimmen. n durch die Länge Ihres Nachnamens ersetzen.

Regexp	Zeichenkette
`[0-9][0-9]...[0-9]`	537e6a3789aee
`[0-9]{2,3}[^0-9]+e{2,}`	bca5545aeeeebeee5566777eee88
`[0-9]{2,3}[^0-9]+?e{2,}`	bca5545aeeeebeee5566777eee88
`c*`	abcc5cccccccc
`c?`	abcc5cccccccc
`c+`	abcc5cccccccc
`[0-9]{2,n}[^0-9]*e{4,}`	a55abe567ee889abecdeeeebeeeeedee
`[0-9]{2,n}[^0-9]*?e{4,}`	a55abe567ee889abecdeeeebeeeeedee

c* bzw. c? passen zur leeren Zeichenkette, die am Anfang jeder Zeichenkette enthalten ist! Ohne Kontext selten sinnvoll.

RegExplorer ... Praktische Übungen

more und less implementieren eine eigene Kommandozeile mit Befehlen wie etwa /regExp, n und q. Experimentieren Sie.

Strukturinformation in HTML-Code suchen. Etwa aus <li class="f"><p>Romeo and Juliet</p></li> <li>a</li> nur <li class="f"> isolieren und nicht die ganze Zeichenkette! Wie könnte man ganze Elemente finden?

Web-crawling für diese Webseite schrittweise durchführen mit Zwischendateien und visueller Kontrolle:

ganzen Inhalt auf Kleinschreibung normieren (tr)
alle Tags durch ein Leerzeichen ersetzen (sed)
HTML-Entities in Text umwandeln bzw. löschen mit sed -f Befehlsdatei
alle Wörter (Sequenzen aus Buchstaben) extrahieren (egrep -o)
doppelte Wörter löschen (sort, uniq)

Web-crawling manuell anwenden auf diese Webseite auf einer Kommandozeile mittels Pipes.

Non-greedy Suche auf Linux mit grep -P, falls ? den Operatoren *, + oder {n,} folgt (auf OSX nicht unterstützt; nicht bei sed). Suchen Sie interaktiv non-greedy nach ganzen li-Elementen mit Inhalt anhand der Zeichenkette <li> a < > </li> <li> > << >> </li>

reguläre Ausdrücke

Mengen

Wiederholungen

regular expression

sets

repetition

greedy repetition

non-greedy repetition

Reguläre Ausdrücke

Suchen im Web

Suchen in Daten

Web-crawler: Daten extrahieren

Reguläre Ausdrücke

RegExplorer Quiz

RegExplorer Zeichenmengen

RegExplorer Wiederholungen [repetitions]

Shell-Globs und Reguläre Ausdrücke

sed sed + egrep

[H][e][l][l][o]

RegExplorer Praktische Übungen ...

RegExplorer ... Praktische Übungen

syslog

Unix