Python cho người Việt

Python cho người Việt

Entries tagged “algorithm”

Thuật toán đẹp: Tìm chuỗi Boyer-Moore-Horspool

written by Nguyễn Thành Nam, on Jan 9, 2014 2:35:00 PM.

Mục đích

Tìm chính xác (exact match) chuỗi con (substring) trong một chuỗi dài hơn.

Ý tưởng chính

Gọi chuỗi cần tìm là P (pattern), và chuỗi dài là T (text).

So sánh ngược P trong T, nghĩa là ta sẽ so sánh ký tự cuối của P trước, sau đó so sánh ký tự kế cuối, và lần lượt như vậy đến ký tự đầu tiên trong P. Gọi vị trí trong T để bắt đầu so sánh hai chuỗi là i. Việc so sánh sẽ so sánh lần lượt T[i] với ký tự cuối của P, rồi T[i-1] với ký tự kế cuối của P, v.v...

Nếu việc so sánh ngược vượt qua được ký tự đầu tiên trong P, ta đã tìm được P trong T.

Nếu việc so sánh ngược bị thất bại, ta sẽ căn P cho khớp với T[i] và thử lại việc so sánh ngược. Điều này tương đương với việc dịch chuyển i đến vị trí xa hơn trong T. Đây là ý tưởng chủ chốt của thuật toán BMH.

  • Nếu T[i] không có trong P, thì ta có thể dịch chuyển i đến vị trí i + len(P).
  • Nếu vị trí cuối cùng của T[i] trong P là x thì ta dịch chuyển i đến vị trí i + len(P) - x - 1.
Trạng thái bắt đầu

             i
             |
             v
+-+-+-+-+-+-+-+-+-+-+-+-+
| | | | |d|b|a| | | | | |
+-+-+-+-+-+-+-+-+-+-+-+-+

    +-+-+-+-+-+
    |a|a|c|b|a|
    +-+-+-+-+-+

------------------------------------------

So sánh tiếp tục

             i
             |
             v
+-+-+-+-+-+-+-+-+-+-+-+-+
| | | | |d|b|a| | | | | |
+-+-+-+-+-+-+-+-+-+-+-+-+
             =
    +-+-+-+-+-+
    |a|a|c|b|a|
    +-+-+-+-+-+

------------------------------------------

So sánh tiếp tục

             i
             |
             v
+-+-+-+-+-+-+-+-+-+-+-+-+
| | | | |d|b|a| | | | | |
+-+-+-+-+-+-+-+-+-+-+-+-+
           = =
    +-+-+-+-+-+
    |a|a|c|b|a|
    +-+-+-+-+-+

------------------------------------------

So sánh sai

             i
             |
             v
+-+-+-+-+-+-+-+-+-+-+-+-+
| | | | |d|b|a| | | | | |
+-+-+-+-+-+-+-+-+-+-+-+-+
         ! = =
    +-+-+-+-+-+
    |a|a|c|b|a|
    +-+-+-+-+-+

------------------------------------------

Căn P theo T[i]...

             i
             |
             v
+-+-+-+-+-+-+-+-+-+-+-+-+
| | | | |d|b|a| | | | | |
+-+-+-+-+-+-+-+-+-+-+-+-+
             |
          +-+-+-+-+-+
          |a|a|c|b|a|
          +-+-+-+-+-+

------------------------------------------

... cũng có nghĩa là dịch chuyển i

                   i
                   |
                   v
+-+-+-+-+-+-+-+-+-+-+-+-+
| | | | |d|b|a| | | | | |
+-+-+-+-+-+-+-+-+-+-+-+-+

          +-+-+-+-+-+
          |a|a|c|b|a|
          +-+-+-+-+-+

Để cài đặt hai bước trên, người ta thường dùng một mảng chứa vị trí cuối cùng của các ký tự trong P trừ ký tự cuối cùng (P[ : -1]).

Ví dụ

Giả sử chúng ta muốn tìm chuỗi needle trong chuỗi find the needle in the haystack.

Trước khi bắt đầu, ta sẽ lập bảng vị trí cuối của các ký tự trong P[ : -1].

Ký tựVị tríDiễn giải
n0
e2Ta chọn vị trí của ký tự thứ hai.
d3
l4

Và sự thay đổi ở các bước của thuật toán. Vì độ dài của P là 6, nên i sẽ bắt đầu từ vị trí 5. Trong bảng dưới, chữ đậm là ký tự trùng nhau của T và P, chữ gạch dưới là các ký tự đang xét.

iTT[i]Diễn giải
5find the needle in the haystacktt không có trong bảng. Dịch i lên 11 (5 + 6).
11find the needle in the haystackee có trong bảng. Dịch i lên 14 (11 + 6 - 2 - 1).
14find the needle in the haystackeTìm thấy. e có trong bảng. Dịch i lên 17 (14 + 6 - 2 - 1).
17find the needle in the haystacknn có trong bảng. Dịch i lên 22 (17 + 6 - 0 - 1).
22find the needle in the haystackkhoảng trắngkhoảng trắng không có trong bảng. Dịch i lên 28 (22 + 6).
28find the needle in the haystackaa không có trong bảng. Dịch i lên 34 (28 + 6). Dừng việc tìm kiếm vì đã xét hết chuỗi.

Độ phức tạp

Thời gian chạy: Tệ nhất là O(n*m), với n là độ dài của T và m là độ dài của P. Trung bình là O(n). Và tốt nhất là dưới tuyến tính (sublinear) vì thuật toán có thể nhảy qua nhiều ký tự. Trong ví dụ trên, ta chỉ cần 12 phép so sánh để tìm chuỗi needle (6 ký tự) trong chuỗi find the needle in the haystack (31 ký tự).

Bộ nhớ cần thiết: O(n) với n là số ký tự trong bảng chữ cái (ví dụ như 256 giá trị của một byte, hoặc nếu bảng chữ cái là Unicode thì có thể sẽ nhiều hơn 60000 giá trị) vì chúng ta cần tạo bảng vị trí các ký tự trong P.

Thuật toán BMH là thuật toán tìm chuỗi chính xác tổng quát nhất, nhanh nhất, và đơn giản nhất.

Thuật toán đẹp: Partition (ngăn)

written by Nguyễn Thành Nam, on Jan 1, 2014 12:34:00 AM.

Mục đích

Chia một mảng ra thành hai cụm: một cụm thỏa điều kiện, và cụm còn lại.

Cài đặt

Sử dụng mảng phụ

def partition(a, pred):
    head = [x for x in a if pred(x)]
    tail = [x for x in a if not pred(x)]
    return head + tail, len(head)

Không dùng mảng phụ

Ý tưởng chính là sử dụng một biến phụ chứa vị trí trong mảng A mà nếu phần tử đang xét thỏa điều kiện sẽ được chuyển vào.

def partition(a, pred):
    okay_idx = 0
    for i, x in enumerate(a):
        if pred(x):
            a[okay_idx], a[i] = a[i], a[okay_idx] # swap
            okay_idx += 1
    return a, okay_idx

Độ phức tạp

Thời gian chạy: O(n)

Bộ nhớ cần thiết: O(n) nếu sử dụng mảng phụ, hoặc O(1) nếu không

Ứng dụng

Ứng dụng nổi tiếng nhất là thuật toán QuickSort do Tony Hoare sáng tạo ra. Thuật toán QuickSort sắp xếp một mảng với độ phức tạp trung bình là O(n*logn) với n là số lượng phần tử trong mảng. Độ phức tạp trong trường hợp xấu nhất có thể là O(n*n).

Sau đây là một cài đặt dễ hiểu của QuickSort. Cài đặt này chỉ dùng để thể hiện ý tưởng chứ không nên dùng trong các ứng dụng.

Ý tưởng chủ đạo là lấy ra một phần tử nào đó trong A (tức là A' chỉ còn N-1 phần tử) gọi là pivot, ngăn A' thành hai cụm (một cụm nhỏ hơn pivot, một cụm còn lại). Tiếp tục gọi đệ quy để sắp xếp hai cụm đó và nối chúng lại với nhau thông qua pivot.

def quicksort(a):
    if len(a) <= 1:
        return a
    pivot = a[-1]
    a, pivot_idx = partition(a[ : -1], lambda x: x <= pivot)
    return quicksort(a[ : pivot_idx]) + [pivot] + quicksort(a[pivot_idx : ])

import itertools
for l in range(8):
    a = range(l)
    for p in itertools.permutations(a):
        p = list(p)
        assert quicksort(p) == a

Bài toán mở rộng

  1. Cho một mảng số nguyên A. Tìm K phần tử nhỏ nhất trong A.
  2. Cho một mảng số nguyên A và một số nguyên X. Đếm số tập hợp 2-phần-tử trong mảng A có tổng nhỏ hơn hoặc bằng X.

Các bạn có thể trao đổi về cách giải bài các bài toán mở rộng này với độ phức tạp trung bình O(n) trong diễn đàn.

Thuật toán đẹp: Tìm nhị phân

written by Nguyễn Thành Nam, on Dec 27, 2013 1:13:00 PM.

Mục đích

Tìm phần tử X trong một mảng đã được sắp xếp.

Ý tưởng chính

Chia mảng ra thành 3 cụm: cụm bên trái, phần tử ở giữa, và cụm bên phải. So sánh X với phần tử ở giữa. Nếu X bằng với phần tử ở giữa thì ta đã tìm được X trong mảng. Nếu X lớn hơn thì tìm X trong cụm bên phải. Nếu X nhỏ hơn thì tìm X trong cụm bên trái.

Hiệu quả

Thời gian thực hiện: O(logn)

Bộ nhớ cần thiết: O(1)

Cài đặt

Cài đặt đệ quy

def bin_search(x, a, left_idx, right_idx):
    if left_idx > right_idx:
        return -1
    mid_idx = left_idx + (right_idx - left_idx) // 2
    mid = a[mid_idx]
    if x == mid:
        return mid_idx
    elif x < mid:
        return bin_search(x, a, left_idx, mid_idx - 1)
    else:
        return bin_search(x, a, mid_idx + 1, right_idx)

assert bin_search(0, [0], 0, 0) == 0
assert bin_search(0, [1], 0, 0) == -1
assert bin_search(0, [0, 1], 0, 1) == 0
assert bin_search(1, [0, 1], 0, 1) == 1
assert bin_search(2, [0, 1], 0, 1) == -1

Cài đặt vòng lặp

def bin_search(x, a, left_idx, right_idx):
    while left_idx <= right_idx:
        mid_idx = left_idx + (right_idx - left_idx) // 2
        mid = a[mid_idx]
        if mid == x:
            return mid_idx
        elif x < mid:
            right_idx = mid_idx - 1
        else:
            left_idx = mid_idx + 1
    return -1

Tham khảo thêm

Mô-đun bisect trong thư viện chuẩn của Python.

Một số bài toán mở rộng

  1. Mảng đã được sắp xếp nhưng đã bị xoay vòng (ví dụ [4, 5, 6, 7, 1, 2, 3]).
  2. Mảng 2 chiều đã được sắp xếp theo dòng, và cột (a[i][j] < a[i + 1][j] và a[i][j] < a[i][j + 1]).

Các bạn có thể trao đổi ý tưởng giải quyết các bài toán mở rộng này trong diễn đàn.