Substrings lexikographisch ordnen

[Moppel]

Hallo!

Ich bin ein ziemlicher Newbie auf dem Gebiet der Programmierung.
Trotzdem habe ich folgendes Problem.
Ich habe eine Reihe von Wörtern vorliegen, gespeichert z.B. in einem Array.
Diese (in beliebiger Reihenfolge) vorliegenden Wörter muss ich nun in ihre Teilstrings zerlegen und diese Teilstrings möchte ich in lexikographisch korrekter Reihenfolge in einer Datenstruktur erfassen.
Um es mal an einem Beispiel zu verdeutlichen:
Ich habe folgende Ausgangswörter: a, baa, babaa, ab, abb.
Damit ergeben sich folgende Substrings (Präfixreihe) in lexikographischer Ordnung: a, b, ab, ba, abb, baa, bab, baba, babaa.

Wie realisiert man so etwas programmiertechnisch?
Wie gesagt, ich bin in der Hinsicht völlig "unterbelichtet".
Ich bin gar nicht unbedingt auf konkreten Quellcode aus, sondern ich bin vielmehr an einer allgemeinen Herangehensweise an dieses Problem interessiert.
Also wie gehe ich da grundsätzlich vor? Welche Datenstrukur brauche ich für die Präfixreihe? (z.B. verkettete Liste o.ä.) Braucht man einen Sortieralgorithmus?
Ist der Ausgangspunkt in Form eines Stringarrays (die Ausgangsworte sind in einem Array gespeichert) sinnvoll gewählt oder sollte man lieber eine andere Datenstruktur nehmen?

Die Programmiercracks unter euch können das sicherlich besser einschätzen als ich. Ich will halt auch nicht ewig rumprobieren, um dann festzustellen, dass meine Methode gar nicht funktionieren kann. Ich muss diese Aufgabe (und das hier geschilderte Problem ist nur ein klitzekleines Teilproblem der Gesamtaufgabe) bis spätestens Ende Februar fertig kriegen. Das ist übrigens eine Aufgabe aus der Lehrveranstaltung "Automaten und formale Sprachen", daher auch die "seltsamen" Wörter.
Soweit also meine Anfrage. Ich werde wahrscheinlich mit den nachfolgenden Problemen in Zukunft noch des öfteren hier "reinschneien".

Auf alle Fälle schon mal Danke im Voraus für eure Unterstützung.
Moppel

[Werner Salomon]

Moppel schrieb:

Ich habe eine Reihe von Wörtern vorliegen, gespeichert z.B. in einem Array.
Diese (in beliebiger Reihenfolge) vorliegenden Wörter muss ich nun in ihre Teilstrings zerlegen und diese Teilstrings möchte ich in lexikographisch korrekter Reihenfolge in einer Datenstruktur erfassen.
Um es mal an einem Beispiel zu verdeutlichen:
Ich habe folgende Ausgangswörter: a, baa, babaa, ab, abb.
Damit ergeben sich folgende Substrings (Präfixreihe) in lexikographischer Ordnung: a, b, ab, ba, abb, baa, bab, baba, babaa.

Wie realisiert man so etwas programmiertechnisch?

Hallo Moppel,

Jede Aufgabe beginnt damit, dass man sich über die Anforderungen genau klar wird.
1.) was bedeutet 'in Teilstrings zerlegen' genau?
2.) wie soll die Sortierung aussehen? nach Länge so wie Du es sortiert hast oder lexikographisch (wie von Dir angegeben)?

Mal angenommen Du meinst alle möglichen Teilstrings - das wären allein beim Wort 'babaa':

a aa ab aba abaa b ba baa bab baba babaa

und die Sortierung sei lexikographisch.

Zunächst brauchst Du einen Algorithmus der über alle Wörter läuft.
Jedes Wort soll in alle Teilstrings zerlegt werden. Ein Teilstring kann an einer beliebigen Position innerhalb des Wortes beginnen. D.h. Deine nächste Schleife sollte über alle Zeichen-Positionen 'i' von 0 bis 'Wortlänge - 1' laufen.
Von einer bestimmten Position 'i' aus gesehen, erzeugst Du dann alle Teilstrings von der Länge 1 bis zur Länge 'Wortlänge - i'.
Diese kannst Du gleich sortiert in einen Container eintragen (std::set). Dann fällt die spätere Sortierung weg und gleiche Teilstrings müssen erst gar nicht abgespeichert werden.

Als Datenstrukturen empfehle ich die Container der STL. std::string für die Wörter; std::set< std::string > - wie schon erwähnt - für das Ergebnis. In welcher Art von Speicher die ursprünglichen Wörter stecken sollen, hängt davon ab, wo diese herkommen. Werden sie generiert? Stehen sie fest codiert im Code? Oder liegen sie in einer Datei vor?
Bei fester Codierung einfach ein std::vector< std::string >, falls sie in einer Datei liegen, brauchst Du gar keinen Container, sondern liest sie ein und verarbeitest sie gleich.

Wenn Du Dir dann noch den Algorithmus std::for_each, und den std::inserter zu Hilfe nimmst, so ist das in wenigen Zeilen zu erledigen.

Gruß
Werner

[Moppel]

Danke Werner!

Nun zu den angesprochenen Problemen.
- in Teilstrings zerlegen: soll lexikographisch erfolgen (so wie von mir auch in dem Beispiel angedeutet), allerdings wird als Ausgangspunkt jeweils die Position 0 (bzw. 1) jedes Strings festgelegt.
Mit anderen Worten: eine vollständige Zerlegung in Substrings (wobei man an jeder beliebigen Stelle innerhalb des Wortes beginnen kann - so wie von dir angedeutet) mit anschließender Ordnung erfolgt nicht. Es ergeben sich für das Wort 'babaa' maximal fünf zu sortierende Teilstrings: b, ba, bab, baba, babaa.
Dies ist also auf den ersten Blick eine Sortierung der Länge nach. Bezieht man aber die anderen Wörter mit ein, so ist durchaus eine lexikographische Ordnung erkennbar (siehe mein Beispiel aus der Aufgabenstellung: a, b, ab, ba, abb, baa, bab, baba, babaa).
Man könnte also sagen, eine lexikographische Ordnung unter Beachtung der Länge (oder so ähnlich ).
Wie auch immer, die Aufgabenstellung und damit das zu erreichende Ziel ist mit durchaus klar (ich habe mich immerhin mehr als drei Monate mit der Durchdringung des theoretischen Teils der Aufgabenstellung herumgeschlagen ... und jetzt soll ich es halt auch noch praktisch umsetzen).

- Ursprung der Ausgangswörter: die Wörter werden einfach zum Programmstart innerhalb eines Memos erfasst. Von da können sie dann weiterverarbeitet werden.

Auf jeden Fall erst mal ein dickes Dankeschön für deine Anregungen und Hilfe.
Dann werde ich mich wohl mal mit der STL auseinandersetzen.
Na mal schauen, ob ich damit klar komme.

Danke und bis demnächst
Moppel

P.S.: Letztendlich soll mit diesem Programm anhand von gegebenen Worten ein möglicher regulärer Audruck (für diese Wörter) generiert werden. Keine Ahnung ob ich das hinkriege. Vom theoretischen Teil war mein Prof. jedenfalls ziemlich angetan. Nur mit der Programmierung hapert's halt bei mir...

[Konfusius]

die lösung dieses problems ist weniger dramatisch, als es klingt. die c++-standardbibliothek bietet da nützliche werkeuge.

an deiner stelle würde ich ein stl-set von stl-strings verwenden, um die teilstrings zu speichern. sets speichern jedes element automatisch nur einmal. in wenn ich mich nicht irre, dann bekommst du mit dem iterator für das set die elemente auch noch automatisch aufsteigend sortiert.

du schreibst einfach eine funktion, die als argument teilstring-set, ein wort und die startposition für die teilstrings im wort nimmt. die generiert dann alle teilstrings und fügt sie ins set ein.

diese funktion rufst du für jedes wort auf. anschließend gibst du den inhalt des sets mit dem iterator des sets einfach aus. das sollte dann bereits automatisch sortiert sein.

fertig.

[Cyriz]

Hallo,

ich kann dir ein paar Literatur empfehlungen geben.

Introduction to Algorithms
von Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest

sehr gutes Buch, was auch String matching Probleme behandelt.

Wenn du den Algrithmus selbst erstellen willst.
Solltest du an eine Automaten-Lösung denken, denn die Strings welche die Grammtik a*b* bildet werden wunderbar von FSA akzeptiert.

Man könnte z.B. einen Trie erzeugen, das ist dann sogar noch äußerst effiezient.
Aber ich weis nicht was du genau in der Aufgabe machen sollst...

[Cyriz]

Nochmal ich.

Ich habe folgende Ausgangswörter: a, baa, babaa, ab, abb.
Damit ergeben sich folgende Substrings (Präfixreihe) in lexikographischer Ordnung: a, b, ab, ba, abb, baa, bab, baba, babaa.

warum a,b,?

müsste da nicht

a, ab, ba, baa... rauskommen?

Oder die Sternhülle über dem Eingabealphabet?
Dann wäre es ja egal... man nimmt nur den längsten und erzeugt die Potenzmenge...

Hab ich die Frage falsch verstanden?

grüße

[Moppel]

@Cyriz:

Die Präfixreihe stimmt schon so, wie ich sie angegeben habe, also: a, b, ab, ba, abb, baa, bab, baba, babaa.
Um diese Präfixreihe zu ermitteln, geht man so vor, dass man zunächst alle Teilstrings mit nur einem Buchstaben betrachtet (wobei man immer die Wörter von links nach rechts betrachtet und nicht einfach irgendwo in der Mitte einen Teilstring herauslöst) und entsprechend lexikographisch ordnet. Dann werden die Teilstrings mit zwei Buchstaben betrachtet. Und immer so weiter.
Es ist quasi eine lexikographische Ordnung aller Teilstrings, wobei die Teilstrings jedoch stets am Anfang der Ausgangswörter beginnen. Insofern eine spezielle lexikographische Ordnung.

Auf alle Fälle ein dickes Dankeschön an alle für die Anregungen.
Ich werd' mir dann mal die STL zu Gemüte führen. Mal schauen, ob ich damit zurecht komme.

Ach ja, die komplette Aufgabenstellung lautet wie folgt:
----------------
Entwicklung einer Methode zur Ableitung eines regulären Ausdruckes aus
einer gegebenen Menge von Sätzen einer regulären Sprache, die durch
diesen Ausdruck spezifiziert wird.

Beispiel:
Gegeben sind die Worte: a, baa, babaa, ab, abb, die zu der Sprache
gehören und die Worte aa, bbaa, baba, die nicht zu der Sprache gehören

Worte mit gleichem Präfix, die zu der Sprache gehören, werden
zusammengefaßt:
• a + ab + abb = a(e + b + bb) =verallgemeinert=> ab*. Überprüfung der
Verallgemeinerung mit den Worten, die nicht zu der Sprache gehören -
von diesen wird keines durch den Ausdruck abgedeckt: aa, bbaa, baba sind
nicht Element von ab*
• baa, babaa = (ba + baba)a = verallgemeinert=> (ba)+a. Überprüfung der
Verallgemeine-rung mit den Worten, die nicht zu der Sprache gehören -
von diesen wird keines durch den Ausdruck abgedeckt: aa, bbaa, baba sind
nicht Element von (ba)+a

Damit ist der gesuchte Ausdruck: ab* + (ba)+a
Wenn ein Wort, das nicht zu der Sprache gehört, durch einen Teilausdruck
abgedeckt wird, dann ist dieser zu allgemein und er muß spezialisiert
werden. Das Kann durch anhängen oder Voranstellen von Symbolen oder
durch Benutzung einer Teilmenge geschehen. Z.B ist ab + abab spezieller
als (ab)*.
--------------

Aber das nur der Vollständigkeit halber.
Rein vom theoretischen Hintergrund her, habe ich keine Probleme mit der Durchdringung dieser Aufgabe. Hat mich zwar einiges an Zeit gekostet, aber mittlerweile, weiß ich wie dieses Problem zu lösen ist. Es gibt da einige interessante Algorithmen.
Momentan hapert's bei mir lediglich an der Implementierung des Ganzen.
Na mal schauen, vielleicht krieg ich's ja doch noch hin.

Nun denn, danke noch mal und bis zu meinen nächsten Fragen
Moppel

[Cyriz]

also wenn du Fragen hast immer her damit...
die formale Sprachen und Automatentheorie ist auch eins meiner Lieblingsgebiete.
Besonders das implementieren

gutes gelingen!

gruß

[Werner Salomon]

Moppel schrieb:

Dies ist also auf den ersten Blick eine Sortierung der Länge nach. Bezieht man aber die anderen Wörter mit ein, so ist durchaus eine lexikographische Ordnung erkennbar (siehe mein Beispiel aus der Aufgabenstellung: a, b, ab, ba, abb, baa, bab, baba, babaa).
Man könnte also sagen, eine lexikographische Ordnung unter Beachtung der Länge (oder so ähnlich ).

Na ja, ich verstehe: eine Sortierung nach der Größe unter Beachtung der lexikographischen Ordnung. Noch ein Tipp dazu: in C++ kannst Du das Ordnungskriterium für einen std::set selber festlegen. Man definiert z.B. einen Funktor mit einem Ordnungskriterium Deiner Wahl und diesen Typ gibst Du als 2.Template-Argument an. Dann werden die Teilstrings wie gewünscht in den set geschrieben.
Beispiel:

#include <algorithm>    // copy
#include <iterator>     // ostream_iterator
#include <set>
#include <string>       // string

struct SizeComparator
{
    bool operator()( const std::string& a, const std::string& b ) const
    {
        if( a.size() == b.size() )  // bei gleicher Länge
            return a < b;           //  .. entscheidet die lexikographische Ordnung
        return a.size() < b.size(); // sonst die kurzen nach vorne
    }
};

int main()
{
    using namespace std;
    set< std::string, SizeComparator > s;  // Ordnungs-Funktor mit angeben
    s.insert( "ab" );
    s.insert( "a" );
    s.insert( "b" );
    copy( s.begin(), s.end(), ostream_iterator< string >( cout, " " ) );
    cout << endl;
    return 0;
}

.. lass den SizeComparator einfach mal weg, dann siehst Du den Unterschied.

Gruß
Werner