Tìm kiếm nội suy trên các chuỗi

Question

Đối với những người không quen thuộc với tìm kiếm nội suy, đó là phương pháp tìm kiếm một giá trị trong một mảng được sắp xếp có khả năng tìm kiếm nhanh hơn tìm kiếm nhị phân. Bạn nhìn vào phần tử đầu tiên và cuối cùng và (giả sử rằng nội dung của mảng được phân bố đồng đều) nội suy tuyến tính để dự đoán vị trí.

Ví dụ: chúng tôi có một mảng có độ dài 100 với mảng [0] = 0 và mảng [99] = 99. Nếu chúng ta đang tìm kiếm 80, nó là trực quan để thử mảng [80] trên mảng [50], và nếu mảng gần phân phối đồng đều, thời gian chạy dự kiến ​​sẽ giảm xuống log(log(N))

Để biết số, vị trí cần kiểm tra được xác định theo phương trình: low + ((toFind - sortedArray[low]) * (high - low + 1))/(sortedArray[high] - sortedArray[low]).

Một ví dụ phổ biến được sử dụng để thể hiện bản chất trực quan của tìm kiếm nội suy là: hãy tưởng tượng cố gắng tìm từ 'vàng' trong từ điển. Bạn sẽ không sử dụng tìm kiếm nhị phân và đi đến một nửa điểm. Thay vào đó, bạn sẽ đi đến vị trí mong đợi.

Con người có thể tự nội suy tuyến tính chuỗi, nhưng tôi không thể tìm ra cách mã nó lên. Làm cách nào để chúng ta nội suy tuyến tính?

Answer 1

Để tìm "khoảng cách" giữa hai chuỗi, một phương pháp đơn giản là xem chữ cái đầu tiên khác nhau giữa chúng và gán giá trị số cho mỗi chuỗi, sau đó lấy sự khác biệt.

Ví dụ: khoảng cách từ "a" đến "y" sẽ là 24 và khoảng cách từ "y" đến "z" sẽ là 1, nếu mỗi chữ cái được gán giá trị bằng vị trí của nó trong bảng chữ cái.

Phương pháp hoạt động tốt hơn sẽ đi qua từ điển để cân các chữ cái khác nhau theo mức độ thông dụng của từ.

Một sàng lọc khác là xem hai ký tự - "aa" cách xa "bz" hơn "az" là từ "ba", ví dụ. Đi xa hơn hai nhân vật sẽ không mua cho bạn nhiều.

Lý do phương pháp này không phổ biến hơn là nó làm phức tạp thuật toán tìm kiếm nhị phân mà không có nhiều lợi ích. Nếu bạn đã đến lúc nó thậm chí bạn có thể thấy rằng tìm kiếm nhị phân chuẩn nhanh hơn; những gì bạn đạt được trong việc so sánh ít hơn bạn bị mất trong sự phức tạp của việc xác định khoảng cách.

Cũng lưu ý rằng hiệu suất xấu nhất của thuật toán này kém hơn tìm kiếm nhị phân. Hãy xem xét ví dụ tìm kiếm "ae" trong danh sách "aa", "ab", "ac", "ad", "ae", "zz" - outlier "zz" sẽ thiên vị tìm kiếm để luôn cố gắng bắt đầu phạm vi tìm kiếm. Nó giảm xuống O (n) trong các điều kiện này.