Mustersuche mit Perl

Kryptologie

Mustersuche mit Perl

a7Hzq .#5r< kÜ\as TâÆK$ ûj(Ö2 ñw%h: Úk{4R f~`z8 ¤˜Æ+Ô „&¢Dø

Vorbereitung: Numerische Muster zu Zeichenketten

Definition. Sei Σ ein Alphabet. Seien a₁, ..., a_q Zeichen aus Σ. Das zur Zeichenkette (a₁,...,a_q) gehörige Muster (n₁,...,n_q) ∈ N₁^q ist die Liste von Zahlen, die so gebildet wird:

n₁ := 1.
Für k = 2, ..., q:
Gibt es ein i mit 1 ≤ i < k und a_k = a_i, so n_k = n_i;
sonst n_k := 1 + max{n_i | 1 ≤ i < k}.

Beispiel: Zu REGENBOGEN gehört das Muster 1232456324.

Bemerkungen.

n_i = n_j ⇔ a_i = a_j für 1 ≤ i ≤ j ≤ q.
{n₁, ..., n_q} = [1..m] mit m = #{n₁, ...,n_q}
[= Anzahl der verschiedenen Zeichen in (a₁,...,a_q)].

Algorithmus

Ziel: Zu einer Zeichenkette das numerische Muster ermitteln.

Eingabe: Zeichenkette als Liste string = (a₁,...,a_q).

Ausgabe: Numerisches Muster als Liste pattern = (n₁,...,n_q).
Vorbesetzung: leere Liste.

Hilfsvariablen:

n = aktuelle Nummer; Vorbesetzung: n = 0.
assoc = Liste der abgearbeiteten verschiedenen Zeichen;
dem Index i entspricht das Zeichen assoc[i];
Vorbesetzung: leere Liste.

Prozedur:
   Schleife über die Zeichen von string; aktuelles Zeichen ist x:
      Falls es i gibt mit x = assoc[i]
         hänge i an pattern an;
      sonst:
         inkrementiere n,
         hänge n an pattern an;
         hänge x an assoc an.

Ein Perl-Programm, das dieses umsetzt, steht hier. Es dient nur zum Verständnis des folgenden, komplizierteren Programm und wird sonst nicht weiter benötigt.

Aufbau eines regulären Suchausdrucks für ein Muster

Die Mustersuche mit Perl funktioniert am knappsten mit sogenannten regulären Ausdrücken. Hier das Minimum zum Verständnis des entsprechenden Programms:

Suchausdruck	Wirkung

`/./`	passt auf das erste Zeichen (falls die Zeichenkette nicht leer ist).
`/(.)/`	passt auf das erste Zeichen und weist es der Variablen `$1` zu.

`/../`	passt auf die ersten beiden Zeichen.
`/(..)/`	passt auf die ersten beiden Zeichen und weist sie als Zweierzeichenkette der Variablen `$1` zu.
`/(.)(.)/`	passt auf die ersten beiden Zeichen und weist sie einzeln den Variablen `$1` und `$2` zu.

`/(.)\1/`	passt bei beliebigem ersten Zeichen und mit ihm identischen zweiten Zeichen. [Das erste Zeichen wird der Variablen `$1` zugewiesen; diese wird innerhalb des Suchausdrucks mit `\1` bezeichnet.]
`/(.)(?!\\1)/`	passt auf die ersten beiden Zeichen, falls das zweite ungleich dem ersten ist, und weist sie einzeln den Variablen `$1` und `$2` zu.

`/(.)(.)\1(.)\1/`	Muster 12131, falls verschiedene Zahlen nicht notwendig verschiedene Zeichen bedeuten sollen.
`/(.)(?!\\1)\1(?!\\1\|\\2)\1/`	Muster 12131, falls verschiedene Zahlen verschiedene Zeichen bedeuten sollen.

Mustersuchprogramm

Das fertige Programm im typischen, hochkondensierten Perl-Stil, ist hier zu finden.

Übungsaufgabe. Versuche, das Programm zu verstehen.

Online kann man es über ein WWW-Formular zur Suche in einem Wörterbuch oder einem einzugebenden Text aufrufen.

Übungsaufgabe. Probiere das aus.

Autor: Klaus Pommerening, 29. Oktober 1999; letzte Änderung: 31. Oktober 2004.