Thuật toán ghi nhật ký

Question

Chúng tôi nhận các tệp dữ liệu ~ 50GB này bao gồm 16 mã byte và tôi muốn tìm bất kỳ mã nào xảy ra 1/2% thời gian hoặc hơn. Có cách nào tôi có thể làm điều đó trong một lần vượt qua dữ liệu?

Chỉnh sửa: Có rất nhiều mã - có thể mọi mã đều khác nhau.

EPILOGUE: Tôi đã chọn Darius Bacon là câu trả lời hay nhất, vì tôi nghĩ thuật toán tốt nhất là sửa đổi phần tử đa số mà anh ta liên kết. Thuật toán đa số có thể thay đổi để chỉ sử dụng một lượng nhỏ bộ nhớ - như 201 mã để nhận được 1/2% tôi nghĩ. Về cơ bản, bạn chỉ cần đi bộ trong luồng có tới 201 mã riêng biệt. Ngay sau khi bạn tìm thấy 201 mã riêng biệt, bạn thả một trong mỗi mã (khấu trừ 1 từ các quầy, quên bất kỳ thứ gì trở thành 0). Cuối cùng, bạn đã giảm nhiều nhất là N/201 lần, vì vậy bất kỳ mã nào xuất hiện nhiều lần hơn số đó vẫn phải ở xung quanh.

Nhưng đó là thuật toán hai lần, không phải là một. Bạn cần một đèo thứ hai để kiểm đếm số lượng ứng cử viên. Thật dễ dàng thấy rằng bất kỳ giải pháp nào cho vấn đề này phải sử dụng ít nhất 2 lượt (hàng loạt các phần tử đầu tiên bạn tải có thể khác nhau và một trong các mã đó có thể kết thúc chính xác 1/2%)

Cảm ơn sự giúp đỡ!

Answer 1

Metwally et al., Efficient Computation of Frequent and Top-k Elements in Data Streams (2005). Có một số giấy tờ liên quan khác mà tôi đọc cho công việc của mình tại Yahoo mà tôi không thể tìm thấy bây giờ; nhưng điều này có vẻ như là một khởi đầu tốt.

Chỉnh sửa: Ah, xem điều này Brian Hayes article. Nó phác thảo một thuật toán chính xác do Demaine và cộng sự, với các tham chiếu. Nó làm điều đó trong một lần với rất ít bộ nhớ, mang lại một tập hợp các mục bao gồm những thứ bạn thường xuyên tìm kiếm, nếu chúng tồn tại. Lấy số đếm chính xác mất một lần thứ hai (bây giờ có thể xử lý) vượt qua.

Answer 2

điều này sẽ phụ thuộc vào việc phân phối mã. nếu có một số lượng mã riêng biệt đủ nhỏ, bạn có thể xây dựng một lõi http://en.wikipedia.org/wiki/Frequency_distribution với bản đồ. nếu không bạn có thể sẽ phải xây dựng một http://en.wikipedia.org/wiki/Histogram và sau đó thực hiện nhiều lần vượt qua dữ liệu kiểm tra tần số mã trong mỗi nhóm.

Answer 3

Điều đó tùy thuộc vào số lượng mã khác nhau tồn tại và số lượng bộ nhớ bạn có sẵn.

Ý tưởng đầu tiên của tôi là xây dựng bảng băm của bộ đếm, với mã là khóa. Lặp lại toàn bộ tệp, tăng số lượt truy cập của mã tương ứng và đếm số tổng thể. Cuối cùng, lọc tất cả các khóa có bộ đếm vượt quá (* tổng truy cập 1/200).

Answer 4

Nếu các tệp chỉ bao gồm các mã 16 byte và bạn biết mức độ lớn của từng tệp, bạn có thể tính toán số lượng mã trong mỗi tệp. Sau đó, bạn có thể tìm ngưỡng 0,5% và thực hiện theo bất kỳ đề xuất nào khác để đếm số lần xuất hiện của từng mã, ghi lại từng mã có tần số vượt ngưỡng.

Answer 5

Nội dung của từng tệp có đại diện cho một tập dữ liệu hay không hoặc có một sự ngắt kết nối tùy ý giữa các tệp không? Trong trường hợp thứ hai, và giả định một phân phối khá thường xuyên các mã theo thời gian, bạn có thể làm cho cuộc sống của bạn đơn giản hơn bằng cách chia nhỏ từng tệp thành các phần nhỏ hơn, dễ quản lý hơn. Là một phần thưởng, bạn sẽ nhận được kết quả sơ bộ nhanh hơn và có thể chuyển tiếp vào quy trình tiếp theo trước đó.

Answer 6

Sắp xếp các phần của tệp trong bộ nhớ, như thể bạn đang thực hiện và sắp xếp bên ngoài. Thay vì viết ra tất cả các mã được sắp xếp trong mỗi đoạn, tuy nhiên, bạn chỉ có thể viết từng mã riêng biệt và số lần xuất hiện trong đoạn đó. Cuối cùng, hợp nhất các bản ghi tóm tắt này để tìm số lần xuất hiện của mỗi mã.

Quy trình này chia tỷ lệ cho mọi dữ liệu kích thước và chỉ thực hiện một lần vượt qua dữ liệu đầu vào. Có thể yêu cầu nhiều lần hợp nhất, tùy thuộc vào số lượng tệp tóm tắt bạn muốn mở cùng một lúc.

---

Sắp xếp tệp cho phép bạn đếm số lần xuất hiện của mỗi mã bằng một lượng bộ nhớ cố định, bất kể kích thước đầu vào.

Bạn cũng biết tổng số mã (bằng cách chia kích thước đầu vào theo kích thước mã cố định hoặc bằng cách đếm số lượng mã có độ dài thay đổi trong quá trình sắp xếp trong một vấn đề chung hơn).

Vì vậy, bạn biết tỷ lệ đầu vào được liên kết với mỗi mã.

này về cơ bản là đường ống sort * | uniq -c

Nếu mỗi mã xuất hiện chỉ một lần, đó là không có vấn đề; bạn chỉ cần có thể đếm chúng.