Phân tích

Một tính chất hữu ích của biểu thức chính quy là: một chuỗi khớp với biểu thức khi và chỉ khi nó được một loại máy đặc biệt gọi là ô-tô-mát hữu hạn không đơn định (NFA) chấp nhận.

NFA là một đồ thị gồm các trạng thái và chuyển tiếp, có một trạng thái đầu và một trạng thái cuối đặc biệt. Mỗi chuyển tiếp được gắn nhãn một chữ số hoặc \(\varepsilon\). Khi xử lý chuỗi, máy có thể từ trạng thái hiện tại sang trạng thái khác bằng một chuyển tiếp \(\varepsilon\), hoặc bằng một chuyển tiếp chữ số khớp với chữ số hiện tại của chuỗi rồi tiến sang chữ số kế tiếp. Sau khi đọc chữ số cuối của chuỗi vào, máy chỉ còn được dùng chuyển tiếp \(\varepsilon\). Nếu có một đường đi từ trạng thái đầu đến trạng thái cuối đọc hết đầu vào, ta nói chuỗi được chấp nhận hay được khớp, và đường đi ấy gọi là đường đi chấp nhận.

Xây dựng NFA khớp với các biểu thức chính quy của bài

Phép dựng Thompson là một thuật toán dựng NFA khớp với biểu thức chính quy.

Khung tổng quát bắt đầu bằng hai trạng thái đặc biệt: trạng thái đầu q và trạng thái chấp nhận cuối f. Sau đó dựng NFA \(f(E)\) bằng đệ quy:

• Nếu \(E\) là một chữ số, \(f(E)\) chỉ gồm hai trạng thái đặc biệt nối bằng một chuyển tiếp mang nhãn \(E\).
• \(f(E=E_1E_2)\) là hợp của \(f(E_1)\) và \(f(E_2)\), dùng trạng thái đầu của \(f(E_1)\) làm trạng thái đầu của \(f(E)\), trạng thái cuối của \(f(E_2)\) làm trạng thái cuối, và thêm chuyển tiếp \(\varepsilon\) từ trạng thái cuối của \(f(E_1)\) đến trạng thái đầu của \(f(E_2)\).
• \(f(E=(E_1|E_2|\ldots|E_N))\) là hợp của mọi \(f(E_i)\) cộng thêm một trạng thái đầu và một trạng thái cuối. Thêm các chuyển tiếp \(\varepsilon\) từ trạng thái đầu của \(f(E)\) đến trạng thái đầu của từng \(f(E_i)\) và từ trạng thái cuối của từng \(f(E_i)\) đến trạng thái cuối của \(f(E)\).
• \(f(E=(E_1)*)\) chính là \(f(E_1)\) với một chuyển tiếp \(\varepsilon\) bổ sung từ trạng thái cuối về trạng thái đầu.

Đây là một NFA ví dụ được dựng từ Integeregex (13|1)((2)*|3):

https://cdn.lqdoj.edu.vn/media/pagedown-uploads/pd_1_bfd17a47.png

Kiểm tra một chuỗi đơn lẻ có khớp hay không

Xét ví dụ: chuỗi vào 1322 có một đường đi chấp nhận trong NFA trên qua các trạng thái q, \(s_1,s_2,s_3,s_6,s_7,s_8,s_7,s_8\), f. Lưu ý rằng mỗi chuỗi có thể có nhiều đường đi; một số chấp nhận, số khác không. Chỉ cần một đường đi chấp nhận là chuỗi được chấp nhận.

Bắt đầu với tập trạng thái khả dĩ chỉ chứa trạng thái đầu q. Với mỗi ký tự \(C\) trong chuỗi, từ từng trạng thái khả dĩ trước đó, tìm mọi trạng thái có thể đến bằng một số chuyển tiếp \(\varepsilon\), rồi một chuyển tiếp mang nhãn \(C\); thêm chúng vào tập trạng thái khả dĩ mới. Từ tập cuối cùng, nếu có thể đến trạng thái chấp nhận f bằng các chuyển tiếp \(\varepsilon\) từ bất kỳ trạng thái nào, NFA (và biểu thức chính quy) khớp.

Ví dụ khi kiểm tra chuỗi 1233 với NFA mẫu: NFA bắt đầu tại q. Sau các chuyển tiếp \(\varepsilon\) và một chuyển tiếp trên 1, nó có thể ở \(\{s_2,s_5\}\). Sau các chuyển tiếp \(\varepsilon\) và một chuyển tiếp trên 3, nó có thể ở \(\{s_3,s_{10}\}\). Sau các chuyển tiếp \(\varepsilon\) và một chuyển tiếp trên 2, nó chỉ có thể ở \(s_8\); sau lần tương tự tiếp theo, nó vẫn chỉ có thể ở \(s_8\). Vì có thể đến f từ \(s_8\) bằng các chuyển tiếp \(\varepsilon\), NFA và biểu thức chính quy khớp với 1322.

Đếm nhanh mọi số khớp với NFA

Giờ ta dùng quy hoạch động để đếm nhanh có bao nhiêu số không vượt quá \(X\) khớp với NFA. Ta lưu một ánh xạ từ (is_empty, is_prefix_of_x, possible_states) để ghi nhớ kết quả từ trạng thái đó. is_empty ngăn việc thêm các số 0 ở đầu; is_prefix_of_x ngăn đếm các số lớn hơn \(X\).

def MatchNFA(X, transitions):
  x_digits = []
  for c in str(X):
    x_digits.append(int(c))

  # Start of numbers with same length  as X.
  count_state = { (True, True, 'p') : 1 }
  for index in range(len(X)):
    # Start of shorter and shorter numbers.
    new_count_state = { (True, False, 'p') : 1 }

    for (is_empty, is_prefix_of_x, states), count in count_state.items():
      for new_digit in range(10):
        if is_empty and new_digit == 0:
          continue # Numbers can't start with 0.

        if is_prefix_of_x and new_digit > x_digits[index]:
          continue # Numbers can't be greater than X.

        # Find all possible states if new_digit was next in the string
        new_possible_states = []
        for start_state in states:
          # Add all states that can be reached from start_state by (ε)* new_digit
          for epsilon_state in transitions[start_state]['']:
            new_possible_states += transitions[epsilon_state][new_digit]
        new_count_state[(False, is_prefix_of_x and new_digit == x_digits[index],
                         set(new_possible_states))] += count
    count_state = new_count_state

  count_match = 0
  for (is_prefix_of_x, states), count in count_state.items():
    for final_state in states:
      if 'f' in transitions[state]['']
        count_match += count

  return count_match

Cuối cùng, số giá trị khớp trong đoạn \([A,B]\) là MatchNFA(B, transitions) - MatchNFA(A-1, transitions).

Khi số trạng thái trong NFA tăng, new_possible_states có thể tăng theo hàm mũ (về lý thuyết có thể là tập lũy thừa của tập trạng thái). Tuy nhiên, độ dài tối đa nhỏ của biểu thức chính quy, cùng số ký tự không phải chữ số cần dùng để chứa phép tuyển hay phép lặp, khiến số lượng thực tế vẫn rất nhỏ đối với máy tính. Có những cận có thể chứng minh toán học, nhưng các chứng minh quá dài để nằm vừa trong lề của bài phân tích này.

Nguồn

Bản dịch dựa trên phân tích chính thức Google Code Jam 2016 - World Finals - Integeregex, kho Google Coding Competitions (Apache-2.0).