NLP - Phân tích cấp độ từ

Trong chương này, chúng ta sẽ hiểu phân tích mức độ thế giới trong Xử lý ngôn ngữ tự nhiên.

Biểu thức chính quy

Biểu thức chính quy (RE) là một ngôn ngữ để chỉ định các chuỗi tìm kiếm văn bản. RE giúp chúng tôi so khớp hoặc tìm các chuỗi hoặc bộ chuỗi khác, sử dụng cú pháp chuyên biệt được tổ chức trong một mẫu. Biểu thức chính quy được sử dụng để tìm kiếm văn bản trong UNIX cũng như trong MS WORD theo cách giống hệt nhau. Chúng tôi có nhiều công cụ tìm kiếm sử dụng một số tính năng RE.

Thuộc tính của Biểu thức chính quy

Tiếp theo là một số thuộc tính quan trọng của RE -

  • Nhà toán học người Mỹ Stephen Cole Kleene đã chính thức hóa ngôn ngữ Biểu thức chính quy.

  • RE là một công thức trong một ngôn ngữ đặc biệt, có thể được sử dụng để chỉ định các lớp đơn giản của chuỗi, một chuỗi các ký hiệu. Nói cách khác, chúng ta có thể nói rằng RE là một ký hiệu đại số để đặc trưng cho một tập hợp các chuỗi.

  • Biểu thức chính quy yêu cầu hai thứ, một là mẫu mà chúng ta muốn tìm kiếm và hai là một kho văn bản mà chúng ta cần tìm kiếm.

Về mặt toán học, một biểu thức chính quy có thể được định nghĩa như sau:

  • ε là một Biểu thức chính quy, cho biết rằng ngôn ngữ đang có một chuỗi trống.

  • φ là một Biểu thức chính quy biểu thị rằng nó là một ngôn ngữ trống.

  • Nếu XY là Biểu thức chính quy, sau đó là

    • X, Y

    • X.Y(Concatenation of XY)

    • X+Y (Union of X and Y)

    • X*, Y* (Kleen Closure of X and Y)

cũng là các biểu thức chính quy.

  • Nếu một chuỗi có nguồn gốc từ các quy tắc trên thì đó cũng sẽ là một biểu thức chính quy.

Ví dụ về Cụm từ Thông dụng

Bảng sau đây cho thấy một vài ví dụ về Biểu thức chính quy:

Biểu thức chính quy Bộ thông thường
(0 + 10 *) {0, 1, 10, 100, 1000, 10000,…}
(0 * 10 *) {1, 01, 10, 010, 0010,…}
(0 + ε) (1 + ε) {ε, 0, 1, 01}
(a + b) * Nó sẽ là tập hợp các chuỗi a và b có độ dài bất kỳ bao gồm cả chuỗi rỗng tức là {ε, a, b, aa, ab, bb, ba, aaa …….}
(a + b) * abb Nó sẽ là tập hợp các chuỗi của a và b kết thúc bằng chuỗi abb tức là {abb, aabb, babb, aaabb, ababb, ………… ..}
(11) * Nó sẽ được đặt bao gồm số chẵn của 1 cũng bao gồm một chuỗi rỗng, tức là {ε, 11, 1111, 111111, ……….}
(aa) * (bb) * b Nó sẽ là tập hợp các chuỗi bao gồm số chẵn của a theo sau là số lẻ của b tức là {b, aab, aabbb, aabbbbb, aaaab, aaaabbb, ………… ..}
(aa + ab + ba + bb) * Đó sẽ là chuỗi a và b có độ dài chẵn có thể thu được bằng cách ghép bất kỳ tổ hợp nào của các chuỗi aa, ab, ba và bb bao gồm null tức là {aa, ab, ba, bb, aaab, aaba, …………. .}

Bộ thông thường & Thuộc tính của chúng

Nó có thể được định nghĩa là tập hợp đại diện cho giá trị của biểu thức chính quy và bao gồm các thuộc tính cụ thể.

Thuộc tính của tập hợp thông thường

  • Nếu chúng ta kết hợp hai tập hợp thông thường thì tập kết quả cũng sẽ là chính quy.

  • Nếu chúng ta thực hiện giao của hai tập hợp chính quy thì tập hợp kết quả cũng sẽ là tập hợp chính quy.

  • Nếu chúng ta thực hiện phần bù của các tập hợp thông thường, thì tập hợp kết quả cũng sẽ là tập hợp chính quy.

  • Nếu chúng ta thực hiện sự khác biệt của hai tập hợp thông thường, thì tập hợp kết quả cũng sẽ là tập hợp chính quy.

  • Nếu chúng ta đảo ngược các tập hợp thông thường, thì tập hợp kết quả cũng sẽ là tập hợp chính quy.

  • Nếu chúng ta thực hiện việc đóng các tập hợp thông thường, thì tập hợp kết quả cũng sẽ là tập hợp chính quy.

  • Nếu chúng ta thực hiện việc nối hai tập hợp chính quy, thì tập hợp kết quả cũng sẽ là tập hợp chính quy.

Dữ liệu tự động trạng thái hữu hạn

Thuật ngữ automata, có nguồn gốc từ tiếng Hy Lạp "αὐτόματα" có nghĩa là "tự hoạt động", là số nhiều của automaton có thể được định nghĩa là một thiết bị tính toán tự hành trừu tượng tuân theo một trình tự hoạt động định trước một cách tự động.

Một ô tô tự động có một số trạng thái hữu hạn được gọi là ô tự động hữu hạn (FA) hoặc ô tự động trạng thái hữu hạn (FSA).

Về mặt toán học, một automaton có thể được biểu diễn bằng 5 bộ (Q, Σ, δ, q0, F), trong đó -

  • Q là một tập hữu hạn các trạng thái.

  • Σ là một tập hợp hữu hạn các ký hiệu, được gọi là bảng chữ cái của ô tô.

  • δ là hàm chuyển tiếp

  • q0 là trạng thái ban đầu mà từ đó bất kỳ đầu vào nào được xử lý (q0 ∈ Q).

  • F là tập hợp các trạng thái / trạng thái cuối cùng của Q (F ⊆ Q).

Mối quan hệ giữa dữ liệu tự động hữu hạn, ngữ pháp thông thường và biểu thức chính quy

Những điểm sau đây sẽ cho chúng ta một cái nhìn rõ ràng về mối quan hệ giữa ô tự động hữu hạn, ngữ pháp thông thường và biểu thức chính quy -

  • Như chúng ta biết rằng otomat trạng thái hữu hạn là nền tảng lý thuyết của công việc tính toán và biểu thức chính quy là một cách để mô tả chúng.

  • Chúng ta có thể nói rằng bất kỳ biểu thức chính quy nào đều có thể được triển khai dưới dạng FSA và mọi FSA có thể được mô tả bằng biểu thức chính quy.

  • Mặt khác, biểu thức chính quy là một cách để đặc trưng cho một loại ngôn ngữ được gọi là ngôn ngữ chính quy. Do đó, chúng ta có thể nói rằng ngôn ngữ thông thường có thể được mô tả với sự trợ giúp của cả FSA và biểu thức chính quy.

  • Ngữ pháp thông thường, một ngữ pháp chính thức có thể là từ phải thông thường hoặc trái thông thường, là một cách khác để đặc trưng cho ngôn ngữ thông thường.

Sơ đồ sau cho thấy rằng các tự động hữu hạn, biểu thức chính quy và ngữ pháp thông thường là những cách tương đương để mô tả các ngôn ngữ thông thường.

Các loại tự động hóa trạng thái hữu hạn (FSA)

Tự động hóa trạng thái hữu hạn có hai loại. Hãy để chúng tôi xem các loại là gì.

Tự động hóa hữu hạn xác định (DFA)

Nó có thể được định nghĩa là loại tự động hóa hữu hạn, trong đó, đối với mọi ký hiệu đầu vào, chúng ta có thể xác định trạng thái mà máy sẽ di chuyển. Nó có một số trạng thái hữu hạn, đó là lý do tại sao máy được gọi là Máy tự động hữu hạn xác định (DFA).

Về mặt toán học, DFA có thể được biểu diễn bằng 5 bộ (Q, Σ, δ, q0, F), trong đó -

  • Q là một tập hữu hạn các trạng thái.

  • Σ là một tập hợp hữu hạn các ký hiệu, được gọi là bảng chữ cái của ô tô.

  • δ là hàm chuyển đổi trong đó δ: Q × Σ → Q.

  • q0 là trạng thái ban đầu mà từ đó bất kỳ đầu vào nào được xử lý (q0 ∈ Q).

  • F là tập hợp các trạng thái / trạng thái cuối cùng của Q (F ⊆ Q).

Trong khi đó bằng đồ thị, một DFA có thể được biểu diễn bằng các biểu đồ được gọi là biểu đồ trạng thái trong đó -

  • Các tiểu bang được đại diện bởi vertices.

  • Các chuyển đổi được hiển thị bằng nhãn arcs.

  • Trạng thái ban đầu được đại diện bởi một empty incoming arc.

  • Trạng thái cuối cùng được đại diện bởi double circle.

Ví dụ về DFA

Giả sử một DFA là

  • Q = {a, b, c},

  • Σ = {0, 1},

  • q 0 = {a},

  • F = {c},

  • Hàm chuyển đổi δ được thể hiện trong bảng như sau:

Tình trạng hiện tại Trạng thái tiếp theo cho đầu vào 0 Trạng thái tiếp theo cho đầu vào 1
A a B
B b A
C c C

Biểu diễn đồ họa của DFA này sẽ như sau:

Tự động hóa hữu hạn không xác định (NDFA)

Nó có thể được định nghĩa là kiểu tự động hóa hữu hạn mà đối với mọi ký hiệu đầu vào, chúng ta không thể xác định trạng thái mà máy sẽ di chuyển, tức là máy có thể di chuyển đến bất kỳ tổ hợp trạng thái nào. Nó có một số trạng thái hữu hạn, đó là lý do tại sao máy được gọi là Tự động hóa hữu hạn không xác định (NDFA).

Về mặt toán học, NDFA có thể được biểu diễn bằng 5 bộ (Q, Σ, δ, q0, F), trong đó -

  • Q là một tập hữu hạn các trạng thái.

  • Σ là một tập hợp hữu hạn các ký hiệu, được gọi là bảng chữ cái của ô tô.

  • δ: -là các chức năng chuyển nơi δ: Q × Σ → 2 Q .

  • q0: -là trạng thái ban đầu mà từ đó bất kỳ đầu vào nào được xử lý (q0 ∈ Q).

  • F: -là tập hợp các trạng thái / trạng thái cuối cùng của Q (F ⊆ Q).

Trong khi bằng đồ thị (giống như DFA), NDFA có thể được biểu diễn bằng các sơ đồ được gọi là sơ đồ trạng thái trong đó -

  • Các tiểu bang được đại diện bởi vertices.

  • Các chuyển đổi được hiển thị bằng nhãn arcs.

  • Trạng thái ban đầu được đại diện bởi một empty incoming arc.

  • Trạng thái cuối cùng được biểu diễn bằng đôi circle.

Ví dụ về NDFA

Giả sử một NDFA là

  • Q = {a, b, c},

  • Σ = {0, 1},

  • q 0 = {a},

  • F = {c},

  • Hàm chuyển đổi δ được thể hiện trong bảng như sau:

Tình trạng hiện tại Trạng thái tiếp theo cho đầu vào 0 Trạng thái tiếp theo cho đầu vào 1
A a, b B
B C AC
C b, c C

Biểu diễn đồ họa của NDFA này sẽ như sau:

Phân tích cú pháp hình thái

Thuật ngữ phân tích cú pháp hình thái học có liên quan đến việc phân tích cú pháp các morpheme. Chúng ta có thể định nghĩa phân tích hình thái học là vấn đề nhận biết rằng một từ được chia thành các đơn vị có nghĩa nhỏ hơn được gọi là morphemes tạo ra một số loại cấu trúc ngôn ngữ cho nó. Ví dụ, chúng ta có thể chia từ foxes thành hai, fox-es . Chúng ta có thể thấy rằng từ foxes , được tạo thành từ hai hình thái, một là cáo và một là -es .

Theo nghĩa khác, chúng ta có thể nói rằng hình thái học là nghiên cứu của -

  • Sự hình thành của từ.

  • Nguồn gốc của các từ.

  • Các dạng ngữ pháp của các từ.

  • Sử dụng tiền tố và hậu tố trong việc hình thành từ.

  • Cách các phần của giọng nói (PoS) của một ngôn ngữ được hình thành.

Các loại Morphemes

Morphemes, đơn vị mang ý nghĩa nhỏ nhất, có thể được chia thành hai loại -

  • Stems

  • Trật tự từ

Thân cây

Nó là đơn vị ý nghĩa cốt lõi của một từ. Chúng ta cũng có thể nói rằng nó là gốc của từ. Ví dụ, trong từ foxes, thân là con cáo.

  • Affixes- Như tên cho thấy, chúng bổ sung thêm một số ý nghĩa và chức năng ngữ pháp cho các từ. Ví dụ, trong từ foxes, phụ tố là - es.

Hơn nữa, các phụ tố cũng có thể được chia thành bốn loại sau:

    • Prefixes- Như tên cho thấy, các tiền tố đứng trước thân cây. Ví dụ, trong từ unbuckle, un là tiền tố.

    • Suffixes- Như tên cho thấy, các hậu tố theo sau thân cây. Ví dụ, trong từ mèo, -s là hậu tố.

    • Infixes- Như tên cho thấy, các bản in được chèn vào bên trong thân cây. Ví dụ, từ cupful, có thể được đa nghĩa hóa là cupful bằng cách sử dụng -s làm tiền tố.

    • Circumfixes- Họ đi trước và đi sau thân cây. Có rất ít ví dụ về dấu ngoặc kép trong ngôn ngữ tiếng Anh. Một ví dụ rất phổ biến là 'A-ing' nơi chúng ta có thể sử dụng -A đứng trước và -ing theo sau thân.

Trật tự từ

Thứ tự của các từ sẽ được quyết định bằng cách phân tích hình thái. Bây giờ chúng ta hãy xem các yêu cầu để xây dựng trình phân tích cú pháp hình thái học -

Lexicon

Yêu cầu đầu tiên để xây dựng bộ phân tích cú pháp hình thái là từ vựng, bao gồm danh sách các thân và phụ tố cùng với thông tin cơ bản về chúng. Ví dụ: thông tin như gốc là danh từ hay gốc động từ, v.v.

Hình thái học

Về cơ bản, nó là mô hình sắp xếp hình cầu. Theo nghĩa khác, mô hình giải thích các lớp morphemes nào có thể theo sau các lớp morpheme khác bên trong một từ. Ví dụ, thực tế về hình thái là hình cầu số nhiều trong tiếng Anh luôn đứng sau danh từ hơn là đứng trước nó.

Quy tắc chỉnh hình

Các quy tắc chính tả này được sử dụng để mô hình hóa những thay đổi xảy ra trong một từ. Ví dụ, quy tắc chuyển đổi y thành ie trong từ như city + s = thành phố không phải thành phố.