Phát Hiện Xu Hướng Thường Xuyên Trong Dữ Liệu Chuỗi Thời Gian

Khám phá luận văn thạc sĩ về phát hiện xu hướng trong dữ liệu chuỗi thời gian, ứng dụng trong khoa học máy tính và phân tích dữ liệu.

• Tác giả: Đỗ Duy Quốc
• Người hướng dẫn: PGS. Dương Tuấn Anh
• Trường học: Đại học Quốc gia TP. Hồ Chí Minh
• Chuyên ngành: Khoa học máy tính
• Đề tài: Phát Hiện Tất Cả Các Xu Hướng Thường Xuyên Trong Dữ Liệu Chuỗi Thời Gian
• Loại tài liệu: luận văn thạc sĩ
• Năm xuất bản: 2016
• Địa điểm: TP. Hồ Chí Minh

Tóm tắt

I. Tổng Quan Về Phát Hiện Xu Hướng Trong Chuỗi Thời Gian 55 ký tự

Trong thời đại bùng nổ thông tin, việc khai thác và quản lý dữ liệu hiệu quả trở nên vô cùng quan trọng. Các lĩnh vực như kinh tế, xã hội, giáo dục, y tế đều ứng dụng công nghệ thông tin để phân tích và dự báo. Một trong những ứng dụng quan trọng là khai phá dữ liệu chuỗi thời gian. Chuỗi thời gian là dãy số biểu diễn giá trị của một đại lượng theo thời gian. Ví dụ: số lượng sản phẩm bán ra, tỉ lệ bệnh nhân, giá vàng, lượng mưa. Phân tích chuỗi thời gian giúp dự báo chuỗi thời gian và đưa ra quyết định chính xác hơn. Nhiều thuật toán được phát triển để tối ưu hóa việc tìm kiếm và phát hiện các mẫu ẩn trong dữ liệu chuỗi thời gian.

1.1. Ứng Dụng Thực Tiễn Của Phân Tích Chuỗi Thời Gian

Phân tích chuỗi thời gian có nhiều ứng dụng thực tiễn quan trọng. Nó được sử dụng để dự đoán biến động giá cả trên thị trường chứng khoán, giúp các nhà đầu tư đưa ra quyết định mua bán sáng suốt. Trong lĩnh vực y tế, phân tích chuỗi thời gian được dùng để theo dõi sự lây lan của dịch bệnh, dự báo số lượng ca nhiễm mới và đưa ra các biện pháp phòng ngừa hiệu quả. Ngoài ra, nó còn được ứng dụng trong dự báo nhu cầu tiêu dùng, quản lý chuỗi cung ứng và tối ưu hóa hoạt động sản xuất. Việc hiểu rõ các ứng dụng này giúp ta thấy được tầm quan trọng của việc nghiên cứu và phát triển các phương pháp phân tích chuỗi thời gian hiệu quả.

1.2. Xu Hướng Thường Xuyên Khái Niệm và Tầm Quan Trọng

Xu hướng thường xuyên (frequent trend) là một đoạn trong chuỗi thời gian lặp đi lặp lại. Việc phát hiện xu hướng thường xuyên có ứng dụng lớn trong dự đoán. Ví dụ, dự báo tăng giảm giá vàng hoặc cổ phiếu dựa trên các mẫu lặp lại trong quá khứ. Nhiều thuật toán đã được phát triển để phát hiện xu hướng này. Nghiên cứu của Indyk [1] tập trung vào xác định xu hướng, trong khi Qu [2] trình bày cách tiếp cận tìm kiếm xu hướng và giải thuật chiếu ngẫu nhiên để phát hiện motif. Việc xác định được các xu hướng thường xuyên sẽ giúp đưa ra các quyết định dựa trên bằng chứng, mang lại hiệu quả cao hơn so với các phương pháp dự đoán truyền thống.

II. Thách Thức Khi Tìm Xu Hướng Trong Dữ Liệu Chuỗi 58 ký tự

Tìm kiếm xu hướng trong dữ liệu chuỗi thời gian đặt ra nhiều thách thức. Một trong số đó là xử lý dữ liệu lớn và phức tạp. Dữ liệu chuỗi thời gian thường có kích thước rất lớn, đặc biệt trong các lĩnh vực như tài chính và viễn thông. Điều này đòi hỏi các thuật toán phải có khả năng xử lý dữ liệu hiệu quả và nhanh chóng. Bên cạnh đó, dữ liệu thường chứa nhiễu và các yếu tố ngẫu nhiên, gây khó khăn cho việc xác định các xu hướng thực sự. Ngoài ra, việc lựa chọn phương pháp mã hóa và biểu diễn dữ liệu phù hợp cũng là một thách thức quan trọng.

2.1. Vấn Đề Về Độ Phức Tạp Tính Toán và Lưu Trữ

Các thuật toán tìm kiếm xu hướng trong chuỗi thời gian phải đối mặt với vấn đề độ phức tạp tính toán. Ví dụ, cây hậu tố đòi hỏi bộ nhớ lớn để lưu trữ. Với dữ liệu lớn, việc xây dựng và duyệt cây trở nên chậm chạp. Luận văn của Đỗ Duy Quốc chỉ ra rằng, với dữ liệu có xu hướng tăng giảm không đáng kể trong thời gian ngắn, cây hậu tố khó tìm xu hướng dài hạn và tốn nhiều bộ nhớ. Cần có giải pháp hiệu quả hơn để giải quyết vấn đề này.

2.2. Ảnh Hưởng Của Nhiễu Và Dị Thường Đến Kết Quả Phân Tích

Nhiễu và dị thường trong dữ liệu chuỗi thời gian ảnh hưởng lớn đến kết quả phân tích. Dữ liệu thực tế thường chứa các sai sót do lỗi đo lường, yếu tố bên ngoài hoặc sự kiện bất thường. Những yếu tố này có thể làm sai lệch các xu hướng thực sự và dẫn đến kết luận không chính xác. Các phương pháp tiền xử lý dữ liệu, như làm mịn và loại bỏ dị thường, cần được áp dụng để giảm thiểu ảnh hưởng của nhiễu. Tuy nhiên, việc lựa chọn phương pháp phù hợp và cân bằng giữa việc loại bỏ nhiễu và giữ lại thông tin quan trọng là một thách thức không nhỏ.

III. Mảng Hậu Tố Nâng Cao Giải Pháp Tìm Xu Hướng Tối Ưu 59 ký tự

Luận văn của Đỗ Duy Quốc đề xuất sử dụng mảng hậu tố nâng cao để tìm kiếm xu hướng thường xuyên và motif trong dữ liệu chuỗi thời gian. Ý tưởng chính là làm nhẵn dữ liệu bằng phương pháp xấp xỉ tuyến tính từng đoạn (PLA), sau đó mã hóa dữ liệu thành chuỗi ký tự dựa trên độ lệch góc giữa hai điểm liên tiếp. Phương pháp này giúp tìm các mẫu xu hướng trong khoảng thời gian dài. Ngoài ra, xấp xỉ gộp từng đoạn (PAA) được dùng để giảm số chiều, tăng tốc độ xử lý.

3.1. Ưu Điểm Của Mảng Hậu Tố So Với Cây Hậu Tố

Mảng hậu tố nâng cao có ưu điểm so với cây hậu tố. Nó tiết kiệm bộ nhớ hơn và có thể xử lý dữ liệu lớn hiệu quả hơn. Cây hậu tố tốn nhiều bộ nhớ để lưu trữ các nút và liên kết, trong khi mảng hậu tố chỉ cần lưu trữ các chỉ số. Ngoài ra, việc tìm kiếm trong mảng hậu tố thường nhanh hơn do không cần duyệt qua cấu trúc cây phức tạp. Do đó, mảng hậu tố là lựa chọn tốt hơn cho các ứng dụng đòi hỏi hiệu suất cao.

3.2. Kết Hợp Xấp Xỉ Tuyến Tính Từng Đoạn PLA

Việc áp dụng phương pháp xấp xỉ tuyến tính từng đoạn (PLA) giúp làm nhẵn dữ liệu đầu vào, giảm nhiễu và làm nổi bật các xu hướng chính. PLA thay thế các đoạn dữ liệu bằng các đường thẳng, giúp đơn giản hóa dữ liệu và giảm số lượng điểm cần xử lý. Điều này làm tăng tốc độ xây dựng mảng hậu tố và cải thiện khả năng phát hiện các xu hướng dài hạn. Sự kết hợp giữa mảng hậu tố và PLA mang lại hiệu quả cao trong việc phân tích dữ liệu chuỗi thời gian.

IV. Phương Pháp Xấp Xỉ Gộp Từng Đoạn PAA Tăng Tốc Độ 53 ký tự

Để tăng tốc độ xử lý, luận văn sử dụng phương pháp xấp xỉ gộp từng đoạn (PAA). PAA giảm số chiều của dữ liệu chuỗi thời gian bằng cách chia dữ liệu thành các đoạn và tính giá trị trung bình cho mỗi đoạn. Điều này giúp giảm kích thước dữ liệu và tăng tốc độ xây dựng mảng hậu tố. Theo luận văn, việc áp dụng PAA làm tăng tốc đáng kể thời gian xây dựng và tìm kiếm motif.

4.1. Vai Trò Của PAA Trong Giảm Chiều Dữ Liệu

Xấp xỉ gộp từng đoạn (PAA) đóng vai trò quan trọng trong việc giảm chiều dữ liệu chuỗi thời gian. Bằng cách chia chuỗi thời gian thành các đoạn và tính giá trị trung bình của mỗi đoạn, PAA giảm số lượng điểm dữ liệu cần xử lý. Điều này không chỉ giúp giảm độ phức tạp tính toán mà còn giảm dung lượng lưu trữ cần thiết. Việc giảm chiều dữ liệu giúp các thuật toán phân tích, như xây dựng mảng hậu tố, chạy nhanh hơn và hiệu quả hơn.

4.2. Ảnh Hưởng Của Kích Thước Đoạn Đến Kết Quả

Kích thước đoạn trong PAA ảnh hưởng đến kết quả phân tích. Nếu kích thước đoạn quá lớn, thông tin chi tiết quan trọng có thể bị mất. Ngược lại, nếu kích thước đoạn quá nhỏ, hiệu quả giảm chiều sẽ không đáng kể. Do đó, việc lựa chọn kích thước đoạn phù hợp là rất quan trọng. Cần phải cân bằng giữa việc giảm chiều và giữ lại thông tin quan trọng để đảm bảo kết quả phân tích chính xác và có ý nghĩa.

V. Ứng Dụng Thực Tế Phân Tích ECG Với Mảng Hậu Tố 54 ký tự

Luận văn thử nghiệm phương pháp trên nhiều bộ dữ liệu thực tế, bao gồm dữ liệu ECG (điện tâm đồ), Memory, power_data, koski_ecg và eeg (điện não đồ). Kết quả cho thấy mảng hậu tố nâng cao xử lý tốt hơn so với cây hậu tố và các giải thuật tìm kiếm thông thường (brute force, phương pháp chiếu ngẫu nhiên). Phương pháp này hiệu quả trong việc tìm kiếm xu hướng thường xuyên và motif trong các loại dữ liệu chuỗi thời gian khác nhau.

5.1. So Sánh Hiệu Năng Giữa Các Giải Thuật Trên Dữ Liệu ECG

Kết quả thử nghiệm trên dữ liệu ECG cho thấy mảng hậu tố nâng cao, kết hợp với PLA hoặc PAA, có hiệu năng tốt hơn so với cây hậu tố và giải thuật brute force. Mảng hậu tố có thể tìm kiếm các motif và xu hướng nhanh hơn và sử dụng ít bộ nhớ hơn. Giải thuật brute force tỏ ra chậm chạp và kém hiệu quả, đặc biệt với dữ liệu lớn. Điều này chứng minh ưu thế của mảng hậu tố trong phân tích dữ liệu chuỗi thời gian phức tạp.

5.2. Phân Tích Kết Quả Trên Các Bộ Dữ Liệu Khác Memory Power ...

Kết quả trên các bộ dữ liệu khác như Memory, power_data, koski_ecg và eeg cũng tương tự. Mảng hậu tố luôn cho thấy hiệu quả vượt trội so với các phương pháp khác. Điều này cho thấy tính tổng quát và khả năng ứng dụng rộng rãi của phương pháp này trong nhiều lĩnh vực khác nhau. Việc lựa chọn phương pháp phù hợp phụ thuộc vào đặc điểm của dữ liệu và yêu cầu về hiệu năng của ứng dụng.

VI. Kết Luận và Hướng Phát Triển Nghiên Cứu Chuỗi Thời Gian 54 ký tự

Luận văn đã chứng minh hiệu quả của mảng hậu tố nâng cao trong việc tìm kiếm xu hướng thường xuyên và motif trong dữ liệu chuỗi thời gian. Phương pháp này có tiềm năng ứng dụng rộng rãi trong nhiều lĩnh vực. Hướng phát triển tiếp theo có thể tập trung vào việc tối ưu hóa thuật toán, xử lý dữ liệu thời gian thực và kết hợp với các kỹ thuật học máy để nâng cao khả năng dự đoán.

6.1. Tổng Kết Các Kết Quả Nghiên Cứu Chính

Nghiên cứu đã thành công trong việc xây dựng và triển khai mảng hậu tố nâng cao để tìm kiếm hiệu quả các xu hướng thường xuyên và motif trong dữ liệu chuỗi thời gian. Các phương pháp xấp xỉ PLA và PAA đã được chứng minh là có hiệu quả trong việc giảm chiều dữ liệu và tăng tốc độ xử lý. So sánh với các phương pháp khác, mảng hậu tố cho thấy hiệu năng vượt trội, đặc biệt với dữ liệu lớn và phức tạp.

6.2. Đề Xuất Hướng Nghiên Cứu Tiếp Theo và Mở Rộng

Hướng nghiên cứu tiếp theo có thể tập trung vào việc phát triển các thuật toán tự động lựa chọn tham số cho PLA và PAA để tối ưu hóa hiệu năng. Nghiên cứu cũng có thể mở rộng sang việc kết hợp mảng hậu tố với các mô hình học sâu để tăng cường khả năng dự đoán và phân tích. Ngoài ra, việc ứng dụng mảng hậu tố vào các lĩnh vực mới, như phân tích mạng xã hội và an ninh mạng, cũng là một hướng đi đầy tiềm năng.

Trích đoạn nội dung tài liệu

CHƯƠNG 1. GIỚI THIỆU TỔNG QUAN VỀ ĐỀ TÀI Chương này giới thiệu sơ lược về đề tài, mục tiêu và phạm vi nghiên cứu cũng như cấu trúc của đề tài. CƠ SỞ LÝ THUYẾT Chương này trình bày chi tiết về các vấn đề lý thuyết sẽ được áp dụng trong đề tài như: dữ liệu chuỗi thời gian, cây hậu tố, mảng hậu tố, mảng hậu tố nâng cao, mã hóa dữ liệu chuỗi thời gian thành chuỗi xu hướng. NHỮNG CÔNG TRÌNH LIÊN QUAN Chương này trình bày một số công trình nghiên cứu liên quan đến đề tài như công trình phát hiện tất cả các xu hướng thường xuyên trong dữ liệu chuỗi thời gian, công trình phát hiện motif trên dữ liệu chuỗi thời gian dựa vào xác xuất, và công trình về truy vấn hình dạng dữ liệu chuỗi thời gian.

PHƯƠNG PHÁP GIẢI QUYẾT VẤN ĐỀ Chương này trình bày về việc sử dụng mảng hậu tố nâng cao, cây hậu tố cùng với phương pháp xấp xỉ tuyến tính từng đoạn để phát hiện tất cả các mẫu xu hướng thường xuyên và phương pháp xấp xỉ gộp từng đoạn để phát hiện tất cả các motif trong dữ liệu chuỗi thời gian CHƯƠNG 5. THỰC NGHIỆM VÀ ĐÁNH GIÁ Trang 4 Tìm tất cả các xu hướng thường xuyên trong dữ liệu chuỗi thời gian | Đỗ Duy Quốc Chương này trình bày thực nghiệm, đánh giá độ chính xác và thời gian thực hiện để phát hiện tất cả các mẫu xu hướng và phát hiện tất cả các motif bằng mảng hậu tố nâng cao và cây hậu tố trong dữ liệu chuỗi thời gian. KẾT LUẬN Chương này đánh giá kết quả đạt được, các mặt hạn chế và hướng phát triển của đề tài. Trang 5 Tìm tất cả các xu hướng thường xuyên trong dữ liệu chuỗi thời gian | Đỗ Duy Quốc CHƯƠNG 2.

CƠ SỞ LÝ THUYẾT Chương này sẽ trình bày về các công trình liên quan đến bài toán tìm tất cả các xu hướng thường xuyên trong dữ liệu chuỗi thời gian, các công trình về cây hậu tố, mảng hậu tố, mảng hậu tố nâng cao, phương pháp thu giảm số chiều, phương pháp rời rạc hóa dữ liệu.1 DỮ LIỆU CHUỖI THỜI GIAN Một chuỗi thời gian (Time Series) chiều dài 𝑚 là một tập hợp có thứ tự gồm 𝑚 giá trị thực. Ta ký hiệu chuỗi thời gian là 𝑇 = 𝑥1 , 𝑥2 , … , 𝑥𝑚 với 𝑥𝑖 là các số thực, 𝑚 là một số nguyên. Việc xác định các xu hướng thường xuyên của một chuỗi thời rất quan trọng trong bài toán dự báo chuỗi thời gian. Nó giúp ta lựa chọn được mô hình dự báo phù hợp hay giúp cải tiến mô hình đã có chính xác hơn.

Và các mẫu quan sát được theo thời gian dựa trên các chuỗi thời gian chính là cơ sở để hiểu được đặc tính cũng như là dự báo các hành vi tương lai của đối tượng đó. Chuỗi con (𝑠𝑢𝑏𝑠𝑒𝑞𝑢𝑒𝑛𝑐𝑒) 𝐶 có chiều dài 𝑛 của một chuỗi thời gian 𝑇 có chiều dài 𝑚 (𝑚 ≤ 𝑛) là một đoạn các giá trị liên tục nằm trong T. Ta ký hiệu 𝐶 = 𝑥 𝑝 , 𝑥𝑝+1 , … , 𝑥𝑝+𝑛−1 , với 1 ≤ 𝑝 ≤ 𝑚 − 𝑛 + 1.2 CÂY HẬU TỐ Cho ∑ là một tập hữu hạn các phần tử, với mỗi phần tử là một ký tự trong tập ký tự (𝑎𝑙𝑝ℎ𝑎𝑏𝑒𝑡), các phần tử thuộc ∑ gọi là ký tự. ∑* là một tập hợp con của ∑ mà không chứa chuỗi rỗng (∈).

Ta có: ∑∗ = ∑ − {∈} Chiều dài của một chuỗi 𝑥 ký hiệu là |𝑥 |, là số ký tự trong chuỗi 𝑥. Các ký trong chuỗi 𝑥 được đánh số từ 0 đến|𝑥| – 1:=𝑥 = 𝑥0 𝑥1 𝑥2 … 𝑥|𝑥|−1 Trang 6 Tìm tất cả các xu hướng thường xuyên trong dữ liệu chuỗi thời gian | Đỗ Duy Quốc Gọi chuỗi 𝑤 là tiền tố của chuỗi 𝑥, ký hiệu 𝑤 ⊏ 𝑥, nếu tồn tại chuỗi 𝑎 để 𝑥 = 𝑤𝑎, chuỗi 𝑤 là hậu tố của chuỗi 𝑥, ký hiệu 𝑤 ⊐ 𝑥, nếu tồn tại chuỗi 𝑎 để 𝑥 = 𝑎𝑤. Một chuỗi vừa có thể là tiền tố vừa là hậu tố của một chuỗi khác. Ví dụ chuỗi XYX vừa là tiền tố vừa là hậu tố của chuỗi XYXYX.

Chuỗi rỗng (∈) vừa là tiền tố vừa là hậu tố của tất cả các chuỗi. Trie hậu tố Cho 𝑆 là một tập hợp gồm 𝑛 chuỗi, các chuỗi này không là tiền tố của nhau. Trie là một cấu trúc dữ liệu dạng cây (hình 2-1) biểu diễn các chuỗi của 𝑆. Trie có các tính chất sau:  Mỗi cạnh của Trie có nhãn là một ký tự.

Các cạnh đi từ một nút xuống các nút con có nhãn khác nhau.  Mỗi nút trên Trie cũng có một nhãn, ký hiệu 𝑣̅ là chuỗi tạo thành bằng cách nối các ký tự nhãn của cạnh trên đường đi trừ nút gốc xuống nút con. Chiều dài của chuỗi 𝑣̅ được gọi là độ sâu của nút, ký hiệu: 𝑑𝑒𝑝𝑡ℎ(𝑣).  Hai nút khác nhau có nhãn khác nhau Ví dụ Trie hậu tố: 𝑆 = {𝐵𝐸𝐴𝑅, 𝐵𝐸𝐿𝐿, 𝐵𝐼𝐷, 𝐵𝑈𝐿𝐿, 𝐵𝑈𝑌, 𝑆𝐸𝐿𝐿, 𝑆𝑇𝑂𝐶𝐾, 𝑆𝑇𝑂𝑃}.

Trie hậu tố Trang 7 Tìm tất cả các xu hướng thường xuyên trong dữ liệu chuỗi thời gian | Đỗ Duy Quốc Các chuỗi trong tập 𝑆 phải thỏa mãn tính chất phi tiền tố (prefix-free): tức là không có chuỗi nào là tiền tố của một chuỗi khác trong 𝑆. Không thể xây dựng được cây không thỏa mãn tính chất trên. Ví du: 𝑆 = {ABC, AB}, ta không thể xây dựng được trie hậu tố vì từ nút góc đến các nút lá của Trie ta lần lượt đi qua các nút có nhãn A, AB, ABC. Vì AB ∈ 𝑆 nên ta phải có nút lá của Trie mang nhãn AB, mà ta đã có nhánh của Trie có nhãn AB, nên không thể xây dựng được nút lá có nhãn AB (hình 2.

Không thể xây dựng được Trie với nút lá có nhãn AB Tính chất phi tiền tố là một tính chất quan trọng của cây Trie. Để đảm bảo ta luôn có thể xây dựng được cây Trie, ta dùng một kỹ thuật là bổ sung vào mỗi chuỗi của 𝑆 một ký tự $ ở cuối mỗi chuỗi (hình 2-3) Cho 𝑆 là một tập chứa các hậu tố của 1 chuỗi 𝑇 (𝑇 ∈ ∑∗ ) được gọi là Trie hậu tố của T (hình 2-4). Để thỏa mãn tính chất phi tiền tố, ta thêm vào cuối mỗi phần tử của S ký tự $. Ví dụ: 𝑇 = BANANA$, ta có tập S gồm 7 chuỗi: 𝑆 = {BANANA$, ANANA$, NANA$, ANA$, NA$, A$, $} Trang 8 Tìm tất cả các xu hướng thường xuyên trong dữ liệu chuỗi thời gian | Đỗ Duy Quốc Hình 2-3.

Thêm ký tự $ ở cuối mỗi chuỗi Hình 2-4. Trie hậu tố 𝑻 = 𝑩𝑨𝑵𝑨𝑵𝑨$ Cây hậu tố (suffix tree) là một cấu trúc dữ liệu biểu diễn các hậu tố của một chuỗi khác rỗng tương tự như Trie. Cây hậu tố được tạo thành từ Trie hậu tố bằng cách Trang 9 Tìm tất cả các xu hướng thường xuyên trong dữ liệu chuỗi thời gian | Đỗ Duy Quốc ghép các nút con đơn nhánh lại với nhau. Cây hậu tố cho chuỗi 𝑆 có chiều dài 𝑚 có các tính chất sau: Mỗi cạnh của cây có nhãn là một chuỗi thuộc ∑∗.

Các cạnh đi từ một nút xuống các nút con của nó phải có nhãn là các chuỗi có ký tự đầu tiên khác nhau. Mỗi nút 𝑣 trên cây cũng mang một nhãn, nhãn của nút 𝑣, ký hiệu 𝑣̅ là một chuỗi tạo thành bằng các nối tiếp các nhãn cạnh trên đường đi xuống nút 𝑣. Chiều dài của chuỗi 𝑣̅ : 𝑣̅ được gọi là độ sâu của nút 𝑣, ký hiệu: 𝑑𝑒𝑝𝑡ℎ(𝑣). Ngoại trừ nút góc, các nút phải có nhiều hơn một con.

Với mỗi cạnh được gán nhãn bằng một chuỗi con khác rỗng của 𝑆. Mỗi chuỗi con 𝑎 của chuỗi 𝑆 xuất hiện trên một lối đi duy nhất nào đó từ nút gốc. Ví dụ cây hậu tố: 𝑆 = xabxa$ Hình 2-5. Cây hậu tố cho chuỗi xabxa$ 2.3 MẢNG HẬU TỐ Cho một chuỗi 𝑆 = 𝑥1 , 𝑥2 , 𝑥3 , … 𝑥𝑚 ∈ ∑∗ , có duy nhất 𝑥𝑚 = $.

Mảng hậu tố (suffix array) của 𝑆 ký hiệu SA(T) là thứ tự từ điển của tất cả các hậu tố của 𝑆. Trang 10 Tìm tất cả các xu hướng thường xuyên trong dữ liệu chuỗi thời gian | Đỗ Duy Quốc Mảng hậu tố có thể được biểu diễn theo thứ tự từ điển (hình 2-6). Ví dụ: 𝑆= BANANA$, các hậu tố của 𝑆 và mảng hậu tố của 𝑆 theo thứ tự từ điển. Mảng hậu tố theo thứ tự từ điển Mảng hậu tố được đề xuất bởi Manber và Myer [3] như một sự thay thế cho cây hậu tố trong một số bài toán xử lý chuỗi.

Mảng hậu tố có ưu điểm là có cấu trúc đơn giản và tiết kiệm bộ nhớ trong lúc hiện thực. Manber và Mayer cũng đề xuất thuật toán xây dựng mảng hậu tố trực tiếp mà không phải sử dụng cây hậu tố gọi là thuật toán nhân đôi tiền tố (𝑑𝑜𝑢𝑏𝑙𝑖𝑛𝑔 𝑝𝑟𝑒𝑓𝑖𝑥). Thuật toán có độ phức tạp là Ω(𝑛𝑙𝑜𝑔𝑛) trong trường hợp xấu nhất và 𝑂(𝑛) trong trường hợp trung bình để xử lý chuỗi có độ dài 𝑛. Năm 2003, hai nghiên cứu độc lập của Kärkkäinen [4] và Ko [5] đã tìm ra được hai thuật toán tuyến tính xây dựng mảng hậu tố.

Một điểm đáng chú ý trong các thuật toán của Kärkkäinen [4] là chúng đều dựa trên những nhận định rất tinh tế về tính chất của các hậu tố và mối quan hệ giữa các vị trí trong chuỗi. Trang 11 Tìm tất cả các xu hướng thường xuyên trong dữ liệu chuỗi thời gian | Đỗ Duy Quốc 2.4 MẢNG TIỀN TỐ CHUNG DÀI NHẤT Tiền tố chung dài nhất (longest common prefix) của hai chuỗi (𝑥, 𝑦) là chuỗi 𝑧 sao cho 𝑧 vừa là tiền tố của 𝑥, vừa là tiền tố của 𝑦 và 𝑧 có độ dài lớn nhất. Ví dụ: TIền tố chung của sâu banana và bank là ban. Mảng tiền tố chung dài nhất (LCP) là một mảng có kích thước n (giống như suffix array) sao cho giá trị thứ 𝑖 (𝑙𝑐𝑝[𝑖]) là tiền tố chung dài nhất của hậu tố thứ 𝑖 và 𝑖 + 1 Cho T= t0 t1 …., an-1 là mảng hậu tố của T.

Mảng tiền tố chung dài nhất 𝐿𝐶𝑃(𝑇) là dãy số nguyên ( l0 , l1 ,….