Tôi có một danh sách dài các từ và tôi muốn hiển thị các từ bắt đầu bằng văn bản do người dùng nhập. Khi người dùng nhập một ký tự, ứng dụng sẽ cập nhật danh sách được hiển thị cho người dùng. Nó sẽ giống như AutoCompleteTextView trên Android. Tôi chỉ tò mò về cấu trúc dữ liệu tốt nhất để lưu trữ các từ để tìm kiếm rất nhanh.Cấu trúc dữ liệu tốt nhất để hoàn thành tự động văn bản là gì?
Có thể sử dụng bộ ba. http://en.wikipedia.org/wiki/Triehttps://stackoverflow.com/search?q=trie
Một bài viết tốt đẹp - http://www.sarathlakshman.com/2011/03/03/implementing-autocomplete-with-trie-data-structure/
PS: Nếu bạn có một số tiểu cảnh quay "không chi nhánh", sau đó bạn có thể tiết kiệm không gian bằng cách sử dụng một Trie radix, mà là một thực hiện Trie mà đặt nhiều ký tự trong nút khi có thể - http://en.wikipedia.org/wiki/Radix_tree
Bạn có thể tìm thấy chủ đề này thú vị:
Nó không chính xác những gì bạn muốn, thay vào đó là một phiên bản hơi mở rộng của vấn đề của bạn.
Đối với việc thực hiện các chức năng tự động, cây tìm kiếm tam phân (TST) cũng được sử dụng:
http://igoro.com/archive/efficient-auto-complete-with-a-ternary-search-tree/
Tuy nhiên, nếu bạn muốn tìm thấy bất kỳ chuỗi ngẫu nhiên trong một chuỗi, hãy thử một cây hậu tố tổng quát.
Tries (và các giống khác nhau của họ) là hữu ích ở đây. Điều trị chi tiết hơn về chủ đề này là trong số paper này. Có lẽ bạn có thể thực hiện một trie hoàn thành cho Android?
Tôi nghĩ bảng băm sẽ là tốt nhất. Tôi không chắc chắn về ngôn ngữ hoặc nền tảng bạn đang sử dụng, vì vậy nói chung bảng băm nhanh và năng động. – c0d3Junk13
cũng ... trước tiên chúng tôi cần biết nền tảng bạn đang làm việc. Android? iOS? Các cửa sổ? Linux? OSX? Web hoặc HTML? –
@ c0d3Junk13 Bạn sẽ tìm kiếm các chuỗi với một tiền tố đã cho trong một hashtable như thế nào? – delnan