Bộ nhớ Cấu trúc dữ liệu hiệu quả để thực hiện Trie

Question

Tôi đang triển khai Trie bằng python. Đến bây giờ tôi đã đi qua hai phương pháp khác nhau để thực hiện nó:

1. sử dụng một Node lớp (tương tự như struct Node trong C++) với các thành viên dữ liệu -

char - để lưu trữ vật

is_end - để lưu trữ cuối từ (đúng hoặc sai)

prefix_count - cửa hàng số từ với tiền tố hiện

con - loại Node dict (để lưu trữ các nút khác ví dụ: 26 bảng chữ cái)

class Node(object): 
    def __init__(self): 
     self.char = '' 
     self.word = '' 
     self.is_end = False 
     self.prefix_count = 0 
     self.child = {} 

2. sử dụng một từ điển để lưu trữ tất cả các dữ liệu.

words = {'foo', 'bar', 'baz', 'barz'}

 {'b': {'a': {'r': {'_end_': '_end_', 'z': {'_end_': '_end_'}}, 
     'z': {'_end_': '_end_'}}}, 
     'f': {'o': {'o': {'_end_': '_end_'}}}} 

Đó là cấu trúc dữ liệu hiệu quả và tiêu chuẩn, mà là cả hai bộ nhớ hiệu quả và nhanh chóng cho traversal và Trie khác hoạt động trên tập dữ liệu lớn các từ?

Answer 1

Tại sao không phải cả hai? Mới hôm qua tôi đã thực hiện một cấu trúc dữ liệu tương tự để lưu trữ và truy xuất một hệ thống phân cấp các đối tượng và dự tính tình huống chính xác này. Kết thúc bằng cách sử dụng một đối tượng Node với một từ điển trẻ em. Nút chính là một đối tượng cho phép bạn có phương pháp tùy chỉnh để in nó hay nhận được các công cụ, và bạn thậm chí có thể có một khởi lười biếng nếu cần thiết (bạn đã đề cập ngay bộ dữ liệu lớn?)

class Node(object): 
    def __init__(self): 
     self.children = collections.defaultdict(lambda:self.__class__()) 
     self.stuff = ... 
    def __str__(self,depth=0): 
     if self.children: 
      return str(self.stuff)+'\n'+'\n'.join([' '*depth+k+' ' + v.__str__(depth+1) for k,v in self.children.items()]) 
     else: 
      return str(self.stuff) 
    def get_path(self,path): 
     node = self 
     while path: 
      node = node.children[path.pop(0)] 
     ... 

Answer 2

Một thay thế trực tiếp sẽ lồng nhau list;

Tuy nhiên [cho là] nhiều Pythonic, gọn hơn trong bộ nhớ và do đó nhanh hơn để tra cứu sẽ là một lồng nhau tuple.

Tất nhiên, việc cập nhật trie đó trở thành logN, vì bạn sẽ phải tạo lại mọi nút tổ tiên. Tuy nhiên, nếu tra cứu của bạn thường xuyên hơn nhiều so với các bản cập nhật, nó có thể đáng giá.

Answer 3

Trie là lỗi khi nói đến sự phức tạp của không gian. Trie có xu hướng sử dụng rất nhiều bộ nhớ để xử lý và vận hành. Nhưng để tránh vấn đề này, có một cơ sở dữ liệu biết cấu trúc dữ liệu ngắn gọn. Hãy thử thực hiện điều đó tại đây.

Tham khảo here để biết thêm thông tin.