Cấu trúc dữ liệu để tìm kiếm tên tệp và nhận đường dẫn của nó

Question

Tôi sẽ chèn tên tệp theo cách động, khoảng 1 tỷ tên. Bên cạnh đó, tôi cũng muốn lưu trữ đường dẫn nơi các tệp được đặt để thực hiện các truy vấn sau:

• Tìm kiếm tên của tệp được lưu trữ để lấy đường dẫn.
• Tìm kiếm tên của tất cả các tệp phù hợp với chuỗi con, một kiểu giống như truy vấn (ví dụ: Nếu tìm kiếm * o *, nó sẽ trả về hàm joel, hola, ola, oso, osea, algo, nếu a tìm kiếm aa *, nó sẽ trả về aaab và nếu tôi tìm kiếm * như vậy, nó sẽ trả về oso).
• Xóa tên tệp.

Vì vậy, tôi đang cố gắng để tạo ra một loại cấu trúc dữ liệu Trie theo cách sau:

tôi đã 26 nút (bảng chữ cái az tiếng anh, tôi sẽ không đặt tất cả các nút trong hình ảnh bởi vì không gian) sao cho nếu tôi chèn từ "hola" thì tôi tạo một cạnh từ nút có chữ 'h' đến nút có chữ 'o' và cạnh của nó có dữ liệu 1 vì con số này thể hiện mức độ sâu . Hơn nữa, trong nút nơi 'a' được lưu trữ, tôi sẽ có một cấu trúc bản đồ để lưu trữ đường dẫn của tệp, điều này là bởi vì tôi chắc chắn sẽ có rất nhiều đường dẫn được lưu trữ trong nút chứa ký tự 'a' .

Có nói rằng, tôi đã chèn các từ sau: joel, hola, ola, oso, osea, algo, aaab.

Tôi đã làm như vậy bởi vì tôi không muốn có nhiều nút với Lettres sama (ví dụ a, b, vv) nhưng vấn đề là tôi có rất nhiều cạnh và sctructure cần

byte bộ nhớ (tôi lập trình trong C++), nơi w là một chuỗi các kích thước .

Như bạn có thể thấy, nếu tôi tìm kiếm tên tệp "jola" (không được chèn) thì sẽ không có đường dẫn nào được trả lại và điều này cho chúng tôi biết rằng tệp đó không được lưu trữ.

Tôi làm cách nào để cải thiện điều này? Có cách nào để giảm số cạnh không? hoặc có một cấu trúc tốt hơn và cách để làm điều này? Tôi rất cởi mở khi nghe bất cứ đề xuất nào.

Answer 1

bạn có thể sử dụng một DAG (Đạo mạch hở Graph) hoặc cũng có thể sử dụng các kỹ thuật thiết lập hoạt động tách rời nhau (kỹ thuật tìm nhanh (* là mục tiêu chính của bạn là để tìm))