PNL - Análisis a nivel de palabras

En este capítulo, comprenderemos el análisis a nivel mundial en el procesamiento del lenguaje natural.

Expresiones regulares

Una expresión regular (RE) es un lenguaje para especificar cadenas de búsqueda de texto. RE nos ayuda a hacer coincidir o encontrar otras cadenas o conjuntos de cadenas, utilizando una sintaxis especializada mantenida en un patrón. Las expresiones regulares se utilizan para buscar textos en UNIX y en MS WORD de forma idéntica. Tenemos varios motores de búsqueda que utilizan varias funciones de RE.

Propiedades de las expresiones regulares

Las siguientes son algunas de las propiedades importantes de RE:

• El matemático estadounidense Stephen Cole Kleene formalizó el lenguaje de expresión regular.

• RE es una fórmula en un lenguaje especial, que se puede utilizar para especificar clases simples de cadenas, una secuencia de símbolos. En otras palabras, podemos decir que RE es una notación algebraica para caracterizar un conjunto de cadenas.

• La expresión regular requiere dos cosas, una es el patrón que deseamos buscar y otra es un corpus de texto en el que necesitamos buscar.

Matemáticamente, una expresión regular se puede definir de la siguiente manera:

• ε es una expresión regular, que indica que el idioma tiene una cadena vacía.

• φ es una expresión regular que denota que es un lenguaje vacío.

• Si X y Y son expresiones regulares, entonces

  • X, Y

  • X.Y(Concatenation of XY)

  • X+Y (Union of X and Y)

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

también son expresiones regulares.

• Si una cadena se deriva de las reglas anteriores, también sería una expresión regular.

Ejemplos de expresiones regulares

La siguiente tabla muestra algunos ejemplos de expresiones regulares:

Expresiones regulares	Conjunto regular
(0 + 10 *)	{0, 1, 10, 100, 1000, 10000,…}
(0 * 10 *)	{1, 01, 10, 010, 0010,…}
(0 + ε) (1 + ε)	{ε, 0, 1, 01}
(a + b) *	Sería un conjunto de cadenas de a y b de cualquier longitud que también incluye la cadena nula, es decir, {ε, a, b, aa, ab, bb, ba, aaa …….}
(a + b) * abb	Sería un conjunto de cadenas de a y b que terminan con la cadena abb, es decir, {abb, aabb, babb, aaabb, ababb, ………… ..}
(11) *	Se establecería con un número par de unos que también incluye una cadena vacía, es decir, {ε, 11, 1111, 111111, ……….}
(aa) * (bb) * b	Sería un conjunto de cadenas formado por un número par de a seguido de un número impar de b, es decir, {b, aab, aabbb, aabbbbb, aaaab, aaaabbb, ………… ..}
(aa + ab + ba + bb) *	Sería una cadena de a y b de longitud uniforme que se puede obtener concatenando cualquier combinación de las cadenas aa, ab, ba y bb incluyendo nulo ie {aa, ab, ba, bb, aaab, aaba, …………. .}

Conjuntos regulares y sus propiedades

Puede definirse como el conjunto que representa el valor de la expresión regular y consta de propiedades específicas.

Propiedades de los conjuntos regulares

• Si hacemos la unión de dos conjuntos regulares, el conjunto resultante también sería regulado.

• Si hacemos la intersección de dos conjuntos regulares, el conjunto resultante también sería regular.

• Si hacemos el complemento de conjuntos regulares, entonces el conjunto resultante también sería regular.

• Si hacemos la diferencia de dos conjuntos regulares, entonces el conjunto resultante también sería regular.

• Si hacemos la inversión de conjuntos regulares, entonces el conjunto resultante también sería regular.

• Si tomamos el cierre de conjuntos regulares, entonces el conjunto resultante también sería regular.

• Si hacemos la concatenación de dos conjuntos regulares, entonces el conjunto resultante también sería regular.

Autómatas de estado finito

El término autómata, derivado de la palabra griega "αὐτόματα" que significa "autoactivo", es el plural de autómata que puede definirse como un dispositivo informático autopropulsado abstracto que sigue una secuencia predeterminada de operaciones automáticamente.

Un autómata que tiene un número finito de estados se denomina autómata finito (FA) o autómata de estado finito (FSA).

Matemáticamente, un autómata puede representarse mediante una tupla de 5 (Q, Σ, δ, q0, F), donde -

• Q es un conjunto finito de estados.

• Σ es un conjunto finito de símbolos, llamado alfabeto del autómata.

• δ es la función de transición

• q0 es el estado inicial desde donde se procesa cualquier entrada (q0 ∈ Q).

• F es un conjunto de estados finales de Q (F ⊆ Q).

Relación entre autómatas finitos, gramáticas regulares y expresiones regulares

Los siguientes puntos nos darán una visión clara sobre la relación entre autómatas finitos, gramáticas regulares y expresiones regulares:

• Como sabemos, los autómatas de estado finito son la base teórica del trabajo computacional y las expresiones regulares son una forma de describirlos.

• Podemos decir que cualquier expresión regular se puede implementar como FSA y cualquier FSA se puede describir con una expresión regular.

• Por otro lado, la expresión regular es una forma de caracterizar un tipo de lenguaje llamado lenguaje regular. Por lo tanto, podemos decir que el lenguaje regular se puede describir con la ayuda de FSA y expresiones regulares.

• La gramática regular, una gramática formal que puede ser regular a la derecha o regular a la izquierda, es otra forma de caracterizar el lenguaje regular.

El siguiente diagrama muestra que los autómatas finitos, las expresiones regulares y las gramáticas regulares son las formas equivalentes de describir los lenguajes regulares.

Tipos de automatización de estados finitos (FSA)

La automatización de estados finitos es de dos tipos. Veamos cuáles son los tipos.

Automatización finita determinista (DFA)

Puede definirse como el tipo de automatización finita en la que, para cada símbolo de entrada, podemos determinar el estado al que se moverá la máquina. Tiene un número finito de estados, por eso la máquina se llama Automatón finito determinista (DFA).

Matemáticamente, un DFA se puede representar mediante una tupla de 5 (Q, Σ, δ, q0, F), donde -

• Q es un conjunto finito de estados.

• Σ es un conjunto finito de símbolos, llamado alfabeto del autómata.

• δ es la función de transición donde δ: Q × Σ → Q.

• q0 es el estado inicial desde donde se procesa cualquier entrada (q0 ∈ Q).

• F es un conjunto de estados finales de Q (F ⊆ Q).

Mientras que gráficamente, un DFA se puede representar mediante diagramas llamados diagramas de estado donde:

• Los estados están representados por vertices.

• Las transiciones se muestran etiquetadas arcs.

• El estado inicial está representado por un empty incoming arc.

• El estado final está representado por double circle.

Ejemplo de DFA

Suponga que un DFA es

• Q = {a, b, c},

• Σ = {0, 1},

• q ₀ = {a},

• F = {c},

• La función de transición δ se muestra en la tabla de la siguiente manera:

Estado actual	Siguiente estado para la entrada 0	Siguiente estado para la entrada 1
UN	un	segundo
segundo	segundo	UN
C	C	C

La representación gráfica de este DFA sería la siguiente:

Automatización finita no determinista (NDFA)

Puede definirse como el tipo de automatización finita en el que para cada símbolo de entrada no podemos determinar el estado al que se moverá la máquina, es decir, la máquina puede moverse a cualquier combinación de estados. Tiene un número finito de estados, por eso la máquina se llama Automatización finita no determinista (NDFA).

Matemáticamente, NDFA se puede representar mediante una tupla de 5 (Q, Σ, δ, q0, F), donde -

• Q es un conjunto finito de estados.

• Σ es un conjunto finito de símbolos, llamado alfabeto del autómata.

• δ: -es la función de transición donde δ: Q × Σ → 2 ^Q .

• q0: -es el estado inicial desde donde se procesa cualquier entrada (q0 ∈ Q).

• F: -es un conjunto de estados finales de Q (F ⊆ Q).

Mientras que gráficamente (igual que DFA), un NDFA se puede representar mediante diagramas llamados diagramas de estado donde:

• Los estados están representados por vertices.

• Las transiciones se muestran etiquetadas arcs.

• El estado inicial está representado por un empty incoming arc.

• El estado final está representado por doble circle.

Ejemplo de NDFA

Suponga que un NDFA es

• Q = {a, b, c},

• Σ = {0, 1},

• q 0 = {a},

• F = {c},

• La función de transición δ se muestra en la tabla de la siguiente manera:

Estado actual	Siguiente estado para la entrada 0	Siguiente estado para la entrada 1
UN	a, b	segundo
segundo	C	a, c
C	antes de Cristo	C

La representación gráfica de este NDFA sería la siguiente:

Análisis morfológico

El término análisis sintáctico morfológico está relacionado con el análisis sintáctico de morfemas. Podemos definir el análisis sintáctico morfológico como el problema de reconocer que una palabra se descompone en unidades significativas más pequeñas llamadas morfemas que producen algún tipo de estructura lingüística para ella. Por ejemplo, podemos dividir la palabra zorros en dos, zorro y -es . Podemos ver que la palabra zorros , se compone de dos morfemas, uno es zorro y el otro es -es .

En otro sentido, podemos decir que la morfología es el estudio de:

• La formación de palabras.

• El origen de las palabras.

• Formas gramaticales de las palabras.

• Uso de prefijos y sufijos en la formación de palabras.

• Cómo se forman las partes del discurso (PoS) de un idioma.

Tipos de morfemas

Los morfemas, las unidades portadoras de significado más pequeñas, se pueden dividir en dos tipos:

• Stems

• Orden de las palabras

Tallos

Es la unidad central significativa de una palabra. También podemos decir que es la raíz de la palabra. Por ejemplo, en la palabra zorros, la raíz es zorro.

• Affixes- Como sugiere el nombre, agregan un significado adicional y funciones gramaticales a las palabras. Por ejemplo, en la palabra zorros, el afijo es - es.

Además, los afijos también se pueden dividir en los siguientes cuatro tipos:

• Prefixes- Como sugiere el nombre, los prefijos preceden a la raíz. Por ejemplo, en la palabra desabrochar, un es el prefijo.

• Suffixes- Como sugiere el nombre, los sufijos siguen a la raíz. Por ejemplo, en la palabra gatos, -s es el sufijo.

• Infixes- Como sugiere el nombre, los infijos se insertan dentro del tallo. Por ejemplo, la palabra taza llena se puede pluralizar como tazas llena usando -s como infijo.

• Circumfixes- Preceden y siguen la raíz. Hay muy pocos ejemplos de circunfijos en idioma inglés. Un ejemplo muy común es 'A-ing' donde podemos usar -A precede y -ing sigue a la raíz.

Orden de las palabras

El orden de las palabras se decidirá mediante análisis morfológico. Veamos ahora los requisitos para construir un analizador morfológico:

Léxico

El primer requisito para construir un analizador morfológico es el léxico, que incluye la lista de raíces y afijos junto con la información básica sobre ellos. Por ejemplo, la información como si la raíz es raíz de sustantivo o raíz de verbo, etc.

Morfotacticos

Es básicamente el modelo de ordenamiento de morfemas. En otro sentido, el modelo explica qué clases de morfemas pueden seguir a otras clases de morfemas dentro de una palabra. Por ejemplo, el hecho morfotáctico es que el morfema plural en inglés siempre sigue al sustantivo en lugar de precederlo.

Reglas ortográficas

Estas reglas de ortografía se utilizan para modelar los cambios que ocurren en una palabra. Por ejemplo, la regla de convertir y en ie en palabras como ciudad + s = ciudades, no ciudades.