Jam-Text: Cỗ Máy Lập Chỉ Mục Văn Bản Tốc Độ Với Go Và SimHash

Lê Lân

16/06/2025

Jam-Text: Công Cụ Tạo Chỉ Mục Văn Bản Nhanh Và Linh Hoạt Bằng Go

Mở Đầu

Trong thế giới dữ liệu bùng nổ hiện nay, việc xử lý và tìm kiếm thông tin trong các tập tin văn bản khổng lồ trở thành bài toán cần giải quyết nhanh và hiệu quả.

Tháng trước, tôi cùng với nhóm bạn tài năng gồm Elijah, Kevin, Jerome và Godwin tham gia một cuộc thi hackathon với thử thách xây dựng một text indexer nhanh, có khả năng mở rộng, trong ngôn ngữ Go. Mục tiêu là tạo ra một công cụ có thể phân tích các tập tin văn bản lớn, xây dựng “dấu vân tay” cho từng phần văn bản để tìm kiếm tương tự một cách nhanh chóng và chính xác.

Bài viết này sẽ đưa bạn đọc đi qua từng bước phát triển Jam-Text — từ ý tưởng, kỹ thuật áp dụng, đến những khó khăn và bài học kinh nghiệm. Nếu bạn đang quan tâm đến xử lý văn bản lớn, lập chỉ mục dữ liệu hay các thuật toán similarity, đây sẽ là tài liệu tham khảo quý giá.

Thử Thách: Tốc Độ, Quy Mô Và Độ Tương Tự

Phát Đề Bài Toán

Hackathon đưa ra yêu cầu tưởng chừng đơn giản, nhưng lại đầy thách thức:

Phân chia tập tin văn bản thành các đoạn nhỏ (mỗi đoạn khoảng 4KB)

Tạo SimHash fingerprint cho từng đoạn

Xây dựng chỉ mục lưu trữ trong bộ nhớ

Thực hiện tra cứu nhanh chóng

Thêm điểm cộng nếu áp dụng song song đa luồng và hỗ trợ tìm kiếm gần đúng (fuzzy matching).

Định Nghĩa Về Tính Tương Tự

Một câu hỏi không đơn giản là: “Tương tự là gì?”

Với phát hiện đạo văn, ta ưu tiên các kết quả khớp chính xác hoặc gần chính xác.

Với tìm kiếm nội dung, ta cần xét đến ý nghĩa ngữ cảnh (ví dụ: “cat” và “feline” có thể được xem là tương tự).

Giải pháp của chúng tôi là kết hợp:

SimHash cho tra cứu chính xác.

Vector similarity dựa trên kỹ thuật random hyperplanes để phục vụ truy vấn gần đúng và mở rộng quy mô.

Việc kết hợp hai kỹ thuật giúp Jam-Text vừa thỏa mãn yêu cầu CLI, vừa nâng cao khả năng tìm kiếm linh hoạt thông minh.

Ý Tưởng Lớn Từ Locality-Sensitive Hashing (LSH)

Nguồn Cảm Hứng

Chúng tôi lấy cảm hứng từ bài báo của Moses Charikar với tiêu đề Similarity Estimation Techniques from Rounding Algorithms, giới thiệu kỹ thuật Locality-Sensitive Hashing (LSH) — một giải pháp giúp biến đổi dữ liệu phức tạp (như đoạn văn bản) thành các biểu diễn gọn, dễ so sánh.

Các Phương Pháp LSH Chính

Phương pháp	Ưu điểm chính	Ứng dụng
Min-Hash	Phát hiện sự trùng lặp và chồng lắp	Phát hiện sao chép, trùng lặp
Random Hyperplanes	Biến đổi thành vector, đo khoảng cách cosine	Tìm kiếm ngữ nghĩa (semantic)
Earth Mover Distance	So sánh phân phối phức tạp (không sử dụng)	Phức tạp, không thích hợp

Chúng tôi chọn random hyperplanes để tận dụng sức mạnh của vector similarity, đồng thời vẫn giữ SimHash để thực hiện những truy vấn chính xác theo yêu cầu.

Quá Trình Phát Triển Jam-Text

Bước 1: Phân Đoạn Văn Bản

Đầu tiên, chúng tôi phát triển module chunker để chia tệp vào các đoạn cố định 4KB. Phiên bản đầu tiên chạy đơn luồng gây chậm với các tập tin lớn, nên nhóm triển khai worker pool dùng goroutines xử lý song song theo từng phần riêng biệt của file.

func (c *Chunker) ProcessFile(filePath string) ([]Chunk, error) {
    fileSize := getFileSize(filePath)
    numWorkers := 4
    chunkChan := make(chan Chunk, 100)
    var wg sync.WaitGroup
    sectionSize := fileSize / int64(numWorkers)

    for i := 0; i < numWorkers; i++ {
        start := int64(i) * sectionSize
        end := start + sectionSize
        if i == numWorkers-1 {
            end = fileSize
        }
        wg.Add(1)
        go c.processSection(filePath, start, end, chunkChan)
    }

    go func() {
        wg.Wait()
        close(chunkChan)
    }()

    var chunks []Chunk
    for chunk := range chunkChan {
        chunks = append(chunks, chunk)
    }
    return chunks, nil
}

Bước 2: Tạo Dấu Vân Tay (Fingerprint)

Module simhash chịu trách nhiệm tạo fingerprint cho mỗi đoạn văn bản:

SimHash chuyển văn bản thành giá trị 64-bit nhanh và nhỏ gọn.

Vector sketches biểu diễn đoạn văn bản dưới dạng vectơ (đếm số từ trên tập từ vựng đơn giản), sau đó chuyển thành mã 10-bit sử dụng random hyperplanes.

type Fingerprint struct {
    SimHash     uint64
    VecSketches []int
}

func Hash(content []byte) Fingerprint {
    vector := toVector(string(content))
    return Fingerprint{
        SimHash:     simHash(string(content)),
        VecSketches: vectorSketches(vector, 10),
    }
}

Bước 3: Xây Dựng Chỉ Mục Với LSH

Gói index lưu trữ dấu vân tay SimHash để tra cứu chính xác, đồng thời dùng LSH cho các vector sketch giúp tìm kiếm nhanh gần đúng. Việc đồng bộ hóa qua mutex giúp đảm bảo an toàn đa luồng.

type Index struct {
    Entries    map[uint64]IndexEntry
    LSHBuckets map[int][]IndexEntry
    mu         sync.RWMutex
}

func (idx *Index) AddEntry(fp simhash.Fingerprint, offset int64) {
    idx.mu.Lock()
    defer idx.mu.Unlock()
    idx.Entries[fp.SimHash] = IndexEntry{Fingerprint: fp, Offsets: []int64{offset}}
    bucketKey := fp.VecSketches[0]
    idx.LSHBuckets[bucketKey] = append(idx.LSHBuckets[bucketKey], entry)
}

Bước 4: CLI Tương Tác Người Dùng

Phần giao diện dòng lệnh cho phép các thao tác:

index : tạo chỉ mục từ file văn bản lớn.

lookup : tra cứu bằng SimHash.

compare : so sánh 2 file.

fuzzy : tra cứu gần đúng với ngưỡng độ tương tự.

Ví dụ sử dụng:

./textindex -c index -i large_text.txt -s 4096 -o index.idx
./textindex -c lookup -i index.idx -h 3eff1b2c98a6
./textindex -c compare -i doc1.txt -i2 doc2.txt -o report.txt
./textindex -c fuzzy -i testdata.idx -h $HASH -threshold 0.8

Những Thử Thách Và Thành Quả

Từ Vựng Và Tính Năng Vector

Việc xây dựng từ vựng động cho vector similarity làm chậm quá trình. Để demo nhanh, nhóm chủ động pre-sample từ vựng từ file đầu vào, cải thiện tốc độ đáng kể nhưng chưa hoàn hảo.

Cân Bằng Tốc Độ Và Bộ Nhớ

SimHash gọn nhẹ, 8 byte/chunk.

Thêm 10 vector sketches tăng dung lượng lên khoảng 18 byte/chunk.

Chúng tôi tinh chỉnh giảm số lượng sketch từ 20 xuống 10 để vừa đủ cho fuzzy matching đồng thời tiết kiệm RAM.

Tăng Quy Mô Với LSH

Dùng LSH giúp tránh phải dò tuyến tính, cải thiện hiệu quả tra cứu. Nhưng việc cân chỉnh kích thước sketch với tỷ lệ lỗi giả (false positives) vẫn là bài toán thách thức.

Việc tuning tham số LSH là yếu tố then chốt để Jam-Text hoạt động mượt mà trong thực tế.

Kế Hoạch Tương Lai

Incremental Indexing: cập nhật chỉ mục theo thời gian thực mà không cần lập lại toàn bộ.

Approximate Nearest Neighbors (ANN): tăng tốc tìm kiếm fuzzy.

Lưu trữ bền vững: tích hợp công nghệ như LSM tree hay RocksDB để lưu chỉ mục ra đĩa.

Kết Luận

Jam-Text là kết quả của sự kết hợp sáng tạo giữa các kỹ thuật tiên tiến như SimHash và LSH, cùng với giải pháp kỹ thuật đa luồng trong Go. Nó đem lại một công cụ mạnh mẽ để xử lý và tìm kiếm văn bản quy mô lớn một cách nhanh chóng, chính xác và linh hoạt.

Bạn có thể áp dụng những ý tưởng này để xây dựng các hệ thống xử lý dữ liệu lớn khác, hoặc tùy biến Jam-Text cho nhu cầu riêng.

Chúng tôi rất mong nhận được phản hồi và ý tưởng cải tiến từ cộng đồng — hãy cùng thảo luận nhé! 🚀

Tham Khảo

Charikar, M. (2002). Similarity Estimation Techniques from Rounding Algorithms. Link

Moses Charikar’s SimHash: SimHash Algorithm

Wikipedia contributors. Locality-sensitive hashing. Wikipedia, The Free Encyclopedia. Link

RocksDB Documentation. Link

Go Documentation. Concurrency patterns: https://golang.org/doc/effective_go#goroutines