Kryptologie Buchstabenhäufigkeiten stochastischer Sprachen

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

Einleitung

Es ist eine empirische Beobachtung, dass der Koinzidenzindex κ(a,b) für »natürliche« Sprachen fast eine Konstante ist.

Z. B. ist κ(a,b) ≈ 0.0762 für gleich lange deutsche Texte, wenn deren Länge r genügend groß ist (etwa > 100).

Der entsprechende Wert für Englisch ist 0.0661.

Welche statistischen Eigenschaften »natürlicher« Sprachen liegen derartigen Phänomenen zu Grunde?

Bei der statistischen Kryptoanalyse der monoalphabetischen Substitution wurde die (empirisch genügend gesicherte) Annahme verwendet, dass die durchschnittliche Häufigkeit des Buchstabens s ∈ Σ in genügend langen Texten einer solchen Sprache nahe bei einem Wert p_s liegt. Dies gilt auch, wenn man nur eine beliebige feste Stelle j betrachtet, zumindest für die meisten j - die Anfangsbuchstaben von Texten haben durchaus abweichende Häufigkeiten.

Sei also M ⊆ Σ^* eine Sprache, M_r = M ∩ Σ^r für r ∈ N.

Die durchschnittliche Häufigkeit von s ∈ Σ an der Stelle j ∈ [0 … r-1] für Texte in M_r ist

(Die Summe zählt die a ∈ M_r, an deren j-ter Stelle s steht.)

Beispiel

Sei M = Σ^*. Dann ist

(Es gibt genau n^r-1 mögliche Texte, wenn a_j = s festgehalten wird.)

Definition

Die Sprache M ⊆ Σ^* heißt stochastisch, wenn es eine endliche Ausnahmemenge J ⊆ N gibt, so dass für alle j ∈ N-J und alle s ∈ Σ

gleichmäßig in j existiert und unabhängig von j ist.

Die p_s heißen die Buchstabenhäufigkeiten von M.

Bemerkungen und Beispiele. 1.) Die Ausnahmemenge J besteht bei »natürlichen« Sprachen meist nur aus der Stelle 0; d. h. an der Anfangsposition von Texten darf die Buchstabenverteilung abweichen. Z. B. ist im Deutschen das »e« nicht der häufigste Anfangsbuchstabe eines Textes.

2.) Die Sprache M = Σ^* ist stochastisch.

3.) Da stets ∑_s∈Σ μ_sj^(r) = 1, folgt ∑_s∈Σ p_s = 1.

Achtung. Diese Definition ist in der Literatur nicht üblich. Dort werden meist viel stärkere Einschränkungen gemacht.