Luận văn Công nghệ nén delta ứng dụng trong cập nhật phần mềm tại ngân hàng công thương Việt Nam

ng thứ tự trong cả fold và fnew. Để giải quyết vấn đề đó, người ta đưa ra một thuật toán là thuật toán chỉnh sửa một bước. Thuật toán sử dụng một buffer chứa tất cả các bản sao của yêu cầu, và thực hiện sự chỉnh sửa trên các yêu cầu này sau khi sự phù hợp tốt nhất được tìm thấy. Có 2 loại chỉnh sửa có thể làm. Chỉnh sửa đuôi (tail correction) được thực hiện sau khi insert 1 bản copy yêu cầu từ một phần chưa mã hoá trước đó của fold. Thuật toán cố gắng để mở rộng xâu phù hợp về phía sau trong cả fold và fnew . Nếu sự phù hợp như vậy được tìm thấy theo hướng giật lùi, có một khả năng cho việc thay thế lệnh copy trước đó bằng cách tích hợp chúng vào lệnh copy hiện thời. Loại chỉnh sửa thứ 2 là chỉnh sửa chung, có thể thực hiện khi 1 xâu con phù hợp M được tìm thấy trong phần đã mã hoá của fnew. Trong trường hợp này, thuật toán sẽ cố gắng để xác định xem đoạn mã hoá trước đó của M có thể đã được nén rồi hay chưa và vì thế M có thể được mã hoá bởi một lệnh copy đơn. Hơn nữa, để giới hạn tiêu tốn không gian chứa các xâu con, chúng ta sử dụng một kỹ thuật gọi là kiểm tra điểm. Kỹ thuật này sẽ đảm bảo một xâu con đã được insert vào bảng băm sao cho vùng vị trí nhỏ nhưng việc lựa chọn số phải thật cẩn thận. Kết quả của sự mở rộng này là kỹ thuật nén delta đảm bảo được cả các yêu cầu về không gian và thời gian, có thể làm việc với kích thước file bất kỳ. 2.5.2 Chọn file tham chiếu Trong một vài ứng dụng, sự thi hành của nén delta phụ thuộc lớn vào việc lựa chọn file tham chiếu phù hợp. Chẳng hạn, để nén một tập các file liên quan, chúng ta cần chọn cho mỗi file một hoặc nhiều file tham chiếu có sự giống nhau với nó; mỗi file tham chiếu tự nó cũng có thể nén theo cách này. Trong trường hợp có 1 file tham chiếu cho mỗi file nén, vấn đề này trở thành tìm một nhánh tốt hơn trong đồ thị tương ứng trực tiếp, trong đó, mỗi cạnh (i,j) có trọng số bằng kích thước của delta với i tương ứng với file tham chiếu j. Trong một số tài liệu, vấn đề này có thể giải quyết theo hướng bình phương của thời gian, tuy nhiên lại mắc phải 2 hạn chế: Đầu tiên, giải pháp có thể chứa một chuỗi các tài liệu rất dài cần phải truy nhập nếu muốn giải 41 nén một file cụ thể nào đó. Thứ hai, với một bộ sưu tập lớn, bình phương thời gian trở thành khó chấp nhận, nhất là vấn đề giá trong việc tính trọng số thích hợp của đồ thị trực tiếp. Nếu chúng ta áp độ dài cao hơn đối với chuỗi tham chiếu, sau đó tìm giải pháp tốt hơn thì sẽ trở thành thuật toán NP Complete. Nếu chúng ta cho phép mỗi file được nén sử dụng hơn 1 file tham chiếu, thì vấn đề này có thể được giảm tới 1 nhánh đồ thị tối ưu, như được chỉ ra trong thuật toán NP Complete thậm chí không có giới hạn độ dài của xâu. Một ví dụ của chuỗi tham chiếu dài là khi giải quyết với các phiên bản khác nhau của cùng 1 file, như một hệ thống điều khiển xem xét lại chẳng hạn. Trong trường hợp này, việc lựa chọn file tham chiếu nhằm cực tiểu hoá dữ liệu là hiển nhiên, nhưng sự lựa chọn này có thể phải yêu cầu đến những phiên bản rất cũ và do đó sẽ khá đắt. Rất nhiều kỹ thuật đã được đề xuất để giải quyết vấn đề này bằng cách tạo ra một số giới hạn các short cut tới các phiên bản cũ hơn. 2.5.3 Đồng bộ các file từ xa Trong phần này, chúng ta tập trung vào vấn đề đồng bộ các file ở xa, trong trường hợp khi server không có quyền truy nhập tới file tham chiếu. Những thuật toán đã biết đối với vấn đề này có khác biệt so với bộ nén delta. Chúng ta sẽ bàn về 2 hướng nghiên cứu chính: (1) hướng nghiên cứu dựa trên chuỗi dấu vân tay được thực hiện theo thuật toán rsync tuy nó không đạt được giới hạn tối ưu nào, và (2) dựa trên việc tô màu đồ thị, hướng này đạt được sự thi hành tối ưu dưới các mô hình hiện thời cho khoảng cách file, nhưng dường như nó không phù hợp trong thực tế. Chúng ta cũng sẽ bàn về các vấn đề liên quan trong việc đánh giá sự tương đồng của file và cách điều hoà tập các bản ghi trong một database. 2.5.3.1 Thuật toán rsync Chúng ta sẽ mô tả về thuật toán đồng bộ file được triển khai rộng rãi rsync của Tridgell và MacKerras. Một hướng nghiên cứu tương tự cũng được thực hiện bởi Pyne[7]. Giả sử ta có 1 cuộc giao tiếp giữa 2 bên thông qua điện thoại, mỗi bên có 1 bản copy của một cuốn sách. Bây giờ, giả sử 2 bản copy có thể khác nhau ở một vài chỗ nào đó. Bằng cách nào chúng ta có thể tìm ra 2 cuốn sách có giống nhau hay không, và nếu không thì chúng khác nhau ở chỗ nào và khác nhau như thế nào, mà không cần đọc hết toàn bộ cuốn sách qua điện thoại? Câu trả lời của câu hỏi đầu tiên rất đơn giản, bằng cách dùng hàm checksum (MD5 chẳng hạn) và so sánh checksum của 2 cuốn sách, như thế nó sẽ xác định được 2 cuốn sách có giống nhau hay không. Câu 42 trả lời cho câu hỏi thứ 2 thì khó hơn một chút. Một hướng nghiên cứu ban đầu là người ta chia cuốn sách thành 2 nửa, nửa đầu và nửa cuối, sau đó sẽ thực hiện checksum trên mỗi nửa, cho tới khi vị trí khác nhau được tìm ra. Tuy nhiên, hướng nghiên cứu này sẽ bị sai trong một trường hợp hết sức đơn giản, khi một cuốn sách chứa thêm một số từ vào đầu. Do đó, một hướng nghiên cứu khác, mạnh hơn là cần thiết mặc dù ý tưởng cơ bản vẫn là sử dụng checksum trên các khối. Chúng ta sẽ mô tả và chọn lọc thuật toán rsync. Ý tưởng cơ bản là giải quyết vấn đề về sự sắp xếp thẳng hàng bằng cách tính checksum khối cho file tham chiếu, và so sánh các checksum này với các checksum khối tương ứng của file hiện thời, và với checksum của tất cả các vị trí có thể của các khối trong file hiện thời. Kết quả là, server biết được đoạn nào của file hiện thời đã tồn tại trong file tham chiếu, và phần nào mới cần giao tiếp với client. Để đạt được hiệu quả, 2 checksum khác nhau sẽ được truyền thông tới server, tuy nhanh nhưng không đáng tin cậy, muốn đạt được sự tin cậy hơn thì cần đắt hơn nhiều. 1. Tại client: (a) Phần fold trong các khối Bi = fold [ib,(i+1)b-1] của kích thước b được xác định sau (b) Với mỗi khối Bi, tính 2 checksum, ui = hu (Bi) và ri = hr (Bi) và truyền chúng tới server. Ở đây, hu là hàm checksum không đáng tin cậy nhưng nhanh, và hr thì đáng tin cậy nhưng đắt. 2. Tại server: (a) Với mỗi cặp checksum nhận được (ui,ri), thêm một thực thể (ui,ri,i) vào cấu trúc dữ liệu từ điển, sử dụng ui như một giá trị khoá. (b) Thực hiện một bước trong fnew, bắt đầu tại vị trí j=0, và liên quan tới các bước sau: (i) Tính hàm checksum không đáng tin cậy hu(fnew [j, j+b-1]) trên khối bắt đầu tại j. (ii) Kiểm tra từ điển xem có khối nào có checksum không tin cậy phù hợp không (iii) Nếu tìm thấy, và nếu có checksum đáng tin cậy cũng phù hợp, truyền một con trỏ tới chỉ số của khối phù hợp trong fold tới client, j tiến tới vị trí b, và tiếp tục. (iv) Nếu không tìm thấy, hoặc nếu checksum tin cậy không phù hợp, truyền ký tự fnew[j] tới client, tăng j thêm 2 và tiếp tục. Tại client: Sử dụng dòng dữ liệu và con trỏ với khối trong fold để xây dựng lại fnew. 43 Checksum nhanh và không tin cậy được sử dụng để tìm ra sự phù hợp, và các checksum tin cậy sau đó được dùng để xác nhận sự phù hợp đó. Checksum phù hợp được thi hành bằng cách sử dụng MD4 (128 bit). Checksum không tin cậy có 32bit, nó cho phép chuyển một cách hiệu quả các đường bao khối bởi 1 ký tự, chẳng hạn, checksum cho f[j+1,j+b] có thể được tính trong thời gian không đổi từ f[j,j+b-1]. Rõ ràng, việc lựa chọn một kích thước khối tốt là tiêu chuẩn để thực hiện thuật toán. Sự lựa chọn tốt nhất lại phụ thuộc lớn vào sự giống nhau giữa 2 file – các file càng giống nhau thì chúng ta càng có thể chọn kích thước khối lớn. Hơn nữa, vị trí của các thay đổi trong file thì cũng rất quan trọng. Nếu một ký tự đơn được thay đổi trong mỗi khối của fold, thì không có sự phù hợp nào sẽ được tìm thấy tại server và rsync sẽ không thể hoàn thành một cách hiệu quả được; mặt khác, nếu tất cả các thay đổi được phân thành một vài vùng trên file, rsync sẽ làm rất tốt thậm chí với một kích thước khối lớn. Tuy nhiên, rsync không có sự thi hành tốt với không gian khoảng cách file. Tất nhiên, thông thường kích thước khối thậm chí có thể thay đổi trong một file. Trong thực hành, rsync bắt đầu với một kích thước khối hàng trăm byte, và sử dụng các phép heuristic để chỉnh sửa sau đó. 2.5.3.2 Các kết quả thực nghiệm của rsync Bây giờ, chúng ta sẽ đưa ra một vài kết quả về sự thi hành của rsync so với nén delta. Các kết quả sử dụng tập dữ liệu gcc và emacs. Chúng ta tổng kết 5 con số cho rsync: số lượng dữ liệu được gửi từ client tới server (request), số lượng dữ liệu được gửi từ server tới client (reply), số lượng dữ liệu được gửi từ server tới client với tuỳ chọn nén đã bật (reply compressed), và tổng số cho cả 2 hướng trong trường hợp không nén (total) và đã nén (total compressed). Gcc Emacs Uncompressed 27288 27326 Gzip 7479 8191 Xdelta 461 2131 Vcdiff 289 1821 Zdelta 250 1465 Rsync request 180 227 Rsyn reply 2445 12528 Rsync reply compressed 695 4200 44 Rsync total 2626 12756 Rsync total compressed 876 4428 Bảng 2.2: Các kết quả nén cho tập dữ liệu gcc và emacs (KB) 700 500 300 200 100 80 Rsync request 227 301 472 686 1328 1679 Rsync reply 12528 11673 10504 9603 8433 8161 Rsync reply compressed 4201 3939 3580 3283 2842 2711 Rsync total 12756 11974 10976 10290 9762 9810 Rsync total compressed 4429 4241 4053 3970 4170 4360 Bảng 2.3: Các kết quả nén cho emacs với các tập dữ liệu khác nhau (KB) 2.5.3.3 Các ứng dụng Các ứng dụng cho đồng bộ file cũng tương tự như đối với thuật toán nén delta. Đồng bộ file thì phổ biến hơn, trong đó nó không yêu cầu các kiến thức về file tham chiếu; mặt khác, nén delta hướng tới thi hành sự đồng bộ một cách tốt hơn theo khía cạnh tỷ lệ nén. Có rất nhiều lý do tại sao server có thể không chứa các file tham chiếu, chẳng hạn do không gian bộ nhớ, do các phiên bản trước đó của file tham chiếu đã được cập nhật lên các phiên bản mới hơn… Dưới đây là một vài ví dụ: - Đồng bộ cho các file người dùng: Có một số gói phần mềm như rsync, Microsoft’s ActiveSync, Puma Technologies’ IntelliSync hay Palm’s HotSync cho phép đồng bộ giữa desktop, thiết bị mobile hay các tài khoản cá nhân có thể truy cập web. Trong phần này, các file hay các bản ghi có thể được update bởi rất nhiều phần khác nhau, và nhãn thời gian có thể được dùng để xác định phiên bản gần nhất. Chúng ta cần chú ý rằng có rất nhiều gợi ý cho các công cụ này. Với dữ liệu dạng file, chúng ta có thể đồng bộ các file từ xa, tránh được việc phải truyền toàn bộ file. Với dữ liệu tồn tại dưới dạng các tập lớn của các bản ghi nhỏ, chẳng hạn như danh sách các địa chỉ hay các cuộc hẹn trong các thiết bị cầm tay, vấn đề là làm thế nào để phân biệt các bản ghi này có thay đổi mà không cần gửi một dấu hiệu riêng hay các nhãn thời gian cho mỗi bản ghi. Vấn đề này, được mô hình hoá thành một tập hoà giải. Có rất nhiều các gói chương trình thực hiện truyền toàn bộ thực thể nếu có thay đổi nào xảy ra, thường thấy tại các tập dữ liệu dựa trên bản ghi nhỏ, không dùng cho các file lớn. Thêm vào đó, cũng có những vấn đề về việc định nghĩa về ngữ nghĩa thích hợp trong hệ thống đồng bộ file. 45 - Lưu trữ từ xa các tập dữ liệu khổng lồ: Việc đồng bộ có thể được sử dụng để lưu trữ từ xa các tập dữ liệu mà chỉ có thay đổi một chút giữa các lần cập nhật. Trong trường hợp này, việc giữ các phiên bản cũ tại server có giá đắt làm cho kỹ thuật nén delta trở lên không hiệu quả. - Truy cập web: Đồng bộ file cũng được dùng cho việc truyền HTTP giữa các client với một server hoặc proxy. Lợi ích của nó là server không cần phải giữ dấu vết của các phiên bản cũ được giữ tại client, và cũng không cần phải tìm lại các phiên bản ấy từ đĩa. Tuy nhiên, như chỉ ra trong phần trên, kỹ thuật đồng bộ file có tỷ lệ nén tồi hơn nén delta, và vì thế nó không chỉ đem lại những lợi ích cho các file tương tự nhau. - Hệ thống phân tán ngang hàng: Đồng bộ cũng được dùng cho việc cập nhật các cấu trúc dữ liệu phân tán cao như: routing table, name services, indexes, hay replication tables. 46 CHƯƠNG 3 - ỨNG DỤNG THUẬT TOÁN NÉN DELTA TRONG VIỆC CẬP NHẬT CÁC PHẦN MỀM NGHIỆP VỤ TẠI NGÂN HÀNG CÔNG THƯƠNG VIỆT NAM 3.1 Mô hình hệ thống công nghệ thông tin trong ngân hàng Công Thương Việt Nam Dưới đây là mô hình của hệ thống công nghệ thông tin trong ngân hàng. Hình 3.1: Mô hình hệ thống công nghệ thông tin tại NHCTVN Toàn hệ thống ngân hàng bao gồm rất nhiều chi nhánh trên khắp các tỉnh thành của cả nước. Mỗi chi nhánh lại bao gồm nhiều điểm giao dịch, phòng giao dịch. Tại mỗi điểm giao dịch, có thể có nhiều máy tính Client PC chứa các phần mềm nghiệp vụ giúp các giao dịch viên làm việc với khách hàng. Tại mỗi chi nhánh, có một máy chủ Branch Server nhằm quản lý dữ liệu tập trung của toàn bộ chi nhánh. Các máy chủ chi nhánh này lại được quản lý bởi một máy chủ Server vùng. Có ba máy chủ Server vùng là North Server, Middle Server và South Server tương ứng với ba vùng bắc, trung, nam. Các máy chủ Server vùng lại được quản lý bởi một máy chủ Server của toàn hệ thống, gọi là HQ Server. 47 3.2 Quy trình cập nhật các phần mềm nghiệp vụ trong ngân hàng Công Thương Việt Nam Khi có một nghiệp vụ mới, hoặc khi cần thay đổi các tham số cho một vài nghiệp vụ đang tồn tại,… các phần mềm nghiệp vụ cần được cập nhật tới tất cả các máy tính trong toàn hệ thống. Vậy, bài toán đặt ra là làm thế nào để các phần mềm này được cập nhật nhanh, kịp thời và chính xác? Thông thường, các thay đổi về phần mềm nghiệp vụ trong ngân hàng thường bao gồm hai phần: phần thứ nhất cập nhật trong cơ sở dữ liệu (chỉ cập nhật một lần trên máy chủ chi nhánh cho toàn bộ một chi nhánh, bằng cách chạy các file script); phần thứ hai cập nhật các file (dạng exe, rpt, dll…) cập nhật cho tất cả các máy bằng cách copy file. Toàn bộ quá trình do cán bộ điện toán của chi nhánh thực hiện. Trước tiên, cán bộ điện toán chạy file cript để cập nhật database. Sau khi cập nhật thành công database, cán bộ điện toán tiến hành copy các file cập nhật vào mỗi máy của từng giao dịch viên. Quy trình này sẽ xảy ra nhiều sai sót: Nếu file script bị lỗi (do bị mất mát dữ liệu trên đường truyền từ trung ương về chi nhánh), hoặc database chi nhánh không đáp ứng đủ các điều kiện đê chạy thành công file script, quá trình chạy script sẽ bị lỗi. Cũng có khi quá trình chạy script bị lỗi mà cán bộ điện toán không phát hiện ra (do sơ suất hoặc do trình độ thấp, không hiểu hết các lỗi). Điều này sẽ ảnh hưởng tới hoạt động của toàn chi nhánh, gây phiền hà cho khách hàng, mất lòng tin của khách hàng, ảnh hưởng đến uy tín của ngân hàng… Bên cạnh đó, việc cán bộ điện toán phải copy toàn bộ các file cần cập nhật đến mỗi máy tính cũng tiêu tốn rất nhiều thời gian, công sức. Các phòng giao dịch, điểm giao dịch trong một chi nhánh có thể ở các vị trí địa lý rất xa nhau. Trong khi đó, có những phần mềm nghiệp vụ yêu cầu điện toán chi nhánh phải cập nhật ngay trong ngày, hoặc trước giờ giao dịch của buổi sáng hôm sau… Rõ ràng là, quy trình cập nhật này còn rất nhiều nhược điểm. 3.3 Chương trình cập nhật tự động các phần mềm nghiệp vụ 3.3.1 Thiết kế hệ thống Hệ thống đáp ứng các yêu cầu của chương trình cập nhật tự động sẽ không có thay đổi so với hệ thống hiện tại. Tuy nhiên, hệ thống cũng phải đảm bảo các yêu cầu tính thống nhất, trình tự và dễ kiểm soát. Chẳng hạn, khi có một phần mềm nghiệp vụ cần được cập nhật, phần mềm ấy cần phải được cập nhật đồng bộ cho toàn hệ thống. Không thể xảy ra trường hợp, vào cùng một thời điểm, tại các điểm giao dịch khác nhau, phiên bản chạy của một phần mềm nghiệp vụ nào đó khác nhau. Tính dễ kiểm soát được thể hiện ở chỗ, trong quá trình thực hiện cập nhật tự động toàn hệ thống, 48 nếu phát sinh lỗi cập nhật tại một chi nhánh nào đó, lỗi này sẽ không làm ảnh hưởng đến các chi nhánh khác. Đồng thời, cán bộ thực hiện cập nhật có thể phát hiện ngay lỗi đang xảy ra tại chi nhánh nào, lỗi đó là gì (do đường truyền, do virus, do cấu hình máy client không tương thích, …). Quá trình cập nhật lại cho chi nhánh bị lỗi cũng phải không gặp bất kỳ khó khăn nào. Dựa trên mô hình hệ thống công nghệ thông tin và quy trình cập nhật phần mềm nghiệp vụ tại Ngân hàng Công Thương Việt Nam, các cán bộ thuộc Trung tâm công nghệ thông tin – Ngân hàng công thương Việt Nam đã nghiên cứu và hoàn thiện chương trình cập nhật tự động các phần mềm nghiệp vụ. Chương trình đã thực sự giúp ích rất nhiều cho các cán bộ điện toán tại chi nhánh, đồng thời giảm thiểu tối đa những sai sót cũng như sự tiêu tốn về thời gian và dung lượng trên đường truyền dữ liệu. Chương trình thực hiện theo quy trình sau: - Các gói cập nhật được tạo tại Server TW (HQ), sau đó sẽ được upload xuống các Server Vùng (North, Middle, South). - Các Server Vùng được xem như tầng trung gian, có nhiệm vụ trung chuyển các gói cập nhật từ Server HQ xuống các Server chi nhánh trong vùng. - Tại các máy PC client, chương trình sẽ tự động kiểm tra các gói cập nhật từ Server Chi nhánh và tiến hành cập nhật (nếu có). Phần mô tả về thiết kế chương trình dưới đây sẽ phân tích rõ hơn trong mỗi tầng của hệ thống. 3.3.2 Thiết kế chương trình Chương trình gồm 2 phần: - Đặt lịch tự động trên máy chủ Server TW và Server Vùng. - Chương trình quản lý trên Server TW. 3.3.2.1 Chương trình đặt lịch tự động Thực chất, chương trình này sử dụng một tiện ích của windows, nhằm đặt lịch chạy tự động một chương trình (chương trình upload) vào một thời điểm cố định nào đó. Chương trình được cài đặt tại các Server TW, Server vùng, Server chi nhánh. Tại Server TW, mỗi khi có một phần mềm nghiệp vụ cần cập nhật, chương trình quản lý trên Server TW sẽ tạo ra Patch file (file Delta). Vào một thời điểm cụ thể, chương 49 trình đặt lịch tự động trên Server TW chạy một chương trình upload nhằm upload các Patch file về Server vùng. Tại Server vùng, chương trình đặt lịch tự động được cài đặt sau thời điểm chương trình đặt lịch tự động tại Server TW chạy. Cũng giống như Server TW, Server vùng tiến hành upload các Patch file về Server chi nhánh. Như vậy, không cần sự can thiệp của điện toán chi nhánh, ngay khi có gói chương trình cần cập nhật tại TW, toàn bộ các Server chi nhánh sẽ nhận ngay được bản vá của chương trình. Khác với mô hình cũ đã được áp dụng tại ngân hàng công thương Việt Nam, trong mô hình mới này, phần dữ liệu được truyền đi trên mạng là tương đối nhỏ. Do vậy, việc upload các gói cập nhật thường không làm ảnh hưởng lưu lượng các gói tin truyền đi trên mạng, thậm chí trong cả thời gian giao dịch cao điểm của toàn hệ thống. 3.3.2.2 Chương trình quản lý trên Server TW Chương trình này được đặt tại Server TW, với các chức năng chính như sau: Hình 3.2: Các mô đun chính chương trình quản lý tại Server TW Dưới đây sẽ mô tả chi tiết từng chức năng của chương trình. 3.3.2.2.1 Quản lý gói cập nhật Chức năng Quản lý gói cập nhật bao gồm các chức năng sau: Chương trình quản lý tại Server TW Quản lý gói cập nhật Quản lý danh sách chi nhánh Quản lý danh sách ứng dụng Upload thủ công gói cập nhật Xem nhật ký upload 50 Hình 3.3: Các chức năng của mô đun Quản lý gói cập nhật Chức năng Xóa gói cập nhật có thể được thực hiện khi gói cập nhật không còn cần thiết trên hệ thống nữa, người sử dụng có thể tiến hành xóa để dọn dẹp hệ thống. Chức năng Tạo mới/ chỉnh sửa gói cập nhật có luồng xử lý tương tự nhau. Hình 3.4: Lưu đồ chức năng Tạo mới/chỉnh sửa gói cập nhật Quản lý gói cập nhật Tạo mới gói cập nhật Chỉnh sửa gói cập nhật Xóa gói cập nhật Start Fold Fnew Version (Fold) < Version (Fnew) ? Fold  UTFold Fnew  UTFnew Y N Create Patch File End 51 Đầu vào của mô đun Tạo mới/ Chỉnh sửa gói cập nhật bao gồm file chương trình cũ và file chương trình mới. Hai file chương trình này phải cùng tồn tại trên máy chạy mô đun. Đầu tiên, chương trình thực hiện so sánh version của hai file. Việc so sánh này có thể thực hiện dựa trên ngày/giờ tạo của mỗi chương trình. Nếu file Fold có version mới hơn file Fnew thì chương trình đưa ra thông báo cho người sử dụng kiểm tra lại. Để thực hiện tạo Patch file, chương trình cần thực hiện chuyển đổi các file sang dạng mã UTF (xem bảng mã UTF8 trong phần phụ lục tham khảo). Về kỹ thuật tạo patch file đã được trình bày trong phần trên, dưới đây sẽ mô tả hàm cơ bản được dùng trong quá trình tạo patch file. CreatePatchFile có các tham số sau BOOL CreatePatchFile( LPCTSTR lpszPatchFile, // name of patch file DWORD dwPatchLevel, // patch level DWORD dwPatchOptions, // patch options DWORD dwPatchExpires, // patch expiration DWORD dwReserved, // reserved LPCTSTR lpszPassword, // password LPCTSTR lpszOldFile, // name of old file LPCTSTR lpszNewFile, // name of new file LPPATCHSTATUSPROC lpfnCallback, // pointer to callback function LPARAM lParam // callback function parameter ); Giải thích các tham số LpszPatchFile Một con trỏ chỉ ra tên của patch file được tạo ra. Nếu đã tồn tại một file với tên đó rồi, file sẽ được ghi đè. DwPatchLevel Có giá trị từ 1 đến 9 xác định tốc độ và dung lượng bộ nhớ trong việc tạo patch file. Nếu Patch level càng cao, patch file sẽ càng nhỏ, bộ nhớ yêu cầu càng nhỏ. Giá trị 0 là mức patch file mặc định phù hợp cho hầu hết các file. Xem bảng sau: Giá trị Mô tả 52 PATCH_LEVEL_DEFAULT Một mức nén mặc định nên được lựa chọn để phù hợp với hầu hết các file. Giá trị này nên được sử dụng. PATCH_LEVEL_MINIMUM Tốc độ cực đại trong việc tạo patch file, với tuỳ chọn này, patch file được tạo ra nhanh hơn, sử dụng ít bộ nhớ hơn, patch file được tạo ra có kích thước lớn hơn. PATCH_LEVEL_MAXIMUM Tỷ lệ nén file lớn nhất, quá trình tạo file nén lâu hơn, tốn nhiều bộ nhớ hơn và tạo ra patch file nhỏ hơn. dwPatchOptions Một tập các tuỳ chọn được sử dụng trong khi thực hiện quá trình tạo patch file. Một trong các giá trị sau sẽ được sử dụng: Giá trị Mô tả PATCH_OPTION_FIND_FILE Nếu file tham chiếu không được tìm thấy trong hệ thống, chương trình sẽ cố gắng tìm theo các quy tắc về đường dẫn thư mục chuẩn của Windows. Theo đó, thư mục hiện thời, thư mục hệ thống, và các thư mục trong biến môi trường PATH sẽ được tìm. PATCH_OPTION_BACKUP_FILE Tạo một file backup trên hệ thống trước khi áp dụng patch file. Nếu cờ này không được dựng, file sẽ được cập nhật ngay mà không có bản backup. PATCH_OPTION_COMPARE_FILETIME So sánh thời gian file đích được chỉnh sửa với thời gian file tham chiếu được chỉnh sửa. Nếu file đích có thời gian chỉnh sửa muộn hơn so với file tham chiếu tại thời điểm patch đã được tạo, chương trình sẽ đưa ra lỗi AP_ERROR_NEWER_FILETIME. Điều này đảm bảo rằng file cập nhật luôn có thời gian chỉnh sửa sau 53 file tham chiếu. PATCH_OPTION_COMPARE_VERSION So sánh phiên bản của file tham chiếu với file đích. Nếu file tham chiếu có phiên bản mới hơn so với file đích tại thời điểm patch file được tạo thì chương trình sẽ đưa ra lỗi: AP_ERROR_NEWER_VERSION. Điều này đảm bảo rằng file cập nhật luôn có phiên bản mới hơn file tham chiếu PATCH_OPTION_IGNORE_FILETIME Bỏ qua sự khác nhau về thời gian chỉnh sửa file của các file đích và file tham chiếu tại thời điểm patch file được tạo ra. PATCH_OPTION_IGNORE_VERSION Bỏ qua sự khác nhau về phiên bản file của các file đích và file tham chiếu tại thời điểm patch file được tạo ra. PATCH_OPTION_IGNORE_ATTRIBUTES Bỏ qua các thuộc tính file cập nhật khi patch được áp dụng trên hệ thống và thay vào đó, sử dụng các thuộc tính mặc định. PATCH_OPTION_IGNORE_READONLY Bỏ qua thuộc tính read-only khi áp dụng patch file. Nếu file cần cập nhật có thuộc tính này, nó sẽ được loại bỏ. PATCH_OPTION_IGNORE_SIGNATURE Bỏ qua bất kỳ chữ ký điện tử nào được hiển thị. Nếu file cập nhật đã được ký bởi mã xác thực, chữ ký sẽ được xác thực tại thời điểm patch được áp dụng. dwPatchExpires Xác định số ngày patch có thể được áp dụng. Khi ngày hết hạn được đạt tới, patch file sẽ không còn được áp dụng nữa. Giá trị 0 thể hiện patch file không bao giờ hết hạn. 54 lpszPassword Một con trỏ tới xâu password được dùng để bảo mật. Patch file sau khi được tạo ra, sẽ chưa được áp dụng cho đến khi password được cung cấp trong hàm ApplyPatchFile. Nếu không dùng password, tham số này sẽ được đặt là NULL để trỏ tới một xâu rỗng. lpszOldFile Một con trỏ tới một xâu không rỗng xác định tên của file tham chiếu. lpszNewFile Một con trỏ tới một xâu không rỗng xác định tên của file cập nhật. File này sẽ được so sánh lại với file tham chiếu, bất kỳ thay đổi nào cũng sẽ được ghi trong patch file. Các giá trị trả về Nếu hàm CreatePatchFile thành công, nó sẽ trả về một giá trị khác 0. Ngược lại, nếu hàm lỗi, nó sẽ trả về giá trị 0. Để biết các lỗi có thể có, tham khảo thêm hàm GetLastError. Chú ý Để áp dụng patch file trên hệ thống, sử dụng hàm ApplyPatchFile. Khi patch level càng cao, chương trình sẽ thực hiện phân tích các file tham chiếu và file cập nhật càng lâu. Nó cũng sử dụng tới nhiều bộ nhớ hơn. Chú ý rằng, trong một vài trường hợp, tuỳ thuộc vào cấu trúc bên trong của file, patch level lớn nhất có thể sẽ làm tăng kích thước của patch file kết quả. Vì vậy, ta nên sử dụng patch level mặc định. Nếu cả PATCH_OPTION_COMPARE_FILETIME và PATCH_OPTION_IGNORE_FILETIME đều không được thiết lập, thì PATCH_OPTION_COMPARE_FILETIME là mặc định. Nếu cả PATCH_OPTION_COMPARE_FILETIME và PATCH_OPTION_IGNORE_FILETIME đều được thiết lập, thì PATCH_OPTION_IGNORE_FILETIME giành quyền ưu tiên. Nếu cả PATCH_OPTION_COMPARE_VERSION và PATCH_OPTION_IGNORE_VERSION đều không được thiết lập, thì PATCH_OPTION_COMPARE_VERSION là mặc định. Nếu cả 55 PATCH_OPTION_COMPARE_VERSION và PATCH_OPTION_IGNORE_VERSION được thiết lập, thì PATCH_OPTION_IGNORE_VERSION giành quyền ưu tiên. 3.3.2.3.2 Quản lý danh sách chi nhánh Để thực hiện cập nhật tự động đến từng Server chi nhánh, IP của các Server này cần được cung cấp. Chương trình upload tự động sẽ tìm đến các IP này, và tiến hành upload các patch file lên các Server đó. Các mô đun chính của chức năng Quản lý danh sách chi nhánh bao gồm: Hình 3.5: Các chức năng của mô đun Quản lý danh sách chi nhánh Khi có một chi nhánh mới mở trong hệ thống, chi nhánh này cần được cập nhật vào danh sách. Cũng vậy, khi một chi nhánh đóng cửa, chi nhánh này cần được xoá khỏi danh sách. Khi IP máy chủ chi nhánh có thay đổi, hoặc khi tên chi nhánh có thay đổi, các thông tin thay đổi cũng cần được cập nhật trong database tại trung ương. Có như vậy, chương trình upload mới tìm đúng địa chỉ cần upload các patch file. Chức năng Quản lý danh sách chi nhánh thực chất được thực hiện bởi các thao tác Insert, Update, Delete vào bảng brn_list trong database tại server trung ương. Theo đó, chương trình upload sẽ tiến hành thao tác upload patch file lên các IP trong bảng brn_list. Sửa tên chi nhánh Sửa IP chi nhánh Quản lý danh sách chi nhánh Thêm mới chi nhánh Sửa đổi chi nhánh Xoá chi nhánh 56 Hình 3.6: Mối quan hệ giữa chức năng quản lý danh sách chi nhánh và các chức năng khác 3.3.2.3.3 Quản lý danh sách ứng dụng Chức năng quản lý danh sách ứng dụng nhằm cung cấp đầu vào cho chức năng Quản lý gói cập nhật. Chức năng Quản lý gói cập nhật chỉ thực hiện tạo patch file được cho các ứng dụng nằm trong danh sách ứng dụng do chức năng Quản lý danh sách ứng dụng cung cấp. Tại trung ương, chỉ quản lý tên các ứng dụng phục vụ cho quá trình tạo patch file. Tại chi nhánh, mỗi khi quá trình cập nhật ứng dụng được thực hiện, tên và version của ứng dụng đó sẽ được cập nhật lại trong database tại Server chi nhánh. Brn_lst - Mã CN - Tên CN - IP Server CN Quản lý DS CN Thêm mới Chỉnh sửa Xoá Delete Update Insert Chương trình upload tự động Địa chỉ IP Quản lý gói cập nhật Patch file Server CN1 (IP1) Server CN2 (IP2) Server CN3 (IP3) Patch file Patch file Patch file 57 Hình 3.7: Các mô đun chính của chức năng Quản lý danh sách ứng dụng Cũng giống chức năng Quản lý danh sách chi nhánh, chức năng Quản lý danh sách ứng dụng gồm ba mô đun chính: Thêm mới ứng dụng, Chỉnh sửa ứng dụng và Xoá ứng dụng. Hình 3.8: Mối quan hệ giữa chức năng Quản lý danh sách ứng dụng và chức năng Quản lý gói cập nhật 3.3.2.3.4 Upload thủ công gói cập nhật Sau khi gói cập nhật được tạo xong, gói sẽ được đẩy tự động xuống các Server vùng, và Server chi nhánh bằng chương trình đặt lịch tự động (đã nói ở trên). Tuy nhiên, theo yêu cầu nghiệp vụ, có thể có một số chi nhánh bắt buộc phải được chạy trước. Quản lý danh sách ứng dụng Thêm mới ứng dụng Chỉnh sửa ứng dụng Xoá ứng dụng Quản lý DS ứng dụng Thêm mới ứng dụng Chỉnh sửa ứng dụng Xoá ứng dụng Insert Update Delete Quản lý gói cập nhật Tên ứng dụng Fold: Name(Fold)=Tên ƯD Fnew:Name(Fnew)=Tên ƯD Patch file App_list - App_name - App_desc 58 Tương tự, đối với trường hợp chi nhánh không nhận được gói cập nhật (do lỗi đường truyền chẳng hạn), gói cập nhật cần được upload bằng tay. Hình 3.9: Mối quan hệ giữa chức năng Upload thủ công gói cập nhật và các chức năng khác 3.3.2.3.5 Xem nhật ký upload Khi chức năng Upload tự động/ Upload thủ công được thực hiện, chương trình ghi lại ngày giờ, trạng thái upload tới mỗi Server vùng, Server chi nhánh. Dựa vào đó, chức năng xem nhật ký upload giúp người quản trị biết tình trạng upload gói cập nhật tới mỗi Server và có hướng xử lý cho các trường hợp phát sinh lỗi. Hình 3.10: Mối quan hệ giữa chức năng Xem nhật ký upload và các chức năng khác. Quản lý DS chi nhánh Quản lý gói cập nhật IP chi nhánh Upload thủ công gói cập nhật Patch file Chương trình upload tự động Mô đun: Upload thủ công Package_update - Package_name - From version - To version - Upload time - Server - Status Insert/Update Insert/Update Xem nhật ký upload 59 3.3.3 Thực thi chương trình 3.3.3.1 Chương trình đặt lịch tự động - Chạy chương trình Scheduled Tasks của Windows - Chọn Add Scheduled Task Hình 3.11: Thực thi chương trình đặt lịch tự động (1) - Chọn Next 60 Hình 3.12: Thực thi chương trình đặt lịch tự động (2) - Chọn Browse Hình 3.13: Thực thi chương trình đặt lịch tự động (3) - Chọn File Upload.bat trong thư mục AutoUpdateTask vừa tạo 61 Hình 3.14: Thực thi chương trình đặt lịch tự động (4) - Đặt tên cho Task là Auto Update Task và chọn Perform this task là Daily - Chọn Next Hình 3.15: Thực thi chương trình đặt lịch tự động (5) - Đặt Start time là 7:00 PM - Chọn Next 62 Hình 3.16: Thực thi chương trình đặt lịch tự động (6) - Nhập user name và password - Chọn Next Hình 3.17: Thực thi chương trình đặt lịch tự động (6) - Chọn Finish để hoàn tất việc cài đặt. 63 3.3.3.2 Chương trình quản lý trên server TW Giao diện chương trình như sau: Hình 3.18: Giao diện màn hình quản lý trên Server TW 3.3.3.2.1 Quản lý gói cập nhật Từ màn hình chương trình, chọn Package Manager. Nhấn vào nút Create Update Package, màn hình sẽ hiển thị: Hình 3.19: Thực thi mô đun Quản lý gói cập nhật (1) - Tạo các gói cập nhật: 64 - Nhấn vào nút Add để tạo gói cập nhật: Hình 3.20: Thực thi mô đun Quản lý gói cập nhật (2) - Nhập mã và tên của gói cập nhật. - Nhấn vào nút Add để tạo cập nhật cho file Hình 3.21: Thực thi mô đun Quản lý gói cập nhật (3) - Chọn mã ứng dụng (Application Code), file cập nhật (Application File). 65 - Nhập cập nhật từ phiên bản (From Version) nào tới phiên bản nào (To Version). - Chọn Create để tạo patch file cập nhật Hình 3.22: Thực thi mô đun Quản lý gói cập nhật (4) - Chọn file cũ (Old File), file mới (New File) và nhập patch file sau đó nhấn nút Make để tạo. - Sau khi đã tạo xong các cập nhật, nhấn nút Save để lưu gói cập nhật. - Các gói cập nhật sau khi được tạo ra sẽ được upload theo lịch xuống các Server Vùng (Server Chi nhánh) có trong danh sách. 3.3.3.2.2 Quản lý danh sách chi nhánh Từ màn hình chương trình, chọn Regional Manager 66 Hình 3.23: Thực thi mô đun Quản lý danh sách chi nhánh (1) - Danh sách các chi nhánh được sử dụng để upload sẽ được hiển thị. - Nhấn vào nút Add để thêm chi nhánh mới vào danh sách. Hình 3.24: Thực thi mô đun Quản lý danh sách chi nhánh (2) Nhập Mã chi nhánh, Tên chi nhánh, Địa chỉ IP máy chủ chi nhánh, tên database chi nhánh. - Nhấn vào nút Modify để chỉnh sửa một chi nhánh lựa chọn. 67 Hình 3.25: Thực thi mô đun Quản lý danh sách chi nhánh (3) - Nhấn vào nút Delete để xóa chi nhánh trong danh sách. 3.3.3.2.3 Quản lý danh sách ứng dụng Từ màn hình chương trình, chọn nút Application Manager. Hình 3.26: Thực thi mô đun Quản lý danh sách ứng dụng (1) - Chọn New để thêm ứng dụng mới 68 Hình 3.27: Thực thi mô đun Quản lý danh sách ứng dụng (2) - Nhập Application Code (Mã của ứng dụng, VD: ISAPP, BDS,…) và Application Name (Tên của ứng dụng) sau đó nhấn Add để khai bao các file trong ứng dụng. - Chọn Save để lưu lại ứng dụng mới vừa tạo. - Chọn Modify để thay đổi ứng dụng đã có. - Chọn Delete để xóa bỏ ứng dụng. 3.3.3.2.4 Upload thủ công gói cập nhật Từ màn hình chương trình, nhấn vào nút Upload To Branch Manual, màn hình sẽ hiển thị: Hình 3.28: Thực thi mô đun Upload thủ công gói cập nhật (1) - Chọn gói cần upload rồi chọn Next, 69 Hình 3.29: Thực thi mô đun Upload thủ công gói cập nhật (2) - Chọn chi nhánh cần upload rồi chọn Upload Hình 3.30: Thực thi mô đun Upload thủ công gói cập nhật (3) - Màn hình sẽ thông báo kết quả upload, nhấn Finish để kết thúc. 3.3.3.2.5 Xem nhật ký upload Từ màn hình chương trình, nhấn vào nút Upload History 70 Hình 3.31: Thực thi mô đun Xem nhật ký upload (1) - Lựa chọn việc xem nhật ký theo gói cập nhật (package) hoặc theo chi nhánh (branch). Nhấn Next để hiển thị Hình 3.32: Thực thi mô đun Xem nhật ký upload (2) Trạng thái S thể hiện quá trình upload tới Server thành công, trạng thái N thể hiện quá trình upload không thành công. 71 CHƯƠNG 4 - KẾT LUẬN 4.1 Kết luận Cùng sự phát triển bùng nổ của công nghệ thông tin, có rất nhiều công nghệ nén ra đời nhằm giảm dung lượng file được lưu trữ trên đĩa, trên đường truyền…Mỗi công nghệ đều có những ưu nhược điểm riêng, phù hợp với các mục đích sử dụng khác nhau. Công nghệ nén Delta dựa trên sự sai khác nhau giữa hai file (file nguồn và file đích) và tạo ra một file có kích thước nhỏ hơn nhiều so với các file ban đầu. Microsoft phát triển công nghệ này nhằm mục đích update các bản cập nhật phần mềm bằng cách gửi các bản vá có kích thước nhỏ. Trung tâm công nghệ thông tin – Ngân hàng công thương Việt Nam đã nghiên cứu và áp dụng thành công công nghệ nén Delta, triển khai theo mô hình Server – client. Khi có phần mềm nghiệp vụ cần cập nhật cho các máy client tại chi nhánh, bản vá được tạo ra dựa trên sự sai khác giữa hai bản, sau đó được chuyển tới các Server vùng. Tại Server vùng, thực hiện upload bản vá xuống các Server chi nhánh. Tại các máy client của chi nhánh, mỗi khi một chương trình nghiệp vụ chạy, sẽ có sự so sánh giữa bản đang chạy và bản cần cập nhật, nếu có sự sai khác, chương trình được cập nhật tự động. 4.2. Ưu nhược điểm của phương pháp Ưu điểm lớn nhất của công nghệ nén Delta là tỷ lệ nén lớn. Nếu tỷ lệ nén cho các tệp thực thi thường dao động quanh 3:1 thì tỷ lệ nén của bản vá so với tệp đích theo công nghệ Delta có thể nằm trong khoảng từ 10:1 tới 1000:1 và thậm chí có thể lớn hơn – tùy thuộc vào dung lượng tệp đích và mức độ khác biệt của file đích và file nguồn. Vì vậy, công nghệ này phù hợp với mục đích truyền bản vá trên đường truyền nhằm cập nhật các phiên bản mới hơn. Do tỷ lệ nén lớn, file truyền trên đường truyền có kích thước rất nhỏ, không tốn đường truyền, thời gian truyền nhanh,do vậy mà ít xảy ra các lỗi do mất dữ liệu trên đường truyền. Một ưu điểm dễ nhận thấy khác của công nghệ này là khi được kết hợp với tiện ích lập lịch tự động như được trình bày trong luận văn thì các file được cập nhật tự động, gần như trong suốt với người sử dụng. Do vậy, người sử dụng không cần các thao tác giải nén (dù là đơn giản hay phức tạp). Ưu điểm này rất có ý nghĩa trong các hệ thống 72 nghiệp vụ tại Việt Nam, khi mà trình độ về công nghệ thông tin của các cán bộ nghiệp vụ chưa cao. Tuy nhiên, công nghệ nén Delta cũng có một số nhược điểm nhất định. Nhược điểm lớn nhất là công nghệ này chỉ phù hợp với mục đích truyền bản vá cho các máy từ xa. Công nghệ này gần như không được áp dụng cho các mục đích lưu trữ file trên máy tính cá nhân. Đây là một nhu cầu rất lớn của các người dùng máy tính cá nhân. Microsoft đã xử lý trường hợp khi phiên bản gốc trên các máy cần cập nhật khác nhau không giống nhau, Delta vẫn biến các phiên bản ấy về cùng một phiên bản mới. Tuy nhiên, do giới hạn về mặt thời gian, luận văn này mới chỉ nghiên cứu trong các trường hợp khi phiên bản gốc của tất cả các máy client giống nhau và trùng với phiên bản gốc của bản vá. 4.3 Hướng nghiên cứu trong tương lai Giải quyết đối với trường hợp các phiên bản gốc của các máy cần cập nhật khác nhau là một trong những mục tiêu đầu tiên của các cán bộ trung tâm công nghệ thông tin – Ngân hàng công thương Việt Nam. Khi có nhiều phần mềm nghiệp vụ cần cập nhật tại một thời điểm, cần phải tạo nhiều bản vá tương ứng. Nếu gom tất cả các bản vá thành một bản vá duy nhất, sẽ giảm thiểu tối đa số thao tác cần thực hiện cho các cán bộ kỹ thuật. Đây cũng là một trong những hướng nghiên cứu quan trọng. Vấn đề bảo mật bản vá trên đường truyền cũng là một trong những vấn đề cần được quan tâm. Do giới hạn về mặt thời gian, luận văn chưa thực hiện được mục tiêu này. Đây cũng là một trong những hướng nghiên cứu quan trọng của luận văn. 73 TÀI LIỆU THAM KHẢO Tiếng Việt 1. 9/2009 ,“Tổng quan thuật toán nén dữ liệu”, Diễn đàn sinh viên CNNT Đại học Duy Tân. 2. Phạm Tuấn Anh (2008), Nghiên cứu các thuật toán nén , Tuyển tập báo cáo hội nghị sinh viên nghiên cứu khoa học, Đại học Đà Nẵng. 3. “ m”,Bảng đối chiếu encoding các bộ chữ hiện hành với Unicode. Tiếng Anh 4. A. Cobbs (1995), “Fast approximate matching using suffix trees”, Combinatorial Pattern Matching. 5. G. Navarro, R. Baeza-Yates, E. Sutinen, J. Tarhio (2001), “Indexing methods for approximate string matching”, IEEE Data Eng. Bull (24). 6. J.Hunt, K.P. Vo, and W.Tich (1992), “Delta algorithms: An empirical analysis” ACM Transactions on Computers. 7. J.Ziv and A.Lempel (1997), ”A universal algorithm for data compression” IEEE Transactions on Information Theory. 8. Ramesh C.Agarwal, Suchitra Amalapurapu (2001), “An approximation to the Greedy Algorithm for Differential Compression of Very Large Files”. 9. R.A. Baeza-Yates, G. Navarro (2000), “A faster algorithm for approximate string matching”, Proc. Seventh Ann. Symp. on Combinatorial Pattern 10. R.A. Wagner and M.J.Fisher (2002), “The string – to – string correction problem” J.ACM, 168-173 11. R. Grossi, J.S. Vitter (1996), “Compressed suffix arrays and suffix trees with applications to text indexing and string matching”, ACM 12. Torsten Suel, Nasir Memon, CIS Department Polytechnic University Brooklyn, NY 11201, “Algorithms for Delta Compression and Remote File Synchronization” 13. W. Tichy (1997), “The string – to – string correction problem with block moves”. ACM Transactions on Computers. 74 Bảng đối chiếu encoding các bộ chữ hiện hành với Unicode VIQR VPS VPS Hex VISCII VISCII Hex VNI VNI Hex TCVN TCVN Hex Unicode Symbol Unicode Hex Dec UTF-8 Hex a' á E1 á E1 aù 61 F9 ¸ B8 á 00E1 225 C3 A1 a` à E0 à E0 aø 61 F8 µ B5 à 00E0 224 C3 A0 a? ä E4 ä E4 aû 61 FB ¶ B6 ả 1EA3 7843 E1 BA A3 a~ ã E3 ã E3 aõ 61 F5 · B7 ã 00E3 227 C3 A3 a. å E5 Õ D5 aï 61 EF ¹ B9 ạ 1EA1 7841 E1 BA A1 a( æ E6 å E5 aê 61 EA ¨ A8 ă 0103 259 C4 83 a(' ¡ A1 ¡ A1 aé 61 E9 ¾ BE ắ 1EAF 7855 E1 BA AF a(` ¢ A2 ¢ A2 aè 61 E8 » BB ằ 1EB1 7857 E1 BA B1 a(? £ A3 Æ C6 aú 61 FA ¼ BC ẳ 1EB3 7859 E1 BA B3 a(~ ¤ A4 Ç C7 aü 61 FC ½ BD ẵ 1EB5 7861 E1 BA B5 a(. ¥ A5 £ A3 aë 61 EB Æ C6 ặ 1EB7 7863 E1 BA B7 a^ â E2 â E2 aâ 61 E2 © A9 â 00E2 226 C3 A2 a^' à C3 ¤ A4 aá 61 E1 Ê CA ấ 1EA5 7845 E1 BA A5 a^` À C0 ¥ A5 aà 61 E0 Ç C7 ầ 1EA7 7847 E1 BA A7 75 a^? Ä C4 ¦ A6 aå 61 E5 È C8 ẩ 1EA9 7849 E1 BA A9 a^~ Å C5 ç E7 aã 61 E3 É C9 ẫ 1EAB 7851 E1 BA AB a^. Æ C6 § A7 aä 61 E4 Ë CB ậ 1EAD 7853 E1 BA AD e' é E9 é E9 eù 65 F9 Ð D0 é 00E9 233 C3 A9 e` è E8 è E8 eø 65 F8 Ì CC è 00E8 232 C3 A8 e? È C8 ë EB eû 65 FB Î CE ẻ 1EBB 7867 E1 BA BB e~ ë EB ¨ A8 eõ 65 F5 Ï CF ẽ 1EBD 7869 E1 BA BD e. Ë CB © A9 eï 65 EF Ñ D1 ẹ 1EB9 7865 E1 BA B9 e^ ê EA ê EA eâ 65 E2 ª AA ê 00EA 234 C3 AA e^' ‰ 89 ª AA eá 65 E1 Õ D5 ế 1EBF 7871 E1 BA BF e^` Š 8A « AB eà 65 E0 Ò D2 ề 1EC1 7873 E1 BB 81 e^? ‹ 8B ¬ AC eå 65 E5 Ó D3 ể 1EC3 7875 E1 BB 83 e^~ Í CD AD eã 65 E3 Ô D4 ễ 1EC5 7877 E1 BB 85 e^. Œ 8C ® AE eä 65 E4 Ö D6 ệ 1EC7 7879 E1 BB 87 i' í ED í ED í ED Ý DD í 00ED 237 C3 AD i` ì EC ì EC ì EC × D7 ì 00EC 236 C3 AC 76 i? Ì CC ï EF æ E6 Ø D8 ỉ 1EC9 7881 E1 BB 89 i~ ï EF î EE ó F3 Ü DC ĩ 0129 297 C4 A9 i. Î CE ¸ B8 ò F2 Þ DE ị 1ECB 7883 E1 BB 8B o' ó F3 ó F3 où 6F F9 ã E3 ó 00F3 243 C3 B3 o` ò F2 ò F2 oø 6F F8 ß DF ò 00F2 242 C3 B2 o? Õ D5 ö F6 oû 6F FB á E1 ỏ 1ECF 7887 E1 BB 8F o~ õ F5 õ F5 oõ 6F F5 â E2 õ 00F5 245 C3 B5 o. † 86 ÷ F7 oï 6F EF ä E4 ọ 1ECD 7885 E1 BB 8D o^ ô F4 ô F4 oâ 6F E2 « AB ô 00F4 244 C3 B4 o^' Ó D3 ¯ AF oá 6F E1 è E8 ố 1ED1 7889 E1 BB 91 o^` Ò D2 ° B0 oà 6F E0 å E5 ồ 1ED3 7891 E1 BB 93 o^? ° B0 ± B1 oå 6F E5 æ E6 ổ 1ED5 7893 E1 BB 95 o^~ ‡ 87 ² B2 oã 6F E3 ç E7 ỗ 1ED7 7895 E1 BB 97 o^. ¶ B6 µ B5 oä 6F E4 é E9 ộ 1ED9 7897 E1 BB 99 o+ Ö D6 ½ BD ô F4 ¬ AC ơ 01A1 417 C6 A1 o+' § A7 ¾ BE ôù F4 F9 í ED ớ 1EDB 7899 E1 BB 9B 77 o+` © A9 ¶ B6 ôø F4 F8 ê EA ờ 1EDD 7901 E1 BB 9D o+? ª AA · B7 ôû F4 FB ë EB ở 1EDF 7903 E1 BB 9F o+~ « AB Þ DE ôõ F4 F5 ì EC ỡ 1EE1 7905 E1 BB A1 o+. ® AE þ FE ôï F4 EF î EE ợ 1EE3 7907 E1 BB A3 u' ú FA ú FA uù 75 F9 ó F3 ú 00FA 250 C3 BA u` ù F9 ù F9 uø 75 F8 ï EF ù 00F9 249 C3 B9 u? û FB ü FC uû 75 FB ñ F1 ủ 1EE7 7911 E1 BB A7 u~ Û DB û FB uõ 75 F5 ò F2 ũ 0169 361 C5 A9 u. ø F8 ø F8 uï 75 EF ô F4 ụ 1EE5 7909 E1 BB A5 u+ Ü DC ß DF ö F6 AD ư 01B0 432 C6 B0 u+' Ù D9 Ñ D1 öù F6 F9 ø F8 ứ 1EE9 7913 E1 BB A9 u+` Ø D8 × D7 öø F6 F8 õ F5 ừ 1EEB 7915 E1 BB AB u+? º BA Ø D8 öû F6 FB ö F6 ử 1EED 7917 E1 BB AD u+~ » BB æ E6 öõ F6 F5 ÷ F7 ữ 1EEF 7919 E1 BB AF u+. ¿ BF ñ F1 öï F6 EF ù F9 ự 1EF1 7921 E1 BB B1 y' š 9A ý FD yù 79 F9 ý FD ý 00FD 253 C3 BD 78 y` ÿ FF Ï CF yø 79 F8 ú FA ỳ 1EF3 7923 E1 BB B3 y? › 9B Ö D6 yû 79 FB û FB ỷ 1EF7 7927 E1 BB B7 y~ Ï CF Û DB yõ 79 F5 ü FC ỹ 1EF9 7929 E1 BB B9 y. œ 9C Ü DC î EE þ FE ỵ 1EF5 7925 E1 BB B5 dd Ç C7 ð F0 ñ F1 ® AE đ 0111 273 C4 91 A' Á C1 Á C1 AÙ 41 D9 A¸ 41 B8 Á 00C1 193 C3 81 A` € 80 À C0 AØ 41 D8 Aµ 41 B5 À 00C0 192 C3 80 A? 81 Ä C4 AÛ 41 DB A¶ 41 B6 Ả 1EA2 7842 E1 BA A2 A~ ‚ 82 à C3 AÕ 41 D5 A· 41 B7 à 00C3 195 C3 83 A. 02 € 80 AÏ 41 CF A¹ 41 B9 Ạ 1EA0 7840 E1 BA A0 A( ˆ 88 Å C5 AÊ 41 CA ¡ A1 Ă 0102 258 C4 82 A(' 8D 81 AÉ 41 C9 ¡¾ A1 BE Ắ 1EAE 7854 E1 BA AE A(` Ž 8E ‚ 82 AÈ 41 C8 ¡» A1 BB Ằ 1EB0 7856 E1 BA B0 A(? 8F [1] 02 AÚ 41 DA ¡¼ A1 BC Ẳ 1EB2 7858 E1 BA B2 A(~ ð F0 05 AÜ 41 DC ¡½ A1 BD Ẵ 1EB4 7860 E1 BA B4 A(. 04 ƒ 83 AË 41 CB ¡Æ A1 C6 Ặ 1EB6 7862 E1 BA B6 79 A^  C2  C2 A 41 C2 ¢ A2  00C2 194 C3 82 A^' ƒ 83 „ 84 AÁ 41 C1 ¢Ê A2 CA Ấ 1EA4 7844 E1 BA A4 A^` „ 84 … 85 AÀ 41 C0 ¢Ç A2 C7 Ầ 1EA6 7846 E1 BA A6 A^? … 85 † 86 AÅ 41 C5 ¢È A2 C8 Ẩ 1EA8 7848 E1 BA A8 A^~ 1C 06 Aà 41 C3 ¢É A2 C9 Ẫ 1EAA 7850 E1 BA AA A^. 03 ‡ 87 AÄ 41 C4 ¢Ë A2 CB Ậ 1EAC 7852 E1 BA AC E' É C9 É C9 EÙ 45 D9 EÐ 45 D0 É 00C9 201 C3 89 E` × D7 È C8 EØ 45 D8 EÌ 45 CC È 00C8 200 C3 88 E? Þ DE Ë CB EÛ 45 DB EÎ 45 CE Ẻ 1EBA 7866 E1 BA BA E~ þ FE ˆ 88 EÕ 45 D5 EÏ 45 CF Ẽ 1EBC 7868 E1 BA BC E. 05 ‰ 89 EÏ 45 CF EÑ 45 D1 Ẹ 1EB8 7864 E1 BA B8 E^ Ê CA Ê CA E 45 C2 £ A3 Ê 00CA 202 C3 8A E^' 90 Š 8A EÁ 45 C1 £Õ A3 D5 Ế 1EBE 7870 E1 BA BE E^` “ 93 ‹ 8B EÀ 45 C0 £Ò A3 D2 Ề 1EC0 7872 E1 BB 80 E^? ” 94 Œ 8C EÅ 45 C5 £Ó A3 D3 Ể 1EC2 7874 E1 BB 82 E^~ • 95 8D Eà 45 C3 £Ô A3 D4 Ễ 1EC4 7876 E1 BB 84 80 E^. 06 Ž 8E EÄ 45 C4 £Ö A3 D6 Ệ 1EC6 7878 E1 BB 86 I' ´ B4 Í CD Í CD IÝ 49 DD Í 00CD 205 C3 8D I` µ B5 Ì CC Ì CC I× 49 D7 Ì 00CC 204 C3 8C I? · B7 › 9B Æ C6 IØ 49 D8 Ỉ 1EC8 7880 E1 BB 88 I~ ¸ B8 Î CE Ó D3 IÜ 49 DC Ĩ 0128 296 C4 A8 I. 10 ˜ 98 Ò D2 IÞ 49 DE Ị 1ECA 7882 E1 BB 8A O' ¹ B9 Ó D3 OÙ 4F D9 Oã 4F E3 Ó 00D3 211 C3 93 O` ¼ BC Ò D2 OØ 4F D8 Oß 4F DF Ò 00D2 210 C3 92 O? ½ BD ™ 99 OÛ 4F DB Oá 4F E1 Ỏ 1ECE 7886 E1 BB 8E O~ ¾ BE A0 OÕ 4F D5 Oâ 4F E2 Õ 00D5 213 C3 95 O.  11 š 9A OÏ 4F CF Oä 4F E4 Ọ 1ECC 7884 E1 BB 8C O^ Ô D4 Ô D4 O 4F C2 ¤ A4 Ô 00D4 212 C3 94 O^' – 96 8F OÁ 4F C1 ¤è A4 E8 Ố 1ED0 7888 E1 BB 90 O^` — 97 90 OÀ 4F C0 ¤å A4 E5 Ồ 1ED2 7890 E1 BB 92 O^? ˜ 98 ‘ 91 OÅ 4F C5 ¤æ A4 E6 Ổ 1ED4 7892 E1 BB 94 O^~ ™ 99 ’ 92 Oà 4F C3 ¤ç A4 E7 Ỗ 1ED6 7894 E1 BB 96 81 O^.  12 “ 93 OÄ 4F C4 ¤é A4 E9 Ộ 1ED8 7896 E1 BB 98 O+ ÷ F7 ´ B4 Ô D4 ¥ A5 Ơ 01A0 416 C6 A0 O+' 9D • 95 ÔÙ D4 D9 ¥í A5 ED Ớ 1EDA 7898 E1 BB 9A O+` ž 9E – 96 ÔØ D4 D8 ¥ê A5 EA Ờ 1EDC 7900 E1 BB 9C O+? Ÿ 9F — 97 ÔÛ D4 DB ¥ë A5 EB Ở 1EDE 7902 E1 BB 9E O+~ ¦ A6 ³ B3 ÔÕ D4 D5 ¥ì A5 EC Ỡ 1EE0 7904 E1 BB A0 O+.  13 ” 94 ÔÏ D4 CF ¥î A5 EE Ợ 1EE2 7906 E1 BB A2 U' Ú DA Ú DA UÙ 55 D9 Uó 55 F3 Ú 00DA 218 C3 9A U` ¨ A8 Ù D9 UØ 55 D8 Uï 55 EF Ù 00D9 217 C3 99 U? Ñ D1 œ 9C UÛ 55 DB Uñ 55 F1 Ủ 1EE6 7910 E1 BB A6 U~ ¬ AC 9D UÕ 55 D5 Uò 55 F2 Ũ 0168 360 C5 A8 U.  14 ž 9E UÏ 55 CF Uô 55 F4 Ụ 1EE4 7908 E1 BB A4 U+ Ð D0 ¿ BF Ö D6 ¦ A6 Ư 01AF 431 C6 AF U+' AD º BA ÖÙ D6 D9 ¦ø A6 F8 Ứ 1EE8 7912 E1 BB A8 U+` ¯ AF » BB ÖØ D6 D8 ¦õ A6 F5 Ừ 1EEA 7914 E1 BB AA U+? ± B1 ¼ BC ÖÛ D6 DB ¦ö A6 F6 Ử 1EEC 7916 E1 BB AC 82 U+~ 1D ÿ FF ÖÕ D6 D5 ¦÷ A6 F7 Ữ 1EEE 7918 E1 BB AE U+.  15 ¹ B9 ÖÏ D6 CF ¦ù A6 F9 Ự 1EF0 7920 E1 BB B0 Y' Ý DD Ý DD YÙ 59 D9 Yý 59 FD Ý 00DD 221 C3 9D Y` ² B2 Ÿ 9F YØ 59 D8 Yú 59 FA Ỳ 1EF2 7922 E1 BB B2 Y? ý FD  14 YÛ 59 DB Yû 59 FB Ỷ 1EF6 7926 E1 BB B6 Y~ ³ B3 19 YÕ 59 D5 Yü 59 FC Ỹ 1EF8 7928 E1 BB B8 Y. 19 - 1E Î CE Yþ 59 FE Ỵ 1EF4 7924 E1 BB B4 DD ñ F1 Ð D0 Ñ D1 § A7 Ð 0110 272 C4 90 83 Thuật toán Knuth-Morris-Pratt Pattern Matching. S:array[0…m] of symbol; T:array[0…n] of symbol; N:array[0…n] of symbol; q:={Start at left end of T}; while q<=n do begin { Characters left in T:find longest match starting with T[q]} k:=0; {start match at left end of S} j:=q; {first symbol of pattern} last := q; {last symbol of pattern} N[q] :=q-1; {initialize N[q]} IN := q-1; {initialize computation of N[q+1,…]} Loop {loop with exit from the middle} {try to find a match for T[q] .. T[last] } {T[q]…T[ last-1] has already been matched} kOld :=k; {save last point of old match, if any} while (j<=last) and (k<=m) do begin while (j>=q) and (S[k]T[j]) do j:=N[j]; k:=k+1 ; j:=j+1; end until (j<=last) || (last =n); {exit from middle} {found match; now increase last and compute N[last]} while (iN>=q) and (T[last] T[iN]) do iN := N[iN]; last := last +1; iN :=iN +1; end {end of loop} {print match} if j>last then begin {found match for tail of T} 84 print(k-(n-q+1),q,n-q+1); q:=q+1; end else begin {last match failed; take previous one} print (kOld –(last -q),q,last-q) q:=last; end end