Anhang C. Beispiel für einen Einzeldurchlauf-Kodierungsalgorithmus

Pseudocode für die Einzeldurchlauf-Kodierung, ohne Behandlung von Duplikaten, nicht-blockierendem Modus, verfügbarer Encoder-Stream-Flusskontrolle und Referenzverfolgung.

Hilfsfunktionen

# Eine Ganzzahl mit dem angegebenen Präfix und der Länge kodieren
encodeInteger(buffer, prefix, value, prefixLength)

# Eine dynamische Tabelleneinfügungsanweisung mit optionalem statischen oder dynamischen Namensindex kodieren (aber nicht beides)
encodeInsert(buffer, staticNameIndex, dynamicNameIndex, fieldLine)

# Eine statische Indexreferenz kodieren
encodeStaticIndexReference(buffer, staticIndex)

# Eine dynamische Indexreferenz relativ zu Base kodieren
encodeDynamicIndexReference(buffer, dynamicIndex, base)

# Ein Literal mit optionalem statischen Namensindex kodieren
encodeLiteral(buffer, staticNameIndex, fieldLine)

# Ein Literal mit dynamischem Namensindex relativ zu Base kodieren
encodeDynamicLiteral(buffer, dynamicNameIndex, base, fieldLine)

Kodierungsalgorithmus

base = dynamicTable.getInsertCount()
requiredInsertCount = 0

for line in fieldLines:
    staticIndex = staticTable.findIndex(line)
    if staticIndex is not None:
        encodeStaticIndexReference(streamBuffer, staticIndex)
        continue

    dynamicIndex = dynamicTable.findIndex(line)
    if dynamicIndex is None:
        # Kein passender Eintrag. Entweder einfügen+indexieren oder Literal kodieren
        staticNameIndex = staticTable.findName(line.name)
        if staticNameIndex is None:
            dynamicNameIndex = dynamicTable.findName(line.name)

        if shouldIndex(line) and dynamicTable.canIndex(line):
            encodeInsert(encoderBuffer, staticNameIndex,
                        dynamicNameIndex, line)
            dynamicIndex = dynamicTable.add(line)

    if dynamicIndex is None:
        # Kann nicht indexiert werden, Literal verwenden
        if dynamicNameIndex is not None:
            # Literal mit dynamischem Namen kodieren, möglicherweise über Base
            encodeDynamicLiteral(streamBuffer, dynamicNameIndex,
                                base, line)
            requiredInsertCount = max(requiredInsertCount,
                                    dynamicNameIndex)
        else:
            # Literal mit statischem Namen oder Literal-Namen kodieren
            encodeLiteral(streamBuffer, staticNameIndex, line)
    else:
        # Dynamische Indexreferenz
        assert(dynamicIndex is not None)
        requiredInsertCount = max(requiredInsertCount, dynamicIndex)
        # dynamicIndex kodieren, möglicherweise über Base
        encodeDynamicIndexReference(streamBuffer, dynamicIndex, base)

# Präfix kodieren
if requiredInsertCount == 0:
    encodeInteger(prefixBuffer, 0x00, 0, 8)
    encodeInteger(prefixBuffer, 0x00, 0, 7)
else:
    wireRIC = (
        requiredInsertCount
        % (2 * getMaxEntries(maxTableCapacity))
    ) + 1
    encodeInteger(prefixBuffer, 0x00, wireRIC, 8)
    if base >= requiredInsertCount:
        encodeInteger(prefixBuffer, 0x00,
                    base - requiredInsertCount, 7)
    else:
        encodeInteger(prefixBuffer, 0x80,
                    requiredInsertCount - base - 1, 7)

return encoderBuffer, prefixBuffer + streamBuffer

Algorithmuserklärung

Dieser Algorithmus demonstriert die Kernlogik eines Einzeldurchlauf-Encoders:

1. Initialisierung: Base auf die aktuelle Einfügungsanzahl setzen, requiredInsertCount auf 0 initialisieren.

2. Feldzeilen iterieren: Für jede Feldzeile:

   • Zuerst versuchen, eine vollständige Übereinstimmung in der statischen Tabelle zu finden
   • Wenn nicht gefunden, in der dynamischen Tabelle suchen
   • Wenn keines gefunden wird, entscheiden, ob ein neuer Eintrag eingefügt oder ein Literal verwendet werden soll

3. Entscheidungslogik:

   • Vollständige Übereinstimmung: Direkte Referenz (statisch oder dynamisch)
   • Keine Übereinstimmung: Entscheiden, ob basierend auf der Richtlinie in die dynamische Tabelle eingefügt werden soll
   • Nur Namensübereinstimmung: Literal mit Namensreferenz verwenden

4. Präfixkodierung: Das Feldabschnittspräfix basierend auf den Werten von requiredInsertCount und Base kodieren.

5. Ausgabe: Encoder-Stream-Puffer und kodierten Feldabschnitt (Präfix + Feldzeilen-Darstellungen) zurückgeben.

Wichtige Punkte

• Einzeldurchlauf-Verarbeitung: Der Algorithmus trifft Kodierungs- und Einfügungsentscheidungen während der Iteration durch Feldzeilen
• Base-Verfolgung: Verwendet die Einfügungsanzahl als Base, ermöglicht Post-Base-Indexierung
• Flexible Strategie: Die Funktion shouldIndex() kapselt die Indexierungsstrategie, anpassbar je nach Implementierungsanforderungen
• Referenzzählung: requiredInsertCount verfolgt den erforderlichen maximalen dynamischen Tabellenzustand

---