Tìm kiếm một chuỗi trong luồng đầu vào

Question

Tôi có một tệp nhị phân lớn (nhiều gigabyte, do đó tải nó vào bộ nhớ không phải là một tùy chọn) mà tôi muốn tìm kiếm tất cả các lần xuất hiện của chuỗi "icpf".

Tôi đã thử sử dụng std::search cho điều này, nhưng chỉ bị cắn bởi thực tế là std::search chỉ hoạt động cho các trình vòng lặp chuyển tiếp, không phải trình lặp đầu vào.

Thư viện chuẩn có cung cấp giải pháp thay thế nhanh cho điều này không? Hoặc tôi có cần phải viết mã tìm kiếm (hoặc đọc theo từng khối tại một thời điểm sau đó std::search trên các kết quả đó hoặc ignore mọi thứ cho đến khi 'i' và sau đó kiểm tra thủ công ba ký tự tiếp theo)?

Answer 1

Thư viện chuẩn có cung cấp giải pháp thay thế nhanh không?

Mặc dù thư viện C++ chuẩn cung cấp các cách tìm kiếm luồng văn bản, nó không cung cấp thuật toán so sánh cho luồng nhị phân.

Hoặc tôi cần phải tay mã tìm kiếm (hoặc đọc trong khối tại một thời điểm sau đó std::search trên đó, hoặc bỏ qua tất cả mọi thứ cho đến khi một 'i' và sau đó tự kiểm tra ba nhân vật tiếp theo)?

Việc mã hóa phương pháp "bỏ qua và tìm kiếm" có thể phức tạp, vì dễ dàng mã hóa giải pháp bỏ qua mục nhập. Ví dụ: nếu bạn đang tìm kiếm "icpf" trong tệp có chứa "icpicpf", một chương trình đơn giản xử lý một ký tự cùng một lúc sẽ không tìm thấy hậu tố "icpf" sau khi loại bỏ tiền tố "icpi".

Nếu bạn định tự viết mã này, hãy cân nhắc triển khai Knuth–Morris–Pratt algorithm. Có nhiều triển khai có sẵn trực tuyến và nó hoạt động chính xác trên luồng, bởi vì nó xem xét một nhân vật tại một thời điểm và không bao giờ quay trở lại.

Answer 2

Phương pháp nhanh nhất là tải toàn bộ tệp vào bộ nhớ, sau đó tìm kiếm bộ nhớ.

Cách thay thế tốt nhất tiếp theo là giữ cho ổ đĩa cứng đang chuyển động. Có lẽ có một luồng đọc khối dữ liệu vào một bộ đệm và một luồng khác tìm kiếm bộ đệm.

Đi xuống danh sách, đọc khối dữ liệu lớn vào bộ đệm, sau đó tìm kiếm bộ đệm là một kỹ thuật tốt, mặc dù không hiệu quả như các phương pháp trước.

Bạn có thể đọc từng dòng một, sử dụng std::getline và std::string. Đây không phải là nhanh như đọc khối vì chức năng đầu vào đang tìm kiếm ký tự dòng mới (và phân bổ bộ nhớ trong std::string).

Trường hợp xấu nhất có thể là đọc ký tự theo ký tự. Các chức năng trên không phải là xấu để đọc một ký tự đơn (thường là chi phí là như nhau để đọc một khối lớn dữ liệu).

Không, không có hàm thư viện C++ chuẩn nào để tìm kiếm tệp. Một số hệ điều hành có các tiện ích để tìm kiếm các tập tin; có lẽ bạn có thể sử dụng một trong số đó.

Chỉnh sửa 1:
Nút cổ chai là nhập dữ liệu. Một khi bạn nhận được dữ liệu vào một bộ đệm, sau đó là nhiều thuật toán tìm kiếm hiệu quả hơn là sức mạnh vũ phu (tìm kiếm chữ cái đầu tiên, sau đó tìm kiếm các chữ cái tiếp theo, vv).

Tìm kiếm trên Internet cho "thuật toán tìm kiếm chuỗi".

Answer 3

Tôi không biết về bất kỳ tinh khiết giải pháp thư viện tiêu chuẩn, nhưng hạt nhân đã thực hiện nạp trước, vì vậy nó phải được thể mmap() tập tin để có được những đòi hỏi về phía trước lặp: (Xử lý lỗi bỏ qua)

size_t search(int fd, size_t fileSize) { 
    auto start = reinterpret_cast<char*>(
     ::mmap(nullptr, fileSize, PROT_READ, MAP_PRIVATE | MAP_NORESERVE, fd, 0)); 
    ::madvise(start, fileSize, MADV_SEQUENTIAL); 
    auto pattern = "icpf"; 
    auto offset = std::search(start, start+fileSize, pattern, pattern+4); 
    return offset - start; 
} 

Đó là một bước nhảy vọt nhỏ của đức tin, tin tưởng hạt nhân của bạn để làm việc tải chậm, tìm nạp trước và loại bỏ chính xác. Mặt khác, nếu bạn có thể tin tưởng bất cứ ai với điều này, nó có lẽ sẽ là các nhà phát triển hạt nhân.

Tuyên bố từ chối: Tôi đã không thực sự kiểm tra điều này trên một tệp nhiều gigabyte.