Thuật toán này có tuyến tính không?

Question

Lấy cảm hứng từ hai câu hỏi sau: String manipulation: calculate the "similarity of a string with its suffixes" và Program execution varies as the I/P size increases beyond 5 in C, tôi đã đưa ra thuật toán dưới đây.

Các câu hỏi này sẽ được

1. Là nó đúng, hoặc tôi đã thực hiện một sai lầm trong lập luận của tôi?
2. Trường hợp phức tạp nhất của thuật toán là gì?

Một chút ngữ cảnh trước tiên. Đối với hai chuỗi, hãy xác định sự giống nhau của chúng như độ dài của tiền tố chung dài nhất của hai chuỗi. Tổng số tự tương tự của một chuỗi s là tổng của các điểm tương đồng của s với tất cả các hậu tố của nó. Ví dụ: tổng số tự tương tự của abacab là 6 + 0 + 1 + 0 + 2 + 0 = 9 và tổng số tự tương tự của a lặp lại n lần là n*(n+1)/2.

Mô tả của thuật toán: Thuật toán được dựa trên chuỗi Knuth-Morris-Pratt tìm kiếm thuật toán, trong đó các biên giới các tiền tố của chuỗi đóng vai trò trung tâm.

Để tóm tắc: a biên giới của một chuỗi s là một chuỗi thích hợp b của s đó là đồng thời một tiền tố và hậu tố của s.

Ghi chú: Nếu b và c là biên giới của s với b ngắn hơn c, sau đó b cũng là một biên giới c, và ngược lại, mỗi biên giới c cũng là một đường viền của s.

Hãy s là một chuỗi có độ dài n và p là một tiền tố của s với chiều dài i. Chúng tôi gọi một biên giới b với chiều rộng k của pkhông mở rộng nếu một trong hai i == n hoặc s[i] != s[k], nếu không nó có thể mở rộng (chiều dài k+1 tiền tố của s là sau đó một biên giới dài i+1 tiền tố của s).

Bây giờ, nếu tiền tố chung dài nhất của s và hậu tố bắt đầu với s[i], i > 0, có chiều dài k, chiều dài k tiền tố của s là một biên giới không thể mở rộng chiều dài i + k tiền tố của s. Đó là một đường viền vì đó là tiền tố chung của s và s[i .. n-1] và nếu nó có thể mở rộng, nó sẽ không phải là tiền tố chung dài nhất.

Ngược lại, mỗi biên giới không thể mở rộng (chiều dài k) chiều dài i tiền tố của s là tiền tố chung dài nhất của s và hậu tố bắt đầu với s[i-k].

Vì vậy, chúng ta có thể tính toán tổng số tự giống nhau của s bằng cách tổng hợp các độ dài của tất cả các biên giới không thể mở rộng chiều dài i tiền tố của s, 1 <= i <= n. Để làm điều đó

1. Tính chiều rộng của đường viền rộng nhất của tiền tố theo bước tiền xử lý chuẩn KMP.
2. Tính chiều rộng của đường viền không thể mở rộng rộng nhất của tiền tố.
3. Đối với mỗi i, 1 <= i <= n, nếu p = s[0 .. i-1] có một biên giới không trống không thể mở rộng, chúng ta hãy b là rộng nhất trong số này, thêm chiều rộng của b và cho tất cả biên giới không rỗng c của b, nếu đó là đường viền không thể mở rộng của p, hãy thêm chiều dài của nó.
4. Thêm chiều dài n của s, vì điều đó không được đề cập ở trên.

Mã (C):

#include <stdlib.h> 
#include <stdio.h> 
#include <string.h> 

/* 
* Overflow and NULL checks omitted to not clutter the algorithm. 
*/ 

int similarity(char *text){ 
    int *borders, *ne_borders, len = strlen(text), i, j, sim; 
    borders = malloc((len+1)*sizeof(*borders)); 
    ne_borders = malloc((len+1)*sizeof(*ne_borders)); 
    i = 0; 
    j = -1; 
    borders[i] = j; 
    ne_borders[i] = j; 
    /* 
    * Find the length of the widest borders of prefixes of text, 
    * standard KMP way, O(len). 
    */ 
    while(i < len){ 
     while(j >= 0 && text[i] != text[j]){ 
      j = borders[j]; 
     } 
     ++i, ++j; 
     borders[i] = j; 
    } 
    /* 
    * For each prefix, find the length of its widest non-extensible 
    * border, this part is also O(len). 
    */ 
    for(i = 1; i <= len; ++i){ 
     j = borders[i]; 
     /* 
     * If the widest border of the i-prefix has width j and is 
     * extensible (text[i] == text[j]), the widest non-extensible 
     * border of the i-prefix is the widest non-extensible border 
     * of the j-prefix. 
     */ 
     if (text[i] == text[j]){ 
      j = ne_borders[j]; 
     } 
     ne_borders[i] = j; 
    } 
    /* The longest common prefix of text and text is text. */ 
    sim = len; 
    for(i = len; i > 0; --i){ 
     /* 
     * If a longest common prefix of text and one of its suffixes 
     * ends right before text[i], it is a non-extensible border of 
     * the i-prefix of text, and conversely, every non-extensible 
     * border of the i-prefix is a longest common prefix of text 
     * and one of its suffixes. 
     * 
     * So, if the i-prefix has any non-extensible border, we must 
     * sum the lengths of all these. Starting from the widest 
     * non-extensible border, we must check all of its non-empty 
     * borders for extendibility. 
     * 
     * Can this introduce nonlinearity? How many extensible borders 
     * shorter than the widest non-extensible border can a prefix have? 
     */ 
     if ((j = ne_borders[i]) > 0){ 
      sim += j; 
      while(j > 0){ 
       j = borders[j]; 
       if (text[i] != text[j]){ 
        sim += j; 
       } 
      } 
     } 
    } 
    free(borders); 
    free(ne_borders); 
    return sim; 
} 


/* The naive algorithm for comparison */ 
int common_prefix(char *text, char *suffix){ 
    int c = 0; 
    while(*suffix && *suffix++ == *text++) ++c; 
    return c; 
} 

int naive_similarity(char *text){ 
    int len = (int)strlen(text); 
    int i, sim = 0; 
    for(i = 0; i < len; ++i){ 
     sim += common_prefix(text,text+i); 
    } 
    return sim; 
} 

int main(int argc, char *argv[]){ 
    int i; 
    for(i = 1; i < argc; ++i){ 
     printf("%d\n",similarity(argv[i])); 
    } 
    for(i = 1; i < argc; ++i){ 
     printf("%d\n",naive_similarity(argv[i])); 
    } 
    return EXIT_SUCCESS; 
} 

Vì vậy, đây là đúng? Tôi sẽ khá ngạc nhiên nếu không, nhưng tôi đã sai trước đây.

Trường hợp phức tạp nhất của thuật toán là gì?

Tôi nghĩ rằng đó là O (n), nhưng tôi chưa tìm thấy bằng chứng rằng số lượng biên giới có thể mở rộng mà tiền tố có thể chứa trong biên giới không thể mở rộng nhất của nó bị giới hạn (hoặc đúng hơn là tổng số những lần xuất hiện như vậy là O (n)).

Tôi quan tâm nhiều nhất đến giới hạn rõ ràng, nhưng nếu bạn có thể chứng minh được điều đó, ví dụ: O (n * log n) hoặc O (n^(1 + x)) cho số x nhỏ, điều đó đã tốt. (Rõ ràng là ở bậc hai bậc nhất, vì vậy câu trả lời của "It's O (n^2)" chỉ thú vị nếu đi kèm với một ví dụ cho hành vi bậc hai hoặc gần bậc hai.)

Answer 1

Điều này trông giống như một ý tưởng thực sự gọn gàng, nhưng thật đáng buồn tôi tin rằng hành vi xấu nhất là O (n^2).

Đây là nỗ lực của tôi tại một ví dụ. (Tôi không phải là nhà toán học vì vậy hãy tha thứ cho tôi sử dụng Python thay vì phương trình để thể hiện ý tưởng của tôi!)

Hãy xem xét các chuỗi với 4K + 1 ký tự

s = 'a'*K+'X'+'a'*3*K 

này sẽ có

borders[1:] = range(K)*2+[K]*(2*K+1) 

ne_borders[1:] = [-1]*(K-1)+[K-1]+[-1]*K+[K]*(2*K+1) 

Lưu ý rằng:

1) ne_borders [i] sẽ bằng K cho (2K + 1) giá trị của i.

2) 0 < = j < = K, đường viền [j] = j-1

3) vòng lặp cuối cùng trong thuật toán của bạn sẽ đi vào vòng trong với j == K cho 2K + 1 giá trị của i

4) vòng lặp bên trong sẽ lặp K lần để giảm j đến 0

5) Điều này dẫn đến các thuật toán cần nhiều hơn N * N/8 hoạt động để làm một chuỗi trường hợp xấu nhất có chiều dài N .

Ví dụ, đối với K = 4, nó đi vòng vòng bên trong 39 lần

s = 'aaaaXaaaaaaaaaaaa' 
borders[1:] = [0, 1, 2, 3, 0, 1, 2, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4] 
ne_borders[1:] = [-1, -1, -1, 3, -1, -1, -1, -1, 4, 4, 4, 4, 4, 4, 4, 4, 4] 

Đối với K = 2,248 nó đi vòng vòng trong 10,111,503 lần!

Có lẽ có cách để sửa thuật toán cho trường hợp này?

Answer 2

Bạn có thể muốn có một cái nhìn tại Z-thuật toán, đó là provably tuyến tính:

s là một C-string có chiều dài N

Z[0] = N; 
int a = 0, b = 0; 
for (int i = 1; i < N; ++i) 
{ 
    int k = i < b ? min(b - i, Z[i - a]) : 0; 
    while (i + k < N && s[i + k] == s[k]) ++k; 
    Z[i] = k; 
    if (i + k > b) { a = i; b = i + k; } 
} 

Bây giờ giống nhau chỉ là tổng của mục của Z.