NLP y el Uso de Expresiones Regulares

Sun, Dec 15, 2019

El procesamiento de lenguaje natural es un área sumamente complicada del aprendizaje máquina, del procesamiento estadístico de datos y de la linguística. Para lo cual se han utilizado técnicas desde el conteo de letras, hasta el desarrollo de complejas redes neuronales.

Una de las técnicas básicas para el procesamiento de lenguaje es el uso de expresiones regulares. Una expresión regular es una cadena de caracteres que describe un patrón. El concepto de las expresiones regulares fue desarrollado por Christopher Kleene junto con el de lenguaje regular. Su uso se extendió en la programación mediante las utilidades del sistema Unix en los 60’s y 70’s.

Formalmente los procesadores de expresiones regulares son descritos por la teoría de autómatas, en ella el autómata consume los símbolos del texto y los resultados pueden ser actuar (capturar el símbolo) o no. Idealmente el procesamiento debe hacerse por Autómatas deterministas, o corremos el riesgo de que el autómata nunca acabe de procesar el texto.

Las expresiones regulares describen los patrones que queremos que sean “capturados” a continuación veremos los tipos de patrones mas simples:

Una expresión rtegular entonces, es una manera de describir un patrón para buscar coincidencias en una cadena de texto. Las expresiones regulares pueden servir para resolver los siguientes problemas:

Buscar un patrón
Extraer una subcadena
Reemplazar una subcadena

Una de mis librerías favoritas de expresiones regulares es RE2 la cual fue creada en Google y es utilizada también por Golang. Una de las características determinantes de RE2 es que no permite el uso de back-reference, las cuales no pueden ser implementadas eficientemente y en algunos casos pueden llegar a tener un comportamiento exponencial tanto en procesamiento como en memoria.

Referencia de sintaxis de RE2

Single characters:

. any character, possibly including newline (s=true)
[xyz] character class
[^xyz] negated character class
\d Perl character class
\D negated Perl character class
[[:alpha:]] ASCII character class
[[:^alpha:]] negated ASCII character class
\pN Unicode character class (one-letter name)
\p{Greek} Unicode character class
\PN negated Unicode character class (one-letter name)
\P{Greek} negated Unicode character class

Composites:

xy «x» followed by «y»
x|y «x» or «y» (prefer «x»)

Repetitions:

x* zero or more «x», prefer more
x+ one or more «x», prefer more
x? zero or one «x», prefer one
x{n,m} «n» or «n»+1 or … or «m» «x», prefer more
x{n,} «n» or more «x», prefer more
x{n} exactly «n» «x»
x*? zero or more «x», prefer fewer
x+? one or more «x», prefer fewer
x?? zero or one «x», prefer zero
x{n,m}? «n» or «n»+1 or … or «m» «x», prefer fewer
x{n,}? «n» or more «x», prefer fewer
x{n}? exactly «n» «x»
x{} (== x*) NOT SUPPORTED vim
x{-} (== x*?) NOT SUPPORTED vim
x{-n} (== x{n}?) NOT SUPPORTED vim
x= (== x?) NOT SUPPORTED vim

Implementation restriction: The counting forms «x{n,m}», «x{n,}», and «x{n}» reject forms that create a minimum or maximum repetition count above 1000. Unlimited repetitions are not subject to this restriction.

Possessive repetitions:

x*+ zero or more «x», possessive NOT SUPPORTED
x++ one or more «x», possessive NOT SUPPORTED
x?+ zero or one «x», possessive NOT SUPPORTED
x{n,m}+ «n» or … or «m» «x», possessive NOT SUPPORTED
x{n,}+ «n» or more «x», possessive NOT SUPPORTED
x{n}+ exactly «n» «x», possessive NOT SUPPORTED

Grouping:

(re) numbered capturing group (submatch)
(?P<name>re) named & numbered capturing group (submatch)
(?<name>re) named & numbered capturing group (submatch) NOT SUPPORTED
(?'name're) named & numbered capturing group (submatch) NOT SUPPORTED
(?:re) non-capturing group
(?flags) set flags within current group; non-capturing
(?flags:re) set flags during re; non-capturing
(?#text) comment NOT SUPPORTED
(?|x|y|z) branch numbering reset NOT SUPPORTED
(?>re) possessive match of «re» NOT SUPPORTED
re@> possessive match of «re» NOT SUPPORTED vim
%(re) non-capturing group NOT SUPPORTED vim

Flags:

i case-insensitive (default false)
m multi-line mode: «^» and «$» match begin/end line in addition to begin/end text (default false)
s let «.» match «\n» (default false)
U ungreedy: swap meaning of «x*» and «x*?», «x+» and «x+?», etc (default false) Flag syntax is «xyz» (set) or «-xyz» (clear) or «xy-z» (set «xy», clear «z»).

Empty strings:

^ at beginning of text or line («m»=true)
$ at end of text (like «\z» not «\Z») or line («m»=true)
\A at beginning of text
\b at ASCII word boundary («\w» on one side and «\W», «\A», or «\z» on the other)
\B not at ASCII word boundary
\G at beginning of subtext being searched NOT SUPPORTED pcre
\G at end of last match NOT SUPPORTED perl
\Z at end of text, or before newline at end of text NOT SUPPORTED
\z at end of text
(?=re) before text matching «re» NOT SUPPORTED
(?!re) before text not matching «re» NOT SUPPORTED
(?<=re) after text matching «re» NOT SUPPORTED
(?<!re) after text not matching «re» NOT SUPPORTED
re& before text matching «re» NOT SUPPORTED vim
re@= before text matching «re» NOT SUPPORTED vim
re@! before text not matching «re» NOT SUPPORTED vim
re@<= after text matching «re» NOT SUPPORTED vim
re@<! after text not matching «re» NOT SUPPORTED vim
\zs sets start of match (= \K) NOT SUPPORTED vim
\ze sets end of match NOT SUPPORTED vim
\%^ beginning of file NOT SUPPORTED vim
\%$ end of file NOT SUPPORTED vim
\%V on screen NOT SUPPORTED vim
\%# cursor position NOT SUPPORTED vim
\%'m mark «m» position NOT SUPPORTED vim
\%23l in line 23 NOT SUPPORTED vim
\%23c in column 23 NOT SUPPORTED vim
\%23v in virtual column 23 NOT SUPPORTED vim

Escape sequences:

\a bell (== \007)
\f form feed (== \014)
\t horizontal tab (== \011)
\n newline (== \012)
\r carriage return (== \015)
\v vertical tab character (== \013)
\* literal «», for any punctuation character «»
\123 octal character code (up to three digits)
\x7F hex character code (exactly two digits)
\x{10FFFF} hex character code
\C match a single byte even in UTF-8 mode
\Q...\E literal text «…» even if «…» has punctuation
\1 backreference NOT SUPPORTED
\b backspace NOT SUPPORTED (use «\010»)
\cK control char ^K NOT SUPPORTED (use «\001» etc)
\e escape NOT SUPPORTED (use «\033»)
\g1 backreference NOT SUPPORTED
\g{1} backreference NOT SUPPORTED
\g{+1} backreference NOT SUPPORTED
\g{-1} backreference NOT SUPPORTED
\g{name} named backreference NOT SUPPORTED
\g<name> subroutine call NOT SUPPORTED
\g'name' subroutine call NOT SUPPORTED
\k<name> named backreference NOT SUPPORTED
\k'name' named backreference NOT SUPPORTED
\lX lowercase «X» NOT SUPPORTED
\ux uppercase «x» NOT SUPPORTED
\L...\E lowercase text «…» NOT SUPPORTED
\K reset beginning of «$0» NOT SUPPORTED
\N{name} named Unicode character NOT SUPPORTED
\R line break NOT SUPPORTED
\U...\E upper case text «…» NOT SUPPORTED
\X extended Unicode sequence NOT SUPPORTED
\%d123 decimal character 123 NOT SUPPORTED vim
\%xFF hex character FF NOT SUPPORTED vim
\%o123 octal character 123 NOT SUPPORTED vim
\%u1234 Unicode character 0x1234 NOT SUPPORTED vim
\%U12345678 Unicode character 0x12345678 NOT SUPPORTED vim

Character class elements:

x single character
A-Z character range (inclusive)
\d Perl character class
[:foo:] ASCII character class «foo»
\p{Foo} Unicode character class «Foo»
\pF Unicode character class «F» (one-letter name)

Named character classes as character class elements:

[\d] digits (== \d)
[^\d] not digits (== \D)
[\D] not digits (== \D)
[^\D] not not digits (== \d)
[[:name:]] named ASCII class inside character class (== [:name:])
[^[:name:]] named ASCII class inside negated character class (== [:^name:])
[\p{Name}] named Unicode property inside character class (== \p{Name})
[^\p{Name}] named Unicode property inside negated character class (== \P{Name})

Perl character classes (all ASCII-only):

\d digits (== [0-9])
\D not digits (== [^0-9])
\s whitespace (== [\t\n\f\r ])
\S not whitespace (== [^\t\n\f\r ])
\w word characters (== [0-9A-Za-z_])
\W not word characters (== [^0-9A-Za-z_])
\h horizontal space NOT SUPPORTED
\H not horizontal space NOT SUPPORTED
\v vertical space NOT SUPPORTED
\V not vertical space NOT SUPPORTED

ASCII character classes:

[[:alnum:]] alphanumeric (== [0-9A-Za-z])
[[:alpha:]] alphabetic (== [A-Za-z])
[[:ascii:]] ASCII (== [\x00-\x7F])
[[:blank:]] blank (== [\t ])
[[:cntrl:]] control (== [\x00-\x1F\x7F])
[[:digit:]] digits (== [0-9])
[[:graph:]] graphical (== [!-~] == [A-Za-z0-9!"#$%&'()*+,-./:;<=>?@[\]^_`{|}~])
[[:lower:]] lower case (== [a-z])
[[:print:]] printable (== [ -~] == [ [:graph:]])
[[:punct:]] punctuation (== [!-/:-@[-`{-~])
[[:space:]] whitespace (== [\t\n\v\f\r ])
[[:upper:]] upper case (== [A-Z])
[[:word:]] word characters (== [0-9A-Za-z_])
[[:xdigit:]] hex digit (== [0-9A-Fa-f])