programming algorithms csharp elasticsearch

Giải Mã Nghệ Thuật Tìm Kiếm: Từ Đếm Từ Khóa Đến BM25 - Bí Mật Đằng Sau Google & Elasticsearch

Lê Lân

18/07/2025

Làm Thế Nào Để Tính Điểm Phù Hợp Cho Tài Liệu Khi Tìm Kiếm?

Mở Đầu

Làm việc với khối lượng lớn dữ liệu và log là thách thức quen thuộc với các kỹ sư SRE và nhiều người dùng khác. Khi tìm kiếm từ khóa trong hàng tá tài liệu, câu hỏi thường được đặt ra là: tài liệu nào sẽ được ưu tiên trả về đầu tiên?

Việc tìm kiếm tài liệu không chỉ dựa vào sự xuất hiện gần đây, mà quan trọng hơn là mức độ phù hợp của tài liệu đó với từ khóa tìm kiếm. Vậy làm sao xác định được mức độ phù hợp (score) của một tài liệu với truy vấn tìm kiếm? Bài viết này sẽ cùng bạn khám phá cách đánh giá điểm phù hợp tài liệu dựa trên các thuật toán phổ biến trong xử lý ngôn ngữ tự nhiên và tìm kiếm văn bản.

Chúng ta sẽ bắt đầu từ những ý tưởng cơ bản nhất, đi qua các thuật toán đơn giản tới các phương pháp nâng cao như TF-IDF và BM25. Dùng ví dụ cụ thể để bạn dễ dàng theo dõi và áp dụng vào công việc thực tế.

Phần 1: Khái Niệm Cơ Bản và Các Định Nghĩa

Token Là Gì?

Trong xử lý văn bản, từ không được gọi là từ thông thường mà gọi là token. Token có thể là từ, cụm từ, hoặc các đơn vị nhỏ hơn tùy theo mục đích phân tích.

Ví dụ đoạn văn: "Un panda est un animal blanc et noir" Token: ["Un", "panda", "est", "un", "animal", "blanc", "et", "noir"]

Tất cả các thuật toán về tìm kiếm và tính điểm sẽ dựa trên tập token này.

Index Inversé (Chỉ Mục Đảo Ngược)

Để nhanh chóng tìm tài liệu chứa một token, ta tạo ra một cấu trúc dữ liệu gọi là index inversé. Đây là một từ điển, trong đó:

Khóa: token.

Giá trị: danh sách các tài liệu có chứa token đó.

Ví dụ:

Token	Tài liệu có chứa
"panda"	Doc 1, Doc 4, Doc 5
"noir"	Doc 1, Doc 3, Doc 6

Index inversé giúp tăng tốc độ truy vấn rất nhiều, tránh việc phải duyệt từng tài liệu một.

Lớp Document và Kết Quả Tìm Kiếm

Chúng ta làm việc trên các đối tượng Document có cấu trúc:

public class Document{
    public string Id { get; set; }
    public string Name { get; set; }
    public string Path { get; set; }
    public string Content { get; set; }
    public int Length { get; set; }
    public List<string> ContentTokens { get; set; }
    public List<string> TitleTokens { get; set; }
    public DateTime IndexedAt { get; set; } = DateTime.UtcNow;
}

Và kết quả tìm kiếm trả về dưới dạng một danh sách SearchResult:

public class SearchResult{
    public string Id { get; set; }
    public string Name { get; set; }
    public string Path { get; set; }
    public string ContentSnippet { get; set; }
    public double Score { get; set; }
    public DateTime IndexedAt { get; set; }
}

Phần 2: Thuật Toán Đếm Tần Suất Token – Phương Pháp Đơn Giản

Ý tưởng ban đầu

Tính điểm dựa trên số lần từ khóa xuất hiện trong tài liệu. Ví dụ:

Token "noir" xuất hiện 1 lần ở Doc1, 1 lần ở Doc3, 11 lần ở Doc6.

Ta cấp điểm 1 cho mỗi lần xuất hiện:

public int GetScore(string token, Document doc){
    int score = doc.ContentTokens.Count(t => t == token.ToLowerInvariant());
    return score;
}

Hạn chế

Một tài liệu chứa nhiều từ khóa trong truy vấn có điểm thấp hơn tài liệu chứa token lặp lại nhiều lần.

Ví dụ: truy vấn "chat", "noir" thì Doc6 có điểm 11 (do "noir" lặp 11 lần) còn Doc3 có 2 (do chứa "chat" và "noir" đúng 1 lần mỗi token), trong khi Doc3 lại phù hợp hơn.

Cải tiến nhẹ: Boost điểm cho tài liệu chứa nhiều token

public int GetScore(List<string> queryTokens, Document doc){
    int totalScore = 0;
    int matchedToken = 0;
    foreach (var token in queryTokens) {
        int score = doc.ContentTokens.Count(t => t == token.ToLowerInvariant());
        if (score > 5) score = 5;  // giới hạn max 5 điểm mỗi token
        if (score > 0) matchedToken++;
        totalScore += score;
    }
    totalScore += matchedToken * 10;  // cộng thêm điểm boost
    return totalScore;
}

Giới hạn điểm của mỗi token tránh việc lặp nhiều lần làm lệch điểm.

Thưởng điểm nếu tài liệu có nhiều token trong truy vấn.

Kết quả

Lỗi ban đầu phần nào cải thiện, nhưng vẫn còn vướng mắc việc giá trị điểm tăng phi tuyến tính và dựa trên số đếm thô.

Phần 3: Rendimento Giảm Dần – Giới Hạn Mềm

Thay vì cắt cứng điểm tối đa cho một token, ta áp dụng hàm giảm dần (decay) cho các lần xuất hiện token.

Công thức:

decay thường chọn nhỏ hơn 1, ví dụ 0.97.

Tần suất càng cao, điểm tăng chậm lại.

Ví dụ:

Tần suất 6 cho decay=0.97 → điểm xấp xỉ 5.4 thay vì 6.

Tần suất 50 cho decay=0.97 cho kết quả điểm nhỏ hơn nhiều so với 50.

Mã nguồn:

public double GetScore(List<string> queryTokens, Document doc, double decay = 0.97){
    double totalScore = 0;
    int matchedToken = 0;
    foreach (var token in queryTokens) {
        int frequency = doc.ContentTokens.Count(t => t == token.ToLowerInvariant());
        if (frequency > 0) matchedToken++;
        double freqScore = (1 - Math.Pow(decay, frequency)) / (1 - decay);
        totalScore += freqScore;
    }
    if (matchedToken == queryTokens.Count) 
        totalScore += matchedToken * 10;  // boost nếu đủ token
    return totalScore;
}

Lợi ích:

Tránh tăng điểm vô lý khi một token xuất hiện rất nhiều lần.

Điểm tăng giảm dần, hợp lý với tần suất.

Phần 4: TF-IDF – Cân Bằng Tần Suất và Độ Hiếm Của Token

Tầm quan trọng của độ hiếm token

Các token phổ biến như "le", "est" xuất hiện ở hầu hết tài liệu nên không giúp phân biệt tốt.

Token hiếm hơn như "animal" có giá trị thông tin cao hơn.

Định nghĩa IDF (Inverse Document Frequency)

( N ): Tổng số tài liệu.

( n_t ): Số tài liệu chứa token t.

Điểm TF-IDF

Với TF áp dụng decay như trên.

Mã nguồn tích hợp TF-IDF

public double GetScore(List<string> queryTokens, Document doc, double decay = 0.97){
    double totalScore = 0;
    foreach (var token in queryTokens) {
        int frequency = doc.ContentTokens.Count(t => t == token.ToLowerInvariant());
        if (frequency == 0) continue;
        int df = ReversedIndex[token].Count;
        double idf = Math.Log((double)Documents.Count / (1 + df));
        double tf = (1 - Math.Pow(decay, frequency)) / (1 - decay);
        totalScore += tf * idf;
    }
    return totalScore;
}

Ưu điểm:

Tài liệu chứa token hiếm được ưu tiên hơn.

Không cần boost điểm bằng số token match như cách trước.

Cho điểm phù hợp chính xác hơn.

Phần 5: Thuật Toán BM25 – Nâng Cao Hiệu Quả Tìm Kiếm

Giới thiệu BM25

BM25 là một cải tiến của TF-IDF, nhằm xử lý các hạn chế như:

Tài liệu dài hơn thường có điểm cao hơn dù chưa chắc phù hợp.

Điều chỉnh độ bão hòa tần suất (saturation) tốt hơn.

Công thức BM25

Trong đó:

Ký hiệu	Ý nghĩa
( f(t,d) )	Tần suất token ( t ) trong tài liệu ( d )
( k_1 )	Tham số kiểm soát độ bão hòa của tần suất (thường 1.5)
( b )	Tham số chuẩn hóa theo độ dài tài liệu (thường 0.75)
(	d	)	Độ dài tài liệu (số token)
( avgdl )	Độ dài trung bình toàn bộ tài liệu
( IDF(t) )	Trung số nghịch đảo của số tài liệu chứa token ( t )

Ví dụ minh họa

Giả sử chúng ta chọn ( k_1 = 1.5 ), ( b = 0.75 ).

Độ dài trung bình ( avgdl = 6 ).

Tính điểm cho token "noir" trong doc1 (độ dài 8), với tần suất ( f = 1 ) và IDF khoảng 0.916.

Sau khi thay các giá trị vào công thức, ta tính được điểm cụ thể cho tài liệu.

Mã nguồn BM25

public double GetScore(List<string> queryTokens, Document doc){
    double k1 = 1.5;
    double b = 0.75;
    double score = 0;
    double avgDocLength = Documents.Average(d => d.ContentTokens.Count);

    foreach (var token in queryTokens) {
        int tf = doc.ContentTokens.Count(t => t == token.ToLowerInvariant());
        if (tf == 0 || !ReversedIndex.ContainsKey(token)) continue;

        int df = ReversedIndex[token].Count;
        double idf = Math.Log((double)Documents.Count / (1 + df));

        double numerator = tf * (k1 + 1);
        double denominator = tf + k1 * (1 - b + b * (doc.ContentTokens.Count / avgDocLength));
        score += idf * (numerator / denominator);
    }

    return score;
}

Ưu điểm BM25:

Điều chỉnh phù hợp giữa tần suất token và độ dài tài liệu.

Không ưu tiên quá mức các tài liệu quá dài.

Phù hợp với các hệ thống tìm kiếm hiện đại, như Elasticsearch, Lucene, Solr.

Kết Luận

Việc đánh giá điểm phù hợp tài liệu là nền tảng quan trọng để đưa ra kết quả tìm kiếm chất lượng và đúng mục đích người dùng. Qua bài viết, chúng ta đã đi từ cách tính điểm đơn giản dựa trên tần suất token đến các giải pháp phức tạp như TF-IDF và BM25, với các cải tiến giúp giải quyết các vấn đề như:

Ưu tiên tài liệu có token phù hợp hơn thay vì tài liệu mới nhất

Giới hạn tăng điểm khi token lặp lại nhiều lần

Đưa vào yếu tố hiếm token để tăng tính phân biệt

Điều chỉnh điểm theo độ dài tài liệu để tránh thiên vị

Tùy vào nhu cầu và đặc điểm dữ liệu, bạn có thể áp dụng một hoặc kết hợp nhiều phương pháp để tối ưu hiệu suất tìm kiếm.

Đừng quên rằng các yếu tố khác như tìm kiếm trong tiêu đề, ngày cập nhật hoặc vị trí tài liệu cũng rất quan trọng và có thể được tính thêm vào điểm số cuối cùng để tăng độ chính xác.

Hãy áp dụng ngay hôm nay để nâng cao trải nghiệm tìm kiếm trong hệ thống của bạn!

Tham Khảo

Manning, C. D., Raghavan, P., & Schütze, H. (2008). Introduction to Information Retrieval. Cambridge University Press.

Jarvelin, K., & Kekalainen, J. (2002). Cumulated gain-based evaluation of IR techniques. ACM Transactions on Information Systems.

Elasticsearch Documentation on BM25 – https://www.elastic.co/guide/en/elasticsearch/reference/current/index-modules-similarity.html

Dev.to Article: Ranking Algorithms Explained – https://dev.to/mozillazg/how-to-rank-search-results-with-tf-idf-and-bm25-4l4m