Diskret binäre Verteilung am Beispiel eines Palindromsuchprogramms

Inhaltsverzeichnis

1 Freie Lizenz
1.1 Urheberklausel
1.2 Benutzung durch Leser

2 Einführung
2.1 Definition
2.2 Verwendbarkeit
2.3 Nutzen

3 Diskret binäre Verteilung. Entstehung und abgeleitete Funktionen
3.1 Hauptstring und Teilstrings
3.2 Kettenkodierung und binäre Referenz
3.3 Funktion N (k) und sukzessive {K → N (k)1 . . . N (k)h → K}- Reduktion
3.4 P -Elimination und wahlfreie {Tn → Kn}-Reduktion
3.4.1 Funktion K(n)
3.4.2 Wahlfreier {Tn → Kn}-Ausschluss

4 Programmatische Implementierung
4.1 Das Programm Token
4.2 Programmdesign
4.3 Vorgehensweise bei der Palindromsuche
4.4 Funktion GibtsSatz()

5 Anhang
5.1 Quellcode der Funktion GibtsSatz()
5.2 Palindrombeispiele ,

Zusammenfassung

Als Diskret-Binäre-Verteilung werden hier numerische Zusam- menhänge in einer Abbildung der Menge T , deren Elemente Teil- zeichenfolgen der definierten Hauptzeichenfolge sind, auf die Men- ge K, deren Elemente Ketten der Teilzeichenfolgen sind, die ex- akt die Hauptzeichenfolge bilden, bezeichnet. Von zentraler Be- deutung ist dabei die aufsteigende Anordnung von T -Elementen nach ihrer Position und Länge innerhalb der Hauptzeichenfolge. Die ordinalen Zahlen n dieser Anordnung sind Funktionswerte für jede Zeichenposition einer beliebigen Kette, die eine effiziente Referenzübergabe für T - auf K-Elemente ermöglichen, mit dem Ziel, überflüssige k-Bestimmungen zu vermeiden und notwendige k-Bestimmungen ohne ressourcenaufwendige Wertevergleiche zu gestalten. Das erlaubt, innerhalb einer Zeichenfolge ohne Trenn- zeichen eine automatische non-redundante Suche nach semantisch existenten Sätzen und anderen Textfragmenten durchzuführen. Dasselbe Prinzip kann man unter Gleichstellung des Trennzei- chens einem beliebigen Zeichen oder Zeichenfolge für die Rekon- struktion der beschädigten oder unlesbaren Textfragmente ver- wenden. Eine Demonstration der Anwendung der diskret binären Verteilung geschieht hier auf dem Beispiel eines Palindromsuch- programms.

Stichwörter: Textverarbeitung, quantitative Linguistik, Kryptologie, Programmieren, VB, .NET, Palindrom, diskrete Funktion, Redundanz, Zeichenfolge, Verteilung, binär

1 Freie Lizenz

1.1 Urheberklausel

Der Autor versichert ausdrücklich, dass die in diesem Artikel abgehandelten Zusammenhänge, Daten und Erkenntnisse, falls nicht anders gekennzeichnet oder zitiert, Produkt seiner eigenen geistigen Schöpfung darstellen und nach bestem Wissen und Gewissen ohne Verletzung oder stillschweigende Ausnut- zung der Patent- oder Urheberrechte Anderer verfasst worden sind.

1.2 Benutzung durch Leser

Alle Daten dieser Abhandlung, sofern sie kein Zitat sind, dürfen für pri- vate, Forschungs-, Ausbildungs- und Lehrzwecke FREI kopiert, verändert, gespeichert und weitergegeben werden. Bei der Weitergabe, der Vervielfäl- tigung und der öffentlichen Vorführung 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 vol- len Namen des Verfassers oder seine E-Mail-Adresse fedorowski@web.de beinhalten. Falls Veränderungen am Quelltext vorgenommen sein sollten, ist dies gesondert zu vermerken. Das freie Nutzen des Werkes für kommerzielle Zwecke ist unter Einhaltung der Autorenreferenz und nach einer kurzen Be- nachrichtigung des Autors über die Art des Nutzens grundsätzlich gestattet. Der Autor behält sich jedoch das Recht vor, in Ausnahmefällen das kommer- zielle Nutzen des Artikelinhaltes zu untersagen oder nur unter zusätzlichen 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.

Die Liebe ist Sieger, rege ist sie bei Leid...[1]

DIEL IEB EIS TSI EGER REGEIS TSI EBEIL EID

Abbildung in dieser Leseprobe nicht enthalten

2 Einführung

2.1 Definition

Als Diskret-Binäre-Verteilung wird hier eine Abbildung der Menge T , de- ren Elemente Teilzeichenfolgen der definierten Hauptzeichenfolge sind, auf die Menge K, deren Elemente Ketten ((1, ..., h)-variable Tupel) der Teilzei- chenfolgen 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ätzen und anderen Textfragmenten mittels einer großen bis sehr großen externen Wortliste oder einer datenbankähnlichen Struktur vorgenom- men wird, wobei die Teilzeichenfolgen auf ihre Eigenschaft als Wörter oder andere sinnergebende Strukturen geprüft werden. Um den rechnerischen Auf- wand kleinstmöglich zu halten (non-redundante Suche), werden alle Ketten (potentiellen Sätze), die ein nicht-existentes Wort enthalten würden, frühzei- tig dank negativer Referenz- Übergabe für dieses Wort (Teilzeichenfolge) nach nur einer Wortsuche und Zuordnung des Booleschen Parameters ausgeschlos- sen. Diese Referenzübergabe bedient sich nicht des Inhaltes der Zeichenfolge selbst, wie es im Falle der rechnerisch aufwendigeren repetitiven Wertüber- gabe beim konsekutiven Vergleich wäre, sondern vielmehr der festgelegten sequentiellen Anordnung N der T -Elemente in der auf Grund ihrer Position und Länge innerhalb der Hauptzeichenfolge, die man als eigenständige Funk- tion N (k) für die Validation der Ketten ressourcensparend benutzen kann. Auf diese N -Folge wird aus der besagten T → K Abbildung geschlossen.

Dasselbe Prinzip kann man unter Gleichstellung des Trennzeichens mit einem beliebigen Zeichen oder Zeichenfolge für die Rekonstruktion der beschädigten oder unlesbaren Textfragmente verwenden.

2.3 Nutzen

Eine Implementierung von diskret binärer Verteilung in reiner oder abgewandelter Form könnte in diversen Algorithmen und Verfahren von Vorteil sein: Kryptologische Ver- und Entschlüsselung, Experimente in der ITLinguistik, Erzeugung von Korrekturvorschlägen und intelligente Suchoptionen in der Textverarbeitung, Suchmachinendesign, Entwerfen von Spielen, mehrdimensionale Logik, fehlertolerante Perzeption in der künstlichen Intelligenz, Durchsuchen von genetischen Sequenzen u. Ä.

Nach der Beschreibung der Eigenschaften der diskret binären Verteilung handelt es sich in diesem Artikel um ihre Verwendung in einem Spezialfall. Ein Palindrom-Suchprogramm führt u.a. Wortpaarvergleiche durch, auf das Vorkommen des kürzeren Wortes im inversen String des längeren. Dabei entstehen Zeichenfolgenbruchstücke, die ihrerseits auf Existenz als Wörter, Wortteile oder Wortfolgen geprüft werden.

(1)

Abbildung in dieser Leseprobe nicht enthalten

Start 1 → Länge 3 → Start 4 → Länge 2 ⇒ Länge 5

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

Da eine mitteleuropäische Sprache mit einem mäßigen Anteil an Beu- gungsformen, zusammengesetzten Wörtern, Präfixen, Endungen und anderen

grammatikalischen Varianten schnell eine Wortliste mit über 500.000 Einträgen bedeuten kann, liegt die Anzahl der einfachen Durchläufe der Vergleichssubroutine schon bei

(500.000)

[2]

≈ [125] Milliarden.

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

3 Diskret binäre Verteilung.

Entstehung und abgeleitete Funktionen

3.1 Hauptstring und Teilstrings

Für einen Hauptstring (Hauptzeichenfolge) H der Länge h bilden sich v Teil- strings Tn(a,t) der Länge t1 bis th mit Positionen ihres ersten Zeichens a1 bis ah innerhalb des H. Sortiert man die Tn(a,t) aufsteigend nach ihren a (Kri- terium 1) und t (Kriterium 2) in einem Datenfeld T() und nummeriert sie konsekutiv, so erhält man eine Folge der v natürlichen Zahlen von n = 1 bis n = v, wobei jedes n einen Teilstring Tn(a,t) eindeutig identifiziert.

Das Auffinden von Teilstrings und das gleichzeitige Sortieren nach a, t- Kriterien erfolgt mit dem Algorithmus (2).

(2)

Abbildung in dieser Leseprobe nicht enthalten

(3)

Abbildung in dieser Leseprobe nicht enthalten

(3) besagt, dass die Anzahl aller Teilstrings und somit die obere Grenze des T() gleich Summe aller natürlichen Vorgänger der Hauptstringlänge und

Abbildung in dieser Leseprobe nicht enthalten

ihr selbst ist. Beispiel:[1]

Der Hauptstring H lautet {einKnie} h = 7 ist seine Länge

Abbildung in dieser Leseprobe nicht enthalten

3.2 Kettenkodierung und binäre Referenz

Stellt man sich H als eine Kette Kk aus passenden Tn(a,t) vor, kann man alle u möglichen Anordnungen von Tn(a,t) in u Kk-Varianten mit binären Zahlen der Länge h − 1 codieren, wenn man von links nach rechts, angefangen mit dem zweiten Teilstring, die Bits Nr. a − 1 mit “0” und die übrigen Bits mit “1” kennzeichnet. Der ”Schwanz“deserstenTeilstringswirdebensomit“[1]”ern aufgefüllt. Zum Beispiel:

Die Binärzahl [58] ergibt eine Sequenz “[111010]”:

([4])

Abbildung in dieser Leseprobe nicht enthalten

Die eine Null steht an der Position 4, somit wäre der Anfang des zweiten Teilstrings a = 4 + 1 = 5, und seine Länge - die Anzahl der darauffolgenden “1” plus 1, sprich t = 1 + 1 = 2. Ähnlich a = 7 und t = 1 für den letzten Teilstring. Da der erste Teilstring nie fehlt, wird sein a = 0 + 1 = 1 stets angenommen und seine Länge t wäre in diesem Fall 4. Also codiert die Zahl 58 einen H oder eine Kette K58, die aus Tn(1,4) = {einK}, Tn(5,2) = {ni} und Tn(7,1) = {e} zusammengesetzt ist. Um für diese Teilstrings ihre Ordinalzahlen n zu finden (in diesem Beispiel 4, 24 und 28), hatte man bis jetzt nur die Möglichkeit des konsekutiven Stringvergleiches nach Länge und Anfangszeichen mit schlimmstenfalls allen Elementen des Datenfeldes T(). Um dies zu ändern, betrachten wir die Menge K genauer:

Die Gesamtanzahl von natürlichen Binärzahlen mit h − 1 Stellen und kleiner (bei diesen werden führende Nulls angehängt), beträgt 2h−[1]. Also, es ergeben sich u = 2h−[1] Kettenvarianten Kk 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).

Abbildung in dieser Leseprobe nicht enthalten

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ünfstelligen Binärzahlen, von 2[5] − 1 = 31 ≡ 11111 bis 2[4] = 16 ≡ 10000.

(6)

Abbildung in dieser Leseprobe nicht enthalten

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

Abbildung in dieser Leseprobe nicht enthalten

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önnen wir aus dieser Matrix auf die Abhängigkeit der n-Zahlen von der Zeilennummer j, die der Zahl k der Kk-Elemente entspricht, und der Spaltennummer i - Position innerhalb der Kette schließen.

Matrix fBIN (ij)= n(p, k) (ByRef ) (7)

N (k) ← P, K. Obwohl diese Relation rechts zwei Argumente hat, wird bei der späteren Referenzübergabe jede Spalte durchgegangen, so dass der Positionsparameter p als endliche low-range Variable betrachtet werden kann.

Matrix

Abbildung in dieser Leseprobe nicht enthalten

Tatsächlich fällt es auf, dass in den Spalten der Matrix (7) mit steigen- dem k eine einfache, um Schritt 1 zunehmende Zahlenfolge mit einer geome- trisch abnehmenden doppelt-repetitiven Anordnung der n-Zahlen zur Basis 2 stattfindet, und in den Zeilen - eine arithmetische Folge mit dem aus der vor- herigen Spalte stammenden Augenden und dem um Schritt 1 abnehmenden Addenden.

Angesichts dessen kann man versuchen, für 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ür die Spalte eins (p = 1) trivial bestimmbar zu sein:

(8)

Abbildung in dieser Leseprobe nicht enthalten

wo x - die Ordnungsnummer des n-gleichen Spaltenbereiches ist.

Jeder nachfolgende Spaltenbereich verhält sich wie die untere Hälfte des vorangehenden kontinuierlichen Spaltenbereiches, zuzüglich Erhöhung der Glieder um h − p + 1, und 2h−[1] kann man für weitere Spalten als 2h−p verall- gemeinern. Im voraus sei vermerkt, dass der k-Nummerierung von 1 bis 2h−[1] auf jeden Fall 0 bis 2h−[1] − 1 vorzuziehen ist, denn das wird später die De- finition des Funktionsbereiches N (k) vereinfachen. Angesichts dessen haben wir

(9)

Abbildung in dieser Leseprobe nicht enthalten

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

Abbildung in dieser Leseprobe nicht enthalten

(10)

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

(11)

Abbildung in dieser Leseprobe nicht enthalten

Es bilden sich in späteren Positionen mit immer kürzeren 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 2p−[2] ist, und daher die Anzahl der Repetitionsglieder

(12)

Abbildung in dieser Leseprobe nicht enthalten

davon ist die Hälfte leer. Jedes k in der Repetition unterscheidet sich von seinem Grundabbild kL...U1 durch einen Zusatz ZK , der der Repetitionsnum- mer von 0 bis ⌈2p−[2] − 1⌉ (Aufrundung wegen 2−[1]-Möglichkeit) mal 2h−p+[1] entspricht:

(13)

Abbildung in dieser Leseprobe nicht enthalten

(14)

Abbildung in dieser Leseprobe nicht enthalten

(15)

Abbildung in dieser Leseprobe nicht enthalten

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

(16)

Abbildung in dieser Leseprobe nicht enthalten

Wir können die Modulo-Funktion

(17)

Abbildung in dieser Leseprobe nicht enthalten

später 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öhnliche Weise aus, weil wir möglicherweise noch K(. . .) Funktionen be- nötigen werden:

(18)

Abbildung in dieser Leseprobe nicht enthalten

(19)

Abbildung in dieser Leseprobe nicht enthalten

Nun sind wir dem eingentlichen Zwischenziel, n durch k auszudrücken, entschieden näher gekommen. Auf Grund der Injektivität von (17) und dadurch, dass es sich bei KL und KU um n-gleiche Glieder handelt, werfen wir eine folgende Simplifizierung in den Raum:

Abbildung in dieser Leseprobe nicht enthalten

(20)

Abbildung in dieser Leseprobe nicht enthalten

Wir gehen einfach davon aus, dass der Wert des niedrigsten k-Gliedes im n- gleichen Bereich vollkommen genügt, um in einer logarithmischen Funktion den gesamten Bereich präzise auf N abzubilden. Nach Umformung von (20) und Ausdrücken von n bekommen wir eine bequeme Arbeitsformel, die dem

Computer schnell vorkommen:

”klarmacht“,inwelchenKwelchenunddaherauchTn

Abbildung in dieser Leseprobe nicht enthalten

(21)

Rechentests mit größeren Matrizen mit h über 20 bestätigten Formel 21. Die Gauß’sche Klammer rundet Mantissen herunter, und die Funktionswerte entsprechen den tatsächlichen n-Größen in p-Positionen der jeweiligen Kette, deren Nummern k als Argumente an die N (k)-Funktion übergeben werden. Die leeren n-Werte entsprechen dem Berech, wo log2 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 vor- kommenden Teilstrings Tn in der jeweiligen k-Kette, indem Positionen n1 bis nh bestimmt, und die dabei entstehenden n gleich im bereits angeleg- ten Booleschen Datenfeld auf geprüft werden.

”Vorkommen:JA“oder ”Vorkommen:NEIN“

3.4 P -Elimination und wahlfreie {Tn → Kn}-Reduktion

Eine weitere Steigerung der Programm-Effizienz kann durch eine p-unabhängige Bestimmung aller N -Glieder der K-Kette erreicht werden, was prinzipiell möglich sein müsste, da n-Werte p-eindeutig sind. Außerdem sind sie gleich- sinnig steigend, so dass die Reihenfolge in der Ausgabe kein großes Problem bereiten würde. Eine Herausforderung wäre allerdings, einen Ausdruck zu finden, der einen schnellen Zugriff auf sämtliche K erlaubt, in denen ein be- stimmtes N vorkommt, um das Durchgehen der Ketten, die auf Grund von 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änge.

(22)

Abbildung in dieser Leseprobe nicht enthalten

Abbildung in dieser Leseprobe nicht enthalten

(23)

So dass es für das größte n der p-gleichen Reihe nmax gilt ∑

Wenn q = h − p + 1 und nmax = i, dann (24)

Abbildung in dieser Leseprobe nicht enthalten

(25)

Die beiden Lösungen der Gleichung (25) sind √

q1,2 = 0,5 ± 0, 25 − 2nmax + h(h + 1) (26)

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

Abbildung in dieser Leseprobe nicht enthalten

Verwenden wir die Gauß’sche Klammer nur für die Lösungen q1 und er- setzen q wieder, so erhalten wir exakt den p(n)-Wert:

Abbildung in dieser Leseprobe nicht enthalten

(27)

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

Abbildung in dieser Leseprobe nicht enthalten

(29)

Abbildung in dieser Leseprobe nicht enthalten

(30)

Abbildung in dieser Leseprobe nicht enthalten

Abbildung in dieser Leseprobe nicht enthalten

(32)

...und erhalten eine diskrete p-unabhängige K(n)-Funktion, die aus zwei Unterfunktionen besteht, die für jedes n die untere (KL) und die obere (KU ) Feldgrenze vorgeben, mit entsprechender Anzahl von Feldwiederholungen:

Abbildung in dieser Leseprobe nicht enthalten

(33)

Abbildung in dieser Leseprobe nicht enthalten

(34)

Per analogon zu (17) bis (20) ergibt sich auch eine Gleichung (35) für die N (k)Funktion ohne Vorkommen von p, allerdings ist sie unbrauchbar, da das n als ein Teil der Modulofunktion über k vorkommt. Um es zu eliminieren, würde man p durch k definieren müssen, was sich vom Aufwand her nicht lohnt, da bei den recht überschaubaren p-Werten eine solche Formel rechnerisch viel komlizierter sein würde, als eine programmatische Anweisung, alle p von 1 bis h mit der Formel (21) durchzugehen.

Abbildung in dieser Leseprobe nicht enthalten

3.4.2 Wahlfreier {Tn → Kn}-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äre bei größeren h vielleicht der wahlfreie Ausschluss vorzuziehen und umgekehrt.

Beim wahlfreien Ausschluss werden für 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önnen, falls das n ”sinnlos“ist,enblocausgeschlossenwerden.

4 Programmatische Implementierung

4.1 Das Programm Token

Auf http://public.box.net/fedorowski im Ordner ”mysoftware“findetder

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

- Palindromsuchprogramm
- Prüfen einzelner Sequenzen auf Palindromfähigkeit anhand der (längeren) Wortliste (ab Vers. 1.0.0.8)
- komfortabler Zufallszahlgenerator
- Binär-Dezimal-Konverter für große Zahlen
- Zeitrechner
- Tool zum Umschreiben binärer Dateien in Textdateien mit ihren Bytewerten und zurück
- Werkzeuge zur Manipulation von Textdateien und Listenerstellung für die Palindromsuche:
- String-Ersetzung
- Erstellen der Liste aller in einem Text vorkommenden Wörter
- Anpassen der Wortliste durch Hinzufügen oder Entfernen definier- ter Einträge
- Elimination von Doppeleinträgen
- wahlweise Groß-/Kleinschreibungssensitive oder reverse Sortier- funktion
- alle Operationen können in Unicode oder in regionalspezifischen Textcodierungen vorgenommen werden
- Erstellen der Wortlisten mit Rückwärtssequenzen der normalen Wörter (ab Vers. 1.0.0.8)

Token wurde in VB.NET 2005 geschrieben und läuft auf Windows XP.

Zum Installieren lade man die Archivdatei

”Token[1]_x_x_xSetup.rar“her- unter, entpacke und führe die im Archiv befindliche Datei ”setup.exe“aus.

Möglicherweise 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ähle man den Button WM( ”WordMaster“),es erscheint ein Fenster mit diversen Schaltflächen, Textboxen und Listen. Hat man eine Textdatei mit einer Wortliste erstellt, betätige man den Button

”Palindromesearch“,umdieseaufPalindromezuuntersuchen.

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.
2. Jeder Eintrag (Wort) dieser Liste wird einem Glied des String-Arrays
(Datenfeldes) Wort([Anzahl der Einträge]) zugewiesen.
3. Die alphanumerisch sortierten Glieder werden in Bereiche je nach An fangsbuchstabe eingeteilt, und die Referenzarrays KarteiX() werden erstellt, um die Wortsuche einzugrenzen und dadurch zu beschleuni- gen.
4. Die Ausgabe-Textdatei, die die Palindromvorschläge enthalten soll, wird per Dialogfeld angelegt.
5. Der Benutzer wird aufgefordert, den Arbeitsmodus zu bestimmen. Die- ser gibt vor:

(a) wieviele Wörter die zu testende Sequenz enthalten soll, von 1 bis zu 4 Wörter sind möglich. Z.B. werden im Modus 3 alle möglichen Dreierkombinationen aller Einträge der Wortliste auf die Rück- wärtslesbarkeit geprüft, was natürlich eine enorme Zunahme der Anzahl der Einzelvergleiche und der Vergleichsdauer aufgrund der höheren Sequenzlänge bedeutet und nur bei kürzeren Wortlisten, die ausgewählte, besonders palindromfähige Wörter enthalten, an- gewandt werden sollte. Beispielsweise bildet das Programm das in der Einführung erwähnte Palindrom

”DieLiebeistSieger,regeist sie bei Leid“ aus einer Wortliste, die nur die acht dort vorkommen- den Wörter enthält, nur im Arbeitsmodus [4], sprich ist dann die Anzahl der Einzeldurchgänge [84] = 4096, und angesichts der Ein- zelsequenzlänge bis zu 17 Zeichen dauert es entsprechend lange, und zwar eine gute Minute (AMD XP Prozessor, Systemspeicher DDR 266/333/400).

(b) ob der sog.

”Raupentest“aufKostenderlängerenBerechnungs- zeit durchgeführt werden soll oder nicht. Der Raupentest redu- ziert die zu testende Sequenz zu Teilsequenzen oder erweitert sie um Wortfragmente, um möglicherweise das kurze ”störende“Ende der Testsequenz doch in ein längeres Palindrom einzubinden.

[6]. Anschließend startet die Palindromsuche, dabei wird die Rückwärtsse-

quenz eines jeden Wortes der Wortliste (oder der Sequenz eines jeden Wortpaares, -Drillings oder -Vierlings je nach Arbeitsmodus) an die Funktion GibtsSatz() übergeben, die den Kern des Programms bildet. Die Funktion gibt, falls gefunden, die Sätze zurück, die die Rückwärtsse- quenz beinhalten kann. In die Ausgabedatei wird ggf. die Testsequenz, das Trennzeichen

”=<>=“unddiekomplementärenSätze,getrennt [18]

durch

”/“zeilenweisegeschrieben,z.B.

relativ =<>= vi tal er /vi taler /vital er /vitaler

4.3 Vorgehensweise bei der Palindromsuche

Eine gute Wortliste ist für die Palindromkreation immens wichtig. Je länger ein Palindrom ist und je mehr Sinn der Palindromsatz ergibt, desto wertvoller ist es. Um fündiger zu werden, ist man zwar auf die Verarbeitung von sehr umfangreichen Wortlisten angewiesen, aber das bedeutet, erstens, längere Berechnungszeiten, zweitens, größ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ändige Wörter und bestimmte kurze, selten vorkommende Wörter 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üfung im Programm PSPad editor [3] eingesetzt wird und 325 380 Einträge hat. Es ist nur möglich mit einem gewöhnlichen Rech- ner diese Liste im Arbeitsmodus 1 durchgehen zu lassen. Listenoptimierungen wurden auf verschiedenste Weisen durchgeführt, z.B. Ausschließen von sch- haltigen Wörtern, Begrenzung der Wortlänge usw. Eine weitere Liste mit ca.

22 000 Wörtern lieferte die Lutherbibel [4]. Auf Grund der Fülle an Eigennamen in der Heiligen Schrift entstanden mitunter etwas eigenartige obwohl nicht unschöne 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

Palindromen aus der im Netz wohl größten deutschsprachigen Sammlung von Johannes Plachy [5], was für eine gewisse Authentität 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ächlichen, 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ührt. 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öglicht (s. Abschnitt 3.3 und Kommentare im Quellcode).

Bei längeren Testsequenzen wird das Programm deutlich langsamer, so dass ein wahlfreier K-Ausschluss (s. Abschnitt 3.4.2) zu erwägen wäre. Dies ist gegenwärtig noch nicht praktisch umgesetzt und ist das Ziel weiterer Aktivitäten zur Verbesserung des Programms.

***

5 Anhang

5.1 Quellcode der Funktion GibtsSatz()

'Diese Funktion ist der Hauptgegenstand des Artikels und das Herzstück des Palindromsuchprogramms Public Function GibtsSatz(ByVal gSatz As String) As String

Dim DIFF As String 'für die Ausgabe

If gSatz = "" Then

DIFF = ""

Return DIFF

Exit Function End If

Dim h, a, z As Integer, aZaehler, k, n As Long Dim JaNein(), vor As Boolean

Dim DIFFv As String 'für treffende Teilstrings

h = Len(gSatz) 'gesuchter Satz von h Zeichen Länge ohne Leerräume Dim u As Long = 2 ^ (h - 1) - 1 'siehe Abschnitt 3.2 des Artikels Dim d2, d3 As Long

ReDim JaNein(SigmaSimple(h)) 'SigmaSimple() ist die Funktion zur Berechnung vom “kleinen Gauß” '===Die folgende geschachtelte Doppelschleife ordnet die potentiellen Wörter aufsteigend, '(1) nach Position des 1. Zeichens und (2) nach Wortlänge, prüft die Wörter gleich auf Existenz 'und schreibt die Ergebnisse in den Booleschen Array JaNein() (Algorithmus 2, Artikeltext)

Abbildung in dieser Leseprobe nicht enthalten

5.2 Palindrombeispiele ,

- Eine Xenie *** eine Xenie ist ein Gastgeschenk

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

- Leben nahte, ET-Horde bedrohte Ethannebel. *** da konnten die Erd- bewohner endlich aufatmen

- Haus

”LeahAsaAsahaelSuah“***BiblischeNamen,soheißteineFiliale des Diakonie-Werkes

- Addar, Salut! Ulas Rad da? *** aus einem Dialog im deutsch-französischen Radsportverein

- New als ET-Horde - belagertes Set Regale bedrohte Slawen. ***

hastige Gesprächsnotiz aus Putins Verteidigungsministerium

- Slipeinlage? Egal, nie Pils! *** die Betrunkene wollte natürlich sagen, hatte aber ein Glas Hasseröder in der Hand

”Pilz“

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

- Ei mag Opa, Apogamie! *** Apogamie [bot.] - ungeschlechtliche Fortpflan- zung

- relativ vitaler *** Rettungsassistent über 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 ”nieegal“-Naehe***schöneFormulierungdesWe- sens der Ehe, aus einem Trauversprechen

- Erdnahe Lage egal? Eh, Andre! *** bei der Immobilienbesichtigung. And- re ist im Gegensatz zu seinem Begleiter etwas gleichgültig

- Paketadresse: an die Ostsee

”EsserDate“Kap***postaleRoutine,dieSendunggeht

- Animativ, Vitamin A *** ärztlicher Rat

- Nie Nebel! Gras neben Sarg - Leben ein! *** so beruhigte sich ein überzeugter Kiffer

- Lebens-AG

”Gasnebel“***NameeinerastronomischinteressiertenWohnge- nossenschaft 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äch über Rotlicht- Etablissements

- Sie: Onan, Sua[2] - aus Nano-Eis. *** freigegeben ab dem 16. LJ

- Remade Edamer ** Käsewiederverwertung

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

- seid nun dies ** Resignationsseufzer der Mutter von unbeständigen und schwer- erziehbaren Kindern

- Baut hoeher!.. Rehe!!! Oh, tu ab! ** Streit zwischen Förstern und Land- wirten

- Adresse! Esser da. ** Obdachloser beim Streetwork

- Akkomodativer

”eVitaDom“Mokka**Kaffeesorte,beideremKonsumder Trinkende zu schielen beginnt

- Beil feil, lief lieb ** feil [alt.] = renen eBay-Händlers

”(ver)käuflich“.Meldungeineserfah-

- Eine Tuer reute nie ** Satz eines schlampigen Bauarbeiters

1 Um diese Zeit begab es sich, daß Juda sich von seinen Brüdern trennte und sich an einen Mann aus Adullam namens Hira anschloß. 2 Dort sah Juda die Tochter eines Kanaanäers 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ür 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:

”GehezuderFraudeinesBruderseinundleisteihrdieSchwagerpflicht(= 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ürden, 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.

- Die Tat reut, Tuër 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 über genetische Fingerabdrücke
- 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überschrei- tender ländlicher Arbeitsmärkte, EU-Forschungsprojekt in Maastricht und Osna- brück
- ...ei alle DE, Edellaie... ** Brummen eines besoffenen Punks
- Eh, Andre! Base er hob! Bohre es ab, erdnahe! ** aus dem Ge- spräch von Geologen auf der Expedition
- ...eh anmelde. Eisnebel, eben sie, Eisnebel eben; sie, Edlem nahe! * unvollendetes Palindrom
- Ein Tuër reut nie * Meinung eines Henkers
- Bauen stets neu ab * ?
- Es sah Sua aus Hasse. * Satz voll Pseudosemantik
- Asahael trug Gurt

”LeahAsa“*einemodischeBibelfigur

- Sie tat Eis * unverständlich
- 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är
- 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ür 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 Pa- lindrom
- Adretten, Netter da * Wunsch eines netten Homosexuellen bei der Partner- vermittlung
- Ekle Elke * wer sagt denn so was zu einer Dame?!
- A-silbig, gib Lisa * beim Sortieren in einem Verlag
- <welche>...Sua trug Gurt aus... * <was> 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ühnentechniker beim Montieren der Schlagzeug- anlage
- Die trug Gurt-Eid * er meinte Keuschheitsgürtel
- 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ändnis

Literatur

[1] H. Beusing Sprachpflege (1974)

[2] Prof. Dr. Rudolf Bittner, Dr. Dieter Ilse, Dr. Werner Tietz, Siegmar Kubicek Mathematik in Übersichten (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 more“ http://www.jps.at/

[6] Menge-Bibel auf www.die-bibel.de

”Palindromes&