khi mình lưu trữ dữ liệu thì bản thân dữ liệu mình lưu trữ chứa thông tin, that’s for sure. nhưng điều mà mình thường không nhận ra đó là cấu trúc lưu trữ dữ liệu cũng chứa rất nhiều thông tin.

ví dụ như file permission string hôm trước mình học. ký tự đầu là file type, 3 bộ triplet ký tự sau là r-w-x cho 3 nhóm user khác nhau, nếu mình muốn tìm xem user có khả năng viết vào file này không, mình sẽ đi thẳng đến ký tự thứ 9 và biết chắc chắn rằng thông tin mình cần chỉ nằm ở ký tự này.

file permission string

ví dụ khác như TCP header file information. nếu mình là một cái máy tính và tự dưng nhận được cái packet này, làm sao mình biết packet này cần được gửi đến cổng nào? mình có thể nhìn vào bit thứ 17 cho đến 32 của packet (tính từ bit đầu tiên) để có được thông tin về destination port. again, mình chỉ cần quan tâm đến 16 bit tính từ bit thứ 17, mình không cần nhìn ra các chỗ khác để có được thông tin mình cần.

tcp header format

một ví dụ khác là cây tìm kiếm nhị phân. mọi phần tử thuộc cây con bên trái sẽ nhỏ hơn root, và mọi phần tử thuộc cây con bên phải sẽ lớn hơn root. mình muốn tìm một phần tử? binary search, mỗi lần đưa ra một quyết định là mình chém bài toán gốc xuống một bài toán có size bằng một nửa, giảm đi rất nhiều computation & comparison cần làm. điều này khả thi là vì cấu trúc lưu trữ của cây tìm kiếm nhị phân. mình luôn giảm bài toán hiện tại thành một bài toán nhỏ hơn được mà không phải lo về tính đúng đắn là vì cấu trúc của cây nó như vậy. lời giải này trên cấu trúc dữ liệu này sẽ không bao giờ sai.

binary search tree

kì này mình học NLP xoá mù chữ, và một trong những ý tưởng lớn là attention. khi có cách để giúp mô hình ngôn ngữ (1) cân nhắc nhiều ý nghĩa khả thi cho một đoạn văn bản và (2) pay attention vào ý nghĩa quan trọng, thì chất lượng output của mô hình được cải thiện đáng kể.

mình thấy khả năng có thể chỉ tìm kiếm ở một subset of data nhờ vào sự tổ chức dữ liệu hiệu quả cũng giống như attention của mô hình ngôn ngữ. thay vì phải pay attention to 8, 16, 96 ý nghĩa cùng một lúc, thì mình cân nhắc ngần đó ý nghĩa lúc ban đầu, sau đó chỉ chọn một (vài) ý nghĩa có khả năng cao nhất và làm việc tiếp với nó thôi.

tương tự vậy, khi trồng cây tìm kiếm nhị phân cân bằng, mình phải bỏ công ra sắp xếp lại mỗi lần insert hay delete, nhưng sau đó tìm kiếm sẽ cực kỳ nhanh. pattern số 1 ở đây là mất chút overhead cost để setup data structure, nhưng sau đó thì ai cũng vui vì nhanh và đúng.

ngoài ra trong cây tìm kiếm nhị phân tự cân bằng, thì mình còn biết được thêm là root là median của toàn bộ data set nữa. vậy có thể pattern số 2 là cấu trúc càng phức tạp thì càng chứa nhiều thông tin.

tất cả những cái này thật ra không có mới. ai cũng biết binary search chỉ khả thi trên cấu trúc dữ liệu có thứ tự như sorted array hay bst. mình cũng luôn biết cái đó.

chỉ là bây giờ mình mới nhìn ra một sợi dây chung nối rất nhiều kiến thức đã học từ khắp nơi với nhau. vì sao người ta bỏ bao nhiêu công ra nghiên cứu run time của các cấu trúc dữ liệu? vì sao packet header phải follow đúng format? tại vì ở tầng low low low level (bits 0 1), thì file nào dữ liệu nào cũng chỉ là một dây nhị phân siêu dài : D nếu không có cấu trúc, thì làm sao biết cần phải đọc đến đâu để có thông tin mình cần?

nói chung mình rất thích realization này. giờ mình mới bắt đầu appreciate bao nhiêu công sức thiết kế một hệ thống mà works in tandem với nhau. và thông tin này là kiểu once i see it i cant unsee it. i see structures everywhere now, and i will forever be curious what information the structure alone holds.

credit: người đầu tiên gieo mầm cho mình nhận ra cái này là thầy Nhựt dạy computer networks. hồi đó thầy nói “a protocol is nothing but the header of the packet”. mãi đến bây giờ mình mới hiểu the structure of the header is the most important. và network communication protocol về cơ bản chỉ là các tầng network biết phải đọc thông tin mình cần ở đâu trong một dãy nhị phân siêu dài.

what fascinating realization!