Python cho người Việt

Python cho người Việt

Entries tagged “string”

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.

Làm việc với String (Python 3)

written by vithon, on Feb 9, 2011 11:46:00 AM.

So sánh cơ bản:

>>> A="caulacbopython"
>>> B="pythonviet"
>>> print(A==B)
False
>>> print(A>B)
False
>>> print(A<B)
True

Ghép chuỗi:

>>> A="Yeu"
>>> B="Python"
>>> A+B
'YeuPython'

Split: Hiểu nôm na, ta có một cái chuỗi dài. Giờ ta sẽ cắt nó thành nhiều khúc dài dài và sử dụng khúc nào đó thì tùy:

>>> A="Cau-Lac-Bo-Python-Viet"
>>> B=A.split('-')
>>> B
['Cau', 'Lac', 'Bo', 'Python', 'Viet']
>>> B[0]
'Cau'
>>> B[1]
'Lac'
>>> B[2]
'Bo'

Lấy 1 ký tự bất kì:

>>> chuoi= "NguyenMinhThe"
>>> print(chuoi[2])
u
>>> print(chuoi[1])
g

Thay thế (Replace):

>>> chuoi="MinhThe"
>>> print(chuoi.replace('h','H'))
>>> 'MinHTHe'

Đếm số lần xuất hiện ký tự trong 1 chuỗi:

>>> ch="VithonViet"
>>> print(ch.count('V'))
2

Trích từ bài gửi diễn đàn của Nguyễn Minh Thế.