Tôi được hỏi trong một cuộc phỏng vấn làm thế nào tôi sẽ thiết kế từ điển tiếng Anh Oxford.Thiết kế từ điển tiếng Anh Oxford
Tôi đã nói với anh ấy rằng tôi muốn sử dụng cấu trúc dữ liệu TREE, nhưng anh ấy trả lời rằng nó sẽ mất rất nhiều bộ nhớ. Vậy cấu trúc dữ liệu nào khác nên được sử dụng?
cấu trúc Một dữ liệu tôi nghe được sử dụng trong quá khứ trong điện thoại di động để lưu trữ từ điển T9 là như sau (tốt, điều này đề cập đến chỉ có vấn đề quan trọng, nhưng không phải là lưu trữ định nghĩa):
Entries đều được sắp xếp, và mỗi mục nhập phải bắt đầu bằng một khoản bù vào mục nhập trước đó từ vị trí cần tiếp tục và cũng là phần tiếp theo. Ví dụ:
apple
4icable
7tion
sẽ giải mã cho ứng dụng, ứng dụng của apple. Tuy nhiên điều này có thể không phải là khác biệt so với cố gắng với chuỗi sáp nhập, xem
appl -> e
-> ica -> ble
-> tion
Wikipedia phát hiện các Directed acyclic word graph, mà khác với cây mà nó không chỉ chi nhánh, nhưng các chi nhánh có thể hợp nhất, nơi từ có hậu tố tương tự. Điều này thực sự có thể là một lưu trữ cao cấp.
a
/\
pplic utom
\/
ation
Bằng cách này, wikipedia chỉ nói với tôi rằng "nếu lưu trữ các từ điển là tất cả những gì được yêu cầu, một động cơ tự động hữu hạn xác định nhỏ nhất sẽ sử dụng ít không gian hơn một trie". Đã thêm vào câu trả lời. – ron
Nó sẽ không sử dụng nhiều bộ nhớ. Câu trả lời của bạn ổn. Có lẽ vào năm 1995. Hãy xem xét cho mình may mắn.
Như những người khác đã đề cập, nếu không có đủ mái cho một chiếc xe được thiết kế tốt, có thể không còn chỗ cho bất kỳ loại chỉ mục nào khác. Vì đây là một câu hỏi phỏng vấn, có vẻ như anh ta đang cố gắng hướng bạn đến các cơ sở dữ liệu ngoài lõi cổ điển như cây B.
Cách khác, một phản ứng tốt có thể là hỏi thêm thông tin, như "loại hoạt động nào bạn muốn thực hiện trên cơ sở dữ liệu này và bạn cần loại hiệu suất nào?" Nếu bạn chỉ muốn kiểm tra chính tả, thì bộ lọc Bloom có thể là "datastructure" hiệu quả nhất ...
chỉ là một điều ngớ ngẩn nhưng không sử dụng từ điển tiếng Anh thay vì lập bản đồ thế giới sang một từ khác ý nghĩa của từ trong một vài câu/cụm từ? Trong trường hợp đó, mã hóa từ ít nhất là vấn đề của bạn và bạn nên suy nghĩ về việc đại diện cho ý nghĩa của các từ (ngữ pháp, vv) hoặc thậm chí xem xét đóng gói dựa trên từ điển như LHARC. May mắn cho bạn tiếng Anh không phải là rất phức tạp theo cách này ... – Spektre