Filter: 2013

Um eine schnelle Suche über viele große Datensätze zu haben, ohne jeden Datensatz anfassen zu müssen, eignet sich ein Trigrammfilter. Er ähnelt dem Musterfilter, schliesst aber potentielle Datensätze direkt aus und liefert schneller kleinere Ergebnislisten.

Beispiel (Quellcode): trigramfilter.cpp
Download (Quellcode): trigramfilter.zip

Aufbereitung

In der Basis besteht dieser Filter aus mehreren Listen oder Feldern, die Trigrammen (immer drei Zeichen) zugeordnet sind. Am Anfang werden die Datensätze eingelesen, in alle möglichen Drei-Zeichen-Kombinationen zerlegt und die Datensatznummer in die entsprechende Liste der Kombination abgelegt. Die Datensatznummern sollten z.B. aufsteigend sein oder einem anderen Schema folgen, da dies später beim evtl. nötigen Vergleich einen Geschwindigkeitszuwachs gibt. Ein Dokument muss nicht mehrmals in einer Liste auftauchen, weil nur ermittelt werden muss, ob eine Kombination im Dokument existiert und nicht wo. Dies wäre optional.

Suche

Die Suche folgt dem Schema der…

Die Speicherung von Ganzzahlen kann, je nach Datentypgröße viel Platz auf dem Datenträger oder im Speicher in Anspruch nehmen. Werden aber hauptsächlich kleine Werte erwartet, zum Beispiel bei Deltaeinträgen, ist der Großteil des Wertes nicht belegt. Hier springt diese Art der Kodierung ein und versucht die Werte soweit es geht zu kürzen.

Beispiel (Quellcode): vlq.cpp
Download (Quellcode): vlq.zip

Beschreibung

Die Ganzzahl wird in Teile (meist) gleicher Größe aufgeteilt. Alle oberen Teile die keine Bits gesetzt haben werden nicht in die Ausgabe geschrieben. Alle Teile, bis auf den Letzten, bekommen einen Marker, dass der nachfolgende Teil nicht das Ende darstellt. Häufig werden die Zahlen in 7-Bit Teile gebrochen und mit übrigen Bit des Ausgabebytes markiert.

Es gibt hier allerdings viele Varianten, die häufigsten Unterscheidungen sind:

• Richtung
  • höherwertiger Teil zuerst
  • niederwertiger Teil zuerst
• Position des Markers im Ausgabebyte
• Vorzeichenbehandlu…

Die Huffman-Kodierung stellt neben der arithmetischen Kodierung bzw. der Bereichskodierung eine der häufigsten Formen der Entropiekodierung dar. Es wird und wurde vor allem, wegen der hohen Geschwindigkeit in älteren Kompressionsverfahren eingesetzt, von ZIP/Deflate über RAR bis hin zu JPEG. Allerdings gibt es auch einen kleinen Nachteil: Die Kodierung erreicht nicht immer die theoretische Entropie, da sie nur auf Bitbasis arbeitet.

Beispiel (Quellcode): huffman.cpp
Download (Quellcode): huffman.zip

Beschreibung

Diese Art der Kodierung, errechnet mit Hilfe der Symbolauftrittswahrscheinlichkeiten (oder auch Häufigkeiten), einen möglichst kurzen und eindeutigen Code. Kommt ein Symbol häufiger vor, wird es durch einen kürzeren binären Code ausgedrückt. Werden nicht alle Symbole des Alphabets benötigt, fließen diese nicht weiter in die Bearbeitung ein. Grundsätzlich kann unterschieden werden zwischen statischer, dynamischer und adaptiver Huffman-Kodierung. Die statische hat festgelegte Symbolhäufigkeiten, die…

Radixsort ist eine Sortierungsmethode, die Schrittweise anhand von Schlüsselwertteilen, über einen oder mehrere Sortieralgorithmen, das Eingangsfeld ordnet. Jeder Sortierungsschritt muss stabil sein, d.h. die Elementereihenfolge muss im sortierten Fall gleich bleiben. Am häufigsten wird hier Countingsort verwendet. Die Laufzeit hängt von der Anzahl der Sortierungsschritte und den gewählten Algorithmen ab.

Beispiel (Quellcode): radixsort.cpp
Download (Quellcode): radixsort.zip

Transformation

• Ganzzahlen

  Durch die Aufteilung des Schlüsselwertes, hat der darunterliegende Sortieralgorithmus keine Information, ob es sich um positive oder negative Zahlen handelt. Dies kann leicht durch hinzufügen eines Basiswertes geändert werden. Der Basiswert kann auch der kleinste Schlüsselwert sein und kann dann von allen Schlüsselwerten abgezogen werden.

• Fließkommazahlen

  Da Fließkommazahlen einen Exponenten und ein Vorzeichenbit haben, muss hier mit Vorsicht gearbeitet werden. Die Zahl selbst kann als entsprechend große…

Countingsort (Sortierung durch Zählung) ist eine Sortierungsmethode, die ohne Vergleiche funktioniert. Sie kann je nach zu sortierendem Typen und sehr viel schneller sein als Mergesort sein. Es ist aber in der normalem Implementation nötig ein Eingangs-, ein Ausgangsfeld sowie ein Hilfsfeld zu erstellen. Der Algorithmus ist besonders effektiv bei kleinen Wertebereichen der Eingangswerte, im Verhältnis zur Eingangsfeldgröße. Er funktioniert normalerweise nur mit Ganzzahlwerten, kann aber auch für andere Typen mit einer entsprechenden Transformation der Daten benutzt werden. Dieses wird näher beim Radixsort erläutert.

Beispiel (Quellcode): countingsort.cpp
Download (Quellcode): countingsort.zip

Häufigkeitsaufnahme

Zu Beginn wird ein Zählfeld erstellt, welches die Größe des erwarteten Wertebereiches besitzt. Die Zähler werden mit Null initialisiert. Nun wird der entsprechende Zähler, mit dem Index des Eingangswertes, im Zählfeld erhöht. Kurz gesagt, die Häufigkeitsverteilung wird aufgenommen.

Da dieses Zähl…