Gần đây tôi đã nghiên cứu Patricia cố gắng, và làm việc với một thực sự tốt C++ implementation mà có thể được sử dụng như một STL phân loại liên kết Container. Patricia cố gắng khác với cây nhị phân bình thường vì các nút lá có con trỏ quay lại trỏ tới các nút bên trong. Tuy nhiên, nó có thể đi qua một Tria Patricia theo thứ tự bảng chữ cái bằng cách thực hiện một traversal theo thứ tự, nếu bạn chỉ truy cập các nút nội bộ thông qua các nút con trỏ nút lá.STLish lower_bound chức năng cho Radix/Patricia Trie
Điều này mang lại cho tôi câu hỏi: có thể triển khai các chức năng STL lower_bound và upper_bound với một bộ ba Patricia không? Triển khai tôi đang sử dụng thực hiện trên thực tế, triển khai các chức năng này, nhưng chúng không hoạt động như mong đợi.
Ví dụ:
typedef uxn::patl::trie_set<std::string> trie;
trie ts;
ts.insert("LR");
ts.insert("BLQ");
ts.insert("HCDA");
trie::iterator it = ts.lower_bound("GG");
std::cout << *it << std::endl;
này kết quả đầu ra BLQ, khi tôi mong chờ nó ra HCDA. (Ví dụ: An std::set, chắc chắn sẽ xuất HCDA tại đây.)
Tôi đã gửi email cho nhà phát triển đã tạo thư viện này nhưng không bao giờ nhận được phản hồi. Bất kể, tôi cảm thấy tôi có một sự hiểu biết khá tốt về cách Patricia cố gắng làm việc, và tôi không thể tìm ra cách một thứ gì đó như lower_bound thậm chí có thể thực hiện được. Vấn đề là lower_bound dường như dựa vào khả năng so sánh từ điển hai chuỗi. Vì "GG" không tồn tại trong cây, chúng ta cần phải tìm ra phần tử nào là> = đến GG. Nhưng Radix/Patricia cố gắng không sử dụng so sánh từ điển để di chuyển từ nút này sang nút khác; thay vì mỗi nút lưu trữ một chỉ mục bit được sử dụng để thực hiện so sánh bit trên khóa tìm kiếm. Kết quả của so sánh bit cho bạn biết có di chuyển sang trái hay phải không. Điều này giúp dễ dàng tìm thấy một tiền tố cụ thể trong cây. Nhưng nếu tiền tố không tồn tại trong cây, (như trong trường hợp tìm kiếm của tôi cho "GG"), dường như không có cách nào, thiếu so sánh từ điển, để có được lower_bound.
Thực tế là việc triển khai C++ tôi đang sử dụng dường như không thực hiện low_bound đúng xác nhận nghi ngờ của tôi rằng điều đó có thể không thực hiện được. Tuy nhiên, thực tế là bạn có thể lặp lại trên cây theo thứ tự chữ cái khiến tôi nghĩ rằng có thể có một cách để làm điều đó.
Có ai có kinh nghiệm với điều này hoặc biết liệu có thể triển khai chức năng lower_bound với Patricia Trie không?
Chắc chắn có thể, miễn là vùng chứa trên thực tế được sắp xếp. Tệ nhất, bạn có thể: trie :: iterator it = ts.begin(); trong khi (it! = ts.end() && * it <"GG") ++; Cho dù bạn có thể làm điều đó hiệu quả hơn là một câu hỏi khác. Tôi sẽ ngạc nhiên nếu nó không thể làm tốt hơn bằng cách sử dụng cấu trúc trie thực tế, nhưng tôi không hoàn toàn biết đủ về những cố gắng để phát hiện một lỗi trong mã chỉ từ trình duyệt. – aschepler