Bạn chắc chắn đã thấy các tìm kiếm văn bản mờ ở khắp mọi nơi. Ví dụ bạn gõ "stck" nhưng bạn thực sự có nghĩa là "ngăn xếp"! Bao giờ tự hỏi làm thế nào để công cụ này hoạt động?
Có rất nhiều thuật toán để thực hiện kết hợp văn bản mờ, mỗi đối tượng có tính năng chuyên nghiệp và khuyết điểm riêng. Những người nổi tiếng nhất là chỉnh sửa khoảng cách và qgram. Tôi muốn tập trung vào qgrams ngày hôm nay và thực hiện một mẫu.
Về cơ bản, qgram là thuật toán kết hợp chuỗi mờ phù hợp nhất cho cơ sở dữ liệu quan hệ. Nó khá đơn giản. "q" trong qgram sẽ được thay thế bằng một số như 2 gam hoặc 3 gam hoặc thậm chí 4 gram.
2-gram có nghĩa là mỗi từ được chia thành một tập hợp gồm hai ký tự gram. "Stack" sẽ được chia thành một tập hợp {"st", "ta", "ac", "ck"} hoặc "cơ sở dữ liệu" sẽ được chia thành {"da", "at", "ta", "ba "," là "," se "}.
Khi từ được chia thành 2-gram, chúng tôi có thể tìm kiếm cơ sở dữ liệu cho một tập hợp các giá trị thay vì một chuỗi. Ví dụ: nếu người dùng nhập sai "stck", bất kỳ tìm kiếm nào cho "stck" sẽ không khớp với "ngăn xếp" vì "a" bị thiếu, nhưng tập hợp 2 "{" st "," tc "," ck "} có 2 hàng chung với bộ 2 ngăn xếp! Bingo chúng tôi tìm thấy một trận đấu khá gần. Nó không có điểm chung với bộ cơ sở dữ liệu 2 gram và chỉ có 1 điểm chung với bộ "stat" 2 gram để chúng tôi có thể dễ dàng đề xuất người dùng mà anh ta muốn nhập: "xếp chồng" đầu tiên hoặc thứ hai "sao ".
Bây giờ chúng ta hãy thực hiện nó bằng cách sử dụng Sql Server: Giả sử một số liệu từ giả định. Bạn cần phải có một mối quan hệ nhiều đến nhiều giữa 2grams và các từ.
CREATE TABLE Grams(twog char(2), wordId int, PRIMARY KEY (twog, wordId))
Bảng Gram nên được nhóm lại trên twog đầu tiên và sau đó là wordId để thực hiện. Khi bạn truy vấn một từ (ví dụ: ngăn xếp), bạn đặt gam trong bảng tạm thời. Đầu tiên cho phép tạo một vài triệu bản ghi giả.
--make millions of 2grams
DECLARE @i int =0
WHILE (@i<5000000)
BEGIN
-- a random 2gram
declare @rnum1 char = CHAR(CAST(RAND()*28 AS INT)+97)
declare @rnum2 char = CHAR(CAST(RAND()*28 AS INT)+97)
INS... INTO Grams (twog, wordId) VALUES (@rnum1 + @rnum2, CAST(RAND()*100000 AS int))
END
Bây giờ, hãy truy vấn từ "ngăn xếp" sẽ được chia thành: {'st', 'ta', 'ac', 'ck'} hai gram.
DECLARE @word TABLE(twog char(2)) -- 'stack'
INS... INTO @word VALUES ('st'), ('ta'), ('ac'), ('ck')
select wordId, count(*) from @word w inner join Grams g ON w.twog = g.twog
GROUP BY wordId
Bạn nên đảm bảo rằng Sql Server sử dụng một nhóm chỉ mục nhóm tìm kiếm (hoặc loockups) để chạy truy vấn này.Nó phải là sự lựa chọn tự nhiên nhưng đôi khi số liệu thống kê có thể bị hỏng hoặc lỗi thời và SqlServer có thể quyết định rằng việc quét toàn bộ sẽ rẻ hơn. Điều này thường xảy ra nếu nó không biết cardinality của bảng bên trái, ví dụ SqlServer có thể giả định rằng bảng @word là lớn và hàng triệu loockups sẽ đắt hơn một lần quét chỉ mục đầy đủ.