Cách nhanh nhất để tìm tất cả các lần xuất hiện của chuỗi con là gì?

Question

Điều này hoàn toàn nằm ngoài sự tò mò. Tôi đã duyệt qua một bài báo so sánh các thuật toán tìm kiếm chuỗi khác nhau và nhận thấy rằng tất cả chúng đều được thiết kế để tìm chuỗi con phù hợp đầu tiên. Điều này khiến tôi suy nghĩ ... Nếu tôi muốn tìm tất cả các lần xuất hiện của một chuỗi con? Tôi chắc chắn rằng tôi có thể tạo ra một vòng lặp sử dụng một biến thể của KMP hoặc BM và đổ mỗi lần xuất hiện vào một mảng nhưng điều này hầu như không có vẻ như nó sẽ là nhanh nhất.

Không phải thuật toán phân chia và chinh phục cao hơn? Ví dụ:

Ví dụ: cho phép bạn tìm chuỗi "abc" trong chuỗi "abbcacabbcabcacbccbabc".

1. Khi vượt qua đầu tiên tìm tất cả các lần xuất hiện của ký tự đầu tiên và lưu trữ vị trí của chúng.
2. Trên mỗi đèo bổ sung, sử dụng các vị trí từ vượt qua trước đó để tìm tất cả các lần xuất hiện của ký tự tiếp theo, giảm các ứng cử viên cho lần vượt tiếp theo với mỗi lần lặp.

Xem xét sự dễ dàng mà tôi nghĩ ra ý tưởng này Tôi giả sử một người nào đó đã nghĩ ra và cải thiện nó cách đây 30 năm.

Answer 1

Không có đơn "Cách nhanh nhất" nó phụ thuộc vào

A) Cái chuỗi thực sự là xây dựng của (chiều dài, phân phối vật, ...)

B) Trên đó phần cứng này chạy

C) Nếu bạn muốn tất cả kết quả song song hoặc tuần tự

D) các thông số khác (ví dụ như có thể tìm thấy các yếu tố trùng nhau, bạn đang tìm kiếm một lần hoặc nhiều lần)

E) Nếu bạn thấy việc triển khai này cụ thể hoặc chỉ là học tập. Trong triển khai, có rất nhiều cách bổ sung để tối ưu hóa nội dung. Ví dụ. lưu trữ tạm thời (như trong đề xuất của bạn) thường rất tốn kém.

Ý tưởng bạn có, ví dụ: sẽ hoàn toàn làm hỏng bất kỳ bộ nhớ cache CPU nào cho các chuỗi dài. Vì vậy, nó sẽ là rất chậm trong những trường hợp.

Answer 2

Xem Suffix array

Applications

Mảng hậu tố của một chuỗi có thể được sử dụng như một chỉ số để xác định vị trí một cách nhanh chóng mỗi lần xuất hiện của một chuỗi con trong chuỗi. Tìm mọi sự cố xảy ra của chuỗi con tương đương với tìm mọi hậu tố bắt đầu bằng chuỗi con. Nhờ thứ tự từ điển, các hậu tố này sẽ được nhóm lại với nhau trong mảng hậu tố và có thể được tìm thấy hiệu quả với tìm kiếm nhị phân. Nếu được triển khai đơn giản, việc tìm kiếm nhị phân sẽ mất thời gian O (mlogn), trong đó m là chiều dài của chuỗi con .Để tránh làm lại việc so sánh , cấu trúc dữ liệu bổ sung cung cấp thông tin về dài nhất tiền tố chung (LCP) của hậu tố là được xây dựng, cho phép tìm kiếm O (m + logn) .

Answer 3

Nếu bạn chỉ xử lý chuỗi đã cho một lần, mảng hậu tố quá mức cần thiết. Phải mất thời gian O (n log n) để tạo, vì vậy thuật toán kiểu KMP sẽ đánh bại nó. Hơn nữa, nếu chuỗi của bạn là rất lớn, hoặc bạn muốn nhận được kết quả trong thời gian thực khi bạn nhận được chuỗi, mảng hậu tố sẽ không hoạt động. Có thể sửa đổi thuật toán KMP để tiếp tục sau khi nó tìm thấy một kết quả phù hợp mà không cần dùng thêm bộ nhớ, ngoài bộ nhớ được sử dụng để lưu trữ các kết quả phù hợp (cũng có thể không cần thiết, nếu bạn chỉ đơn giản là in ra phù hợp hoặc xử lý chúng khi bạn đi cùng). Khi bắt đầu, hãy lấy số Wikipedia implementation và sửa đổi câu lệnh "return m" thành "thêm m vào danh sách chỉ mục". Nhưng bạn chưa làm xong. Bạn cũng cần phải tự hỏi mình, bạn có cho phép sự trùng lặp xảy ra không? Ví dụ, nếu chuỗi con của bạn là "abab" và bạn đang tìm kiếm trong chuỗi chính "abababab", có hai lần xuất hiện hay ba? Trong ví dụ tôi đưa ra ("như là một sự khởi đầu"), bạn có thể đặt lại i thành 0 để trả lời "hai" hoặc bạn có thể rơi vào trường hợp "khác" sau "thêm m" để cung cấp cho "ba" " câu trả lời.

Answer 4

Cả KMP và BM đều có thể dễ dàng được sử dụng để tìm nhiều kết quả phù hợp. Tôi cũng khuyên bạn nên sử dụng Rabin-Karp, IMHO dễ hiểu hơn nhưng không thực sự nhanh cho nhiều kết quả phù hợp (O (n + k * m) mà tôi nghĩ, trong đó n là độ dài của văn bản, m là chiều dài của mẫu và k là số lần xuất hiện). Nhưng nó rất dễ dàng để sửa đổi cho cả hai trùng lặp và không chồng chéo trận đấu.

Nó cũng có thể được thực hiện bằng cách sử dụng hậu tố cây/hậu tố mảng, nhưng họ khó mã và không thực sự mua cho bạn bất kỳ tăng tốc độ.