Strings: Lexicographic order

sab
Mausschubser
Mausschubser
Beiträge: 97
Registriert: 28. Okt 2011 08:42

Strings: Lexicographic order

Beitrag von sab »

Hallo,

ich habe eine Frage zur lexikographischen Anordnung.
Damit ein String str1 lexikographisch kleiner ist als str2, muss gelten str1 \(\neq\) str2 \(-\) das ist mir auch klar.
Und dann muss noch eine der zwei Bedinungen erfüllt sein:
  1. 1. Es soll gelten \(l(str1) < l(str2)~-\) das ist auch klar.
    2. Allerdings wird mir diese Bedingung hier nicht klar: Let \(\ell:=\min\{\ell(str1),\ell(str2)\}\) for short. Let \(k:=\min\left\{i\,|\,i\in\{1,\ldots,\ell\},\,str1\neq str2\right\}\). Now the second condition is \(str1[k] < [str2[k]\)

Was hat es mit diesem k auf sich? Wenn ich den String str1 = ab und str2 = abcde, dann ist str1 \(\neq\) str2 und \(l(str1) < l(str2)\). Mir wird nicht ganz klar, wie ich jetzt die zweite Bedingung ausdrücke. Ich habe ein l, das den kürzern String bestimmt. Das k drückt aus, dass an jeder Stelle dieses kürzeren Strings str1 und str2 ungleich sein sollen? Das würde in meinen Augen keinen Sinn machen, weil sie ja bis zu diesem l gleich sind.

Kann mir jemand auf die Sprünge helfen? Danke!

Seldon
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 119
Registriert: 19. Apr 2012 18:12

Re: Strings: Lexicographic order

Beitrag von Seldon »

Wie du schon geschrieben hast: Es muss nur eine Möglichkeit zutreffen. Die erste Bedingung \(l(str1) < l(str2)\) ist auch nicht ganz korrekt zitiert: Da steht "\(str1\) is a proper prefix of \(str2\)" wo dann das < drin vorkommt. Bei deinem Beispiel ist str1 ein echtes Präfix von str2 und deswegen str1 lexikographisch kleiner als str2. Für die zweite Möglichkeit: Wenn man beispielsweise die beiden Strings str1 = tree und str2 = text hat, dann ist l = 4 und k ist der Index des ersten verschiedenen Zeichens (es wird ein Minimum über alle Positionen mit unterschiedlichen Zeichen gebildet), also 2. Dann ist str2[2] < str1[2] und somit \(text \prec tree\).

sab
Mausschubser
Mausschubser
Beiträge: 97
Registriert: 28. Okt 2011 08:42

Re: Strings: Lexicographic order

Beitrag von sab »

Seldon hat geschrieben:Die erste Bedingung \(l(str1) < l(str2)\) ist auch nicht ganz korrekt zitiert: Da steht "\(str1\) is a proper prefix of \(str2\)" wo dann das < drin vorkommt.
Ja, das stimmt. Aber "a proper prefix" ist ja, wie du sagst, \(l(str1) < l(str2)\).
Seldon hat geschrieben:Bei deinem Beispiel ist str1 ein echtes Präfix von str2 und deswegen str1 lexikographisch kleiner als str2. Für die zweite Möglichkeit: Wenn man beispielsweise die beiden Strings str1 = tree und str2 = text hat, dann ist l = 4 und k ist der Index des ersten verschiedenen Zeichens (es wird ein Minimum über alle Positionen mit unterschiedlichen Zeichen gebildet), also 2. Dann ist str2[2] < str1[2] und somit \(text \prec tree\).
Vielen Dank, jetzt ist es mir klar geworden! Ich habe immer die falschen Beispiele gewählt (jetzt verstehe ich, was Herr Weihe mit der Gefährlichkeit der Beispiele meint ;)

Benutzeravatar
JannikV
Nerd
Nerd
Beiträge: 609
Registriert: 24. Apr 2011 12:42

Re: Strings: Lexicographic order

Beitrag von JannikV »

sab hat geschrieben:Ja, das stimmt. Aber "a proper prefix" ist ja, wie du sagst, \(l(str1) < l(str2)\).
Das linke impliziert das rechte, aber es nicht das gleiche. Denn nur weil ein String kürzer ist als ein anderer ist er nicht unbedingt lexikographisch kleiner.

VG

sab
Mausschubser
Mausschubser
Beiträge: 97
Registriert: 28. Okt 2011 08:42

Re: Strings: Lexicographic order

Beitrag von sab »

JannikV hat geschrieben:Das linke impliziert das rechte, aber es nicht das gleiche. Denn nur weil ein String kürzer ist als ein anderer ist er nicht unbedingt lexikographisch kleiner.
Danke für den Hinweis, ihr habt vollkommen Recht - ich habe die Bedingung unvollständig „übersetzt“!

Antworten

Zurück zu „Archiv“