Revision as of 16:17, 26 June 2009

Documentation by Erwin Jurschitza (DirectMedia Verlagsgesellschaft Berlin, http://www.directmedia.de/).

ZenoReader/Library

Die Dokumentation wurde für das Zeno-2.0-Format aktualisiert!

Aufbau einer .zeno-Datei

Header

Nach dem Öffnen der Datei muss der Header eingelesen werden, er steht am Anfang der Datei.

TZenoLibraryHeaderFlag = (zlfIsIndex);
TZenoLibraryHeaderFlags = set of TZenoLibraryHeaderFlag;

TZenoLibraryHeader = record
  rMagicNumber: integer;            // Erkennungsmarke, muss immer den Wert 1439867043 haben
  rVersion: integer;                // wp2006=2, wp2007=3, bei Formatänderungen wird hochgezählt
  rCount: integer;                  // Anzahl der Artikel
  rUnused1: integer;                // da Delphi anscheinend Int64 auf 8-Byte-Grenzen legt entsteht diese Lücke
  rIndexPos: Int64;                 // Position des Inhaltsverzeichnisses
  rIndexLen: integer;               // Länge des Inhaltsverzeichnisses
  rUnused2: integer;                // vormals rFlags 
  rIndexPtrPos: Int64;              // Position der Zeigerliste auf das Inhaltsverzeichnis
  rIndexPtrLen: integer;            // Länge der Zeigerliste auf das Inhaltsverzeichnis, also 4*rCount
  rTreeDataPos: Int64;              // bei wp nicht benutzt
  rTreeDataLen: integer;            // bei wp nicht benutzt
  rIndexTotalArticleCount: integer; // nur für die Indexdatei
  rIsIndexCompressed: boolean;      // in der ausgelieferten Version immer true bei der Indexdatei
  rNamespaceCountPos: int64;        // Fileposition der Tabelle, die Infos über die Namespaces hat, siehe unten
  rNamespaceCountLen: integer;      // Länge dieser Tabelle, z.Zt. fix auf 368 Bytes (8 Bytes * 46 Namespaces)
  rUnused: array [0..57] of integer;// mehr Luft als hier vorher war
end;

Inhaltsverzeichnis

Um den Code erstmal einfach zu halten, wird das ganze Inhaltsverzeichnis auf einen Schlag eingelesen (kann mit dem Parameter /f erzwungen werden, bringt Geschwindigkeitsgewinn auf Kosten von RAM).

 TWPVLibrary = class (TObject)
 private
   FBuffer: array of byte;   // das Inhaltsverzeichnis als Byte-Stream mit Records variabler Länge
   FBufferSize: integer;

Auf jeden Fall ganz eingelesen werden muss die Zeigerliste auf das Inhaltsverzeichnis. Sie wird in einer Listenstruktur gehalten, könnte aber auch ein array of integer sein. Die Liste ist vorsortiert, siehe ZenoReader/Qunicode.

   FList: TList;

Beispiel: Das nullte Element der Liste hat den Wert 0 und zeigt auf Nullte Byte in FBuffer. Das erste Element hat z.B. den Wert 56 und zeigt auf das 56. Byte in FBuffer, was einem Zeiger auf den zweiten Eintrag des Inhaltsverzeichnisses entspricht, usw. Dabei ist der Inhalt von FBuffer folgendermaßen zu interpretieren:

 TZenoLibraryCompressionType = (zenocompDefault, zenocompNone, zenocompZip);
 TZenoLibraryMimeType = (ZenomimeTextHtml, ZenomimeTextPlain, ZenomimeImageJpeg, ZenoMimeImagePng, 
                         ZenoMimeImageTiff, ZenoMimeTextCss, ZenoMimeImageGif, ZenoMimeIndex, 
                         ZenoMimeApplicationJavaScript, ZenoMimeImageIcon, ZenoMimeTextXml)

 RZenoArticle = packed record
   rFilePos: Int64;                            // 8 Byte, absolute Position der Artikeldaten im Stream 
   rFileLen: cardinal;                         // 4 Byte, Läge der Artikeldaten
   rCompression: TZenoLibraryCompressionType;  // 1 Byte
   rMime: TWPVLibraryMimeType;                 // 1 Byte
   rRedirectFlag: char;                        // wird demnächst verwendet
   rNamespace: char;                           // A, B, ...
   rRedirectIndex: integer;                    // 4 Byte, wenn rRedirectFlag dann hier der Artikelindex des Hauptartikels
   rLogicalNumber: integer;                    // 4 Byte, in wp nicht benutzt
   rExtraLen: word;                            // 2-Byte-Länge des nachfolgenden Strings inklusive Nullbyte
   rExtra: array [0..$FFF] of char;            // Artikeltitel, Nullbyte, evtl. Parameter wie h=200, durch Nullbyte getrennt
 end;

Es ist zu beachten, dass der Record auf Bytegrenzen gepackt ist, d.h. ohne rExtra genau 26 Byte groß ist. Durch das zwingene Nullbyte in rExtra auch bei einem leeren Artikeltitel ist somit jeder Eintrag mindestens 27 Byte groß.

Zusatzdaten bei Indexdateien

Die Artikel der Indexdateien gehören zu folgenden Namespaces:

V/xxx: alle Artikel der Kategorie xxx, alphabetisch sortiert
W/xxx: alle Artikel der Kategorie xxx, nach Artikelindex sortiert
X/xxx: alle Artikel in denen das Wort xxx vorkommt, nach Artikelindex sortiert
Y/xxx: reserviert für Weblinks (in WP-zeno nicht vorhanden)
Z/xxx: reserviert für hervorgehobene Wortgruppen (in WP-zeno nicht vorhanden)

Ein Eintrag für V und W ist ein 4-Byte-Integer (Artikelindex), ein Eintrag für X ein 8-Byte-Integer (Artikelindex und Wortindex). Nach dem abschließenden Nullbyte des Wortes in rExtra kommt ein Längenbyte für die nachfolgende Struktur, das stets <= 255 ist. Alle Integers sind komprimiert, siehe unten.

flags: die ersten vier Bit geben an, ob es einen Eintrag für die Gewichtung (0..3) gibt, auch dieses Byte ist (unnötigerweise) schon komprimiert, d.h. in komprimiertem Zustand sind die Bits um 2 nach links verschoben.

Für jede Gewichtung folgt ein Eintrag:

len: Länge des Streams in der Datei in Bytes
firstArticleIndex: bei V, W, X
firstWordIndex: nur bei X

Der erste Eintrag einer jeden Gewichtung befindet sich somit in RZenoArticle und ist schnell zu lesen. Gibt es nur diesen einen Eintrag, ist len=0, ansonsten gibt es weitere Einträge in der Indexdatei.

NamespaceCounts-Tabelle

Gültige Namespace-Characters (TLibNamespaceChar) gehen von '-' bis 'Z', also 46 verschiedene Namespaces. Da die Artikel aufsteigend nach Namespace angelegt sind, kann man mit dem Startindex und der Anzahl der Artikel für diesen Namespace gut auf einen bestimmten Namespace zugreifen, z.B. wenn die Wildcardsuche über den ganzen Namespace 'X' (und nur über den) laufen soll.

 RNamespaceStartCount = record
   rNamespaceStart: integer;  // Startindex ist 1, nicht 0
   rNamespaceCount: integer;
 end;

 RNamespaceStartCountArray = array [TLibNamespaceChar] of RNamespaceStartCount;

Integer-Komprimierung

Bei komprimierten Indexdateien sind sowohl die Zusatzdaten (s.o.) als auch die Daten in der Indexdatei wie folgt komprimiert: Die ersten beiden Bits des ersten Bytes sind reserviert und codieren ob es sich insgesamt um 1, 2, 3 oder 4 Byte handelt, die einen (Pseudo-)-Integer zwischen 0 und $4040403F codieren.

1 Byte : Wertebereich 0 bis 26-1
2 Bytes: Wertebereich 26 bis 214+26-1
3 Bytes: Wertebereich 214+26 bis 222+214+26-1
3 Bytes: Wertebereich 222+214+26 bis 230+222+214+26-1

Ferner wird bei manchen Streams von Interegers noch die Eigenschaft ausgenutzt, dass sie aufsteigend sortiert sind, was bei der Indexdatei für die Namespaces "W" und "X" gilt. Der Integer-Compressor/Decompressor hat eine Property, die das Verhalten steuert:

TIntegerCompressionType = 
  (ictNone,        // keine Komprimierung, je 4 Bytes pro Integer
   ict2Bits,       // Komprimierung wie oben beschrieben, 1-4 Bytes, verwendet für den
                   // Namespace V, da dort die Artikel alphabetisch sortiert sind sowie
                   // für die Struktur in rExtra
   ict2BitsSeq1,   // Namespace W: es wird nur die Differenz zwischen dem vorherigen Wert
                   // und dem aktuellen gespeichert, was die Zahl "kleiner" hält
   ict2BitsSeq2);  // Namespace X: da es sich um Paare von Artikel- und Wortindex handelt
                   // wird die Different des Artikelindex gespeichert, ist dieser Null
                   // wird die Differenz des Wortindex gespeichert, ansonsten die absolute
                   // Zahl

Beispiel für ict2BitsSeq2: Es soll diese Folge codiert werden:

(3,27), (5,3), (5,20), (12,25)

Unkomprimiert, aber mit Differenzenbildung reduziert sich das zu:

(3,27), (2,3), (0,17), (7, 25)

ZenoReader/Qunicode

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.

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.

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!

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.

Difference between revisions of "Zeno file format"