Tối ưu hóa việc xây dựng một trie trên tất cả các chất nền

Question

Tôi đang giải quyết một vấn đề liên quan đến trie. Có một tập hợp các chuỗi S. Tôi phải tạo một trie trên tất cả các chất nền cho mỗi chuỗi trong S. Tôi đang sử dụng các thói quen sau đây:

String strings[] = { ... }; // array containing all strings 
for(int i = 0; i < strings.length; i++) { 
    String w = strings[i]; 
    for (int j = 0; j < w.length(); j++) { 
     for (int k = j + 1; k <= w.length(); k++) { 
      trie.insert(w.substring(j, k)); 
     } 
    } 
} 

Tôi đang sử dụng Trie thực hiện cung cấp here. Tuy nhiên, tôi tự hỏi nếu có một số tối ưu hóa có thể được thực hiện để giảm sự phức tạp của việc tạo ra trie trên tất cả các chất nền?

Tại sao tôi cần điều này? Bởi vì tôi đang cố gắng giải quyết this problem.

Answer 1

Bạn có thể xem xét việc tối ưu hóa sau đây:

• Duy trì danh sách các chuỗi con xử lý. Trong khi chèn một chuỗi con, hãy kiểm tra xem tập hợp đã xử lý có chứa chuỗi con cụ thể đó và nếu có, bỏ qua chèn chuỗi con đó vào trie.

Tuy nhiên, trường hợp phức tạp tồi tệ nhất để chèn tất cả các phần tử trong trie sẽ là thứ tự của n^2 trong đó n là kích thước của mảng chuỗi. Từ trang vấn đề, điều này làm việc ra được thứ tự của 10^8 hoạt động chèn trong trie. Do đó, ngay cả khi mỗi lần chèn có 10 hoạt động trên mức trung bình, bạn sẽ có tổng cộng 10^9 hoạt động trong đó đặt bạn vượt quá giới hạn thời gian.

Trang sự cố đề cập đến mảng LCP làm chủ đề liên quan cho sự cố. Bạn nên xem xét thay đổi trong cách tiếp cận.

Answer 2

Nếu chúng tôi có N từ, mỗi từ có độ dài tối đa L, thuật toán của bạn sẽ mất O(N*L^3) (giả sử thêm vào trie là tuyến tính có chiều dài thêm từ). Tuy nhiên, kích thước của số lượng trie (số lượng nút) tối đa là O(N*L^2), vì vậy có vẻ như bạn đang lãng phí thời gian và bạn có thể làm tốt hơn.

Và thực sự bạn có thể, nhưng bạn phải kéo một vài thủ thuật từ tay áo. Ngoài ra, bạn sẽ không còn cần trie.

1. .substring() trong thời gian liên tục

Trong Java 7, mỗi String đã có một mảng ủng hộ char[] cũng như vị trí bắt đầu và thời gian. Điều này cho phép phương thức .substring() chạy trong thời gian không đổi, vì String là lớp không thay đổi. Đối tượng String mới với cùng sự ủng hộ char[] mảng đã được tạo, chỉ với vị trí bắt đầu và độ dài khác nhau.

Bạn sẽ cần phải mở rộng này một chút, để hỗ trợ thêm ở cuối chuỗi, bằng cách tăng độ dài. Luôn tạo một đối tượng chuỗi mới, nhưng để lại mảng sao lưu giống nhau.

2. Tính toán lại băm trong thời gian liên tục sau khi gắn thêm ký tự đơn

Một lần nữa, hãy để tôi sử dụng hashCode() chức năng của Java cho String:

int hash = 0; 
for (int i = 0; i < data.length; i++) { 
    hash = 31 * hash + data[i]; 
} // data is the backing array 

Bây giờ, làm thế nào sẽ thay đổi băm sau khi thêm một ký tự đơn ở cuối từ? Dễ dàng, chỉ cần thêm giá trị của nó (mã ASCII) nhân với 31^length. Bạn có thể giữ quyền hạn của 31 trong một số bảng riêng biệt, các số nguyên tố khác có thể được sử dụng là tốt.

3. Lưu trữ tất cả các chuỗi con trong đơn HashMap

Với việc sử dụng thủ đoạn 1 và 2, bạn có thể tạo ra tất cả các chuỗi con trong thời gian O(N*L^2), mà là tổng số của chuỗi con. Chỉ cần luôn bắt đầu bằng chuỗi có độ dài một và thêm một ký tự cùng một lúc. Đặt tất cả các chuỗi của bạn vào một HashMap duy nhất, để giảm các bản sao.

(Bạn có thể bỏ 2 và 3 và loại bỏ duplicities khi/sau khi phân loại, có lẽ nó sẽ còn nhanh hơn.)

4. Sắp xếp chuỗi con của bạn và bạn tốt để đi.

Vâng, khi tôi đã đến điểm 4, tôi nhận ra kế hoạch của tôi sẽ không làm việc, vì trong phân loại bạn cần phải so sánh chuỗi, và có thể mất thời gian O(L). Tôi đã đưa ra nhiều nỗ lực để giải quyết nó, trong đó có xô phân loại, nhưng không ai sẽ là nhanh hơn so với ban đầu O(N*L^3)

tôi sẽ chỉ trả lời ở đây trong trường hợp nó truyền cảm hứng cho một ai đó.

---

Trong trường hợp bạn không biết Aho-Corasic algorithm, hãy nhìn vào đó, nó có thể có một số sử dụng cho vấn đề của bạn.

Answer 3

Điều bạn cần có thể là suffix automaton. Nó chỉ tốn O (n) thời gian và có thể nhận ra tất cả các chất nền.

Suffix array cũng có thể giải quyết vấn đề này.

Hai thuật toán này có thể giải quyết hầu hết các vấn đề về chuỗi và chúng thực sự khó học. Sau khi bạn học những người đó bạn sẽ giải quyết nó.

Answer 4

Trước tiên, hãy lưu ý rằng chỉ đủ hậu tố cho trie và các nút cho mỗi chuỗi con sẽ được thêm vào dọc theo đường.

Thứ hai, bạn phải compress the trie, nếu không nó sẽ không phù hợp với giới hạn bộ nhớ do HackerRank áp đặt. Ngoài ra điều này sẽ làm cho giải pháp của bạn nhanh hơn.

Tôi vừa gửi giải pháp của mình triển khai các đề xuất này và nó was accepted. (thời gian thực hiện tối đa là 0,08 giây.)

Nhưng bạn có thể làm cho giải pháp của mình thậm chí nhanh hơn bằng cách triển khai thuật toán thời gian tuyến tính để xây dựng suffix tree. Bạn có thể đọc về thuật toán xây dựng cây hậu tố thời gian tuyến tính here và here.Ngoài ra còn có một giải thích về thuật toán của Ukkonen trên StackOverflow here.