Sommer Sitzung 08

Softwaretechnologie: Java (Teil II, Sommersemester), Notizen zu Sitzung 8

Thema	Stichworte	Material
Überblick	Weiter Richtung Praxis: Sortieralgorithmen OK, aber welche generellen Kriterien zum Zeichenkettenvergleich, z.B. beim Sortieren	Beispiele und Literatur: Home
Grundsätzliches Problem	Wie z.B. beim Sortieren Strings vergleichen? – compareTo; Default für compareTo in Java? – Position in Unicode; in Unicode-Tabelle: erstmal alle Großbuchstaben, dann weitere ASCII-Zeichen, dann alles Andere; d.h. heißt konkret zum Sortieren? – Bsp. "Very", "Über", "very", "ultra", "über" → "Very", "ultra", "very", "Über", "über"; Probleme hier: Großbuchstaben, Umlaute	s. Code: basicProblem
Grundsätzliche Lösung	Was kann man machen? – wir definieren die korrekte Reihenfolge, sortieren nach der Reihenfolge, statt nach dem Wert; wie z.B. umsetzen? – Map: Map<Character,Integer> keys...; keys.put('A', 1); alternativ: Int-Array, mit numerischem Wert des Zeichens als Index im Array, und der Sortierpriorität als Wert, z.B. int[] keys...; keys['A'] = 1; und dann was im Algorithmus? – map.get(x).compareTo(map.get(y)) statt x.compareTo(y); so "Very", "Über", "very", "ultra", "über" → "ultra", "Über", "über", "Very", "very"	s. Code: basicSolution
Verwendung: Comparator, Strategy-Pattern	Wie Verleichskriterium ändern, aber Algorithmus verwenden? – quasi das Verleichskriterium mit übergeben; d.h. in Java: beim Aufruf von Collections.sort zusätzlich angeben, wie sortiert werden soll, d.h. welche Sortierstrategie verwendet werden soll; sowas in Java mit dem Strategy-Pattern: wir übergeben der sort-Methode neben der zu sortierenden Collection auch ein Objekt, das die zu sortierenden Werte vergleicht; konkret: eine Implementierung von Comparator<T> als anonyme Klasse: prinzipiell Collections.sort(words, new Comparator<String>());; z.B. per Content Assist in Eclipse expandieren, s. Code; im Comparator dann statt die Strings zu vergleichen, die Values in der Map vergleichen; warum überhaupt Strategy? – so verbesserte Wiederverwertbarkeit: Sortieralgorithmus immer gleich, Vergleichskriterien/Collation ist austauschbar; so "Very", "Über", "very", "ultra", "über" → "über", "Über", "ultra", "very", "Very"	s. Code: basicSolution
Verwendung: Comparable	Wenn wir die Objekte selbst schreiben, und das Sortieren nicht von Objekt-externen Kriterien abhängt (z.B. Bsp. oben, Sortierfolge; oder Ranking von Ergebnissen relativ zu einer Suchanfrage): Comparable wie schon gesehen, dann Aufruf so, als würden die Objekte automatisch korrekt sortiert: Collections.sort(words);	s. Code: comparable
Weitergehende Sortierregeln natürlicher Sprachen	Weitere Sonderfälle, nicht abgedeckt von einfacher Lösung? – Expansion (behandle ein einzelnes Zeichen wie mehrere Zeichen, z.B. ß wie ss oder ä wie ae einsortieren); Kontraktion (behandle mehrere Zeichen wie ein einzelnes, z.B. spanisch ch eigenes Phonem, das zwischen c und d sortiert wird, statt innerhalb von c); Groß- und Kleinschreibung (erst relevant wann? – wenn alle Buchstaben gleich, d.h. es ist ein sekundäres Kriterium); Diakritika (auch sekundär, erst relevant wenn alles sonst identisch); Lösung in der Praxis hat drei Ebenen/Sortierschritte: Primär-, Sekundär- und Tertiär-Vergleich; z.B. 1. Zeichen, 2. Diakritika, 3. Groß- und Kleinschreibung	—
Implementierung weitergehender Regeln	Zudem ev. Unicode-Issues, Zeichen nicht eindeutig, weil Unicode Sachen kombiniert (z.B. Diakritika, sowas z.B. zerlegen) und andere Zeichensysteme (z.B. römisch 4? – IV, in Unicode auch als eigenes Zeichen, sowas z.B. zusammenführen); für Vergleich daher vereinheitlichen, z.B. alles in Mehrzeichendarstellung (Decomposition) oder alles in Einzeichendarstellung (Composition); d.h. wie z.B. ss-ß lösen in unserem Ansatz mit der Map? – Composition, d.h. alle ss zu ß machen, ß ist in Map; d.h. insgesamt: Problem ist komplex und regionalspezifisch	—
java.text.Collator und java.util.Locale	Java hat die Klasse java.util.Locale (‘Region’) für kulturelle Besonderheiten der verschiedenen Länder; z.B.? – Zeit- und Datumsformat; Zahlendarstellung; auch Sortierung; d.h. Collator mit vordefinierten Regeln einer Locale verwenden; woher kennt der Rechner die Landeseinstellungen? – auf Betriebssytem-Ebene eingestellt, z.B. bei Installation angeben; in Java: bei Start der Runtime wird die Betriebssystem-Locale als Default verfügbar gemacht (Locale.getDefault()); d.h. was macht wohl der Collator wenn keine Locale spezifiziert ist? – Default-Locale des Betriebssystems; so lassen sich prinzipiell sehr einfach ortsspezifische Applikationen in Java entwickeln (weil man wie hier z.B. gar nichts anpassen muss); Verwendung in Comparator s. Code: Erzeugung und Collator#compare	s. Code: collator
Optimierung beim Sortieren	Collator#compare wandelt String in eine Repräsentation zum Vergleich um; beim Sortieren so was für ein Problem? – für gleiche Strings immer wieder neue Berechnung der Collation-Keys; wie optimieren? – für jeden Wert einmal den Key berechnen, und den beim Sortieren, d.h. z.B. im Comparator vergleichen; wie umsetzen, z.B. eigene Klassen? – key als Attribut, im Konstruktor berechnen; Bsp.-Klasse mit Optimierung und Comparable siehe Code; für bestehende Klassen, z.B. String? – z.B. einmal eine Map<String, CollationKey> keys bauen, und im Comparator keys.get(val1) und keys.get(val2) vergleichen	s. Code: comparable
Definition eigener Regeln	Sortierregeln komplex, mit Expansion, Sekundär- und Tertiärmerkmalen; RuleBasedCollator implementiert daher eine eigene Beschreibungssprache für die Regeln, d.h. man kann eigene Regeln schreiben; oder bestehende erweitern; dabei Unterscheidung Primär- (<), Sekundär- (;) und Tertiär-Vergleich (,); unterstützt Kontraktion, d.h. mehr als ein Zeichen als Vergleichselement, z.B. Regel oben: c < ch < d; mit deutschem Standard-Collator entsprechend neuen Rechtschreibung ß wie ss, wenn gleich ß nach ss; z.B. "Löss", "Lee", "Luv", "Löß" → "Lee", "Löss", "Löß", "Luv"; Beispiel-Anforderung: generell ß vor ss, sonst alles normal? – dem RuleBasedCollator zusätzlich zu den Standard-Regeln: ß < ss übergeben; oder ß ; ss als Sekundärregel; dann "Löss", "Lee", "Luv", "Löß" → "Lee", "Löß", "Löss", "Luv"; zu Details s. Literatur, zur Implementierung s. Code (Regeln von Default-RuleBasedCollator holen, eigene dranhängen, damit neuen RuleBasedCollator erzeugen)	s. Code: customRules
Hausaufgabe	Telefonbuch mit lexikalisch korrekter Sortierung; nach 1. Nachname und 2.Vorname	Sommer-Aufgabe-07