Đếm xác suất bằng Python

Question

Tôi có một tệp txt gồm 50GB chuỗi ngẫu nhiên, trong đó tôi muốn đếm số lần xuất hiện của chuỗi con trong tệp đó .. nhiều lần, cho các số khác nhau không được xác định trước ngẫu nhiên.

Tôi đã tự hỏi liệu có cách nào khác để tiếp cận vấn đề hay không.

cách xác suất

Cái gì đó như một bộ lọc nở, nhưng thay vì kiểm tra xác suất thành viên, chúng tôi có thể có xác suất đếm. Cấu trúc dữ liệu đó sẽ được sử dụng cho các ước tính số đếm.

khác phương pháp thống kê (?)

Bất kỳ phương pháp giả mà tôi có thể sử dụng để ước tính số lần xuất hiện của một chuỗi trong một file văn bản? Mở để lựa chọn thay thế.

Sẽ rất tuyệt nếu nó có thể được thực hiện trong < = thời gian logarit vì tôi sẽ thực hiện cùng một nhiệm vụ rất nhiều lần.

Answer 1

Một số âm thanh streaming algorithms có liên quan đến vấn đề này, riêng biệt hoặc kết hợp với nhau.

1. Lần truyền đầu tiên trên tệp có thể xấp xỉ heavy hitters. Tùy thuộc vào vấn đề của bạn, có thể phân phối của người chơi nặng là đủ cho bạn, nhưng bộ này đủ nhỏ để chứa trong bộ nhớ. Nếu đây là trường hợp, bạn có thể thực hiện một vượt qua thứ hai, chỉ đếm những người nặng ký từ đèo đầu tiên.

2. Cấu trúc dữ liệu count-min sketch có thể thực hiện tính toán gần đúng. Bạn có thể sử dụng cấu trúc dữ liệu này một mình, hoặc bạn có thể sử dụng nó để đếm sự xuất hiện của những người nặng ký.

Vì đây được gắn thẻ như Python:

• StreamLib

• count-min-sketch libraries on PyPI

Answer 2

Bạn có thể tính toán một suffix array cho tập tin của bạn.

Mảng này chứa vị trí bắt đầu của hậu tố theo thứ tự được sắp xếp. Với 50GB văn bản, bạn có thể phân bổ 5 byte cho mỗi vị trí và kết thúc với một mảng hậu tố 5 * 50 = 250 GByte. Nếu điều này là quá nhiều, thì bạn có thể thử một số compressed suffix array.

Việc tính toán mảng này có thể được thực hiện trong O (n) (có thể là một vài giờ với thuật toán thích hợp, chủ yếu bị giới hạn bởi tốc độ đọc/ghi đĩa).

Khi bạn có mảng, bạn có thể đếm số lần xuất hiện của bất kỳ chuỗi con nào trong thời gian logarit. Trong thực tế thời gian sẽ bị chi phối bởi thời gian tìm kiếm đến các phần khác nhau của đĩa của bạn, do đó, phần này sẽ nhanh hơn nhiều nếu bạn lưu trữ các tệp trên ổ đĩa trạng thái rắn.