Lässt es sich mit cremefarbenem Papier, einer Tönung, mehr Kontrast oder größerer Schrift besser lesen? Wählen Sie Ihre Farben und Ihre Schrift, einmalig für alle Seiten.

Kostenlose Lektion

Text, der sich zusammenführt: Sequenz-CRDTs

Nach dieser Lektion: Ich kann zwei Replikate eines Textes zusammenführen, dessen Zeichen Positionen tragen.

Lektion, 70 Min.2 BefehleCRDT-Lab: Local-first-Abgleich mit Zählern, Mengen, Vektoruhren und Text in Python

Zwei Personen, ein Satz

Zwei Studierende schreiben einen Gruppenbericht in einem gemeinsamen Dokument. Die eine korrigiert ein Wort am Anfang, der andere ergänzt einen Satz am Ende, beide offline.

Text lässt sich am schwersten zusammenführen. Jedes Zeichen hat einen Platz, und Plätze verschieben sich, sobald jemand tippt.

Am Ende dieser Lektion

Notiz

Ich kann zwei Replikate eines Textes zusammenführen, dessen Zeichen Positionen tragen.

Schlüsselwörter

BegriffWas er bedeutetBeispiel
Sequenz-CRDTein CRDT für eine geordnete Liste, etwa Text
Indexder Platz eines Zeichens, vom Anfang gezählt0, 1, 2
Zeichen-Idein Name, den kein anderes Zeichen hat(6, 'ben')
Tombstoneein gelöschtes Zeichen, das als Markierung bleibt
Verschränkungzwei gleichzeitig getippte Wörter, Buchstabe für Buchstabe vermischt

Die Zellen, die Lernende ausfüllen, bleiben in dieser Vorschau leer.

Ein Index bedeutet Verschiedenes

Am einfachsten sendet man eine Änderung als "füge S an Index 0 ein" oder "lösche Index 2". Ein Index zählt aber vom Anfang eines Textes, der sich auf dem anderen Replikat schon geändert hat.

Fügt Ida am Anfang etwas ein, rückt jedes spätere Zeichen einen Platz weiter. Jans "lösche Index 2" zeigt jetzt auf ein anderes Zeichen.

Probieren Sie es: zwei Änderungen per Index

Code: python
def anwenden(text, aenderung):
    art, index, zeichen = aenderung
    if art == "einfuegen":
        return text[:index] + zeichen + text[index:]
    return text[:index] + text[index + 1:]

start = "Hut"
ida = ("einfuegen", 0, "S")   # Ida tippt S an den Anfang: "SHut"
jan = ("loeschen", 2, "")     # Jan löscht das t an Index 2: "Hu"

# Jedes Replikat wendet zuerst die eigene Änderung an, dann die andere.
bei_ida = anwenden(anwenden(start, ida), jan)
bei_jan = anwenden(anwenden(start, jan), ida)
print("Ida sieht:", bei_ida)
print("Jan sieht:", bei_jan)
# Welches Zeichen wollte Jan löschen? Welches hat Idas Kopie gelöscht?

Idee 1: eine Position zwischen Nachbarn

Jedes Zeichen bekommt eine Positionszahl, und sortiert wird danach. Um zwischen 0.4 und 0.5 zu tippen, nimmt man 0.45. Nichts anderes verschiebt sich.

Echte Systeme nutzen eine Liste ganzer Zahlen wie [4, 5], damit immer Platz für eine weitere bleibt. Der Replikatname entscheidet bei Gleichstand. Das ist die Idee hinter Logoot.

Idee 2: eine Id und ein Elternzeichen

RGA gibt jedem Zeichen eine Id aus Zähler und Replikatname und merkt sich, nach welchem Zeichen es getippt wurde. Gelesen wird der Text vom Anfang aus, neuere Kinder zuerst.

Eine Löschung markiert das Zeichen nur als Tombstone, weil ein anderes Replikat noch dahinter tippen kann. Die Datei rga.py des Labs arbeitet so.

Zwei Änderungen an einer Zeile zusammenführen

Befehl
docker exec jupyter python3 steps/text.py

Hier angezeigt, nicht ausgeführt. Mit „Lab starten“ geben Sie ihn im Terminal Ihres eigenen Labs ein.

Beispiel: was das Lab gedruckt hat

ZeitpunktAnaBen
GemeinsamHelloHello
OfflineHello worldOh, ello (H gelöscht)
Nach dem AbgleichOh, ello worldOh, ello world
Gespeichertein Tombstone, das Hein Tombstone, das H

Die Zellen, die Lernende ausfüllen, bleiben in dieser Vorschau leer.

Wenn zwei Wörter sich vermischen

Ana tippt "cat" und Ben "dog", an derselben Stelle und zur selben Zeit. Bei Positionen zwischen Nachbarn wählen beide dieselben Zahlen, und der Replikatname sortiert jedes Paar.

Die Buchstaben wechseln sich ab. RGA hängt jeden Buchstaben an den vorigen, also bleibt jedes Wort ganz.

Zwei Wörter beim Verschränken beobachten

Befehl
docker exec jupyter python3 steps/interleave.py

Hier angezeigt, nicht ausgeführt. Mit „Lab starten“ geben Sie ihn im Terminal Ihres eigenen Labs ein.

Ein häufiger Fehler

Warnung

Viele glauben, ein Zusammenführen sei richtig, wenn alle Replikate denselben Text haben. "cdaotg" steht auf jedem Replikat gleich da, und niemand hat es getippt. Übereinstimmung ist Pflicht, aber ein gutes Text-CRDT hält auch zusammen, was jede Person getippt hat.

Über dieses Lab und seinen Quellcode: CRDT-Lab: Local-first-Abgleich mit Zählern, Mengen, Vektoruhren und Text in Python

Sie unterrichten eine Gruppe? Weisen Sie dieses Modul Ihren Studierenden zu, mit Handbuch für Lehrende, automatisch geprüften Aufgaben und einem Lab für jede Person.