109
edits
Line 122: | Line 122: | ||
Unkomprimiert, aber mit Differenzenbildung reduziert sich das zu: | Unkomprimiert, aber mit Differenzenbildung reduziert sich das zu: | ||
(3,27), (2,3), (0,17), (7, 25) | (3,27), (2,3), (0,17), (7, 25) | ||
=ZenoReader/Qunicode= | |||
Aus DirectWiki | |||
Wechseln zu: Navigation, Suche | |||
Inhaltsverzeichnis | |||
1 Codierung | |||
2 Vergleichsroutine | |||
3 Folding | |||
4 Testroutine | |||
[bearbeiten] Codierung | |||
Die Artikeltitel sind in einem eigenen Format codiert, da UTF8 oder ähnliches Geschwindigkeitsnachteile beim Sortieren und Matchen bringt. Es ist eine Ad-hoc-Codierung, die davon ausgeht, dass Characters mit den Werten 1 und 2 nicht im Titel vorkommen. Ein Byte mit dem Wert 1 zeigt an, dass die nachfolgenden 2 Bytes als 2-Byte-Unicode zu interpretieren sind. Um Nullbytes im String zu vermeiden wird der Wert 2 genommen, wenn das niedrige Byte des 2-Byte-Unicode null ist, das dann als 1 (?) codiert ist. Das hohe Byte kann niemals Null sein, da $20..$FF sowieso als ein Byte codiert werden. | |||
Beispielhaft sei die Funktion QunicodeToXML angeführt: | |||
function QunicodeToXML (const qunicode: string): string; | |||
type | |||
PWord = ^word; | |||
var | |||
l: integer; | |||
p: PChar; | |||
entity: string[8]; | |||
begin | |||
if qunicode='' then begin | |||
Result := ''; | |||
exit; | |||
end; | |||
SetLength(Result, 8*Length(qunicode)); | |||
l := 0; | |||
p := @qunicode[1]; | |||
while p^<>#0 do begin | |||
case p^ of | |||
#1: begin | |||
inc(p); | |||
entity := '&#x'+IntToHex(PWord(p)^, 4)+';'; | |||
Move(entity[1], Result[l+1], 8); | |||
inc(p, 2); | |||
inc(l, 8); | |||
end; | |||
#2: begin | |||
inc(p); | |||
entity := '&#x'+IntToHex(PWord(p)^ and $FF00, 4)+';'; | |||
Move(entity[1], Result[l+1], 8); | |||
inc(p, 2); | |||
inc(l, 8); | |||
end; | |||
else | |||
inc(l); | |||
Result[l] := p^; | |||
inc(p); | |||
end; | |||
end; | |||
SetLength(Result, l); | |||
end; | |||
Diese Codierung erlaubt ein schnelleres Sortieren und Matchen und ist - bei westeuropäischen Texten - meist sogar kürzer als UTF-8, was daran liegt, dass Umlaute weiterhin nur ein Byte benötigen. | |||
[bearbeiten] Vergleichsroutine | |||
Für das Sortieren und Finden benötigt man eine Vergleichsroutine zweier Qunicode-Strings: | |||
function PCharCompareUseTable (p1, p2: PChar): integer; | |||
var | |||
px1, px2: PChar; | |||
begin | |||
px1 := p1; | |||
px2 := p2; | |||
while true do begin | |||
if p1^=#0 then begin | |||
if p2^=#0 then begin | |||
break; | |||
end else begin | |||
Result := -1; | |||
exit; | |||
end; | |||
end else if p2^=#0 then begin | |||
Result := 1; | |||
exit; | |||
end else begin | |||
Result := ord(_ZZZ[ord(p1^)])-ord(_ZZZ[ord(p2^)]); | |||
if Result<>0 then begin | |||
exit; | |||
end; | |||
inc(p1); | |||
inc(p2); | |||
end; | |||
end; | |||
// laut table gleich, jetzt ASCII-Vergleich | |||
while true do begin | |||
if px1^=#0 then begin | |||
if px2^=#0 then begin | |||
Result := 0; | |||
exit; | |||
end else begin | |||
Result := -1; | |||
exit; | |||
end; | |||
end else if px2^=#0 then begin | |||
Result := 1; | |||
exit; | |||
end else begin | |||
Result := ord(px1^)-ord(px2^); | |||
if Result<>0 then begin | |||
exit; | |||
end; | |||
inc(px1); | |||
inc(px2); | |||
end; | |||
end; | |||
end; | |||
Entscheidend ist dabei das Folding von 2-Byte-Zeichen auf 1-Byte-Zeichen, um Umlaute und diakritische Zeichen "richtiger" zu sortieren als es per Bytevergleich wäre. "Richtiger" deshalb, da "richtig" einen enormen Aufwand darstellen würde, siehe Unicode Collation Algorithm. | |||
PCharCompareUseTable besteht aus zwei Teilen: Zuerst wird der String gefaltet verglichen, wenn er gleich ist, wird der Unicode-Wert genommen. Dies hat folgende Vorteile: | |||
A, a, Ä, a, Ā, ā usw. stehen vor B, b, ... | |||
A, a, Ä, a, Ā, ā sortiert ergibt genau die Reihenfolge, die hier steht | |||
Wichtig: Diese Sortierung entspricht keiner Norm - sie ist eher so etwas wie eine intuitive Sotierung, die für Sprachen im Latin-Alphabet brauchbare Ergebnisse liefert. Da Offline-Wikipedia in allen Sprachen funktionieren soll, wäre es wünschenswert, doch den Unicode Collation Algorithm zu implementieren - es muss erstmal eine Aufwands- und Runtimeverhalten-Abschätzung her. | |||
[bearbeiten] Folding | |||
_ZZZ ist ein array [0..$FFFF], in dem jedem 2-Byte-Unicode ein ASCII-Zeichen 0..$7F zugeordnet wird. Die Tabelle: qunicode.zip. | |||
Diese Tabelle kann für alle 2-Byte-Unicodes erweitert werden; das Folding von z.B. chinesischen Zeichen auf ASCII-Zeichen stellt dann eine Art Hashfunktion dar, mit der bei Eingabe eines chinesischen Strings ein passender Match (aber u.U. noch mehr) gefunden werden kann. Die Tabelle sollte Bestandteil einer Zeno-Datei sein! | |||
[bearbeiten] Testroutine | |||
Da die Artikel in einer Zeno-Datei vorsortiert sind, ist es ein guter Test festzustellen, ob mit der selbst geschriebenen Compare-Routine dies auch weiterhin stimmt. Das muss zwingend der Fall sein, damit beim Laden des Headers der Zeno-Datei nicht jedesmal sortiert werden muss. |