Inhaltsverzeichnis

1  Freie Lizenz  3

1.1  Urheberklausel  3

1.2  Benutzung durch Leser  3

2  Einf uhrung  4

2.1  Definition  4

2.2  Verwendbarkeit  4

2.3  Nutzen  5

3  Diskret bin are Verteilung.  

Entstehung  und abgeleitete Funktionen  6

3.1  Hauptstring und Teilstrings  6

3.2  Kettenkodierung und bin are Referenz  7

3.3  Funktion N (k) und sukzessive K N (k) 1 N (k) h K -  

Reduktion   8

3.4  P -Elimination und wahlfreie T n K n -Reduktion  12

3.4.1  Funktion K(n)  13

3.4.2  Wahlfreier T n K n -Ausschluss  16

4  Programmatische Implementierung  16

4.1  Das Programm Token  16

4.2  Programmdesign  17

4.3  Vorgehensweise bei der Palindromsuche  19

4.4  Funktion GibtsSatz()  20

5  Anhang  21

5.1  Quellcode der Funktion GibtsSatz()  21

5.2  Palindrombeispiele  22

2

1 Freie Lizenz

1.1 Urheberklausel

Der Autor versichert ausdr¨ ucklich, dass die in diesem Artikel abgehandelten Zusammenh¨ ange, Daten und Erkenntnisse, falls nicht anders gekennzeichnet oder zitiert, Produkt seiner eigenen geistigen Sch¨ opfung darstellen und nach bestem Wissen und Gewissen ohne Verletzung oder stillschweigende Ausnutzung der Patent- oder Urheberrechte Anderer verfasst worden sind.

1.2 Benutzung durch Leser

Alle Daten dieser Abhandlung, sofern sie kein Zitat sind, d¨ urfen f¨ ur private, Forschungs-, Ausbildungs- und Lehrzwecke FREI kopiert, ver¨ andert, gespeichert und weitergegeben werden. Bei der Weitergabe, der Vervielf¨ altigung und der ¨ offentlichen Vorf¨ uhrung des Werkes oder seiner Teile muss jedoch ein jedes Kopieexemplar bzw. Zitat einen deutlich lesbaren oder bei den nicht-visuellen Medien anderweitig unverkennbaren Verweis auf den vollen Namen des Verfassers oder seine E-Mail-Adresse fedorowski@web.de beinhalten. Falls Ver¨ anderungen am Quelltext vorgenommen sein sollten, ist dies gesondert zu vermerken. Das freie Nutzen des Werkes f¨ ur kommerzielle Zwecke ist unter Einhaltung der Autorenreferenz und nach einer kurzen Benachrichtigung des Autors ¨ uber die Art des Nutzens grunds¨ atzlich gestattet.

Der Autor beh¨ alt sich jedoch das Recht vor, in Ausnahmef¨ allen das kommerzielle Nutzen des Artikelinhaltes zu untersagen oder nur unter zus¨ atzlichen Bedingungen zu genehmigen. Diese Lizenzbedingungen erstrecken sich auch auf die verfassereigene Demonstrationssoftware, auf die im Artikel verwiesen wird, und die kostenlos heruntergeladen werden kann. Bei der Herstellung eigener Daten, Produkte und Medien durch Dritte unter der Anwendung der im Artikel oder der Begleitsoftware festgehaltenen Prinzipien, Schemen, Ideen und anderen Inhalten besteht ebenfalls eine Autorenreferenzpflicht.

3

2 Einf¨ uhrung

2.1 Definition

Als Diskret-Bin¨ are-Verteilung wird hier eine Abbildung der Menge T , deren Elemente Teilzeichenfolgen der definierten Hauptzeichenfolge sind, auf die Menge K, deren Elemente Ketten ((1, ..., h)-variable Tupel) der Teilzeichenfolgen sind, die exakt die Hauptzeichenfolge bilden, bezeichnet.

2.2 Verwendbarkeit

Diese Verteilung ist einer Untersuchung Wert, wenn z.B. innerhalb von Zeichenfolgen ohne Trennzeichen automatisiertes Suchen nach semantisch existenten S¨ atzen und anderen Textfragmenten mittels einer großen bis sehr großen externen Wortliste oder einer datenbank¨ ahnlichen Struktur vorgenommen wird, wobei die Teilzeichenfolgen auf ihre Eigenschaft als W¨ orter oder andere sinnergebende Strukturen gepr¨ uft werden. Um den rechnerischen Auf-wand kleinstm¨ oglich zu halten (non-redundante Suche), werden alle Ketten (potentiellen S¨ atze), die ein nicht-existentes Wort enthalten w¨ urden, fr¨ uhzeitig dank negativer Referenz- ¨ Ubergabe f¨ ur dieses Wort (Teilzeichenfolge) nach nur einer Wortsuche und Zuordnung des Booleschen Parameters ausgeschlossen. Diese Referenz¨ ubergabe bedient sich nicht des Inhaltes der Zeichenfolge selbst, wie es im Falle der rechnerisch aufwendigeren repetitiven Wert¨ ubergabe beim konsekutiven Vergleich w¨ are, sondern vielmehr der festgelegten sequentiellen Anordnung N der T -Elemente in der auf Grund ihrer Position und L¨ ange innerhalb der Hauptzeichenfolge, die man als eigenst¨ andige Funktion N (k) f¨ ur die Validation der Ketten ressourcensparend benutzen kann. Auf diese N -Folge wird aus der besagten T → K Abbildung geschlossen.

4

Dasselbe Prinzip kann man unter Gleichstellung des Trennzeichens mit einem beliebigen Zeichen oder Zeichenfolge f¨ ur die Rekonstruktion der besch¨ adigten oder unlesbaren Textfragmente verwenden.

2.3 Nutzen

Eine Implementierung von diskret bin¨ arer Verteilung in reiner oder abge-wandelter Form k¨ onnte in diversen Algorithmen und Verfahren von Vorteil sein: Kryptologische Ver- und Entschl¨ usselung, Experimente in der IT-Linguistik, Erzeugung von Korrekturvorschl¨ agen und intelligente Suchoptionen in der Textverarbeitung, Suchmachinendesign, Entwerfen von Spielen, mehrdimensionale Logik, fehlertolerante Perzeption in der k¨ unstlichen Intelligenz, Durchsuchen von genetischen Sequenzen u. ¨ A.

Nach der Beschreibung der Eigenschaften der diskret bin¨ aren Verteilung handelt es sich in diesem Artikel um ihre Verwendung in einem Spezialfall. Ein Palindrom-Suchprogramm f¨ uhrt u.a. Wortpaarvergleiche durch, auf das Vorkommen des k¨ urzeren Wortes im inversen String des l¨ angeren. Dabei entstehen Zeichenfolgenbruchst¨ ucke, die ihrerseits auf Existenz als W¨ orter, Wortteile oder Wortfolgen gepr¨ uft werden. (1)

SARGNAGEL Wort 1

−→

Wort 2 GRAS

LEGANGRAS inverser String des l¨ angeren Wortes

←−

LEGANGRAS Wort 2 gefunden? JA

LEGAN

L

LE

LEG

LEGA

LEGAN

E

EG

EGA

EGAN

G

GA

GAN

A

AN

N

Start 1 → L¨ ange 3 → Start 4 → L¨ ange 2 ⇒ L¨ ange 5

Ergebnis: JA 3-14-Wort2 : LEG AN GRAS

Da eine mitteleurop¨ aische Sprache mit einem m¨ aßigen Anteil an Beu-gungsformen, zusammengesetzten W¨ ortern, Pr¨ afixen, Endungen und anderen

5

grammatikalischen Varianten schnell eine Wortliste mit ¨ uber 500.000 Eintr¨ a-

gen bedeuten kann, liegt die Anzahl der einfachen Durchl¨ aufe der Vergleichssubroutine schon bei

So wird von allen Eigenschaften derartiger Programme der Grad an Redundanz-Reduktion eine der wichtigsten.

3 Diskret bin¨ are Verteilung.

Entstehung und abgeleitete Funktionen

3.1 Hauptstring und Teilstrings

F¨ ur einen Hauptstring (Hauptzeichenfolge) H der L¨ ange h bilden sich v Teilstrings T n(a,t) der L¨ ange t 1 bis t h mit Positionen ihres ersten Zeichens a 1 bis a h innerhalb des H. Sortiert man die T n(a,t) aufsteigend nach ihren a (Kriterium 1) und t (Kriterium 2) in einem Datenfeld T() und nummeriert sie konsekutiv, so erh¨ alt man eine Folge der v nat¨ urlichen Zahlen von n = 1 bis n = v, wobei jedes n einen Teilstring T n(a,t) eindeutig identifiziert. Das Auffinden von Teilstrings und das gleichzeitige Sortieren nach a, t- Kriterienerfolgt mit dem Algorithmus (2).

(2)

n = 0 Von a = 1 Bis h Von t = 1 Bis h - a + 1 n = n + 1

T(n) = [Teilstring aus]([String]H, [Start]a, [L¨ ange]t) N¨ achstes t N¨ achstes a

Aus (2) folgt f¨ ur die Anzahl v der m¨ oglichen Teilstrings:

(3) besagt, dass die Anzahl aller Teilstrings und somit die obere Grenze des T() gleich Summe aller nat¨ urlichen Vorg¨ anger der Hauptstringl¨ ange und

6

ihr selbst ist.

Beispiel: 1

Der Hauptstring H lautet {einKnie}

h = 7 ist seine L¨ ange 7 a=1 a = ⁷⁽⁷⁺¹⁾ v = = 28. Es gibt 28 Teilstrings aus H.

2

Teilstrings (Auswahl): T 3(1,3) = {ein} n = 3 a = 1 t = 3 T 8(2,1) T 13(2,6) = {inKnie} T 22(4,4) = {Knie} n = 22 a = 4 t

= 4 3.2 Kettenkodierung und bin¨ are Referenz

Stellt man sich H als eine Kette K k aus passenden T n(a,t) vor, kann man alle u m¨ oglichen Anordnungen von T n(a,t) in u K k -Varianten mit bin¨ aren Zahlen der L¨ ange h − 1 codieren, wenn man von links nach rechts, angefangen mit

dem zweiten Teilstring, die Bits Nr. a−1 mit “0” und die ¨ kennzeichnet. Der ” aufgef¨ ullt. Zum Beispiel: Die Bin¨ arzahl 58 ergibt eine Sequenz “111010”:

Die eine Null steht an der Position 4, somit w¨ are der Anfang des zweiten Teilstrings a = 4 + 1 = 5, und seine L¨ ange - die Anzahl der darauffolgenden “1” plus 1, sprich t = 1 + 1 = 2. ¨ Ahnlich a = 7 und t = 1 f¨ ur den letzten

Teilstring. Da der erste Teilstring nie fehlt, wird sein a = 0 + 1 = 1 stets angenommen und seine L¨ ange t w¨ are in diesem Fall 4. Also codiert die Zahl

¹ Vgl. {LEGAN} in der Aufstellung (1), Seite 5. Dort h = 5, v = 15

7

58 einen H oder eine Kette K 58 , die aus T n(1,4) = {einK}, T n(5,2) = {ni} und T n(7,1) = {e} zusammengesetzt ist. Um f¨ ur diese Teilstrings ihre Ordinalzahlen n zu finden (in diesem Beispiel 4, 24 und 28), hatte man bis jetzt nur die M¨ oglichkeit des konsekutiven Stringvergleiches nach L¨ ange und Anfangszeichen mit schlimmstenfalls allen Elementen des Datenfeldes T(). Um dies zu ¨ andern, betrachten wir die Menge K genauer: Die Gesamtanzahl von nat¨ urlichen Bin¨ arzahlen mit h − 1 Stellen und kleiner (bei diesen werden f¨ uhrende Nulls angeh¨ angt), betr¨ agt 2 ^h−1 . Also, es ergeben sich u = 2 ^h−1 Kettenvarianten K k aus dem Hauptstring H, wobei die Abbildung deren aufsteigender Folge K{k} = {1, . . . , u} auf die Menge N {n} = {1, . . . , v} von weiterem Interesse ist (5).

f : K{k} = {1, . . . , 2 ^h−1 } −→ N {n} = {1, . . . ,

3.3 Funktion N (k) und sukzessive {K → N (k) 1 . . . N (k) h →

K}- Reduktion

Tragen wir eine kleine Matrix zusammen, aus 16 mit Schritt 1 abnehmenden f¨ unfstelligen Bin¨ arzahlen, von 2 ⁵ − 1 = 31 ≡ 11111 bis 2 ⁴ = 16 ≡ 10000.

Und nun setzen wir f¨ ur jede “1”er Komponente der Matrix (6) ein nach der Codierung aus [3.2, S. 7] passenden T n(a,t) Element mit Ursprung in einem 5-Stelligen Hauptstring (h = 5) ein. Da die a und t von T n(a,t) aus der Position

8

in der Matrix ersichtlich sind, kann man diese auslassen und nur die n-Zahlen einsetzen. Zur Erinnerung: n ist desto kleiner, je, erstens, kleiner das a und je, zweitens, kleiner das t ist. Vielleicht k¨ onnen wir aus dieser Matrix auf die Abh¨ angigkeit der n-Zahlen von der Zeilennummer j, die der Zahl k der K k -Elemente entspricht, und der Spaltennummer i - Position innerhalb der Kette schließen.

Matrix f BIN (ij) ∼ = n(p, k) (ByRef ) (7)

N (k) ← P, K. Obwohl diese Relation rechts zwei Argumente hat, wird bei der sp¨ ateren Referenz¨ ubergabe jede Spalte durchgegangen, so dass der Positionsparameter p als

Tats¨ achlich f¨ allt es auf, dass in den Spalten der Matrix (7) mit steigendem k eine einfache, um Schritt 1 zunehmende Zahlenfolge mit einer geometrisch abnehmenden doppelt-repetitiven Anordnung der n-Zahlen zur Basis 2 stattfindet, und in den Zeilen - eine arithmetische Folge mit dem aus der vorherigen Spalte stammenden Augenden und dem um Schritt 1 abnehmenden Addenden.

9

Angesichts dessen kann man versuchen, f¨ ur die Funktion N (k) zu einer beliebigen Kettenposition p = {1, . . . , h} eine Formel zu bilden. Die untere L und die obere U Grenze des n-gleichen k-Spaltenbereiches k(x) scheint f¨ ur die Spalte eins (p = 1) trivial bestimmbar zu sein:

L[k(x)] 1 = 2 ^h−1 − 2 ^h−x + 1 U [k(x)] 1 = 2 ^h−1 − 2 ^h−x−1 und (8)

wo x - die Ordnungsnummer des n-gleichen Spaltenbereiches ist. Jeder nachfolgende Spaltenbereich verh¨ alt sich wie die untere H¨ alfte des vorangehenden kontinuierlichen Spaltenbereiches, zuz¨ uglich Erh¨ ohung der Glieder um h − p + 1, und 2 ^h−1 kann man f¨ ur weitere Spalten als 2 ^h−p verallgemeinern. Im voraus sei vermerkt, dass der k-Nummerierung von 1 bis 2 ^h−1 auf jeden Fall 0 bis 2 ^h−1 − 1 vorzuziehen ist, denn das wird sp¨ ater die Definition des Funktionsbereiches N (k) vereinfachen. Angesichts dessen haben wir

L[k(x)] p = 2 ^h−p − 2 ^h−p+1−x U [k(x)] p = 2 ^h−p − 2 ^h−p−x − 1 (9) und

Das n vom n-gleichen k-Glied x nimmt abh¨ angig von der Position p Werte an, wie f¨ ur x = 1 → {1; 6; 10; 13; 15}, x = 2 → {2; 7; 11; 14} usw. Es bilden sich Folgen vom Typ

{x, x + h − 0, x + h − 0 + h − 1, x + h − 0 + h − 1 + h − 2, x + . . . h − h} so dass es zusammenfassend gilt

Substituieren wir nun x in den Gleichungen (9), so k¨ onnen wir die untere und die obere Grenze des n-gleichen K-Bereiches abgesehen von p ausschließlich durch n definieren, allerdings zun¨ achst nur f¨ ur die erste der vertikal repetitiven K-Reihen:

k L1 = 2 ^h−p − 2 p(h− p−1

Es bilden sich in sp¨ ateren Positionen mit immer k¨ urzeren K-Reihen logischerweise auch immer mehr von deren senkrechten Wiederholungen, in der Matrix (7), Position 5, z.B. gleich vier 13;14-Sequenzen. Um diese auch durch n zu definieren, beachten wir, dass pro Position die Anzahl der Repetitionen 2 ^p−2 ist, und daher die Anzahl der Repetitionsglieder

10

davon ist die H¨ alfte leer. Jedes k in der Repetition unterscheidet sich von seinem Grundabbild k L...U 1 durch einen Zusatz Z K , der der Repetitionsnummer von 0 bis 2 ^p−2 − 1 (Aufrundung wegen 2 ⁻¹ -M¨ oglichkeit) mal 2 ^h−p+1 entspricht:

Aus (15) folgt, dass ein beliebiges k seinem Grund-k 1 modulo 2 ^h−p+1 kongruent ist:

k ≡ k 1 (mod 2 h−p+1 ) (16)

Wir k¨ onnen die Modulo-Funktion

k mod 2 h−p+1 := k 1 (17)

sp¨ ater als einen Term der N (k) Funktion sehr gut gebrauchen, doch jetzt, da die Gleichung (17) injektiv, also in der obigen Schreibweise linkstotal und rechtseindeutig ist, schreiben wir lieber die K-Definitionsbereiche auf gew¨ ohnliche Weise aus, weil wir m¨ oglicherweise noch K(. . .) Funktionen ben¨ otigen werden:

K L = 2 h−p − 2 p(h− ^p−1 2 )−n + {0, . . . , 2 p−2 − 1} · 2 h−p+1 (18)

K U = 2 h−p − 2 p(h− ^p−1 2 )−n−1 − 1 + {0, . . . , 2 p−2 − 1} · 2 h−p+1 (19) Nun sind wir dem eingentlichen Zwischenziel, n durch k auszudr¨ ucken, entschieden n¨ aher gekommen. Auf Grund der Injektivit¨ at von (17) und dadurch, dass es sich bei K L und K U um n-gleiche Glieder handelt, werfen wir eine folgende Simplifizierung in den Raum:

Wir gehen einfach davon aus, dass der Wert des niedrigsten k-Gliedes im n- gleichenBereich vollkommen gen¨ ugt, um in einer logarithmischen Funktion den gesamten Bereich pr¨ azise auf N abzubilden. Nach Umformung von (20) und Ausdr¨ ucken von n bekommen wir eine bequeme Arbeitsformel, die dem Computer schnell ” klar macht“, in welchen K welche n und daher auch T ⁿ vorkommen:

Rechentests mit gr¨ oßeren Matrizen mit h ¨ uber 20 best¨ atigten Formel 21.

Die Gauß’sche Klammer rundet Mantissen herunter, und die Funktionswerte entsprechen den tats¨ achlichen n-Gr¨ oßen in p-Positionen der jeweiligen Kette, deren Nummern k als Argumente an die N (k)-Funktion ¨ ubergeben werden.

Die leeren n-Werte entsprechen dem Berech, wo log 2 nicht definiert oder unendlich klein ist.

Formel (21) kann zum sukzessiven Ausschluss von nicht-sinnergebenden K-Sequenzen anhand von Registrierung einer der nicht in der Wortliste vorkommenden Teilstrings T n in der jeweiligen k-Kette, indem Positionen n ¹ bis n h bestimmt, und die dabei entstehenden n gleich im bereits angelegten Booleschen Datenfeld auf ” Vorkommen: JA“ oder ” Vorkommen: NEIN“ gepr¨ uft werden.

3.4 P -Elimination und wahlfreie {T n → K n }-Reduktion Eine weitere Steigerung der Programm-Effizienz kann durch eine p-unabh¨ angige Bestimmung aller N -Glieder der K-Kette erreicht werden, was prinzipiell m¨ oglich sein m¨ usste, da n-Werte p-eindeutig sind. Außerdem sind sie gleichsinnig steigend, so dass die Reihenfolge in der Ausgabe kein großes Problem bereiten w¨ urde. Eine Herausforderung w¨ are allerdings, einen Ausdruck zu finden, der einen schnellen Zugriff auf s¨ amtliche K erlaubt, in denen ein bestimmtes N vorkommt, um das Durchgehen der Ketten, die auf Grund von

12

in der Vergleichsliste nicht-existenten Teilstrings keinen Sinn ergeben, von vornherein auszuschließen.

3.4.1 Funktion K(n)

Das Substituieren von p in (18) und (19) gelingt, wenn man sich die Verteilung von n auf p in einer Matrix ansieht.

Zwecks besserer Anschaulichkeit betrachten wir beispielsweise die n-Verteilung bei einem Hauptstring von 7 Elementen L¨ ange.

In der Matrix 22 verteilen sich n p,x folgendermaßen:

n 1,x = {1, . . . , h}

n 2,x = {h + 1, . . . , h + (h − 1)}

n 3,x = {h + (h − 1) + 1, . . . , h + (h − 1) + (h − 2)}

n 4,x = {h + (h − 1) + (h − 2) + 1, . . . , h + (h − 1) + (h − 2) + (h − 3)}

. . .

n h,1 = {h + (h − 1) + (h − 2) + . . . + (h − (h − 1))}

(23)

So dass es f¨ ur das gr¨ oßte n der p-gleichen Reihe n max gilt

Die beiden L¨ osungen der Gleichung (25) sind

Die q 1,2 nehmen Ganzzahlwerte bei n max (q) an, die das Schlußglied jeder Verteilungsreihe bilden, und abnehmende reele Werte zwischen zwei ganzen Zahlen q 1,2 und q 1,2 1, wenn man als Argument anstelle von n max einen beliebigen n-Wert zwischen n max (q 1) und n max (q) einsetzt. Vgl. bei h = 7: n q 1

18 5 19 4,77 -3.77 20 4,53 -3,53 21 4,27 -3,27 22 4 -3 Verwenden wir die Gauß’sche Klammer nur f¨ ur die L¨ osungen q 1 und ersetzen q wieder, so erhalten wir exakt den p(n)-Wert:

bei a ∈ N und b ∈ R gilt a − b = a − b ∴

Setzen wir nun (27) in (18) und (19) ein.

2 ^h−p = 2 h−h−−0,5−

2 ^h−p = 2 −−0,5− 0,25−2n+h(h+1)

bei a ∈ Z und b ∈ R gilt a − b = a − b ∴ 0 − 0, 5 − 0, 25 − 2n + h(h + 1) =

14

2 p(h− p−1

2 p(h− p−1

2 p(h− p−1

(32)

. . . und erhalten eine diskrete p-unabh¨ angige K(n)-Funktion, die aus zwei Unterfunktionen besteht, die f¨ ur jedes n die untere (K L ) und die obere (K U ) Feldgrenze vorgeben, mit entsprechender Anzahl von Feldwiederholungen: K L

√ ^{0,25−2n+h(h+1)−0,5} − √ √

− 2

+ {0, . . . , 2 h+1,5+

√ ^{0,25−2n+h(h+1)−0,5} − √ √

− 2

+ {0, . . . , 2 h+1,5+

(34)

Per analogon zu (17) bis (20) ergibt sich auch eine Gleichung (35) f¨ ur die N (k)-Funktion ohne Vorkommen von p, allerdings ist sie unbrauchbar, da das n als ein Teil der

Modulofunktion ¨ uber k vorkommt. Um es zu eliminieren, w¨ urde man p durch k definieren m¨ ussen, was sich vom Aufwand her nicht lohnt, da bei den recht ¨ eine solche Formel rechnerisch viel komlizierter sein w¨ urde, als eine programmatische Anweisung, alle p von 1 bis h mit der Formel (21) durchzugehen.

15

D

3.4.2 Wahlfreier {T n → K n }-Ausschluss

Nun ergibt sich eine Alternative zum sukzessiven K-Ausschluss, allerdings mit rechnerisch etwas komplexeren Formeln (33) und (34). Welcher Algorithmus geeigneter ist, ist nach der jeweiligen Eingangsdatenkonstellation zu entscheiden. Z.B. w¨ are bei gr¨ oßeren h vielleicht der wahlfreie Ausschluss vorzuziehen und umgekehrt.

Beim wahlfreien Ausschluss werden f¨ ur jeden beliebigen n-Wert gleich die obere, die untere k-Grenze und ggf. k-Bereichswiederholungen bestimmt, so dass als Ergebnis alle k registriert werden, die dieses n beinhalten, und k¨ onnen, falls das n ” sinnlos“ ist, en bloc ausgeschlossen werden.

4 Programmatische Implementierung

4.1 Das Programm Token

Auf http://public.box.net/fedorowski im Ordner ” my software“ findet der

Leser ein Beispielprogramm zum kostenlosen Herunterladen. Das Programm heißt Token (Benutzeroberfl¨ ache auf Englisch) und ist ein Sammeltopf f¨ ur diverse Werkzeuge, die f¨ ur quantitativ-linguistische und andere kreative Zwecke n¨ utzlich sind. Das Programm ist ein quelloffenes Projekt, und es werden laufend neue Funktionen hinzugef¨ ugt. Bereits vorhanden sind:

• Palindromsuchprogramm

• Pr¨ ufen einzelner Sequenzen auf Palindromf¨ ahigkeit anhand der (l¨ angeren) Wortliste (ab Vers. 1.0.0.8)

• komfortabler Zufallszahlgenerator

• Bin¨ ar-Dezimal-Konverter f¨ ur große Zahlen

• Zeitrechner

16

• Tool zum Umschreiben bin¨ arer Dateien in Textdateien mit ihren Bytewerten und zur¨ uck

• Werkzeuge zur Manipulation von Textdateien und Listenerstellung f¨ ur die Palindromsuche:

- String-Ersetzung

- Erstellen der Liste aller in einem Text vorkommenden W¨ orter

- Anpassen der Wortliste durch Hinzuf¨ ugen oder Entfernen definierter Eintr¨ age

- Elimination von Doppeleintr¨ agen

- wahlweise Groß-/Kleinschreibungssensitive oder reverse Sortierfunktion

- alle Operationen k¨ onnen in Unicode oder in regionalspezifischen Textcodierungen vorgenommen werden

- Erstellen der Wortlisten mit R¨ uckw¨ artssequenzen der normalen W¨ orter (ab Vers. 1.0.0.8)

Token wurde in VB.NET 2005 geschrieben und l¨ auft auf Windows XP.

Zum Installieren lade man die Archivdatei ” unter, entpacke und f¨ uhre die im Archiv befindliche Datei ” M¨ oglicherweise wird man aufgefordert, wenn auf System nicht vorhanden, das .NET Framework 2.0 von der Microsoft-Website herunterzuladen und zu installieren.

Nach dem Programmstart w¨ ahle man den Button WM( Word Master“), es

”

erscheint ein Fenster mit diversen Schaltfl¨ achen, Textboxen und Listen. Hat man eine Textdatei mit einer Wortliste erstellt, bet¨ atige man den Button Palindrome search“, um diese auf Palindrome zu untersuchen.

”

Der Leser bekommt auf Anfrage (fedorowski@web.de) auch den Quellcode und alle sonstigen Quelldateien. Der Code ist mit deutschsprachigen Kommentaren versehen. Der Autor ist gerne bereit, Fragen zu beantworten und einzelne Aspekte zu diskutieren.

4.2 Programmdesign

Der Aufbau des Palindromsuch-Unterprogamms von Token setzt sich aus folgenden Schritten zusammen:

1. Zuerst wird die Textdatei eingelesen, die als Wortliste dienen soll, und in der jede Textzeile ein Wort darstellt.

17

2. Jeder Eintrag (Wort) dieser Liste wird einem Glied des String-Arrays (Datenfeldes) Wort([Anzahl der Eintr¨ age]) zugewiesen. 3. Die alphanumerisch sortierten Glieder werden in Bereiche je nach Anfangsbuchstabe eingeteilt, und die Referenzarrays KarteiX() werden erstellt, um die Wortsuche einzugrenzen und dadurch zu beschleunigen.

4. Die Ausgabe-Textdatei, die die Palindromvorschl¨ age enthalten soll, wird per Dialogfeld angelegt.

5. Der Benutzer wird aufgefordert, den Arbeitsmodus zu bestimmen. Dieser gibt vor:

(a) wieviele W¨ orter die zu testende Sequenz enthalten soll, von 1 bis

(b) ob der sog. ”

6. Anschließend startet die Palindromsuche, dabei wird die R¨ uckw¨ artssequenz eines jeden Wortes der Wortliste (oder der Sequenz eines jeden Wortpaares, -Drillings oder -Vierlings je nach Arbeitsmodus) an die Funktion GibtsSatz() ¨ ubergeben, die den Kern des Programms bildet.

Die Funktion gibt, falls gefunden, die S¨ atze zur¨ uck, die die R¨ uckw¨ artssequenz beinhalten kann. In die Ausgabedatei wird ggf. die Testsequenz, das Trennzeichen ” =<>=“ und die komplement¨ aren S¨ atze, getrennt

18

durch ” /“ zeilenweise geschrieben, z.B. relativ =<>= vi tal er /vi taler /vital er /vitaler

4.3 Vorgehensweise bei der Palindromsuche

Eine gute Wortliste ist f¨ ur die Palindromkreation immens wichtig. Je l¨ anger ein Palindrom ist und je mehr Sinn der Palindromsatz ergibt, desto wertvoller ist es. Um f¨ undiger zu werden, ist man zwar auf die Verarbeitung von sehr umfangreichen Wortlisten angewiesen, aber das bedeutet, erstens, l¨ angere Berechnungszeiten, zweitens, gr¨ oßere Ausgabelisten, die viel Unbrauchbares beinhalten und zuweilen langwierige Nachbearbeitung erfordern, und drittens, sind dabei die Arbeitsmodi 3 und 4 illusorisch. Die Zusammensetzung der Wortliste ist auch extrem wichtig. Logisch ist es, auf einzelne Buchstaben als eigenst¨ andige W¨ orter und bestimmte kurze, selten vorkommende W¨ orter zu verzichten, sonst ist die Ausgabe voll von Ergebnissen wie:

nassrasierer =<>= re re is ar s s an /re re is ar s san /re re is ar ss an /re re is ars s an /re re is ars san /re re isar s s an /re re isar s san /re re isar ss an /re rei s ar s s an /re rei s ar s san /re rei s ar ss an /re rei s ars s an /re rei s ars san /re reis ar s s an /re reis ar s san /re reis ar ss an /re reis ars s an /re reis ars san /rer ei s ar s s an /rer ei s ar s san /rer ei s ar ss an /rer ei s ars s an /rer ei s ars san /rer eis ar s s an /rer eis ar s san /rer eis ar ss an /rer eis ars s an /rer eis ars san

Andererseits opfert man dann Palindrome wie Animativ =<>= Vitamin A. Empfehlenswert ist es daher, mit verschiedenen Wortlisten zu arbeiten. Als Basis benutzte der Autor eine umfassende Liste der deutschen Sprache, die zur Rechtschreibpr¨ ufung im Programm PSPad editor [3] eingesetzt wird und 325 380 Eintr¨ age hat. Es ist nur m¨ oglich mit einem gew¨ ohnlichen Rechner diese Liste im Arbeitsmodus 1 durchgehen zu lassen. Listenoptimierungen wurden auf verschiedenste Weisen durchgef¨ uhrt, z.B. Ausschließen von sch- haltigenW¨ ortern, Begrenzung der Wortl¨ ange usw. Eine weitere Liste mit ca. 22 000 W¨ ortern lieferte die Lutherbibel [4]. Auf Grund der F¨ ulle an Eigennamen in der Heiligen Schrift entstanden mitunter etwas eigenartige obwohl nicht unsch¨ one Palindrome wie: Haus ’Leah Asa Asahael Suah’

Im Anhang 2 findet der Leser eine kurze Auswahl von Palindromen, die mit Token gefunden worden waren. Kaum eins von ihnen ist gleich mit den

19

Palindromen aus der im Netz wohl gr¨ oßten deutschsprachigen Sammlung von Johannes Plachy [5], was f¨ ur eine gewisse Authentit¨ at des Ansatzes spricht. Die Liste soll nur als Beispiel dienen und hat keinen Anspruch auf Rekord oder besondere Anerkennung, zumal sie das Resultat eines eher oberfl¨ achlichen, grob orientierenden Tests des Programms ist.

4.4 Funktion GibtsSatz()

Der Quellcode der Funktion GibtsSatz() (Syntax - .NET 2005) ist auf der Seite 21 komplett aufgef¨ uhrt. Die Namen der Variable sind weitgehend der Bezeichnungen im Artikeltext angepasst. Die Variable z entspricht dem t aus dem Beispiel (2) auf der Seite 6.

Eine zenrale Rolle spielt hier die Formel (21), S. 12, die zur n-Berechnung anhand des aktuellen k eingesetzt wird und eine sukzessive K-Reduktion erm¨ oglicht (s. Abschnitt 3.3 und Kommentare im Quellcode). Bei l¨ angeren Testsequenzen wird das Programm deutlich langsamer, so dass ein wahlfreier K-Ausschluss (s. Abschnitt 3.4.2) zu erw¨ agen w¨ are. Dies ist gegenw¨ artig noch nicht praktisch umgesetzt und ist das Ziel weiterer Aktivit¨ aten zur Verbesserung des Programms.

5 Anhang

5.1 Quellcode der Funktion GibtsSatz()

21

• Eine Xenie *** eine Xenie ist ein Gastgeschenk

• Knabe, bewege Gewebebank. *** aus dem Mediziner-Alltag

• Leben nahte, ET-Horde bedrohte Ethannebel. *** da konnten die Erdbewohner endlich aufatmen

• Haus ” Leah Asa Asahael Suah“ *** Biblische Namen, so heißt eine Filiale des Diakonie-Werkes

• Addar, Salut! Ulas Rad da? *** aus einem Dialog im deutsch-franz¨ osischen Radsportverein

• New als ET-Horde - belagertes Set Regale bedrohte Slawen. *** hastige Gespr¨ achsnotiz aus Putins Verteidigungsministerium

• Slipeinlage? Egal, nie Pils! *** die Betrunkene wollte nat¨ urlich ” Pilz“ sagen, hatte aber ein Glas Hasser¨ oder in der Hand

• Ziegelhammer: R.E.M. mahle Geiz *** klugsch...erische Schlagzeile einer avantgardistischen Musikzeitschrift

• Ei mag Opa, Apogamie! *** Apogamie [bot.] - ungeschlechtliche Fortpflanzung

• relativ vitaler *** Rettungsassistent ¨ uber sein Opfer

• Eh, an! Melde Eisnebel! ...Leben Sie Edlem nahe! *** von einem Meteorologen, der zuerst nicht merkte, dass er auf Sendung war, sich aber schnell fassen konnte

• Ehe-Anlage, eine ” nie egal“-Naehe *** sch¨ one Formulierung des Wesens der Ehe, aus einem Trauversprechen

• Erdnahe Lage egal? Eh, Andre! *** bei der Immobilienbesichtigung. Andre ist im Gegensatz zu seinem Begleiter etwas gleichg¨ ultig

• Paketadresse: ” Esser Date“ Kap *** postale Routine, die Sendung geht an die Ostsee

• Animativ, Vitamin A *** ¨ arztlicher Rat

• Nie Nebel! Gras neben Sarg - Leben ein! *** so beruhigte sich ein uberzeugter Kiffer ¨

22

• Lebens-AG ” Gasnebel“ *** Name einer astronomisch interessierten Wohngenossenschaft in der Schweiz

• A, ich masturbiere, Kokerei-Brut. Sam H., CIA *** “Kokerei-Brut“ ist ein bei den CIA-Agenten beliebter Fluch

• Kokotten nett? OK, OK. *** aus einem ruhigen Gespr¨ ach ¨ uber Rotlicht-Etablissements

• Sie: Onan, Sua ² - aus Nano-Eis. *** freigegeben ab dem 16. LJ

• Remade Edamer ** K¨ asewiederverwertung

• Nereide edieren ** [Ne-re-i-de e-die-ren] heißt Meeresjungfrau oder gleichnamigen Borstenwurm verlegen, was ist Ihnen lieber?

• seid nun dies ** Resignationsseufzer der Mutter von unbest¨ andigen und schwererziehbaren Kindern

• Baut hoeher!.. Rehe!!! Oh, tu ab! ** Streit zwischen F¨ orstern und Landwirten

• Adresse! Esser da. ** Obdachloser beim Streetwork

• Akkomodativer ” eVita Dom“ Mokka ** Kaffeesorte, bei derem Konsum der Trinkende zu schielen beginnt

• Beil feil, lief lieb ** feil [alt.] = ” (ver)k¨ auflich“. Meldung eines erfahrenen eBay-H¨ andlers

• Eine Tuer reute nie ** Satz eines schlampigen Bauarbeiters

² Sua war die Mutter von Onan (s. Genesis / 1. Mose 38:2-4) [6] Genesis/1. Mose 38 1 Um diese Zeit begab es sich, daß Juda sich von seinen Br¨ udern trennte und sich an einen Mann aus Adullam namens Hira anschloß. 2 Dort sah Juda die Tochter eines Kanaan¨ aers namens Sua; die nahm er zur Frau und lebte mit ihr. 3 Sie wurde guter Hoffnung und gebar einen Sohn, den er Ger nannte. 4 Hierauf wurde sie wieder guter Hoffnung und gebar einen Sohn, den sie Onan nannte. 5 Sodann wurde sie nochmals Mutter eines Sohnes, dem sie den Namen Sela gab; sie befand sich aber in Chesib, als sie ihn gebar. 6 Juda nahm dann f¨ ur seinen erstgeborenen Sohn Ger eine Frau namens Thamar. 7 Aber Ger, der Erstgeborene Judas, zog sich das Mißfallen des HERRN zu; daher ließ der HERR ihn sterben. 8 Da sagte Juda zu Onan: ” Gehe zu der Frau deines Bruders ein und leiste ihr die Schwagerpflicht (= vollziehe mit ihr die Schwagerehe; vgl. 5.Mose 25,5-10), damit du das Geschlecht deines Bruders fortpflanzest!“ 9 Da Onan aber wußte, daß die Kinder nicht als seine eigenen gelten w¨ urden, ließ er, sooft er zu der Frau seines Bruders einging, (den Samen) zur Erde fallen, um seinem Bruder keine Nachkommen zu verschaffen. 10 Dieses sein Tun mißfiel aber dem HERRN, und so ließ er auch ihn sterben.

23

• Die Tat reut, Tu¨ er tat Eid ** aus der Gerichtspraxis

• Steuer-Fredies, seid erfreuet. S. ** Finanzamtmitarbeiter packt aus

• Subsummier’ drei mm US-Bus ** Matheaufgabe

• Addar baut - tu ab, Rad da! ** dt.-fr. Radsportverein, Teil 2

• Relativismus um SI vitaler ** Physiker diskutieren

• Gurte-Bande = DNA-Betrug ** Fachausdruck ¨ uber genetische Fingerabdr¨ ucke

• Kolorit! Tirol OK. ** von einem zufriedenen Urlauber

• Euer Nathan naht an Reue. ** d.h. Nathan beginnt langsam zu verstehen, was er falsch gemacht hatte

• Alge, Edamer - remade EGLA ** EGLA = Entwicklung grenz¨ uberschreitender l¨ andlicher Arbeitsm¨ arkte, EU-Forschungsprojekt in Maastricht und Osnabr¨ uck

• ...ei alle DE, Edellaie... ** Brummen eines besoffenen Punks

• Eh, Andre! Base er hob! Bohre es ab, erdnahe! ** aus dem Gespr¨ ach von Geologen auf der Expedition

• ...eh anmelde. Eisnebel, eben sie, Eisnebel eben; sie, Edlem nahe! * unvollendetes Palindrom

• Ein Tu¨ er reut nie * Meinung eines Henkers

• Bauen stets neu ab * ?

• Es sah Sua aus Hasse. * Satz voll Pseudosemantik

• Asahael trug Gurt ” Leah Asa“ * eine modische Bibelfigur

• Sie tat Eis * unverst¨ andlich

• Drei goldene Regeln eines Bestatters:

• tot neben tot * 1

• Ton tut Not * 2

• Tor stets rot * 3

• Base enge S, segne es ab * Chemiker versucht, seinen Chef zu erpressen

24

• Base tat es ab * Meldung beim Milit¨ ar

• Ton neben Not * 4. Zusatzregel eines musikinteressierten Bestatters

• Bohre, er hob. * beim Einbruch

• Steuerfreies. Sei erfreuet. S. * Finanzamtler packt aus, Teil 2

• Florierende Rednerei, Rolf * Bewertung eines Toastspruchs

• Ohrenspiegel. Leg Ei. PS: Ner Ho * wer Ner Ho war, bleibt obskur

• nenne Kreuz zu erkennen * Kirchendiener mit Migrationshintergrund

• nenne Kreuz, na anzuerkennen * Kirchendiener mit Migrationshintergrund, versucht, sich zu verbessern

• Addierender Redner - Eid da. * ohne Bedeutung

• ...Sammeldepot - top edlem Mas... * unvollendetes Palindrom

• Roger Gregor * Wunschname

• Murmellaut, tu alle MR um * MR = Magnetresonanz

• letzten Netz-Tel. * unvollendetes Palindrom

• Handregel: Leg erdnah * wof¨ ur denn?

• Belerender Redner Heleb * ob Heleb wirklich so war, steht in der Bibel

• Codein! Nie Doc * Hoffnung eines Junkies

• Belagertes Set Regale B * Aufkleber

• Bedrohtem Met - Horde B * Aufgabenverteilung auf einem Mittelalter-Markt

• Traume - Emu Art * unvollendetes Palindrom

• Unzip Piz Nu * Piz (retoroman.) - Bergspitze, bes. in Namen

• Tor trug Gurt rot. * Rot und blau - Kaspersfrau!

• ...eh anmelde Einehe, Ehe nie Edlem nahe... * unvollendetes Palindrom

• Adretten, Netter da * Wunsch eines netten Homosexuellen bei der Partnervermittlung

25

• Ekle Elke * wer sagt denn so was zu einer Dame?!

• A-silbig, gib Lisa * beim Sortieren in einem Verlag

• ...Sua trug Gurt aus... * unvollendetes Palindrom

• Burg bauen - neu ab Grub’ * Befehl eines mittelalterlichen Bauherrn

• Darein, bohre! Er hob nie Rad. * an den Ohren herbeigezogen

• Beil darnieder! Rede in Rad lieb. * Verfolgungsjagd zu Ende

• Beil hoeher! Rehe, oh lieb! * Reh-Plage 1813

• Base lief, feil es ab * B¨ uhnentechniker beim Montieren der Schlagzeuganlage

• Die trug Gurt-Eid * er meinte Keuschheitsg¨ urtel

• Die tat Eid * er besteht auf der Formulierung zuvor

• ...euer Nase, es an Reue... * unvollendetes Palindrom

• Eher neuer, reuen Rehe * 1813

• Ton tat Not * Musikergest¨ andnis

Literatur

[1] H. Beusing Sprachpflege (1974)

[2] Prof. Dr. Rudolf Bittner, Dr. Dieter Ilse, Dr. Werner Tietz, Siegmar Kubicek Mathematik in ¨ Ubersichten (1976) Volk und Wissen Volkseigener Verlag Berlin

[3] PSPad freeware editor. Version 4.5.1 (2207). Autor: Jan Fiala, Prog-Soft s.r.o., Na Kovarske strani 1, 317 03 Plzen [4] Bibel Luther Revision 1912 Deutsch auf theology.de [5] Johannes Plachy - IT Solutions and Services - unter ” Palindromes & more“ http://www.jps.at/ [6] Menge-Bibel auf www.die-bibel.de

26