Tìm k từ phổ biến nhất trong một tập tin - sử dụng bộ nhớ

Question

Giả sử bạn được cung cấp một tệp lớn, giả sử là 1GB. Tệp có chứa một từ trên mỗi dòng (tổng số từ n) và bạn muốn tìm các cụm từ thường gặp nhất trong tệp.

Bây giờ, giả sử bạn có đủ bộ nhớ để lưu trữ những từ này, cách tốt nhất để tiếp cận câu hỏi về cách giảm mức sử dụng bộ nhớ và chi phí liên tục trong độ phức tạp của Big-O là gì? Tôi tin rằng có hai thuật toán cơ bản mà một người có thể sử dụng:

1. Sử dụng bảng băm và một phần nhỏ để lưu trữ các lần xuất hiện và các từ đầu K được xem. Đây là O (n + nlogk) ~ O (N)
2. Sử dụng bộ ba để lưu trữ các từ và lần xuất hiện và sau đó đi qua bộ ba để đếm các từ thường xuyên nhất. Đây là O (n * p) ~ O (N) trong đó p là độ dài của từ dài nhất.

Cách tiếp cận nào tốt hơn?

Ngoài ra: nếu bạn không có đủ bộ nhớ cho bảng băm/trie (nghĩa là bộ nhớ giới hạn 10MB hoặc hơn), thì cách tiếp cận tốt nhất là gì?

Answer 1

Đối với tùy chọn bộ nhớ giới hạn, bạn có thể nhanh chóng sắp xếp danh sách trước, sau đó chỉ cần điền bảng băm có k mục trong đó. Sau đó bạn sẽ cần thêm một truy cập để biết có bao nhiêu mục trong từ hiện tại bạn đang kiểm tra - nếu nó cao hơn thì bạn thay thế mục thấp nhất trong bảng băm bằng mục hiện tại của bạn.

Điều này có thể hoạt động tốt cho danh sách ban đầu, nhưng sẽ chậm hơn so với chỉ quét danh sách đầy đủ và điền bảng băm với số lượng.

Answer 2

Hiệu quả hơn về hằng số là rất phụ thuộc. Một mặt, trie cung cấp độ phức tạp thời gian nghiêm ngặt O(N) để chèn tất cả các phần tử, trong khi bảng băm có thể phân rã thành thời gian tối thiểu trong trường hợp xấu nhất.
Mặt khác, cố gắng không hiệu quả khi nói đến cache - mỗi yêu cầu yêu cầu O(|S|)truy cập ngẫu nhiên yêu cầu bộ nhớ, có thể làm giảm hiệu suất đáng kể.

Cả hai cách tiếp cận đều hợp lệ và tôi nghĩ có nhiều cân nhắc cần thực hiện khi chọn một cái khác như tối đa latency (nếu đó là hệ thống thời gian thực), thông lượng và thời gian phát triển.

Nếu hiệu suất của trường hợp trung bình là quan trọng, tôi khuyên bạn nên tạo một loạt tệp và chạy statistical analysis cách tiếp cận nào tốt hơn. Wilcoxon kiểm tra đã ký là bài kiểm tra giả thuyết thực tế hiện đang được sử dụng.

---

Về hệ thống nhúng: cả hai phương pháp vẫn còn hiệu lực, nhưng ở đây: Mỗi "Node" (hoặc bó nodes) trong Trie sẽ được trên đĩa chứ không phải sau đó trên RAM. Lưu ý rằng nó có nghĩa là cho trie O (| S |) truy cập ngẫu nhiên đĩa tìm kiếm mỗi mục, có thể bị chậm.

Đối với các giải pháp băm, bạn có 10MB, giả sử chúng có thể sử dụng 5MB trong số này cho bảng băm của con trỏ vào đĩa.Giả sử bạn có thể lưu trữ 500 địa chỉ đĩa khác nhau trên 5MB (phân tích bi quan ở đây), điều đó có nghĩa là bạn còn 5MB để tải một thùng sau mỗi lần tìm kiếm băm và nếu bạn có 500 nhóm, với hệ số tải là 0.5, điều đó có nghĩa là bạn có thể lưu trữ 500 * 5MB * 0,5 ~ = 1,25GB> 1GB dữ liệu của bạn, do đó, sử dụng giải pháp bảng băm, do đó, sử dụng băm - mỗi tìm kiếm sẽ chỉ cần O(1)ngẫu nhiên đĩa tìm kiếm để tìm nhóm chứa chuỗi có liên quan.

Lưu ý rằng nếu nó vẫn chưa đủ, chúng tôi có thể khôi phục lại bảng con trỏ, rất giống với những gì đang được thực hiện trong paging table trong cơ chế bộ nhớ ảo.

Từ điều này chúng ta có thể kết luận, đối với các hệ thống nhúng, giải pháp băm tốt hơn cho hầu hết các trường hợp (lưu ý nó vẫn có thể bị trễ cao trong trường hợp xấu nhất, không có dấu đầu dòng bạc).

---

PS, radix tree thường là nhanh hơn và nhỏ gọn sau đó Trie, nhưng bị các tác dụng phụ tương tự của Trie so với băm bảng (mặc dù ít quan trọng, tất nhiên).

Answer 3

Bạn có lái xe để lưu trữ kết quả trung gian không? nếu đúng:

bạn có thể có một số cấu trúc meta. và một bộ băm. Bạn đọc một phần dữ liệu (trong khi kích thước của bạn băm < 3 mb) và điền vào có thể bắt đầu. khi kích thước> 3mb bạn lưu trên đĩa. nếu bạn giới hạn kích thước 10 mb của hashtable là 3 mb (ví dụ).

meta phân tách các thẻ bắt đầu bằng # của bạn. trong meta, bạn có thể lưu trữ số lượng từ và số lượng duy nhất của tất cả các từ trong hash này và số lượng tối đa của một thế giới !!! i

sau này. bạn có thể tải hashtables từ đĩa và hợp nhất. Ví dụ:

ví dụ: bạn có thể tải Hashtable theo thứ tự tăng dần của các từ duy nhất hoặc số lượng tối đa của một thế giới bằng băm. trong bước này bạn có thể sử dụng một số heuristic.