👋 Hi anh em, hôm nay mình muốn chia sẻ một case study nho nhỏ trong dự án mà mình đang làm. Cụ thể là bài toán lọc các từ khóa nhạy cảm. Đây là một bài toán nghe đơn giản nhưng khi đụng đến data thật với hàng trăm, hàng nghìn từ khóa thì lại phát sinh nhiều vấn đề thú vị về hiệu năng. Và thế là mình có dịp “đào bới” lại một giải thuật kinh điển: Aho-Corasick. 🚀
1. Vấn đề
Trong dự án hiện tại, nhóm mình đang phát triển một service – đóng vai trò trung gian để điều hướng và forward các request từ nhiều chatbot nội bộ sang các mô hình ngôn ngữ khác nhau (như OpenAI, Gemini, v.v.).
Trước khi chuyển request ra bên thứ ba, service này cần thực hiện tiền xử lý dữ liệu nhằm đảm bảo tính an toàn và tuân thủ quy tắc nội bộ. Một trong những bước quan trọng chính là lọc từ khóa nhạy cảm.
Việc lọc này giúp:
- Loại bỏ hoặc cảnh báo khi người dùng nhập những từ ngữ vi phạm chính sách (chửi tục, nhạy cảm chính trị, thông tin cá nhân…).
- Đảm bảo trải nghiệm an toàn và phù hợp với người dùng cuối. Tuy nhiên, với số lượng từ khóa nhạy cảm lên đến hàng trăm hay hàng nghìn, việc tìm kiếm theo cách thông thường (so sánh chuỗi từng từ với input) vừa tốn thời gian, vừa kém hiệu quả trên các đoạn văn bản dài.
2. Giải pháp
Khi bắt đầu xử lý bài toán, cách đầu tiên mình nghĩ tới là duyệt từng từ khóa rồi dùng IndexOf hoặc regex để kiểm tra trong đoạn text. Cách này thì dễ hiểu, dễ làm, nhưng khi số lượng từ khóa lên đến hàng trăm hay hàng nghìn thì tốc độ giảm rõ rệt, đặc biệt với những input rất dài.
Trong quá trình tìm hiểu, mình phát hiện ra một giải thuật kinh điển cho việc tìm kiếm nhiều mẫu cùng lúc, đó là Aho-Corasick. Ưu điểm của nó là có thể duyệt chuỗi đầu vào chỉ một lần mà vẫn phát hiện được tất cả các từ khóa, với độ phức tạp O(N + M + Z) (N là độ dài chuỗi, M là tổng độ dài của tất cả từ khóa, Z là số lần khớp).
May mắn là trong .NET đã có sẵn thư viện Ganss.Text.AhoCorasick cài đặt thuật toán này, nên mình có thể áp dụng ngay mà không cần tự viết lại từ đầu.
3. Triển khai
Cài đặt NuGet
dotnet add package AhoCorasick --version 2.0.279
Ví dụ code
using SharpToken;
using System;
using System.Diagnostics;
using System.Text;
public class ToxicWord
{ // array of toxic words public static readonly string[] _toxicWords = ["chó", "chó điên", "dm", "tổ sư"]; // get toxic words public static List<string> GetToxicsWords(int repeat = 1) { //return _toxicWords; return Enumerable.Range(0, repeat) .SelectMany(_ => _toxicWords) .ToList(); }
} using Ganss.Text;
using System.Diagnostics;
using System.Text;
using ToxicDetection; class PerfTest
{ static void Main() { Console.OutputEncoding = Encoding.UTF8; // Tạo danh sách từ nhạy cảm giả lập var keywords = ToxicWord.GetToxicsWords(1000); // Build input 128k * " abc", rải keyword var sb = new StringBuilder(); for (int i = 0; i < 100 * 1024; i++) { sb.Append(" abc"); if (i % 777 == 0) sb.Append(" chó điên "); // rải keyword thật } string input = sb.ToString(); Console.WriteLine("============== Thông tin Input =============="); Console.WriteLine($"Chuỗi ký tự dài : {input.Length:N0} ký tự"); //Console.WriteLine($"Tổng số token : {tokens.Count:N0}"); Console.WriteLine($"Số keyword : {keywords.Count}"); Console.WriteLine(); // ==================== // Naive Matching // ==================== var sw = Stopwatch.StartNew(); var naiveMatches = new List<string>(); foreach (var kw in keywords) { if (input.IndexOf(kw, StringComparison.OrdinalIgnoreCase) >= 0) naiveMatches.Add(kw); } sw.Stop(); Console.WriteLine("============== Naive Matching =============="); Console.WriteLine($"Thời gian : {sw.ElapsedMilliseconds} ms"); Console.WriteLine($"Số từ tìm thấy : {naiveMatches.Count}"); if (naiveMatches.Count > 0) Console.WriteLine($"Danh sách : {string.Join(", ", naiveMatches)}"); Console.WriteLine(); // ==================== // Aho-Corasick Matching // ==================== var ac = new AhoCorasick(keywords); sw.Restart(); var ahoMatches = new List<string>(); foreach (var m in ac.Search(input)) { ahoMatches.Add(m.Word); } sw.Stop(); Console.WriteLine("============== Aho-Corasick =============="); Console.WriteLine($"Thời gian : {sw.ElapsedMilliseconds} ms"); Console.WriteLine($"Số từ tìm thấy : {ahoMatches.Count}"); if (ahoMatches.Count > 0) Console.WriteLine($"Danh sách : {string.Join(", ", ahoMatches)}"); }
}
4. Kết quả
- Với chuỗi dài 410,920 ký tự, danh sách 43,800 từ khóa:
- Naive search mất 7,434s
- Aho-Corasick chỉ mất 5 ms.
- Kết quả cho thấy Aho-Corasick tối ưu vượt trội khi cần kiểm tra nhiều từ khóa trong văn bản lớn.