Làm cách nào để tôi có thể xây dựng biểu đồ từ tuần hoàn định hướng gia tăng để lưu trữ và tìm kiếm chuỗi?

Question

Tôi đang cố gắng lưu trữ một danh sách lớn các chuỗi theo cách súc tích để chúng có thể được phân tích/tìm kiếm rất nhanh chóng.

Biểu đồ từ tuần hoàn hướng (DAWG) phù hợp với mục đích này một cách tuyệt vời. Tuy nhiên, tôi không có một danh sách các chuỗi để bao gồm ở nơi đầu tiên, do đó, nó phải được xây dựng từng bước. Ngoài ra, khi tôi tìm kiếm thông qua nó cho một chuỗi, tôi cần phải mang lại dữ liệu liên kết với kết quả (không chỉ là một boolean nói nếu nó đã có mặt).

Tôi đã tìm thấy thông tin về sửa đổi DAWG để theo dõi dữ liệu chuỗi tại đây: http://www.pathcom.com/~vadco/adtdawg.html Dường như cực kỳ phức tạp và tôi không chắc mình có khả năng viết nó hay không.

Tôi cũng đã tìm thấy một số tài liệu nghiên cứu mô tả thuật toán xây dựng gia tăng, mặc dù tôi thấy rằng các tài liệu nghiên cứu nói chung không hữu ích lắm.

Tôi không nghĩ rằng tôi đủ nâng cao để có thể tự kết hợp cả hai thuật toán này. Có tài liệu về thuật toán đã có các tính năng này hay một thuật toán thay thế có sử dụng bộ nhớ tốt & tốc độ không?

Answer 1

Tôi đã viết trang web ADTDAWG. Thêm từ sau khi xây dựng không phải là một tùy chọn. Cấu trúc không có gì hơn 4 mảng của các kiểu số nguyên không dấu. Nó được thiết kế để không thay đổi đối với tổng bộ nhớ cache của CPU, và độ phức tạp truy cập đa luồng tối thiểu.

Cấu trúc là một automaton tạo thành hàm băm tối thiểu và hoàn hảo. Nó được xây dựng cho tốc độ trong khi di chuyển đệ quy bằng cách sử dụng một ngăn xếp rõ ràng.

Khi được xuất bản, nó hỗ trợ tối đa 18 ký tự. Bao gồm tất cả 26 ký tự tiếng Anh sẽ yêu cầu tăng thêm.

Lời khuyên của tôi là sử dụng Trie chuẩn, với chỉ mục mảng được lưu trữ trong mỗi nút. Ya, có vẻ như trẻ con, nhưng mỗi nút END_OF_WORD chỉ đại diện cho một từ. ADTDAWG là một giải pháp cho mỗi nút END_OF_WORD trong một DAWG truyền thống đại diện cho nhiều, nhiều từ.

Bảng băm tối thiểu và hoàn hảo không phải là thứ bạn có thể đặt cùng lúc khi đang di chuyển.

Tôi đang tìm kiếm một thứ gì đó khác để thực hiện hoặc công việc, vì vậy hãy liên hệ với tôi và tôi sẽ làm những gì có thể. Bây giờ, tất cả những gì tôi có thể nói là không thực tế khi sử dụng tối ưu hóa nặng nề trên một cấu trúc có thể thay đổi thường xuyên.

Answer 2

Bạn cũng có thể muốn xem cấu trúc trie cho điều này (có khả năng xây dựng một radix-tree). Nó có vẻ như một cấu trúc thay thế 'đơn giản' phong nha.

tôi đang đề xuất này trong một vài lý do:

1. tôi thực sự không có một sự hiểu biết đầy đủ các kết quả của bạn.
2. Chắc chắn gia tăng để xây dựng.
3. Nút lá có thể chứa bất kỳ dữ liệu nào bạn muốn.
4. Chủ quan, một thuật toán đơn giản.

Answer 3

Java

Đối với vấn đề biểu đồ đòi hỏi sự kiên trì, tôi muốn có một cái nhìn tại dự án Neo4j graph DB. Neo4j được thiết kế để lưu trữ các đồ thị lớn và cho phép xây dựng gia tăng và sửa đổi dữ liệu, dường như đáp ứng các tiêu chí bạn mô tả.

Họ có một số ví dụ hay để giúp bạn nhanh chóng và thường có mã ví dụ để giúp bạn bắt đầu với hầu hết các sự cố.

Họ có một số DAG example có liên kết ở cuối đến full source code.

C++

Nếu bạn đang sử dụng C++, một giải pháp chung để vẽ đồ thị xây dựng/phân tích là sử dụng Boost graph library. Để duy trì biểu đồ của bạn, bạn có thể duy trì phiên bản dựa trên tệp của biểu đồ trong GraphML (ví dụ) và đọc và ghi vào tệp đó khi biểu đồ của bạn thay đổi.