Lückenkodierung

Lückenkodierung, oft auch als Gap-Encoding bezeichnet, ist eine Codierungstechnik zur Darstellung von Sequenzen, in denen zwischen relevanten Symbolen häufig Lücken auftreten. Die Grundidee besteht darin, nicht jedes Symbol der ursprünglichen Sequenz zu speichern, sondern die Abstände (Lückenlängen) zwischen aufeinanderfolgenden gespeicherten Symbolen zu kodieren. Dadurch ergibt sich eine kompaktere Darstellung, wenn die Sequenz viele Lücken enthält.

Funktionsweise: Bei der Lückenkodierung werden typischerweise zwei Informationen gespeichert: die tatsächlich vorhandenen Symbole und die Längen der Lücken zwischen diesen Symbolen. Man kann zwei gängige Varianten verwenden:

- positionsbasierte Kodierung: Es werden die Werte der nicht-leeren Positionen zusammen mit den Abständen zu den vorhergehenden nicht-leeren Positionen gespeichert.

- rein gap-basierte Kodierung: Es werden nur die Lückenlängen zwischen den Symbolen angegeben, zusammen mit den jeweiligen Symbolwerten.

Beispiel: Eine Sequenz der Länge 100 enthält an den Positionen 5, 20 und 75 die Buchstaben A, T bzw. G; alle anderen Positionen sind Lücken. Die Werte gespeichert werden A, T, G und die Lückenlängen 4, 14, 54 (d. h. vor dem ersten Symbol liegen 4 Lücken, zwischen dem ersten und zweiten Symbol 14 Lücken, zwischen dem zweiten und dritten Symbol 54 Lücken).

Anwendungen: Lückenkodierung findet Anwendung in der Genomik (Sequenzabgleich, Alignmentspeicherung), bei Differenzkodierungen in Versionierungssystemen sowie in der Speicherung sparsamer Zeitreihen oder Diff-Daten.

Vorteile und Nachteile: Sie spart Speicherplatz bei vielen Lücken und ermöglicht teilweise schnellen Zugriff auf die nicht-leeren Elemente. Bei wenigen Lücken oder stark unregelmäßigen Lücken kann der Overhead der Lückenangaben die Vorteile mindern.