Từ điển được lưu trữ hiệu quả. Cấu trúc dữ liệu này có tồn tại không và nó được gọi là gì?

Question

Tôi muốn có cấu trúc dữ liệu lưu trữ nhiều mẩu dữ liệu entropy thấp thường tương tự nhau. Tôi muốn lưu trữ chúng một cách hiệu quả (nén bằng cách nào đó) và lấy ra bằng chỉ mục hoặc khớp. Khôi phục nhanh là quan trọng hơn nén, nhưng nó không phải là một tùy chọn để lưu trữ chúng không nén.

Ví dụ tốt nhất mà tôi có thể nghĩ đến là lưu trữ hàng tỷ câu được viết từ khối văn bản (dưới dạng nén trên đĩa).

dict: 
1: 'The quick brown fox jumps over the lazy dog.' 
2: 'The quick green frog jumps over the lazy fox.' 
3: 'The quick brown fox jumps over the lazy frog.' 

Nếu hai câu giống nhau thì phải có cùng một chỉ mục.

Tôi muốn truy xuất chúng theo kết hợp chỉ mục hoặc ký tự đại diện (regex cũng tốt, nhưng không cần thiết). tức là:

dict.get(1) => 'The quick brown fox jumps over the lazy dog.' 
dict.match('The quick brown *') => [1, 3] 

Tôi có thể nén từng câu, nhưng bỏ qua thực tế là nhiều mục nhập tương tự nhau.

Tôi có thể sắp xếp và lưu trữ các điểm khác biệt. nhưng rất khó để thêm và xóa các phần tử.

Nó phải hỗ trợ unicode.

Tôi chắc chắn có một số cấu trúc cây ở đó thực hiện việc này.

Điểm thưởng nếu nó có trình bao bọc python.

Điều này https://hkn.eecs.berkeley.edu/~dyoo/python/suffix_trees/ trông rất gần nhưng chưa thấy hành động từ năm 2002/py2.2 và tôi không thể chạy nó. Nếu có các lựa chọn thay thế mới hơn/tốt hơn để kiểm tra, tôi rất muốn nghe về chúng.

Tôi bao gồm thẻ tin sinh học vì tôi hiểu rằng hậu tố_trees và cấu trúc dữ liệu tương tự được sử dụng ở đó.

Answer 1

Sự cố của bạn có vẻ giống hệt trường hợp sử dụng cho trie, là cấu trúc dữ liệu dựa trên cây để lưu trữ chuỗi theo tiền tố. Tôi chưa tự mình sử dụng những triển khai này, nhưng tìm kiếm nhanh trên mã Google cho thấy các dự án mã nguồn mở here và here và here. Hai cái đầu tiên là trong Java và phần thứ ba là trong C++. Tôi mong chờ viết một wrapper xung quanh C++ cho Python sẽ dễ dàng hơn so với việc viết một wrapper xung quanh Java, vì Python đã được xây dựng trong khả năng cho khả năng tương tác với C.

EDIT

Tôi đã kiểm tra GitHub, và có thành công hơn một chút với triển khai Python. Tôi đã tìm thấy việc triển khai Python trie here và here và here.

Tuy nhiên, nếu bạn đang thực sự làm việc với hàng tỷ câu, ngay cả việc thực thi Python thuần túy được viết rất tốt (vì cả ba câu này đều có thể) hết bộ nhớ.

Answer 2

Như bạn đã chỉ ra, một cây hậu tố hoặc cây gốc có lẽ là con đường để đi. Tôi muốn đề xuất:

1. Tạo một số radix tree, lưu id trong lá.Kiểm tra các liên kết trong this answer để bắt đầu, nhưng tôi tin rằng bạn sẽ phải tinh chỉnh bất cứ điều gì bạn tìm thấy để phù hợp với nhu cầu của bạn;

2. Tạo id ánh xạ dict cho đường dẫn trong cây. Điều này sẽ cho phép bạn nhanh chóng lấy câu bằng id (tìm đường dẫn, theo dõi nó để gắn kết câu). Lưu ý rằng điều này sẽ làm cho chèn và xóa một chút tốn kém: mỗi khi một nút không phải lá được thay đổi, mỗi hậu duệ sẽ cần phải có đường dẫn của họ được cập nhật trong dict;

   2.1. Một thay thế (trong trường hợp các đường dẫn kết thúc quá dài) là có mỗi nút lưu trữ một tham chiếu đến cha mẹ của nó, vì vậy dict chỉ cần tham chiếu đến nút lá. Tôi tin rằng hầu hết các triển khai hiện có không làm điều đó, vì mục tiêu chính của cố gắng là để tăng tốc độ tra cứu, không phải để nén văn bản chính nó.

3. Tìm kiếm theo ký tự đại diện hơi phức tạp, tùy thuộc vào độ phức tạp của nhu cầu của bạn. Ví dụ được cung cấp rất đơn giản: theo các nút cho tiền tố, cho đến khi tìm thấy ký tự đại diện, sau đó trả về tất cả các con cháu. Trong trường hợp này, một trie tổng hợp có thể dễ dàng xử lý hơn cây radix chuyên biệt hơn, nhưng các yêu cầu trong không gian cao hơn một chút.

Bằng cách này, bạn cũng có thể tối ưu hóa Trie radix của bạn để mất ít không gian, bằng cách sử dụng một số gián tiếp bởi thực tập các chuỗi trong các nút, và thêm các nút thêm cho dài, chuỗi con chung. Ví dụ:

unique_strings = [ # Not a real array, just an hypothetical "intern table" 
    "The quick ", 
    "brown fox ", 
    "green frog ", 
    "jumps over the lazy ", 
    "dog.", 
    "fox.", 
    "frog.", 
] 
radix_trie = (0, {  # The quick * 
    "b":(1, {    # The quick brown fox * 
     "j":(3, {   # The quick brown fox jumps over the lazy * 
      "d":(4,{},1), # The quick brown fox jumps over the lazy dog. 
      "f":(6,{},3), # The quick brown fox jumps over the lazy frog. 
     }), 
    }), 
    "g":(2, {    # The quick green frog * 
     "j":(3, {   # The quick green frog jumps over the lazy * 
      "f":(5,{},2), # The quick green frog jumps over the lazy fox. 
     }), 
    }), 
}) 
# The nodes ("b", "j") and ("g", "j") wouldn't occur in a regular radix tree, 
# since they have no siblings. Adding them, however, gives a net gain of space. 
# 
# "jumps over the lazy " is a common substring of 
#  "brown fox jumps over the lazy " and 
#  "green frog jumps over the lazy fox." 
# which would occur naturally in a radix tree with only the 3 sentences given. 
paths = { 
    1:("b", "j", "d"), 
    2:("g", "j", "f"), 
    3:("b", "j", "f"), 
} 

Tất nhiên, ví dụ của bạn dễ thiết lập, nhưng việc tìm kiếm các dữ liệu lặp lại "trong tự nhiên" sẽ phức tạp hơn một chút. (tìm các đoạn dài phổ biến trong bất kỳ chuỗi nào: hoạt động rất tốn kém doable, xem cập nhật) Tuy nhiên, giả sử rằng chèn/xóa là một hoạt động không thường xuyên, đó không phải là vấn đề lớn.

Lưu ý: Tôi đề xuất một cây radix thay vì một trie vì các yêu cầu về không gian trước đây nhỏ hơn nhiều.

---

Cập nhật: chỉ trong trường hợp bạn đang có kế hoạch giải quyết vấn đề bằng cách cho mình, đây là một gợi ý nhiều hơn để nén dữ liệu của bạn sử dụng một cây radix: theo bài viết trên Wikipedia về longest common substring, bạn có thể xây dựng một generalised suffix tree và sử dụng nó để tìm các chất nền chung của hai hoặc nhiều chuỗi (nó cũng đề cập đến nó chủ yếu được sử dụng trong tin sinh học). Tạo một cái cho các nút của cây radix của bạn (hoặc, ít nhất, những cái ở trên một kích thước nhất định), bạn có thể tìm thấy các trường hợp bạn muốn chia chúng thành các nút nhỏ hơn.

Sử dụng ví dụ của bạn, "thường xuyên" (không có con duy nhất) cây radix sẽ là:

radix_tree = ("The quick ", { 
    "b":("brown fox jumps over the lazy ", { 
     "d":("dog.",{},1), 
     "f":("frog.",{},3), 
    }), 
    "g":("green frog jumps over the lazy fox.", {}, 2), 
}) 

mà rõ ràng không làm một công việc tuyệt vời tại nén văn bản của bạn. Nhưng sau khi tạo một cây hậu tố cho tập hợp các từ trong mỗi nút, nó trở nên rõ ràng rằng " jumps over the lazy " là một ứng cử viên tốt để được interned và tái sử dụng trong hai hoặc nhiều nút (kết quả trong ví dụ tôi đã cho thấy trước đó). Không gian được lưu sẽ luôn là (string_length - (1..2)*sizeof_node) * num_nodes (1 cho tiền tố/hậu tố, 2 cho phần còn lại), vì vậy các chuỗi ngắn không cần phải được xem xét khi thực hiện tối ưu hóa này.

Phức tạp, có, và như Adam Mihalcin lưu ý, một giải pháp Python thuần túy có thể sẽ quá tốn kém để lưu trữ một tập dữ liệu rất lớn. Nhưng trong trường hợp không có giải pháp làm sẵn trên mạng, đây là những gì tôi sẽ cố gắng đầu tiên ...