Đồ án Xây dựng ứng dụng phân tích ngữ nghĩa trong tìm kiếm tài liệu trực tuyến

us – Based) Hướng tiếp cận này sẽ rút ra các quy luật xử lý ngữ nghĩa (bằng thống kê, bằng máy học,…) từ những kho dữ liệu lớn đã có sẵn và áp dụng các luật này cho trường hợp mới. Thực ra, cách tiếp cận này đã được nêu ra rất sớm (1940), nhưng do nguồn dữ liệu hạn chế, thiết bị xử lý chưa hiện đại nên không có điều kiện phát triển. Mãi tới thập niên 1990, khi mà công nghệ phát triển mạnh, đã có thể vượt qua được khó khăn của mình, cách tiếp cận này được hồi sinh và phát triển mạnh tới ngày nay. Hiện nay, cách tiếp cận dựa trên ngữ liệu kết hợp với tri thức có sẵn là hướng tiếp cận đang được nhiều nhà ngôn ngữ học – máy tính quan tâm. Phân tích ngữ nghĩa tiềm ẩn (LSA) Cũng liên quan tới mảng ngữ nghĩa của từ, trong đồ án tốt nghiệp này, chúng tôi khai thác chiều khác của phân tích về mặt ngữ nghĩa. Ngoài việc tương đồng từ khóa về mặt hình thức (về bản mặt từ), chúng tôi còn đề cập tới tương đồng về nội dung của tài liệu. Có nhiều phương pháp khác nhau để đánh giá sự tương đồng về nội dung như phương pháp Định chỉ số ngữ nghĩa tiềm ẩn (LSI – Latent Semantic Index), phương pháp Phân tích ngữ nghĩa tiềm ẩn (LSA – Latent Sematic Analys). Chỉ mục ngữ nghĩa tiềm ẩn (LSI) thêm một bước quan trọng cho việc xử lý chỉ mục tài liệu.Thêm vào việc ghi những từ khóa mà một tài liệu chứa. Phương pháp này khảo sát toàn bộ tập dữ liệu, để thấy những tài liệu khác chứa một số từ tương được với các từ đó. LSI được phát triển đầu tiên ở Bellcore trong cuối những năm 80. LSI xem các tài liệu có nhiều từ thông dụng là có nghĩa, và xem những tài liệu ít từ thông dụng là ít có nghĩa. Mặc dù thuật giải LSI không hiểu tí gì về nghĩa của các từ, nó nhận ra các khuân mẫu. Khi bạn tìm kiếm một CSDL chỉ mục LSI, công cụ tìm kiếm này xem xét những giá trị tương tự mà nó tính toán cho mỗi từ của nội dung, và trả về các tài liệu mà nó nghĩ là thích hợp nhất với câu truy vấn. Bởi vì hai tài liệu có thể rất gần nghĩa với nhau thậm chí nếu chúng không cùng chung một từ khóa đặc biệt, LSI không yêu cầu một sự phân tích lấy tương xứng để trả về các kết quả hữu dụng. Ở những vị trí mà một tìm kiếm theo từ khóa đơn giản sẽ không thực hiện được nếu không có phân tích lấy tương xứng, thì LSI sẽ thường trả về những tài liệu liên quan mà không chứa tất cả những từ khóa đó. Phương pháp đề cập nữa là phân tích ngữ nghĩa tiềm ẩn (LSA), là phần kia của đồ án. Xin vui lòng xem đồ án của Mr Cường sẽ có trình bầy chi tiết về phương pháp LSA, và áp dụng của nó trong việc phân tích nội dung của tài liệu. Nhận xét, kết luận Phân tích ngữ nghĩa là một khâu rất quan trọng trong hệ thống gợi ý. Bước tách từ vựng đã tách tài liệu thành các từ khóa và nó đặc trưng cho tài liệu đó. Hệ thống sẽ tìm kiếm trong kết quả trả về cho người dùng lần đầu tiên bằng việc so khớp các từ khóa được nhập với các từ khóa trong phần từ khóa của các tài liệu. Khâu xử lý về nội dung sẽ xác định các tài liệu nào giống tài liệu nào. Giống ở đây chỉ mức độ tương đồng về mặt nội dung giữa các tài liệu đem gợi ý. Có thể hai tài liệu không có bộ từ khóa giống nhau, nhưng nó có thể sẽ giống về nội dung. Thu thập thông tin người dùng Ưu điểm của các hệ thống tự học Hệ thống tự học là hệ thống dựa vào thông tin của người dùng mà người dùng cung cấp những lần giao dịch với hệ thống để phát hiện ra những sở thích lĩnh vực người dùng quan tâm để cải thiện kết quả trả về cho người dùng cho sát với những yêu cầu thực tế. Hệ thống là một phần nhỏ của hệ chuyên gia-là hệ mà khai thác tri thức trong những lần “giao tiếp” với người dùng bằng các tập luật đã được định nghĩa sẵn. Những ưu điểm của hệ thống tự học chúng tôi tổng kết được. Tri thức của hệ thống là tri thức mở. Các giao tiếp với người dùng có thể thay đổi sau những lần giao dịch để thích hợp với sở thích của người dùng hơn. Cho phép người dùng lựa chọn bước tiếp theo của hệ thống. Kết quả tìm kiếm đối với một hệ thống search engine ngày càng sát hơn với nhu cầu của người tìm kiếm. Càng thông minh hơn sau nhiều lần giao dịch với người dùng. Hệ thu nhận và tạo một profile cho người dùng (nếu họ đăng ký thông tin với hệ thống). Và sau những lần giao dịch với hệ, hệ sẽ học được và loại bỏ những thông tin không cần thiết, tăng bộ lọc cho kết quả trả về. Phân tích logfile Logfile là file ghi nhận thông tin về lịch sử làm việc của người dùng với một hệ nào đó. Việc phân tích logfile sẽ góp phần quan trọng để xác định những sở thích của người dùng để thu hẹp phạm vi các kết quả trả về, đồng thời cũng thu thập để chính xác hơn những dữ liệu mà hệ thống có với những hệ gợi ý. Có rất nhiều các kỹ thuật phân tích logfile, trong phạm vi đồ án này, tôi chỉ giới thiệu mà không đi sâu vào phương pháp nào, để giới thiệu một ứng dụng nhỏ trong hệ thống về việc phân tích các thông tin trong các lần giao dịch với hệ thống. Phân tích dựa thông tin người dùng Việc ghi nhận các thông tin của người dùng như địa điểm, độ tuổi, giới tính, hay một số các thông tin về sở thích sẽ giúp hệ thống lọc chính xác hơn các kết quả đưa lại cho người dùng. Thí dụ, một trang nhạc có thể đưa mặc định trong playlist của một người dùng có tuổi 13 những bài hát thiếu nhi. Những hệ thống đa người sử dụng, phân tích dựa trên thống tin người dùng thể hiện ở các nhóm quản trị hệ thống, nhóm các người dùng thông thường hay những khác vãng lai. Với những hệ thống đó, những thông tin về người dùng sẽ quyết định giao diện của hệ thống đối với người dùng đó. Kết luận Một hệ thống recommender system cần phải kết hợp tối đa các phân tích để trả lại kết quả chính xác và phù hợp nhất cho yêu cầu của người dùng. Những thông tin do người dùng cung cấp sẽ là những bộ lọc cho kết quả, những nguồn thông tin đầu vào cho những gợi ý nâng cao. Hệ thống khai thác tri thức dựa trên thông tin được cung cấp bởi người được áp dụng rất nhiều ngay từ những năm 60 được thể hiện ở những hệ chuyên gia, hệ tư vấn. Vấn đề lưu trữ dữ liệu Vấn đề lưu trữ dữ liệu cũng là bài toán không nhỏ với những bộ máy tìm kiếm. Ở phần dưới, tôi sẽ giới thiệu những công cụ tìm kiếm nổi tiếng trên internet hiện nay. Mỗi hệ thống đều có những giải pháp lưu trữ dữ liệu riêng phụ thuộc vào giải thuật tìm kiếm của mình. Với những search engine, phải có kế hoạch cập nhật thông tin định kỳ nhất định để cập nhật sự thay đổi (những hệ thống tìm kiếm online) hay khi cập nhật tài liệu mới (những hệ thống trên CSDL có sẵn). Trong đồ án này, chúng tôi cũng lựa chọn một phương thức lưu trữ dữ liệu sẽ được trình bày chi tiết trong phần sau. PHẦN II: CƠ SỞ LÝ THUYẾT CÁC BỘ MÁY TÌM KIẾM Một số engine thông dụng Sau đây là danh sách một số search engine. Tại sao chúng được gọi là các search engine “lớn”? Đó là vì chúng được biết đến nhiều và sử dụng tốt. Với các chuyên gia web, các công cụ tìm kiếm lớn là danh sách những nơi quan trọng nhất bởi chúng phát sinh ra một lượng lớn các trang web tiềm tàng. Đối với những người tìm kiếm, các công cụ tìm kiếm phổ biến thường trả lại kết quả đáng tin cậỵ Dưới đây là danh sách các search engine. Hình 12: Giao diện tìm kiếm của Google Nguyên thủy, Google là một đề án của trường Đại học Stanford được thực hiện bởi hai sinh viên Larry Page và Sergey Brin gọi là BackRub. Đến năm 1998 thì đổi thành Google, và đồ án đó đã trở thành công ty riêng Google đặt tại khuôn viên trường đại học. Google là công cụ tìm kiếm nổi tiếng, tốt nhất hiện tại cho tìm kiếm thông tin trên web. Dịch vụ dựa vào crawler, spider cung cấp trang web với thông tin đưa ra toàn diện cùng mức độ liên quan tốt. Hình 13: Giao diện tìm kiếm Yahoo Đưa ra năm 1994, yahoo là “thư mục” cũ nhất của web, một nơi các nhà tổ chức trang web thành các thư mục. Tuy nhiên, vào tháng 10 năm 2002, yahoo chuyển sang lập danh sách dựa vào crawler cho những kết quả chính của nó. Công cụ này sử dụng công nghệ từ Google cho tới 2/2004. Hiện nay, Yahoo sử dụng công cụ tìm kiếm riêng của mình. Yahoo Directory vẫn tồn tai. Bạn sẽ chỉ ra các liên kết “danh mục” phía dưới một số các trang web liệt kê trong kết quả trả về của một tìm kiếm từ khóa. Khi được đề xuất, những trang web này dẫn bạn đến một danh sách các trang web đã được xem xét và phê chuẩn bởi một nhà biên tập. Công nghệ Alta Vista và AllTheWeb được phối hợp với kỹ thuật Inktomi, một công cụ tìm kiếm dựa trên crawler, để tạo nên một Yahoo crawler hiện nay. Vừa qua, thương vụ mua bán Yahoo với Microsoft không thành, khiến nhiều chuyên gia đánh giá, trong thời gian tới, cả 2 hãng này sẽ có bước đột phá trong công nghệ tìm kiếm và đánh giá các site. Ask Jeeves Ask Jeeves bắt đầu nổi tiếng từ năm 1998 và 1999, được biết như một công cụ tìm kiếm “ngôn ngữ tự nhiên” cho phép ta tìm kiếm bằng cách đặt câu hỏi và trả về kết quả với những gì có vẻ là trả lời đúng. Hình 14 Giao diện tìm kiếm Ask Jeeves Thực sự, công nghệ không phải là những gì làm cho Ask Jeeves thực thi tốt. Bên cạnh các bối cảnh, công vụ này tại một thời điểm có hơn 100 trình soạn thảo giám sát các log tìm kiếm. Sau đó, chúng vào trong web và định vị những site mà chúng cho là tốt nhất tương xứng với các truy vấn phổ biến nhất. All the web Hình 15: Giao diện tìm kiếm All the web Chiến lược tìm kiếm Công nghệ tìm kiếm ngữ nghĩa trên thế giới hiện nay Hầu hết các hiệu quả gần đây của các công cụ tìm kiếm dựa vào ngữ nghĩa phụ thuộc vào công nghệ xử lý ngôn ngữ tự nhiên để phân tích và hiểu câu truy vấn. Một trong những công cụ tìm kiếm đầu tiên và thông dụng nhất là Ask Jeesves. Nó liên kết những điểm mạnh của phần mềm phân tích ngôn ngữ tự nhiên, xử lý khai khoáng dữ liệu và tạo cơ sở tri thức với những phân tích theo kinh nghiệm. Người dùng có thể gõ các truy vấn bằng ngôn ngữ tự nhiên và nhận được những trả lời thỏa đáng. Một kiểu nâng cao khác của công cụ tìm kiếm Internet là Cycorp ( Cyc liên kết cơ sở tri thức lớn nhất trên thế giới với Internet. Cyc là một cơ sở tri thức bao la và đa ngữ cảnh. Với Cyc Knowledge Server, nó cho phép các site Internet thêm vào tri thức ngữ nghĩa thông dụng và phân biệt những nghĩa khác nhau của khái niệm nhập nhằng. Bàn về hiệu quả của các tìm kiếm ngữ nghĩa. Nhiều công ty lớn đang thật sự hướng đến vấn đề của tìm kiếm ngữ nghĩa, sự phát triển của Microsoft về web có lẽ phụ thuộc vào khả năng của nó để hoàn thiện công cụ tìm kiếm mà dẫn đầu là Google. Kết quả là Microsoft đưa ra một chương trình tìm kiếm mới gọi là MSNBot, nó lướt Web để xây dựng một chỉ mục các liên kết HTML và các tài liệu. MSNBot được dự định như là một công nghệ mà kết hợp các ứng dụng cho hệ điều hành Windows. Sau đó Microsoft sẽ kết nối công cụ tìm kiếm của nó với cômg MSN trong phiên bản Wíndows kế tiếp của nó nhằm dễ dàng tìm kiếm e-mail, spreadsheets và các tài liệu trên PC. Về Công nghệ tìm kiếm. Tìm kiếm ngữ nghĩa giải quyết với các khái niệm và các mối quan hệ logic. Nếu xem xét các vấn đề thực tế của tìm kiếm ngữ nghĩa, chúng ta sẽ thấy rằng, cây tìm kiếm đứng trước tình trạng thiếu logic đưa đến vấn đề chưa hoàn tất hay “ngắc ngứ” (Incompleteness and Halting Problem). Đầu tiên, về vấn đề Incompleteness, kết luận có thể được xem như là một sự suy diễn của một dãy logic gắn lại với nhau. Ở mỗi điểm, có thể có nhiều hướng khác nhau để tới một suy diễn mới. Vì vậy, để đạt hiệu quả, có một nhóm các khả năng phân nhánh để bằng cách nào đó hướng tới một giải pháp đúng, và nhóm các phân nhánh đó có thể trải ra trong các hướng mới lạ. Trong một hệ thống logic phức tạp, có một số lượng lớn các chứng cớ tiềm tàng. Một số chúng dài và không rõ ràng nếu chỉ có một chứng cơ. Được chúng minh vào những năm 1930, một số hệ thống logic đủ phức tạp vốn đã là không đầy đủ. Nói cách khác, có các câu lệnh mà không thể được chứng minh một cách logic. Luận cứ của nó cho điều đó liên quan đến một vấn đề khác, vấn đề Halting. Vấn đề Halting suy ra rằng, các giải thuật hiện nay sẽ không bao giờ kết thúc trong một câu trả lời. Khi nói về Web, chúng ta nói tới hàng triệu các sự kiện và chục ngàn luật và có thể nối kết đan lại với nhau trong những hướng phức tạp. Vì thế, không gian của các chứng cứ tiềm tàng là vô tận, và cây này theo logic sẽ trở nên vô tận. Chiến lược tìm kiếm Chiến lược tìm kiếm với thông tin trên Web ngữ nghĩa dựa trên nền tảng các công nghệ trên. Từ search engine thường được dùng rộng rãi để mô tả các công cụ tìm kiếm dựa trên crawler và các thư mục do con người cung cấp. Đây là hai loại của các search engine tập hợp các danh sách của chúng trong những cách khác nhau hoàn toàn. Search engine dựa vào crawler gồm 3 phần: 1. Bộ thu thập thông tin: 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à đệ quy nó để nhật về tất cả các tài liệu có liên quan với tài liệu này. Về bản chất, nó chỉ là một chương trình duyệt và thu thấp thông tin từ các site theo đúng giao thức web. Như trình duyệt thông thường không được gọi là robot do thiếu tính chủ động. Chúng chỉ duyệt web khi có sự tác động của con người. 2. Bộ lập chỉ mục - Index Hệ thống lập chỉ mục hay 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, trích chọn những thông tin cần thiết (thường là các từ đơn, từ ghép, cụm từ quan trọng) từ những dữ liệu mà robot thu thập được và tổ chức thành cơ sở dữ liệu riêng để có thể tìm kiếm trên đó một cách nhanh chóng, hiệu quả. Hệ thống chỉ mục là danh sách các từ khóa, chỉ rõ các từ khóa nào xuất hiện ở trang nào, địa chỉ nào. 3. Bộ tìm kiếm thông tin Search engine là cụm từ để chỉ toàn bộ hệ thống bao gồm bộ thu thập thông tin, bộ lập chỉ mục và bộ tìm kiếm thông tin. Các bộ này hoạt động liên tục từ lúc khởi động hệ thống, chúng phụ thuộc lần nhau về mặt dữ liệu và độc lập về hoạt động. Search engine tương tác với user thông qua giao diện web, có nhiệm vụ nhận và trả về những tài liệu thỏa yêu cầu của user. Nói các khác, tìm kiếm từ là tìm kiếm các trang mà những từ trong câu truy vấn xuất hiện nhiều nhất, trừ stopword (những từ quá thông dụng, cảm thán…). Một từ trong câu truy vấn càng xuất hiện nhiều trong một trang thì trang đó càng được chọn để trả về. Một trang chứa tất cả các từ trong câu truy vấn thì tốt hơn là trang không chứa hoặc chỉ một số từ. Ngày nay, hầu hết các search engine đều hỗ trợ chức năng tìm kiếm cơ bản và nâng cao, từ đơn từ ghép, cụm từ, danh từ riêng… Ngoài việc tìm chính xác theo từ khóa, các search engine còn cố gắng hiểu ý nghĩa thực sự của câu hỏi thông qua câu chữ do người dùng cung cấp. Điều này được thể hiện qua chức năng sửa lỗi chính tả. Nguyên lý hoạt động Search engine điều khiển robot đi thu thập thông tin trên mạng thông qua các hyperlink. Khi robot phát hiện ra một site mới, nó gửi tài liệu về cho server chính để tạo cơ sở dữ liệu chỉ mục phục vụ cho nhu cầu tìm kiếm thông tin. Vì thông tin trên mạng luôn thay đổi nên robot phải cập nhật liên tục các site cũ. Mật độ cập nhật phụ thuộc vào từng hệ thống search engine. Khi search engine nhận câu truy vấn, nó tiến hành phân tích, tìm trong cơ sở dữ liệu chỉ mục và trả về những tài liệu thỏa yêu cầu. XỬ LÝ VĂN BẢN TIẾNG VIỆT Từ và cấu trúc từ của tiếng Việt Định nghĩa từ Khái niệm từ nghe rất thông dụng dễ hiểu nhưng định nghĩa chính xác thế nào thì không đơn giản. Từ trước tới nay cũng có nhiều định nghĩa được đưa ra, tất cả đều đúng, nhưng chưa hoàn chỉnh. Dưới đây, tôi nêu ra một số định nghĩa về từ. Thời Hy Lạp cổ đại, trường phái ngôn ngữ Alexandre định nghĩa: “Từ là đơn vị nhỏ nhất trong chuỗi lời nói”. Theo E.Sapir: “Từ là một đoạn nhỏ nhất có ý nghĩa, hoàn toàn có khả năng độc lập và bản thân có thể làm thành câu tối giản. Còn với những nhà ngôn ngữ học tiếng Việt, thì theo Lê Văn Lý: “Từ là một tín hiệu ngữ âm có thể cấu tao bằng một âm vị hay sự kết hợp với âm vị, mà sự phát âm chỉ tiến hành trong một lần, hoặc là một âm tiết mà chữ viết biểu thị bằng một đơn vị tách rời có thể hiểu được.” Theo Nguyễn Kim Thản thì “Từ là đơn vị cơ bản của ngôn ngữ, có thể tách khỏi các đơn vị khác của lời nói để vận dụng một cách độc lập và là một khối hoàn chỉnh về mặt ý nghĩa và cấu tạo”. Quan niệm của ông về “đơn vị cơ bản” là những đơn vị có số lượng hữu hạn để thông báo, trao đổi tư tương cho nhau. Đơn vị này phải có ý nghĩa, và khi sử dụng, người dùng phải có ý thức về nó. Chính vì thế, từ không thể là câu, và không thể là âm tiết (vì nhiều khi âm tiết không có nghĩa và khi sử dụng, người dùng không ý thức về nó). Cấu trúc từ tiếng Việt Từ của tiếng Việt không giống với những ngôn ngữ phương Tây khác là không thể tách để xác định từ loại. Từ trong tài liệu tiếng Việt có thể là từ đơn (1 từ) , từ ghép. Theo như thống kê trên trang thì độ dài của một từ tiếng Việt được thể hiệnt trong bảng: Độ dài của từ Tần số Tỉ lệ % 1 8933 12.2 2 48995 67.1 3 5727 7.9 4 7040 9.7 ≥ 5 2301 3.1 Tổng cộng 72994 100 Table 1: : Tần suất xuất hiện độ dài từ tiếng Việt trên trang Vdict.com Các phương pháp tách từ tiếng Việt đã được nghiên cứu Nguyên lý thống kê dựa vào Internet Thông qua các search engine thương mại, chúng ta có thể rút trích những thông tin thống kê hữu ích từ Internet. Đó là tần số tài liệu (document frequency – df), số lượng các tài liệu đã được lập chỉ mục có chứa từ cần xét. Ta chuẩn hóa giá trị df bằng cách chia cho một hằng số MAX (là số lượng các tài liệu tiếng Việt đã được lập chỉ mục) để xấp xỉ xác suất xuất hiện của một từ trên Internet. Trên thực tế, chúng ta khó có thể biết được chính xác số lượng các tài liệu tiếng Việt đã được lập chỉ mục, do đó, thông qua thực nghiệm1 giá trị df của các từ thông dụng, chúng tôi chọn giá trị MAX là 109. Tiếng Việt df có 21.3 × 106 của 20.4 × 106 một 14.4 × 106 Table 2: Tần số tài liệu của một số từ thông dụng trong tiếng Việt Do từ tiếng Việt gồm một (số) tiếng liên tiếp nhau, ta cần độ đo thông kê mức độ liên kết giữa các tiếng. Mutual information -MI là một khái niệm quan trọng trong lý thuyết thông tin, được dùng trong xử lý ngôn ngữ tự nhiên để thể hiện quan hệ giữa hai từ cụ thể x và y (Church et al [3]): Tuy nhiên, chúng tôi không chỉ xét các cặp tiếng mà còn xét nhóm n tiếng (n-gram). Tương tự Chien et al [3], chúng tôi mở rộng công thức tính MI của bigram cho n-gram: Với cw là chuỗi gồm n tiếng (cw = s1s2…sn), lw và rw là hai chuỗi con dài nhất (n-1) của cw (lw = s1s2…sn-1 và rw = s2s3…sn). Nếu giá trị MI(cw) lớn thì lw và rw có khuynh hướng cùng xuất hiện chung trong tài liệu trên Internet (tức là cw có khả năng cao là từ ghép). Ví dụ: xét chuỗi “đại học khoa học tự nhiên”, ta so sánh khả năng chuỗi “khoa học tự nhiên” hay “học khoa học tự” là từ ghép. Ta thấy rằng “khoa học tự nhiên” có giá trị MI lớn hơn hẳn MI của “học khoa học tự” (không có ý nghĩa). Chuỗi Wf MI khoa học tự nhiên 39200 0.92 khoa học tự 41800 học tự nhiên 39900 học khoa học tự 14900 0.27 học khoa học 28600 Table 3: Ví dụ về MI của n-gram Trong phần tiếp theo, tôi sẽ giới thiệu hướng tiếp cận bằng giải thuật di truyền để xác định MI tối ưu toàn cục, tức là cách tách từ hợp lý nhất của câu Giải thuật di truyền Với mỗi câu, chúng ta sẽ xác định cách tách từ hợp lý nhất. Tuy nhiên, không gian tìm kiếm sẽ rất lớn do có nhiều cách tổ hợp các tiếng thành từ. Dựa vào nguyên lý tiến hóa và di truyền, giải thuật di truyền thích hợp cho việc xác định (xấp xỉ) các lời giải tối ưu hóa toàn cục trong không gian tìm kiếm rất lớn thay vì các lời giải tối ưu cục bộ (Michalewicz, [10]). Giải thuật di truyền sẽ tiến hóa một quần thể qua nhiều thế hệ nhằm tối ưu hóa toàn cục thông quá quá trình chọn lọc, lai, biến dị và tái sinh. Chất lượng của mỗi cá thể trong quần thể được xác định bằng hàm thích nghi và qua mỗi thế hệ, chúng ta sẽ chọn lại N cá thể tốt nhất sau khi thực hiện quá trình lai, biến dị và tái sinh. Giải thuật di truyền áp dụng cho bài toán tách từ tiếng Việt được tóm tắt như sau: Mục tiêu: Xét văn bản t gồm n tiếng t=s1s2…sn. Mục tiêu của quá trình GA là xác định những cách tách hợp lý nhất văn bản t thành m đọan t=w1w2…wm với wk=si…sj (1 ≤ k≤ m, 1≤ i, j≤ n) có thể là từ đơn hay từ phức. Cách biểu diễn: Quần thể (pop) là tập hợp các cá thể (id) được biểu diễn bằng xâu nhị phân. Mỗi bit tương ứng với một tiếng. Vậy, một từ sẽ gồm các bit giống nhau liên tiếp. Ví dụ: học sinh học sinh học 0 0 1 0 0 học sinh # học # sinh học w1 w2 w3 Khởi tạo quần thể: Ở bước này, ta khởi gán các tham số như số lượng thế hệ, kích thước quần thể, tỉ lệ lai, tỉ lệ biến dị và tỉ lệ tái sinh. Các cá thể ban đầu của quần thể được phát sinh ngẫu nhiên. Tuy nhiên, chúng tôi áp dụng một số ràng buộc nhằm tối ưu hóa các chuỗi ngẫu nhiên được phát sinh ra. Dưới đây là thống kê rút ra từ từđiển trực tuyến chưa 72994 từ và ngữ2 Thống kê theo độ dài của từ trong từ điển Độ dài của từ Tần số Tỉ lệ % 1 8933 12.2 2 48995 67.1 3 5727 7.9 4 7040 9.7 ≥ 5 2301 3.1 Tổng cộng 72994 100 Do hiện chưa có từ điển chuẩn dành cho xử lý ngôn ngữ nên chúng tôi quyết định chọn thống kê dựa trên một từ điển thông dụng. Dựa vào số liệu thống kê, ta thấy rằng có trên 67% các từ trong từđiển có độ dài là 2 tiếng, khoảng 30% là từ đơn hay từ gồm 3-4 tiếng. Các từ dài hơn chỉ chiếm khoảng 3% trong từđiển, trong đó thường là các thành ngữ. Phép lai: Chúng tôi áp dụng thao tác lai 1-điểm chuẩn trên hai xâu bit. Với cặp cá thể id1 id2, hai cá thể con được tạo ra bằng cách lấy phần đầu của id1 nối vào phần sau của id2 và ngược lại. Tuy nhiên, nếu cá thể con vi phạm các điều kiện giới hạn về kích thước (mỗi đoạn wk có kích thước tối đa là 4), ta sẽ chuẩn hóa cá thể này bằng cách đảo các bit gây ra vi phạm ở cuối đoạn này. Phép biến dị: Thay vì dùng phép biến dị đảo bit ngẫu nhiên, chúng tôi chỉ đảo các bit ở biên của mỗi phân đoạn. Tương tự phép lai, ta sẽ chuẩn hóa các cá thể để thỏa điều kiện giới hạn kích thước của phân đoạn. Tái sinh: Sau khi thực hiện phép lai và biến dị, ta chọn lại một số cá thể ở thế hệ trước (theo tỉ lệ đã chọn) đưa vào quần thể mới. Phép chọn: Ở mỗi thế hệ, chúng ta chỉ chọn giữ lại N cá thể tốt nhất. Hàm thích nghi của mỗi cá thể id được xác định như sau: với id=w1w2…wm là một cá thể trong quần thể pop = {id1, …, idN} Hội tụ: Quá trình tiến hóa nhằm cải thiện độ thích nghi của các cá thể trong quần thể, tức là cải thiện chất lượng của việc tách từ. Do đó, chúng ta sẽ dừng quá trình tiến hóa nếu độ thích nghi của thế hệ sau không cao hơn thế hệ trước, hoặc số lượng thế hệ đạt ngưỡng cho trước. Giải thuật dùng trong bài toán sẽ dựa vào bộ từ điển ngôn ngữ tiếng Việt cho sẵn trước để xác định các từ loại. Giải thuật chúng tôi dùng sẽ được trình bày phần sau cố gắng phán đoán chính xác nhất ý nghĩa từ loại. Thuật toán, otomat tách từ Trong phần này, tôi chỉ giới thiệu mang tính lý thuyết các giải thuật, các otomat tách từ tiếng Việt đã được nghiên cứu. 1. Xây dựng ôtômát âm tiết đoán nhận tất cả các âm tiết tiếng Việt 2. Xây dựng ôtômát từ vựng đoán nhận tất cả các từ vựng tiếng Việt. 3. Dựa trên các ôtômát nêu trên, xây dựng đồ thị tương ứng với câu cần phân tích và sử dụng thuật toán tìm kiếm trên đồ thị để liệt kê các cách phân tích có thể. Bảng chữ cái của ôtômát âm tiết là bảng chữ cái tiếng Việt, mỗi cung chuyển được ghi trên đó một ký tự. Ví dụ, với ba âm tiết phương, pháp, trình ta sẽ có ôtômát đoán nhận âm tiết như Hình 1. Hình 16: Xây dựng ôtômát âm tiết Thuật toán xây dựng ôtômát âm tiết Input: Từ điển âm tiết Output: Ôtômát âm tiết. Thuật toán: 1. Lập trạng thái khởi đầu ; 2. Vòng lặp đọc cho tới khi hết tệp dữ liệu, lấy ra từng âm tiết. Gọi các ký tự của âm tiết đó là a. b. Vòng lặp trong khi () i. Lấy ra ký tự ; ii. Tìm trong các cung chuyển từ trạng thái cung trên đó ghi ký tự . Nếu có cung như thế: 1. 2. iii. Nếu không có cung ( nào như thế thì thoát khỏi vòng lặp b. c. Với từ i đến i. Tạo mới trạng thái q, ghi nhận là trạng thái không kết; ii. Thêm cung chuyển trên đó ghi ký tự ; iii. d. Ghi nhận q là trạng thái kết; Ôtômát từ vựng được xây dựng tương tự, với điểm khác như sau: thay vì ghi trên mỗi cung chuyển một âm tiết, ta ghi số hiệu của trạng thái (kết) của ôtômát âm tiết tại đó đoán nhận mỗi âm tiết của từ nhằm giảm kích thước của ôtômát từ vựng. Ví dụ, với hai từ phương pháp và phương trình, giả sử khi đưa lần lượt các âm tiết phương, pháp, trình qua ôtômát âm tiết, ta đến được các trạng thái kết ghi các số n1, n2, n3 thì trên các cung chuyển tương ứng ta ghi các số n1, n2, n3 (Hình 2). Hình 17: Xây dựng ôtômát từ vựng Thuật toán xây dựng ôtômát từ vựng Input: Từ điển từ vựng, ôtômát âm tiết Output: Ôtômát từ vựng. Thuật toán: 1. Lập trạng thái khởi đầu ; 2. Vòng lặp đọc cho tới khi hết tệp dữ liệu, lấy ra từng mục từ word. Gọi các âm tiết của word là ; 3. Sử dụng ôtômát âm tiết để đoán nhận các âm tiết trên, được các số hiệu của trạng thái (kết) tương ứng là a. b. Vòng lặp trong khi ( ) i. Lấy ra số ; ii. Tìm trong các cung chuyển từ trạng thái cung trên đó ghi số . Nếu có cung như thế 1. 2. iii. Nếu không có cung ( nào như thế thì thoát khỏi vòng lặp b. c. Với từ i đến i. Tạo mới trạng thái q, ghi nhận là trạng thái không kết; ii. Thêm cung chuyển ( t