Alice hat einen String $x \in \{0,1\}^n$ und Bob einen String $y \in \{0,1\}^n$. Sei $k = d_H(x,y)$ ihre Hamming-Distanz. Alice und Bob kennen eine obere Schranke $K$ für die Hamming-Distanz, wissen also, dass $k \leq K$ gilt. Wir nehmen an, dass $K \ll n$ ist und wollen ein Protokoll definieren, in dem Alice eine Nachricht an Bob schickt, die viel kürzer ist als $n$, so dass Bob den String $x$ rekonstruieren kann. Aus dem vorherigen Kapitel kennen wir obere und untere Schranken der Größenordnung $\Theta(K \log n)$. Allerdings war das Prokotoll ineffizient, weil Alice und Bob im Voraus eine Färbung $h : \{0,1\}^n \rightarrow [2K \log n]$ festlegen müssen.

Wir wollen nun ein Protokoll Verfahren von Porat und Lipsky beschreiben, mit dem Alice ihren String Bob mitteilen kann und das für beide Seiten effizient ist; das mit einer Nachricht von Alice an Bob auskommt. Und, als Bonus, das in Streaming-Manier durchgeführt werden kann: Alice und Bob müssen jeweils nur einmal von links nach rechts durch ihre jeweiligen Strings gehen, um die Nachricht zu berechnen (Alice) bzw. um mittels der Nachricht die Positionen, an denen $x$ und $y$ sich unterscheiden, zu berechnen (Bob).

Die Art von Verfahren, die wir beschreiben, nennt sich Sketching (Skizzieren). Alice und Bob berechnen jeweils eine kleine skizze $s(x)$ bzw. $s(y)$; deren Bitgröße ist viel kleiner als die von $x$ und $y$, aber dennoch sollen sie all die Information enthalten, um das Problem lösen zu können.

Einfachster Fall: $k=1$. Dann gilt also entweder $x = y$ oder $y = x \oplus e_i$ für ein $i \in [n]$. Bob will den Wert von $i$ herausfinden (oder feststellen, dass $x=y$ gilt). Alice and Bob berechnen die folgenden Skizzen: \begin{align*} s(x) & = \sum_{i=1}^n i x_i \ \textnormal{ und } \\ s(y) & = \sum_{i=1}^n i y_i \ . \\ \end{align*} So wäre beispielsweise $s(100110) = 1 + 4 + 5$ und $s(101110) = 1 + 3 + 4 + 5$. Alice schickt $s(x)$ zu Bob. Der berechnet nun $s(x) - s(y)$. Es gilt

\begin{align*} s(x) - s(y) = \begin{cases} 0 & \textnormal{ falls $x=0$,}\\ i & \textnormal{ falls $x_i=1$ und $y_i=0$,} \\ -i & \textnormal{ falls $x_i=0$ und $y_i=1$.} \end{cases} \end{align*}

Wieviele Bits muss Alice kommunizieren? Es gilt $0 \leq s(x) \leq 1 + 2 + 3 + \cdots n = {n+1 \choose 2}$. Für $n \geq 2$ ist dies höchstens $n^2 - 1$ und somit benötig $s(x)$ höchstens $\ceil{2 \log n}$ Bits. Alice kann das reduzieren: es gilt $-n \leq s(x) - s(y) \leq n$, es kommen also nur $2n+1$ Werte in Frage. Daher reicht es, den Wert von $s(x)$ modulo $2n+1$ zu kommunizieren, und dafür benötigt Alice $\ceil{\log (2n+1)} \leq 2 + \log n$ Bits.

Allgemeiner Fall: $k \geq 2$.. Wir nehmen für erste an, Alice und Bob verfügten über gemeinsamen Zufall. Sie wählen eine zufällige Funktion $h: [n] \rightarrow [C]$, eine "Färbung" der Positionen mit $C$ Farben. Dies zerlegt den String $x \in \{0,1\}$ in $C$ "farbige" Strings, und wir können das obige Protokoll für jede Farbklasse individuell ausführen. Das geht natürlich in einem Durchgang:

def sketchWithColors(dataStream, C):

$h: [n] \rightarrow [C]$ zufällig # Details dazu unten
Initialisiere $s[c] = 0$ für jedes $c \in [C]$. # $s$ also ein Integer-Array der Länge $n$
for $i = 1, \dots, n$:
1. sei $c := h(i)$ die "Farbe" der Position $i$
2. $s[c] += i \cdot x_i$
return $s$

Wir definien \begin{align*} I := \{i \in [n] \ | \ x_i = y_i\} \ . \end{align*} Es gilt $|I| = k \leq K$. Der Algorithmus sketchWithColors geht gut, falls jede Position $i\in I$ eine andere Farbe bekommt:

Alice und Bob berechnen nun die Skizzen $u := s(x)$ und $v := s(y)$, also $u,v \in \Z^C$. Bob betrachtet nun die Differenzen $u_c - v_c$ für jedes $c$. Falls Position $i \in I$ die einzige in $I$ mit Farbe $c$ ist, so gilt $u[c] - v[c] \in \{-i, i\}$. Im Allgemeinen:

Behauptung Wenn $h(i) \ne h(j)$ für alle verschiedenen $i,j \in I$, dann ist

\begin{align} \Delta(u,v) := \{ |u[c] - v[c]| \ \big| \ c \in [C]\} \setminus \{0\} \label{set-of-differences} \end{align}

genau die Menge $I$. Falls es zwei $i,j \in I$ gleicher Farbe $h(i) = h(j)$ gibt, so ist $|\Delta| \lt k$.

Der Erfolgsfall, nämlich dass alle $i \in I$ verschiedene Farben $h(i)$ bekommen, tritt dann ein, wenn $h$ auf $I$ injektiv ist.

\begin{align*} \Pr[\textnormal{Erfolg}] & = \Pr[h: I \rightarrow [C] \textnormal{ ist injektiv}]\\ & = \frac{\textnormal{Anzahl der injektiven Funktionen}}{\textnormal{Anzahl aller Funktionen}} = \frac{C(C-1)(C-2)\dots(C-k+1)}{C^k} \\ & = 1 \cdot \left(1 - \frac{1}{C}\right) \cdot \left(1 - \frac{2}{C}\right) \cdot \left(1 - \frac{3}{C}\right) \cdots \left(1 - \frac{k-1}{C}\right)\\ & \geq 1 - \frac{1}{C} - \frac{2}{C} - \frac{3}{C} - \dots - \frac{k-1}{C} \\ & = 1 - \frac{{k \choose 2}}{C} \ . \end{align*}

Diese Schranke kann man auch anders herleiten: seien $i, j \in I$ zwei Positionen, in denen sich $x$ und $y$ unterscheiden. Die Wahrscheinlichkeit, dass beide die gleiche Farbe in $[C]$ bekommen, dass also $h(i) = h(j)$ ist, ist $\frac{1}{C}$. Sei $E_{ij}$ dieses Ereignis. Es gilt nun

\begin{align*} \Pr[\textnormal{Erfolg}] & = \Pr[\textnormal{zwei Positionen in $I$ bekommen die gleiche Farbe}]\\ & = \Pr\left[\bigcup_{\{i,j\} \in {I \choose 2}} E_{ij}\right] \\ & \leq \sum_{\{i,j\} \in {I \choose 2}} \Pr[E_{ij}] \\ & = {k \choose 2} \frac{1}{C} \ . \end{align*}

Alice und Bob kennen $k := d_H(x,y)$ nicht, kennen aber eine obere Schranke: $k \leq K$. Wenn sie nun $C = K^2$ wählen, dann gilt

\begin{align*} \Pr[\textnormal{Erfolg}] \geq 1 - \frac{{k \choose 2}}{K^2} \geq 1 - \frac{{K \choose 2}}{2}{K^2} \geq \frac{1}{2} \ . \end{align*}

Die Erfolgswahrscheinlichkeit boosten

Wir hatten die Menge

\begin{align*} \Delta(u,v) := \left\{ |u_c - v_c| \ \big| \ c \in [C] \right\} \setminus \{0\} \end{align*}

definiert. Im Erfolgsfalls gilt $\Delta(s(x),s(y)) = I$. Andernfalls bekommen mehrere Positionen die gleiche Farbe zugewiesen, und das Ergebnis ist zu klein: $|\Delta(s(x), s(y))| \lt k$. Wir können nun die Erfolgswahrscheinlichkeit erhöhen, in dem wir $t$ Skizzen parallel berechnen (mit frischen Zufall jedes mal) und Bob dann das größte $\Delta$ wählt:

def sketchWithColorsAndBoost(dataStream, l, T):

$h^{(1)}, \dots, h^{(T)}: [n] \rightarrow [C]$ zufällig # Details dazu unten
Initialisiere $s[t][c] = 0$ für jedes $c \in [C]$ und jedes $t \in [T]$; $s$ ist also ein zweidimensionales Array $\Z^{T \times l}$
for $i = 1, \dots, n$:
1. for $t = 1, \dots, T$:
  1. sei $c := h^{(t)}(i)$ die Farbe der Position $i$ in der $t$-ten Färbung
  2. $s[t][c] += i \cdot x_i$
return $s$

def recoverDifferences(Sketches $u, v \in \Z^{T \times C}$):

for $t = 1, \dots, T$:
1. $\Delta^{(t)} := \Delta(u[t], v[t])$; # $u[t], v[t]$ sind Sketches in $\Z^{l}$ und somit ist $\Delta(u[t], v[t])$ definiert wie in (\ref{set-of-differences})
2. return das größte unter den $\Delta^{(t)}$

Für jedes $t$ gilt $\Pr[\Delta^{(t)} = I] \geq 1/2$; andernfalls ist $|\Delta^{(t)}| \lt |I|$; die Wahrscheinlichkeit, dass das größte $\Delta^{(t)}$ genau $I$ ist, ist also mindestens $1- 2^{-T}$.

Theorem Sei $C = K^2$ und $u =$ sketchWithColorsAndBoost$(x, C, T)$ und $v =$ sketchWithColorsAndBoost$(v, C, T)$. Dann gilt

\begin{align*} \Pr[\texttt{recoverDifferences}(u,v) = d_H(x,y)] \geq 1 - \frac{1}{2^T} \ . \end{align*}

Die Länge der Sketches $u$ und $v$ ist jeweils höchstens $2 K^2 T \log n$ Bits.

Bessere Schranken

Die quadratische Abhängigkeit von $k$ in der Schranke von ist unbefriedigend. Wir können sie mit einem zweistufigen Färbeprozess verbessern. Wir wählen deutlich weniger Farben: $C = \frac{K}{\log K}$, und wiederum eine zufällige Färbung $h: [n] \rightarrow [C]$. Für $c \in [C]$ sei $X_c$ die Anzahl der Positionen $i \in I$, die Farbe $i$ bekommen, also

\begin{align*} X_c := \left|\left\{ i\in [n] \ | \ x_i \ne y_i \textnormal{ und } h(i)=c \right\} \right| \end{align*}

Es gilt nun $\E[X_c] = \frac{|I|}{C} \leq \frac{K}{C} = \log K$. Wir können also nicht mehr damit rechnen, dass jede Farbklasse nur eine Position enthält. Allerdings ist es unwahrscheinlich, dass eine Farbklasse weitaus mehr als $\log k$ Farben enthält.

Lemma Es gibt eine Konstante $b \in \N$ mit folgender Eigenschaft: die Wahrscheinlichkeit

\begin{align} \Pr[X_c \gt b \cdot \log K] \leq \frac{1}{4K} \ . \label{ineq-one-color} \end{align}

Dies folgt aus der Chernoff-Schranke. Die Wahrscheinlichkeit, dass es mindestens eine Farbe $c$ gibt, für die (\ref{ineq-one-color}) eintritt, ist somit höchstens $\frac{C}{4K} = \frac{1}{4 \log K}$. Und somit ist

\begin{align} \Pr[\textnormal{jede Farbklasse $c$ enthält höchstens $b \log K$ Positionen aus $I$}] \geq 1 - \frac{1}{4 \log K} \ . \label{ineq-all-colors-small} \end{align}

Die weitere Idee ist nun, dass Alice und Bob ihre jeweiligen Strings in Farbklassen zerlegen (zumindest virtuell): $x^{(1)}, \dots, x^{(C)}$ und $y^{(1)}, \dots, y^{(C)}$. Wenn der gute Fall (\ref{ineq-all-colors-small}) eintritt, dann gilt

\begin{align*} d_H(x^{(c)}, y^{(c)}) \leq b \log K =: L \ . \end{align*}

Wir können nun also für jede Farbklasse $c$ die obige Skizze anfertigen; da die obere Schranke für deren Hamming-Distanz nun $L$ ist, reichen dafür $L^2$ Unter-Farben. Wie in sketchWithColorsAndBoost wiederholen wir das $T$ mal, um die Fehlerwahrscheinlichkeit auf $2^{-T}$ zu drücken. Die Wahrscheinlichkeit, dass das Protokoll auf mindestens einer der Farbklassen versagt ist höchstens

\begin{align*} \frac{K}{\log K} \cdot 2^{-T} \ . \end{align*}

Wenn wir also $T = 2 + \log K$ setzen, dann ist diese Wahrscheinlichkeit höchstens $\frac{1}{4 \log K}$. Zusammenfassend: mit Wahrscheinlichkeit höchstens $\frac{1}{4 \log K}$ gibt es eine Farbklasse $c$, auf die "zu viele" Positionen kommen; andernfalls geschieht mit Wahrscheinlichkeit höchstens $\frac{1}{4 \log K}$, dass wir innerhalb einer dieser Farbklassen die Positionen der Unterschiede falsch bestimmen, höchstens $\frac{1}{4 \log K}$. Mit Wahrscheinlichkeit mindestens $1 - \frac{1}{2 \log K}$ geht also alles gut. Hier der gesamte Code:

def sketchWithColorsAndBoostAndSubcolors(dataStream):

Wir setzen
- $C = \frac{K}{\log K}$ # Anzahl der Farben
- $b$ groß genug, wie in verlangt.
- $T = 2 + \log K$ # Anzahl der Wiederholungen für die zuverlässige Berechnung pro Farbklasse
- $L = (b \log K)^2$ # Erhoffte obere Schranke für die Hamming-Distanz pro Farbklasse
$h: [n] \rightarrow [C]$ zufällig
$h^{(1)}, \dots, h^{(T)}: [n] \rightarrow [L^2]$ zufällig Unter-Färbungen
Initialisiere $s[c][t][l] = 0$ für jede Farbe $c \in [C]$, jeden Versuch $t \in [T]$ und jede Unterfarbe $f \in [L^2]$; $s$ ist also ein dreidimensionales Array $\Z^{C \times T \times L^2}$
for $i = 1, \dots, n$:
1. sei $c := h(i)$ die Farbe von $i$
2. for $t = 1, \dots, T$:
  1. sei $f := h^{(t)}(i)$ die "Farbe" der Position $i$ in der $t$-ten Unter-Färbung
  2. $s[t][c][f] += i x_i$
return $s$

Und hier der Code, mit dem Bob die Positionen $I$ rekonstruieren kann:

def recoverDifferencesWithSubcolors(Sketches $u, v \in \Z^{C \times T \times L^2}$):

for $c = 1, \dots, C$:
1. Wir wollen nun $I_c := \{i \in [n] \ \big| \ x_i \ne y_i \wedge h(i)=c\}$ rekonstruieren. Wir hoffen, dass $|I_c| \leq L$ gilt.
2. for $t = 1, \dots, T$:
  - $\Delta^{(t)} := \Delta(u[c][t], v[c][t])$; # $u[c][t], v[c][t]$ sind Sketches in $\Z^{L^2}$ und somit ist $\Delta(u[c][t], v[c][t])$ definiert wie in (\ref{set-of-differences})
3. $\hat{I}_c := $ das größte unter den $\Delta^{(t)}$ # es gilt $\hat{I}_c = I_c$, falls mindestens eine Unterfärbung $h_t$ den Positionen in $I_c$ lauter unterschiedliche Farben zugewiesen hat
return $\bigcup_{c=1}^C \hat{I}_c$

Theorem Der Sketch sketchWithColorsAndBoostAndSubcolors und der Rekonstruktionsalgorithmus recoverDifferencesWithSubcolors berechnet die Menge $I$ korrekt mit Wahrscheinlichkeit mindestens \begin{align*} 1 - \frac{1}{2\log K} \end{align*} Die Länge der Skizze $s(x)$ ist \begin{align*} C \cdot T \cdot L \cdot 2 \log n = O(k \log^2 k \log n) \end{align*} Bits.

Wir sind also der optimalen Schranke $\Theta(k \log n)$ bis auf einen Faktor von $O(\log^2k)$ Bits nahegekommen, mit einem Sketch, der effizient und in Streaming-Manier mit einem Durchgang berechnet werden kann.

Wie wählt man die zufällige Färbung $h$

Literatur

Porat und Lipsky, Improved Sketching of Hamming Distance with Error Correcting, in Combinatorial Pattern Matching, 18th Annual Symposium, CPM 2007, pages 173-182.