Công cụ tìm kiếm được viết bằng 80 dòng Python

 (alexmolas.com)
6 điểm bởi GN⁺ 2024-02-08 | 1 bình luận | Chia sẻ qua WhatsApp
  • microsearch là một bản triển khai đồ chơi nhằm trực tiếp hiểu cách hoạt động bên trong của công cụ tìm kiếm; lớp công cụ tìm kiếm cốt lõi có chưa đến 80 dòng, nhưng toàn bộ dự án lớn hơn khi tính cả crawler, API và template HTML
  • Xuất phát từ vấn đề các website và blog nhỏ khó được công cụ tìm kiếm lớn phát hiện tốt, dự án thu thập bài viết từ 642 feed RSS để tạo dữ liệu tìm kiếm
  • Với crawl bất đồng bộ dựa trên asyncio, thời gian thu thập giảm từ 20 phút xuống 20 giây, và phần nội dung đã làm sạch được lưu dưới dạng dữ liệu Parquet
  • Tìm kiếm hoạt động trên chỉ mục đảo liên kết từ với số lần xuất hiện theo URL, và dùng BM25 dựa trên nội dung thay vì PageRank dựa trên liên kết để xếp hạng kết quả
  • Giao diện FastAPI cung cấp ô tìm kiếm và trang kết quả, nhưng vẫn chưa có các tính năng như toán tử truy vấn, chỉ mục n-gram, mở rộng truy vấn/tài liệu, hay lập chỉ mục trong lúc crawl

Mục tiêu và phạm vi của microsearch

  • microsearch là một bản triển khai công cụ tìm kiếm bằng Python được công bố trên GitHub repository
  • Mục tiêu không phải là một công cụ tìm kiếm cho production, mà là tạo ra một ví dụ đồ chơi có thể dùng được để cho thấy công cụ tìm kiếm vận hành nội bộ ra sao
  • Đối tượng tìm kiếm gần với các website và blog nhỏ vốn khó được tìm thấy trong cuộc cạnh tranh SEO trên Google
  • Phần triển khai công cụ tìm kiếm cốt lõi có chưa đến 80 dòng, nhưng nếu tính cả mã phụ trợ như crawler dữ liệu, API và template HTML thì toàn bộ dự án lớn hơn
  • Bản triển khai được tạo ra trong quá trình làm việc với Solr và Lucene để hiểu sâu hơn cách công cụ tìm kiếm hoạt động

Crawler dựa trên RSS

  • Để tạo dữ liệu cho việc tìm kiếm, dự án crawl các feed RSS của blog
  • Tổng cộng đã dùng 642 feed RSS
    • khoảng 100 feed là từ các blog thường đọc về ML, khoa học dữ liệu, toán học, v.v.
    • khoảng 500 feed còn lại được lấy từ dự án surprisetalk blogs.hn
  • Quy trình crawl là trích xuất URL bài viết từ từng feed RSS, tải HTML của bài viết, rồi làm sạch phần văn bản nội dung
  • Việc làm sạch HTML dùng BeautifulSoup để loại bỏ script và style, rồi chuẩn hóa xuống dòng và khoảng trắng để chuyển thành văn bản
  • Nhờ crawl bất đồng bộ dùng aiohttp và asyncio, thời gian chạy giảm từ 20 phút xuống 20 giây
  • Kết quả được tạo thành DataFrame chứa URL và nội dung đã làm sạch, rồi lưu vào output.parquet

Cấu trúc chỉ mục đảo

  • Cấu trúc dữ liệu cốt lõi đầu tiên của công cụ tìm kiếm là chỉ mục đảo
  • Chỉ mục đảo ánh xạ từ khóa tới tài liệu, giúp nhanh chóng tìm ra tài liệu nào chứa một từ cụ thể
  • Bản triển khai dùng defaultdict có dạng dict[str, dict[str, int]]
    • khóa bên ngoài là từ
    • khóa bên trong là URL
    • giá trị bên trong là số lần từ đó xuất hiện trong tài liệu của URL tương ứng
  • Lớp SearchEngine có hai dictionary nội bộ
    • _index: lưu số lần xuất hiện theo URL của từng từ
    • _documents: lưu nội dung gốc theo từng URL
  • index(url, content) chuẩn hóa nội dung rồi tách theo khoảng trắng, sau đó tăng số lần xuất hiện theo URL của từng từ
  • bulk_index() nhận danh sách URL và nội dung để lập chỉ mục nhiều tài liệu cùng lúc
  • get_urls(keyword) chuẩn hóa từ khóa rồi trả về các URL chứa từ đó cùng số lần xuất hiện

Chuẩn hóa chuỗi và tìm kiếm cơ bản

  • Chuẩn hóa chuỗi là thay dấu câu bằng khoảng trắng, dọn khoảng trắng thừa, rồi chuyển sang chữ thường
  • Để giảm khác biệt hoa/thường, Foo và foo được xử lý như cùng một từ khóa
  • Nếu lập chỉ mục hai tài liệu ví dụ, kết quả tìm foo sẽ trả về cả hai tài liệu
    • Foo: Hello, World! My name is Foo!
    • Bar: Hello, World! My name is Bar, I'm not Foo!
  • Ở giai đoạn này chỉ biết tài liệu có chứa từ tìm kiếm hay không và chứa bao nhiêu lần, nên cần một cơ chế xếp hạng riêng để quyết định thứ tự kết quả

Bộ xếp hạng BM25

  • Việc sắp xếp kết quả tìm kiếm dùng BM25
  • PageRank xếp hạng tài liệu dựa trên liên kết, còn BM25 tính điểm dựa trên nội dung tài liệu
  • SearchEngine có các tham số mặc định k1=1.5, b=0.75 để tính BM25
  • Lớp này cung cấp các thuộc tính cần cho việc tính xếp hạng
    • posts: danh sách URL đã được lập chỉ mục
    • number_of_documents: tổng số tài liệu
    • avdl: độ dài tài liệu trung bình
  • idf(kw) tính tần suất tài liệu nghịch đảo của một từ khóa cụ thể
    • tổng số tài liệu là N
    • số tài liệu chứa từ khóa đó là n_kw
    • dùng công thức log((N - n_kw + 0.5) / (n_kw + 0.5) + 1)
  • bm25(kw) tính điểm BM25 cho từng URL có chứa từ khóa đó
  • search(query) chuẩn hóa truy vấn rồi tách thành các từ, sau đó cộng dồn điểm BM25 của từng từ theo URL để trả về kết quả
  • Trong ví dụ, nếu chỉ tìm foo thì tài liệu Foo có điểm cao hơn Bar, còn khi tìm foo bar thì tài liệu Bar có điểm cao hơn

Giao diện FastAPI

  • Công cụ tìm kiếm được cung cấp dưới dạng một ứng dụng FastAPI nhỏ
  • Ứng dụng tạo một instance SearchEngine, và khi khởi động sẽ đọc URL cùng nội dung từ dữ liệu Parquet rồi lập chỉ mục bằng bulk_index()
  • Có ba route chính
    • /: render trang tìm kiếm và truyền danh sách bài viết đã lập chỉ mục
    • /results/{query}: tìm truy vấn và hiển thị 5 URL đứng đầu trên trang kết quả
    • /about: render trang giới thiệu
  • Kết quả được sắp theo điểm giảm dần rồi chỉ chọn top-N URL
  • UI và UX còn nhiều chỗ để cải thiện, nhưng việc tìm kiếm chạy nhanh và kết quả cũng khá ổn

Tính năng còn thiếu và giới hạn

  • Bản triển khai còn thiếu nhiều tính năng thường được kỳ vọng ở một công cụ tìm kiếm thực tế
  • Không có toán tử truy vấn
    • Ví dụ, chưa hỗ trợ kiểu tìm kiếm loại trừ một từ như how to build a search engine -solr của Google
  • Không có chỉ mục n-gram
    • Chưa hỗ trợ cách tìm chỉ những tài liệu có hai từ xuất hiện theo đúng thứ tự như "search engine"
  • Không có mở rộng truy vấn hoặc tài liệu
    • Nếu tìm engine thì tài liệu chứa engines sẽ không tự động được tìm ra
  • Crawl và lập chỉ mục đang tách rời nhau
    • Có thể tích hợp theo hướng lập chỉ mục ngay khi nhận được tài liệu, và quá trình này cũng có thể làm bất đồng bộ

Bước tiếp theo

  • Dự án này giúp tăng thêm trực giác về cách Solr hoạt động bên trong
  • Nó cũng cho thấy mã bất đồng bộ đem lại hiệu quả lớn trong các tác vụ thiên về IO
  • Bước tiếp theo là bổ sung khả năng tìm kiếm ngữ nghĩa cho công cụ tìm kiếm
  • Tác giả đã thử nghiệm với mô hình embedding và ANN, và việc đưa tính năng đó vào microsearch là công việc tiếp theo

Bài viết liên quan

1 bình luận

 
GN⁺ 2024-02-08
Các ý kiến trên Hacker News

  • Cái này thực sự rất hay. Tôi đang làm một công cụ tìm kiếm BM25 khá nhanh bằng Pandas để thử nghiệm cục bộ: https://github.com/softwaredoug/searcharray
    Lý do dùng Pandas là vì chỉ BM25 thôi thì chưa đủ; tôi muốn dễ dàng tính toán và kết hợp các yếu tố khác như độ mới, độ phổ biến bằng pandas/numpy
    Nhân tiện, tìm kiếm cụm từ mới là phần khó. Khớp cụm từ có rất nhiều trường hợp biên, và còn phải xét cả những thứ như slop. Thông tin vị trí cũng phải được nén sao cho dùng ít bộ nhớ nhất có thể: https://github.com/softwaredoug/searcharray/blob/main/searcharray/utils/roaringish.py

    • Tôi từng xử lý khớp cụm từ trong một dự án đồ chơi: https://github.com/vasilionjea/lofi-dx/blob/main/test/search/inverted-search.test.ts#L140
      Tôi nghĩ mình đã kiểm thử khá kỹ, nhưng rất mong nhận được phản hồi. Thông tin vị trí được mã hóa delta rồi mã hóa bằng base36
    • Tôi tò mò liệu việc thêm phân tích cảm xúc có giúp ích cho xử lý cụm từ không, hay ngược lại còn gây hại. Cụm từ khó xử lý, và tôi đang suy nghĩ xem có thể làm gì để cải thiện hiệu năng
    • Tôi tò mò vì sao bạn tìm thấy bài này và bình luận nhanh đến vậy. Muốn biết bạn có dùng kiểu công cụ giám sát tìm kiếm để quét trang đầu nhằm tìm từ khóa quan tâm không, hay chỉ là tình cờ

  • Nói đúng. Phần lớn độ khó trong tìm kiếm nằm ở việc xử lý quy mô dữ liệu. Bản thân logic thì dễ đến đáng ngạc nhiên, hoặc có thể được làm cho dễ
    Tất nhiên cũng có thể làm nó phức tạp vô tận, nhưng dự án này đã lược bỏ tốt những phần không cần thiết. Nếu tiếp cận không phải như vấn đề làm công cụ tìm kiếm lớn hơn, mà là làm dữ liệu nhỏ hơn về mặt vật lý hoặc tăng tỷ lệ tín hiệu trên nhiễu, thì có thể đi được khá xa

  • Nhìn vào src/microsearch/engine.py có đoạn như SearchEngine.__init__(self, k1: float = 1.5, b: float = 0.75), nhưng tôi hoàn toàn không biết k1 hay b là gì, và cả tệp không có lấy một chú thích nào
    Dạo này chú thích không còn thịnh hành nữa sao? _documents có vẻ là dict với khóa là URL và giá trị là nội dung của URL đó, nhưng cũng có thể tôi sai. Đây đã có thể là tài liệu để học cách xây dựng và mở rộng công cụ tìm kiếm, nhưng vì không được tài liệu hóa nên chất lượng mã hơi đáng tiếc

    • Phần đó được giải thích trong bài viết, và chính bài viết đóng vai trò như tài liệu cho mã. Liên kết BM25 dẫn tới nền tảng toán học, và nếu tìm thêm một chút về các tham số BM25 thì cũng sẽ thấy các bài liên quan nói về cách chọn chúng
    • Muốn tiêu đề bài viết gây chú ý thì phải giảm số dòng mã xuống mức tối đa ;)
      Đùa vậy thôi, tôi đồng ý rằng thông thường có cả tài liệu lẫn mã đi cùng nhau thì tốt hơn. Tuy nhiên trong trường hợp này đây là dự án giáo dục, nên tôi tách mã và tài liệu, rồi tài liệu hóa mã trong bài blog
    • Tôi đang dùng di động nên không xem kỹ được, nhưng k1 và b là các giá trị trọng số chuẩn dùng trong TF-IDF hoặc BM25, và ở đây là BM25
      Có chú thích thì hữu ích, nhưng với người quen vấn đề này thì đây cũng là những tên có thể nhận ra ngay
    • k1 và b là các tham số điều chỉnh của hàm xếp hạng BM25. Đây không phải tên do tác giả bài gốc tự đặt, mà hầu như mọi triển khai và giáo trình đều dùng các tên biến này
      Để người biết lĩnh vực truy hồi thông tin hiểu được, đặt tên là k1 và b thực ra mới đúng: https://en.wikipedia.org/wiki/Okapi_BM25
    • Nhìn những kiểu như a: float tôi luôn nhớ tới bài nói chuyện của Rich Hickey rằng “thứ ta cần không phải là kiểu, mà là tên gọi đúng”
      Tôi rất ghét xu hướng dùng tên biến một chữ cái không có giải thích, cảm giác như đến từ Go, rồi lạm dụng hệ thống kiểu như một công cụ hỗ trợ đặt tên. Tên gọi có thể truyền tải thông tin ngữ nghĩa về việc chương trình làm gì, nên cần dùng cho đúng

  • Tôi không hiểu việc dùng phụ thuộc bên ngoài mà lại khoe số dòng mã thay vì tổng số \r\n có ý nghĩa gì
    Không có đơn vị SI để đo codebase, nhưng tôi nghĩ tải nhận thức thì bằng cách nào đó vẫn phải được đo

    • Không phải chuẩn chính thức, nhưng nhóm chúng tôi thỉnh thoảng mượn cách nói từ https://grugbrain.dev rằng “mã này không grug” hoặc “mã này khá grug”
    • Bản thân công cụ tìm kiếm 80 dòng không dùng phụ thuộc bên ngoài. Nó chỉ import collections, math, string, toàn bộ đều là thư viện chuẩn
      Tuy nhiên nói chính xác hơn có lẽ nên gọi là “engine của công cụ tìm kiếm”. Crawler và giao diện không nằm trong 80 dòng đó nhưng dưới dạng nào đó vẫn cần có, và phần triển khai được đưa ra làm tăng đáng kể cả số dòng lẫn thư viện. Dù vậy các thư viện đó không liên quan đến bản thân công cụ tìm kiếm. Nếu bắt đầu tính cả các phụ thuộc chung như pandas hay fastapi, thì có lẽ còn phải tính cả hàng triệu dòng của hệ điều hành, firmware card mạng, và độ phức tạp phần cứng nữa
    • Có lý do gì mà ta không nên chúc mừng thành quả của ngành đã giúp làm được những thứ như vậy trong 80 dòng không?
    • Ở đây thì có ý nghĩa. Nếu là “công cụ tìm kiếm viết bằng 4000 dòng Python” thì đa số người ta sẽ lướt qua, nhưng 80 dòng thì đủ ngắn để đáng mở ra xem
    • Theo cách cũ thì có độ phức tạp chu trình

  • Tôi thích. Cũng có thể có một công cụ gợi ý dưới 20 dòng dùng cùng với công cụ tìm kiếm. Nếu lưu nhật ký phiên của các URL đã nhấp, có thể nhìn vào cửa sổ trượt phía sau URL hiện tại trong mỗi phiên, gán trọng số cao hơn cho các liên kết gần hơn để tạo danh sách gợi ý
    Sắp xếp kết quả gợi ý và chỉ giữ lại N mục đầu sẽ cho ra danh sách URL được gợi ý cho một URL cụ thể. Chỉnh thêm một chút thì có thể trộn truy vấn tìm kiếm đã nhập và URL đã nhấp vào nhật ký để rút ra cả đề xuất sửa chính tả

  • Rất hay và mang tính giáo dục. Chỉ là đừng đem triển khai nhé :-)
    Trước đây tôi từng cần một thứ tương tự, nhưng quy mô lớn hơn một chút, khoảng vài chục nghìn tài liệu, và câu trả lời, như mọi khi, là sqlite. Về mặt cấu trúc thì giống như ở đây, chỉ khác là lớp lưu trữ bền vững cho chỉ mục đảo đã được người khác viết hộ.

    • SQLite FTS được tôi dùng ở gần như mọi nơi, và chưa từng làm tôi thất vọng lần nào.
    • Thực ra còn có cả cùng công thức đó nữa. Nhờ bình luận này mà tôi có cảm giác như “rùng mình vì hiểu ra”.

  • Google nếu tìm bằng dấu ngoặc kép như "search engine" thì chỉ hiển thị các kết quả trong đó hai từ xuất hiện theo đúng thứ tự đó.
    Ít nhất là trong một số trường hợp thì đúng vậy, nhưng tiếc là không phải lúc nào cũng thế. Thứ người dùng nâng cao muốn là “grep cho web”, chứ không phải “thứ Google muốn nói rằng họ nên xem”.

    • Tôi dám chắc là gần như không ai thực sự muốn “grep cho web”. So với một công cụ tìm kiếm chỉ làm mở rộng truy vấn rất nhỏ thôi, grep cho web rõ ràng là tệ hơn.
      Đúng là Google đang tự cho mình quá nhiều quyền tự do khi diễn giải truy vấn, nhưng có rất nhiều xử lý mà bất kỳ công cụ tìm kiếm nào làm cũng chắc chắn tốt hơn là không làm. Vấn đề của Google Search hiện nay là khó suy luận vì sao lại ra các kết quả như vậy, và có vẻ là do họ phụ thuộc quá nhiều vào embedding cho việc so khớp chuỗi. Khi "cat food" khớp với "dog restaurant", tức là trong không gian embedding thì gần nhau về mặt ngữ nghĩa nhưng lại không phù hợp với suy luận của con người, điều đó rất gây bực bội.

  • Tôi nghĩ nói là 80 dòng mã trong khi dùng các thư viện bên ngoài như feedparser, bs4 thì không công bằng.

    • Nếu nó được xây trên elasticsearch thì tôi đồng ý, nhưng nếu phần công cụ tìm kiếm thực sự được triển khai trong 80 dòng đó thì tôi thấy là công bằng. Những thư viện được import là loại không nên tự triển khai.
      Thỉnh thoảng có bài “tự làm công cụ tìm kiếm của riêng bạn” nhưng thực ra lại là hướng dẫn cài searxng hoặc yacy; trường hợp này khác với những bài đó.
    • Tôi nghĩ ổn nếu các dependency đó rất phổ biến và thuộc dòng chính.

  • Hay đấy. Thêm chức năng tìm kiếm mờ vào đây có lẽ cũng không quá khó. Ví dụ, để tìm "hackrnew" khớp với "hackernews", có thể tìm các kết quả có khoảng cách chỉnh sửa tiền tố dưới một ngưỡng nào đó.
    Ý tưởng cơ bản là thêm một chỉ mục đảo nữa, trong đó khóa là n-gram (thường là 3-gram) của các từ trong tập tài liệu, còn posting là từ hoặc ID từ có chứa n-gram đó. Có thể dùng bổ đề PED(x, y) <= delta thì |N(x) ∩ N(y)| >= |N(x)| - n ∙ delta. Tính n-gram của đầu vào x, lấy posting của từng n-gram rồi gộp các bản trùng, ta có được số n-gram mà mỗi từ ứng viên y chia sẻ. Nếu con số này lớn hơn ngưỡng thì mới tính PED thật sự, còn nếu nhỏ hơn thì bỏ qua, nhờ đó giảm mạnh các phép tính đắt đỏ.
    Sau đó chỉ cần dùng danh sách từ thu được để truy vấn chỉ mục hiện có. Trước đây khi làm công cụ tìm kiếm mờ phía client bằng JS cho https://dont.watch/, tôi đã dùng cách tiếp cận này. Nếu xem trong mã JS, bạn sẽ thấy chỉ mục đảo và chỉ mục n-gram đã nén được chuyển thẳng vào file JS. Công cụ tìm kiếm thực tế khoảng 300 dòng JS, không có phụ thuộc bên ngoài, và chỉ có vài heuristic rất cơ bản để cải thiện kết quả tìm kiếm.

    • Với cách đó thì kích thước chỉ mục tăng lên bao nhiêu?