Câu hỏi đặt ra là cách kết hợp chuỗi được thực hiện để tìm các mục phù hợp bằng firefox 3 url bar. Kết hợp chuỗi con trên mỗi mục nhập có thể chậm. Thuật toán nào có thể được sử dụng để khớp ở bất kỳ vị trí nào một cách nhanh chóng?Thanh 'tuyệt vời' của Firefox khớp với các chuỗi như thế nào?
Cách thông thường để thực hiện kết hợp chuỗi con nhanh là tạo cấu trúc dữ liệu chứa tất cả hậu tố của tất cả các chuỗi bạn muốn tìm kiếm. Tùy thuộc vào tổ chức, điều này có thể được gọi là "hậu tố cây" hoặc "hậu tố mảng". Ví dụ: nếu bạn có 1000 chuỗi và mỗi chuỗi dài 50 ký tự, bạn có 1.000 x 50 hậu tố không thuận lợi, nghĩa là mảng hậu tố của bạn sẽ có 50.000 mục nhập. Sau đó, để thực hiện kết hợp, bạn tìm kiếm nhị phân (nếu mảng) hoặc tìm kiếm cây (nếu cây) để tìm tất cả các hậu tố đó trong cấu trúc dữ liệu có bắt đầu khớp với chuỗi được viết trong hộp tìm kiếm. Bởi vì nó là sự khởi đầu của hậu tố bạn đang kết hợp, bạn có thể sử dụng các thủ tục tìm kiếm chuẩn (tìm kiếm nhị phân, gốc cây) để có được kết quả nhanh chóng. Mỗi hậu tố được liên kết với những chuỗi mà nó xuất hiện.
Ví dụ: bạn có hai chuỗi "CAT" và "DOT". mảng hậu tố của bạn trông như thế này (lưu ý lexiographic = chữ cái đặt hàng):
#1 AT --> CAT
#2 CAT --> CAT
#3 DOT --> DOT
#4 OT --> DOT
#5 T --> DOT, CAT
Lưu ý rằng có sáu hậu tố nhưng hai trong số đều giống nhau (cuối cùng "T" trong "CAT" và "DOT") và đều được đại diện bởi cùng một mục (# 5).
Bây giờ, khi người dùng nhập vào tìm kiếm, ví dụ: "OT" (phải khớp với "DOT"), bạn có thể thực hiện tra cứu đơn đặt hàng lexiographic đơn giản trong thời gian đăng nhập khi bạn đang tìm kiếm bắt đầu trận đấu trong mảng hậu tố.
Đây là nguyên tắc cơ bản về tìm kiếm văn bản nhanh khi mẫu tìm kiếm không chứa ký tự đại diện.
Tôi nghĩ rằng điều này là để lưu trữ cơ bản: Cơ sở dữ liệu SQLite nơi Firefox lưu trữ các trang bạn đã truy cập cung cấp chức năng nhanh để so sánh chuỗi con.
Tôi nghĩ Firefox phát hành Truy vấn SQL đến Cơ sở dữ liệu. Điều này là khá nhanh vì cơ sở dữ liệu được lưu trữ trong bộ nhớ của bạn.
Điều đó hoàn toàn không đúng. Dữ liệu trong thực tế thu được từ SQLite, nhưng việc kết hợp được thực hiện với một thuật toán hoàn toàn khác. – sdwilsh
Thanh ngang gợi ý URL bằng thuật toán được gọi là The Places frecency algorithm.
Theo trang web của nhà phát triển Mozilla: "recency"
Từ "frecency" tự nó là một sự kết hợp của dòng chữ "tần số" và
Thuật toán thanh vị trí trong Firefox 3.0 hơi phức tạp. Nó sẽ lấy dữ liệu từ hai (ba cho Firefox 3.5 và mới hơn) truy vấn khác nhau:
Đối với truy vấn đầu tiên, nó sẽ kiểm tra bảng moz_inputhistory để xem nếu chuỗi tìm kiếm hiện tại được lưu trữ trong bảng đó. Các kết quả này được sắp xếp theo "xếp hạng", là một số xác định mức độ sử dụng gần đây của nó. Con số này xuống cấp mỗi ngày một lần. Tìm kiếm này là những gì làm cho thanh vị trí thích ứng với những gì bạn chọn theo thời gian (được thực hiện trong bug 95739).
Trong Firefox 3.5 và sau đó, nó sau đó kiểm tra bảng moz_keyword cho các dấu trang với một từ khóa khớp chính xác với văn bản tìm kiếm.
Truy vấn cuối cùng, nó truy cập mọi mục nhập trong moz_places, bao gồm tất cả lượt truy cập lịch sử và dấu trang. Những kết quả này được sắp xếp theo frecency.
Đối với cả ba trường hợp này, thuật toán sau được sử dụng để khớp với thẻ, tiêu đề và url (được gọi là "văn bản có thể tìm kiếm" bên dưới). Đây là một chút khó khăn để giải thích bằng lời, vì vậy nó có thể dễ dàng hơn để look at the source code.
Hy vọng điều đó sẽ giải thích nó theo cách dễ hiểu!
Giải thích tốt +1 –
Điều này chỉ cần thiết nếu bạn muốn tìm các kết quả phù hợp ở giữa một từ. Nếu bạn hài lòng với kết hợp từ đầu của một từ, một chỉ số đảo ngược bình thường là đủ. –
Dựa trên các thử nghiệm của riêng tôi, 'firefo' bật lên một kết quả rất nhanh (và tăng dần), trong khi 'irefo' mất một lúc. Tôi đoán nó sử dụng một chỉ số đảo ngược một cách trực tiếp, và thực hiện quét brute-force của toàn bộ db nếu không có gì được trả về. –