Paarkodierung

Paarkodierung bezeichnet eine Methode, aus einem geordneten Paar zweier Elemente ein einzelnes kodiertes Element zu erzeugen, das eindeutig beide Bestandteile repräsentiert. Ziel ist es, zweidimensionale Datenpunkte in eine singuläre Repräsentation zu überführen, die sich speichern, indexieren oder vergleichen lässt, während eine spätere Entkodierung die ursprünglichen Werte wiederherstellt.

Eine häufige Form ist eine bijektive Abbildung von N×N nach N, so dass jedes Paar eindeutig auf eine natürliche Zahl abgebildet wird und umgekehrt. Gängige Verfahren umfassen Cantor-Paarungsfunktion pi(a,b) = (a+b)(a+b+1)/2 + b, sowie Bitinterleaving, bei dem die Binärbits beider Zahlen abwechselnd eingefügt werden, um eine neue Ganzzahl zu bilden (Morton Code).

Anwendung: Paarkodierung wird genutzt, um zweidimensionale Koordinaten, Indexwerte oder Schlüssel in Datenstrukturen zu speichern, in Datenbanken zur Generierung eindeutiger Schlüsseleinträge, in räumlichen Indizes (GIS) und in Algorithmen, die klare, deterministische Schlüssel benötigen. Bei Strings oder anderen Datentypen muß die Eingabe zunächst in ganze Zahlen überführt werden, beispielsweise durch ein geeignetes Mappings oder Hashing, gefolgt von der Kodierung des Paarwerts.

Vorteile und Einschränkungen: Paarkodierung liefert eine eindeutige Repräsentation und ermöglicht einfache Vergleiche oder Sortierungen. Sie kann jedoch zu sehr großen Zahlen führen, insbesondere wenn die ursprünglichen Werte große Bereiche haben, und erfordert eine Entkodierung, um die Originalwerte zurückzubekommen. Je nach Methode ergeben sich unterschiedliche Eigenschaften bezüglich Ausnutzung des Wertebereichs oder der Nähe von Paaren in der kodierten Reihenfolge.

Aus historischen Gründen ist die Idee der Paarabbildung eng mit der Theorie der Kodierungen und Numerischen Mathematik verbunden; Cantor entwickelte eine der frühesten bekannten Paarfunktionen. In der Praxis wählen Anwender je nach Anforderungen an Speicher, Decodierbarkeit und lokaler Nähe der Paare die passende Methode.