引言

最近筆者正在優(yōu)化 Android 開源代碼編輯器項目 TextWarrior 的一些算法，包括時間、空間兩方面。TextWarroir 的文本編輯器算法采用經(jīng)典的 GapBuffer，其基本思想是利用編輯時的局部性原理，在光標處維護一個緩沖區(qū)，實現(xiàn)高效替換。

但是筆者需要對其代碼高亮、自動斷行等功能用到的標記數(shù)組進行優(yōu)化：

• 原編輯器的代碼高亮標記數(shù)組直接采用差分數(shù)組存儲其文本下標，好處是文章內容頻繁更新時差分數(shù)組可以只需要改動其中一兩個元素的值便能導致后面整體的改動，缺點是查找某個下標時需要從頭開始，時間復雜度為 \(O(N)\)。
• 原編輯器的自動斷行標記數(shù)組直接存儲文本下標，好處是定位時可以采用二分查找，但是當文本改動時需要對整個數(shù)組光標處的后半段進行修改，時間復雜度 \(O(N)\)。

不管是差分數(shù)組還是直接存下標，貌似都有其缺陷。那有沒有一種兩全其美的方法呢？答案是有的。這要從 GapBuffer 說起。

GapBuffer 基本思想

GapBuffer 又叫間隙緩沖區(qū)，是一種文本編輯器算法，主要對編輯器中頻繁的字符串插入、刪除操作進行優(yōu)化。

我們知道，對于中間插入，數(shù)組的時間復雜度為 \(O(N)\)，而鏈表的時間復雜度為 \(O(1)\)。字符串常常用數(shù)組的方式存儲，若采用鏈表，每個字符都會附帶一個指針指向下一個字符結點，數(shù)據(jù)冗余度很高。而 GapBuffer 則實現(xiàn)了對于數(shù)組高效的中間插入刪除。

GapBuffer 利用編輯時的局部性——編輯操作在一段時間內往往集中在最初光標附近，換位置的情況比較少這一事實——進行優(yōu)化。GapBuffer 在原字符串數(shù)組光標附近維護一個緩沖區(qū)（即所謂間隙緩沖區(qū)，后文簡稱間隙），并通過雙指針限定該間隙的范圍。

由于間隙內的內容實際不可見，當我通過字符串索引獲取字符時，需要跳過間隙，此時存在一個下標映射：將獲取字符時的邏輯下標映射到所維護字符數(shù)組的實際下標。

基本操作

• 局部性編輯：當光標位于間隙開始位置時，輸入時直接將輸入內容從間隙開始位置拷貝到間隙，并后移起始指針；刪除時，直接前移起始指針。此時時間復雜度為 \(O(1)\)。

• 跨域編輯：若出現(xiàn)跨域編輯，即此時光標位置不在間隙開始處，則需要進行整體復制，以將間隙移動到當前光標處，再進行相關操作。時間復雜度 \(O(m)\)，其中 \(m\) 表示間隙區(qū)移動的距離。

• 若插入時間隙所剩空間不足，則需要進行擴容，并把間隙后的字符全部向后整體復制。時間復雜度 \(O(k)\)，其中 \(k\) 為間隙之后的部分數(shù)組長度。

插入操作示例：

插入前
|H|e|l|l|o| | | | |W|o|r|l|d|
           ^ Gap (size=4)
插入后
|H|e|l|l|o|!| | | |W|o|r|l|d|
             ^ Gap (size=3)

刪除操作示例：

刪除前
|H|e|l|l|o|!| | | |W|o|r|l|d|
             ^ Gap (size=3)
插入后
|H|e|l|l|o|!| | | |W|o|r|l|d|
           ^ Gap (size=4)

基于下標映射的標記記錄法

既然 GapBuffer 采用下標映射實現(xiàn)實際下標和邏輯下標的轉換，而在編輯的過程中，某個字符的邏輯下標往往是不斷變動的，而其實際下標則要穩(wěn)定得多，因此完全可以記錄實際下標實現(xiàn)高效率的標記管理。

記錄實際下標，即記錄標記在原字符數(shù)組中的下標，當間隙發(fā)生變動時維護下標的映射關系。可以對比邏輯下標和差分下標，實際下標+映射方式兼具二者有點同時避免了各自的缺陷。

下標映射

在需要訪問下標時，會用到 GapBuffer 的下標映射函數(shù)將記錄的實際下標轉為邏輯下標再返回，而增加記錄時會把邏輯下標轉為實際下標進行記錄。

private ArrayList<Integer> records;

private int mapToReal(int i) {
    return i < gapStart ? i : i + gapLength();
}

private int mapToLogical(int i) {
    return i < gapEnd ? i : i - gapLength();
}

public void getMark(int i) {
    return mapToLogical(records.get(i));
}

public void addMark(int i) {
    records.add(mapToReal(i));
}

搜索

在需要進行查找時，只需要將邏輯下標轉為實際下標并應用二分查找即可，時間復雜度 \(O(\log N)\)，繼承了記錄邏輯下標的優(yōu)點，而記錄差分下標則必須從頭遍歷累加。

public int findMark(int i) {
     return Collections.binarySearch(records, mapToReal(i));
}

維護

由于記錄為實際下標，因此維護需保證與 GapBuffer 的一致性。對于間隙維護的三種情況均需考慮，其時間復雜度也和三種情況基本對等：

• 局部性編輯：在間隙開頭插入時，如果間隙不需要擴容，則記錄不變，如果是刪除，檢查并處理實際下標落入間隙區(qū)中的下標，移動或刪除，平均時間復雜度 \(O(1)\)。由于間隙發(fā)生了改變，雖然實際下標沒有改變，但映射函數(shù)的參數(shù)發(fā)生變化，因此映射到的邏輯下標會變化。

• 跨域編輯：在間隙以外的地方插入或刪除，此時只需檢查移動區(qū)間內的下標并加或減去間隙長度，再同上處理插入刪除情況，時間復雜度 \(O(m)\)，此處 \(m\) 為移動區(qū)間內標記數(shù)量。

• 間隙擴容：當間隙大小不足插入時需要進行擴容，此時需要將間隙之后的所有標記加上擴容量，時間復雜度 \(O(k)\)，此處 \(k\) 為間隙之后的標記數(shù)量。

實際下標記錄的維護在滿足局部性的情況下時間復雜度為 \(O(1)\)，與差分下標記錄同級，同時避免了邏輯輯下標記錄的不足。當然，實際下標記錄的維護難度要比二者大一些。

對比

總結

本文討論文本編輯器經(jīng)典算法 GapBuffer 的標記記錄優(yōu)化方案，利用算法中的局部性思想提出配套的基于映射的下標記錄算法，并對比了 TextWarrior 用到的兩種記錄方案，表現(xiàn)出該方法在時間復雜度上的優(yōu)勢。另外，局部性原理也是很多算法的依據(jù)，在計算機軟硬件設計很多地方都有所體現(xiàn)，值得研究。希望本文為讀者提供一些參考幫助。

原文鏈接：http://www.rzrgm.cn/RainbowC0/p/18805061 ，未經(jīng)作者許可禁止轉載。