fachverteilung: auffuellung von woertern durch leerwort? Kontextabhaengigkeit?

[Elessar]

Hallo,


hab mir grade "Sortieren durch Fachverteilung" angesehen. Das Verfahren ist ja sehr einfach, solange alle Wörter aus dem Alphabet dieselbe Länge l besitzen.

Nun zu den Fällen, wo unterschiedlich lange Wörter gegeben sind (laut VO-Skriptum S. 46 explizit erlaubt). Rein aus der Erklärung des Algorithmus im Skriptum ist mir nicht klar, wie verfahren wird, wenn Wörter mit einer Länge < l (l sei die maximale Wortlänge) vorkommen.

Nehmen wir an, das Alphabet besteht nur aus den Zahlen {0, 1, 2, 3, 4}, und wir haben z.B.
123 32 44
Ich könnte "32" und "44" vorne mit einer '0' "auffüllen". Das geht abr nur, weil uns implizit klar ist, dass "032" und "44" dasselbe ist.
Was wäre, wenn
- im obigen Beispiel die "0" nicht Teil des Alphabets wäre? Dann könnte ich nicht auffüllen
- ich irgendwelche Symbole verwende? Ohne Kontext ist dann nicht klar, wie aufgefuellt wird bzw. ob ueberhaupt aufgefuellt werden kann.

Nehmen wir an, ich habe Wörter aus dem Alphabet {'A', .. 'E'}, z.B.:
ABCD, ACC, AF.
Wie soll ich die Wörter mit Länge < 4 einsortieren?
Hätte ich ein Leerwort (sei hier dargestellt durch '_'), könnte ich implizit ACC=ACC_ und AF=AF__ setzen. Das waere jedoch wieder kontextabhaengig: ich weiss, dass Wörter unterschiedlicher Länge mit gleichem Anfangsbuchstaben in einem Wörterbuch alle unter dem Anfangsbuchstaben zu finden sind.

Ist der Algorithmus also kontextabhaengig, bzw, nicht ausreichend genau spezifiziert, oder habe ich etwas grundsaetzliches uebersehen, vergessen, denkfehler usw?


-- Elessar

[locutus]

das auffüllen kann man sich ersparen, wenn man strings die kürzer als die aktuelle länge sind einfach in das niedrigste fach einordnet. das ist dann äquivalent zum auffüllen mit nullen oder leerzeichen.

[Elessar]

hai,

danke erstmal fuer deine Antwort.
Du meinst: strings "normal" von hinten nach vorne bearbeiten und jene die fertig bearbeitet sind, immer ins 1. fach?
Das funktioniert so nur, wenn das Alphabet nur aus Zahlen besteht, und in dem Fall ist es natuerlich dasselbe wie auffuellen mit 0, weil das 1. Fach das Fach mit der '0' ist.
Wenn du das mit Buchstaben *so* machst stoesst du gleich auf 2 Probleme:

1) hast du kein Leerwort (das der '0' bei Zahlen entsprechen wuerde), d.h. die Woerter mit Länge <= l landen im 1. Fach mit 'A'. Wenn du wie bei Zahlen einfach von hinten nach vorne vorgehst, ist das deshalb dasselbe, als wuerdest du die Zahlen *VORNE* mit A's auffuellen. Das ist nicht, was du intuitiv willst.

2) selbst wenn du dem Alphabet ein Leerwort hinzufuegst, hast du noch dasselbe Problem wie unter (1): Du fuellst implizit die Strings mit dem Leerwort auf, aber *VORNE*. Das ist keine alphabetische Sortierung, wie wir sie uns intuitiv erwarten würden. Du musst bei Strings zuerst hinten das Leerwort anhaengen, bis die maximale Länge erreicht ist, oder du bearbeitest Strings mit Laenge < l so lange nicht, bis t=Laenge(String)-1 (da t von 0 bis l-1 laeuft, "rueckwaerts")


Worauf ich eigentlich hinauswollte, ist, dass das kontextabhaengig zu sein scheint, wie man vorgehen muss. Zahlen werden nun mal anders sortiert als Buchstaben, .. aber wie sollen wir z.B. vorgehen, wenn wir *irgendein* Alphabet mit irgendwelchen Zeichen als Eingabe erhalten?
Ich finde nur, der Algorithmus ist so, wie er im Skriptum beschrieben ist, nicht 100% klar, da er Strings unterschiedlicher Laenge ausdruecklich erlaubt, jedoch nicht klar ist, wie mit derartigen Strings verfahren werden soll.

Vielleicht soll das auch so sein, wir sollen selbst nachdenken, und es haengt vom Ziel der Aufgabenstellung ab, .. bzw. von der Implementierung, usw.


-- Elessar