Thuật toán dùng cho từ điển thế thôi , ngoài ra còn có thể dùng để làm kiểm tra chính tả
Tôi xin giới thiệu với các bạn tư tưởng cả thuật toán 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ì lỗi cộng thêm 1, 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ừ , đọ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 <=30% thì là đạt , không thì không đạt , đơn giản vậy thôi
Lớp xử lý
Từ tư tưởng được trình bày ở trên, tôi xây dựng lớp xử lý.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 |
class ApproximatString { string s; int i, j, k, loi, saiSo; public ApproximatString(string nhap) { s = nhap; saiSo = (int)Math.Round(s.Length * 0.3); } public bool SoSanh(string s1) { if (s1.Length < (s.Length – saiSo) || s1.Length > (s.Length + saiSo)) return false; i = j = loi = 0; while (i < s.Length && j < s1.Length) { if (s[i] != s1[j]) { loi++; for (k = 1; k <= saiSo; k++) { if ((i + k < s.Length) && s[i + k] == s1[j]) { i += k; //loi += k – 1; break; } else if ((j + k < s1.Length) && s[i] == s1[j + k]) { j += k; //loi += k – 1; break; } } } i++; j++; } loi += s.Length – i + s1.Length – j; if (loi <= saiSo) return true; else return false; } } |
Kết luận
Nếu ai muốn biết nó hoạt động thế nào thì down từ điển super power dict phần tìm kiếm nâng cao về dùng thử nhé.
(st)
