Giới thiệu về Search Engine

Khi nói tới Search Engine, ta thường nghĩ ngay đến các dịch vụ nổi tiếng như Google Search, Yahoo! Search hay MSN Search, v.v…Tuy nhiên, bộ phận tìm kiếm trong một website cụ thể cũng được coi là Search Engine. Internet chứa hầu như tất cả những thông tin liên quan tới mọi lĩnh vực, mọi ngõ ngách trong cuộc sống. Nhưng nó rất rộng, rộng đến mức gần như không ai có thể kiểm soát được. Diện mạo của Internet lại thay đổi quá nhanh chóng và mạnh mẽ. Hạt nhân của Internet là Word Wide Web, với số lượng lên tới hàng chục tỉ trang, được lưu trữ trong hàng triệu máy chủ đặt khắp nơi trên toàn thế giới. Có thể ví Internet như một biển dữ liệu khổng lồ, với muôn vàn những viên ngọc quí nằm giữa các hạt sạn. Trong đời sống hàng ngày, nhu cầu tìm kiếm thông tin đóng vai trò vô cùng to lớn, và một trong những vấn đề bức thiết nhất của công nghệ hiện nay là làm sao "đãi cát tìm vàng", khai thác nguồn tài nguyên này một cách hợp lí, đem lại lợi ích tốt nhất cho con người. Tìm kiếm thông tin trên mạng Internet quả thật là một thách thức lớn lao. Nó không giống như việc bới các hạt đỗ đen nằm lẫn lộn trong thùng gạo, bởi dữ liệu trên mạng Internet do con người đưa vào, chúng cũng có cấu trúc và tổ chức xác định (mặc dù thiếu tính nhất quán), trong khi đó thì các hạt đỗ đen lại nằm rải rác và lộn xộn, không có một vị trí hay qui luật nào. Tuy nhiên, bài toán tìm kiếm khó hơn bài toán nhặt đỗ đen rất nhiều. Muốn tìm tất cả các hạt đỗ đen, bạn đơn giản chỉ cần thiết kế một cái sàng hình cầu đủ lớn để có thể đổ cả thùng gạo vào đó, với những chiếc lỗ có kích thước phù hợp sao cho hạt gạo chui lọt còn hạt đỗ đen thì không, và quay đủ số vòng để tất cả các hạt gạo đều có cơ hội bay ra ngoài. Việc tìm kiếm thông tin trên Internet lại hoàn toàn khác. Có tới hàng chục tỉ trang Web tràn ngập trên mạng Internet (gấp nhiều lần số hạt gạo trong thùng), và vấn đề là làm sao đưa ra những gì ta muốn thu thập sao cho đồng thời thỏa mãn hai tiêu chí: Chính xác và nhanh chóng. Hơn thế nữa, người dùng cũng không đủ kiên nhẫn để ngồi duyệt qua tất cả các trang web chứa thông tin cần tìm (anh ta cũng không nhất thiết phải đếm từng hạt đỗ đen, tuy nhiên nếu xét trên tiêu chí dinh dưỡng thì đa phần những hạt đỗ đen đều giống nhau, do đó hạt nào cho vào nồi trước cũng không quan trọng). Trên thực tế, người dùng hiếm khi vào quá mười trang web kết quả, và vì thế, một yêu cầu khó khăn nữa cần giải quyết, đó là: những gì phù hợp nhất phải được đặt lên hàng đầu. Trước đây, người ta thường chia dữ liệu cần lưu trữ làm nhiều mục, đến lượt các mục con này lại được chia nhỏ hơn. Người dùng tìm kiếm thông tin thông qua việc duyệt qua liên kết giữa các mục. Tuy nhiên, những chủ đề được nêu trong Internet đã rộng lớn đến nỗi sự phân chia này trở nên cực kì cồng kềnh và bất tiện. Ngày nay, hầu hết mọi người đều sử dụng Search Engine để tìm kiếm thông tin trên mạng Internet. Đối với mỗi Search Engine (Google, Yahoo, MSN, v.v…), người dùng truy vấn tìm kiếm (hay nói đơn giản hơn là nhập vào một số từ khóa liên quan đến chủ đề cần tìm), và nhận được một danh sách các trang kết quả (thông thường là những trang web chứa các từ khóa cần tìm kiếm), được sắp xếp theo một tiêu chí nào đó. Những tiêu chí này đều nhằm mục đích "đưa ra kết quả phù hợp nhất với yêu cầu tìm kiếm". Trong bài này ta sẽ nghiên cứu về các Search Engine. Bài viết là một phần trong loạt bài có tựa đề: "Giới thiệu về hệ thống Google". Mục đích của tôi nhằm: - Nêu lên cấu trúc tổng quan của một Search Engine. - Nghiên cứu chi tiết các thành phần của Search Engine. - Giúp bạn có những kiến thức cơ bản để hiểu được cấu trúc phức tạp của hệ thống Google. - Chuẩn bị nền tảng cho loạt bài viết hướng dẫn cách xây dựng một Search Engine. Ban đầu, tôi chỉ định nêu ra các tư tưởng chủ đạo trong việc xây dựng cũng như nói sơ qua về cấu tạo và nguyên lý hoạt động của Search Engine. Tuy nhiên, trong quá trình nghiên cứu tài liệu, tôi đã thay đổi ý định, vì những lí do sau: - Những kiến thức liên quan tới Search Engine rất rộng và tổng hợp, bao gồm thuật toán, cấu trúc dữ liệu, cơ sở dữ liệu, các hệ thống phân tán, tính toán song song, tổ chức file, data mining,v.v… cũng như những vấn đề có liên quan tới toán học. Do đó, việc tìm hiểu Search Engine sẽ hứa hẹn rất nhiều điều thú vị, nếu chỉ đề cập sơ sài, ta sẽ bỏ qua một chủ đề hấp dẫn. Đây cũng là dịp để chúng ta cùng nhau kiểm tra cũng như cập nhật vốn kiến thức của mình.- Tôi nhận thấy nếu không đề cập chi tiết đến cấu tạo của một Search Engine, sẽ khó khăn khi tiếp cận hệ thống Google, vốn chứa đựng rất nhiều sự phức tạp. - Tự xây dựng một Search Engine là một "thách thức" không nhỏ và rất đáng để xem xét. Tất nhiên sản phẩm của những sinh viên như chúng ta không có ý nghĩa gì khi so sánh với Google Search hay Yahoo! Search, và tất nhiên cũng mang rất ít giá trị về mặt thương mại cũng như thực tiễn (phải nói là không có thì đúng hơn). Nhưng đối với bản thân mỗi người học chúng ta thì giá trị học hỏi và kiến thức là rất to lớn, bởi như tôi đã nói ở trên, những mảng đề tài liên quan đến Search Engine là rất nhiều. Tôi coi bài viết này như nền tảng để bạn có thể hiểu cặn kẽ cấu tạo của Internet Search Engine. Tôi có ý định cùng các bạn thử viết một Search Engine với mục đích học tập sau này. Với tinh thần đó, tôi sẽ trình bày thật chi tiết tới mức có thể. - Việc hiểu cấu trúc của Search Engine cũng giúp ích cho các bạn trong việc lập trình xây dựng các trang Web (mặc dù công việc đối với trang Web đơn giản hơn nhiều). - Trong giáo trình công nghệ thông tin cũng như khoa học máy tính ở các trường đại học Việt Nam hiện nay không có môn học về Information Retrieval. Việc tìm hiểu Search Engine cũng cho ta một số kiến thức về lĩnh vực này. Hơn nữa, đây là cơ hội rất tốt để thực hành các tri thức ta đã thu thập được trong những năm học đại học. Vì những lí do trên, tôi sẽ trình bày bài viết theo tư tưởng như sau: - Phần một sẽ đưa ra cái nhìn chung về Search Engine. Bạn đọc không có đủ thời gian cũng như không muốn đi quá sâu vào chi tiết cũng có thể hiểu cấu trúc tổng quan nhất của một Search Engine. Những thông tin trình bày ở đây là đủ để bạn có thể chuyển sang phần sau của loạt bài viết: "Tìm hiểu về hệ thống Google". - Từ phần hai trở đi, chúng ta sẽ đi sâu vào phân tích các thành phần của một Internet Search Engine. Nội dung những phần này vừa nhằm mục đích nghiên cứu kĩ lưỡng từng bộ phận cấu thành một Search Engine, vừa đưa ra những gợi ý liên quan đến cài đặt, tạo tiền đề cho việc tự viết một Search Engine sau này. Khi nói tới Search Engine, ta thường nghĩ ngay đến các dịch vụ nổi tiếng như Google Search, Yahoo! Search hay MSN Search, v.v…Tuy nhiên, bộ phận Tìm kiếm trong một website cụ thể cũng được coi là Search Engine. Xét về mặt bản chất, tìm kiếm thông tin trên mạng Internet hay trên website nào đó đều là tìm kiếm trong cơ sở dữ liệu có sẵn. Mặc dù vậy, việc thực hiện trên Internet khó hơn rất nhiều bởi miền tìm kiếm là vô cùng lớn. Trong loạt bài viết này, ta sẽ dùng thuật ngữ Search Engine để chỉ công cụ tìm kiếm trên mạng Internet nhằm tránh những hiểu lầm về sau. <<http://www.ticsoft.com>>

Kỷ niệm những người học trò!

Tối ưu đa mục tiêu Pareto

Khái niệm then chốt trong tối ưu hoá đa mục tiêu là phương án tối ưu Pareto.
Định nghĩa: X* là nghiệm cần tìm thì X* phải có các tính chất sau:

1. X* phải thuộc điểm các phương án khả thi của bài toán tức là thoả mãn các ràng buộc X* thuộc tập hợp D.
2. Mọi phương án khả thi khác X thuộc D mà có một mục tiêu nào đó tốt hơn ( fi(X)> = fi(X*) thì cũng phải có ít nhất một mục tiêu khác xấu hơn ( fj(X)<fj(X*)) với i khác j.

Nghiệm X* này còn được gọi là nghiệm hiệu quả. Trên tổng thể không có một X nào có thể trội hơn X*.
Từ tối ưu Pareto cho ra các nghiệm hiệu quả, bán hiệu quả và lý tưởng của bài toán. Vậy sự khác biệt của nghững nghiệm này là gì? Có thể nói khi tối ưu hoá đa mục tiêu thì tập tối ưu Pareto thu được là các giá trị thuộc miền xác định D của bài toán mà chúng toả mãn các điều kiện Pareto!
Ta thấy rằng nghiệm bán hiệu quả là các nghiệm mà thoả mãn: không tồn tại một nghiệm X nào khác thuộc tập xác đinh D mà với mọi i : fi(X)> fi(X*).
Nghiệm hiệu quả sẽ là các nghiệm thoả mãn: không tồn tại một nghiệm X nàothuộc tập xác đinh D mà có thể: với mọi i mà fi(X)>= fi(X*) và phải tồn tại một j mà fj(X)>fj(X*).
Để hiểu hơn Gió lấy ví dụ các điểm trên toạ độ De-cac hai chiều như sau(bạn nên vẽ ra để hiểu rõ hơn): nếu có 4 là a,b,c,d. Có toạ độ lần lượt x(a) = x(b) = x(c) = x(d) = 3 nhưng y(a) = 2, y(b) = 3, y(c) = 4, y(d) = 5. Vậy lúc này nghĩ xem đâu là nghiệm bán hiệu quả và hiệu quả ?? Xin trả lời như sau: Nghiệm hiệu quả ở đây sẽ là d. Bởi vì với d thì: f1(a)=f1(b)=f1(c)=f1(d)=2, nhưng không có một f2(a),f2(b) hoặc f2(c) nào có thể lớn hơn f2(d)! Nghiệm bán hiệu quả ở đây là: a,b,c,d. Nếu lúc này ta cho thêm một điểm e(4,4) thì lúc này nghiệm bán hiệu quả sẽ là: c,d,e và nghiệm hiệu quả là: d,e. Nếu  có thêm một điểm là e(2,4) thì nghiệm bán hiệu quả sẽ là: a,b,c,d và nghiệm hiệu quả là d. Nói đến đây Gió nghĩ chúng ta đã phân biệt được hai loại nghiệm này.

Vậy có thể kết luận:

1. Nghiệm hiệu quả cũng chính là nghiệm bán hiệu quả, và không có điều ngược lại! (cho nên nếu gọi tập nghiệm hiệu quả là A, tập nghiệm bán hiệu quả là B thì A<=B).
   
2. Nghiệm hiệu quả và bán hiệu quả luôn luôn tồn tại.

Nghiệm lý tưởng là một nghiệm hiệu quả nhưng nó thoả mãn yêu cầu: mọi X thuộc tập xác định D thì fi(X*)>=fi(X). Vậy trong ví dụ trên 4 điểm a,b,c,d thì nghiệm lý tưởng là d rồi. Nhưng không đánh đồng nghiệm lý tưởng với nghiệm hiệu quả. Nghiệm lý tưởng không phải bao giờ cũng tồn tại. Nếu lấy một ví duk như thế này: cũng trên không gian hai chiều  có 4 điểm a(1.3), b(2,2), c(3,1) thì 3 nghiệm này đều là nghiệm bán hiệu quả và nghiệm hiệu quả nhưng không có nghiệm lý tưởng nào!
Tiếp tục, các bài toán tối ưu trên hàm lồi mạnh (ví dụ parabol) thì nghiệm tối ưu tìm được luôn là nghiệm lý tưởng của bài toán, trên hàm lồi (một đường thẳng) thì nghiệm tìm được có thể là nghiệm hiệu quả thôi.
<<Trích http://hahong.wordpress.com/>>

Một số địa chỉ hay

http://www.scribd.com/doc/72870359/Tim-hi%E1%BB%83u-v%E1%BB%81-cong-ngh%E1%BB%87-NET-Compact-Framework-va-l%E1%BA%ADp-trinh-%E1%BB%A9ng-d%E1%BB%A5ng-tren-Pocket-PC#outer_page_2

Phần 1: Giới thiệu Domain-Specific Development

Giới thiệu:

DSL Tools và một phần của Visual Studio SDK, có thể download từ http://www.microsoft.com/downloads/details.aspx?familyid=51A5C65B-C020-4E08-8AC0-3EB9C06996F4&displaylang=en nếu bạn dùng Visual Studio 2005 và http://www.microsoft.com/downloads/details.aspx?familyid=30402623-93CA-479A-867C-04DC45164F5B&displaylang=en nếu bạn dùng Visual Studio 2008.

DSL Tools tích hợp trong Microsoft Visual Studio 2005 và Microsoft Visual Studio 2008 để hỗ trợ một hướng phát triển phần mềm có tên là Domain-Specifc Development.

Domain-Specific Development dựa trên sự quan sát rằng: nhiều vấn đề phát triển phần mềm có thể được giải quyêt dễ dàng bằng cách thiết kế một ngôn ngữ mục đích đặc biệt (special-purpose language).

Ví dụ, hãy nghĩ đến việc tìm kiếm tất cả sự xuất hiện của một mẫu (pattern) trong một file, và làm một cái gì đó với mỗi sự xuất hiện mà bạn tìm thấy?

· Cách 1: Sử dụng lớp .NET System.Text.RegularExpression.Regex, biểu thức chính qui (regular expression) (?<user>[^@]+)?<host>.+) được áp dụng cho một chuỗi các kí tự sẽ tìm các địa chỉ email trong nó, và cho mỗi địa chỉ tìm thấy, gán chuỗi con ngay trước dấu”@” cho biến user, và chuỗi con ngay sau dấu “@” cho biến host.

· Cách 2: Nếu không có regular expresion, một developer sẽ phải viết một chương trình đặc biệt để nhận ra các pattern (mẫu) và gán các giá trị đúng cho các biến thích hợp. Đây là một nhiệm vụ khá nặng và sẽ gặp nhiều lỗi.

Domain-Specific Development áp dụng cùng hướng tiếp cận trên cho nhiều vấn đề, đặc biệt là những vấn đề bao gồm việc quản lý sự phức tạp của các hệ thống phân tán hiện đại ( ví dụ như những thứ có thể được phát triển trên .NET platform ). Thay vì chỉ sử dụng các ngôn ngữ lập trình mục đích chung (general-purpose programming language) để giải quyết những vấn đề này mỗi cái tại một thời điểm, người sử dụng Domain-Specific Development tạo và cài đặt các ngôn ngữ đặc biệt, mỗi ngôn ngữ giải quyết một cách hiệu quả toàn bộ một lớp các vấn đề tương tự nhau.

Các Domain-Specific Languaguage có thể là textual (text) hay graphical (đồ họa). Các ngôn ngữ đồ họa có các thuận lợi quan trọng hơn các ngôn ngữ text trên nhiều vấn đề, bởi vì chúng cho phép giải pháp được trực quan hóa một cách rất trực tiếp trên các diagram. DSL Tools làm cho việc cài đặt DSL đồ họa trở nên dễ dàng, và cho phép Domain-Specific Development được áp dụng cho một phạm vi rộng và cho nhiều vấn đề.

Domain-Specific Development

Domain-Specific Development là một cách giải quyết các vấn đề mà bạn có thể áp dụng khi một vấn đề cụ thể xuất hiện lặp đi lặp lại.

Mỗi sự xuất hiện của vấn đề có nhiều khía cạnh giống nhau, và mỗi phần có thể được giải quyết một lần và cho tất cả (xem Figure 1-1).

Các khía cạnh khác nhau của một vấn đề được thể hiện bởi một ngôn ngữ đặc biệt. Mỗi sự xuất hiện cụ thể đó được giải quyết bằng cách tạo ra một model hay biểu thức trong ngôn ngữ đặc biệt và gắn model này vào trong phần cố định của solution.

Phần cố định của solution được viết sử dụng các thiết kế, coding và testing truyền thống, phụ thuộc vào kích thước và hình dạng của vấn đề, phần cố định này của solution có thể được gọi là một framework, một platform, một trình thông dịch, hay một Aplication Programming Interface (API). Phần cố định capture các mẫu kiến trúc mà hình thành nên domain và đưa ra các điểm mở rộng cho phép nó được sử dụng trong nhiều solution.

What makes the approach applicable is the fact that you create the variable part of the solution by using a special-purpose language—a DSL.

DSL có thể là văn bản hay đồ họa. Vì công nghệ cho domain-specific development đã hoàn thiện, chúng ta mong đợi thấy các công cụ hổ trợ việc phát triển và tích hợp của các DSL text và đồ họa. Con người có một dãy các cảm giác về loại ngôn ngữ nào mà họ thích hơn. Ví dụ, nhiều người thích các ngôn ngữ text cho input, bởi vì họ có thể gõ nhanh, nhưng các ngôn ngữ đồ họa cho ouput, bởi vì có thể dàng xem “bức tranh lớn” (big picture) trong một diagram. Các biểu thức text thì dễ tính toán sự khác biệt và dễ kết hợp hơn, trong khi các biểu thức đồ họa thì dễ thấy các mối quan hệ hơn.

Để tạo ra một giải pháp hoạt động cho vấn đề được chỉ ra, phần cố định của giải pháp phải được tích hợp với phần thay đổi được thể hiện bởi model. Có 2 hướng tiếp cận phổ biến cho việc tích hợp này.

· Thứ nhất, là hướng tiếp cận trình diễn, mà phần cố định chứa một trình thông dịch cho DSL được sử dụng để thể hiện phần thay đổi. Một hướng tiếp cận như thế có thể linh hoạt, nhưng nó có thể có các bất lợi về việc thể hiện kém và khó khăn trong việc debug.

· Thứ hai, một biểu thức đặc biệt hay diagram (biểu đồ) có thể được convert một cách đầy đủ thành code và có thể được biên dịch cùng với phần còn lại của giải pháp – đó là hướng tiếp cận phát sinh code. Đây là một thủ tục biến đổi phức tạp hơn, nhưng nó cung cấp các thuận lợi trong khả năng mở rộng, biểu diễn, và debug.

Các DSL đồ họa không chỉ là các diagram. Nếu bạn chỉ muốn tạo ra các diagram, bạn có thể sử dụng các chương trình vẽ diagram nổi tiếng như Microsoft Visio để đạt được kết quả lớp thứ nhất (first-class result). Thay vào đó, bạn đang thực sự tạo ra các model thể hiện một cách khái niệm hệ thống mà bạn đang xây dựng, cùng với các sự thể hiện bằng biểu đồ nội dung của chúng. Một model được thể hiện đồng thời bởi một hay nhiều diagram, với mỗi diagram thể hiện một khía cạnh đặc biệt của model, xem Figure 1-2 để thấy rõ hơn

 
>>Phần 2

Vì sao tôi viết Blog!

Tôi muốn chia sẻ kỉ niệm của tôi với mọi người!