cách tìm kiếm một từ đã cho từ một cơ sở dữ liệu khổng lồ?

Question

Phương pháp hiệu quả nhất để tìm kiếm một từ từ cơ sở dữ liệu từ điển là gì. Tôi đã tìm kiếm câu trả lời và mọi người đã đề xuất sử dụng cấu trúc dữ liệu trie. Nhưng chiến lược tạo cây cho một số lượng lớn các từ sẽ là tải bộ nhớ chính. Tôi đang cố gắng tạo một ứng dụng Android liên quan đến việc triển khai này cho dự án cấu trúc dữ liệu của tôi. Vì vậy, bất cứ ai có thể cho tôi biết làm thế nào để làm việc từ điển.

Ngay cả khi tôi sử dụng từ điển t9 trong điện thoại, các đề xuất cho các từ xuất hiện rất nhanh trên màn hình. Tò mò để biết thuật toán và thiết kế đằng sau nó.

Answer 1

Bạn có thể sử dụng Trie hữu ích nhất để tìm kiếm từ điển lớn. Bởi vì có quá nhiều từ đang sử dụng khởi động tương tự, trie brgins xung quanh tìm kiếm yếu tố liên tục, bạn cũng có thể sử dụng tại chỗ, với số lượng hạn chế truy cập vào bộ nhớ vật lý. Bạn có thể tìm thấy nhiều triển khai trong web.

Nếu ai đó không quen thuộc với Trie, tôi nghĩ this trang web là tốt và tôi chỉ trích mẫu của họ ở đây:

Một Trie (từ hồi), là một cấu trúc cây đa chiều rất hữu ích cho lưu trữ chuỗi trên bảng chữ cái. Nó đã được sử dụng để lưu trữ lớn từ điển tiếng Anh (nói) từ trong các chương trình kiểm tra chính tả và trong các chương trình "hiểu biết" ngôn ngữ tự nhiên. Căn cứ vào dữ liệu:

an, ant, all, allot, alloy, aloe, are, ate, be 

các Trie tương ứng sẽ là:

này là tốt thực tiễn thực hiện Trie trong java: http://code.google.com/p/google-collections/issues/detail?id=5

Answer 2

Có rất nhiều cách để làm điều đó. Cái mà tôi đã sử dụng một thời gian trước đây (đặc biệt tốt nếu bạn không thay đổi từ điển của bạn) là tạo ra một chỉ mục tiền tố.

Tức là, bạn sắp xếp các mục nhập lexicologicaly. Sau đó, bạn lưu các vị trí (cuối) của các phạm vi cho các chữ cái đầu tiên khác nhau. Tức là, nếu các mục của bạn có các chỉ mục từ 1 đến 1000, và các từ "aardvark - azerbaijan" lấy phạm vi từ 1 đến 200, bạn tạo một mục trong một bảng riêng "a | 200", thì bạn cũng làm như vậy cho lần đầu tiên và chữ cái thứ hai. Sau đó, nếu bạn cần tìm một từ cụ thể, bạn sẽ giảm đáng kể phạm vi tìm kiếm. Trong trường hợp của tôi, chỉ số trên hai chữ cái đầu tiên là khá đầy đủ.

Một lần nữa, phương pháp này yêu cầu bạn sử dụng một DB, như SQLite, mà tôi nghĩ là có mặt trên Android.

Answer 3

Sử dụng trie thực sự là không gian, chỉ cần nhận ra khi tôi kiểm tra việc sử dụng RAM sau khi tải 150.000 từ vào trie, mức sử dụng là 150 MB (Trie được thực hiện bằng C++). Mức tiêu thụ bộ nhớ rất lớn do con trỏ. Tôi đã kết thúc với cố gắng ba lần mà có rất ít bộ nhớ lãng phí khoảng 30 MB (so với 150 MB) nhưng độ phức tạp thời gian đã tăng lên một chút. Một lựa chọn khác là sử dụng "Left child Right anh chị em" trong đó có rất ít lãng phí bộ nhớ nhưng phức tạp thời gian là nhiều hơn so với trie ternary.