Cấu trúc dữ liệu hiệu quả nhất để thêm kiểu vào văn bản

Question

Tôi đang tìm cấu trúc dữ liệu tốt nhất để thêm kiểu vào văn bản (nói trong trình soạn thảo văn bản). Cấu trúc nên cho phép các hoạt động sau đây:

1. tra cứu nhanh của tất cả các phong cách tại tuyệt đối vị trí X
2. chèn nhanh các văn bản tại vị trí bất kỳ (phong cách sau khi vị trí đó phải được di chuyển).
3. Mọi vị trí của văn bản phải hỗ trợ số lượng kiểu tùy ý (chồng chéo).

Tôi đã xem danh sách/mảng có chứa phạm vi văn bản nhưng không cho phép chèn nhanh mà không tính toán lại vị trí của tất cả các kiểu sau điểm chèn.

Cấu trúc cây có bù tương đối hỗ trợ # 2 nhưng cây sẽ thoái hóa nhanh khi tôi thêm nhiều kiểu vào văn bản.

Bất kỳ tùy chọn nào khác?

Answer 1

Tôi chưa bao giờ developped một biên tập viên, nhưng làm thế nào về điều này:

tôi tin rằng nó sẽ có thể mở rộng các chương trình được sử dụng để lưu trữ các ký tự văn bản themeselves, phụ thuộc vào khóa học về các chi tiết thực hiện của bạn (ngôn ngữ, bộ công cụ, vv) và yêu cầu sử dụng tài nguyên và hiệu suất của bạn.

Thay vì sử dụng cấu trúc dữ liệu riêng cho kiểu, tôi muốn có tham chiếu đi kèm với từng ký tự và trỏ đến một mảng hoặc danh sách có các ký tự có thể áp dụng. Các ký tự có cùng một tập hợp các kiểu có thể trỏ đến cùng một mảng hoặc danh sách để có thể chia sẻ.

Chèn và xóa ký tự sẽ không ảnh hưởng đến kiểu chủ đề, ngoài việc thay đổi số lượng tham chiếu đến chúng, có thể được xử lý bằng một chút tính tham chiếu.

Tùy thuộc vào ngôn ngữ lập trình của bạn, bạn thậm chí có thể nén nhiều thứ hơn bằng cách chỉ nửa chừng vào danh sách, mặc dù việc lưu giữ sổ sách bổ sung cho điều này có thể làm cho nó kém hiệu quả hơn.

Vấn đề chính với đề xuất này là mức sử dụng bộ nhớ. Trong một trình soạn thảo ASCII được viết bằng C, việc bó một con trỏ với mỗi char sẽ tăng việc sử dụng bộ nhớ hiệu quả của nó từ 1 byte lên 12 byte trên hệ thống 64 bit, do cấu trúc liên kết đệm.

Tôi sẽ xem xét việc chia nhỏ văn bản thành các khối kích thước nhỏ có thể cho phép bạn nén con trỏ một cách hiệu quả. Ví dụ. một khối gồm 32 ký tự có thể trông giống như thế này trong C:

struct _BLK_ { 
    unsigned char size; 
    unsigned int styles; 
    char content[]; 
} 

Phần thú vị là xử lý siêu dữ liệu trên phần biến của cấu trúc, chứa cả văn bản được lưu trữ và bất kỳ con trỏ kiểu nào. Phần tử kích thước sẽ cho biết số ký tự. Kiểu số nguyên (do đó giới hạn 32 ký tự) sẽ được xem như một bộ 32 trường bit 1 bit, với mỗi ký tự cho biết liệu một ký tự có con trỏ kiểu của riêng nó hay không hoặc sử dụng cùng kiểu với ký tự trước đó. Bằng cách này, một khối 32-char với một phong cách duy nhất sẽ chỉ có các chi phí bổ sung của char kích thước, mặt nạ kiểu và một con trỏ duy nhất, cùng với bất kỳ byte đệm nào. Chèn và xóa các ký tự vào một mảng nhỏ như thế này sẽ khá nhanh.

Đối với bản thân lưu trữ văn bản, một cây có vẻ giống như một ý tưởng hay.Có lẽ một cây nhị phân trong đó mỗi giá trị nút sẽ là tổng của các giá trị con, với các nút lá cuối cùng trỏ đến khối văn bản với kích thước của chúng như là giá trị nút của chúng? Giá trị nút gốc sẽ là tổng kích thước của văn bản, với mỗi cây con lý tưởng giữ một nửa văn bản của bạn. Tuy nhiên, bạn vẫn phải tự động cân bằng, đôi khi phải hợp nhất các khối văn bản trống một nửa.

Và trong trường hợp bạn bị mất nó, tôi không có chuyên môn trong cây :-)

EDIT:

Rõ ràng những gì tôi đề xuất là một phiên bản sửa đổi của cấu trúc dữ liệu này:

http://en.wikipedia.org/wiki/Rope_%28computer_science%29

như được tham chiếu trong bài đăng này:

Data structure for text editor

CHỈNH SỬA 2:

Việc xóa cấu trúc dữ liệu được đề xuất sẽ tương đối nhanh, vì nó sẽ chuyển sang byte dịch chuyển trong mảng và một vài thao tác bit trên mặt nạ kiểu. Chèn là khá nhiều giống nhau, trừ khi một khối đầy lên. Nó có thể có ý nghĩa để dự trữ một số không gian (nghĩa là một số bit trong mặt nạ kiểu) trong mỗi khối để cho phép chèn trực tiếp trong các khối, mà không phải thay đổi chính cây cho một lượng văn bản mới tương đối nhỏ.

Một ưu điểm khác của việc gộp các ký tự và kiểu trong các khối như thế này là vị trí dữ liệu vốn có của nó sẽ cho phép sử dụng bộ đệm CPU hiệu quả hơn các lựa chọn thay thế khác, do đó cải thiện tốc độ xử lý ở một mức độ nào đó. Tuy nhiên, cũng giống như bất kỳ cấu trúc dữ liệu phức tạp nào, bạn có thể cần lược tả với các trường hợp thử nghiệm đại diện hoặc thuật toán thích nghi để xác định các tham số tối ưu cho hoạt động của nó (kích thước khối, bất kỳ khoảng trống được bảo lưu nào vv).