Hiện có một trie vào một tập tin - C

Question

Tôi có một trie mà tôi đang sử dụng để thực hiện một số xử lý chuỗi. Tôi có một trình biên dịch đơn giản tạo ra trie từ một số dữ liệu. Khi được tạo, số trie của tôi sẽ không thay đổi khi chạy.

Tôi đang tìm cách tiếp cận nơi tôi có thể duy trì bộ ba trong một tệp và tải nó hiệu quả. Tôi đã xem xét sqllite để hiểu cách chúng bền bỉ b-tree nhưng định dạng tệp của chúng có vẻ hơi nâng cao và tôi có thể không cần tất cả những định dạng này.

Sẽ rất hữu ích nếu ai đó có thể cung cấp một số ý tưởng để tồn tại và đọc trie. Tôi lập trình bằng C.

Answer 1

tôi đã làm một số nghiên cứu và tìm thấy những viên đá quý nhỏ sau trực tuyến:

1. trie.h
2. trie.c

Một Trie làm việc với serialization và deserialization. Ban đầu nó được viết để sử dụng trong Python (có một số triemodule.c tương ứng để buộc nó vào Python), nhưng nó thuần túy là C; bạn có thể khai thác nó cho ý tưởng hoặc sử dụng nó như bạn muốn.

Cập nhật:

Nó xuất hiện các liên kết không còn làm việc. Tôi sẽ giữ bản chính lên, nhưng đây là các liên kết trong máy Wayback:

1. trie.h
2. trie.c

Answer 2

Giả sử toàn bộ cấu trúc dữ liệu của bạn phù hợp trong bộ nhớ, một cách tiếp cận serialization đệ quy là đơn giản nhất . Sqllite làm việc với các cấu trúc dữ liệu không phù hợp với bộ nhớ, vì vậy nó có lẽ là quá mức cần thiết để thử sao chép các phương thức của chúng.

Dưới đây là ví dụ giả để đọc/ghi một nút. Nó hoạt động bằng cách đệ quy đọc/ghi các nút con. Nó không có gì đặc trưng, ​​và cũng nên làm việc cho các cấu trúc dữ liệu cây khác.

void writeNode(Node *node) 
    write node data to file 
    write node.numOfChildren to file 
    for each child: 
     writeNode(child) 

Node *readNode() 
    Node *node = allocateNewNode() 
    read node data from file 
    read node.numOfChildren from file 
    for (i=0; i<node.numOfChildren; i++) 
     Node *child = readNode() 
     node.addChild(child) 

Answer 3

Nếu tất cả các nút của bạn có cùng kích thước sau đó bạn chỉ có thể liệt kê các nút của bạn (root = 0) và viết mỗi trong số họ vào một tập tin tại chỉ mục của họ. Trong khi viết chúng, bạn sẽ phải thay đổi các tham chiếu đến các nút khác thành các chỉ mục của các nút đó. Bạn có thể cũng sẽ cần một giá trị NULL. Bạn có thể sử dụng -1 hoặc bạn có thể sử dụng (root = 1) và (NULL = 0).

Có lẽ bạn cũng có thể nén các nút hơi bằng cách thay đổi các lĩnh vực con trỏ của họ là loại nhỏ hơn.

Nếu nút của bạn là kích cỡ khác nhau thì đó là hơn