Lập trình từ điển cơ bản

Trước đây, tôi đã từng có một bài viết Lập trình từ điển sử dụng C. Tuy nhiên, đó chỉ là một kiểu bài tập sinh viên nho nhỏ, dữ liệu chỉ là một file text vài dòng, tập trung vào giải thuật nhiều hơn là ứng dụng. Xuất phát từ nhu cầu thực tế là tôi cần tích hợp một bộ từ điển Anh-Việt cho ứng dụng Học Tiếng Anh Streamline của mình, tôi bắt đầu mày mò tìm hiểu cách để có được một bộ từ điển đúng chuẩn với dữ liệu phong phú.

Tìm kiếm dữ liệu

Cá nhân tôi cho rằng, đối với một ứng dụng từ điển thì có hai điều quan trọng nhất chúng ta cần đảm bảo: Thứ nhất là dữ liệu phải nhiều và phải chuẩn, thứ hai là tốc độ tìm kiếm phải nhanh. Việc tự nhập liệu tôi không muốn tự làm vì quá mất thời gian cũng như không thể nào chuẩn được.

May mắn thay, từ điển không phải là một ứng dụng quá xa lạ, ở Việt Nam chúng ta đã có rất nhiều tổ chức, cá nhân tự tạo ra các bộ từ điển của họ. Vậy nên, tôi tin chắc là phải có một chuẩn chung nào đó giữa các bộ từ điển mà tôi có thể kế thừa.

Tìm kiếm trên mạng, tôi vô tình "lụm" được tài liệu này: https://www.slideshare.net/duyanhphamkiller/ebook-huong-dan-lam-tu-dien-ti-123docvn, trong đó mô tả khá chi tiết cách để tạo nên một bộ từ điển, bao gồm cả nguồn dữ liệu lẫn giải thuật. Tài liệu dẫn tôi tới trang cá nhân của tác giả Hồ Ngọc Đức, một người Việt sinh sống và học tập ở nước ngoài. Dựa theo thông tin về niên học lớp 12 của tác giả (1987), tôi đoán chứng vị tiền bối này sinh vào khoảng năm 1970. Ông cũng chính là tác giả của công cụ Âm Lịch VN mà khi gõ vào google từ khóa "âm lịch", bạn sẽ thấy công cụ này luôn được hiển thị đầu tiên.

Data cho các bộ từ điển có thể được tải về ở đây: https://www.informatik.uni-leipzig.de/~duc/Dict/install.html#manual. Bộ từ điển Anh-Việt bao gồm hơn 100 ngàn từ, các bạn chỉ cần tải về file zip, xả nén, xả nén tiếp file *.dict.dz bạn sẽ thu được file data cuối cùng có dạng *.dict (bản chất là 1 file *.txt). Nếu tinh ý, bạn sẽ thấy khá nhiều phần mềm từ điển ở Việt Nam dùng chung bộ data này. Tuy vậy, bộ data này có khá nhiều lỗi chính tả, từ bị trùng lặp, thậm chí có cả từ không tồn tại. Hiện tôi đã và đang thanh lọc bộ dữ liệu này xuống còn khoảng hơn 95 ngàn từ, và vẫn đang trong quá trình rà soát sửa lỗi.

Chuẩn dữ liệu

Dữ liệu từ điển trên thực tế được lưu trữ rất đơn giản, dưới dạng file text đi kèm với một file index (đánh chỉ mục). Bạn có thể vào trang dict.org để tham khảo các bộ từ điển khác. Quy ước lưu và trình bày như thế nào là do bạn quyết định, tôi thì dùng cách bên dưới. Một khi đã có quy ước trình bày rõ ràng thì bạn chỉ cần viết cách đọc file tương ứng ra là được.

@headword
*part of speech
-definition 1
=example explaining definition 1+translation of example
-definition 2
=example explaining definition 2+translation of example
*part of speech
-definition 3

Ví dụ cụ thể một đoạn trong file dữ liệu như sau: 

@nasturtium /nəs'tə:ʃəm/
*danh từ
-(thực vật học) cây sen cạn
@nasty /'nɑ:sti/
*tính từ
-bẩn thỉu; dơ dáy; kinh tởm, làm buồn nôn
=a nasty smell+mùi kinh tởm
=a nasty taste+vị buồn nôn

Làm sao cho nhanh?

Dữ liệu đã có, và có rất nhiều, vậy câu hỏi tiếp theo là làm sao để từ điển của chúng ta chạy nhanh, chỉ cần bấm nút là trả về kết quả ngay lập tức từ file dữ liệu chứa cả trăm ngàn từ? Câu trả lời chính là index (lập chỉ mục). Việc index dữ liệu nói nôm na là bằng cách nào đó, chúng ta có thể "đánh dấu" được vị trí của dữ liệu, từ đó tìm ra kết quả nhanh hơn.

Giả sử bạn phải quản lý 100 ngàn quyển sách cho một thư viện, nếu chỉ chất đống để đó thì việc tìm kiếm một quyển sách cụ thể sẽ cực kỳ tốn thời gian. Nhưng nếu chúng ta bỏ công sức ra để sắp xếp, phân loại theo một quy luật nào đó (ví dụ phân loại sách theo chủ đề, sắp theo thứ tự bảng chữ cái, đánh số cho kệ sách v.v...) thì việc tìm kiếm sẽ nhanh hơn rất nhiều. Việc lập chỉ mục cho dữ liệu từ điển cũng tương tự như vậy, trong đó, sách sẽ được thay bằng những từ mà chúng ta cần tra cứu.

Nhìn lại hình trên, bạn sẽ thấy có một file .index đi kèm với file dữ liệu .dict.dz, đây chính là file đánh dấu vị trí của mỗi một từ trong file dữ liệu. Trong file index, mỗi dòng sẽ gồm 3 phần: từ, vị trí, và độ dài lưu trữ tính theo bytes. Các phần được chia tách nhau bởi ký tự tab (\t). Ví dụ, từ "nasty" được đánh dấu như sau:

nasty	aDL1	Mb

aDL1 và Mb vốn là số thập phân được mã hóa Base64, để hiểu hơn về cách mã hóa, bạn vui lòng đọc bài viết sau. Còn ở đây, để dịch ngược lại mã trên thì cách làm rất đơn giản: dựa theo bảng bên dưới, số thứ tự của a là 26, D là 3, L là 11, và 1 là 53 vậy quy đổi thành 26*64^3 + 3*64^2 + 11*64^1 + 53*64^0 = 6828789. Tương tự với Mb, chúng ta có 12*64^1 + 27*64^0 = 795.

 

STT	Nhị phân	Đầu ra		STT	Nhị phân	Đầu ra		STT	Nhị phân	Đầu ra		STT	Nhị phân	Đầu ra
0	000000	A		16	010000	Q		32	100000	g		48	110000	w
1	000001	B		17	010001	R		33	100001	h		49	110001	x
2	000010	C		18	010010	S		34	100010	i		50	110010	y
3	000011	D		19	010011	T		35	100011	j		51	110011	z
4	000100	E		20	010100	U		36	100100	k		52	110100	0
5	000101	F		21	010101	V		37	100101	l		53	110101	1
6	000110	G		22	010110	W		38	100110	m		54	110110	2
7	000111	H		23	010111	X		39	100111	n		55	110111	3
8	001000	I		24	011000	Y		40	101000	o		56	111000	4
9	001001	J		25	011001	Z		41	101001	p		57	111001	5
10	001010	K		26	011010	a		42	101010	q		58	111010	6
11	001011	L		27	011011	b		43	101011	r		59	111011	7
12	001100	M		28	011100	c		44	101100	s		60	111100	8
13	001101	N		29	011101	d		45	101101	t		61	111101	9
14	001110	O		30	011110	e		46	101110	u		62	111110	+
15	001111	P		31	011111	f		47	101111	v		63	111111	/
Đệm		=

Bây giờ hãy mở file index bằng một ứng dụng biên tập nào đó, như Notepad++ chẳng hạn. Đặt con trỏ chuột ở ngay phía trước ký tự @ của chữ nasty, bạn sẽ thấy vị trí hiển thị (pos) chính là con số 6828789 chúng ta đã tính ở trên.

Bây giờ hãy copy toàn bộ phần nội dung của chữ nasty và paste vào một công cụ byte counter nào đó, bạn sẽ thấy dung lượng được tính ra chính là 795. Nên nhớ vì dữ liệu của chúng ta được lưu ở dạng utf-8 nên 1 ký tự chưa chắc đã là 1 byte mà còn tùy thuộc vào ký tự có dấu hay không, có phải là ký tự đặc biệt hay không nên dung lượng thực tế sẽ dao động từ 1 tới 4 bytes cho mỗi ký tự.

Khi chúng ta đã biết được vị trí và độ dài chính xác của từng từ thì việc đọc dữ liệu sẽ cực kỳ nhanh. Lý do là chúng ta sẽ không đọc file theo cách thông thường (quét từng dòng một) mà dùng cơ chế đọc ngẫu nhiên (random access file), trong đó chúng ta có thể ngay lập tức nhảy tới bất kỳ vị trí nào trong file để lấy ra từ và dữ liệu tương ứng.

Làm sao để tạo được file chỉ mục?

Bây giờ chúng ta đã hiểu cách lưu trữ dữ liệu và đánh chỉ mục. Từ đây có thể hiểu rằng, nếu chúng ta chỉnh sửa file dữ liệu, như thêm xóa sửa một từ thì toàn bộ những từ theo sau nó sẽ bị ảnh hưởng theo. Do đó chúng ta sẽ phải đánh lại chỉ mục để cập nhật lại vị trí và độ dài của từng từ. Đây cũng là lý do mà khi chọn field để đánh chỉ mục trong SQL, chúng ta thường chọn những field có tính cố định, ít thay đổi.

Rõ ràng, để đánh chỉ mục cho gần 100 ngàn từ vựng bằng tay là điều không thể. May mắn thay là trên trang chủ của tác giả Hồ Ngọc Đức đã cung cấp sẵn công cụ giúp chúng ta có thể làm được điều này một cách dễ dàng.

Download ứng dụng từ điển của Hồ Ngọc Đức ở đây: https://www.informatik.uni-leipzig.de/~duc/Dict/TuDienHND_Win32.exe. Sau khi cài đặt, xả nén, bạn sẽ thấy tập tin vietdict.jar. Chạy file bằng lệnh java -cp vietdict.jar vietdict.tools.DBIndexGenerator (máy tính của bạn cần được cài sẵn JDK) sẽ mở ra công cụ Generate Index File.

Copy file dữ liệu dưới dạng *.txt vào cùng thư mục với vietdict.jar. Trong file eng_vni.cfg chỉ cần lưu tên của file dữ liệu cần xử lý, trong trường hợp này là "eng_vni.txt".

Trong ứng dụng Generate Index File, chọn file .cfg ở trên, cấu hình như hình và bấm Run.

File *.dict và *.index đã được tạo thành công, bạn đã có thể dùng 2 file này phục vụ cho việc lập trình ứng dụng

Viết phần mềm

Giờ chúng ta đã có trong tay đầy đủ nguyên liệu cần thiết. Bạn có thể chọn một ngôn ngữ bất kỳ để viết ứng dụng. Trong trường hợp này, tôi sử dụng Java để tích hợp thêm tính năng tra cứu vào ứng dụng Android đã có sẵn.

Đầu tiên chúng ta sẽ cần hàm chuyển đổi từ Base64 sang thập phân, dùng để chuyển đổi dữ liệu từ file index:

public class Base64Helper {
    public static int getDecimalValue(String s) {
        String base64 = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/";
        int decValue = 0;
        int len = s.length();
        for (int i = 0; i < len; i++) {
            int pos = base64.indexOf(s.charAt(i));
            decValue += (int) Math.pow(64, len - i - 1) * pos;
        }
        return decValue;
    }
}

Còn đây là 2 method: readIndex() để đọc dữ liệu từ file index và nạp vào một HashMap collection có tên wordIndex; getMeaning(key) sẽ nhận vào từ mà chúng ta cần tra, lấy dữ liệu từ file *.dict bằng cơ chế Random Access File và trả về toàn bộ nghĩa ở dạng thô tương ứng.

protected final HashMap<String, String> wordIndex;

@SuppressLint("NewApi")
private HashMap<String, String> readIndex() {

	HashMap<String, String> wordIndex = new HashMap<>();
	InputStream fis;
	try {
		if (mode == null) {
			AssetManager assetManager = this.context.getAssets();
			fis = assetManager.open(this.indexPath);
		} else {
			// for unit test only
			fis = Files.newInputStream(Paths.get(this.indexPath));
		}

		BufferedReader br = new BufferedReader(new InputStreamReader(fis));
		String line;
		while ((line = br.readLine()) != null) {
			int pos = line.indexOf('\t');
			String sWord = line.substring(0, pos);
			String sData = line.substring(pos + 1).replaceAll("\t", " ");
			wordIndex.put(sWord, sData);
		}
	} catch (IOException e) {
		throw new RuntimeException(e);
	}
	return wordIndex;
}

public String getMeaning(String key) {
	StringBuilder meaning = new StringBuilder();
	try {
		RandomAccessFile f = new RandomAccessFile(dictFile, "r");

		String sData = wordIndex.get(key);
		if (sData == null) {
			sData = wordIndex.get(new PorterStemmerHelper().stem(key));
		}
		if (sData == null) {
			return null;
		}

		int offset = Base64Helper.getDecimalValue(sData.split(" ")[0]);
		int len = Base64Helper.getDecimalValue(sData.split(" ")[1]);

		f.seek(offset);

		byte[] buffer = new byte[2048];
		int bytesRead;
		while (len > 0 && (bytesRead = f.read(buffer, 0, Math.min(len, buffer.length))) != -1) {
			meaning.append(new String(buffer, 0, bytesRead, StandardCharsets.UTF_8));
			len -= bytesRead;
		}

		f.close();
	} catch (IOException e) {
		throw new RuntimeException(e);
	}
	return meaning.toString();
}

Khi đã lấy được nội dung nghĩa của một từ, thì bạn có thể show lên UI ngay hoặc xử lý màu mè cho đẹp mắt. Kết quả cuối cùng như sau:

Kết luận

Như vậy, về cơ bản chúng ta đã hiểu được cơ bản cách thức một ứng dụng từ điển hoạt động. Dĩ nhiên, để một ứng dụng từ điển có thể thu hút được người dùng đòi hỏi nhiều tính năng và tiện ích hơn thế, nhưng dù thế nào đi chăng nữa thì dữ liệu và tốc độ tìm kiếm vẫn là yếu tố quan trọng nhất. Cảm ơn các bạn đã đọc bài viết, chúc các bạn thành công!