Chúng tôi thấy Google, Firefox một số trang AJAX hiển thị danh sách các mục có thể xảy ra khi người dùng nhập ký tự.Thuật toán tự động hoàn thành/đề xuất, datastructure [C++/C]
Ai đó có thể cung cấp thuật toán, cấu trúc dữ liệu tốt để triển khai tự động hoàn thành không?
A trie là cấu trúc dữ liệu có thể được sử dụng để nhanh chóng tìm các từ khớp với tiền tố.
Edit: Đây là một ví dụ cho thấy làm thế nào để sử dụng một trong để thực hiện tự động hoàn http://rmandvikar.blogspot.com/2008/10/trie-examples.html
Đây là sự so sánh giữa 3 khác nhau auto-complete implementations (mặc dù đó là trong Java không phải C++).
* In-Memory Trie
* In-Memory Relational Database
* Java Set
Khi tra cứu các phím, trie nhanh hơn so với thực hiện Cài đặt. Cả trie và bộ đều nhanh hơn một chút so với giải pháp cơ sở dữ liệu quan hệ.
Chi phí thiết lập của Bộ thấp hơn giải pháp Trie hoặc DB. Bạn sẽ phải quyết định xem bạn có đang xây dựng mới "các từ" thường xuyên hay không hay tốc độ tra cứu là ưu tiên cao hơn.
Các kết quả này bằng Java, số dặm của bạn có thể thay đổi theo giải pháp C++.
Đối với một giải pháp đơn giản: bạn tạo ra một 'ứng cử viên' với một chỉnh sửa tối thiểu (Levenshtein) khoảng cách (1 hoặc 2) sau đó bạn kiểm tra sự tồn tại của các ứng cử viên với một container băm (thiết sẽ đủ cho một soltion đơn giản , sau đó sử dụng unordered_set từ tr1 hoặc tăng).
Ví dụ: Bạn đã viết carr và bạn muốn ô tô. arr được tạo bởi 1 lần xóa. Là arr trong unordered_set của bạn? Số crr được tạo ra bởi 1 lần xóa. Là crr trong unordered_set của bạn? Số xe được tạo ra bởi 1 lần xóa. Là chiếc xe trong unordered_set của bạn? Có, bạn thắng.
Tất nhiên có chèn, xóa, chuyển vị vv ...
Bạn thấy rằng thuật toán của bạn để tạo ra các ứng cử viên thực sự là nơi mà bạn đang lãng phí thời gian, đặc biệt là nếu bạn có một rất ít unordered_set.
Đối với các tập dữ liệu lớn, một ứng cử viên tốt cho chương trình phụ trợ sẽ là cây tìm kiếm Ternary. Chúng kết hợp tốt nhất trong hai thế giới: chi phí không gian thấp của cây tìm kiếm nhị phân và hiệu quả thời gian dựa trên ký tự của các tìm kiếm kỹ thuật số.
Xem trong TS Dobbs Journal: http://www.ddj.com/windows/184410528
Mục đích là việc thu hồi nhanh chóng của một resultset hữu hạn như các loại dùng trong Cho phép đầu tiên cho rằng để tìm kiếm "khoa học máy tính" bạn có thể gõ từ "máy tính". hoặc "khoa học" nhưng không phải "máy tính". Vì vậy, đưa ra một cụm từ, tạo các cụm từ con bắt đầu bằng một từ. Bây giờ cho mỗi cụm từ, hãy đưa chúng vào TST (cây tìm kiếm bậc ba). Mỗi nút trong TST sẽ đại diện cho một tiền tố của một cụm từ đã được gõ cho đến nay. Chúng tôi sẽ lưu trữ 10 kết quả tốt nhất (nói) cho tiền tố đó trong nút đó. Nếu có nhiều ứng cử viên hơn số lượng kết quả hữu hạn (10 ở đây) cho một nút, cần có một hàm xếp hạng để giải quyết sự cạnh tranh giữa hai kết quả.
Cây có thể được xây dựng sau mỗi vài giờ, tùy thuộc vào tính năng động của dữ liệu.Nếu dữ liệu trong thời gian thực, thì tôi đoán một số thuật toán khác sẽ mang lại sự cân bằng tốt hơn. Trong trường hợp này, yêu cầu tuyệt đối là thu hồi nhanh các kết quả cho mọi lần gõ phím mà nó thực hiện rất tốt.
Các biến chứng khác sẽ phát sinh nếu đề xuất sửa lỗi chính tả có liên quan. Trong trường hợp đó, các thuật toán chỉnh sửa khoảng cách cũng sẽ được xem xét.
Đối với các tập dữ liệu nhỏ như danh sách các quốc gia, việc triển khai Trie đơn giản sẽ thực hiện. Nếu bạn định triển khai một trình đơn thả xuống tự động hoàn chỉnh trong một ứng dụng web, tiện ích tự động hoàn thành của YUI3 sẽ làm mọi thứ cho bạn sau khi bạn cung cấp dữ liệu trong danh sách. Nếu bạn sử dụng YUI3 chỉ là giao diện người dùng cho tự động hoàn tất được hỗ trợ bởi dữ liệu lớn, hãy tạo các dịch vụ web dựa trên TST bằng C++ và sau đó sử dụng nguồn dữ liệu nút tập lệnh của tiện ích tự động điền để tìm nạp dữ liệu từ dịch vụ web thay vì danh sách đơn giản.
Nếu bạn muốn đề nghị hoàn phổ biến nhất, một "Đề nghị Tree" có thể là một lựa chọn tốt: Suggest Tree
Segment trees thể được sử dụng để thực hiện một cách hiệu quả auto complete
Hơi liên quan là mô tả Peter Norvig của Google Làm thế nào để sửa lỗi chính tả: http://norvig.com/spell-correct.html –
Một Trie tiêu chuẩn là bộ nhớ rất chuyên sâu, đối với các bộ lớn hơn, bạn muốn sử dụng một Trie nhỏ gọn giúp giảm đáng kể dung lượng bộ nhớ. Các tối ưu hóa bổ sung bao gồm việc khởi tạo lười biếng các giá trị nút và cấu trúc dữ liệu phù hợp cho các tập con/giá trị. Cách đây không lâu, tôi đã tạo [thư viện tự động hoàn chỉnh] (https://github.com/fmmfonseca/completely) có khả năng xử lý các tập dữ liệu rất lớn (10.000.000+) và trả lời hiệu quả các tìm kiếm chính xác và gần đúng. –