Tiếp tục series, hôm nay chúng ta sẽ sử dụng giải thuật tìm kiếm nhị phân (Binary Search) để chuyển đổi chuỗi TCVN3 sang UNICODE. Trước khi đi vào giải thuật ta tìm hiểu chút về mấy cái mã này nhé!
Mã TCVN3 là bảng mã theo chuẩn cũ của Việt Nam, sử dụng 1 byte để mã hóa ký tự. Kiểu mã này vẫn còn được hỗ trợ trong công cụ UniKey, các bạn có thể mở lên là thấy ngay. Một điểm hạn chế của TCVN3 là khi gửi văn bản viết bằng TCVN3 sang máy khác không cài font này thì không thể đọc được văn bản đó.
Mã Unicode là bảng mã chung của thế giới, sử dụng 2 byte để mã hóa các kỹ tứ (như vậy sẽ có nhiều ký tự hơn) và khắc phục được các hạn chế của TCVN3.
Hiện nay, thi thoảng ta vẫn gặp các văn bản viết bằng font TCVN3 rất khó dịch, là dân lập trình chúng ta cùng nhau viết một tool nho nhỏ chuyển chúng về unicode cho dễ đọc nhé!
Ý tưởng của bài toán là lấy mã Unicode của các ký tự font TCVN3 và tương ứng với nó là mã Unicode của ký tự font Unicode để hoán đổi cho nhau.
Unicode À Á Ã Ạ Ả È É Ẹ Ẻ Ẽ Ì Í Ĩ Ỉ Ị Ò Ó Õ Ọ Ỏ Ù Ú Ũ Ụ Ủ Ý Ỳ Ỵ Ỷ Ỹ Ă Ắ Ằ Ẳ Ẵ Ặ Â Ấ Ầ Ẩ Ẫ Ậ Ê Ế Ề Ể Ễ Ệ Ô Ố Ồ Ổ Ỗ Ộ Ơ Ớ Ờ Ở Ỡ Ợ Ư Ứ Ừ Ử Ữ Ự Đ ă â ê ô ơ ư đ à ả ã á ạ ằ ẳ ẵ ắ ặ ầ ẩ ẫ ấ ậ è ẻ ẽ é ẹ ề ể ễ ế ệ ì ỉ ĩ í ị ò ỏ õ ó ọ ồ ổ ỗ ố ộ ờ ở ỡ ớ ợ ù ủ ũ ú ụ ừ ử ữ ứ ự ỳ ỷ ỹ ý ỵ
192 193 195 7840 7842 200 201 7864 7866 7868 204 205 296 7880 7882 210 211 213 7884 7886 217 218 360 7908 7910 221 7922 7924 7926 7928 258 7854 7856 7858 7860 7862 194 7844 7846 7848 7850 7852 202 7870 7872 7874 7876 7878 212 7888 7890 7892 7894 7896 416 7898 7900 7902 7904 7906 431 7912 7914 7916 7918 7920 272 259 226 234 244 417 432 273 224 7843 227 225 7841 7857 7859 7861 7855 7863 7847 7849 7851 7845 7853 232 7867 7869 233 7865 7873 7875 7877 7871 7879 236 7881 297 237 7883 242 7887 245 243 7885 7891 7893 7895 7889 7897 7901 7903 7905 7899 7907 249 7911 361 250 7909 7915 7917 7919 7913 7921 7923 7927 7929 253 7925
TCVN3 Aµ A¸ A· A¹ A¶ EÌ EÐ EÑ EÎ EÏ I× IÝ IÜ IØ IÞ Oß Oã Oâ Oä Oá Uï Uó Uò Uô Uñ Yý Yú Yþ Yû Yü ¡ ¡¾ ¡» ¡¼ ¡½ ¡Æ ¢ ¢Ê ¢Ç ¢È ¢É ¢Ë £ £Õ £Ò £Ó £Ô £Ö ¤ ¤è ¤å ¤æ ¤ç ¤é ¥ ¥í ¥ê ¥ë ¥ì ¥î ¦ ¦ø ¦õ ¦ö ¦÷ ¦ù § ¨ © ª « ¬ ® µ ¶ · ¸ ¹ » ¼ ½ ¾ Æ Ç È É Ê Ë Ì Î Ï Ð Ñ Ò Ó Ô Õ Ö × Ø Ü Ý Þ ß á â ã ä å æ ç è é ê ë ì í î ï ñ ò ó ô õ ö ÷ ø ù ú û ü ý þ
65 65 65 65 65 69 69 69 69 69 73 73 73 73 73 79 79 79 79 79 85 85 85 85 85 89 89 89 89 89 161 161 161 161 161 161 162 162 162 162 162 162 163 163 163 163 163 163 164 164 164 164 164 164 165 165 165 165 165 165 166 166 166 166 166 166 167 168 169 170 171 172 173 174 181 182 183 184 185 187 188 189 190 198 199 200 201 202 203 204 206 207 208 209 210 211 212 213 214 215 216 220 221 222 223 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 241 242 243 244 245 246 247 248 249 250 251 252 253 254
Ok, đến đây thì ta có hai cách để giải quyết thay một ký tự c trong văn bản từ TCVN3 sang Unicode:
- Cách tay to: duyệt tất cả phần tử trong mảng TCVN3 nếu gặp ký tự nào bằng ký tự c thì ta thay bằng ký tự Unicode tại vị trí tìm được đó. Cách này ta thấy ngay độ phức tạp thời gian O(n^2), nếu văn bản lớn thì không ổn.
- Ta sẽ sử dụng thuật toán cây nhị phân tìm kiếm (Binary Search) cho độ phức tạp thời gian O(nlogn).
1. Cây nhị phân tìm kiếm - Binary Search
Giải thuật được lấy ý tưởng từ phương pháp chia để trị (Devide and Conquer) và có hai cách cài đặt là sử dụng đệ quy (Recursion) hoặc vòng lặp. Trong một dãy có thứ tự (mình đã sắp xếp sẵn mảng TCVN3 như trên bảng rồi đó), để tìm kiếm vị trí của phần tử x, đầu tiên ta chia mảng thành hai nửa tại vị trí m = (l + r)/2, nếu may mắn x = TCVN3[m] thì ta trả về vị trí m luôn, nếu TCVN3[m] < x thì chắc chắn x sẽ thuộc nửa bên phải, ta tiếp tục chia đôi nửa bên phải ra và cứ thế đến khi l > r thì thôi.
1.1. Recursion
int FindRecursion(int code, int l, int r) {
int m = (l + r) / 2;
if (l <= r) {
if (TCVN3[m] == code)
return m;
if (TCVN3[m] < code)
return FindRecursion(code, l, m - 1);
if (TCVN3[m] > code)
return FindRecursion(code, m + 1, r);
}
return -1;
}
1.2. Vòng lặp
int Find(int code, int l, int r) {
while (l <= r) {
int m = (l + r) / 2;
if (TCVN3[m] == code)
return m;
if (TCVN3[m] < code)
l = m + 1;
else
r = m - 1;
}
return -1;
}
2. TCVN3 to Unicode
string Convert(string text) {
int index;
string uniText = "";
for (int i = 0; i < text.length(); i++) {
index = Find(text[i], 0, 132); // do mảng TCVN3 có 133 phần tử nhé!
if (index != -1)
uniText += char(UNICODE[index]);
esel
uniText += text[i];
}
return uniText;
}
Ok rồi, mọi người có thể kiểm tra chuỗi trong tool mình viết sẵn ở đầu bài viết nhé! Hẹn gặp lại mọi người.
