cấu trúc/thuật toán thu thập chuỗi nhanh nhất để bắt đầu và/hoặc chứa tìm kiếm

Question

Tôi có tình huống sau: Tôi có một bộ sưu tập lớn các chuỗi (cho phép 250.000+) chiều dài trung bình có thể là 30. Những gì tôi phải làm là để làm nhiều tìm kiếm trong số này .. chủ yếu là những người sẽ được của StartsWith và Chứa loại.

Bộ sưu tập là tĩnh khi chạy. Có nghĩa là việc đọc và điền ban đầu của bộ sưu tập lựa chọn chỉ được thực hiện một lần .. do đó hiệu suất của việc xây dựng cơ sở hạ tầng là hoàn toàn không quan trọng. Bộ nhớ cũng không phải là một vấn đề: điều này cũng có nghĩa là tôi không nhớ có hai bộ sưu tập với cùng một dữ liệu trong mỗi bộ nếu cần thiết (như một bộ cho phần bắt đầu và một cho chứa). Chỉ có điều quan trọng là hiệu suất của các tìm kiếm sẽ trả về tất cả các yếu tố phù hợp với điều kiện tìm kiếm.

Để bắt đầu, tôi đã đến Trie hoặc cây Radix .. nhưng có lẽ thậm chí còn có sự lựa chọn tốt hơn?

Đối với chứa .. Tôi không có ý tưởng nào cả (bên cạnh việc chạy truy vấn LINQ trên danh sách sẽ không quá nhanh với lượng dữ liệu đó).

Cảm ơn mọi người trước!

update: Tôi quên một phần quan trọng: với Chứa đựng tôi có nghĩa là không có kết hợp chính xác trong bộ sưu tập .. nhưng tôi muốn tìm tất cả các chuỗi trong bộ sưu tập có chứa searchstring cho

Answer 1

Xây dựng một suffix tree sẽ cho phép bạn thực hiện tìm kiếm chuỗi con trên tất cả các chuỗi của bạn song song trong O(1). Các pedantic trong tôi không thể không lưu ý rằng nó thực sự là O(n + m) nơi n là số chuỗi phù hợp với chuỗi con của bạn và m là kích thước của chuỗi con được truy vấn.

Vậy cây hậu tố bạn yêu cầu là gì? Trong thực hiện cơ bản nhất của nó, nó là một trie với một phương pháp chèn fancier: ngoài việc thêm một chuỗi, nó cũng thêm tất cả các hậu tố có thể có của chuỗi đó vào trie. Trên cấu trúc dữ liệu này, tìm kiếm chuỗi con trở thành tìm kiếm tiền tố của tất cả các hậu tố có thể. Vì bạn cũng muốn thực hiện tìm kiếm tiền tố, bạn sẽ muốn thêm một ký tự đặc biệt ở trước mỗi chuỗi được chèn vào và các phần tử truy vấn. Ký tự đặc biệt sẽ cho phép bạn phân biệt giữa hậu tố và chuỗi đầy đủ.

Trong khi việc thực hiện cây hậu tố này là đơn giản đáng kể, nó cũng rất kém hiệu quả (không gian O(n^2) và thời gian xây dựng). May mắn thay, có những triển khai hiệu quả hơn có thể làm giảm đáng kể không gian và giới hạn thời gian. Một trong những thuật toán này, thuật toán của Ukkonen, được giải thích rất rõ trong this SO answer và mang không gian bị ràng buộc xuống O(n). Bạn cũng có thể muốn xem xét suffix arrays là một đại diện tương đương nhưng hiệu quả hơn về các hậu tố cây.

Mặc dù tôi biết có rất nhiều triển khai cây hậu tố nữa (một trong số đó có thể là điểm nhạy cảm cho trường hợp sử dụng của bạn) Tôi chỉ không biết chúng. Tôi khuyên bạn nên làm một số nghiên cứu về chủ đề này trước khi bạn giải quyết về việc thực hiện.