Đề tài Phần mềm tối ưu chi phí quảng cáo trực tuyến Easy-Op

HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG KHOA CÔNG NGHỆ THÔNG TIN ---o0o--- Báo cáo nghiên cứu khoa học sinh viên ĐỀ TÀI: Phần mềm tối ưu chí phí quảng cáo trực tuyến Easy – Op GV Hướng dẫn : Ts. Phạm Hoàng Duy Ths. Nguyễn Thị Ngọc Vinh Hà Nội, Tháng 11 năm 2011 Table of Contents LỜI MỞ ĐẦU Sự đổi mới không ngừng của khoa học kỹ thuật công nghệ, nhiều lĩnh vực đã và đang phát triển vượt bậc đặc biệt là lĩnh vực công nghệ thông tin. Thành công lớn nhất có thể kể đến là sự ra đời của chiếc máy tính. Máy tính được coi là một phương tiện trợ giúp đắc lực cho con người trong nhiều công việc đặc biệt là công tác quản lý. Mạng máy tính được sinh từ nhu cầu muốn chia sẻ và dùng chung dữ liệu. Máy tính cá nhân là công cụ tuyệt vời giúp tạo dữ liệu, bảng tính, hình ảnh, và nhiều dạng thông tin khác, nhưng không cho phép chia sẻ dữ liệu bạn đã tạo nên. Sự bùng nổ dịch vụ Internet cũng như bùng nổ số lượng người sử dụng khi công nghệ trở nên thân thiện với con người, các cơ hội đã được mở ra với một thị trường cực kì rộng lớn cho các doanh nghiệp, các sản phẩm, dịch vụ được phân phối và cung cấp rộng khắp, nhanh chóng và cực kì tiện lợi. Để thông tin về sản phẩm của mình, các doanh nghiệp thường sử dụng các hình thức quảng cáo, tuy nhiên với chi phí đắt đỏ, cho dù mang lại hiểu quả cao nhưng các hình thức quảng cáo trên truyền hình, báo chí chưa thực sự tối ưu. Từ thực tế đó, các hình thức quảng cáo qua thư điện tử, máy tìm kiếm thông tin trên mạng đã dần có được sự quan tâm đặc biệt. Với những doanh nghiệp mới thành lập, quảng cáo trực tuyến là một sự lựa chọn hoàn hảo để cân bằng giá và hiệu quả. Đã có rất nhiều doanh nghiệp sử dụng các hình thức quảng cáo trực tuyến để mang sản phẩm và dịch vụ của mình đến người tiêu dung với chi phí thấp. Điều quan trọng của loại hình quảng cáo qua máy tìm kiếm là khi được lựa chọn kĩ càng và tối ưu, chi phí sẽ giảm xuống rất nhiều. Chính vì đó em đã chọn đề tài Xây dựng phầm mềm tối ưu hóa chi phí quảng cáo trực tuyến. Nhưng do thời gian và kiến thức có hạn nên bài viết còn hạn chế, rất mong được sự góp ý của các thầy cô giáo và chung em xin chân thành cảm ơn TS.Phạm Hoàng Duy, ThS. Nguyễn Thị Ngọc Vinh đã giúp đỡ để em hoàn thành đề tài này. CHƯƠNG I :TỔNG QUAN VỀ E - MARKETING E-marketing (Internet marketing hay online marketing), hay tiếp thị qua mạng, tiếp thị trực tuyến là hoạt động cho sản phẩm và dịch vụ thông qua mạng kết nối toàn cầu Internet. Sự xuất hiện của Internet đã đem lại nhiều lợi ích như chi phí thấp để truyền tải thông tin và truyền thông (media) đến số lượng lớn đối tượng tiếp nhận, thông điệp được truyền tải dưới nhiều hình thức khác nhau như văn bản, hình ảnh, âm thanh, phim, trò chơi,... Với bản chất tương tác của E-marketing, đối tượng nhận thông điệp có thể phản hồi tức khắc hay giao tiếp trực tiếp với đối tượng gửi thông điệp. Đây là lợi thế lớn của E-marketing so với các loại hình khác. E-marketing kết hợp tính sáng tạo và kỹ thuật của Internet, bao gồm thiết kế, phát triển, quảng cáo và bán hàng. Các hoạt động của E-marketing bao gồm: search engine marketing, web display advertising, e-mail marketing, affiliate marketing, interactive advertising, blog marketing và viral marketing. Một trong những lợi thế của E-marketing là sự sẵn sàng của lượng lớn thông tin. Người tiêu dùng có thể truy cập thông tin sản phẩm và thực hiện giao dịch, mua bán mọi lúc mọi nơi. Doanh nghiệp sử dụng e-makerting có thể tiết kiệm được chi phí bán hàng như chi phí thuê mặt bằng, giảm số lượng nhân viên bán hàng,.. E-marketing còn giúp doanh nghiệp tiếp cận với thị trường rộng lớn cũng như phát triển ra toàn cầu. Ngoài ra, so sánh với các phương tiện khác như in ấn, báo đài,  truyền hình, e-marketing có lơi thế rất lớn về chi phí thấp. E-marketing đã và đang có ảnh hưởng rộng lớn với nhiều ngành công nghiệp như âm nhạc, ngân hàng, thương mại, cũng như bản thân ngành công nghiệp quảng cáo. Trong ngành công nghiệp âm nhạc, nhiều khách hàng mua và tải các bản nhạc qua Internet thay vì mua CD. Ngày càng nhiều ngân hàng cung cấp các dịch vụ trực tuyến. Dịch vụ ngân hàng trực tuyến được cho rằng sẽ hấp dẫn khách hàng hơn khi họ không phải đến các chi nhánh ngân hàng để thực hiện. Hiện tại, hơn 150 triệu người Mỹ sử dụng dịch vụ ngân hàng trực tuyến và tốc độ tăng trưởng ngày càng cao. Sự cải thiện tốc độ kết nối Internet là nguyên nhân chính cho sự tăng trưởng này. 44% những cá nhân sử dụng Internet thực hiện các giao dịch với ngân hàng qua Internet. Đấu giá qua Internet cũng đang trở nên phổ biến. Những mặt hàng hiếm trước đây chỉ có thể tìm ở các chợ trời nay đang được rao bán trên eBay. Trang Web nay cũng có ảnh hưởng mạnh đến giá cả. Người mua và người bán thường tham khảo giá trên eBay trước khi đến chợ trời và giá trên eBay thường trở thành giá mà sản phẩm được bán. Ngày càng nhiều người bán hàng ở chợ trời rao bán hàng trên eBay và điều hành công việc kinh doanh ở nhà. Sự ảnh hưởng của E-marketing lên nền công nghiệp quảng cáo ngày càng lớn. Chỉ trong vài năm, quảng cáo trực tuyến tăng trưởng đều đặn đến hàng chục tỷ USD. Theo báo cáo của Pricewaterhouse Coopers, thị trường E-marketing Mỹ trị giá tổng cộng 16,9 tỷ USD trong năm 2006. Trong tất cả các công cụ của E – Marketing, Seach Engine Marketing và thiết kế web là một trong những công cụ không thể thiểu đế tạo nên thành công của chiến dịch Marketing. Trong xu thế phát triển của mạng Internet như hiện nay. Mọi thứ đều có thể được đưa lên mạng để cùng chia sẻ. Người tiêu dùng đã mặc nhiên coi Google là một công cụ tìm kiếm hữu hiệu và với họ. Họ mặc định rằng mọi thứ muốn tìm kiếm thì cứ lên trang Google tìm là có. Do vậy việc đòi hỏi tối ưu hóa công cụ tìm kiếm cũng như các hình thức quảng cáo trên máy tìm kiếm là rất cần thiết trong môi trường đầy cạnh tranh hiện nay. CHƯƠNG II: GIỚI THIỆU CÔNG CỤ TÌM KIẾM 1. Công cụ tìm kiếm là gì? Công cụ tìm kiếm(Search Engine) là một hệ thống thu thập thông tin được thiết kế để giúp cho việc tìm kiếm thông tin lưu trữ trên một hệ thống máy tính. Công cụ tìm kiếm tối thiểu hóa thời gian cần thiết để tìm kiếm thông tin bằng việc lưu trữ và xử lý thông tin theo nhiều cách. Dạng phổ biến nhất của công cụ tìm kiếm đó là công cụ tìm kiếm Web (Web Search Engine) . vd: Google Search, Yahoo Search, … Công cụ tìm kiếm cung cấp một giao diện giúp cho người dùng có thể chọn thông tin cần tìm và có cơ chế xử lý và tìm được thông tin tương ứng. Thông tin cần tìm sẽ tương ứng với một câu truy vấn. 2. Nguyên tắc hoạt động của công cụ tìm kiếm. Một công cụ tìm kiếm được gọi là thành công nếu nó thỏa mãn được 3 điều kiện: - Cho phép tìm kiếm trong một tập hợp lớn các trang web. - Đưa ra kết quả gần với mong muốn của người sử dụng nhất. - Tốc độ tìm kiếm chấp nhận được. Để đạt được các mục đích trên, các công cụ tìm kiếm hiện đại đều tiến hành lần lượt theo bốn bước: web crawler, indexing, rank page và searching. Sau đây ta sẽ đi chi tiết vào từng phần. 2.1. Web crawler: Web crawler là bộ phận chịu trách nhiệm download các trang web và lưu trữ chúng dưới dạng nén ở trong kho dữ liệu. Mục đích thiết kế của web crawler là làm cho nó download được số lượng trang web nhiều nhất trong khả năng đáp ứng của tài nguyên mạng và tốc độ, khả năng lưu trữ của máy. Hình1.2a - Hoạt động của web crawler Tất cả các công cụ tìm kiếm đều dựa trên mô hình web crawler như hình 1.2a Một Webcrawler sẽ sử dụng hai hàng đợi để quản lý các URL, đó là URLsToVisit (URL sẽ tới) và VisitedURLs (URL đã tới). Hàng đợi VisitedURL chứa danh sách các trang đã được download. Danh sách này rất quan trọng đối với các crawler để tránh việc download một trang nhiều lần. Trong khi đó hàng đợi URLsToVisit chứa danh sách các trang sẽ được download. Nội dung ban đầu của hàng đợi URLsToVisit được gọi là seed list (danh sách hạt giống). Danh sách này sẽ ngày càng mở rộng theo thời gian. Trước khi crawler chạy lần đầu tiên, danh sách URLs hạt giống này sẽ được khởi tạo một cách thủ công hoặc có thể được lấy từ một số nguồn khác. Danh sách khởi tạo này lúc đầu có thể là một tập các web site bất kỳ, hoặc có thể là một tập các web site có chủ đề nhất định do người khởi tạo quyết định. Webcrawler hoạt động dưới dạng các vòng lặp nối tiếp nhau. Một vòng lặp sẽ bắt đầu với việc lấy một URL từ hàng đợi URLsToVisit, tiếp đó webcrawler sẽ download trang web tương ứng với URL đó, lưu trữ trang web đó vào trong kho và đẩy URL đó vào trong hàng đợi VisitedURLs. Trong mỗi vòng lặp, webcrawler sẽ trích tất cả các link mà trang web vừa được lấy về, chuyển nó từ dạng link tương đối sang dạng link tuyệt đối, rồi kiểm tra ở hàng đợi VisitedURLs xem các trang này đã được download về chưa. Nếu URL nào đã được download về rồi, nó sẽ bỏ qua URL đó còn nếu chưa được download, nó sẽ chuyển URL đó vào hàng đợi URLsToVisit. Quá trình này sẽ được lặp đi lặp lại cho đến khi nào hàng đợi URLsToVisit rỗng hoặc nó được dừng lại một cách có mục đích bởi người điều khiển. Nếu việc lấy về một URL thất bại, crawler sẽ chuyển URL đó ngược lại vào hàng đợi URLsToVisit để thử lại lần sau. Nếu như việc lấy một URL thất bại trong nhiều lần, crawler sẽ bỏ qua nó vì rất có thể webserver chứa URL đó đã không còn hoạt động nữa. Theo cách này, một crawler có thể lấy về một số lượng lớn các trang web chỉ từ một lượng rất nhỏ URL trong danh sách khởi tạo (seed list). Để có thể hiểu kỹ hơn về webcrawler, ta sẽ tìm hiểu những thiết kế và những rủi ro tiềm ẩn có thể gặp phải trong việc cài đặt và điều hành một webcrawler mức độ lớn. Crawler song song Hình 1.2a chỉ nêu nguyên tắc hoạt động chung của 1 crawler riêng biệt, nó chỉ sử dụng một hàng đợi URLsToVisit và một hàng đợi VisitedURLs. Mô hình trên là tổng quát cho các crawler nhưng có các nhược điểm sau: - Dung lượng của bộ nhớ chính sẽ giới hạn kích thước của các hàng đợi URL, khi số trang web tăng lên rất lớn, một crawler riêng lẻ sẽ có thể bị quá tải và hiệu năng sẽ không cao. - Tốc độ download các trang web về sẽ chậm do tiến trình download diễn ra một cách tuần tự. Để giải quyết vấn đề trên, người ta đưa ra mô hình crawler song song (parallelism) Web site – đơn vị cho quá trình crawler song song Trước hết ta định nghĩa: một web site là một tập các trang web có cùng một tên miền đầy đủ trong URL của nó. VD: các trang và trang sẽ thuộc cùng một website trong khi đó trang sẽ không thuộc cùng một Site với hai trang trên. Vì vậy các link tương đối chắc chắn sẽ nằm trên cùng một site với trang đang xét còn các link tuyệt đối sẽ cần phải kiểm tra trước. Hình 1.2b - Mô hình crawler song song Tiếp theo ta sẽ làm rõ mô hình crawler song song. Hình 1.2b cho chúng ta thấy mô hình chung của một webcrawler song song. Mô hình này thực chất là một tập hợp các phần tử của mô hình crawler riêng biệt trong đó mỗi một crawler sẽ chịu trách nhiệm lấy về các trang web của chỉ duy nhất một Site và tiến trình lấy về các trang web này sẽ được diễn ra một cách đồng thời giữa các crawler trong mô hình. Một điểm đáng lưu ý là mô hình trên đưa ra một bộ phân phối các URL khởi tạo (seed-URL dispenser). Bộ phân phối trên chứa danh sách tất cả các URL khởi tạo cho tất cả các tiến trình crawl. Mỗi một phần tử trong danh sách trên chứa các URL khởi tạo cho chỉ một Website, thông thường nó chứa URL gốc của site đó. Trong mô hình trên, mỗi một site crawler sẽ bắt đầu bằng việc lấy về URL khởi tạo cho một Website từ bộ phân phối URL và sử dụng nó để khởi tạo cho hàng đợi URLsToVisit. Crawler sẽ đẩy vào hàng đợi URLsToVisit các URL mà nó lấy được trong site đó. Nguyên tắc của nó là nếu gặp các link ở trong site đó, nó sẽ lấy về còn nếu gặp các link ở ngoài site đó, nó sẽ bỏ qua. Việc sử dụng crawler song song có giải quyết được các nhược điểm của crawler riêng biệt. - Dung lượng của bộ nhớ chính sẽ không còn là vấn đề vì mỗi một site crawler chỉ lấy về các trang web có URL nằm trong site đó, do đó kích thước của các hàng đợi URLsToVisit và VisitedURLs không quá lớn. - Tốc độ download các trang web lớn do việc lấy các trang web về diễn ra đồng thời. Các trang web không liên quan đến nhau sẽ được lấy về cùng một lúc. Đó là nguyên tắc hoạt động chung của crawler, tất nhiên việc crawler không chỉ phụ thuộc vào nguyên tắc hoạt động, cấu trúc của nó mà còn phụ thuộc vào các yêu tố khác trên các trang web mà nó cần phải giải quyết. Một vấn đề điển hình đó là việc lấy về các trang web sẽ sinh ra những lưu lượng lớn trên đường truyền, và sẽ chẳng thú vị gì nếu những người chủ các site đó phải trả tiền cho băng thông của họ. Một cách tự nhiên, có những luật đã được phát triển để quy định phương thức hoạt động của crawler, tuy không có ai chịu trách nhiệm hay đứng ra bảo đảm cho những luật này nhưng các crawler tốt đều chấp nhận và thực hiện đúng theo nó. Thời gian trễ Như chúng ta đã đặt vấn đề ở trên, việc tìm ra thời gian chạy một vòng lặp là rất quan trọng, nó phục thuộc vào kích thước và băng thông của mỗi site. Các site có kích thước và băng thông chênh lệch nhau quá lớn không thể có cùng một thời gian chạy các vòng lặp. Thông thường đối với mỗi site, crawler sẽ lưu thông tin về thời gian trễ tương ứng với site đó ở chính trong danh sách URL khởi tạo. Ví dụ như mặc định của thời gian trễ của webBase crawler là 5 giây cho các trang web thương mại lớn và 20 giây cho các trang web nhỏ. Tuy nhiên điều này không cố định, các chủ nhân của site đó có thể liên lạc và thỏa thuận với quản trị của search engine về thời gian trễ này. Các quy định đối với từng Server Khi một quản trị web không muốn một số trang của họ bị crawl, họ sẽ sử dụng một công cụ đặc biệt đó là giao thức Robots Exclusion. Giao thức này bắt buộc tất cả các crawler sẽ phải tìm file robots.txt ở thư mục gốc của site đó. File này sẽ liệt kê một danh sách các URL mà crawler không được lấy về và một crawler tốt sẽ tuân theo quy định này. Một trong những nhược điểm của crawler song song đó là vấn đề các trang cô lập địa phương. Bởi vì các site crawler không theo các link tới các trang ở ngoài site đó nên có thể có nhiều site sẽ không được lấy về. Hình 1.2c chỉ rõ vấn đề này. Hai Website S1 và S2 được download bởi hai site crawler C1 và C2. Vì trang d chỉ có thể đến thông qua link từ site S2 nên các trang d và e sẽ không bao giờ được download bởi bất cứ crawler nào. Bằng cách kiểm tra các nhanh các trang có được trong lần crawl trước. Nếu một trang trong lần kiểm tra trước có một link tới trang d, nhưng trang d không tồn tại trong lần kiểm tra này, trang d sẽ được cho vào bộ phân phối URL khởi tạo cho lần crawl tiếp theo. Hình 1.2c - Các site bị khuất Crawler đơn tiến trình Một cách tiếp cận thiết kế điển hình như trên là mô hình thiết kế một tiến trình gắn với một site (process-per-site). Cách thiết kế này sẽ thực hiện mỗi site crawler như một tiến trình độc lập, nó sẽ trút gánh nặng quản lý song song vào bộ phận điều khiển tiến trình của hệ điều hành. Trong khi đó, thiết kế crawl đơn tiến trình (single-crawl-process) gói tất cả các site crawler vào một tiến trình duy nhất và quản lý các yêu cầu như một vòng lặp sự kiện. Trong thiết kế này, vòng lặp được tạo ra các sự kiện site request một cách tuần tự sau khi đã có thời gian trễ. Cách tiếp cận này được chỉ ra trong hình 1.2d. Hình 1.2d - Crawl nhiều site trên một tiến trình Hình trên cho thấy 2 crawler chạy trên cùng một tiến trình. Ngược lại với thiết kế ở hình 1.2a, việc cài đặt crawl đơn tiến trình đưa ra một bộ đếm thời gian trước khi lấy về các trang từ URLsToVisit. Bộ đếm thời gian này sẽ quyết định độ trễ trước mỗi một lần request trang đó. Vòng lặp sự kiện trung tâm sẽ điều khiển việc đồng bộ các crawler. 2.2. Indexing: Khối Indexer được dùng để xây dựng và bảo trì các chỉ mục phục vụ cho các truy vấn. Khối Indexer xây dựng 3 chỉ mục cơ bản: chỉ mục offset (offset index), chỉ mục text (text index) và chỉ mục link/graph (link/graph index). Offset index ghi nhận vị trí vật lý của mỗi trang web trong cơ sở dữ liệu, nơi mà lưu trữ các trang web đã được nén. Chỉ mục này cho phép truy xuất ngẫu nhiên tới 1 web cho phép trong cơ sở dữ liệu. Text index cho phép truy vấn hướng nội dung, sử dụng các chỉmục ngược để sung cấp tìm kiếm theo từ khóa trong cơ sở dữ liệu. Cuối cùng, link index cung cấp truy vấn hướng liên kết (VD: Gọi đến tập các trang mà trang X trỏ tới ). Sử dụng 3 chỉ mục cơ sở này và các trang web, khối Phân Tích sẽ xây dựng lên các chỉ mục gốc khác nhau. Ví dụ, sử dụng chỉ mục liên kết và các thuật toán lặp PageRank, khối phân tích sẽ tính toán và lưu trữ PageRank của mỗi trang trong cơ sở dữ liệu ( chỉ mục PageRank ). Tương tự, bằng cách kết hợp thông tin liên kết và nội dung của trang web, khối phân tích có thể xây dựng một chỉ mục tương tự mà ánh xạ mỗi trang tới 1 tập các trang tương tự. Thiết kế chiến lược Ảnh hưởng to lớn bởi số lượng khổng lồ các trang Web trên mạng, chúng ta phải thiết kế một lược đồ xây dựng và cấu trúc biểu diễn mới cho rất nhiều chỉ mục được sử dụng. Thiết kế này có các đặc điểm sau: - Chỉ mục được xây dựng song song và phân tán. Do kích cỡ khổng lồ của mạng không cho phép thực hiện trực tiếp lược đồ xây dựng chỉ mục tuần tự đơn giản mà áp dụng rất tốt cho các tập hợp dữ liệu vừa và nhỏ ( khoảng vài triệu văn bản hoặc hình ảnh của vài nghìn node ). Cách thực hiện song song và phân tán các tính toán tích kiệm lớn chi phí và thời gian thực hiện. - Nén và bộ đệm của cấu trúc chỉ mục. Nhiều chỉ mục trên mạng quá đồ sộ để có thể chứa trong bộ nhớ chính. Vì vậy, chỉ mục được nén và lưu đệm là giải pháp nhằm giảm thiểu thời gian truy cập các chỉ mục. - Định danh trang đặc tả chỉ mục. Điều này cấn thiết cho mỗi cấu trúc chỉ mục để tận dụng các định danh đặc tả chỉ mục của chính nó để giảm thiểu thời gian truy nhập và kích cỡ chỉ mục. Chỉ mục văn bản ( Text index) Để cung cấp dịch vụ hướng văn bản cơ sở, chúng ta xây dựng các chỉ mục ngược thông qua tập các trang web trong cơ sở dữ liệu. Kích cỡ của cơ sở dữ liệu các trang web lưu trữ và sự cần thiết của việc thu thập định kì và xây dựng lại chỉ mục yêu cầu chúng ta xây dựng một lược đồ xây dựng chỉ mục tin cậy và hiệu quả cao. Việc xây dựng các chỉ mục ngược tăng tối đa tốc độ và khối lượng sử lý index cho hệ thống. Do đó các hệ thống hiện nay đều sử dụng phương pháp này để tiết kiệm tài nguyên. Hình 1.2e - Chỉ mục văn bản Chỉ mục ngược xây dựng hệ thống kiến trúc không chia sẻ phân tán như hình trên. Chỉ mục ngược được xây dựng thành 2 giai đoạn. Giai đoạn đầu tiên, mỗi một chỉ mục nhận một tập con tách rời của trang web. Khối Indexer sẽ phân tích và trích dẫn các đoạn từ trang web, sắp xếp các đoạn vào trong bộ nhớ, và chuyển chúng vào cấu trúc hiện tại trên đĩa. Trong giai đoạn thứ hai, các cấu trúc này được trộn lẫn nhau để tạo ra một hoặc nhiều file phân tán. Hai chức năng chính của hệ thống là đánh chỉ mục song song mức độ cao và việc sử dụng hệ thống cơ sở dữ liệu nhúng để lưu trữ và quản lý các file chỉ mục ngược. Đánh chỉ mục song song mức độ cao. Chúng ta chia quá trình sắp xếp thành ba pha: pha tải (một số trang được đọc từ luồng đầu vào và được lưu trong bộ nhớ), pha xử lý (các trang được phân tích và đánh dấu để sinh ra các đoạn, mà sau đó được sắp xếp thứ tự), và pha ghi