Tìm các chuỗi trùng lặp trong một tệp lớn

Question

Một tệp có chứa số lượng lớn (ví dụ.10 tỷ) các chuỗi và bạn cần phải tìm các chuỗi trùng lặp. Bạn có sẵn N hệ thống. Bạn sẽ tìm thấy các bản sao như thế nào

Answer 1

Tách tệp thành các phần N. Trên mỗi máy, nạp càng nhiều phần vào bộ nhớ càng tốt, và sắp xếp các chuỗi. Viết các khối này vào dung lượng lưu trữ trên máy đó. Trên mỗi máy, hợp nhất các khối thành một dòng duy nhất, sau đó hợp nhất luồng từ mỗi máy vào một luồng có chứa tất cả các chuỗi theo thứ tự sắp xếp. So sánh từng chuỗi với chuỗi trước đó. Nếu chúng giống nhau, nó trùng lặp.

Answer 2

Câu trả lời của erickson có lẽ là câu trả lời có thể xảy ra bởi bất kỳ ai đặt câu hỏi này.

Bạn có thể sử dụng mỗi máy N như một cái xô trong một Hashtable:

• cho mỗi chuỗi, (nói chuỗi số i theo thứ tự) tính toán một hàm băm vào nó, h.
• gửi các giá trị của i và h tới số máy n để lưu trữ, trong đó n = h% N.
• từ mỗi máy, truy xuất danh sách tất cả giá trị băm mà đã nhận được nhiều hơn một chỉ mục với danh sách các chỉ mục.
• kiểm tra tập hợp các chuỗi có giá trị băm bằng nhau để xem liệu chúng có thực sự bằng nhau hay không.

Thành thật mà nói, với 10 tỷ chuỗi, bạn có thể làm điều này một cách đáng tin cậy trên 1 PC. Các hashtable có thể chiếm một cái gì đó như 80-120 GB với một băm 32 bit, tùy thuộc vào thực hiện hashtable chính xác. Nếu bạn đang tìm kiếm một giải pháp hiệu quả, bạn phải cụ thể hơn một chút về "máy", bởi vì nó phụ thuộc vào dung lượng lưu trữ của mỗi máy và chi phí tương đối của truyền thông mạng.