Tìm kiếm
Đang tải khung tìm kiếm
Kết quả 1 đến 1 của 1

    THẠC SĨ Nghiên cứu phương pháp so sánh xâu xấp xỉ và ứng dụng

    D
    dream dream Đang Ngoại tuyến (18495 tài liệu)
    .:: Cộng Tác Viên ::.
  1. Gửi tài liệu
  2. Bình luận
  3. Chia sẻ
  4. Thông tin
  5. Công cụ
  6. Nghiên cứu phương pháp so sánh xâu xấp xỉ và ứng dụng

    Số hóa bởi Trung tâm Học liệu - ĐHTN http://www.lrc-tnu.edu.vn/

    iii
    LỜI CẢM ƠN

    Trong thời gian nghiên cứu và thực hiện luận văn này, em đã may mắn được
    các thầy cô chỉ bảo, dìu dắt và được gia đình, bạn bè quan tâm, động viên. Em xin
    bày tỏ lời cảm ơn sâu sắc nhất tới tất cả các tập thể, cá nhân đã tạo điều kiện giúp
    đỡ em trong suốt quá trình thực hiện nghiên cứu luận văn này.
    Trước hết em xin trân trọng cảm ơn Ban giám hiệu trường Đại học Công
    nghệ thông tin và truyền thông, Phòng Đào tạo và Khoa Sau đại học của nhà
    trường cùng các thầy cô giáo, những người đã trang bị kiến thức cho em trong
    suốt quá trình học tập.
    Với lòng biết ơn chân thành và sâu sắc nhất, em xin trân trọng cảm ơn thầy
    giáo – PGS.TS Nguyễn Trí Thành, giảng viên khoa Công nghệ thông tin – Trường
    Đại học Công nghệ - Đại học Quốc gia Hà Nội; người thầy đã trực tiếp chỉ bảo,
    hướng dẫn khoa học và giúp đỡ em trong suốt quá trình nghiên cứu, hoàn thành
    luận văn này.
    Xin chân thành cảm ơn tất cả các bạn bè, đồng nghiệp đã động viên, giúp đỡ
    nhiệt tình và đóng góp nhiều ý kiến quý báu để em hoàn thành luận văn này.
    Do thời gian nghiên cứu có hạn, luận văn của em chắc hẳn không thể tránh
    khỏi những sơ suất, thiếu sót, em rất mong nhận được sự đóng góp của các thầy cô
    giáo cùng toàn thể bạn đọc.
    Xin trân trọng cảm ơn!
    Thái Nguyên, ngày 18 tháng 8 năm 2015
    TÁC GIẢ LUẬN VĂN


    Nguyễn Thanh Hùng


    Số hóa bởi Trung tâm Học liệu - ĐHTN http://www.lrc-tnu.edu.vn/

    iv
    MỤC LỤC
    MỞ ĐẦU 1
    CHƯƠNG 1: GIỚI THIỆU CHUNG VỀ XẤP XỈ 4
    1.1 Khái niệm xấp xỉ 4
    1.1.1 Đối sánh chuỗi 4
    1.1.2 Đối sánh chính xác 5
    1.2.3 Đối sánh chuỗi xấp xỉ 6
    1.2 Nội dung và ý nghĩa ứng dụng 10
    1.2.1 Nội dung . 10
    1.2.2 Ý nghĩa ứng dụng 12
    1.3 Kết luận chương . 12
    CHƯƠNG 2: TÌM HIỂU MỘT SỐ THUẬT TOÁN . 14
    2.1 Thuật toán của Galil-Park 14
    2.2 Thuật toán của Ukkonen-Wood và một số cải tiến . 18
    2.3 Thuật toán của Boyer-Moore 21
    2.4 Thuật toán đối sánh xâu vòng tròn gần đúng 29
    2.5 Kết luận chương . 36
    CHƯƠNG 3: THỰC NGHIỆM VÀ ỨNG DỤNG 38
    3.1 Chương trình ứng dụng asmf-master . 38
    3.1.1 Giới thiệu chung 38
    3.1.2 Các hàm asmf-master 39
    3.1.3 Thiết lập môi trường cài đặt và chạy ứng dụng 40
    3.1.4 Thực nghiệm với chương trình asmf-master 41
    3.2 Thực nghiệm, ứng dụng trong bài toán sửa lỗi chính tả . 43
    3.2.1 Giới thiệu về ứng dụng sửa lỗi chính tả 43
    3.2.2 Thực nghiệm ứng dụng 46
    3.3 Thực nghiệm, ứng dụng trong bài toán gợi ý truy vấn từ điển 47
    3.3.1 Giới thiệu về ứng dụng gợi ý truy vấn từ điển . 47
    3.3.2 Thực nghiệm ứng dụng 48
    3.4 Nhận xét 51
    3.5 Kết luận chương . 52
    KẾT LUẬN . 54
    TÀI LIỆU THAM KHẢO . 55


    Số hóa bởi Trung tâm Học liệu - ĐHTN http://www.lrc-tnu.edu.vn/

    v

    DANH MỤC HÌNH VẼ

    Hình 1.1: Cây hậu tố cho S= "xabxac" . 10
    Hình 1.2: Hoạt động cơ bản của thuật toán Boyer-Moore 11
    Hình 2.1: cây hậu tố cho S= "xabxac" 18
    Hình 2.2: Cây hậu tố cho chuỗi "xabxac$" . 18
    Hình 2.3: Cây bao hàm cho chuỗi "xabxa$" . 19
    Hình 2.4: Cây bao chùm cho chuỗi axabxb 20
    Hình 2.5 : Cây biểu diễn hậu tố cho chuỗi 21
    Hình 3.1: Giao diện ứng dụng sửa lỗi chính tả . 45
    Hình 3.2: Sửa từ cho từ sai 46
    Hình 3.3: Thực nghiệm với từ khóa 46
    Hình 3.4: Thực nghiệm với từ "Cổng" 47
    Hình 3.5: Thực nghiệm với từ "Tỏa" 47
    Hình 3.6: Hệ thống gợi ý từ điển 47
    Hình 3.7: Thực nghiệm hệ thống gợi ý với từ khóa "Gợi" . 49
    Hình 3.8: Thực nghiệm với từ khóa "Tổng" . 50
    Hình 3.9: thực nghiệm với từ khóa "Trường" . 50
    Hình 3.10: Thực nghiệm với từ khóa "Việt" . 51



    Số hóa bởi Trung tâm Học liệu - ĐHTN http://www.lrc-tnu.edu.vn/

    1
    MỞ ĐẦU

    1. Lý do chọn đề tài
    Kiểu dữ liệu văn bản (Text) là dạng trình bày thông tin gần gũi nhất với con
    người, vì vậy, đây cũng là dạng trình bày thông tin số rất phổ biến. Chính vì lẽ đó,
    bài toán tìm kiếm văn bản (text searching) là một trong những bài toán quan trọng
    nhất trong hoạt động tìm kiếm thông tin của con người. Trong thời đại ngày nay,
    văn bản số hóa đang tăng trưởng "bùng nổ" trong các cơ sở dữ liệu trên Internet,
    dung lượng tăng gấp đôi sau mỗi chu kỳ 18 tháng. Trong bối cảnh đó, vấn đề tìm
    kiếm văn bản một cách tự động đã rất quan trọng thì lại ngày càng quan trọng hơn.
    Dạng phổ biến nhất của bài toán tìm kiếm văn bản là: Cho trước nguồn tìm
    kiếm là một tập D các văn bản (hoặc là cơ sở dữ liệu văn bản, hoặc là tập các văn
    bản trên Internet). Cho một câu hỏi dạng văn bản q (thường là một từ, một xâu văn
    bản ngắn), hãy tìm tất cả các văn bản thuộc D mà có chứa q. Trong nhiều trường
    hợp (chẳng hạn, tìm kiếm thông qua máy tìm kiếm) thì q còn được gọi là "truy vấn"
    và bài toán còn có tên gọi là "tìm kiếm theo truy vấn". Để tìm được các văn bản có
    chứa văn bản truy vấn q, hệ thống tìm kiếm cần phải kiểm tra văn bản truy vấn q có
    là một xâu con của các văn bản thuộc tập D hay không (sánh mẫu) và đưa ra các
    văn đáp đáp ứng. Trong nhiều trường hợp, bài toán còn đòi hỏi tìm tất cả các vị trí
    của các xâu con trong văn bản trùng với q. Đồng thời, điều kiện tìm kiếm có thể
    được làm "xấp xỉ" theo nghĩa văn bản kết quả có thể không cần chứa q (không cần
    có một xâu con của văn bản trùng một cách hoàn toàn chính xác với q) mà chỉ cần
    "liên quan" tới q (có xâu con trong văn bản "xấp xỉ" q). Có thể thấy, các máy tìm
    kiếm sử dụng cả cơ chế tìm kiếm xấp xỉ khi mà văn bản kết quả tìm kiếm không
    chứa hoàn toàn chính xác văn bản truy vấn [1].
    Thời gian gần đây, bài toán sánh mẫu càng trở nên quan trọng và được quan
    tâm nhiều do sự tăng trưởng nhanh chóng của các hệ thống tìm kiếm thông tin và
    các hệ thống sinh- tin học. Một lý do nữa, con người ngày nay không chỉ đối mặt


    Số hóa bởi Trung tâm Học liệu - ĐHTN http://www.lrc-tnu.edu.vn/

    2
    với một lượng thông tin khổng lồ mà còn đòi hỏi những yêu cầu tìm kiếm ngày
    càng phức tạp. Các mẫu đưa vào không chỉ đơn thuần là một xâu ký tự mà còn có
    thể chứa các ký tự thay thế, các khoảng trống và các biểu thức chính quy. Sự “tìm
    thấy” không đơn giản là xuất hiện chính xác mẫu trong văn bản mà còn cho phép
    “một xấp xỉ” giữa mẫu và xuất hiện của nó trong văn bản. Từ đó, bên cạnh vấn đề
    kinh điển là “tìm kiếm chính xác”, nảy sinh một hướng nghiên cứu là "sánh mẫu
    xấp xỉ / tìm kiếm xấp xỉ” (approximate matching / approximate searching) [2].
    So sánh thực nghiệm của thời gian chạy của thuật toán xấp xỉ chuỗi kết hợp
    cho k vấn đề khác nhau được trình bày. Với một chuỗi mô hình, một chuỗi văn bản,
    và một số nguyên k, nhiệm vụ là để tìm tất cả các lần xuất hiện gần đúng của mô
    hình trong văn bản với ít nhất k khác biệt (chèn thêm, xóa, thay đổi). Xem xét bảy
    thuật toán dựa trên phương pháp tiếp cận khác nhau bao gồm lập trình năng động,
    Boyer-Moore chuỗi kết hợp, hậu tố bị tự động, và sự phân bố của các nhân vật. Nó
    chỉ ra rằng không ai trong số các thuật toán là tốt nhất cho tất cả các giá trị của các
    thông số vấn đề, và sự khác biệt tốc độ giữa các phương pháp có thể là đáng kể.
    Xuất phát từ những yêu cầu và lý do trên, em lựa chọn đề tài luận văn là:
    "Nghiên cứu phương pháp so sánh xâu xấp xỉ và ứng dụng".
    Luận văn này định hướng nghiên cứu một số thuật toán so sánh mẫu xâu xấp
    xỉ, tập trung vào một số thuật toán của Galil Park, Ukkonen Wood Boyer-Moore,
    thuật toán xâu vòng tròn gần đúng với độ phức tạp là hàm tuyến tính và tiến hành
    thực nghiệm ứng dụng.
    2. Mục tiêu nghiên cứu
    - Nghiên cứu để hiểu các khái niệm và đặc trưng liên quan tới bài toán so
    sánh xâu xấp xỉ.
    - Nghiên cứu các lớp thuật toán so sánh xâu xấp xỉ.
    - Khảo sát, phân tích một số thuật toán và các bước tiến hóa và hiệu suất
    (nghiên cứu khả năng về ý tưởng cải tiến thuật toán).

    Số hóa bởi Trung tâm Học liệu - ĐHTN http://www.lrc-tnu.edu.vn/

    3
    - Khảo sát chương trình ứng dụng asmf-master để có thể khai thác vào
    trường hợp của luận văn.
    - Cài đặt thử nghiệm tìm vị trí các câu hỏi trong nội dung, kết quả trả về của
    một máy tìm kiếm.
    3. Đối tượng và phạm vi nghiên cứu
    Nghiên cứu một số thuật toán so sánh xâu xấp xỉ miền dữ liệu văn bản. Tiếp
    đó, luận văn thi hành một số thuật toán trong họ thuật toán nói trên, cài đặt thử
    nghiệm tìm kiếm.
    4. Ý nghĩa thực tiễn của luận văn
    Nghiên cứu thuật toán so sánh xâu xấp xỉ và ứng dụng của chúng vào hệ
    thống tìm kiếm văn bản. Vì vậy, nó có ý nghĩa rất lớn trong lý thuyết và thực tiễn.
    5. Phương pháp nghiên cứu
    - Phương pháp nghiên cứu tài liệu, phân tích, tổng hợp.
    - Phương pháp thực nghiệm và đối chứng qua chương trình thử nghiệm.

    Xem Thêm: Nghiên cứu phương pháp so sánh xâu xấp xỉ và ứng dụng
    Nội dung trên chỉ thể hiện một phần hoặc nhiều phần trích dẫn. Để có thể xem đầy đủ, chi tiết và đúng định dạng tài liệu, bạn vui lòng tải tài liệu. Hy vọng tài liệu Nghiên cứu phương pháp so sánh xâu xấp xỉ và ứng dụng sẽ giúp ích cho bạn.
    #1
  7. Đang tải dữ liệu...

    Chia sẻ link hay nhận ngay tiền thưởng
    Vui lòng Tải xuống để xem tài liệu đầy đủ.

    Gửi bình luận

    ♥ Tải tài liệu

social Thư Viện Tài Liệu

Từ khóa được tìm kiếm

Nobody landed on this page from a search engine, yet!

Quyền viết bài

  • Bạn Không thể gửi Chủ đề mới
  • Bạn Không thể Gửi trả lời
  • Bạn Không thể Gửi file đính kèm
  • Bạn Không thể Sửa bài viết của mình
  •  
DMCA.com Protection Status