Gi i thi u v tìm ki m thông tin
Khái ni m v công c tìm ki m
Công cụ tìm kiếm (Search Engine) là hệ thống thu thập thông tin được thiết kế để hỗ trợ việc tìm kiếm dữ liệu trên mạng máy tính Công cụ này tối ưu hóa thời gian cần thiết để tìm kiếm thông tin bằng cách lưu trữ và xử lý dữ liệu theo nhiều phương pháp khác nhau.
_ 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 người dùng dễ dàng chọn thông tin cần tìm và có cách xử lý phù hợp để tìm được thông tin từ ngữ Thông tin cần tìm sẽ được tối ưu hóa với một câu truy vấn.
M t s v n đ trong vi c tìm ki m thông tin
Kể từ năm 40, việc lưu trữ và tìm kiếm thông tin đã trở thành một vấn đề thu hút sự chú ý lớn Trong bối cảnh thông tin khổng lồ hiện nay, việc tìm kiếm chính xác và nhanh chóng càng trở nên cần thiết và khó khăn hơn Sự phát triển của máy tính đã tạo ra nhiều yếu tố mới giúp cung cấp một hệ thống tìm kiếm thông tin thông minh và chính xác Tuy nhiên, vấn đề tìm kiếm hiệu quả vẫn chưa được giải quyết triệt để.
Việc lưu trữ thông tin hiện nay rất đơn giản, nhưng khi có một kho dữ liệu lớn, người dùng gặp khó khăn trong việc tìm kiếm tài liệu liên quan đến yêu cầu của mình Họ cần phải xác định tất cả các tài liệu trong kho, lọc ra những tài liệu có liên quan và loại bỏ các tài liệu không liên quan Tuy nhiên, phương pháp này không thực sự hiệu quả vì tốn rất nhiều thời gian.
Với sự phát triển của công nghệ máy tính, việc trích xuất tài liệu liên quan từ một tập dữ liệu lớn trở nên khả thi hơn Tuy nhiên, thách thức hiện tại là xác định chính xác tài liệu nào liên quan đến câu hỏi đặt ra Mục tiêu của hệ thống tìm kiếm thông tin là truy lục hiệu quả tất cả các tài liệu có liên quan đến yêu cầu của người dùng.
H tìm ki m thông tin-Information Retrieval Search
Sau đây là đnh ngh a v h th ng tìm ki m thông tin c a m t s tác gi :
Theo Salton (1989), việc tìm kiếm thông tin liên quan đến các tập tin lưu trữ và yêu cầu thông tin, xác định và truy xuất các tập tin phù hợp với yêu cầu đó Quá trình truy tìm thông tin phụ thuộc vào sự tương tác giữa các giá trị của các thuộc tính liên quan đến thông tin được lưu trữ và các yêu cầu thông tin.
Theo Kowalski (1997), hệ thống truy tìm thông tin là một cấu trúc có khả năng lưu trữ, truy xuất và duy trì thông tin Thông tin trong các trường hợp này có thể bao gồm văn bản, âm thanh, video và nhiều định dạng đa phương tiện khác.
Hệ thống tìm kiếm thông tin là công cụ hữu ích giúp người dùng nhanh chóng và dễ dàng truy cập thông tin Người dùng có thể nhập các câu hỏi và yêu cầu bằng ngôn ngữ tự nhiên, và hệ thống sẽ tìm kiếm trong kho tài liệu để đưa ra các kết quả liên quan Sau đó, các tài liệu này sẽ được sắp xếp theo mức độ liên quan, từ đó cung cấp thông tin chính xác và hữu ích cho người dùng.
T ng quan v c a m t h th ng tìm ki m thông tin
B ph n thu th p thông tin (Spyder/Robot/Web Crawler…)
Robot là m t ch ng trình t đ ng duy t qua các c u trúc siêu liên k t đ thu th p tài li u và t đ ng nh n v t t c các siêu liên k t có trong tài li u đ ti p t c duy t
Robot được biết đến dưới nhiều tên gọi khác nhau như Web crawler, Spider, Web wanderer hay Web worm Những tên gọi này đôi khi gây nhầm lẫn, đặc biệt là "Spider" và "Wanderer" khiến người ta nghĩ rằng robot di chuyển tự do, trong khi "Worm" lại liên tưởng đến virus Thực chất, robot chỉ là một chương trình duyệt và thu thập thông tin từ các website theo đúng giao thức web Những trình duyệt thông thường không được xem là robot do thiếu tính tự động, chúng chỉ duyệt web khi có sự tác động của con người.
B phân l p ch m c (Indexing)
Hệ thống lọc và phân tích dữ liệu, còn gọi là hệ thống phân tích và xử lý dữ liệu, thực hiện việc phân tích và trích xuất những thông tin cần thiết, như từ đơn, từ ghép, và các cụm từ quan trọng, từ dữ liệu mà robot thu thập Dữ liệu này được tổ chức thành cơ sở dữ liệu riêng, giúp tìm kiếm một cách nhanh chóng và hiệu quả Hệ thống này cũng bao gồm danh sách các từ khóa, rõ ràng chỉ ra từ khóa nào xuất hiện trên trang nào và tần suất xuất hiện của chúng.
B ph n giao ti p, so kh p và s p x p các tài li u tr v
Công cụ tìm kiếm tương tác với người dùng qua giao diện web, thực hiện nhiệm vụ tiếp nhận và phân tích các câu truy vấn Sau đó, chúng so sánh và tìm kiếm tài liệu liên quan, nhằm cung cấp những thông tin phù hợp nhất với yêu cầu của người dùng.
Các tài liệu được trích xuất từ câu truy vấn và các từ khóa của văn bản sẽ được so sánh với nhau để tìm ra những tài liệu liên quan đến câu truy vấn Mỗi tài liệu sẽ có một độ tương đồng nhất định với câu hỏi Những tài liệu này sẽ được sắp xếp theo độ tương đồng giảm dần và trả về cho người dùng.
Công việc của SEO là tìm kiếm các trang web mà các từ trong câu truy vấn xuất hiện nhiều nhất, ngoại trừ các từ dừng (stopword) như "a", "an", "the", Một từ càng xuất hiện nhiều trên một trang thì trang đó càng có giá trị hơn đối với người dùng.
Mạng trang chứa tất cả các từ trong câu truy vấn là một trang không chứa mật hoặc một số từ Ngày nay, hầu hết các công cụ tìm kiếm đều hỗ trợ chức năng tìm kiếm nâng cao, tìm từ đồng nghĩa, từ ghép, cụm từ, danh từ riêng, hay giới hạn phạm vi tìm kiếm nhằm cải thiện độ chính xác và hiệu quả của kết quả tìm kiếm, bao gồm tiêu đề, mô tả và nội dung giới thiệu về trang web.
Ngoài việc tìm kiếm chính xác theo từ khóa, các công cụ tìm kiếm còn có khả năng "hiểu" ý nghĩa thực sự của câu hỏi thông qua những câu hỏi do người dùng cung cấp Điều này được thể hiện qua việc nhận diện và tìm kiếm những hình thức biến đổi khác nhau của mặt từ.
Ví d : search engine s tìm nh ng t nh speaker, speaking, spoke khi ng i dùng nh p vào t speak.
Nguyên lý ho t đ ng
Công cụ tìm kiếm sử dụng robot để thu thập thông tin trên mạng thông qua các siêu liên kết Khi robot phát hiện một trang web mới, nó sẽ gửi dữ liệu về trang đó đến máy chủ chính để lưu trữ và phục vụ cho nhu cầu tìm kiếm thông tin.
Do thông tin trên mạng luôn thay đổi, robot cần liên tục cập nhật các trang web Việc cập nhật này phụ thuộc vào từng hệ thống công cụ tìm kiếm Khi người dùng thực hiện truy vấn, công cụ tìm kiếm sẽ tiến hành phân tích và tìm kiếm trong cơ sở dữ liệu để trả về những tài liệu phù hợp.
Hình 2: Nguyên lý ho t đ ng c a search engine
CH NG 2: NH NG V N C A B THU
Tóm t t l c s c a WebCrawler
Chu k thu th p d li u c a m t web crawler
_ The crawler b t đ u t i n i dung c a các trang h t gi ng, t nh ng trang h t gi ng này The Crawler s phân tích và quét đ tìm ra các liên k t m i
_ Các liên k t ch a đ c ghé th m s đ c thêm vào m t hàng đ i và đ c t i v sau
_ Ti p theo đó, the Crawler s ch n m t trang m i đ t i v và quá trình đ c l p đi l p l i cho đ n khi g p m t đi u ki n ch n đ d ng quá trình.
Web Crawler đ u tiên
Web Crawler đầu tiên được một sinh viên tại MIT, Matthew Gray, tạo ra vào năm 1993 Vào tháng 6 năm đó, Gray đã gửi một tin nhắn đến www-talk mailing list, chia sẻ rằng ông đã viết một script bằng Perl để thu thập URL qua WWW, theo dõi máy chủ mà nó đã đi qua và tìm ra máy chủ mới Cuối cùng, ông đã hack mã để thu thập thông tin hữu ích hơn Dự án thu thập thông tin này được gọi là World Wide Web Wanderer (WWWW), và nó được sử dụng chủ yếu để nghiên cứu các đặc tính của web.
Vào tháng 6 năm 1994, Brian Pinkerton, một sinh viên tại Đại học Washington, thông báo rằng WebCrawler đã sẵn sàng để tìm kiếm thông tin từ nhiều máy chủ khác nhau Công cụ này thu thập dữ liệu từ hơn 4000 máy chủ toàn cầu, trở thành một trong những công cụ tìm kiếm thành công đầu tiên Sau đó, nhiều công cụ tìm kiếm khác như Lycos (1994), Excite (1995), Altavista (1995) và Hotbot (1996) đã ra đời dựa trên thông tin mà WebCrawler thu thập được.
Các ng d ng c a WebCrawler
General Web Search (T o ch m c bao g m các ch đ r ng)
Công cụ tìm kiếm trên web cần đảm bảo hai yếu tố quan trọng: bảo mật thông tin và chất lượng dữ liệu Để thực hiện điều này, chúng phải quét toàn bộ các trang web có thể sử dụng để phục vụ cho nhiều truy vấn khác nhau, đồng thời đảm bảo rằng các trang được thu thập có giá trị và đáng tin cậy.
Vertical Web Search (T o ch m c cho các ch đ c th )
Tìm kiếm theo chiều dọc (Vertical Crawler) là công cụ thu thập thông tin từ các trang web có mục tiêu cụ thể trong một lĩnh vực nhất định, một quốc gia hoặc một ngôn ngữ cụ thể Vertical Crawler tập trung vào việc thu thập dữ liệu từ một tập hợp các trang web, với khả năng xác định chính xác theo đa lý, ngôn ngữ và miền cụ thể Ví dụ, nó có thể được sử dụng để tìm kiếm thông tin trong các lĩnh vực như du lịch, y tế hoặc giáo dục.
• Shopbot: đ c thi t k đ t i thông tin t các danh m c mua s m tr c tuy n và cung c p giao di n so sánh giá theo cách t p trung
• News crawler: t p h p các m c tin t c t m t ngu n đã đ c xác đ nh tr c
• Spambot: vi c thu th p nh m vào các đa ch email đ đ c chèn vào trang web
Tìm kiếm theo chiều dọc (Vertical Search) bao gồm nhiều loại phân loại dữ liệu Trong trường hợp này, The Crawler được điều chỉnh để thu thập các định dạng thuộc loại được chỉ định, chẳng hạn như hình ảnh, âm thanh và video Ví dụ, Feed crawler sẽ kiểm tra việc cập nhật thông tin trong các tệp RSS/RDF trên trang web.
Trình thu thập dữ liệu (Crawler) là một công cụ quan trọng trong việc thu thập thông tin từ các trang web, giúp cung cấp các chiến lược thu thập dữ liệu hiệu quả và tránh tình trạng trùng lặp Crawler này nhận diện một mô hình đầu vào, thường là một bảng chứa các truy vấn chính hoặc tập hợp tài liệu mẫu Có hai chế độ hoạt động của Crawler: chế độ hàng loạt (Batch mode) cho phép thu thập các trang theo một lịch trình định kỳ, và chế độ theo yêu cầu (On Demand) cho phép thu thập các trang dựa trên các truy vấn cụ thể từ người dùng.
Thu th p đ c tính c a Web (Web Characterization)
Thu th p đ c tính web bao g m các n l c đ l y đ c các th ng kê thu c tính c a các trang web Việc xác định đ c tính web là một thách thức lớn, và cần xem xét các yếu tố như mục đích, nội dung và đối tượng người dùng Các yếu tố này ảnh hưởng đến cách mà một trang web được định hình và tiếp cận người dùng Đặc biệt, việc thu thập thông tin một cách có hệ thống sẽ giúp cải thiện kết quả truy vấn Cuối cùng, các URL cũng cần được lựa chọn một cách cẩn thận để tối ưu hóa khả năng hiển thị.
4 Ánh x trang web (Mirroring-Gi l i b n sao ho c tái t o trang web): _ Mirroring là hành đ ng gi l i m t ph n hay toàn b n i dung gi ng nh b n sao c a trang web M t Crawler dùng đ ánh x th ng khá đ n gi n Chính sách ánh x bao g m: th i gian làm m i (c p nh t l i b n sao) đi n hình là hàng ngày hay hàng tu n và th i gian trong ngày đ th c hi n Mirroring.
Web archival (L u tr n i dung)
Web archiving là một phương pháp lưu trữ các trang web mà không cần lo ngại về việc thay đổi nội dung Dự án lưu trữ trang web lớn nhất hiện nay là Internet Archive, có thể truy cập tại URL http://www.archive.org Dự án này tập trung vào việc bảo tồn trạng thái của các trang web trong thời gian dài, với bộ sưu tập các trang từ tháng 3/2006 lên tới 55 tỷ trang.
Web Site Anaylysis (Phân tích trang web)
_ Web crawler có th đ c dùng đ phân tích m t trang web và th m chí nó th thay đ i nó theo m t tiêu chu n đ nh d ng s n Ví d :
• Xác th c liên k t (Link Validation): Quét các trang web c a m t website đ xác đnh các liên k t h ng
• Xác th c mã (Code Validation): đ m b o r ng t t c các trang c a m t website đúng d ng (well-formed)
• Phân thích cây c a web (Web directories analysis): tìm nh ng trang không còn s n sàng (available) n a
_ M t công c phân tích website còn đ c dùng đ tìm ra các l h ng c a m t website bao g m vi c tìm ra nh ng phiên b n c ho c ch a đ c vá c a nh ng k ch b n thông d ng (popular script).
Ki n trúc c a Web Crawler
_ Trình thu th p thông tin g m 3 module chính là : Downloader, Storege, và Scheduler
Lịch trình trong web crawler bao gồm hai phần chính: Lập lịch dài hạn (Long-term Scheduling) và lập lịch ngắn hạn (Short-term Scheduling) Lập lịch dài hạn xác định các trang cần truy cập tiếp theo, trong khi lập lịch ngắn hạn sắp xếp các trang dựa trên tình trạng hiện tại của máy chủ Quá trình này yêu cầu duy trì nhiều hàng đợi, mỗi hàng đợi dành cho một website cụ thể, cùng với danh sách các trang cần truy cập trong từng hàng đợi.
Lưu trữ là một phần quan trọng cho các trang web, cung cấp khả năng lưu trữ thông tin và siêu dữ liệu Việc lưu trữ có thể được chia thành ba phần chính: văn bản phong phú (rich text), siêu dữ liệu (metadata) và liên kết (link).
Nh ng th c m c liên quan đ n ho t đ ng c a WebCrawler
Trong môi tr ng m ng, robot l y thông tin t các site V y robot s
Bắt đầu với câu hỏi "Site nào?" thì câu trả lời phụ thuộc hoàn toàn vào robot Mỗi loại robot sẽ có những chiến lược khác nhau Thông thường, robot sẽ ưu tiên các site phổ biến hoặc những trang có nhiều liên kết dẫn đến chúng.
Ai s cung c p đ a ch c a các site này cho robot ?
• Robot nh n các URL ban đ u t user
• Robot phân tích các trang web đ l y các URL m i, đ n l t các URL này tr thành đ a ch đ u vào cho robot Quá trình này đ c l p l i liên t c.
Ch n d li u nào trong tài li u đ l p ch m c ?
Quy t đnh ch n d li u nào trong tài li u c ng hoàn toàn ph thu c vào robot, th ng thì nh ng t đ c li t kê nh sau đ c xem là quan tr ng :
• Trong tiêu đ (quan tr ng)
• Trong ph n miêu t trang web (description)
• Trong các th dành cho hình nh (ALT graphisc)
• Trong các th ch a t khóa
Robot lập chỉ mục trên tiêu đề và mô tả giúp thu thập toàn bộ tài liệu (full text) Một số khác là lập chỉ mục trên các thẻ META hoặc các thẻ, nhằm xác định từ khóa cho tài liệu của trang web Tuy nhiên, chức năng này bị lạm dụng quá nhiều, do đó các thẻ META không còn giá trị như ban đầu.
Các thu t toán thu thâp d li u
Tìm ki m theo chi u sâu
N u có, thêm vào đ u danh sách
Danh sách đ a ch các trang đ u tiên
L y trang đ u tiên trong danh sách
Trang này đ ã xét t i ch a? ánh d u đã t i và xác đ nh xem có liên k t nào trong trang đó không?
Tìm ki m theo ng u nhiên
N u có, thêm vào cu i danh sách
Danh sách đ a ch các trang đ u tiên
L y trang đ u tiên trong danh sách
Trang này đã xét t i ch a? ánh d u đã t i và xác đ nh xem có liên k t nào trong trang đó không?
N u có, thêm vào cu i danh sách
Danh sách đ a ch các trang đ u tiên
L y trang ng u nhiên trong danh sách
Trang này đ ã xét t i ánh d u đã t i và xác đ nh xem có liên k t nào trong trang đó không?
Nh ng v n đ c n l u ý v web crawler
Có th nói web crawler là con dao 2 l i, s d ng đúng s gi i quy t đ c nhi u v n đ , s d ng sai s đ l i nh ng h u qu khó đoán Sau đây là tóm t t cho nh ng v n đ c n l u ý c a web crawler:
_ Tránh lãng phí tài nguyên
• Ch t i v nh ng tài li u c n thi t
• N u h th ng ch quan tâm đ n các file text (.html, htm, xml,
…), web crawler nên b qua các liên k t d n đ n nh ng file th c thi (.exe, …), file nh (.gif, bmp, …)
• B qua các tr ng d li u h th ng không dùng đ n
• ng l y v các trang gi ng nhau nhi u h n m t l n
_ Tránh c p nh t l i các site c quá th ng xuyên b ng cách :
• Ghi nh nh ng đa ch web crawler đã duy t qua
• D a vào tr ng LastModified, tr ng head N u các tr ng này khác v i d li u ta đã có thì đó là nh ng thông tin c n ghi nh n
• Không nên duy t h t m t site, ch c n duy t đ n m t đ sâu (deep link) c n thi t
• Duy trì m t kho ng th i gian đ i gi a các l n truy xu t liên ti p
• K t n i v i server vào nh ng th i đi m thích h p Tham kh o ý ki n c a admin đ bi t thông tin này
• Ki m tra web crawler trên máy c c b , s a l i tr c khi ch y trên server th c s
_ Tuân theo các lu t lo i tr robot: Sau đây là b n quy t c tìm ki m c a b n c máy tìm ki m thông tin l n:
• Ask search: ĩ http://about.ask.com/en/docs/about/webmasters.shtml
• Google (Googlebot) ĩ http://www.google.com/webmasters/bot.html
• MSN Search ĩ http://www.msnsearch.com/msnbot.htm
• Yahoo! Search (Slurp!) ĩ http://help.yahoo.com/help/us/ysearch/slurp/
CH NG 3: NH NG V N C A B PH N
Khái quát v h th ng l p ch m c
M t cách đ t ng t c đ tìm ki m thông tin là t o ch m c cho tài các tài li u Tuy nhiên, việc l p ch m c có nh c đi m l n, đó là khi thêm m t tài li u m i ph i c p nh t l i t p tin ch m c Đ i v i h th ng tìm ki m thông tin, ch c n c p nh t l i ch m c vào m t kho ng th i gian đnh k Do đó, ch m c là m t công c r t có giá tr.
_ L p ch m c bao g m các công vi c sau:
• Xác đnh các t có kh n ng đ i di n cho n i dung c a tài li u (bao g m c vi c tách t , lo i b stop-word, x l ý h u t …)
• ánh tr ng s cho các t này, tr ng s ph n ánh t m quan tr ng c a t trong m t tài li u.
V n đ tách t t đ ng đ l p ch m c
Tách t trong ti ng Anh
_ Do đ c đi m ng pháp c a ti ng anh, tách t đ n gi n ch d a vào kho ng tr ng đ phân bi t t
Tách t trong ti ng vi t
M t s đ c đi m chính v ti ng Vi t
• V m t ng âm, ti ng là âm ti t Âm ti t bao g m nh ng đ n v b c th p h n g i là âm v M i âm v đ c ghi b ng m t ký t g i là ch
• V m t ng ngh a, ti ng là đ n v nh nh t có ngh a, nh ng c ng có m t s ti ng không có ngh a
Trong ngữ pháp tiếng Việt, ti ng đóng vai trò quan trọng trong cấu trúc câu Có hai trường hợp sử dụng ti ng: Thứ nhất, khi một ti ng xuất hiện, nó được gọi là ti ng đơn, ví dụ như: tôi, bạn, cha, mẹ Thứ hai, khi có hai ti ng trở lên, chúng được gọi là ti ng phức, ví dụ như: giao lưu, văn hóa.
Trong tiếng Việt, từ "t" mang nhiều ý nghĩa khác nhau và thể hiện sự hoàn chỉnh của một nội dung Từ này không chỉ là một đích đến mà còn nhấn mạnh tính chất của câu.
• Ng i ta dùng "t " k t h p thành câu ch không ph i dùng
"ti ng" do đó quá trình l p ch m c b ng cách tách câu thành các
"t " cho k t qua t t h n là tách câu b ng “ti ng”.
Tách t t đ ng ti ng vi t
Hi n nay có r t nhi u ph ng pháp đ c s d ng đ tách t
Tiếng Việt có nhiều phương pháp học khác nhau, nhưng hiện tại chưa có phương pháp nào đảm bảo chính xác 100% Việc lựa chọn phương pháp học phù hợp vẫn đang là vấn đề gây tranh cãi trong cộng đồng.
Phương pháp tách từ động tiếng Việt dựa trên Fast Transformation-based Learning (fnTBL) có ý nghĩa quan trọng trong việc giải quyết bài toán phân tách từ Cụ thể, phương pháp này áp dụng các phép biến đổi để đạt được kết quả tách từ chính xác và hiệu quả Thuật toán sẽ dừng lại khi không còn phép biến đổi nào được chọn Hệ thống fnTBL bao gồm hai tập tin chính.
- T p tin d li u h c (Training): T p tin d li u h c đ c làm th công, đòi h i đ chính xác M i m u (template) đ c đ t trên m t dòng riêng bi t Ví d : t p d li u h c cho vi c xác đnh t lo i c a m t v n b n có th đ c đnh d ng nh sau:
Công ty danhtu ISA danhturieng b dongtu ki m tra dongtu Trong ví d này m i m u g m hai ph n: ph n đ u tiên là t , ph n th hai là t lo i t ng ng
- T p tin ch a các m u lu t (rule template): M i lu t đ c đ t trên m t dòng, h th ng fnTBL s d a vào các m u lu t đ áp d ng vào t p d li u h c
Khi xác định loại của một từ, nếu hai từ trước đó là động từ và trạng từ, thì chuyển loại hiện hành thành danh từ.
Phương pháp này tốn khá nhiều chi phí và khó sử dụng, do đó không thể áp dụng một cách chi tiết vào tác phẩm trong dự án này Nếu muốn tìm hiểu rõ hơn, xin tham khảo luận văn cao học của Nguyễn Thị Thu Hằng - Trường Đại học Công Nghệ - 2007 (Phương pháp phân cắt tài liệu Web và áp dụng vào máy tìm kiếm, Chương 2 mục 2.6.3 trang 39).
Ph ng pháp Longest Matching:
Vi c xác đ nh t trong ti ng Vi t là r t khó và t n nhi u chi phí
Cách đơn giản nhất để sử dụng từ điển là tách từ tiếng Việt từ trái sang phải và chọn những từ có nhiều âm tiết, trong đó có một từ trong từ điển Tài liệu cần được tách thành các từ, loại bỏ các từ láy, từ nối, từ đệm và các từ không quan trọng Một câu có thể chứa nhiều từ ghép, tuy nhiên trong một câu có thể có nhiều cách phân tích từ khác nhau.
Ví d : xét câu "T c đ truy n thông tin s t ng cao" có th phân tích t theo các cách sau:
T c đ / truy n/ thông tin / s / t ng cao
T c đ / truy n thông / tin / s / t ng cao
Hiện nay, có nhiều giải pháp hiệu quả cho vấn đề này với kết quả thu được rất cao Tuy nhiên, thời gian và chi phí tính toán, xử lý lại không hợp lý cho việc lập chỉ mục cho hệ thống tìm kiếm thông tin do khối lượng tài liệu phải xử lý rất lớn.
Cách gi i quy t: l p ch m c cho các t có th có trong m t tài li u Ví d câu trên ta nên l p xem xét các t : t c đ , truy n , truy n thông ,thông tin, tin , s , t ng cao
Trong tài liệu, thuật ngữ "truyền thông" không xuất hiện thường xuyên, chỉ có sự kết hợp ngẫu nhiên giữa "truyền" và "thông tin" Do đó, xác suất xuất hiện của thuật ngữ này là rất thấp Khi tính toán trọng số cho hai hay nhiều từ, phương pháp xác định một thuật ngữ được ghép lại thông qua nhiều từ dựa trên việc xem xét độ gắn kết (DGK) giữa chúng.
• Trong đó: ĩ DGK(n ij ): đ g n k t t ghộp c a ti ng i và j ĩ KTTCM: kớch th c t p ch m c ĩ TSTij : t n s xu t hi n t ĩ ni , nj : t n s xu t hi n ti ng i, j
Hai ti ng có kh n ng t o thành m t t cao khi chúng th ng xu t hi n chung v i nhau, ngh a là cohension c a chúng cao
Phương pháp này không hoàn toàn tách biệt chính xác, nhưng có thể áp dụng trong hệ thống tìm kiếm thông tin Trong quá trình lập trình, việc xác định đúng các từ có tần suất cao là rất quan trọng Nếu tách từ không chính xác, từ sai chỉ có thể được lập trình khi nó có tần suất cao, vì việc lập trình từ hoàn toàn sai sẽ làm tăng chi phí lưu trữ mà không ảnh hưởng đến tính chính xác của kết quả tìm kiếm, vì từ này vẫn có tần suất lớn.
Còn trong tr ng h p m t t ghép đ c tách thành nhi u t đ n ví d t "thông tin" khi đ c l p ch m c s luôn có 3 t "thông", "tin",
Việc lập trình cho từ "thông tin" gặp khó khăn do tính chính xác bị ảnh hưởng bởi sự xuất hiện của các từ "thông" và "tin" Để giải quyết vấn đề này, nếu "thông tin" được lập trình chính xác, số lần xuất hiện của "thông" và "tin" sẽ được tính toán lại dựa trên các trường hợp đã xuất hiện trong "thông tin" Nếu từ "tin" chỉ xuất hiện trong "thông tin", thì số lần xuất hiện của "tin" và "thông tin" sẽ bằng nhau, dẫn đến số lần xuất hiện riêng của "tin" sẽ bằng 0 khi lập trình cho "thông tin", do đó không thể lập trình chính xác cho từ này.
V n đ xác đ nh t ch m c
V n đ l p ch m c t đ ng trong ti ng anh
Việc xác định từ khóa chính trong một đoạn văn là rất quan trọng để tối ưu hóa tài liệu Trong các ngôn ngữ Âu, từ khóa có thể được coi là đặc trưng vì chúng không phải là ký tự phân biệt Điều cần chú ý là xác định những từ này, vì chúng đại diện cho toàn bộ nội dung của tài liệu Các từ stop-word thường xuất hiện nhiều, chiếm khoảng 40-50% trong tổng số từ của một văn bản, nhưng chúng có khả năng phân biệt kém và không thể sử dụng để xác định nội dung của tài liệu.
250 t S l ng t này không nhi u l m nên gi i pháp đ n gi n nh t là l u các t này vào trong m t t đi n, và sau đó ch c n th c hi n so sánh t c n phân tích v i t đi n đ lo i b
Bước theo là nhận ra các chấm có thể tách Giảm bớt dung lượng lưu trữ, các chấm cần được biến đổi về nguyên gốc (step of stemming đối với tiếng Anh) Phải loại bỏ các tiền tố, hậu tố, và các biến thể số nhiều, quá khứ… Giải pháp là sử dụng một danh sách các hậu tố Trong khi loại bỏ hậu tố thì những hậu tố dài được ưu tiên loại bỏ trước, rồi sau đó mới loại bỏ những hậu tố ngắn hơn Sau đây là một số ví dụ khi loại bỏ trong tiếng Anh:
• Ch rõ chi u dài t i thi u c a m t t g c sau khi lo i b h u t
Ví d : vi c lo i b h u t “ability” ra kh i “computability” hay lo i b “ing” ra kh i “singing” là h p lý Tuy nhiên, nh ng h u t đó không c n ph i lo i b trong các t “ability” và “sing”
• N u nhi u h u t đ c k t h p vào m t g c thì ta s áp d ng đ quy cho quá trình lo i b h u t vài l n ho c l p t đi n h u t r i lo i b nh ng h u t dài h n tr c r i đ n các h u t ng n sau Vớ d : “effectiveness” ồ “effective” ồ “effect”
Trong tiếng Anh, từ gốc có thể bị biến đổi sau khi đã loại bỏ phụ âm Do đó, chúng ta cần có những luật nhất định để xác định cách thức gốc Chúng thường loại bỏ một trong hai ký tự trùng nhau của những từ có sự xuất hiện b, d, g, l, m, n, p, r, s, t cuối cùng của các từ gốc sau khi đó loại bỏ phụ âm Ví dụ như “beginning” trở thành “beginn” khi áp dụng quy tắc này.
Mỗi ngữ điệu đều phải chú ý đến những quy tắc cụ thể trong cách phát âm Ví dụ, một quy tắc cho âm tiết "allic" yêu cầu rằng chiều dài của nguyên âm phải được giữ vững, không được có âm tiết nào theo sau "met" hoặc "r yst" Tương tự, quy tắc cũng quy định rằng âm tiết "yl" không được xuất hiện sau "n" hoặc "r".
Tóm l i, gi i quy t v n đ h u t không quá khó n u chúng ta có s n m t danh sách ch a các h u t , m t danh sách ch a các lu t thêm các h u t và ph c h i t g c sau khi thêm h u t
V n đ l p ch m c t đ ng trong ti ng vi t
_ L p ch m c cho ti ng vi t c ng t ng t nh cho ti ng anh Tuy nhiên có vài đi m khác bi t sau:
Giai đoạn tách từ trong tiếng Anh thường đơn giản hơn so với tiếng Việt, do tiếng Anh là ngôn ngữ phân lập, trong khi tiếng Việt lại là ngôn ngữ tổng hợp và có thể có nhiều từ ghép Điều này đã được phân tích chi tiết trong mục Tách từ.
• i v i ti ng Vi t không ph i qua giai đo n lo i b h u t
Để cải thiện chất lượng nội dung tiếng Việt, cần xác định các từ ngữ không cần thiết trong tài liệu Đầu tiên, loại bỏ các từ có tần suất xuất hiện cao, tương tự như danh sách stop list trong tiếng Anh, bao gồm các từ như "và", "với", "những", "gì", "sao", "nào" Tiếp theo, cần loại bỏ những từ có tần suất thấp, vì chúng có thể làm giảm độ rõ ràng của nội dung Cuối cùng, các từ thu được cần được sắp xếp một cách hợp lý để đảm bảo nội dung dễ hiểu và hấp dẫn.
V n đ tính tr ng s cho t ch m c
Cách tính trong s cho vector ch m c
_ Ngh ch đ o tr ng s t n s tài li u (The Inverse Document Frequency Weight)
• wk : là tr ng l ng c a m c t k
• nDock : t ng s tài li u mà m c t k xu t hi n
• nki : s l n xu t hi n m c t k trong tài li u i
• nk : s l n xu t hi n m c t k trong toàn t p tài li u
• idfk : giá tr ngh ch đ o t n s tài li u (Inverse Document Frequency)
_ Nh v y, tr ng s c a m c t k s t ng lên khi t n s xu t hi n c a m c t k trong các tài li u i t ng lên nh ng gi m xu ng khi t n s xu t hi n c a m c t k trong t p tài li u (nDock) t ng lên
_ Hàm này gán đ quan tr ng cao cho nh ng m c t ch xu t hi n trong m t s ít tài li u c a m t t p h p tài li u (đ cao đ phân bi t).
nhi u tín hi u (Signal Noise)
Trọng số của từ khóa trong tài liệu có thể được phân loại thành hai loại: tập trung và phân tán Ví dụ, nếu từ "hardware" xuất hiện 1000 lần trong 200 tài liệu (tập trung), thì trọng số của nó sẽ cao hơn so với từ "computer" xuất hiện 1000 lần trong 800 tài liệu Điều này cho thấy sự khác biệt trong mức độ tập trung của các từ khóa trong các tài liệu khác nhau.
( ki ).log ( 2 ki ) 1, k k k n n noise i nDoc n n
Hàm s ngh ch đ o c a đ nhi u đ c g i là đ signal có th đ c dùng đ tính tr ng l ng c a m c t k : log ( 2 ) k k k k w = signal = n − noise
Giá tr phân bi t t
Phân biệt từ khóa là giá trị phân biệt mà nó tạo ra giữa các tài liệu Nếu một từ khóa có trong nhiều tài liệu và làm cho độ độc đáo của các tài liệu đó thấp, thì nó có phân biệt kém (nghĩa là từ này thường xuyên xuất hiện trong các tài liệu) Do đó, các từ khóa có độ phân biệt cao nên được chọn lựa kỹ lưỡng Thực chất việc sử dụng độ phân biệt này càng góp phần nâng cao kết quả tìm kiếm và tạo lòng tin hiệu quả hơn.
G i SIMILAR(Di, Dj) là đ t ng quan gi a c p tài li u Di và
Dj Khi đó, đ t ng quan trung bình c a t p tài li u này là:
Giá trị trung bình của tập tài liệu sẽ giảm khi có nhiều từ khóa xuất hiện thường xuyên trong đó Ngược lại, nếu từ khóa chỉ tập trung trong một số tài liệu, giá trị trung bình sẽ tăng lên khi có sự xuất hiện của từ khóa.
Giá tr phân bi t DifValuek c a t k đ c tính nh sau: k k
Tr ng s c a t k trong tài li u i đ c tính b ng cách k t h p gi a T ng s c a k trong tài li u I FREQik và DifValuek: k k * k
T p tin ngh ch đ o tài li u
T p tin l u tr c ti p(direct file) là t p tin mà chính các m c thông tin đã cung c p th t chính c a t p tin
Ng c l i t p tin ngh ch đ o (inverted file) đ c x p theo ch đ , m i ch đ l i bao g m m t t p các m c thông tin
Ví dụ tài liệu có tập hợp các tài liệu, mỗi tài liệu chứa danh sách các mục Nếu một mục xuất hiện trong một tài liệu, ghi 1 Ngược lại, ghi 0 Khi đó, tập tin trước tiếp và tập tin nghịch đảo sẽ được ghi nhận như sau:
Tài li u 1 Tài li u 2 Tài li u 3
T i sao ph i s d ng t p tin ngh ch đ o?
Trong một thế giới đầy thông tin, việc tìm kiếm dữ liệu có ý nghĩa rất quan trọng, giúp người dùng truy cập nhanh chóng vào nội dung cần thiết trên các trang web Ví dụ, khi người dùng nhập câu truy vấn, hệ thống sẽ nhanh chóng cung cấp kết quả chính xác và phù hợp với yêu cầu của họ.
Hai tài liệu được tách thành hai phần "t1" và "t2" Dựa vào tập tin nghịch đảo, chúng ta có thể xác định chính xác các tài liệu chứa hai phần này để cung cấp cho người tìm kiếm Tuy nhiên, khó khăn chính của tập tin nghịch đảo là khi thêm một tài liệu mới, tất cả các từ khóa liên quan đến tài liệu này đều phải được cập nhật lại.
Chi phí để xây dựng một tập tin nghịch đảo là rất lớn, nhưng nó có thể chứa hàng trăm ngàn tài liệu Tuy nhiên, trong hệ thống tìm kiếm thông tin, người dùng chỉ cần cập nhật lại tập tin tại thời điểm đánh k Do đó, tập tin nghịch đảo vẫn được sử dụng rất phổ biến.
CH NG 4: NH NG V N C A B PH N GIAO TI P, SO KH P VÀ S P X P K T QU
V n đ giao ti p v i ng i dùng
Công cụ tìm kiếm cần hiểu rõ câu hỏi và yêu cầu tìm kiếm của người dùng, do đó giao diện phải đơn giản, dễ sử dụng và rõ ràng Câu hỏi mà người dùng nhập vào sẽ được xử lý tách biệt Phương pháp tách biệt câu hỏi áp dụng theo cách thu thập dữ liệu phù hợp Sau đó, hệ thống tìm kiếm trong tập tin sẽ xác định các tài liệu liên quan đến câu hỏi của người dùng.
V n đ so kh p câu truy v n và tài li u
Thu t toán không gian vector
Tính toán không gian vector giúp xác định độ tương quan giữa câu hỏi và tài liệu thông qua việc biểu diễn mỗi tài liệu và câu truy vấn dưới dạng vector Mô hình này dựa trên ý nghĩa của tài liệu, phụ thuộc vào các từ đặc trưng bên trong nó Sau đó, vector tài liệu và vector câu hỏi được tính toán để xác định độ tương quan giữa chúng; độ tương quan càng lớn, tài liệu đó càng liên quan đến câu truy vấn.
Ví dụ về một tài liệu có hai thành phần "t1" và "t2" cho thấy cách vector được xây dựng từ hai yếu tố: thành phần đầu tiên biểu diễn số xuất hiện của "t1" và thành phần thứ hai biểu diễn số xuất hiện của "t2".
“t2” Cách đ n gi n là đánh 1 vào thành ph n t ng ng n u t đó xu t hi n, và đánh không n u t đó không xu t hi n Vector nh sau :
Trong bài viết này, chúng ta sẽ xem xét cách biểu diễn một tập hợp tài liệu bằng vector, nhằm phân tích sự xuất hiện của các từ khóa Thay vì chỉ so sánh các từ trong tài liệu với từ trong câu truy vấn, chúng ta cần chú trọng đến tần suất xuất hiện của các từ khóa Ý tưởng chính là một từ xuất hiện trong một tập tài liệu sẽ có tần suất cao hơn so với việc phân bố của nó trong nhiều tập tài liệu khác nhau Tần suất này được tính toán dựa trên tần suất của tài liệu liên quan đến các từ khóa cụ thể.
• N : s t phân bi t trong t p tài li u
• Tfij : s l n xu t hi n c a t tj trong t p tài li u Di
• Dfj: s tài li u có ch a t tj
• Idfj =log10(d/dfj) trong đó d là t ng s tài li u
Vector được xây dựng cho mỗi tài liệu gồm có các thành phần, mỗi thành phần là giá trị trọng số đã được tính toán cho mỗi từ trong tập tài liệu Các từ trong tập tài liệu được gán trọng số tương ứng với tần suất xuất hiện của chúng trong tập tài liệu và sự xuất hiện của mỗi từ trong một tài liệu riêng biệt Trọng số của mỗi từ thường xuyên xuất hiện trong một tài liệu và giảm dần nếu xuất hiện trong nhiều tài liệu Tính trọng số của từ trong tài liệu được dựa vào công thức: \( tf \times idf \).
Dij là trọng số của tài liệu Di trong hệ thống tìm kiếm dựa trên thuật toán vector Mỗi tài liệu được biểu diễn dưới dạng một vector với các thành phần: (Di(di1, di2, di3, din)) Tổng thể, câu truy vấn được xây dựng dựa trên các trọng số này để tối ưu hóa kết quả tìm kiếm.
Q c ng là m t vector có d ng Q(w1, w2, w3, , wn) t ng quan SIM gi a câu truy v n Q và tài li u Di đ c tính nh sau :
Tìm ki m Boolean
Thu t toán tìm ki m Boolean khá đ n gi n Câu truy v n đ a ph i ph i d ng bi u th c Boolean Ngh a là ph i tho :
Do các t ho c xu t hi n ho c không xu t hi n, nên tr ng s wij thu c {0, 1}
Trong truy vấn động Boolean, khi sử dụng phép toán "and" giữa hai từ khóa t1 và t2, chúng ta có thể xác định các tài liệu liên quan Cụ thể, tài liệu liên quan đến t1 là {d1, d3, d5} và tài liệu liên quan đến t2 là {d3, d5, d7} Kết quả cuối cùng từ phép "and" sẽ là {d3, d5}, tức là các tài liệu đáp ứng yêu cầu của người dùng Tuy nhiên, phương pháp này cũng có một số nhược điểm cần lưu ý.
• Các tài li u tr v không đ c s p x p
• Câu truy v n đòi h i ph i đúng đnh d ng c a bi u th c Boolean gây khó kh n cho ng i dùng
• K t qu tr v có th là quà ít ho c quá nhi u tài li u.
Thu t toán Boolean m r ng
Mô hình boolean không thể xử lý các truy vấn phức tạp vì các tài liệu học thuật không đáp ứng yêu cầu Boolean Tất cả các tài liệu thỏa mãn đều được trả về, nhưng không có sức mạnh nào được tính toán cho sự liên quan của chúng đối với câu truy vấn.
Thuật toán Boolean mở rộng ra đánh giá mức độ xếp hạng kết quả truy vấn dựa trên ý tưởng cốt lõi là đánh trọng số cho mỗi từ trong câu hỏi và trong tài liệu Ví dụ, trong câu truy vấn (t1 or t2) và một tài liệu D có chứa t1 với trọng số w1 và t2 với trọng số w2 Nếu w1 và w2 đều bằng 1, thì tài liệu nào có chứa cả hai từ này sẽ có thể được xếp hạng cao nhất Ý tưởng đơn giản là tính khoảng cách Euclid từ (w1, w2) tới gốc.
SC W D = + • SC cao nh t khi w 1 và w 2 đ u b ng 1 Khi đó:
SC W D = + • đ a SC vào kho ng [0,1], Sc đ c tính nh sau:
Công thức này áp dụng cho toán tử "or", trong khi đối với toán tử "and", thay vì tính khoảng cách từ điểm gốc, chúng ta tính khoảng cách đến điểm (1, 1) Tài liệu nào càng gần điểm (1, 1) thì càng đáp ứng yêu cầu của toán tử "and".
_ M r ng thêm vào tr ng s c a câu truy v n
• N u câu truy v n có trong s là q1 và q2 thì đ t ng quan s đ c tính nh sau:
• tính kho ng cách Eclide trong không gian đa chi u, tham s p đ c s d ng tham s p ch s bi n đ i t m quan tr ng c a tr ng s trong vi c đánh giá đ thích h p
• t ng quan SC t ng quát nh sau:
• N u p ồ ∞ : chuy n v h th ng boolean thụng th ng (khụng có tr ng s )
• N u p = 1: chuy n v h th ng không gian vector
Các thuật toán so khớp không yêu cầu người dùng nhận biết các toán tử phức tạp Trong số đó, có thể được gán tự động và tài liệu được sắp xếp bằng cách chèn toán tử OR vào giữa các từ Bất kỳ tài liệu nào có chứa ít nhất một từ trong câu truy vấn sẽ được sắp xếp thật với một số điểm lớn hơn 0.
Thu t toán xác su t
Thuật toán xác suất được sử dụng để tính độ tương quan giữa câu truy vấn và tài liệu dựa vào xác suất mà tài liệu đó liên quan đến câu truy vấn Các lý thuyết về xác suất được áp dụng để tính toán độ liên quan giữa câu hỏi và tài liệu Các từ trong câu truy vấn được xem là đầu mối xác định tài liệu liên quan Ý tưởng chính là tính xác suất của mỗi từ trong câu truy vấn và sau đó sử dụng chúng để tính xác suất mà tài liệu liên quan đến câu truy vấn.
Thu t toán PageRank c a Google
PageRank là m t thu t toán đ c s d ng trong công c tìm ki m Google, đ c phát tri n t i i h c Stanford b i Larry Page và Sergey Brin trong nghiên c u c a h “The Anatomy of a Large-Scale Hypertextual Web Search Engine”
Hình 3: Minh h a liên k t gi a các site s d ng trong PageRank
Thuật toán PageRank, được phát triển bởi Brin và Page, đánh giá tầm quan trọng của một trang web dựa trên số lượng và chất lượng các liên kết đến trang đó Tương tự như trong giới học thuật, nơi một bài báo được xem xét qua số lượng trích dẫn từ các bài báo khác, PageRank xác định giá trị của một trang web thông qua các liên kết từ các trang khác Điều này giúp cải thiện khả năng hiển thị của trang web trên các công cụ tìm kiếm.
Web đ c quy t đnh b i s l ng các hyperlink tr đ n nó t các trang Web khác”
PageRank là một chỉ số đo lường độ tin cậy của một trang web dựa trên số lượng và chất lượng các liên kết từ các trang web khác trên toàn cầu Mỗi liên kết được coi như một phiếu bầu, và giá trị của các phiếu bầu này phụ thuộc vào độ uy tín và tầm quan trọng của trang web mà chúng liên kết đến.
M t trang đ c liên k t đ n b i các trang có PageRank cao s nh n đ c PageRank cao N u 1 trang web không có liên k t nào đ n thì s không có phi u b u nào
Google đánh giá các trang web trên thang điểm từ 0-10 thông qua chỉ số PageRank Chỉ số này cho biết mức độ quan trọng của trang web theo cách nhìn nhận của Google Các website có PageRank cao thường có chất lượng tốt và được coi là quan trọng hơn Do đó, trong quá trình tìm kiếm, Google sẽ ưu tiên hiển thị các trang có PageRank cao hơn.
Khi tìm kiếm, việc không chỉ dựa vào PageRank cao để xếp hạng trang đầu tiên là điều tự nhiên, mà còn phụ thuộc vào nội dung bạn muốn tìm kiếm và nhiều yếu tố khác Google kết hợp PageRank với nhiều heuristics khác để đưa ra kết quả tìm kiếm phù hợp nhất.
Trích t Google, PageRank đ c đnh ngh a nh sau:
Trang A có các trang liên kết T1, T2, …, Tn, với tham số d có giá trị từ 0 đến 1, thường được đặt là d = 0.85 C(A) là số lượng liên kết mà trang A trỏ đến PageRank của trang A được tính theo công thức cụ thể, phản ánh mức độ quan trọng và sự ảnh hưởng của trang trong mạng lưới web.
Chú ý r ng t ng t t c PageRank c a t t c các trang web là m t s c đnh
PageRank PR(A) có th đ c tính toán b ng cách s d ng 1 thu t toán l p đ n gi n
PR(Tn) - PageRank c a trang Tn C(Tn) - S các link đi ra c a trang Tn
(1-d) - Th hi n r ng t ng PageRank t t c các trang web là m t s c đ nh Ngoài ra còn có ý ngh a là n u 1 trang web mà không có trang nào tr t i nó thì nó s có PR < 0.15
Ta th y PageRank c a m t trang web đ c tính b ng t ng c a PageRank c a t t c các trang tr t i nó (incoming links), chia cho s các link đi ra c a trang đó ( outgoing links) Ý ngh a thu t toán
Trên quan đi m c a Search Engine, đ nh ngh a thu t toán PageRank cho ta th y có 2 y u t nh h ng đ n v trí c a trang web c a b n trên Google ó là:
Số lượng link đi đến một trang web (incoming links) thường tỷ lệ thuận với độ tin cậy và thứ hạng của trang đó trong các công cụ tìm kiếm Một điểm quan trọng cần lưu ý là nếu một trang không có liên kết trỏ đến, nó có thể ảnh hưởng tiêu cực đến PageRank của trang đó, khiến giá trị của nó trở nên bằng 0.
Số lượng liên kết đi ra từ trang web là yếu tố quan trọng ảnh hưởng đến PageRank Càng ít liên kết đi ra, trang web càng giữ được giá trị PageRank cao hơn Nếu có hai trang web cùng có PageRank, trang có ít liên kết đi ra sẽ được ưu tiên hơn trong việc xếp hạng.
10 link đi ra thì PageRank đ c tính t trang có 5 link đi ra s g p đôi trang có 10 link đi ra
Có th th y thu t toán PageRank không liên quan gì đ n các câu truy v n tìm ki m Nó ch đ n thu n là m t ph n c a thu t toán x p h ng c a Google
Có l cách t t nh t đ xem xét PageRank là coi nó nh là 1 y u t b sung, đ c x lý trên các k t qu tìm ki m c a Google sau khi t t c các tính toán khác đã hoàn t t
Thuật toán tìm kiếm của Google hoạt động bằng cách truy cập vào các trang đã được đánh chỉ mục, sau đó tính toán PageRank cho các trang trong kết quả tìm kiếm Các trang có PageRank cao hơn sẽ được xếp hạng cao hơn trong danh sách kết quả cuối cùng.
PageRank được tính toán dựa trên sự phụ thuộc giữa các trang web Quy trình này khá phức tạp, vì PageRank của một trang phụ thuộc vào PageRank của các trang liên kết đến nó Tuy nhiên, chúng ta không thể biết PageRank của các trang đó cho đến khi tính toán PageRank của các trang liên kết, tạo thành một vòng lặp vô tận mà không thể xác định chính xác.
Chúng ta có thể tính toán PageRank của một trang mà không cần biết giá trị cuối cùng của nó Mặc dù điều này có vẻ không hợp lý, nhưng thực tế là trong mỗi lần chạy thuật toán, chúng ta sẽ dần dần tiếp cận giá trị cuối cùng Do đó, công việc cần làm là ghi nhận giá trị mới trong mỗi lần tính toán và lặp lại phép toán cho đến khi kết quả thay đổi trong một giá trị đã định cho phép.
Hãy xem xét m t ví d đ n gi n nh t: có 2 trang web, m i trang l i tr đ n trang kia
M i trang có 1 link đi ra ( outgoing links) C(A) = C(B) = 1
Ban đ u chúng ta ch a bi t đ c PageRank c a t ng trang, vì th ta s đ t b ng 1, sau đó th c hi n phép tính: d = 0.85
Theo ví d trên ta tính đ c:
Nh n th y k t qu không thay đ i so v i PageRank đã c l ng, cho th y PageRank d đoán ban đ u là chính xác
Chú ý: Ta tính đ c giá tr t t h n cho PR(A) sau phép tính th nh t, vì th ta s s d ng k t qu này trong phép tính th 2
Giá trị PageRank của một trang web có thể thay đổi sau mỗi lần tính toán Vậy liệu PageRank của một trang có thể đạt đến 1.0? Có khả năng nào để PageRank của một trang vượt quá 1.0 hay không? Chúng ta có thể kiểm tra kết quả bài toán từ phần phân tích Sau các bước lập trình, PageRank của trang A và
B đ u ti n t i n đ nh và PageRank trung bình b ng 1
Chúng ta s th l i v i 1 giá tr c l ng ban đ u l n h n cho PageRank c a m i trang Gi s c l ng PageRank c a m i trang ban đ u là 40
Quá trình tính toán qua m i vòng l p:
Th y r ng các giá tr này đ u gi m d n và s ti n t i 1.0
Không ph thu c vào giá tr c l ng ban đ u, khi thu t toán PageRank n đnh thì giá tr trung bình c a PageRank c a t t c các trang b ng 1.0
Mặc dù chúng ta không thể thay đổi trực tiếp PageRank của tất cả các trang web, nhưng có thể tác động đến PageRank riêng biệt của từng trang Ví dụ, nếu muốn thu hút lượt truy cập vào trang web thông qua trang chủ, cần đảm bảo rằng trang chủ có PageRank cao hơn so với các trang khác trong cùng một website Tất cả PageRank của các trang đều được tổng hợp và phân chia cho các liên kết ra ngoài Do đó, các trang có nhiều liên kết ngoài sẽ có PageRank thấp hơn so với các trang khác trong website, nhằm giảm thiểu việc "thất thoát" PageRank ra ngoài.
Để tăng PageRank của một trang web, bạn có thể tạo ra nhiều trang mới, vì PageRank được phân phối dựa trên số lượng trang Ví dụ, một trang web có 10 trang sẽ có PageRank tổng cộng là 10, và PageRank này sẽ được phân phối qua các liên kết nội bộ Tương tự, một trang web với 12 trang sẽ có PageRank bằng 12 Do đó, việc tăng số lượng trang và nội dung mới, như thêm trang mới, có thể giúp cải thiện PageRank của trang web thông qua các chiến lược liên kết nội bộ hiệu quả.
Thu t toán PageRank trên th c t r t đ n gi n Nh ng khi m t phép tính đ n gi n đ c th c hi n hàng nghìn ( ho c hàng t ) l n thì thu t toán tr lên r t ph c t p
PageRank ch là 1 ph n trong chi n l c s p x p th t k t qu tìm ki m c a Google Nh ng nó là m t tiêu chí không th thi u trong vi c s p x p th t d li u.
S p x p các tài li u tr v
Các tài liệu được xác định là liên quan đến câu truy vấn của người dùng sẽ được sắp xếp theo thứ tự giảm dần của độ tương quan Hệ thống sử dụng một trong những phương pháp nêu trên để xác định tài liệu nào có liên quan nhiều nhất.
CH NG 5: GI I THI U M T S SEARCH
ENGINE THÔNG D NG HI N NAY
Gi i thi u chung
Trong những ngày đầu của Internet, người sử dụng rất ít và lượng thông tin cũng không phong phú Vì vậy, việc tìm kiếm thông tin trên Internet không thật sự cần thiết như bây giờ.
Truy cập site directory là một trong những phương pháp đơn giản để tiếp cận nguồn thông tin trên mạng Những liên kết trong directory giúp người dùng dễ dàng tìm kiếm tài nguyên theo từng chủ đề Yahoo là một trong những dịch vụ directory đầu tiên được ra mắt vào tháng 3 năm 1994.
Vào năm 1994, Yahoo Directory nhanh chóng phát triển và nhóm phát triển Yahoo đã tạo ra một công cụ tìm kiếm cho thư mục này Tuy nhiên, công cụ tìm kiếm này không phải là một search engine thực thụ, vì nó chỉ cho phép tìm kiếm trong các trang đã được chỉ định trong Yahoo Directory, và không thể tìm kiếm các trang mới Khái niệm SEO thời điểm đó vẫn chưa được hình thành.
Ngày nay, các directory không còn được sử dụng rộng rãi như trong quá khứ, chủ yếu vì chúng cung cấp thông tin không đầy đủ so với khối lượng khổng lồ trên Internet Ví dụ, DMOZ, một trong những directory lớn nhất hiện nay, chỉ tập hợp thông tin từ khoảng 5 triệu website, trong khi Google có hơn 8 tỉ nguồn tài nguyên Sự chênh lệch này cho thấy sự thay đổi trong cách mà người dùng tìm kiếm thông tin trực tuyến.
D án crawl web đ c b t đ u trong n m 1994 và đó là d ng đ u tiên c a search engine Lycos và AltaVista search engine xu t hi n n m
1995 và nhi u n m sau Alta Vista tr thành ng i d n đ u trong th tr ng này
Vào năm 1997, Sergey Brin và Larry Page đã sáng lập Google tại đại học Stanford Hiện nay, Google được biết đến như là công cụ tìm kiếm hàng đầu thế giới, thu hút rất nhiều người tham gia quảng cáo trên nền tảng này.
Trên thế giới, có ba công cụ tìm kiếm chính là Google, Yahoo và MSN, mỗi công cụ đều sở hữu cơ sở dữ liệu và thuật toán riêng Nhiều công cụ tìm kiếm khác sử dụng dữ liệu từ ba công cụ này; ví dụ, AOL Search sử dụng cơ sở dữ liệu của Google, trong khi AltaVista, Lycos và AllTheWeb lại dựa vào dữ liệu của Yahoo.
Hiện nay, Google là một trong những công cụ tìm kiếm phổ biến nhất Để đạt được kết quả tìm kiếm với độ chính xác cao, cần chú trọng đến hai yếu tố quan trọng của Google: đầu tiên là việc sử dụng cấu trúc của các siêu liên kết, cụ thể là thuật toán PageRank để phân hạng cho mỗi trang web; thứ hai là tên miền và các siêu liên kết được tối ưu hóa để cải thiện hiệu quả tìm kiếm.
Google được cài đặt bằng C hay C++, hoạt động trên hệ điều hành Solaris và Linux Quá trình tìm kiếm các trang web được thực hiện bởi các bot dò tìm (web crawler) phân tán Một máy chủ (server) sẽ gửi danh sách các URL cần tìm đến các bot dò tìm Các trang web tìm kiếm sẽ được lưu trữ trong kho của các server, sử dụng nén dữ liệu Khi phân tích một URL mới, mỗi trang web sẽ được gán một mã nhận dạng duy nhất, gọi là DocID Việc lập chỉ mục có thể thực hiện bởi bộ lập chỉ mục (Indexer) và bộ sắp xếp (Sorter) Bộ lập chỉ mục thực hiện các chức năng như lưu trữ dữ liệu, nén và phân tích các tài liệu Mỗi tài liệu sẽ được chuyển đổi thành tập tin xuất hiện của các từ, gọi là các hit.
Các hit được ghi nhận, vị trí trong tài liệu, kích thước font chữ, và chữ hoa hay chữ thường Bộ nhớ sẽ phân phối các hit này vào trong một tập các barrels (thùng), tạo thành một cấu trúc đã sắp xếp theo từng phần Ngoài ra, bộ nhớ còn phân tích tất cả liên kết trong môi trường web và lưu thông tin quan trọng về chúng trong một file anchor Tập tin này chứa đựng thông tin xác định liên kết này từ đâu, đến đâu và chứa đựng nội dung liên quan đến các liên kết Trình phân giải URL được tập tin các neo tạm thời và chuyển các URL tương đối thành các URL tuyệt đối và trả về các docID Từ các bản neo vào bộ nhớ forward có liên quan đến docID mà neo chỉ đến và tạo một cơ sở dữ liệu tương ứng về các liên kết với các docID.
C s d li u này đ c dùng đ tính các PageRank cho t t c các tài li u
BSPXPLy các barrel đã được xử lý và sắp xếp chúng theo docID để sinh ra một chỉ mục ngữ nghĩa Công việc này được thực hiện ngay tại chỗ nên không mất nhiều băng thông BSPXPLy cũng đồng thời sinh ra một danh sách WordID và bù lấp cho chỉ mục ngữ nghĩa đó Một chương trình gọi là DumpLexicon sẽ lấy danh sách này và tạo một từ vựng được sinh bởi bậc chỉ mục và tạo một từ vựng mới được dùng cho bộ tìm kiếm Bộ tìm kiếm được chạy bởi một web server và sử dụng từ vựng đã được DumpLexicon xây dựng cùng với chỉ mục ngữ nghĩa và các PageRank để trả lời các truy vấn.
T c đ tìm ki m c a Google ph thu c và hai y u t : hi u qu c a thu t toán tìm ki m và s liên k t x lý c a hàng ngàn hàng ngàn máy tính c p th p đ t o nên m t S.E siêu t c
Google sử dụng thuật toán PageRank để đánh giá hơn 100 tỷ trang web, một phương pháp được phát triển bởi Larry Page và Sergey Brin tại Đại học Stanford PageRank dựa vào cấu trúc liên kết giữa các trang web, coi mỗi liên kết từ trang A đến trang B như một lá phiếu ủng hộ cho trang B Ngoài ra, Google còn phân tích khối lượng liên kết từ các trang khác để xác định tầm quan trọng của trang web Các trang có chất lượng cao sẽ nhận được PageRank cao hơn, điều này ảnh hưởng đến vị trí của chúng trong kết quả tìm kiếm Tuy nhiên, một trang không có giá trị ban đầu sẽ không phù hợp với truy vấn Google kết hợp PageRank với các thuật toán tìm kiếm tinh vi để xác định các trang quan trọng và phù hợp với nội dung tìm kiếm Kết quả tìm kiếm không chỉ dựa vào số lượng mà còn vào nội dung của trang và các trang liên kết đến nó.
Google cập nhật các thuật toán của mình hàng tháng, dẫn đến sự thay đổi trong thứ hạng của các trang web Mỗi khi có dữ liệu mới, có thể có những trang mới được thêm vào, một số trang bị xóa, và thứ hạng của một số trang có thể thay đổi Thứ hạng ban đầu của một trang có thể bị ảnh hưởng bởi thứ hạng của các trang khác Không ai có thể can thiệp để nâng cao thứ hạng của một trang, vì kết quả trả về hoàn toàn tự động Dù Yahoo có sử dụng Google để hỗ trợ tìm kiếm, cách xử lý truy vấn của hai công cụ này không hoàn toàn giống nhau Điều này khiến kết quả của cả hai công cụ không thể hoàn toàn trùng khớp Tính năng lưu trữ (cache) của Google, được giới thiệu vào năm 1997, cho phép người dùng truy cập vào bản sao của bất kỳ website nào, nhưng không giống như các dự án lưu trữ khác, tính năng này không tạo ra bản sao cố định của trang web mà thực hiện tìm kiếm liên tục các đường link Tuy nhiên, tính năng cache cũng gây ra vấn đề về quyền riêng tư, khi người tìm kiếm có thể xem thông tin dành riêng cho các thuê bao có đăng ký Hiện nay, Google đã xử lý hơn 8 tỷ trang tài liệu và đang thử nghiệm một phiên bản mới tại http://www.scholar.google.com/.
LYCOS
Lycos là một công cụ tìm kiếm thuộc gia đình nhện Lycosidae, chuyên cung cấp thông tin từ các trang web Kết quả tìm kiếm được sắp xếp theo chu kỳ hàng tuần, giúp người dùng dễ dàng tìm kiếm tài liệu Lycos cho phép người dùng tìm kiếm các tài liệu chứa các từ khóa do chính họ cung cấp, nhanh chóng trở thành phổ biến đối với những ai có nhu cầu tìm kiếm toàn bộ nội dung trong không gian tài liệu.
Lycos là một công cụ tìm kiếm trên không gian Web, cho phép truy cập vào các tài liệu trong các không gian HTTP, FTP, và Gopher Công cụ này sử dụng văn bản trong tài liệu để tạo thành các liên kết khám phá (anchor text) cho việc tìm kiếm Tuy nhiên, Lycos không thể tìm kiếm và lập chỉ mục cho các không gian vô hạn hoặc biến đổi, do đó nó không hỗ trợ các không gian như cơ sở dữ liệu WAIS, tin tức Usenet, không gian Mailto, dịch vụ Telnet, và các không gian tệp tin cục bộ.
Nhằm gia tăng hiệu quả tối ưu hóa công cụ tìm kiếm (SEO), Lycos lưu trữ thông tin quan trọng từ tài liệu như tiêu đề, heading và sub-heading, cùng với 100 từ khóa chính và 20 dòng đầu tiên của nội dung, được tính theo kích thước byte Hệ thống đánh giá các từ khóa dựa trên vị trí và tần suất xuất hiện trong tài liệu, với các từ xuất hiện trong tiêu đề và đoạn đầu tiên được tính điểm cao hơn Điều này giúp nâng cao khả năng hiển thị và xếp hạng của tài liệu trên các công cụ tìm kiếm.
Lycos sử dụng phương pháp thống kê độc lập qua các server trong không gian Web, nhằm tránh làm quá tải máy chủ với hàng loạt yêu cầu Điều này cho phép Lycos tiếp cận các URL có nhiều thông tin hơn một cách hiệu quả Các bước cần thiết của thuật toán bao gồm:
1 Khi m t tìm th y m t Url, Lycos quét qua n i dung c a nó, tìm các tham chi u đ n các Url m i và đ a vào m t hàng đ i n i b
2 ch n Url k ti p, Lycos l a ng u nhiên m t tham chi u trong hàng đ i trên theo đ u tiên
Lycos là công cụ tìm kiếm chuyên cung cấp các tài liệu phức tạp, bao gồm những tài liệu có nhiều kết nối nội dung Nó cũng hỗ trợ các URL ngắn gọn, tập trung vào các thư mục cấp cao nhất (top-level) và các tài liệu liên quan chặt chẽ.
Bùng n c máy tìm ki m ti ng Vi t
Các website tìm ki m VN đang đe d a Google và Yahoo!
Google hi n đang là c máy tìm ki m s m t trên th gi i, nh ng các n c nh Trung Qu c, Nh t, Hàn Qu c, Philippines h luôn đ ng sau các website tìm ki m n i đ a
Từ năm 2007, thị trường tìm kiếm trực tuyến tại Việt Nam đã trở nên sôi động với sự ra đời của nhiều website tìm kiếm như timnhanh.com, do Công ty cổ phần mạng trực tuyến Việt Nam (VON) phát triển, nhận được đầu tư 2 triệu USD từ VinaCapital Timnhanh.com tích hợp thông tin theo kiểu Yahoo! với 25 dịch vụ khác nhau và áp dụng công nghệ web 2.0, cho phép người dùng tương tác với thông tin Ông Phan Ngọc Dũng, giám đốc VON, cho biết họ có kế hoạch phát triển Timnhanh thành một "đô thị" dịch vụ cho người sử dụng Cùng thời điểm, IDG Ventures Việt Nam cũng đầu tư vào các dịch vụ tìm kiếm như baamboo.com và diadiem.com Tháng 11 năm 2007, VinaGame ra mắt trang tìm kiếm nhạc Zing MP3, trong khi monava.vn xuất hiện với tuyên bố có 2 triệu người dùng Việt Nam trong vòng hai năm Nhiều website tìm kiếm khác như 7sac.com và socbay.com đang trong giai đoạn thử nghiệm Vinaseek.com, một website tìm kiếm nổi tiếng, cũng đang được Công ty Tinh Vân đầu tư mạnh mẽ Cuộc chiến giành thị phần tìm kiếm tại Việt Nam đang diễn ra quyết liệt, với sự cạnh tranh từ Google và Yahoo! Ông Lê Trần Trọng An, tổng giám đốc Công ty Vietbooks, nhận xét rằng đây là một sân chơi đầy tiềm năng cho các website tìm kiếm Việt Nam, với nội dung đa dạng và sáng tạo.
Khi so sánh các công cụ tìm kiếm với từ khóa "Trịnh Công Sơn", kết quả cho thấy Google dẫn đầu với 1.270.000 trang thông tin, tiếp theo là Yahoo với 799.000, Monava 715.000, MSN 382.000 và Vinaseek 114.300 Đối với các trang nhạc, ZingMp3 đứng đầu với 1.467 kết quả, theo sau là Baamboo với 1.250, Socbay 624, Monava 498 và 7sac 170.
Theo nhu cầu người sử dụng, Google vẫn là công cụ tìm kiếm hàng đầu, nhưng Monava lại tỏ ra không kém cạnh so với Yahoo! Trong khi đó, nếu tìm kiếm các bản nhạc, các công cụ tìm kiếm của Việt Nam hoàn toàn vượt trội hơn Google và Yahoo!.
Ông Hoàng Quốc Việt, Tổng Giám đốc Công ty Nguyễn Hoàng, đã đầu tư 500.000 USD vào Monava, nhấn mạnh rằng hiện tại không có website nào của Việt Nam có thể cạnh tranh với Google Ông cho biết Google đã phát triển hơn 10 năm và có số lượng server khổng lồ, đảm bảo tốc độ truy cập nhanh và nguồn kinh phí dồi dào cho đầu tư.
Thị trường Việt Nam còn khá nhỏ so với Google, nên không có nhiều đầu tư vào các tính năng phù hợp với người dùng Việt Điều này tạo cơ hội cho các công cụ tìm kiếm Việt Nam cạnh tranh với Google, nếu họ tập trung vào nhu cầu cụ thể của người dùng trong nước Việc phát triển những tính năng độc đáo và phù hợp với người dùng Việt sẽ giúp họ có cơ hội thành công trên "sân nhà".
Các công cụ tìm kiếm của Việt Nam đang phát triển mạnh mẽ với ba yếu tố nổi bật: các công cụ tìm kiếm tập trung phát triển những tính năng mới mà Google hay Yahoo! chưa có; khả năng tìm kiếm hỗ trợ tiếng Việt hiệu quả.
Việc tìm kiếm theo chiều dọc đang ngày càng phát triển tại Việt Nam, với nhiều hình thức như nhạc, blog, video và hình ảnh, nhằm đáp ứng nhu cầu tìm kiếm đa dạng của người dùng Trong bối cảnh số lượng người sử dụng Internet gia tăng, các công cụ tìm kiếm theo chiều dọc cũng có những bước tiến đáng kể Mặc dù Google vẫn dẫn đầu trong tìm kiếm thông tin chung, các công cụ tìm kiếm tại Việt Nam đang có tiềm năng cạnh tranh mạnh mẽ trong lĩnh vực tìm kiếm theo chiều dọc.
M t s trang web “cây nhà lá v n” n i b t
http://socbay.vn/
M t trong s ít nh ng trang tìm ki m c a Vi t Nam xây d ng đ c b máy tìm ki m riêng So v i Yahoo! hay Google, kh n ng "hi u" ti ng
Sóc Bay, một hệ thống tìm kiếm độc đáo được phát triển bởi Naiscorp từ năm 2002, đang không ngừng cải thiện chất lượng dịch vụ để đáp ứng nhu cầu đa dạng của người dùng Trang web hiện cung cấp nhiều dịch vụ tìm kiếm phong phú như tin tức, MP3, video, rao vặt, từ điển và hình ảnh Với hơn 80 triệu lượt truy cập mỗi ngày, Sóc Bay đã khẳng định vị thế của mình trong lĩnh vực tìm kiếm tại Việt Nam, nhờ vào sự đầu tư nghiên cứu lâu dài và đội ngũ chuyên gia chất lượng Kết quả tìm kiếm của Sóc Bay được xử lý chỉ trong 1 giây, mang lại trải nghiệm nhanh chóng và hiệu quả cho người dùng.
http://xalo.vn/
Phát tri n b i công ty Tinh Vân, http://xalo.vn/ đ c phát tri n theo hai h ng ch đ o
Thành phố đã tập trung vào việc đáp ứng nhu cầu tìm kiếm của người dùng như tìm web, tin tức, blog, MP3, video, và nhiều nội dung khác Công cụ tìm kiếm này có khả năng cung cấp cho người dùng thông tin chuyên sâu về một lĩnh vực cụ thể như bất động sản, tài chính, thể thao, và du lịch Đây thực sự là một lợi thế của Thành phố, khi công ty Tinh Vân đã khéo léo áp dụng kinh nghiệm từ nhiều năm cung cấp Vinaseek, một công cụ tìm kiếm khác trước đó.
Trang web cung cấp thông tin "Việt hóa" cho người dùng, với mục tiêu tối ưu hóa kết quả tìm kiếm bằng tiếng Việt Được phát triển bởi Sóc Bay, công cụ này hiện có hơn 600.000 địa điểm nổi tiếng tại Việt Nam và hơn 26.000 trò chơi mới, đi kèm với kho dữ liệu phong phú Người dùng khó có thể phàn nàn về chất lượng của công cụ này.
http://baamboo.com/
M i đ u, Baamboo là m t s n ph m c a Công ty CP Truy n thông
Việt Nam đang hoạt động đa dạng trên sân khấu hợp của nhiều dự án khác nhau như Trà Tân, Đàm Tiến, Đàm Thị, và hơn thế nữa Tuy nhiên, Baamboo nổi bật với sản phẩm "nội nhạc cần", cung cấp Baamboo MP3 và Video, hai loại hình giải trí hấp dẫn thu hút người dùng Internet đến với trang web của mình Như các bạn đã thấy, tất cả các video được xem trên Gamek đều "Powered by Baamboo".
Mỗi tính năng nổi bật của Baamboo giúp người dùng dễ dàng kết hợp với các trang web như http://tratu.vn/ và http://timdiemthi.com/ Điều này cung cấp cho học sinh một phương pháp nhanh chóng để tra cứu điểm thi đại học và điểm chuẩn của các trường, đáp ứng nhu cầu học tập của các bạn học sinh.
Baamboo đã ra mắt trang web http://muagioi.vn/, chuyên cung cấp thông tin về các mặt hàng điển hình trong ngành thời trang di động Trang web này giúp người dùng tìm kiếm và cập nhật thông tin mới nhất về thị trường Hiện tại, Baamboo trung bình nhận khoảng 500.000 lượt truy cập mỗi ngày và dự đoán số lượng này sẽ tiếp tục tăng trong thời gian tới.
Chúng ta có thể tìm kiếm thông tin qua nhiều trang web hữu ích như http://diadiem.com/ cho các địa điểm, và các trang rao vặt chuyên nghiệp như http://timnhanh.com/, http://www.7sac.com/, và http://www.123go.vn/ để tìm kiếm sản phẩm và dịch vụ.
Trong những năm gần đây, sự bùng nổ của Internet tại Việt Nam đã giúp các doanh nghiệp nhận ra lợi ích to lớn từ việc quảng cáo trên các công cụ tìm kiếm, trở thành nguồn thu chính cho các trang web Việt Nam hiện đang nằm trong số những quốc gia có tốc độ phát triển công nghệ thông tin nhanh nhất thế giới, và hy vọng rằng trong tương lai, các công cụ tìm kiếm "made in Việt Nam" sẽ ngày càng phát triển và đạt được thành công.
PH N B: CH NG TRÌNH DEMO
Gi i thi u ch ng trình
_ Ch ng trình s tìm ki m t trong trang web offline (đã t i v t ngu n Internet)
_ Qui trình th c thi c a ch ng trình:
• Quét file, th m c trong th m c root (do ng i l p trình đnh s n)
• Tìm t p tin HTML N u có s x lý t p tin HTML (đánh ch m c, …) Ng c l i quét ti p th m c con đ l y t p tin HTML cho đ n khi nào h t
_ Scan all folders and files.
Are there HTML or HTM files ?
_ Open this file _ Scan all words to index _ Save results in cache
Mô hình ch ng trình
Ý NGH A
_ CATALOG qu n lý danh sách các WORD
_ WORD qu n lý danh sách các FILE.
L p FILE
_ Ch a thông tin c a t p tin mà ch ng trình quét đ c
• FileDate: th i gian mà t p tin đ c quét
• Description: chú thích t p tin HTML
• Kh i t o: File(url, title, filedate, size, desc).
L p WORD
_ Ch a danh sách các FILE mà ch ng trình quét đ c
Word text: string fileCollection: Hashtable
File url: string title: string fileDate: Date size: long int Desc: string File(url, title, filedate, size, desc)
• fileCollection (Hashtable): ch a danh sách các FILE
• Text (String) : t _ Ph ng th c:
• L y danh sách t p tin: Hashtable InFiles()
L p CATALOG
_ Ch a danh sách các WORD
• Index (Hashtable) _ Ph ng th c:
• Thêm: Add (word, file) _ Tìm ki m: Hashtable Search (word)
T p tin Crawler.aspx
_ Xây d ng CATALOG và l u k t qu vào cache.
T p tin Home.aspx
_ Truy v n CATALOG t cache và cho phép tìm ki m t mà ng i dùng nh p vào.
Chi ti t ch ng trình
L p FILE
{ public string Url; public string Title; public string Description; public DateTime CrawledDate; public long Size;
{ return "\tFILE :: " + Url + " " + Title + " - " + Size + " bytes + \n\t" + Description + "\n";
L p WORD
using System.Collections; public class Word
//chua tu da co trong danh muc (co trong Catalog) public string Text;
// Danh sach cac file co tu xuat hien trong do private Hashtable fileCollection = new Hashtable();
// Thiet lap voi file duoc tham chieu dau tien public Word(string text, File inFile, int position)
Text = text; fileCollection.Add(inFile, 1);
// Them file dang tham chieu tu dang xet public void Add(File inFile, int position)
// If da co file trong ds thi cong gia tri them 1 if (fileCollection.ContainsKey(inFile))
/*int nWordCount = (int)fileCollection[inFile]; fileCollection[inFile] = nWordCount + 1;*/ fileCollection[inFile] =
// Tra ve ds file chua tu (gia tri la wordCount) public Hashtable InFiles()
{ string temp = ""; foreach (object tempFile in fileCollection.Values) temp += ((File)tempFile).ToString(); return "\tWORD :: " + Text + "\n\t\t" + temp + "\n"; }
L p CATALOG
using System.Collections; using System.IO; using System.Text.RegularExpressions; public class Catalog
// Ds doi tuong Word private Hashtable index; public Catalog()
// Them cap Word/File vao Catalog (dua no vao index) public bool Add(string word, File inFile, int position) {
// xet dieu kien de tu muon them chi duoc index 1 lan
// if tu muon them da dc index thi add file tham chieu do vao doi tuong Word
// Nguoc lai thi them word vao index if (index.ContainsKey(word))
Word theWord = (Word)index[word]; theWord.Add(inFile, position);
Word theWord = new Word(word, inFile, position); index.Add(word, theWord);
// Tra ve tat ca files co chua tu duoc search (Dau ra la Hashtable) public Hashtable Search(string searchWord)
/// If tu do co trong index
/// thi dung phuong thuc InFiles cua Word obj tra ve ds file chua tu do
/// Nguoc lai thi tra ve null
Hashtable retVal = null; if (index.ContainsKey(searchWord))
Word theWordMatch = (Word)index[searchWord]; retVal = theWordMatch.InFiles();
{ string wordlist = ""; return "\nCATALOG :: " + index.Values.Count.ToString() + " words.\n" + wordlist;
Crawler.aspx
_ Nhi m v đ u tiên là xây d ng các t p tin HTML mà chúng ta mu n tìm ki m
• Spidering – b t/theo các đ ng d n (link) trong toàn b website (ho c các trang web)
• Crawling – vi c thu th p d li u s thông qua các t p tin, th m c và l p ch m c t t c các t p tin trong th m c đó b ng cách s d ng t p tin h th ng
_ ch ng trình này chúng em hi n th c ch ng trình theo cách th
2 private void CrawlCatalog(string sRoot, string sPath)
DirectoryInfo m_dir = new DirectoryInfo(sPath);
// Tao vong lap lay files foreach (FileInfo fInfo in m_dir.GetFiles(m_filter)) {
Response.Write(DateTime.Now.ToString("t") + " " + m_url + sPath.Substring(m_path.Length) + "\\" + fInfo.Name);
//
} // foreach xu ly (danh dau/phan tich) noi dung file
// Goi de qui de qua thu muc khac foreach(DirectoryInfo d in m_dir.GetDirectories()) {
Hình 4: Thu th p các t p tin – đã t i v t trang http://www.java2s.com/
_ Quá trình th c hi n craw:
• L y danh sách t p tin và th m c trong th m c g c (đã hoàn thành)
• M t p tin đ u tiên và đ c n i dung c a nó
• Tìm tiêu đ (Title), mô t (Description) và tính kích th c t p tin HTML
• T o đ ng d n URL c a t p tin đó (khi craw ch ng trình s l y đ ng d n h th ng Vì v y ph i t o đ ng d n URL đ ng i dùng click vào k t qu đ d n đ n trang web đó)
• Chu n hóa các t (bi n các t HOA thành t th ng)
• Thêm m i WORD vào CATALOG và đ ng d n URL t p tin ch a t
• óng t p tin đang xét và m t p tin ti p theo N u đã quét h t t p tin trong th m c đó thì quét th m c ti p theo
• Quét cho đ n khi không còn t p tin
_ Có 3 công vi c chính ph i làm:
• M t t c các t p tin tìm th y - s d ng không gian tên System.IO
DirectoryInfo m_dir = new DirectoryInfo(sPath);
// Tao vong lap lay files foreach (FileInfo fInfo in m_dir.GetFiles(m_filter))
Response.Write(DateTime.Now.ToString("t") + " " + m_url + sPath.Substring(m_path.Length) + "\\" + fInfo.Name);
Response.Flush(); sFileUrl = m_url + sPath.Substring(m_path.Length).Replace("\\", "/") + "/" + fInfo.Name;
StreamReader reader = System.IO.File.OpenText(sPath
// Do noi dung trang web vao sFileContents sFileContents = reader.ReadToEnd(); reader.Close();
• Tìm ki m nh ng ch đ c bi t trong t p tin (title, description,…) – s d ng không gian tên System.String ho c System.RegularExpressions
Match TitleMatch = Regex.Match(sFileContents,
RegexOptions.Multiline); sFileTitle = TitleMatch.Groups[1].Value;
// - Xu ly the META data -
Match DescriptionMatch = Regex.Match(sFileContents,
RegexOptions.IgnoreCase | RegexOptions.Multiline); sFileDesc = DescriptionMatch.Groups[1].Value;
// - Lay kich thuoc - nFileSize = sFileContents.Length;
// - Lay noi dung tap tin (Loai bo cac the
HTML) - string sWordsOnly = stripHtml(sFileContents);
// - Thu thap META DESC - if (sFileDesc == null || sFileDesc == String.Empty)
{ if (sWordsOnly.Length > 350) sFileDesc = sWordsOnly.Substring(0, 350); else if (sWordsOnly.Length > 100) sFileDesc = sWordsOnly.Substring(0, 100); else sFileDesc = sWordsOnly;
• Phân tích thành nh ng t riêng l - s d ng không gian tên System.RegularExpressions protected string stripHtml(string sHTML)
// Thay cac the bang khoang trang string sOutPut = objRegExp.Replace(sHTML, " ");
// Doi thanh < and > sOutPut = sOutPut.Replace(">", "<"); sOutPut = sOutPut.Replace("
