- Triển khai kiến trúc công cụ tìm kiếm hoạt động không cần dịch vụ bên ngoài bằng cách tận dụng cơ sở dữ liệu sẵn có, tập trung vào token hóa, trọng số và chấm điểm
- Ý tưởng cốt lõi là token hóa toàn bộ văn bản rồi lưu lại, sau đó khi tìm kiếm sẽ đối chiếu token theo cùng một cách để tính mức độ liên quan
- Kết hợp Word, Prefix, N-Gram tokenizer để xử lý đồng thời khớp chính xác, khớp một phần và cả lỗi gõ, với mỗi tokenizer có trọng số riêng
- Thông qua hệ thống trọng số và thuật toán chấm điểm dựa trên SQL, đánh giá tổng hợp độ dài tài liệu, độ đa dạng token, chất lượng trung bình, v.v.
- Có khả năng mở rộng và tính minh bạch cao, nên có thể tự do thêm tokenizer mới hoặc loại tài liệu mới, điều chỉnh trọng số hay sửa logic chấm điểm
Vì sao tự xây dựng công cụ tìm kiếm
- Các dịch vụ bên ngoài như Elasticsearch hay Algolia rất mạnh, nhưng đi kèm gánh nặng học API phức tạp và quản lý hạ tầng
- Khi chỉ cần chức năng tìm kiếm tích hợp với cơ sở dữ liệu hiện có và dễ debug, việc tự xây dựng sẽ hữu ích
- Mục tiêu là một công cụ tìm kiếm đơn giản, không phụ thuộc bên ngoài nhưng vẫn trả về kết quả có độ liên quan cao
Khái niệm cốt lõi: token hóa và đối sánh
- Nguyên lý cơ bản là token hóa (tokenize) toàn bộ văn bản để lưu trữ, rồi khi tìm kiếm tạo token theo cùng cách để đối sánh
- Ở bước lập chỉ mục, nội dung được tách thành các đơn vị token và lưu cùng trọng số
- Ở bước tìm kiếm, truy vấn được token hóa giống hệt để tìm token trùng khớp và tính điểm
- Ở bước chấm điểm, các trọng số đã lưu được dùng để tính điểm mức độ liên quan
Thiết kế schema cơ sở dữ liệu
- Sử dụng hai bảng:
index_tokens và index_entries
index_tokens: lưu token duy nhất và trọng số theo từng tokenizerindex_entries: liên kết token với tài liệu, đồng thời lưu điểm cuối cùng đã phản ánh trọng số của field, tài liệu và tokenizer
- Công thức tính trọng số cuối cùng:
field_weight × tokenizer_weight × ceil(sqrt(token_length))
- Chỉ mục được thiết lập để phục vụ tra cứu tài liệu, tra cứu token, truy vấn theo field và lọc trọng số
Hệ thống token hóa
- WordTokenizer: tách theo từ, loại bỏ từ quá ngắn, dùng cho khớp chính xác (trọng số 20)
- PrefixTokenizer: tạo tiền tố của từ, dùng cho tự động hoàn thành và khớp một phần (trọng số 5)
- NGramsTokenizer: tạo tổ hợp ký tự có độ dài cố định, dùng để xử lý lỗi gõ và khớp một phần (trọng số 1)
- Tất cả tokenizer đều cùng thực hiện chuyển về chữ thường, loại bỏ ký tự đặc biệt và chuẩn hóa khoảng trắng
Hệ thống trọng số
- Trọng số field: phản ánh mức độ quan trọng của tiêu đề, nội dung, từ khóa, v.v.
- Trọng số tokenizer: theo thứ tự Word > Prefix > N-Gram
- Trọng số tài liệu: được tính bằng cách kết hợp hai yếu tố trên với độ dài token
- Hàm
ceil(sqrt()) được dùng để làm giảm ảnh hưởng của token dài; nếu cần có thể thay bằng hàm log hoặc tuyến tính
Dịch vụ lập chỉ mục
- Chỉ những tài liệu triển khai
IndexableDocumentInterface mới có thể được lập chỉ mục
- Khi tài liệu được tạo hoặc sửa, quá trình lập chỉ mục sẽ chạy qua event listener hoặc lệnh (
app:index-document, app:reindex-documents)
- Quy trình:
- Xóa chỉ mục cũ rồi tạo token mới
- Chạy tất cả tokenizer cho từng field
- Kiểm tra token đã tồn tại hay chưa rồi tạo nếu cần (
findOrCreateToken)
- Chèn theo lô (batch insert) vào
index_entries bằng trọng số đã tính
- Cấu trúc này hỗ trợ tránh trùng lặp, tăng hiệu năng và xử lý cập nhật
Dịch vụ tìm kiếm
- Truy vấn được xử lý bởi cùng các tokenizer để thu được tập token giống với lúc lập chỉ mục
- Loại bỏ token trùng lặp, sắp xếp theo độ dài giảm dần (ưu tiên token dài), và giới hạn tối đa 300 token
- Thông qua truy vấn SQL để join token với tài liệu, tính điểm mức độ liên quan và sắp xếp
- Kết quả được trả về dưới dạng
SearchResult(documentId, score)
Thuật toán chấm điểm
- Điểm cơ bản:
SUM(sd.weight)
- Hiệu chỉnh độ đa dạng token:
LOG(1 + COUNT(DISTINCT token_id))
- Hiệu chỉnh trọng số trung bình:
LOG(1 + AVG(weight))
- Penalty cho độ dài tài liệu:
1 / (1 + LOG(1 + token_count))
- Chuẩn hóa (normalization): chia cho điểm tối đa để đưa về khoảng 0~1
- Loại bỏ các khớp vô nghĩa có trọng số thấp thông qua bộ lọc trọng số token tối thiểu (
st2.weight >= ?)
Xử lý kết quả
- Kết quả tìm kiếm trả về ID tài liệu và điểm số, sau đó được chuyển thành tài liệu thực tế thông qua repository
- Dùng hàm
FIELD() để giữ nguyên thứ tự kết quả tìm kiếm khi truy vấn tài liệu
Khả năng mở rộng của hệ thống
- Có thể thêm tokenizer mới bằng cách triển khai
TokenizerInterface
- Có thể đăng ký loại tài liệu mới bằng cách triển khai
IndexableDocumentInterface
- Trọng số và logic chấm điểm đều có thể điều chỉnh chỉ bằng cách sửa SQL
Kết luận
- Cấu trúc này là một công cụ tìm kiếm đơn giản nhưng thực sự hoạt động, đủ cung cấp hiệu năng tốt ngay cả khi không có hạ tầng bên ngoài
- Ưu điểm là logic rõ ràng, kiểm soát hoàn toàn và dễ debug
- Bài viết nhấn mạnh rằng so với những hệ thống phức tạp, đoạn mã mà bạn có thể tự hiểu và kiểm soát trực tiếp đôi khi còn giá trị hơn
1 bình luận
Ý kiến trên Hacker News
Ý tưởng cơ bản của tìm kiếm thì đơn giản và là một lĩnh vực bài toán thú vị
Nhưng điều thực sự khó là xử lý khối lượng dữ liệu lớn và các truy vấn mơ hồ
Cách tiếp cận dựa trên DBMS ổn ở quy mô website nhỏ, nhưng đến cỡ Wikipedia tiếng Anh thì sẽ nhanh chóng chạm trần
Với người mới bắt đầu, SeIRP e-book là một tài liệu miễn phí rất tốt
Việc không có đáp án rõ ràng khiến vấn đề này đặc biệt hóc búa
Google đôi khi còn hiển thị quảng cáo như là “kết quả phù hợp nhất”, nên Marginalia Search là một trường hợp đối chiếu hay
Tôi cũng tò mò không biết bạn đã từng tham khảo các bài báo TREC chưa
Công cụ tìm kiếm phải liên tục chiến đấu với các đối thủ mang tính đối kháng đang nhắm tới doanh thu quảng cáo
Nó trở thành một trò mèo vờn chuột bất tận, khi phải liên tục thay đổi các chỉ số chất lượng để họ không thể khai thác ngược
Với mốc 5 giây mỗi truy vấn và khoảng 12 truy vấn mỗi phút, tôi muốn biết có thể tìm kiếm trên corpus lớn đến mức nào
Ví dụ, rất khó để đánh giá bài wiki về Gilligan’s Island hay một blog fan là kết quả “tốt” hơn
Khi cộng thêm thao túng xếp hạng hoặc nhồi nhét từ khóa, nó trở thành một thách thức phức tạp hơn rất nhiều so với vấn đề mở rộng quy mô
Tìm kiếm thực sự rất khó
Ngay cả những công ty có nguồn lực và năng lực kỹ thuật dồi dào như Apple, Microsoft, OpenAI cũng có chất lượng tính năng tìm kiếm thấp
Đây không chỉ là một vấn đề kỹ thuật
Để nâng chất lượng tìm kiếm, cần tinh chỉnh rất chi tiết các tham số xếp hạng, nhưng kiểu công việc này rất khó lập kế hoạch bằng những hệ thống quản trị như sprint hay Jira
Cuối cùng, đây là lĩnh vực đòi hỏi sự tin tưởng và tính tự chủ dành cho lập trình viên
Họ đầu tư hàng tỷ vào mô hình AI, còn webapp hay tìm kiếm chỉ là thứ yếu nên mới ra kết quả như vậy
Khoảng 10 năm trước tôi từng làm việc cùng một đồng nghiệp đang học tiến sĩ về thiết kế công cụ tìm kiếm
Anh ấy nói rất say mê về việc tích hợp tìm kiếm và cơ sở dữ liệu, và nhờ vậy tôi đã học được rất nhiều
Một ngày nào đó tôi muốn đào sâu vào nội bộ của Apache Solr và Lucene
Trước đây không có giải pháp tìm kiếm mã nguồn mở nên phải tự làm
Bài học rút ra từ trải nghiệm đó là: “đừng tự xây công cụ tìm kiếm”
Rất nhiều người đã dành nhiều năm vật lộn với bài toán này, và nếu tự làm thì bạn sẽ rơi vào địa ngục bảo trì bất tận
Một khi bắt đầu xuất hiện các yêu cầu như “thêm tính năng sửa lỗi gõ sai” hay “năm sau thêm cả taxonomy nữa”, thì coi như xong
Trước đây tôi đã rất thích khóa học xây dựng công cụ tìm kiếm do giáo sư David Evans của Virginia University giảng dạy
Tự tay làm một “công cụ tìm kiếm cổ điển” là một dự án cực kỳ thú vị
Có thể tham khảo liên kết bài giảng và playlist YouTube
Tôi khó chịu vì những công cụ tìm kiếm tôi hay dùng lại bỏ qua các từ hoặc chữ viết tắt 2~3 ký tự
Khi tìm các từ ngắn như “mp3” hay “PHP” mà bị loại bỏ thì thực sự rất bất tiện
Tôi đã đọc Programming Collective Intelligence của Toby Segaran và lấy được cảm hứng từ nhiều ý tưởng về tìm kiếm, gợi ý, bộ phân loại
Đây là một bài viết thú vị
Nó khiến tôi tò mò không biết mức độ tối ưu hóa của tokenizer mà các công cụ tìm kiếm phổ biến đang dùng cao đến đâu
Tôi tò mò hệ thống này sẽ hoạt động mở rộng quy mô tốt đến mức nào
Elasticsearch cho thấy hiệu năng khá ấn tượng ngay cả khi vượt quá quy mô khuyến nghị
Làm một công cụ tìm kiếm văn bản đơn giản thì không quá khó
Nhưng làm ra một công cụ tìm kiếm tốt lại là câu chuyện hoàn toàn khác
Chỉ triển khai các thuật toán như BM25 thôi thì chưa đủ
Hầu hết các công ty tôi từng tư vấn đều dùng giải pháp tự xây rồi cuối cùng chuyển sang Elasticsearch hoặc Opensearch
Tự triển khai ban đầu thì đơn giản, nhưng theo thời gian sẽ trở nên phức tạp vì vấn đề xếp hạng và suy giảm hiệu năng
Những triệu chứng như “chậm”, “ra kết quả kỳ quặc” cứ lặp đi lặp lại
Elasticsearch đã giải quyết các vấn đề này từ 10 năm trước, và giờ còn tiến xa hơn nhiều
Có người nói “cấu hình khó”, nhưng dạo này phần lớn đã được tự động cấu hình, lại còn có nhiều dịch vụ managed
Thậm chí còn dễ xử lý hơn Postgres
Cuối cùng, điều quan trọng là tối ưu index mapping
Có người nói “không cần những tính năng cao cấp đó”, nhưng thực tế thì chất lượng tìm kiếm gắn trực tiếp với sự sống còn của doanh nghiệp
Nếu muốn tìm kiếm tử tế, rốt cuộc vẫn phải chấp nhận sự phức tạp này
Những phương án thay thế mới nổi như SeekStorm, thứ gần đây được nhắc khá nhiều trên HN, cũng trông khá thú vị, nhưng tôi vẫn chưa thấy ca production thực tế nào
Đặc biệt, mẹo tắt dynamic mapping và chặn index các field không cần thiết rất hữu ích
Theo tôi biết thì đây là một dự án còn lâu đời hơn cả Lucene