Số hóa bởi Trung tâm Học liệu

ĐẠI HỌC THÁI NGUYÊN
TRƢỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN & TRUYỀN THÔNG
NGUYỄN NGỌC ANH
NGHIÊN CỨU VÀ THỬ NGHIỆM MỘT SỐ THUẬT TOÁN
PHÁT HIỆN CÁC ĐỒ THỊ CON THƢỜNG XUYÊN

LuËn v¨n th¹c SÜ KHOA HỌC MÁY TÍNH Th¸i Nguyªn - 2014 Số hóa bởi Trung tâm Học liệu
và thuật toán phù hợp để giải quyết cho từng bài toán cụ thể, đem lại hiệu quả
cao đó chính là ý nghĩa thực tiễn của đề tài.
 Nội dung của luận văn và các vấn đề cần giải quyết:
1. Tìm hiểu về các phƣơng pháp khai phá dữ liệu đồ thị.
2. Tìm hiểu các thuật toán phát hiện đồ thị con thƣờng xuyên trong CSDL đồ
thị.
3. Cài đặt thử nghiệm thuật toán phát hiện các đồ thị con thƣờng xuyên
trong CSDL đồ thị
 Phƣơng pháp nghiên cứu
+ Nghiên cứu về khai phá dữ liệu đồ thị với trọng tâm là phát hiện các đồ
thị con thƣờng xuyên trong CSDL đồ thị.
+ Tìm hiểu các nguồn thông tin từ các sách,bài báo,tạp chí, Internet ,liên
quan đến khai phá dữ liệu đồ thị.
 Cấu trúc luận văn chia làm 4 chƣơng:
Chƣơng 1: “ Tổng quan về khai phá dữ liệu đồ thị ” trình bày tổng quan
các hƣớng nghiên cứu hiện nay về khai phá dữ liệu đồ thị.
Chƣơng 2: “ Phát hiện các cấu trúc con thƣờng xuyên ” trình bày cơ sở lý
thuyết đồ thị, cách tiếp cận dựa trên Apriori, cách tiếp cận dựa trên sự phát
triển mẫu.
Chƣơng 3: “ Các thuật toán phát hiện đồ thị con thƣờng xuyên ” trình
bày một số thuật toán phát hiện đồ thị con thƣờng xuyên theo chiến lƣợc tìm
kiếm theo chiều rộng và chiều sâu.
Chƣơng 4: “ Thiết kế hệ thống thử nghiệm ” trình bày kết quả cài đặt của
thuật toán trong chƣơng 3.
Số hóa bởi Trung tâm Học liệu

CHƢƠNG 1: TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU ĐỒ THỊ

Số hóa bởi Trung tâm Học liệu Dữ liệu lớn bao gồm cả tính chất về độ lớn lƣu trữ (Volume), đa dạng,
phức tạp (Variety) và tăng trƣởng nhanh chóng (Velocity)[8].
Dữ liệu lớn thƣờng đề cập tới các kiểu dữ liệu nhƣ sau:
- Dữ liệu doanh nghiệp truyền thống: bao gồm các thông tin khách hàng, dữ
liệu giao dịch, dữ liệu kế toán tổng hợp.
- Dữ liệu cảm biến hoặc máy sinh dữ liệu: bao gồm các bản ghi chi tiết các
cuộc gọi, nhật ký web, hệ đo thông minh, dữ liệu từ các cảm biến, các hệ
thống dữ liệu truyền thống.
- Dữ liệu xã hội: bao gồm các luồng thông tin phản hồi của khách hàng, dữ
liệu từ các trang nhật ký và mạng xã hội nhƣ Twitter, Facebook,
1.1.2.

Giải pháp dữ liệu lớn của một số nhà cung cấp dịch vụ:
* Giải pháp Big data của Oracle
Oracle là nhà cung cấp đầu tiên cung cấp một giải pháp hoàn chỉnh và tích
hợp để giải quyết đầy đủ yêu cầu về dữ liệu lớn của doanh nghiệp. Các dữ
liệu lớn của Oracle tập trung trên ý tƣởng có thể phát triển kiến trúc dữ liệu
doanh nghiệp hiện tại để kết hợp dữ liệu lớn và cung cấp giá trị kinh doanh,
linh hoạt, hiệu suất để giải quyết yêu cầu về dữ liệu lớn với doanh nghiệp.
Với việc giới thiệu ứng dụng Quản lý Dữ liệu lớn (Oracle Big Data
Appliance), Oracle cung cấp một giải pháp hoàn chỉnh đáp ứng mọi yêu cầu
liên quan đến dữ liệu lớn của doanh nghiệp. Thiết bị xử lý dữ liệu lớn Oracle
Big Data Appliance, cùng với máy chủ cơ sở dữ liệu Oracle Exadata và Máy
chủ thông tin hỗ trợ ra quyết định Oracle Exalytics mới, giúp khách hàng có để
thu thập, tổ chức, phân tích và khai thác tối đa giá trị của dữ liệu lớn.
Oracle Big Data Appliance có thể đƣợc tích hợp dễ dàng với cơ sở dữ liệu
Oracle Database 11g, Oracle Exadata Database Machine và Oracle Exalytics

Có hai nhóm phƣơng pháp đƣợc đề xuất để giải quyết vấn đề trên, đó là:
nhóm phƣơng pháp khai phá theo chiều rộng và nhóm phƣơng pháp khai phá
theo chiều sâu:

Số hóa bởi Trung tâm Học liệu Một số kỹ thuật khai phá theo chiều rộng nhƣ: kỹ thuật AGM đƣợc
phát triển bởi Inokuchi, kỹ thuật FSG đƣợc đề xuất bởi Kuramochi và
Karypis. Các kỹ thuật này khai phá đồ thị theo từng mức trong đó mỗi mức
chứa các đồ thị có nhiều hơn một đỉnh hoặc một cạnh so với mức trƣớc đó.
Các đồ thị thƣờng xuyên của mức tiếp theo đƣợc tìm ra bằng cách, đầu tiên
tạo ra các đồ thị ứng viên với các cặp đồ thị của mức hiện tại, sau đó lọc ra
các đồ thị không thƣờng xuyên. Ƣu điểm chính của những kỹ thuật này dựa
trên nguyên tắc ƣu tiên bằng cách một đồ thị chỉ đƣợc xem là thƣờng xuyên
nếu tất cả các đồ thị con của nó là thƣờng xuyên. Vì một đồ thị đƣợc tìm ra
sau khi tìm ra các đồ thị con của nó, do đó có thể loại bỏ các đồ thị không
thƣờng xuyên mà không cần phải tính toán hàm hỗ trợ của chúng bằng cách
kiểm tra nếu các đồ thị con của chúng là thƣờng xuyên. Tuy nhiên, nhóm
phƣơng pháp tìm kiếm theo chiều rộng có hai vấn đề đó là: sinh ra nhiều đồ
thị ứng viên và yêu cầu về lƣu trữ các đồ thị thƣờng xuyên ở mỗi mức.
Nhóm phƣơng pháp khai phá theo chiều sâu đã khắc phục những vấn
đề này bằng cách tìm kiếm đồ thị theo chiều sâu, có thể kể đến một số thuật
toán nhƣ: gSpan đƣợc đề xuất bởi Han và Yan, FFSM đƣợc đề xuất bởi Huan,
và GASTON bởi Nijssen và Kok. Tƣ tƣởng của nhóm phƣơng pháp này bắt
đầu với một đồ thị có chứa một đỉnh hoặc một cạnh thƣờng xuyên, những kỹ
thuật này đƣợc mở rộng đệ quy bằng cách thêm mới một cạnh giữa hai đỉnh
hiện tại hoặc thêm mới một đỉnh kết nối tới một đỉnh hiện tại khác. Vì một đồ
thị là không thƣờng xuyên hơn các đồ thị con của nó, do đó không cần mở
rộng tới các đồ thị không thƣờng xuyên. Các đồ thị không thƣờng xuyên có

’
.
2.1.1.

Định nghĩa 2.1 (Graph):
Chomột nhãn node bằng chữ cái (alphabet) L
V
và một nhãn cạnh bằng
chữ cái L
E
đồ thị g (có hƣớng) đƣợc định nghĩa bằng bộ gồm 4 thành phần
g=(V , E, µ, ν), trong đó:
• V biểu diễn một tập hữu hạn các node.
• E
⊆
V×V biểu diễn một tập các cạnh.
• µ:V→L
V
biểu diễn một hàm ghi nhãn node.
• ν:E→L
E
biểu diễn một hàm ghi nhãn cạnh.
Tập V có thể đƣợc coi là một tập các định danh nút và thƣờng đƣợc chọn
bằng V = {1, , | V |}. Trong khi V xác định các nút, tập các cạnh E thể hiện
cấu trúc của đồ thị. Đó là một nút u
∈
V đƣợc kết nối với một nút v
∈
V bằng
một cạnh= (u, v) nếu (u, v)

ε
,ν
ε
).
2.1.2.

Định nghĩa 2.2 (Subgraph):
Cho g
1
=(V
1
,E
1
,µ
1
,ν
1
) và g
2
=(V
2
,E
2
,µ
2
,ν
2
) là các đồ thị, đồ thị g
1
là một đồ

1
.
• ν
1
(u, v)=ν
2
(u, v) cho tất cả (u, v)
∈
E
1
.
Ngƣợc lại, đồ thị g
2
đƣợc gọi là một đồ thị con của g
1
đôi khi điều kiện
thứ hai của định nghĩa này đƣợc thay thế bằng E
1
⊆
E
2
.
2.1.3.

Định nghĩa 2.3 (Graph Isomorphism):
Cho g
1
=(V
1
,E

∈
V
1
.
• Cho mỗi cạnh e
1
=(u, v)
∈
E
1
, tồn tại một cạnh e
2
=(f (u), f (v))
∈
E
2
sao
cho ν
1
(e
1
)=ν
2
(e
2
).
• Cho mỗi cạnh e
2
=(u, v)
∈
Số hóa bởi Trung tâm Học liệu
Hình 2.1. (b) đẳng cấu với (a), (c) đẳng cấu với một đồ thị con của (a).
2.1.4.

Định nghĩa 2.4 (Subgraph Isomorphism):
Cho g
1
=(V
1
,E
1
,µ
1
,ν
1
) và g
2
=(V
2
,E
2
,µ

node và một số cạnh. Để minh họa hai đồ thị với một đồ thị con đẳng cấu giữa
chúng xem hình 2.1(a) và hình 2.1(c).
2.1.5.

Định nghĩa 2.5 (Maximum Common Subgraph, MCS):
Cho g
1
=(V
1
,E
1
,µ
1
,ν
1
) và g
2
=(V
2
,E
2
,µ
2
,ν
2
) là các đồ thị. Một đồ thị g
=(V,E,µ,ν) đƣợc gọi là một đồ thị con phổ biến của g
1
và g
2

n
},support(g) (
hoặc frequency(g)) là phần trăm (hoặc số) của các đồ thị trong D trong đó g
là một đồ thị con. Một đồ thị là thƣờng xuyên nếu độ hỗ trợ của nókhông nhỏ
hơn ngƣỡng hỗ trợ tối thiểu minsupport.

Hình 2.3. Mẫu cơ sở dữ liệu đồ thị
Hình 2.4. Các đồ thị con thƣờng xuyên
Ví dụ 2.1: Hình 2.3 biểu diễn một mẫu cơ sở dữ liệu đồ thị biểu diễn cấu
trúc hóa học , hình 2.4 mô tả hai đồ thị con thƣờng xuyên trong tập dữ liệu
này nếu độ hỗ trợ tối thiểu minsupport đƣợc thiết lập là 66,6%.
2.2.

CÁC DẠNG CHUẨN CỦA CÂY
Cây tự do (free tree) là một đồ thị vô hƣớng liên thông và phi chu trình.
Cây có gốc (gọi tắt là cây) là cây tự do, trong đó có một đỉnh đặc biệt đƣợc
gọi là gốc thỏa mãn các tính chất sau:
1. Tồn tại một đỉnh phân biệt không có các đỉnh đầu vào đƣợc gọi là nút gốc,
2. Mỗi đỉnh khác gốc đều có đúng một đỉnh vào,
3. Có đúng một đƣờng đi từ gốc tới các đỉnh khác của cây.

Số hóa bởi Trung tâm Học liệu
D
C
C
E
B
B
A
B
C
D
C
B
E
C
B
A
B
D
C
E
B
B
A
B
D
C
C
B
E
class="bi x14 yfb wc h16" src="data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAA3gAAAJfCAIAAACi0uMjAAAACXBIWXMAABYlAAAWJQFJUiTwAAAgAElEQVR42u3dT2hc18E34GN3oPAqoW6Jk0nbEBnS0BY8CqS0pHaJAxODbYoNDQXJxXUpXrQ0cot3XVSWF+nKtImyMKRJTYiU0mRhB+SAI0gCEiWE0HgEXZSAFJLFINHWoVKhaEDf4n7fvPpsWRrN3Llz75znWcqjZHTmzLm/83/X+vp6AACAtO1WBAAACJoAAAiaAAAImgAAIGgCACBoAgAgaAIAgKAJAICgCQCAoAkAAIImAACCJgAAgiYAAAiaAAAImgAACJoAACBoAgAgaAIAIGgCAICgCQCAoAkAgKAJAACCJgAAgiYAAIImAAAImgAACJoAAAiaAAAgaAIAIGhGYHV1dXFxceNPFhcXV1dXlQwAIGjSvvn5+Yceemjfvn0bf7hv377vfve7jUZD+QAAgibtmJubq1Qq9Xp9enp6489HR0drtdqlS5cUEQAgaLJjFy5cOHjwYLlcrtVqR48e3fhPFy9eLJfLTz/99C1T6tCJ5eXl+++///nnn2/+ZHFxcWhoaH5+XuEAIGj2iUajMTIyMjY2lqTM/fv33/KCUql0/fr1EMLx48dNoJOK+fn5ZPj8S1/6UvOHAwMDtVrt8OHDqhkAPfe58+fPK4UOra6ufv/733/jjTeq1eoHH3xw9913b/qy++6775577rl8+XKpVHr88ceVG524du3a9773vZWVldnZ2WPHjm0Mmvfcc89rr7322WefHTlyREGRevdm9+7dAwMDzdbv/fff//KXv7x7t2EL8ltRQwhzc3Mqam+s05mlpaVyuRxCGB8fX1tb2/rFa2trlUolhFCr1RQdbRsfHw8hJMPnm1azarWqmtGlijc8PNz8ycLCQghhdHRU4ZD/irrxJ2RG0OzI7OxsktcnJiZa/JWkupfL5W1TKWwaIoeHh5MqtLS0tEX/J3nNysqKQiOVijc6Onp7xdN5phAVdX19Pel+T09PKyVBszAmJyeTlDk7O7ujX5yYmDAGQBtWVlaStrJarW7bUUnqpx486Va827suzV6NzjM9T5lbVNSVlZVyubx1Fx1BM0e1uTl32UaVNbNJG3a0SEMPntQr3ujo6J0qnl4NhaioybGD1WpVcQmahekztd0xMrPJjrSxSEM1I5WKlzy8t614ejXkoaKOj49v/cpk6dHk5KRCEzTz22dKFiS1Mne5NWMA7KiqtLFIo9mDV83odsXTq6FXmtejtFJRkwn0EIIJdEEzjxYWFlrsM7XIGABb63CRhh48bWtWvIWFBb0a+qmiJhNEJtAFzdxpzl2mmAuNAbB1yux8kYYePFlWPL0asq+olUplpxU12Zm+o5VICJoZ9ZnamLs0BkB7nZBkkcbw8HDnm3ktgWenFa+91UF6NWRWUVs/gmPTkJpU1NbHQRE0u9hnutOhXGkxBsAtarVauos0VDNakcrqIL0aMkiZOz2CY9NmNhkNdSyXoNlLOzq2sJP/izEAmrqxSGNjD141o9sVL+mc69XQ1YraeQUzgS5o5qXPtMWhXGkxBkCie4s09ODJrOKZl6RLkutO2juCY9OKmiwUUVEFzd70mVKfu9yamc3IZbBIQw+ezCqeXg2pV9TOj+C4nUuhBc3e2NGhXCl+i8xsRiubRRrrhprIsOLp1ZBiw7XF3ZIdcim0oJm1Ng7lMgZAJ7JcpKGakVnF06sh3YqayhEcm1bUZALdpdCCZnZ9pjYO5TIGQHtav+Iv9R58ZstCiLbimZek845xBsvYVFRBM6M+UzZzl8YAaOrkbkk9eApR8cxL0rYsl7ElXwoVVdDsYm8m460/W3fgzGzGoIeLNPTgVbzMKp5eDR1W1MxqjkuhBc1uSfFQrnTHAMxs9qs8LNJYN9QUccXr8FJTvRq6XVGTY1i6egTH7VwKLWh28VnbpWMLjQGwaVuWh0UaG2OHahZJxevkbskOJfOS7tplW5kdwaGiCppZPGUzOLbQGAC3fKz5WaShB6/iZcm8JK20SJ3fLamiCpp5SZndO5QrLWY2+0wOF2nowUdV8Xr77NSrocWK2ttzV5JLofM5AiVoFq/P1KVDuVJMwybQ+0Y+F2nowfe9rl5qqldDunUj+yM4NuVSaEGzI9kcymUMgI0dhjwv0lDNVLwsuWuX2ytqN+6WVFEFzV52U3LSZzIGEEkbmv9FGs2vhmrWN3q7o2LrN+auXTZtIXNVJVRUQbP9R2mWh3KlJfkeFigck8j4bkk9eApR8cxL0qyoPTwJYVvJmlEVVdDcWaUZHh4uYu9kaWlpeHjYXUGFq28FWqShB99/FS/PN9nq1ZC3Izg25VLoVOxaX18PQKrm5uYOHjyYjEMfOHCgKG/72rVrx44dq1arb731lg+xiKampk6ePJn/itdoNB544IF6vb6wsDA4OOiDi7aFnJ6ePnr0qIra33YrAkjdz3/+82SRRoFSZgjh6NGjw8PDMzMzjUbDh1g4Fy5cOHnyZHK3ZM4rXqlUun79egjh+PHjKluEFfXgwYPJSQh5TpkqqqAJ+TUzM/PRRx/t37+/cO98ampqYWGhVCr5EAuk0Wg8+eSTY2Nj1Wq1VqsVYuhl//79o6OjtVrt0qVLPsF4KurZs2fHxsYK1A9XUTtn6hyg2M6ePfvcc89Vq9U333yzQJ2E5rzk0tLS3r17fY4qqoral4xoAhTexMTEW2+9Vayh6FKpVKvVRkdHv/jFL/oEY/Cd73xnfHy8WClTRe2cEU0AALrCiCYAAIImAACCJgAAgiYAAAiaAAAImgAACJoAACBoAgAgaAIAIGgCAICgCQCAoAkAgKAJAACCJgAAgiYAAIImAAAImgAACJoAAAiaxbO8vDw/Px/Vx9ZoNObm5lZXV+/0gmvXrm3xrwAAgub2VldXK5XK4cOHo/rYzp07d/DgweXl5TuVybFjx06cOKF+AwCCZvtOnDhRr9cvXrwYz2c2Pz//3HPPVSqVr371q5u+YGBgYHh4eGZm5tq1a6o4AHSDmcP+D5rPP//8zMzM8PDwyMhIPNU6Gb6dmZkplUp3etkLL7xQLpd/+tOf+hqkW/j333//1NRUVH/1hQsXdu3adad/nZubu//++xcXF1UPIB6NRmNoaOjMmTOKop+D5vz8/NNPP10ul19++eV4PrAzZ87U6/XJycm9e/du8bKBgYGLFy/W63VfgxQlw+d79uyJ50+em5sbGxurVqt3esFXvvKVer1+/PjxRqOhhgCRuHTpUq1W++53v6sotrdeTGtra+VyOYSwsLCwHo3p6ekQQrVabfH1ST6o1WrrdGxiYiKEMDw8HM+fvLKyknzLlpaWtnjZ6OhoCGFyclIl6cZXPqombn19fWlpadO6tLa2FkKYnp5WK/JZUaN60CwsLIQQKpXK2traxp9PTk7e8hPW19eLGjSHh4dDCBMTE576WzfZIYRyuazqd6hWq0VYksm3bNsE2ez1tV4zab1jGVUr16xLd/onrVkOzc7ORtUJX1tbq1Qqt49zJekzqsGIfg6ak5OTOxrY6w/J8OROO/TJONz4+Li63vnDz/D51k+a2L6SXdXsJa6srOjbJMbHx0MIs7Ozqkd+tDECUnTJU3XTHuCmAZTiBc04298kW7fRVbpT34udPvyiGlhaWlpKRo9a/5YlpWRmM62+TfK1jSpUbdu3WVlZSeYr1ZD8aG8EpLjuNGm+8V8NahY7aDbb36iWg3SYrbf+YtBKxDd83uLARmw9wC5Jlr1GNRHR4sCYQc1ciW3leisJJOly2xpR4KAZYfu7traWPPU7aVtt1+ik82r4vNu/yEbJOoTYeoYtjognX0mLNPIgwpXrSbAeHR3dtooady9q0GxOrETV/rZSs1tJq7ZrdKPz2n86HD530EHn5R/hV3VHXZQkkloL1PPmMbaV681xh20TSFJFjbsXL2jG2f62XrO3ZbvGTsU5fN5htk6xxsb58I5txVsbfZtkIM3AeW/FtnJ9R21jczGxZrBIQTPO9jf1ETXbNVpn+LzD/0hUe6dyVf6F00bbnjSMVgP3SoQr13f63UwWE1uuVqSgGWf7m9TUFEfUkm6W7RrbMnyeSgfJ5OaOxHlWa3ttezI/49S2XjWPsT1H2mgbm09bg5rFCJpJ+xvbKHSX/uqkJxpbZN9pTopz+DzFFVfN2qs6tf5YivCs1k76NgY1e9VQxLZyve0/OXnaGtQsQNCMs/3t6jpr2zW2lgwkx5bFkwWpKc53O+hgR1q8hMnz21M8Dw1FVGPJbU+oNp/jukN5D5pJKoqtNUn9qZ/WKELfM3yeemfJQQctZqbYNup1uDTIjZTZi3DleoePy+SrbY1HroNmnMfy7ejqv066aLZr3MLweTdqst3BLT7Johr2SKVvk7RjBjWzEeHK9c7XCTT/C5EPauY3aMbZ/mZzb6ztGpuKc/i8q5O2DjpoMeVHtZQlrb6NGymz/MgiXLmeyi7kZONa5P3tkNtqHWH7u57hUi3bNW5h+LxLHScHHWyhq4tkYvir3UhZoMhVLCmuMTOsk9OgGWf7m8Gk+e2FbOJpPdZ1q9kMnzvoYNvve1S1rnlzRCp/dXLUjg5zNqMS8VTUdDfXu2Igj0Ez47yVE9kfTma7xi3lENvweWZzYRHe5Nn69z2qb183+jZupMzmI4uqhFMfwY28luYuaMbZ/mb51L8900e+fCS2u9QSWS4VSAaMXci2sW+TfN9jm/PtxtKgpHbZc9bVB1NUE1/dmOBqtoGCZi7a32TwI7b2t4cLBCPfrmH4PMsRAgcdJOI8q7V737UkDDlIq58eTD3UpRmY5FEb53rifAXNONvf3i4QjPA+sdv/dsPnGfQhI5yA21SySDG28d2utjNupOzqgymqR0P31pTHfEhCjoJmnO1vHm70inO7RrTD573aQJqsiI9t8Pj2h02cC6O73bdxWmGXeoZRLa1udoe6FEKSobQIN+CG/HzAcba/OTk2IsLtGh1eTFL0UYqedOccdBDnWa0ZzMAm8/IGNdMS58r1bt/P3DzuLbbV6iFXH3BsKwXzc6pObNs1DJ/35A00x/PiHHlKepWxrXjLZnGOGylTT+2xTT5kM7OX/F9i62rmImjG2f7mbdVaPNs1oh0+z8MgbrQHHcR5VmuWfZs4H+Hd6xhE1Tx2e9L89h5RVJ3t3gfNZOVWhD3RvB1KH892jTiHz/Nz6nKEBx1Euxcqy6VBzXlJYbHzjkFsK9e7PWl+e48oqmUeoefVOs72N593LcSwXcPweTyDB/kR54q37Adx3UiZSgHGttQ14+2wzTQfz6Bmj4NmnO1vnnee9vd2DcPncbbsefhjY1vx1pO+TcwnyHQu8oO3svyrk6KO56SXXgbNONvf9e5cj5F6CO6/zla0w+fp3i6dlkgOOoj2nNpe9W2S/6/7TtuoqDEfvJV9hUkawEgeRj0LmnEeBrtehA19/bpdI8/5PoOeQ96eHzEcdBDtirceLg1yI2UneSu2les9nFpJ+v+RVNTeBM08nFLew6d+/jf09d92DcPnOXxvyYKwPl45k4yuxbbiredTB0mddwdV6xy81auKGskyj94EzTjb3wL1Gvtsu4bh85wnkr6crcvnioUY+jaxLYDrULQr1/PwOI7kkdSDoNl8+MVWrTO4HiP1d9sHjXW0w+eFWB3YrwcdRLviLSd9GzdS7rSzF9sAcLEex4JmO+1vbIfBrhdwT0AznxW9ATJ8nvP32X9rZ9fW1uJc8ZafBcHJoKYbKSP89vXl41jQ1P7u4KlfrD0BfbBdw/B5UdJJPzX6WZ5Srm9zp2dNEnndSLltKxHhyvVoc0gUQTNZ+x/n0pmCdq8LvV0jzrvUithf76eDDqJd8Za3vo0bKVsZR4hwVM+kefZ2JRkoA/Pz85VKpVKpfPDBB6VSKVAEjUbjgQceqNfrS0tLe/fuLdY7P3LkyMzMzPT09NGjR6P6yB599NFarVar1fbv31+Ut/3kk0/OzMzMzs4eOHCguIW/urr60EMP1ev1hYWFwcHBeGrd8vLyvffeWy6XP/roo4GBgfy0XSGETz75xBOnP1qJvqyoMdidWft7+PDhEMLVq1d95wukVCpdv349hDAyMlKsd/7MM8/MzMyMjo5GlTJDCJ9++mmtVhsdHS3W82NqaiqE8NRTTzUajeIW/okTJ+r1+uTkZFQps9k+vPjii/l5eJdKpZ/97Gf1ev29997Tkt/i3LlztVptfHw8qpSZz4oaBbMYbKtw59Ll8yr5bKysrMzOzhbxDy/6QQfRTsnldk2qGym3WKli5Tr9NnW+uLj473//O7bOUz/Ns7z33ntFmdNsTl8WbrpfNUum84o477y4uLhv374Ip+Sac5H5nKGempr64x//+NZbb/l+NT+v5nFvUTWPq6urd911l0nznsho6nxwcFDKLK5SqVSglXO//vWvk+lLKbNw1ezq1ashhOPHjxcuIj/22GMhhOvXr8f2DFtdXa1UKtevX8/nmqiRkREpc2NFHRkZqdfrL774YoTNY6VSef3116XMHrTtioA+87WvfW18fLxwi0pJeqQTExP//Oc/i/W2z507V6/XJyYmIuxODw4O3rhxQ9UthGhXrocQBgYGVNReyW7XOUD/uXbt2rFjx6rVqpEz8szBL/TKbkUA0LZXXnmlXC4nu+Yht377298GB7/QC0Y0Adq3vLwcQrAgmJxbXV39z3/+o6IiaAIA0CdMnQMAIGgCACBoAgAgaAIAgKAJAICgCQCAoAkAAIImAACCJgAAgiYAAD3QaDSmpqYWFxcFTQAA0nTq1KmTJ0/+7W9/EzQBAEjNhQsXXn311Wq1evjw4eYP5+fnp6amGo2GoAkAQDuuXbs2NjZWqVTefPPNUqm0MWiePHny0qVLRf8Dd62vr/uYAQAyNjc3d/DgwXK5XKvV9u7du/GfGo3GAw88UK/Xl5aWbvmnYjGiCQCQteXl5aeeeiqE8Je//OX2KFkqlV5//fUQwsjISKH/TEETgD4xNzc3NDS0vLysKMi51dXVSqVSr9dnZ2cHBwc3fc2BAweGh4dnZmampqaK+5eaOu+KCxcu/OMf/3j22WcVBUBmKTOZhfzoo48GBgYUCLnVaDSOHDkyMzMzMTHxi1/8Yus8+tBDD4UQilurjWh2JWWOjY315SEFAPm0cRZy4/N4ZGTk7NmzyodcOXXq1MzMzOjo6NYpM4QwMDBw8eLFer1+5syZgv6xgmbKNm4f2/jzoaGhQg99k+cq15dn/ELrtpiF3Lt373PPPXft2jWlRE40DzO6ePFiK68fGRmpVquvvvrq3NxcEf9eU+dp2mL72NDQUK1WW1hYuNNSDGivwRobG5ucnCz6anFoW3MWcnx8/De/+c3tGbToM4/0ZU745JNPNh5mtLXl5eV77713p7+VE0Y0U7P19rFXXnklhHD8+HEFRYoN1tjYWLlc/uEPf7jxsdofZ/xCi86dO5fMQt6eMkNfzDzSN+bn55ujUTvKi3v37p2cnKzX6+fOnSven71OGtbW1srlcghhdnb2Tq8ZHR0NIUxOTiouOler1UII5XJ5aWlp488XFhZCCKOjo4qIGIyPj4cQqtXq2traFi+rVqshhFqtpsTolaWlpSQntFcP19bWKpVKCGFhYaFYf7ip865P3Gx8WX8cvkoehs+bK9IOHDhwy78m6zRqtdr+/fuVFf09qN/iLGShZx7pj5yQBIBNG+0WLS4u7tu3r1KpfPDBBwWqxqbOuz5x01QqlV588cUQgi2QdNhgVavVer0+PT29aYN19erVEMKPfvQjE+j0sR3NQu7du3diYqJerz/zzDOKjuwb7SNHjtTr9fHx8bZTZghhcHBwfHy8VqsV7F5Ko9nZTNw0DQ8PhxCmp6cVHe3NniSTgOPj41u8bGJiIoQwMTGhxDALWfSZR4ouWTiXyoqm5jq9WxZN5Zmg2ZHZ2dkQQrlcbjFlJu3jTn8FbunYDA8Pt9gYeabSl92tbdfEbypZwVypVDS/ZNxotz4ata1kgX61WhU0+9+ddmNsa3J