Matroids Matheplanet Forum Index
Moderiert von matroid
Informatik » Algorithmen / Datenstrukturen » Unicode Sortierung mit Quicksort
Druckversion
Druckversion
Antworten
Antworten
Autor
Kein bestimmter Bereich Unicode Sortierung mit Quicksort
Casler
Junior Letzter Besuch: im letzten Quartal
Dabei seit: 25.11.2020
Mitteilungen: 6
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2020-11-25


Ich suche nach einem Algorithmus,
mit dem man Strings/Datensätze sortieren kann,
die keine ASCII sondern Unicode Zeichen enthalten. Ich benutze bisher den Quicksort, der ja ziemlich performant ist, mit zufrienstennden Ergebnissen für ASCII.
Aber mit dem Stringvergleich >= und <= habe ich doch Probleme bei Unicode.
Wer kann mir helfen?



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
DerEinfaeltige
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.02.2015
Mitteilungen: 2626
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, eingetragen 2020-11-25


Wenn du durch paarweisen Vergleich sortieren willst, kannst du natürlich weiterhin QuickSort, MergeSort, HeapSort oder was auch immer verwenden.

Den (vergleichenden) Sortieralgorithmus interessiert es nicht, was du sortierst.


Du musst dich nur festlegen, nach welchem Standard du sortieren willst. Bereits bei ASCII kann man ja über die korrekte Reihenfolge bezüglich Groß-/Kleinschreibung und Sonderzeichen trefflich streiten.

Dann schreibst du den passenden Vergleichsoperator und lässt damit sortieren.


-----------------
Why waste time learning when ignorance is instantaneous?
- Bill Watterson -



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Casler
Junior Letzter Besuch: im letzten Quartal
Dabei seit: 25.11.2020
Mitteilungen: 6
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.2, vom Themenstarter, eingetragen 2020-11-26


Danke, dass du das Problem nochmal mit anderen Worten beschrieben hast.
Aber auf den Vergleich kommt es doch genau an.
Ich habe das mal mit verschiedenen Vergleichsmethoden versucht, aber keine Sortierung erhalten.
Auch ein Sort mit Excell, dem ja egal ist, was es sortiert, hat kein Ergebnis geliefert.
Oder mache ich etwas falsch ?



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
viertel
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 04.03.2003
Mitteilungen: 27700
Herkunft: Hessen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.3, eingetragen 2020-11-26


Hi Casler

Willkommen auf dem Planeten

Da niemand weiß, was du machst, kann auch niemand sagen ob, und wenn ja, was du vielleicht falsch machst.

Casler schreibt:
habe ich doch Probleme bei Unicode
Welche Probleme?

Casler schreibt:
aber keine Sortierung erhalten
Was heißt das? Beispiel?

Gruß vom ¼


-----------------
Bild



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
DerEinfaeltige
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.02.2015
Mitteilungen: 2626
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.4, eingetragen 2020-11-26


Also Python macht keine Zicken:
Python
L = ['hiragana', 'ひらがな', 'drink', 'のむ']
 
print(L)
print(sorted(L))
 
# Ausgabe:
# ['hiragana', 'ひらがな', 'drink', 'のむ']
# ['drink', 'hiragana', 'のむ', 'ひらがな']
 


[Die Antwort wurde nach Beitrag No.2 begonnen.]


-----------------
Why waste time learning when ignorance is instantaneous?
- Bill Watterson -



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
zippy
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 24.10.2018
Mitteilungen: 1784
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.5, eingetragen 2020-11-26


2020-11-26 11:49 - DerEinfaeltige in Beitrag No. 4 schreibt:
Also Python macht keine Zicken:

Emacs auch nicht:
Elisp
(sort '("hiragana" "ひらがな" "drink" "のむ") #'string-lessp)
 
("drink" "hiragana" "のむ" "ひらがな")



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Casler
Junior Letzter Besuch: im letzten Quartal
Dabei seit: 25.11.2020
Mitteilungen: 6
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.6, vom Themenstarter, eingetragen 2020-11-27


Ja danke soweit, die Beiträge mit japanischer Schrift gehen in die richtige Richtung.
Und tatsächlich konnte ich solche eine Sortierung nun auch erreichen.
Nun kommt der zweite Teil meiner Frage:
Im Japanischen oder chinesischen möchte man bei der Sortierung keine Zeichen an den oberen Stellen sehen, die eigentlich sehr selten verwendet werden.
Also muss man so etwas wie Kollation betreiben.
Meine Frage lautet nun ganz konkret: wie kann ich dem Sortieralgorithmus sagen, da wo du zwischen >,= oder < unterscheidest gilt nicht die ASCII-Reihenfolge sondern eine eigene? (Einen Sortierparameter gibts wohl nicht?)
Das klingt nach Hinterlegung einer Tabelle. Aber das kann auch das schelle Sortieren mit QuickSort stark verlangsamen.
Also geht es mir auch um eine ertragbare Geschwindigkeit beim Sortieren von sagen wir mal 200.000 Sätzen.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
zippy
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 24.10.2018
Mitteilungen: 1784
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.7, eingetragen 2020-11-27


2020-11-27 11:51 - Casler in Beitrag No. 6 schreibt:
(Einen Sortierparameter gibts wohl nicht?)

Das hängt von der Sprache ab, die du verwendest.

In meinem Beispiel ist das zweite Argument von sort die Funktion, die die gewünschte Reihenfolge definiert:

   (sort '("hiragana" "ひらがな" "drink" "のむ") #'string-lessp)

Ich habe für dieses Argument string-lessp eingesetzt, das die übliche lexikographische Ordnung abbildet. Aber man könnte genausogut eine selbstdefinierte Funktion übergeben, die eine andere Reihenfolge abbildet.

Ähnliche Sortierfunktionen gibt es in so gut wie jeder Sprache.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Casler
Junior Letzter Besuch: im letzten Quartal
Dabei seit: 25.11.2020
Mitteilungen: 6
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.8, vom Themenstarter, eingetragen 2020-11-27


Was meinst du hier mit Sprache ?
(Programmiersprache oder Sprachen wie Japanisch?)
und was ist im Japanischen oder Chinesischen lexikographisch?




Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
DerEinfaeltige
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.02.2015
Mitteilungen: 2626
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.9, eingetragen 2020-11-27


Da Excel angesprochen wurde:

Excel hat Sortierfunktionen für viele Sprachen meines Wissens nach (bzw. gemäß kurzer Googlesuche) in den entsprechenden Sprachpaketen.

Man muss ja nicht nach China oder Japan reisen.
Bereits Deutsch sortiert im Allgemeinen nicht nach Unicodetabelle, sondern ignoriert Groß-/Kleinschreibung, wertet Umlaute wie Basiskonsonanten und "ß" als "ss".
Die anderen europäischen Sprachen haben für Umlaute, Akzente und Sonderzeichen wiederum eigene Standards.

Die Sprachpakete für Japanisch und Chinesisch bieten mit Sicherheit ebenfalls alle dort üblichen Sortierstandards.

[Die Antwort wurde nach Beitrag No.7 begonnen.]


-----------------
Why waste time learning when ignorance is instantaneous?
- Bill Watterson -



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
viertel
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 04.03.2003
Mitteilungen: 27700
Herkunft: Hessen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.10, eingetragen 2020-11-27


2020-11-27 13:14 - Casler in Beitrag No. 8 schreibt:
Was meinst du hier mit Sprache ?
(Programmiersprache oder Sprachen wie Japanisch?)
und was ist im Japanischen oder Chinesischen lexikographisch?

Ich hatte es bereits angesprochen:
2020-11-26 11:34 - viertel in Beitrag No. 3 schreibt:
Da niemand weiß, was du machst, kann auch niemand sagen ob, und wenn ja, was du vielleicht falsch machst.

Mit Sprache ist natürlich die Programmiersprache gemeint. Womit programmierst du?
Irgendwie mußt du doch den Quicksort implementiert haben.
Und da gibt es eine Stelle, wo du den Vergleich zweier Strings machst. Anstatt den Stringvergleich der von dir benutzen Programmiersprache zu verwenden mußt du dort deine eigene Vergleichsfunktion einbauen. Dann hast du es in der Hand, nach welchem Kriterium du sortierst. Du könntest die beiden Strings rückwärts nehmen und vergleichen, oder erst ab dem zweiten Zeichen. Oder eben so, wie du es gerne hättest.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Casler
Junior Letzter Besuch: im letzten Quartal
Dabei seit: 25.11.2020
Mitteilungen: 6
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.11, vom Themenstarter, eingetragen 2020-11-27


Ja genau und das habe ich ja doch gemacht, siehe oben.
Mit meiner etwas antiquierten Programmiersprache funktioniert der
Quicksort für ASCII-Vergleich wunderbar.
Nun habe ich für die Unicode-Vergleich an den Stellen < oder > eigene Vergleiche angelegt, die aber nicht funktioniert haben.
Die Unicode-Zeichen sind 3 Byte lang, also muss ich auch 3 Byte zusammen untersuchen.
Nun muss ich wohl mit den 3 Byte eine eindeutige Größe suchen, vermutlich in einer noch zu erstellenden Tabelle.
Die Größe entscheidet dann ob < oder > zutrifft.

bisher hatte ich folgendes für die  <  Entscheidung:

txt1 und txt2 sind die zu vergleichenden Größen

 vt1 = 0
 vt2 = 0
 i = 0
 LT_U8 = False
 While vt1 = vt2 And i < Minimum Länge von txt1 und txt2
    i = i + 1
    vt1 = Asc(Mid(txt1, i, 1))
    vt2 = Asc(Mid(txt2, i, 1))
    If vt1 < vt2 Then
       LT_U8 = True
       Exit
    End If
    If vt1 > vt2 Then
       LT_U8 = False
       Exit
    End If
 Wend
' wenn vt1 = vt2
If n1 < n2 Then
  LT_U8 = True
End If

das liefert nur einen byteweisen Vergleich (aber scheint fehlerhaft zu sein) und auch nicht das gewünschte Ergebnis.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
zippy
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 24.10.2018
Mitteilungen: 1784
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.12, eingetragen 2020-11-28


Wenn ich es richtig verstehe, arbeitest du mit einer Programmiersprache, die Unicode-Zeichen nicht kennt, und du verwendest die ASCII-Zeichenketten dieser Sprache, um die Bytes einer Unicode-Codierung zu speichern. Das ist natürlich möglich, macht die Sortierung aber unnötig kompliziert.

2020-11-27 23:56 - Casler in Beitrag No. 11 schreibt:
Die Unicode-Zeichen sind 3 Byte lang

Was für eine Codierung verwendest du denn?

Als Codierung, in der alle Unicode-Zeichen die gleiche Zahl von Bytes benötigen, ist mir nur UTF-32 bekannt, und da wären es 4 Bytes je Unicode-Zeichen.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Casler
Junior Letzter Besuch: im letzten Quartal
Dabei seit: 25.11.2020
Mitteilungen: 6
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.13, vom Themenstarter, eingetragen 2020-11-28


Es handelt sich um eine UTF-8-Kodierung, zumindest zeigt, der Windows 10-Editor das so an. Und wenn ich mir den Hex-Code der Zeichen ansehe, so sind sie 3 Byte lang. Vielleich trifft dies nicht auf alle Unicode-Zeichen zu, aber für die von mir bisher verarbeiteten schon.
Woran erkenn ich, dass das Zeichen 4 Byte hat?
Natürlich gibt es auch kürzere, nämlich  die deutschen Umlaute, die haben nur 2 Byte und die normalen ASCII-Zeichen verwenden nur 1 Byte. Alles bekannt.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
DerEinfaeltige
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.02.2015
Mitteilungen: 2626
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.14, eingetragen 2020-11-28


2020-11-28 14:32 - Casler in Beitrag No. 13 schreibt:
Es handelt sich um eine UTF-8-Kodierung, zumindest zeigt, der Windows 10-Editor das so an. Und wenn ich mir den Hex-Code der Zeichen ansehe, so sind sie 3 Byte lang. Vielleich trifft dies nicht auf alle Unicode-Zeichen zu, aber für die von mir bisher verarbeiteten schon.
Woran erkenn ich, dass das Zeichen 4 Byte hat?
Natürlich gibt es auch kürzere, nämlich  die deutschen Umlaute, die haben nur 2 Byte und die normalen ASCII-Zeichen verwenden nur 1 Byte. Alles bekannt.

Wenn der Standard bekannt ist, sollte auch bekannt sein, dass man die Länge an der Anzahl führender 1-en im ersten Byte erkennt.


-----------------
Why waste time learning when ignorance is instantaneous?
- Bill Watterson -



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Casler hat die Antworten auf ihre/seine Frage gesehen.
Neues Thema [Neues Thema] Antworten [Antworten]    Druckversion [Druckversion]

 


Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2021 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]