## Memo ## Memo with LLM ### 論文情報 **タイトル:** Peritext: A CRDT for Collaborative Rich Text Editing **著者:** Geoffrey Litt (MIT CSAIL)、Sarah Lim (UC Berkeley)、Martin Kleppmann (University of Cambridge)、Peter van Hardenberg (Ink & Switch) **カンファレンス:** Proceedings of the ACM on Human-Computer Interaction (PACMHCI), Volume 6, Issue CSCW2 **発表年:** 2022年11月 ### 論文概要 本論文は、リッチテキストの協調編集のための新しいCRDT（Conflict-Free Replicated Data Type）アルゴリズム「Peritext」を提案している。従来のプレーンテキスト用CRDTをリッチテキストに拡張する際の問題点を解決し、ユーザーの意図を保持しながら非同期的な協調編集を可能にする。 ### 詳細解説 #### 問題設定 **入力:** リッチテキスト文書に対する複数ユーザーの同時編集操作（文字の挿入・削除、太字・斜体・リンクなどの書式設定） **出力:** 全ユーザーが同一の結果に収束する、意図を保持したマージ済み文書 **必要なデータ:** 文字列データ、書式情報、操作の一意識別子（opId）、各操作の因果関係 #### 提案手法 Peritextは以下の4つの主要コンポーネントから構成される： 1. **基盤プレーンテキストCRDT:** RGA/Causal Treesを使用し、各文字に一意のIDを付与 2. **書式操作の生成:** `addMark`/`removeMark`操作を生成し、文字IDによる安定した位置参照を使用 3. **操作の適用:** アンカー位置に操作セット（op-set）を格納し、決定論的にマージ 4. **最終文書の生成:** last-write-wins方式で衝突を解決し、UIに適した形式で出力 具体的には、書式スパンを文字列と分離して格納し、各スパンの開始・終了位置を文字の一意IDで参照する。例えば、太字操作は以下のように表現される： ``` { action: "addMark", opId: "18@A", start: { type: "before", opId: "5@A" }, end: { type: "before", opId: "17@B" }, markType: "bold" } ``` #### 新規性 - **既存手法の限界克服:** Yjs-richtextの制御文字方式やRitzyの文字単位属性方式が抱える意図保持問題を解決 - **包括的意図保持モデル:** 8つの具体的シナリオを通じて、協調リッチテキスト編集における意図保持の要件を体系化 - **マーク型の分類:** 重複可能性（Can marks overlap?）と拡張性（Do marks expand?）の2軸でマーク型を分類（太字：No/Yes、リンク：No/No、コメント：Yes/No） - **実装とUI統合:** TypeScript実装とProseMirrorエディタとの統合を実現 #### 実験設定 **データセット:** ランダム生成された編集トレースを使用し、最大5,000操作を3つのピア間で交換 **評価指標:** - 収束性：同一操作セットを適用した全レプリカが同一状態に収束 - 因果性保持：操作の因果関係が保持される - 意図保持：提案された8つのシナリオで期待される結果が得られる **検証方法:** プロパティベーステスト、[[ファジングテスト]]、手動テストによる多面的検証 #### 実験結果 - **収束性証明:** Theorem A.1により、同一操作セットを持つ任意の2つの文書バージョンが同一状態になることを数学的に証明 - **ファジングテスト:** 5,000操作の協調編集セッションでも収束性を維持 - **意図保持テスト:** 提案された全8シナリオで期待される動作を実現 - **性能特性:** 操作は影響範囲のみをスキャンし、文書全体の再計算は不要 論文では、ブロック要素（見出し、箇条書き、表など）への拡張は今後の課題として位置づけており、現段階ではインライン書式のみをサポートしている。 ## Abstract Conflict-Free Replicated Data Types（[[CRDT]]）は、共有データの分散協調編集をサポートし、ピアツーピア共有と柔軟な分岐・マージワークフローを可能にします。プレーンテキスト用のCRDTについては広範な研究が存在する一方で、書式付きリッチテキスト用のCRDTについてはほとんど知られていません。アルゴリズムが公開されておらず、既存のオープンソース実装では常にユーザーの意図が保持されるとは限りません。 本論文では、一連の同時編集シナリオを通じて開発された、リッチテキスト編集における意図保持のモデルについて説明します。次に、このモデルの基準を満たすリッチテキスト用CRDTアルゴリズム「Peritext」について述べます。核となるアイデアは、プレーンテキストの文字列と並行して書式スパンを格納し、各スパンの最初と最後の文字の安定した識別子にリンクさせ、これらのスパンから決定論的な方法で最終的な書式付きテキストを導出することで、同時操作の可換性を保証することです。 我々は[[TypeScript]]でアルゴリズムをプロトタイプ実装し、ランダム化プロパティベーステストを使用して検証し、エディタUIと統合しました。また、アルゴリズムが収束を保証することを証明し、因果性保持と意図保持の特性を実証しています。