Kiểm tra khoảng trắng khó đến đâu: từ bất đồng Unicode đến perfect hash trong Guava

Sergey Tselovalnikov có một bài viết nhỏ nhưng thú vị xuất phát từ một câu hỏi tưởng như vô nghĩa: tại sao hàm kiểm tra khoảng trắng trong Guava, thư viện Java của Google, không chỉ là c == ' '? Đi theo câu hỏi này, ta gặp hai thứ dev nào cũng nên biết: định nghĩa khoảng trắng không thống nhất giữa các runtime, và một ứng dụng đẹp của perfect hashing.

Phần đầu liên quan trực tiếp đến các bug xử lý dữ liệu mà có lẽ nhiều người đã từng gặp. Phần sau là một mẹo tối ưu đáng để biết, dù ít khi cần tự viết.

Khoảng trắng là gì

Ngoài SPACE (U+0020), tab và newline, thuộc tính White_Space của Unicode hiện có 25 ký tự. Mỗi ký tự có mục đích riêng. FIGURE SPACE (U+2007) rộng bằng một chữ số để căn bảng. THIN SPACE (U+2009) và HAIR SPACE (U+200A) tạo khoảng hở nhỏ dần. NO-BREAK SPACE (U+00A0) rộng như dấu cách thường nhưng không cho ngắt dòng ở đó.

Tên gọi và hình dạng đều dễ gây nhầm:

ZERO WIDTH SPACE (U+200B) có chữ "space" trong tên nhưng không thuộc nhóm whitespace. Nó là ký tự định dạng.
OGHAM SPACE MARK (U+1680) là whitespace nhưng có thể được hiển thị thành một vạch ngang nhìn thấy được, tùy font.

Mỗi runtime một quy tắc

Đây là phần đáng ghi nhớ nhất của bài. Ba ngôn ngữ phổ biến cho ba đáp án khác nhau:

Ký tự	Unicode `White_Space`	Java `Character.isWhitespace`	Python `str.isspace`	JavaScript `/\s/`
U+00A0 NO-BREAK SPACE	Có	Không	Có	Có
U+0085 NEXT LINE	Có		Có	Không
U+001C FILE SEPARATOR	Không		Có
U+FEFF ZERO WIDTH NO-BREAK SPACE	Không		Không	Có

Ô trống là những trường hợp bài gốc không đề cập, nên hãy tự kiểm tra nếu cần. Java cố ý loại U+00A0 và hai ký tự non-breaking khác. Python nhận 29 ký tự thay vì 25. JavaScript coi U+FEFF, ký tự BOM quen thuộc, là khoảng trắng nhưng U+0085 thì không.

Ngay cả định nghĩa của Unicode cũng thay đổi theo thời gian. Từ Unicode 6.3, MONGOLIAN VOWEL SEPARATOR (U+180E) bị chuyển sang nhóm ký tự định dạng, nên tập hợp giảm từ 26 xuống 25. Với thư viện chuẩn cần tương thích ngược, những thay đổi như vậy không hề nhỏ.

Bug thực tế từ những khác biệt này

Phần này là ghi chú bổ sung cho dev làm ứng dụng, không có trong bài gốc.

Dữ liệu dán từ Excel, Word hoặc trang web. NBSP rất hay đi kèm khi copy từ HTML, nhất là nơi có  . Với Java, cả trim() và strip() đều không loại U+00A0, nên " abc".strip() vẫn giữ nguyên ký tự đó. Nếu đang nhập số điện thoại, mã sản phẩm hay email thì hai chuỗi nhìn giống hệt nhau vẫn không bằng nhau, và lỗi rất khó nhận ra khi đọc log.

Hai dịch vụ cùng xử lý một chuỗi. Frontend JavaScript gọi trim() đã xóa NBSP và BOM, còn backend Java thì không. Kết quả có thể là validate qua ở một phía nhưng không ở phía kia, hoặc sinh ra hai khóa khác nhau cho cùng một nội dung nhìn thấy được. Đặc biệt cần cẩn thận ở các trường dùng để so khớp hoặc đảm bảo unique như username.

U+200B trong dữ liệu người dùng. Vì không phải whitespace nên trim() không xử lý được. Một username có thể chỉ gồm ký tự vô hình, hoặc trông giống hệt tên của người khác. Với trường định danh, cách an toàn hơn là dùng allowlist ký tự, thay vì cố loại trừ từng ký tự xấu.

Một cách phòng ngừa là chuẩn hóa ở một điểm duy nhất và tường minh về tập ký tự của mình:

// Tập ký tự do hệ thống của bạn quy định, không phụ thuộc runtime
const WS = /[\s\u0085⁠]+/g;

function normalizeInput(value) {
  return value.normalize("NFC").replace(WS, " ").trim();
}

Tập ký tự cụ thể cần được chọn theo nghiệp vụ. Điều quan trọng là bên frontend và backend dùng cùng một định nghĩa, có test với chính những ký tự khó này.

Kiểm tra thật nhanh bằng perfect hash

Giờ quay lại Guava. Giả sử đã thống nhất dùng 25 ký tự của Unicode. Cách đơn giản nhất là duyệt danh sách và so sánh, nhưng hàm kiểm tra khoảng trắng có thể bị gọi trên từng ký tự của khối lượng lớn văn bản. Guava làm như sau:

static final String TABLE = " ..."; // 32 ký tự

public boolean matches(char c) {
    int slot = (1682554634 * c) >>> 27;
    return TABLE.charAt(slot) == c;
}

Chỉ một phép nhân, một phép dịch bit và một lần so sánh. Không vòng lặp, không chia.

Cách nó hoạt động

Perfect hash là hàm băm bảo đảm không có va chạm trên một tập khóa biết trước. TABLE có 32 ô chứa cả 25 ký tự, các ô còn lại được lấp bằng ký tự trùng.

Phép nhân tạo ra một số nguyên 32-bit, bị tràn số một cách có chủ đích. >>> 27 giữ lại 5 bit cao nhất, cho ra một số trong khoảng [0, 32), dùng làm chỉ số. Chẳng hạn, với dấu cách U+0020 (32 trong hệ thập phân), 32 * 1682554634 tràn thành -1992826560, và 5 bit đầu của nó là 10001, tức ô số 17.

Vì mọi ký tự khác cũng rơi vào một ô nào đó, phép so sánh cuối == c là cần thiết để loại các ký tự không nằm trong tập.

Con số ma thuật đến từ đâu

Tác giả bài gốc cũng không rõ 1682554634 được chọn thế nào, và cho thấy nó không phải lựa chọn duy nhất. Ý tưởng tìm kiếm rất trực tiếp: thử từng hệ số, loại ngay khi hai ký tự rơi vào cùng ô. Nhờ không gian tìm kiếm là số nguyên 32-bit nên brute force hoàn toàn khả thi.

static boolean isPerfect(int mul, char[] chars) {
    var slots = new java.util.BitSet(32);
    for (char c : chars) {
        int index = (mul * c) >>> 27;
        if (slots.get(index)) return false;
        slots.set(index);
    }
    return true;
}

Git history của Guava cho thấy cách làm này được tiến hóa dần: từ matcher đơn giản, đến một bản dùng phép chia lấy dư cho 79, rồi đến perfect hash để bỏ được phép chia.

Viết lại trong JavaScript

Nếu chuyển sang ngôn ngữ khác, cần giữ đúng hành vi tràn số 32-bit. Trong JavaScript phải dùng Math.imul, vì phép * thông thường tính trên số thực double và sẽ cho kết quả sai với số lớn:

const WS = [9, 10, 11, 12, 13, 0x20, 0x85, 0xa0, 0x1680,
  0x2000, 0x2001, 0x2002, 0x2003, 0x2004, 0x2005, 0x2006,
  0x2007, 0x2008, 0x2009, 0x200a, 0x2028, 0x2029, 0x202f,
  0x205f, 0x3000];

const slot = (c) => Math.imul(1682554634, c) >>> 27;
const table = new Array(32).fill(0);
for (const c of WS) table[slot(c)] = c;

const isWhitespace = (c) => table[slot(c)] === c;

Mình đã chạy đoạn này trên toàn bộ 65.536 code unit: 25 ký tự không va chạm và kết quả khớp với danh sách. Riêng c = 0 là trường hợp cần lưu ý nếu ô trống được khởi tạo bằng 0 như trên. Trong kiểm tra này U+0000 không bị nhận nhầm vì ô của nó đã có ký tự khác, nhưng bản Guava lấp đầy các ô bằng ký tự whitespace trùng lặp nên không phụ thuộc vào chi tiết đó.

Có nên dùng trong code của bạn

Thường là không cần. Trong đa số ứng dụng, một Set, một switch hoặc bảng tra đều đủ nhanh, lại dễ đọc hơn nhiều. Perfect hash có ý nghĩa khi hàm nằm trên đường thực thi nóng thực sự, ví dụ parser, tokenizer hay protocol handler, khi tập khóa cố định và số liệu profile đã xác nhận đây là nút thắt. Daniel Lemire gần đây cũng có bài về ứng dụng tương tự, dùng để kiểm tra HTTP method.

Điều đáng giữ lại nhiều hơn là tinh thần của bài: tác giả cho rằng những bài đào sâu kiểu này đang hiếm dần khi ta có ít lý do để nhìn vào bên trong một hàm đơn giản như isWhitespace. Lần tới, khi gặp một hàm trông phức tạp hơn mức cần thiết, có thể bên trong có một bài học đáng để bỏ ra vài chục phút.

Bài viết được AI của DevViet viết lại bằng tiếng Việt từ một bài viết/thảo luận tiếng Anh trên Lobsters, có thể chưa chính xác tuyệt đối. Nguồn: How hard is it to check for whitespace?