Sự phức tạp về thuật toán của các trình phân tích cú pháp/trình xác nhận hợp lệ XML

Question

Tôi cần biết hiệu suất của các công cụ XML khác nhau như thế nào (các trình phân tích cú pháp, trình xác nhận hợp lệ, các bộ đánh giá biểu thức XPath) bị ảnh hưởng bởi kích thước và độ phức tạp của tài liệu đầu vào. Có những tài nguyên ngoài kia ghi lại cách thời gian CPU và mức sử dụng bộ nhớ bị ảnh hưởng bởi ... à, cái gì? Kích thước tài liệu bằng byte? Số lượng nút? Và mối quan hệ tuyến tính, đa thức hay tệ hơn?

Cập nhật

Trong một bài báo trên tạp chí IEEE Computer, vol 41 nr 9, tháng 9 năm 2008, các tác giả khảo sát bốn mô hình phân tích cú pháp XML phổ biến (DOM, SAX, Stax và VTD). Họ chạy một số thử nghiệm hiệu năng cơ bản cho thấy rằng trình phân tích cú pháp DOM sẽ có thông lượng giảm một nửa khi kích thước của tệp đầu vào được tăng từ 1-15 KB lên 1-15 MB hoặc lớn hơn khoảng 1000x. Thông lượng của các mô hình khác không bị ảnh hưởng đáng kể.

Thật không may là họ không thực hiện các nghiên cứu chi tiết hơn, chẳng hạn như sử dụng thông lượng/bộ nhớ làm chức năng của số lượng nút/kích thước.

Bài báo là here.

Cập nhật

tôi đã không thể tìm thấy bất kỳ điều trị chính thống của vấn đề này. Đối với những gì nó có giá trị, tôi đã thực hiện một số thí nghiệm đo số lượng các nút trong một tài liệu XML như một hàm của kích thước của tài liệu theo byte. Tôi đang làm việc trên một hệ thống quản lý kho và các tài liệu XML là các tài liệu kho điển hình, ví dụ: Thông báo vận chuyển nâng cao, vv

Biểu đồ dưới đây cho thấy mối quan hệ giữa kích thước tính theo byte và số nút (tỷ lệ thuận với khoảng trống bộ nhớ của tài liệu trong mô hình DOM). Các màu khác nhau tương ứng với các loại tài liệu khác nhau. Thang đo là log/log. Đường màu đen phù hợp nhất với các điểm màu xanh lam. Thật thú vị khi lưu ý rằng đối với tất cả các loại tài liệu, mối quan hệ giữa kích thước byte và kích thước nút là tuyến tính, nhưng hệ số tỷ lệ có thể rất khác nhau.

Answer 1

Nếu tôi đã phải đối mặt với vấn đề đó và không thể tìm thấy bất cứ điều gì trên google có lẽ tôi sẽ cố gắng để làm điều đó bản thân tôi.

Một số công cụ "back-of-an-evelope" để có cảm nhận về nơi nó đang diễn ra. Nhưng nó sẽ kinda cần tôi để có một ý tưởng về làm thế nào để làm một phân tích cú pháp xml. Đối với tiêu chuẩn không algorithmical hãy xem ở đây:

• http://www.xml.com/pub/a/Benchmark/exec.html
• http://www.devx.com/xml/Article/16922
• http://xerces.apache.org/xerces2-j/faq-performance.html

Answer 2

Tôi nghĩ rằng có quá nhiều biến có liên quan để đưa ra một phức tạp đơn giản metric trừ khi bạn thực hiện rất nhiều giả định.

Trình phân tích cú pháp kiểu SAX đơn giản phải là tuyến tính theo kích thước tài liệu và bằng phẳng cho bộ nhớ.

Một cái gì đó giống như XPath sẽ không thể mô tả trong điều khoản của chỉ là tài liệu đầu vào kể từ khi sự phức tạp của biểu thức XPath đóng một vai trò rất lớn.Tương tự như vậy để xác nhận lược đồ, một lược đồ lớn nhưng đơn giản có thể là tuyến tính, trong khi lược đồ nhỏ hơn có cấu trúc phức tạp hơn nhiều sẽ hiển thị hiệu năng thời gian chạy tồi tệ hơn.

Như với hầu hết các câu hỏi về hiệu suất, cách duy nhất để có được câu trả lời chính xác là đo lường và xem điều gì xảy ra!

Answer 3

Rob Walker đúng: vấn đề không được chỉ định đầy đủ chi tiết. Chỉ xem xét các trình phân tích cú pháp (và bỏ qua câu hỏi liệu chúng có thực hiện xác thực), có hai hương vị chính: dựa trên cây — suy nghĩ DOM — và luồng/sự kiện dựa trên — nghĩ rằng SAX (đẩy) và StAX (kéo). Nói theo các tổng quát lớn, các phương pháp dựa trên cây tiêu thụ nhiều bộ nhớ hơn và chậm hơn (vì bạn cần hoàn thành phân tích cú pháp toàn bộ tài liệu), trong khi các phương pháp dựa trên sự kiện trực tuyến tiêu thụ ít bộ nhớ hơn và nhanh hơn. Các trình phân tích cú pháp dựa trên cây thường được coi là dễ sử dụng hơn, mặc dù StAX đã được báo trước là một cải tiến lớn (dễ sử dụng) trên SAX.

Answer 4

Tôi dự định tải các tệp XML cực lớn trong ứng dụng của mình. Tôi đã đặt câu hỏi ở đây trên Stack Overflow: Fastest Possible XML handling for very large documents.

Và có, đó là phần phân tích cú pháp, đó là nút cổ chai.

Tôi đã hoàn toàn không sử dụng trình phân tích cú pháp XML. Thay vào đó, tôi phân tích từng ký tự một cách hiệu quả nhất có thể để tối ưu hóa tốc độ. Điều này dẫn đến tốc độ 40 MB mỗi giây trên PC Windows 3 GHz cho việc đọc, phân tích cú pháp và tải cấu trúc dữ liệu nội bộ.

Tôi rất muốn nghe các phương thức phân tích cú pháp XML khác nhau như thế nào.