Làm thế nào để phù hợp với một cây chống lại một tập hợp lớn các mẫu?

Question

Tôi có một bộ ký hiệu vô hạn tiềm tàng: A, B, C, ... Ngoài ra còn có một biểu tượng giữ chỗ đặc biệt riêng biệt ? (ý nghĩa của nó sẽ được giải thích bên dưới).

Xem xét các cây hữu hạn không trống sao cho mỗi nút có biểu tượng gắn với nó và 0 hoặc nhiều cây con không trống. Thứ tự cây con của một nút cụ thể là có ý nghĩa (ví dụ, nếu có một nút có 2 cây con, chúng ta có thể phân biệt cái nào là cái còn lại và cái nào là đúng). Bất kỳ biểu tượng đã cho nào cũng có thể xuất hiện trong cây 0 của nhiều lần gắn với các nút khác nhau. Biểu tượng trình giữ chỗ ? chỉ có thể được gắn vào các nút lá (tức là các nút không có cây con). Nó theo định nghĩa thông thường của một cái cây mà cây cối được chu kỳ.

Yêu cầu về độ mịn có nghĩa là tổng số nút trong cây là số nguyên hữu hạn dương. Sau đó, tổng số ký hiệu đính kèm, độ sâu cây và tổng số nút trong mỗi cây con đều là hữu hạn. Cây được đưa ra trong một ký hiệu chức năng: một nút được biểu thị bằng một biểu tượng gắn liền với nó và, nếu có bất kỳ cây con nào, nó được theo sau bởi dấu ngoặc đơn chứa danh sách cây con được phân cách bằng dấu phẩy được biểu diễn đệ quy trong phần tử cùng một cách. Vì vậy, ví dụ: cây

    A 
       /\ 
        ? B 
        /\ 
        A C 
        /|\ 
        A C Q 
         \ 
         ? 

được biểu thị là A(?,B(A(A,C,Q(?)),C)).

Tôi có bộ cây không thay đổi được tính toán trước S sẽ được sử dụng làm mẫu để khớp. Bộ này thường có ~ 10 cây và mọi phần tử của nó thường có ~ 10-30 nút. Tôi có thể sử dụng nhiều thời gian để tạo trước mọi đại diện của S phù hợp nhất với vấn đề của tôi được nêu bên dưới.

tôi cần phải viết một chức năng chấp nhận một cây T (thường là với ~ 10 nút) và kiểm tra càng nhanh càng tốt nếu T chứa như một cây con bất kỳ yếu tố S, với điều kiện bất kỳ nút nào có ký hiệu giữ chỗ ? khớp với bất kỳ cây con không trống nào (cả khi nó xuất hiện trong T hoặc trong một phần tử của S).

Vui lòng đề xuất cấu trúc dữ liệu để lưu trữ tập hợp S và thuật toán để kiểm tra kết quả phù hợp. Bất kỳ ngôn ngữ lập trình hoặc mã giả là OK.

Answer 1

This paper mô tả một biến thể của Aho–Corasick algorithm, nơi thay vì sử dụng một máy trạng thái hữu hạn (mà thuật toán Aho-Corasick tiêu chuẩn sử dụng cho phù hợp với chuỗi) các thuật toán thay vì sử dụng một automaton kéo xuống cho phù hợp với cây con. Giống như thuật toán kết hợp chuỗi Aho-Corasick, biến thể của chúng chỉ yêu cầu một biến đi qua cây đầu vào để khớp với toàn bộ từ điển của S.

Bài báo khá phức tạp - có thể đáng giá đến contact the author để xem liệu anh ấy có sẵn bất kỳ mã nguồn nào không.

Answer 2

Những gì bạn cần là một máy trạng thái hữu hạn theo dõi tập hợp các kết quả phù hợp bạn có thể có.

Về bản chất, một máy như vậy là kết quả của việc khớp các mẫu với nhau và xác định phần nào của cá nhân mà chúng khớp với nhau. Điều này tương tự như cách các bộ từ vựng sử dụng các cụm từ thông dụng cho các thẻ và soạn chúng thành một FSA lớn có thể khớp với bất kỳ cụm từ thông dụng nào bằng cách xử lý từng ký tự một.

Bạn có thể tìm thấy các tham chiếu đến các phương pháp để thực hiện việc này dưới term rewriting systems.