Cấu trúc dữ liệu cho trình soạn thảo văn bản

Question

Đây là câu hỏi phỏng vấn. Bạn sẽ sử dụng cấu trúc dữ liệu nào để lưu trữ văn bản trong trình soạn thảo văn bản?

Answer 1

Trên bộ xử lý văn bản ZX-Spectrum cũ (hoặc hơn nữa, tôi không biết) đã sử dụng cấu trúc rất đơn giản.

Có một bộ đệm lớn, chiếm toàn bộ RAM miễn phí. Văn bản được chia thành hai phần tại con trỏ. Phần trước con trỏ, được đặt ở đầu bộ đệm và phần còn lại ở cuối bộ đệm. Khi nhập văn bản, dữ liệu chỉ được thêm vào phần cuối của phần đầu tiên và khi di chuyển con trỏ, văn bản được sao chép ra và quay lại. bố trí

Buffer:

Hello, World! 
     ^------Cursor here 

+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 
|H|e|l|l|o|,| |W| <free> |o|r|l|d|!| 
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 
|    ^  ^  | 
begin   cur1  cur2 end 

Đó là, làm thế nào một số chỉnh sửa hoạt động đã được thực hiện:

Type a char: buffer[cur1++] = character 

Backspace:  cur1-- 

Cursor left: buffer[--cur2] = buffer[--cur1] 

Cursor right: buffer[cur1++] = buffer[cur2++] 

Buffer trong hành động:

   Hello, W..............orld! 
Press right  ^   ^
      Hello, Wo..............rld! 
Press backspace  ^   ^
      Hello, W...............rld! 
Press 0   ^   ^
      Hello, W0..............rld! 
        ^   ^

Answer 2

Bạn có thể tìm thấy điều này thú vị, thậm chí nếu nó không chính xác trả lời câu hỏi của bạn:

Most efficient data structure to add styles to text

Tôi hy vọng rằng các cuộc thảo luận sẽ đi đến những nơi hấp dẫn :-)

Answer 3

Rope

Một sợi dây cơ bản là cây nhị phân có lá là mảng ký tự. Một nút trong cây có một con trái và một con phải - con trái là phần đầu tiên của chuỗi, trong khi con phải là phần cuối cùng của chuỗi. Nối hai dây chỉ đơn giản là liên quan đến việc tạo ra một nút cây mới với cả hai dây thừng như trẻ em. Để đảm bảo lập chỉ mục thời gian logarit và các hoạt động chuỗi con, dây dẫn có thể cần được cân bằng. Có thể có nhiều chiến lược cân bằng khác nhau.

Ưu điểm chính của dây so với lưu trữ chuỗi là mảng ký tự là chúng cho phép nối nhanh hơn nhiều so với chuỗi thông thường và không yêu cầu dung lượng bộ nhớ tiếp giáp lớn để lưu trữ chuỗi lớn. Những bất lợi chính là sử dụng không gian tổng thể lớn hơn và lập chỉ mục chậm hơn, cả hai đều trở nên nghiêm trọng hơn khi cấu trúc cây trở nên lớn hơn và sâu hơn. Tuy nhiên, nhiều ứng dụng thực tế của việc lập chỉ mục chỉ liên quan đến phép lặp qua chuỗi, mà vẫn còn nhanh miễn là các nút lá đủ lớn để hưởng lợi từ các hiệu ứng bộ nhớ cache.

Answer 4

Tôi biết đó là quá muộn cho một câu trả lời, nhưng tôi tìm thấy The Craft of Text Editing cuốn sách thực sự hữu ích. Nó chứa mô tả của một số mô hình bộ đệm với ưu và nhược điểm của chúng. Thật không may, nó không đề cập đến cấu trúc dữ liệu Ropes.

Answer 5

Khi @Vovanium đã đề cập đến lý thuyết cơ bản về cách bộ đệm khoảng cách có thể được sử dụng, tôi đã triển khai phiên bản C/C++.

Code:

#include <stdio.h> 
#define SZ 1000 

char leftArray[SZ], rightArray[SZ]; 
int leftCount, rightCount; 
int cursorPos; 

/* 
* Private APIs 
*/ 

void printArray(){ 

    for(register int i = 0; i < leftCount; i++){ 
     printf("%c", leftArray[i]); 
    } 

    for(register int i = rightCount - 1; i >= 0; i--){ 
     printf("%c", rightArray[i]); 
    } 
    printf("\n"); 
} 

void adjust(int pos){ 

    while(leftCount > pos){ 
     rightArray[rightCount++] = leftArray[--leftCount]; 
    } 

    while(leftCount < pos){ 
     leftArray[leftCount++] = rightArray[--rightCount]; 
    } 
} 


/* 
* Public APIs for Text Editor 
*/ 

void init(){ 

    cursorPos = leftCount = rightCount = 0; 
} 

void addWord(char word[], int len){ 

    adjust(cursorPos); 

    for(register int i = 0; i < len; i++){ 
     leftArray[leftCount++] = word[i]; 
    } 
    leftArray[leftCount] = 0; 
} 

void addBackSpace(){ 

    adjust(cursorPos); 
    leftCount--; 
} 

void moveCurson(int newPosition){ 

    cursorPos = newPosition; 
} 

void subString(int pos, int length, char result[]){ 

     adjust(cursorPos); 

    int k = 0; 
     int l = 0; 
    while(k + pos < leftCount && k < length){ 
     result[k] = leftArray[pos + k]; 
     k++; 
    } 

    length -= k; 
    while(l < length){ 
     result[k++] = rightArray[rightCount - 1 - l]; 
     l++; 
    } 
}