Thuật toán tìm kiếm string gần đúng như google

Chia sẻ: Lê Hùng Quốc | Ngày: | Loại File: DOC | Số trang:6

Thêm vào BST

Báo xấu

903
lượt xem 56
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Tài liệu về Thủ toán tìm kiếm chuỗi gần đúng trong visual basic. Mời các bạn cùng tham khảo thực hành.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Thuật toán tìm kiếm string gần đúng như google

Thuật toán tìm kiếm string gần đúng gửi bởi tienlbhoc » T.Năm 10/04/2008 2:39 pm mới chế cái code tìm kiếm gần đúng , nhờ mọi người cho ý kiến cái : Tư tưởng như sau: +Đầu tiên kiểm tra độ dài string so sánh :ít hay hơn 30% thì loại +Tiếp là so sánh từng ký tự của 2 string nếu không bằng nhau thì so sánh các từ lân cận tiếp theo của cả 2 string Trong khoảng sai số nếu có , thì chỉnh lại vị trí i,j là chỉ số của 2 string đó, cái này sẽ kiểm tra các lỗi thừa hay thiếu từ , nếu có thì số lỗi là số ký tự phải chỉnh lại vị trí i,j .còn nếu không thì cho lỗi là 1 , đọc ký tự kế tiếp +Cuối cùng , khi 1 trong 2 string đã đi hết thì còn mẩu đuôi ta làm : loi += s.Length - i + s1.Length - j; tức là nếu 1 string còn thừa thì cho mẩu đó là lỗi cộng vào nếu số lỗi (s.Length + saiSo)) 13. return false; 14. i = j = loi = 0; 15. while (i < s.Length && j < s1.Length) 16. { 17. if (s[i] != s1[j]) 18. { 19. loi++; 20. for (k = 1; k
24. i += k; 25. break; 26. } 27. else if ((j + k < s1.Length) && s[i] == s1[j + k]) 28. { 29. j += k; 30. break; 31. } 32. } 33. } 34. i++; 35. j++; 36. } 37. loi += s.Length - i + s1.Length - j; 38. if (loi
Còn đây là kết quả: Sửa lần cuối bởi tienlbhoc vào ngày T.Năm 18/09/2008 2:17 pm với 1 lần sửa. Diễn đàn và blog phần mềm tự làm : http://my.opera.com/DienDanTienlbhoc/forums/ http://my.opera.com/tienlbhoc/blog/ tienlbhoc Thành viên tâm huyết Bài viết: 410 Ngày tham gia: T.Bảy 14/07/2007 10:06 pm Đến từ: Hà Nội Đầu trang Re: Thuật toán tìm kiếm string gần đúng gửi bởi ngaymaikhongtan » T.Bảy 12/04/2008 7:23 am
Ý tưởng cũng khá hay, nhưng minh vẩn không hĩu chổ này, bạn giải thích cho mình rỏ nhe, tai sao bạn chọn kiểm tra độ dài string so sánh :ít hay hơn 30% thì loại, tại sao bạn lại chọn mức la 30% vậy! welcome to http://gocnhinviet.com ngaymaikhongtan Thành viên chính thức Bài viết: 39 Ngày tham gia: T.Bảy 29/03/2008 12:05 pm Đến từ: Cà Mau • Tài khoản Yahoo Đầu trang Re: Thuật toán tìm kiếm string gần đúng gửi bởi tienlbhoc » T.Bảy 12/04/2008 8:03 am thuật toán trên mình sửa rồi , cái đoạn tìm lân cận chỉ cho mặc định lỗi ++ thôi (vì thế kết quả sẽ rộng hơn). Còn vì sao là 30% vì 20% mình thử thấy hơi ít 40% thấy hơi nhiều , con số này tuỳ theo thực nghiệm mà chỉnh thôi . Còn vì sao mà độ dài lớn hơn hoặc nhỏ hơn 30% vì ví dụ a so sánh với application , thì dài thế này có cần phải so sánh nữa không hả , làm chậm chương trình. Mã: Chọn tất cả 1. class ApproximatString 2. { 3. string s; 4. int i, j, k, loi, saiSo; 5. public ApproximatString(string nhap) 6. { 7. s = nhap; 8. saiSo = (int)Math.Round(s.Length * 0.3); 9. } 10. public bool SoSanh(string s1) 11. { 12. if (s1.Length < (s.Length - saiSo) || s1.Length > (s.Length + saiSo))
13. return false; 14. i = j = loi = 0; 15. while (i < s.Length && j < s1.Length) 16. { 17. if (s[i] != s1[j]) 18. { 19. loi++; 20. for (k = 1; k
Re: Thuật toán tìm kiếm string gần đúng gửi bởi giongto35 » T.Bảy 12/04/2008 10:30 am Hay thật . Tìm chuẩn quá , hết chỗ chê , _______________________________________________________________________ _________________________ . . . . . . . . . . . . .. . giongto35 Advance Member Bài viết: 197 Ngày tham gia: T.Năm 19/04/2007 10:17 am Đến từ: Đà Nẵng City • Tài khoản Yahoo Đầu trang Re: Thuật toán tìm kiếm string gần đúng gửi bởi vinhphuoc91 » T.Bảy 12/04/2008 12:20 pm Cái này ứng dụng từ điển là ok nhất, hehe phải nhanh chóng paste nó vào chương trình của mình thôi Cảm ơn tienlbhoc nhiều nhá. [b][color=#FF0000]Xin lỗi, tạm thời không thể online thường xuyên được, dạo này có việc bận quá :( [/color][/b] vinhphuoc91 Advance Member Bài viết: 146 Ngày tham gia: T.Tư 26/03/2008 5:52 pm Đến từ: Phú Yên • Tài khoản Yahoo Đầu trang Re: Thuật toán tìm kiếm string gần đúng