triển khai công cụ tìm kiếm cơ bản với cây tiền tố

Question

Sự cố là triển khai cây tiền tố (Trie) bằng ngôn ngữ chức năng mà không sử dụng bất kỳ phương pháp lưu trữ và lặp lại nào.

Tôi đang cố giải quyết vấn đề này. Tôi nên tiếp cận vấn đề này như thế nào? Bạn có thể cho tôi thuật toán chính xác hoặc liên kết cho thấy đã thực hiện một trong bất kỳ ngôn ngữ chức năng nào không?

Tại sao tôi đang cố gắng để làm => tạo ra một công cụ tìm kiếm đơn giản với một tính năng của

• thêm từ để cây
• tìm kiếm một từ trong cây
• xóa một từ trong cây

Tại sao tôi muốn sử dụng ngôn ngữ chức năng => Tôi muốn cải thiện khả năng giải quyết vấn đề của mình thêm một chút.

LƯU Ý: Vì đây là dự án sở thích của tôi, trước tiên tôi sẽ triển khai các tính năng cơ bản.

EDIT:

i) Những gì tôi có ý nghĩa về "mà không sử dụng lưu trữ" => Tôi không muốn sử dụng lưu trữ biến (ví dụ: int a), tham chiếu đến một biến, mảng.. Tôi muốn tính toán kết quả theo đệ quy sau đó hiển thị kết quả cho màn hình.

ii.) Tôi đã viết một số dòng nhưng sau đó tôi đã bị xóa vì những gì tôi đã viết khiến tôi tức giận. Xin lỗi vì đã không thể hiện nỗ lực của tôi.

Answer 1

Hãy xem số Data.IntMap của haskell.Nó hoàn toàn là chức năng thực hiện của Patricia trie và nó là source là khá dễ đọc.
bytestring-trie gói mở rộng phương pháp này để ByteStrings

Có kèm theo giấy Fast Mergeable Integer Maps mà cũng có thể đọc và thông qua. Nó mô tả việc thực hiện từng bước: từ nhị phân cố gắng đến cây patricia lớn.
Dưới đây là ít trích xuất từ ​​bài báo.

Tại đơn giản nhất, một Trie nhị phân là một cây nhị phân hoàn chỉnh về chiều sâu bằng số bit trong các phím, trong đó mỗi lá là một trong hai rỗng, chỉ ra rằng các phím tương ứng là không ràng buộc, hay đầy đủ, trong trường hợp nào chứa dữ liệu mà khóa tương ứng là bị ràng buộc. Phong cách này của Trie có thể được đại diện trong Standard ML như

datatype 'a Dict = 
    Empty 
    | Lf of 'a 
    | Br of 'a Dict * 'a Dict 

Để tra cứu một giá trị trong một Trie nhị phân, chúng tôi chỉ đơn giản là đọc các bit của khóa , Với thiết bị sang trái hoặc phải theo chỉ dẫn, cho đến khi chúng ta đạt được một lá.

fun lookup (k, Empty) = NONE 
    | lookup (k, Lf x) = SOME x 
    | lookup (k, Br (t0,t1)) = 
     if even k then lookup (k div 2, t0) 
       else lookup (k div 2, t1) 

Answer 2

Điểm quan trọng trong việc triển khai cấu trúc dữ liệu không thay đổi là chia sẻ của cả hai dữ liệu và cấu trúc . Để cập nhật một đối tượng, bạn nên tạo phiên bản mới của nó với số lượng nút chia sẻ nhiều nhất có thể. Cụ thể cho các cố gắng sau cách tiếp cận có thể được sử dụng.

xem xét như một Trie (từ Wikipedia):

Hãy tưởng tượng rằng bạn chưa thêm chữ "quán trọ", nhưng bạn đã có chữ "trong". Để thêm "quán trọ", bạn phải tạo phiên bản mới của toàn bộ trie với "quán trọ" được thêm vào. Tuy nhiên, bạn không bắt buộc phải sao chép toàn bộ điều - bạn chỉ có thể tạo ra cá thể mới của nút gốc (điều này không có nhãn) và lệnh cấm đúng. Nút gốc mới sẽ trỏ đến lệnh cấm mới, nhưng đến các chi nhánh cũ khác, vì vậy với mỗi lần cập nhật hầu hết cấu trúc được chia sẻ với trạng thái trước đó.

Tuy nhiên, các phím của bạn có thể khá dài, do đó, tạo lại toàn bộ nhánh mỗi lần vẫn còn tốn thời gian và không gian. Để giảm bớt hiệu ứng này, bạn cũng có thể chia sẻ cấu trúc bên trong một nút. Thông thường, mỗi nút là một vectơ hoặc bản đồ của tất cả các kết quả có thể có (ví dụ: trong một nút ảnh có nhãn "te" có 3 kết quả - "a", "d" và "n"). Có rất nhiều triển khai cho các bản đồ bất biến (Scala, Clojure, xem kho lưu trữ của họ để biết thêm ví dụ) và Clojure cũng có tuyệt vời implementation của một vectơ không thay đổi (thực tế là một cây).

Tất cả các thao tác tạo, cập nhật và tìm kiếm các kết quả tìm kiếm có thể được triển khai đệ quy mà không có trạng thái có thể thay đổi.