Biểu thức chính quy (regex), công cụ cần thiết trong tiền xử lý văn bản
Một phần trong công việc xử lý văn bản là phải tìm hiểu về biểu thức chính quy (regular expressions), và cách học về Regex nhanh và vững chắc nhất là xem cách thức hoạt động của nó. Một khi hiểu được cấu trúc của Regex, bạn sẽ sử dụng biểu thức chính quy tốt hơn, nhất là trong các trường hợp phức tạp.
Hai thuật toán text-directed engines và regex-directed engines
Có hai loại thuật toán nằm bên dưới biểu thức chính quy chính là text-directed engines và regex-directed engines.
Rất khó để có một định nghĩa rõ ràng về khái niệm text-directed engines và regex-directed engines. Nó là thuật toán, công nghệ, hay là giải pháp?
Nếu xem xét cách thức hoạt động của Regex, nó thuộc tập hợp các quy tắc được sử dụng để giải quyết một vấn đề, thì chúng ta tạm gọi text-directed engines và regex-directed engines ở trong phạm trù thuật toán.
Thuật toán text-directed engines
Text-directed engines: Trước hết, cách thức hoạt động của text-directed engines như sau: Nó sẽ duyệt qua chuỗi và thử tất cả các khả năng khớp biểu thức chính quy. Nếu một khả năng khớp, thuật toán sẽ dừng lại và trả về kết quả. Các thuật toán text-directed được sử dụng để xử lý các biểu thức chính quy đơn giản hơn. Hầu hết các regular expressions hiện đại đều dựa trên nền tảng regex-directed.
Thuật toán regex-directed engines
Regex-directed engines: Thuật toán này sẽ xử lý chỗi theo trình tự bắt đầu từ đầu biểu thức chính quy và xem liệu nó có khớp với một phần của chuỗi hay không. Nếu không, thuật toán sẽ quay trở lại một bước trước đó và thử một khả năng khác. Các engine regex-directed được sử dụng để xử lý các biểu thức chính quy phức tạp hơn, bao gồm các tính năng như lazy quantifiers và backreferences.
Mỗi loại thuật toán có ưu và nhược điểm riêng. Text-directed engines thường nhanh hơn regex-directed engines, nhưng chúng không thể khớp với một số biểu thức chính quy phức tạp. Regex-directed engines có thể khớp với tất cả các biểu thức chính quy, nhưng chúng có thể chậm hơn text-directed engines.
Chúng ta có thể dễ dàng kiểm tra thử, biểu thức Regex mà chúng ta đang sử dụng thuộc về thuật toán nào bằng cách xem xét kết quả mà nó trả về.
Ví dụ: Chúng ta có cụm từ "text not" và biểu thức chính quy "text|text not".
Nếu kết quả nhận được là từ "text" thì Regex này sử dụng thuật toán Regex-directed, và nếu kết quả là "text not" thì nó sử dụng thuật toán Regex-directed.
Cách thức hoạt động của biểu thức Regex
Khi biểu thức chính quy chính thức hoạt động, nó sẽ khởi đầu tại ký tự đầu tiên bên trái. Nó sẽ thử tất cả các kết quả ngay tại giá trị đâuù tiên. Chỉ khi tất cả khả năng đều thất bại thì nó mới chuyển sang ký tự thứ hai.
Chúng ta hãy tiếp tục xem xét một ví dụ khác như sau:
- Chuỗi: “He bought a bookshelf for his book.”
- Từ cần tìm kiếm: book.
(1) Thuật toán Regex sẽ khởi đầu tại ký tự đầu tiên, nó cố gắng so khớp chữ "H" với chữ "b" nhưng không tìm thấy kết quả khớp nào.
(2) Nó sẽ cố gắng so khớp chữ "b" với chữ "e" nhưng vẫn chưa có kết quả.
(3) Đến từ "bought", nó tìm khớp được chữ "bo" nhưng các kết quả khác thì không đúng.
(4) Sau khi so khớp đến ký tự thứ 30 thì nó tìm thấy kết quả đúng.
Tuy nhiên, sau khi so khớp thì nó sẽ dừng tại vị trí này và không tìm kiếm các kết quả tốt hơn. Và quả thực, cách hoạt động của nó không khác gì cách tìm kiếm văn bản tuyến tính.
Nếu Regex sử dụng thuật toán text-directed thì nó cũng cho kết quả tương tự, tuy nhiên, điều quan trọng là nó thông minh hơn một chút. Vài kết quả nó sẽ khiến cho bạn ngạc nhiên.
