Luận văn Một số phương pháp thiết kế thuật toán cơ bản trong tính toán song song và ứng dụng

thường có thêm một số đại lượng đo lường khác. Độ phức tạp thời gian của thuật toán song song không chỉ đơn giản là việc đếm số câu lệnh cơ bản như trong thuật toán tuần tự mà thay vào đó nó phụ thuộc vào các phép toán cơ bản này có thể được thực hiện trên bộ xử lý như thế nào. Bên cạnh độ phức tạp thời gian độ phức tạp về số bộ xử lý cũng là một đại lượng quan trọng trong phân tích thuật toán song song. Thiết kế thuật toán song song hiệu quả bao gồm việc lựa chọn cấu trúc dữ liệu phù hợp, phân bố bộ xử lý và cuối cùng là thực hiện thuật toán. Ba đại lượng này tác động lẫn nhau như một tổ chức tính toán. Đánh giá thuật toán song song Độ phức tạp tính toán của thuật toán song song không chỉ phụ thuộc vào kích cỡ của dữ liệu đầu vào mà còn phụ thuộc vào kiến trúc máy tính song song và số lượng các bộ xử lý được phép sử dụng trong hệ thống. Độ phức tạp thời gian là thước đo quan trọng nhất đánh giá mức độ hiệu quả của thuật toán song song. Chúng ta giả thiết rằng mô hình tính toán có p bộ xử lý. Nghĩa là mức độ song song là có giới hạn. Ngược lại, mức độ song song không bị giới hạn khi số các bộ xử lý là không bị chặn. Độ phức tạp thời gian của thuật toán song song sử dụng bộ xử lý để giải một bài toán có kích cỡ là hàm xác định thời gian cực đại trôi qua giữa thời điểm bắt đầu thực hiện thuật toán bởi một bộ xử lý và thời điểm kết thúc của các bộ xử lý đối với bộ dữ liệu vào bất kỳ. Có hai loại thao tác khác nhau trong các thuật toán song song: 1. Các phép toán cơ sở như +, -, *, /, AND, OR, v.v 2. Các phép toán truyền dữ liệu trên các kênh truyền. Độ phức tạp thời gian của thuật toán song song được xác định bởi số các phép toán cơ sở và số các bước truyền tải dữ liệu giữa các bộ xử lý với nhau. Từ đó suy ra, độ phức tạp thời gian của thuật toán song song không chỉ phụ thuộc vào mô hình tính toán mà còn phụ thuộc vào số bộ xử lý được sử dụng. Nói chung, chương trình tính toán song song thường bắt đầu bằng việc nhập dữ liệu vào bộ nhớ và kích hoạt một phần tử xử lý. Mỗi bước tính toán, phần tử xử lý này có thể đọc một số dữ liệu từ bộ nhớ, thực hiện một số phép toán cơ sở và ghi kết quả vào bộ nhớ riêng hoặc bộ nhớ chung. Đồng thời mỗi bước tính toán, một phần tử xử lý có thể kích hoạt một hay một số phần tử xử lý khác. Thực tế thì các máy tính đều có số bộ xử lý là hữu hạn, nên những thuật toán song song không bị giới hạn chỉ có nghĩa sử dụng khi chúng có thể chuyển đổi về thuật toán song song bị giới hạn. Thời gian tính toán song song Để đánh giá được độ phức tạp tính toán của các thuật toán song song, ngoài số bước tính toán chúng ta còn cần đánh giá thời gian truyền thông của các tiến trình. Trong một hệ thống truyền thông điệp, thời gian truyền thông điệp cũng phải được xem xét trong thời gian thực hiện của thuật toán. Thời gian thực hiện song song: ký hiệu là gồm hai phần và . (1.1) Trong đó, là thời gian tính toán và là thời gian truyền thông dữ liệu. Thời gian tính toán được xác định giống như thuật toán tuần tự. Khi có nhiều tiến trình thực hiện đồng thời thì chỉ cần tính thời gian thực hiện của tiến trình phức tạp nhất. Trong phân tích độ phức tạp tính toán, chúng ta luôn giả thiết rằng, tất cả các bộ xử lý là giống nhau và cùng một tốc độ xử lý như nhau. Đối với những cụm máy tính không thuần nhất thì điều này không đảm bảo nên việc đánh giá thời tính toán của những hệ như thế là rất phức tạp. Thời gian truyền thông lại phụ thuộc vào kích cỡ của các thông điệp, vào cấu hình kết nối mạng đường truyền và cả cách thức truyền tải thông điệp. Công thức ước lượng thời gian truyền thông được xác định như sau: . (1.2) Trong đó, là thời gian cần thiết để gửi những thông điệp không phải là dữ liệu. Nó bao gồm cả thời gian để đóng gói thông điệp ở nơi gửi và thời gian mở gói ở nơi nhận. Để đơn giản chúng ta giả thiết thời gian này là hằng số. là thời gian cần thiết để chuyển một mục dữ liệu (data word) từ nơi gửi tới nơi nhận, được giả thiết là hằng số và là số từ dữ liệu được trao đổi trong hệ thống. Chi phí cho một thuật toán song song được xác định bằng tích của thời gian tính toán song song và số bộ xử lý được sử dụng. Chi phí này phản ánh tổng số thời gian mà một bộ xử lý dùng để giải quyết bài toán. Một thuật toán song song sử dụng bộ vi xử lý để giải quyết bài toán đặt ra trong đơn vị thời gian, sử dụng bộ xử lý trong đơn vị thời gian, khi đó chi phí cho thuật toán song song : . (1.3) Hệ số tăng tốc cũng là yếu tố đáng chú ý khi đánh giá thuật toán song song được song song hóa từ một thuật toán tuần tự. Hệ số tăng tốc là tỉ lệ giữa thời gian thực hiện của thuật toán tuần tự ts và thời gian thực hiện của thuật toán song song với bộ xử lý (1.4) Giả sử các bộ xử lý trong hệ thống song song hoàn toàn giống với bộ xử lý sử dụng trong tính toán tuần tự và ts là thời gian thực hiện bài toán bằng tính toán tuần tự tối ưu nhất. Hệ số tăng tốc lí tưởng đạt được khi . Rõ ràng khả năng tăng tốc càng lớn thì giải thuật song song càng tốt. Tuy nhiên, năm 1967 Amdahl đã đưa ra luật về giới hạn khả năng tăng tốc như sau: Khi tăng số lượng bộ xử lý trong máy tính song song, khối lượng công việc được phân phối cho nhiều bộ xử lý thực hiện. Mục tiêu chính là tìm được kết quả bài toán nhanh nhất có thể hay nói cách khác là giảm đến mức tối đa thời gian tính toán. Luật Amdahl: luật này phát biểu rằng nếu là tỉ lệ có thể song song hóa của thuật toán tuần tự thì hệ số tăng tốc lớn nhất có thể đạt được khi sử dụng bộ xử lý là . Ta dễ dàng thấy được, là hàm tăng theo và nên . Ta có biểu đồ thể hiện luật Amdahl như hình 1.4. Hình 1.10 Luật Amdahl Hiệu suất của tính toán song song là tỉ số giữa hệ số tăng tốc và số các phần tử xử lý trong hệ thống song song: (1.5) Thuật toán song song có thể có độ phức tạp lớn hơn thuật toán tuần tự, do đó rất khó để đánh giá thuật toán song song. Kết quả đạt được thường được đánh giá bằng thực nghiệm chương trình. Mô hình lập trình truyền thông điệp – MPI song song Giới thiệu mô hình truyền thông điệp Có rất nhiều ngôn ngữ lập trình và các thư viện được xây dựng nên để dành cho lập trình song song. Mô hình truyền thông điệp chuẩn MPI (MessagePassing Interface) là một giao diện chuẩn cho phép nhiều máy tính giao tiếp với nhau, được sử dụng trong các cụm máy tính và siêu máy tính và là một trong các mô hình cổ nhất được sử dụng rộng rãi nhất trong các mô hình dùng cho lập trình trên các máy tính song song bởi vì nó yêu cầu tối thiểu về phần cứng. Có hai tính chất quan trọng tạo nên bản chất của mô hình truyền thông điệp: thứ nhất là nó giả sử không gian địa chỉ được phân chia và thứ hai là nó chỉ hỗ trợ song song hóa tường minh. Hình 1.11: Sự trao đổi thông điệp giữa hai tiến trình Lập trình truyền thông điệp - MPI Giới thiệu về MPI MPI là giao thức độc lập ngôn ngữ sử dụng cho các máy tính song song. MPI là một giao diện lập trình ứng dụng truyền thông điệp với mục đích là đem lại hiệu năng cao, khả năng mở rộng và linh hoạt. MPI là một thư viện chương trình mà có thể được gọi trực tiếp từ chương trình Fortran, C/C++ và bất cứ ngôn ngữ nào khác tương thích với thư viện hàm (như C#, Java và Python). Lợi ích của việc sử dụng MPI là tính khả chuyển (vì MPI được cài đặt cho hầu hết các kiến trúc bộ nhớ phân tán) và tốc độ (vì mỗi cài được được tối ưu hoá về nguyên lý cho phần cứng mà nó thực thi trên đó). MPI sử dụng đặc tả độc lập ngôn ngữ (LIS) cho các lời gọi hàm. Hiện nay, các chuẩn MPI có hai phiên bản phổ biến là 1.2 (gọi tắt là MPI-1) chủ yếu là truyền thông điệp và có môi trường hoạt động tĩnh, và phiên bản MPI-2.1 (gọi tắt là MPI-2) bao gồm nhiều đặc điểm mới như vào/ra song song, quản lý tiến trình động và truy cập bộ nhớ từ xa. MPI-2 gần như bao hàm toàn bộ MPI-1, mặc dù có một số hàm đã bị loại bỏ. Vì thế, các chương trình viết theo MPI-1.2 vẫn có thể tương thích với chuẩn MPI-2. Chức năng của MPI Chức năng của thư viện MPI bao gồm (nhưng không hạn chế) các hoạt động gửi nhận điểm-điểm, lựa chọn topo tiến trình logic dạng hình học phẳng hay đồ thị, trao đổi dữ liệu giữa các cặp tiến trình, phối hợp kết quả từng phần của quá trình tính toán, các nút đồng bộ cũng như các thông tin về mạng .v.v. Trong chương trình MPI thì số lượng các tiến trình là cố định, các tiến trình có thể thực hiện trao đổi thông tin một-một để gửi dữ liệu từ tiến trình này sang tiến trình khác. Một nhóm các tiến trình có thể thực hiện các thao tác kết hợp để thực hiện các thao tác chung và phổ biến như là phép công hay broadcast. MPI có khả năng thăm dò các thông điệp có hỗ trợ truyền thông bất đồng bộ. Các thuật toán chỉ tạo ra một tác vụ trên một bộ xử lý có thể apd dụng trực tieeos các thủ tục trao đổi kết hợp hay một-một nhằm đáp ứng các yêu cầu truyển thông. TRong khi đó các thuật toán tác vụ động hay dựa trên sự thực thi đồng thời của nhiều tác vụ trên cùng một bộ xử lý, thì cần phải điều chỉnh lại cho thích hợp với mô hình MPI. Một số khái niệm về MPI Bộ truyền thông: Bộ truyền thông chịu trách nhiệm kết nối các tiến trình sử dụng MPI. Trong truyền thông, mỗi tiến trình có một bộ nhận diện độc lập và các tiến trình được sắp xếp theo một thứ tự topo nhất định. MPI cũng có các nhóm, nhưng chủ yếu phục vụ cho tổ chức và tái tổ chức các tiến trình con, trước khi các bộ truyền thông khác được tạo ra. MPI hiểu được các hoạt động nhóm truyền thông nội bộ đơn, và hoạt động truyền thông liên nhóm. Trong MPI-1, hoạt động truyền thông của nhóm đơn là phổ biến nhất, còn truyền thông liên nhóm giữ vai trò quan trọng nhất trong MPI-2 để mở rộng cho quản lý tiến trình động và truyền thông tập thể. Cơ sở điểm-điểm: Các hoạt động điểm-điểm, thực sự hữu ích trong truyền thông không đồng đều, mỗi tiến trình lặp đi lặp lại trao đổi các vùng dữ liệu với tiến trình khác giữa các bước tính toán, trong kiến trúc chủ-tớ, tiến trình chủ thường xuyên gửi dữ liệu cho tiến trình kia mỗi khi có một tác vụ hoàn thành. MPI-1 đặc tả cơ chế truyền thông điểm-điểm không khoá và có khoá. Cơ sở cộng tác tập thể: Chức năng hoạt động tập thể trong MPI liên quan đến truyền thông giữa mọi tiến trình trong nhóm. Một hàm, hay gặp, dạng này là MPI_Bcast. Hàm này lấy dữ liệu từ một nút đặc biệt nào đó và gửi thông điệp tới mọi tiến trình trong nhóm. Một hàm khác đó là MPI_Reduce, hàm này dùng để lấy dữ liệu từ mọi tiến trình khác trong nhóm. Các loại hàm này thường hữu ích khi bắt đầu hoặc kết thúc quá trình tính toán phân tán lớn. Còn có một số hàm phức tạp hơn như MPI_Alltoall, hàm này tái sắp xếp phần dữ liệu từ mỗi tiến trình để nút thứ lấy dữ liệu phần tử thứ n từ mỗi nút. Các loại dữ liệu: Nhiều hàm MPI cần chúng ta đặc tả loại dữ liệu được gửi giữa các bộ xử lý. Điều này xuất phát từ việc các tham số của hàm MPI đều là các biến, không phải là loại được định nghĩa trước. Nếu loại dữ liệu là chuẩn như int, char, double.., thì ta có thể sử dụng các loại dữ liệu định nghĩa của MPI như MPI_INT, MPI_CHAR, MPI_DOUBLE Giả sử ta có một mảng các số nguyên, và mọi bộ xử lý muốn gửi các mảng dữ liệu đó tới nút gốc, thì có thể gọi hàm MPI_Gather. Ví dụ: int array[100]; int root, total_p, *receive_array; MPI_Comm_size(comm, &total_p); receive_array=(int *) malloc(total_p*100*sizeof(int)); MPI_Gather(array, 100, MPI_INT, receive_array, 100, MPI_INT, root, comm); Truyền thông một phía (MPI-2): MPI-2 xác định ba thao tác truyền thông một phía, bao gồm Put, Get, và Accumulate, dùng để ghi, đọc đối với bộ nhớ từ xa, và một thao thác rút gọn một số tác vụ trên cùng một bộ nhớ đó. Các hàm này thường được sử dụng trong các thuật toán mà việc đồng bộ là không thuận tiện (ví dụ như nhân ma trận phân tán), hoặc ở những bài toán mà nhiệm vụ cần cân bằng tải trong khi các bộ xử lý khác đang sử dụng dữ liệu. Quản lý tiến trình động (MPI-2): Vấn đề cốt lõi của đặc điểm này đó là “khả năng của một tiến trình MPI có thể tạo ra một tiến trình MPI mới hoặc để thiết lập một giao tiếp với các tiến trình MPI để có thể khởi động rời rạc nhau”. Chuẩn MPI-2 mô tả ba giao diện chính để các tiến trình MPI có thể thiết lập giao tiếp động, đó là: MPI_Comm_spawn, MPI_Comm_accept/MPI_Comm_connect và MPI_Comm_join. Hàm MPI_Comm_spawn cho phép một tiến trình MPI có thể nhân bản một số tiến trình MPI nữa. Tập hợp các tiến trình MPI mới nhân bản này tạo thành một bộ truyền thông MPI_COMM_WORLD và có thể giao tiếp với tiến trình cha. Hàm MPI_Comm_spawn_multiple là một biến thể, nó cho phép các tiến trình nhân bản khác nhau với các tham số khác nhau. MPI vào/ra (MPI-2): Đặc điểm vào ra song song được giới thiệu với MPI-2, đôi khi còn được gọi là MPI-IO, liên quan đến một tập các hàm cho phép có thể giảm bớt khó khăn trong quản lý vào/ra trên các hệ thống phân tán, cũng như là cho phép các tệp có thể được truy cập dễ dàng hơn. Cấu trúc chương trình MPI Các tập tin thư viện: liên quan đến các hàm các thủ tục, các kiểu dữ liệu. Bao gồm tập tin .h như mpi.h mpio.h và các tập tin khác. Thông thường người lập trình chỉ cần dùng thư viện mpi.h là đủ. Môi trường MPI: Tất cả các kiểu dữ liệu, các thủ tục, các giá trị defined nếu muốn dùng nó, sau khi gọi các tập tin thư viện liên kết thì phải khởi tạo môi trường sử dụng thì mới có thể dùng được các chức năng mà MPI cung cấp. Các thủ tục, hàm MPI: sử dụng giống như các hàm trong C và cả các ngôn ngữ khác như Fortran Các tập tin thư viện Khởi tạo môi trường MPI Thực hiện các thủ tục hàm của MPI Thoát khỏi môi trường MPI Hình 1.12: Cấu trúc chương trình MPI Chương 2 – SONG SONG HÓA THUẬT TOÁN TÌM XÂU CON CHUNG DÀI NHẤT Đặt vấn đề Tin sinh học (bioinformatics) là một lĩnh vực khoa học sử dụng các công nghệ của ngành toán học ứng dụng, tin học, thống kê, khoa học máy tính và toán sinh học (biomathematics) để nghiên cứu thông tin về cuộc sống từ góc độ sinh học. Các ứng dụng của tin sinh học tập trung vào nghiên cứu ở cấp độ phân tử để hiểu sâu sắc về cấu trúc cơ bản và các quá trình ở cấp độ tế bào và phân bào. Những lĩnh vực nghiên cứu chính bao gồm bắt cặp trình tự (sequence alignment), bắt cặp cấu trúc protein (protein structural alignment), dự đoán cấu trúc protein (protein structural prediction), dự đoán biểu hiện gen (gene expression), tương tác protein-protein (protein-protein interaction), mô hình hoá quá trình tiến hoá. Hai lĩnh vực phát triển cụ thể của tin sinh học là di truyền học và nghiên cứu protein. Các ứng dụng chủ tập trung vào việc sử dụng thông tin kết hợp với tính toán trong việc tìm hiểu vai trò kết hợp giữa DNA, RNA và protein trong một cơ thể sống. Bài toán tìm dãy con chung dài nhất của nhiều chuỗi được ứng dụng nhiều trong các lĩnh vực sinh học và di truyền học tính toán. Đã có nhiều phương pháp có hiệu quả cho bài toán này với phương pháp quy hoạch động song song cho trường hợp đặc biệt là so khớp hai chuỗi. Tuy nhiên, do kích thước của dữ liệu tin sinh học ngày càng đồ sộ và phức tạp, nhu cầu giải nhanh bài toán so khớp xâu nói chung và đặc biệt là bài toán tìm xâu còn chung dài nhất với số xâu lớn hơn hai đang trở nên rất cấp thiết. Nội dung chương này sẽ tập trung vào giải quyết bài toán tìm xâu con chung dài nhất với số xâu lớn hơn hai với chiến lược song song hóa tính toán. Bài toán tìm xâu con chung dài nhất Định nghĩa xâu. Kí hiệu là các kí tự trong bảng chữ cái . Một xâu được xác định như một dãy liên tiếp của các kí tự. Với một xâu ta có một số quy ước về ký hiệu như sau: là độ dài xâu . Nếu thì là xâu rỗng và được ký hiệu là . là ký tự thứ của xâu . Định nghĩa xâu con. Cho là một xâu có độ dài trên bảng chữ cái . Một xâu là một xâu con của , nếu : , và Định nghĩa xâu con chung dài nhất Cho là một tập các xâu trên bảng chữ cái với độ dài tương ứng. Xâu con chung dài nhất của tập là một xâu thỏa mãn: (i) là một xâu con của , . (ii) có độ dài lớn nhất thỏa mãn (i). Ví dụ: Cho 3 xâu , , . Khi đó xâu con chung dài nhất của cả ba xâu là . Trong tin sinh học, tùy thuộc vào kiểu của dữ liệu, kích thước của bảng chữ cái thì độ dài của xâu ký tự rất đa dạng. Bảng 1 dưới đây thống kê về độ dài xâu ký tự của một số dữ liệu tin sinh học [12]. Bảng 2.1 Độ dài xâu ký tự của một số dữ liệu tin sinh học Dữ liệu sinh học Bảng chữ cái Độ dài xâu ký tự Protein ~ 102 – 104 ARN ~ 102 – 104 Gen ~ 102 – 104 ADN ~ 103 – 1012 Bảng 2.1 cho thấy độ dài của các xâu trong dữ liệu tin sinh học là rất lớn. Do đó việc tìm ra xâu con chung dài nhất giữa các xâu đòi hỏi tính toán rất phức tạp và tốn rất nhiều thời gian. Thuật toán quy hoạch động giải bài toán tìm xâu con chung dài nhất. Giả sử ta có hai dãy và . Ta có là một xâu con chung bất kỳ của và . Tiền tố thứ của xâu là một dãy con của bao gồm từ phần tử ban đầu đến phần tử tứ thứ của nghĩa là , . Khi đó ý tưởng giải bài toán là tính xâu con chung dài nhất cho mọi khả năng các cặp của tiền tố hai dãy đã cho. Ký hiệu là độ dài của dãy con chung dài nhất và . Khi đó đại lượng là xâu con chung dài nhất của toàn bộ hai chuỗi đã cho. Các bước tính như sau: Bước cơ sở: , Nếu một trong những xâu đã cho là rỗng thì dãy con chung dài nhất cũng rỗng và có độ dài bằng 0. Ký tự cuối cùng của tiền tố bằng nhau: Giả sử . Khi đó phần tử cuối cùng của xâu con chung dài nhất và là một xâu con chung dài nhất của xâu và . Thật vậy, nếu thì ta ghép thêm vào để có được dãy con chung của và có chiều dài , mâu thuẫn với giả thiết cho rằng là dãy con chung dài nhất của và . Như vậy ta phải có . Vậy thì là xâu con chung dài nhất của và có độ dài . Như vậy, nếu thì . Ký tự cuối cùng của tiền tố không bằng nhau: Giả sử . Khi đó phần tử ( hoặc ) nghĩa là là xâu con chung dài nhất của và ( hoặc là xâu con chung dài nhất của và ). Thật vậy, nếu , thì là xâu con chung của và . Nếu có một xâu con chung của và , điều này mâu thuẫn với giả thiết là xâu con chung dài nhất của và . Như vậy, và không đồng thời nằm trong xâu con chung dài nhất, nghĩa là hoặc nằm trong xâu con chung dài nhất, hoặc nằm trong xâu con chung dài nhất (có khả năng cả hai đều không nằm trong xâu con chung dài nhất). Vậy nếu thì . Công thức truy hồi cho xâu con chung dài nhất được thiết lập như sau: (2.1) Thuật toán tuần tự tìm xâu con chung dài nhất. Dựa trên công thức truy hồi, thuật toán tiếp nhận hai chuỗi hữu hạn, mỗi giá trị sẽ được lưu vào mảng . Việc tính toán sẽ được thực hiện theo các hàng của mảng và cột trước đó theo công thức trên. Việc truy xuất lại mảng phương án để tìm ra xâu con chung dài nhất sẽ đi từ điểm của ma trận phương án. Ta lập mảng thứ hai để ghi những giải pháp tối ưu. Thuật toán trả về mảng, và chứa chiều dài xâu con chung dài nhất của và . Thuật toán tìm xâu con chung dài nhất (lengthLCS) function lengthLCS(X[1..m], Y[1..n]) Đầu vào: Hai chuỗi X[1..m], Y[1..n]) Đầu ra: Dãy con chung lớn nhất giữa hai chuỗi V, W. 1. Khai báo c[1..m, 1..n] và b[1..m, 1..n] 2. m:= length (X); n= length (Y) 3. c(i=0 to m,0) = 0 4. c(0,j=0 to n) = 0 5. Loop i over length (X) 6. Loop j over length (Y) 7. c(i,j) = MAX [ c(i-1,j), c(i, j-1), c(i-1,j-1)+1 if X(i) = Y(j) ] 8. b(i,j) = UP if c(i,j) = c(i-1,j) 9. b(i,j) = LEFT if c(i,j) = c(i,j-1) 10. b(i,j) = DIAGONAL if c(i,j) = c(i-1,j-1) +1 11. Tìm giá trị lớn nhất trong hàng và cột cuối cùng của c 12. Return ( c và b) Thuật toán 2.1. Thuật toán tuần tự tìm dãy con chung dài nhất Ví dụ: Cho hai xâu : , . Tính giá trị sau đó lưu vào mảng A G G T G C T G 0 1 1 1 1 1 1 C 0 1 1 1 1 2 1 C 0 1 1 1 1 2 1 T 0 1 1 2 2 2 3 A 1 1 1 2 2 2 3 C 0 1 1 2 2 3 3 Mảng ghi những giải pháp tối ưu: A G G T G C T G ­ 0 Õ 1 ¬1 ¬1 ¬1 ¬1 ¬1 C ­ 0 ­ 1 ­ 1 ­ 1 ­ 1 Õ 2 ­ 1 C ­ 0 ­ 1 ­ 1 ­ 1 ­ 1 ­2 ­ 1 T ­ 0 ­ 1 ­ 1 Õ 2 ¬2 ­ 2 Õ 3 A Õ 1 ­ 1 ­ 1 ­ 2 ­ 2 ­ 2 ­ 3 C ­ 1 ­ 1 ­ 1 ­ 2 ­ 2 Õ 3 ­ 3 Như vậy: thời gian thực hiện thuật toán là . Nghiệm của thuật toán sẽ được tìm như sau: function printLCS(b,X[1..m],i,j) Đầu vào: Ma trận b, Mảng X[1..m] Đầu ra: Mảng LCS của X và Y Các bước: 1. If i = 0 or j = 0 return 2. if b(i,j) = DIAGONAL THEN 3. printLCS(b,X,i-1,j-1) 4. write X(i) 5. ELSE 6. IF b(i,j) = UP THEN 7. printLCS(b,X,i-1,j) 8. ELSE 9. printLCS(b,X,i,j-1) Thuật toán 2.2. Thuật toán tuần tự in ra dãy con chung dài nhất Phương pháp phần tử trội trong bài toán xâu con chung dài nhất. Thuật toán quy hoạch động giải quyết bài toán xâu con chung dài nhất khá hiệu quả với ma trận phương án có thể truy xuất lại xâu rất nhanh. Tuy nhiên khi dữ liệu lớn với số chuỗi tăng lên, phương pháp lưu trữ bằng ma trận như vậy sẽ không hiệu quả. Đặc biệt, khi độ dài chuỗi tăng dần, kích thước ma trận sẽ tăng đột biến và khi đạt đến một cỡ đủ lớn thì máy tính sẽ bị tràn bộ nhớ. Để giải quyết vấn đề này một cách hiệu quả, Hakata và Imai [8] đã đưa ra phương pháp phần tử trội để lưu trữ các phương án tìm xâu con chung dài nhất. Phương pháp này như sau: Giả sử là ma trận phương án với chiều tương đương với xâu ký tự trên bảng chữ cái . là một điểm trên ma trận với mỗi thành phần số nguyên là các vị trí tương ứng trên xâu . Giá trị của vị trí trong ma trận được ký hiệu là . Tương tự như vậy, với một xâu , ký tự ở vị trí thứ trong xâu được ký hiệu là . Định nghĩa điểm khớp Một điểm trong được gọi là một điểm “khớp” nếu: . Điểm khớp tương ứng với một ký tự được ký hiệu là .[8] Định nghĩa điểm trội Một điểm được gọi là trội hơn điểm nếu . Nếu điểm trội hơn điểm thì ta ký hiệu là . Tương tự như vậy, một điểm được gọi là trội hơn hẳn điểm nếu . Nếu điểm trội hơn điểm thì ta ký hiệu là . Một điểm không trội hơn điểm nếu sao cho . Nếu điểm không trội hơn điểm thì ta ký hiệu là . [8] Định nghĩa điểm k trội Một điểm khớp được gọi là một điểm trội (phần tử trội) nếu: ; Không có một điểm khớp nào thỏa mãn (i) và . Ký hiệu là tập tất cả các điểm trội. Ký hiệu là tập tất cả các điểm trội. [8] Định nghĩa điểm cha Một điểm khớp được gọi là điểm cha của điểm , nếu và không có một điểm khớp nào thỏa mãn . Ký hiệu là tập tất cả các điểm cha của điểm , là tập tất cả các điểm cha của tập các điểm và là tập tất cả các điểm cha () của tập các điểm . [8] Định nghĩa thành phần nhỏ nhất: Một điểm trong tập các điểm được gọi là thành phần nhỏ nhất của , nếu . Nếu , khi đó thành phần duy nhất chính là thành phần nhỏ nhất của . Bảng 2.2 Ví dụ về các điểm trội trong ma trận phương án. H E A G A W G H E E A 0 0 1 1 1 1 1 1 1 1 W 0 0 1 1 1 2 2 2 2 2 H 1 1 1 1 1 2 2 3 3 3 E 1 2 2 2 2 2 2 3 4 4 A 1 2 3 3 3 3 3 3 4 4 E 1 2 3 3 3 3 3 3 4 5 Bảng 2 nêu ví dụ về các phần tử trội trong ma trận phương án của bài toán tìm xâu con chung dài nhất của hai xâu và . Các điểm được khoanh tròn là các điểm trội. Các điểm được khoanh ô vuông là các điểm có vị trí khớp nhưng không phải là điểm trội. Cho là xâu ký tự trên bảng chữ cái và là ma trận phương án. Khi đó chúng ta có nhận xét sau: Mỗi một vị trí trên xâu con chung dài nhất của xâu ký tự trên là một vị trí khớp trên ma trận phương án . Như vậy chúng ta chỉ cần tập trung vào tất cả các điểm khớp trên ma trận phương án . Số lượng các mức của phần tử trội chính là độ dài của xâu con chung dài nhất của xâu. Hơn nữa, tại mỗi mức sẽ có ít nhất một phần tử trội tương ứng với vị trí của ký tự thứ trong xâu con chung dài nhất của xâu. Các phần tử trội của có thể được tính một cách thông qua tập các phần tử trội trước đó, tức là việc tính toán sẽ trực tiếp dựa vào . Tập các phần tử trội chính là tập con của tập các điểm cha của tập hay . Phần tử nhỏ nhất trong tập các phần tử cha của tập các phần tử trội chính là các phần tử trội. Qua các nhận xét trên, có thể thấy rằng các phần tử trội ở mức cao hơn luôn trội hơn hẳn một phần tử trội ở mức thấp hơn một bậc. Như vậy, để tìm các phần tử trội, chúng ta thực hiện như sau: Xuất phát với , . Dò tìm lần lượt trên các xâu ký tự, nếu gặp điểm khớp đầu tiên thì đó chính là phần tử trội ở mức 1. Bổ sung vào . Giả sử ta đã có là tập các phần tử trội nhỏ hơn hoặc bằng mức (). Khi tìm thấy một điểm khớp , chúng ta sẽ kiểm tra xem trội hơn so với các phần tử trội với . Nếu trội hơn được một phần tử trong tập , lập tức so sánh với các phần tử trong . Khi tìm được là mức lớn nhất mà trội hơn ít nhât một phần tử trong tập , chúng ta sẽ kiểm tra xem có trội hơn hẳn một phần tử trội nào trong tập hay không. Nếu có thì chính là phần tử trội của tập , ngược lại thì không phải là phần tử trội. Truy xuất tìm xâu con chung dài nhất khi biết phần tử trội Khi có được tập tất cả các phần tử trội, chúng ta hoàn toàn có thể xây dựng ma trận phương án như sau: Giả sử là xâu ký tự trên bảng chữ cái và là ma trận phương án với tất cả các phần tử bằng 0. Xâu con chung dài nhất với độ dài là . Xuất phát từ tập tất cả các phần tử trội ở mức lớn nhất (mức ). Tại vị trí này ta đánh số . Tất cả vị trí trội hơn các phần tử trội này cũng sẽ đều được đánh số . Sau đó giảm xuống và lại đánh số như trên. Cần lưu ý rằng các vị trí đã được đánh số khác 0 thì sẽ không được đánh số lại nữa. Cứ tiếp tục như vậy ta sẽ có ma trận phương án. Bảng 2.3 mô tả việc dựng lại ma trận bảng phương án khi biết các phần tử trội. Bảng đang thể hiện việ