Expresiones regulares y distancia de edici´on. Francisco Barreras QUANTIL S.A.S.

19 de agosto de 2015

Francisco Barreras (QUANTIL S.A.S.)

Expresiones regulares y distancia de edici´ on.

19 de agosto de 2015

1 / 31

Introducci´on ¿Qu´ e son expresiones regulares? Son la notaci´on est´andar para caracterizar secuencias de texto. Una expresi´on regular es un patr´ on de b´ usqueda que al aplicarse a una linea de texto, nos dice si contiene o no el patr´on. Algunos editores de texto como Word las usan para encontrar o reemplazar palabras, pero sirven para b´ usquedas mucho m´as complejas.

Francisco Barreras (QUANTIL S.A.S.)

Expresiones regulares y distancia de edici´ on.

19 de agosto de 2015

2 / 31

Algunos ejemplos

Con expresiones regulares podemos hacer tareas como: Buscar todos los precios en un texto. Identificando todos los strings que sean como $1.999 o $1’000.000 Buscar todas las palabras que empiecen por may´ uscula en un texto. Identificar los URLs en un tweet o status de Facebook. Identificar las palabras que est´an entre una palabra de negaci´on y un signo de puntuaci´on.

Francisco Barreras (QUANTIL S.A.S.)

Expresiones regulares y distancia de edici´ on.

19 de agosto de 2015

3 / 31

Algunas definiciones

String: Es una secuencia de s´ımbolos alfanum´ericos. El espacio se trata como un s´ımbolo m´as y se denota como . Expresi´ on Regular: Es un patr´ on de b´ usqueda que define un conjunto de Strings. A saber, los strings con los que hace match. Lenguaje generado: Son todos los strings que hacen match con una expresi´ on regular dada. Corpus: Es el conjunto de strings al que se le hace la b´ usqueda o reemplazo. Puede ser un documento, un tweet o una linea de texto.

Francisco Barreras (QUANTIL S.A.S.)

Expresiones regulares y distancia de edici´ on.

19 de agosto de 2015

4 / 31

¿C´omo opera una expresi´on regular?

Aplicaci´on Dependiendo del software que se utilice, una expresi´ on regular puede retornar: BOOLEAN: Si el string contiene el patr´ on buscado. INDEX: Los ´ındices de inicio y fin del patr´ on emparejado en el string. ´ PATRON: Para b´ usquedas complejas, me puede interesar el patr´on encontrado como tal. En R el paquete base tiene funciones como grep, grepl y gsub que nos ayudan en estas tareas.

Francisco Barreras (QUANTIL S.A.S.)

Expresiones regulares y distancia de edici´ on.

19 de agosto de 2015

5 / 31

Patr´on de b´usqueda simple

Una expresi´ on regular puede consistir de un s´ olo caracter o de varios caracteres. Para Pearl (El lenguaje que maneja expresiones regulares), las may´ usculas y las min´ usculas son caracteres diferentes.

Francisco Barreras (QUANTIL S.A.S.)

Expresiones regulares y distancia de edici´ on.

19 de agosto de 2015

6 / 31

Disjunci´on

¿Qu´e pasa si queremos buscar un patr´ on m´as amplio, como ”banco”´o ”Banco¿ En este caso necesitamos una disjunci´ on.

Disjunci´on Para indicar que queremos un caracter u otro, usamos el operador [ ]. Para buscar ”banco.o ”Banco”necesitamos la siguiente expresi´on regular: /[Bb]anco/

Francisco Barreras (QUANTIL S.A.S.)

Expresiones regulares y distancia de edici´ on.

19 de agosto de 2015

7 / 31

Disjunci´on

Rangos Los rangos nos permiten abreviar algunas expresiones regulares. /[2-7]/ busca todos los d´ıgitos entre 2 y 7. /[A-G]/ busca todas las may´ usculas entre A y G. /[a-fk-o/ busca todas las min´ usculas entre la a y la f, y entre la k y la o.

Francisco Barreras (QUANTIL S.A.S.)

Expresiones regulares y distancia de edici´ on.

19 de agosto de 2015

8 / 31

Negaci´on

¿Qu´e pasa si queremos excluir algunos caracteres de la b´ usqueda?

Negaci´on Para negar inclu´ımos el s´ımbolo ˆ al comienzo de los corchetes cuadrados []. /[ˆsS]/ encuentra lo que no sea ”S” o ”s”. /[ˆ( [a-z] )]/ retorna ”no una palabra de una sola letra min´ uscula”.

Francisco Barreras (QUANTIL S.A.S.)

Expresiones regulares y distancia de edici´ on.

19 de agosto de 2015

9 / 31

Cuantificadores

A menudo queremos buscar distinto n´ umero de ocurrencias de un patr´on. Los Cuantificadores nos ayudan a incorporar esta idea en nuestras expresiones regulares. Los s´ımbolos ?,+,*,{,} son cuantificadores. /ho+la/ empareja ”hola”,”hoola” y ”hooooooola”. /perros?/ empareja ”perro” o ”perros”.

Francisco Barreras (QUANTIL S.A.S.)

Expresiones regulares y distancia de edici´ on.

19 de agosto de 2015

10 / 31

Cuantificadores

Cuantificadores ? sirve para emparejar cero o una ocurrencia del caracter anterior. + se conoce como Kleene plus sirve para emparejar una o m´as ocurrencias del caracter anterior. * se conoce como Kleene star sirve para emparejas cero o m´as ocurrencias del caracter anterior. {m,n} sirve para emparejar entre m y n ocurrencias del caracter anterior.

Francisco Barreras (QUANTIL S.A.S.)

Expresiones regulares y distancia de edici´ on.

19 de agosto de 2015

11 / 31

Anclas

A menudo queremos ubicar una expresi´ on s´ olo al comienzo de una linea, o queremos especificar que una expresi´ on est´e antes de acabar una palabra. ¿C´omo buscamos la palabra ”humo”, sin encontrar tambi´en la palabra ”humor”? ¿C´omo encontramos las lineas que empiezen por un n´ umero en la Biblia? Usamos anclas.

Ejemplo / \b humo\b / /ˆ[1-9]+/

Francisco Barreras (QUANTIL S.A.S.)

Expresiones regulares y distancia de edici´ on.

19 de agosto de 2015

12 / 31

Anclas

Anclas ˆ al inicio de una expresi´ on regular significa que va a buscar el patr´on al inicio del string proporcionado. $ al final de una expresi´ on regular significa que va a buscar el patr´on al final del string proporcionado. \b se empareja con la frontera de una palabra. \B se empareja con lo que no sea la frontera de una palabra. * Noten que a veces se usa el \ para distinguir los caracteres tradicionales de los operadores.

Francisco Barreras (QUANTIL S.A.S.)

Expresiones regulares y distancia de edici´ on.

19 de agosto de 2015

13 / 31

Wildcards Los wildcards son otras herramientas que nos ayudan a ahorrar tiempo al escribir expresiones regulares y hacen todo m´as f´acil. ¿C´omo buscamos todas las lineas que contengan dos veces la palabra Banagrario?

Wildcards \W o Whitespace busca cualquier espacio, tabulaci´on o enter en el string seleccionado. \w o Not whitespace busca cualquier caracter alfanum´erico. . busca cualquier caracter. /Banagrario . * Banagrario/ es la expresi´ on que buscamos.

Francisco Barreras (QUANTIL S.A.S.)

Expresiones regulares y distancia de edici´ on.

19 de agosto de 2015

14 / 31

Disjunci´on

Para buscar una u otra expresi´ on regular, usamos el operador |. /perros|gatos/ busca los patrones ”perro” o ”gato”. ¿Qu´e pasa si en un texto quiero buscar los patrones ”pr´ıncipe” o ”princesa”? /pr´ıncipe|esa/ va a emparejas ”pr´ıncipe” o ”esa”. Necesitamos agrupar la subexpresi´ on donde nos interesa hacer la disjunci´on. /pr´ınc(ipe|esa)/ es la expresi´ on que buscamos.

Francisco Barreras (QUANTIL S.A.S.)

Expresiones regulares y distancia de edici´ on.

19 de agosto de 2015

15 / 31

Backtracking

A veces me interesa referirme a una expresi´ on regular que encontr´e. Bien para sustituir, o para buscar varias veces algo indeterminado. Cuando envolvemos una expresi´ on regular en par´entesis ( ) , esta queda almacenada en la primera vacante de memoria. Los siguientes par´entesis se guardan en las vacantes sucesivas. Para llamar a esas expresiones guardadas se usa \1, \2, etc.

Ejemplo ¿C´ omo buscamos si un adverbio se repite en un texto? /([a-z]+).* \1/ es la expresi´ on que necesitamos.

Francisco Barreras (QUANTIL S.A.S.)

Expresiones regulares y distancia de edici´ on.

19 de agosto de 2015

16 / 31

Tutorial pr´actico

Tutorial Una buena fuente de material para repasar este lenguaje es: REGEXONE

Francisco Barreras (QUANTIL S.A.S.)

Expresiones regulares y distancia de edici´ on.

19 de agosto de 2015

17 / 31

Miner´ıa de texto en acci´on

Cuando se hace miner´ıa de texto en redes sociales, a menudo se requiere hacer procesamiento. Veamos algunos ejemplos:

Ejercicio 1 ¿C´ omo podemos convertir un tweet en una lista de palabras usando R?

Francisco Barreras (QUANTIL S.A.S.)

Expresiones regulares y distancia de edici´ on.

19 de agosto de 2015

18 / 31

Miner´ıa de texto en acci´on

Ejercicio 2 Reducir palabras que tengan una misma letra repetida a una sola instancia de esa letra. Exceptuando e,l y r. Pasar de ”Hooooooooola” a ”Hola”.

Francisco Barreras (QUANTIL S.A.S.)

Expresiones regulares y distancia de edici´ on.

19 de agosto de 2015

19 / 31

Miner´ıa de texto en acci´on

Ejercicio 3 Procesar un Hashtag de manera que ”# HolaMundo” se convierta en ”Hola Mundo”. Esto nos permite identificar palabras en el hashtag que pueden tener informaci´on.

Francisco Barreras (QUANTIL S.A.S.)

Expresiones regulares y distancia de edici´ on.

19 de agosto de 2015

20 / 31

Miner´ıa de texto en acci´on

Ejercicio 4 Queremos identificar donde hay un URL, y reemplazarlo con el string ”URL”.

Francisco Barreras (QUANTIL S.A.S.)

Expresiones regulares y distancia de edici´ on.

19 de agosto de 2015

21 / 31

Expresiones regulares y distancia de edici´on. Francisco Barreras QUANTIL S.A.S.

19 de agosto de 2015

´ M´INIMA DISTANCIA DE EDICION

Francisco Barreras (QUANTIL S.A.S.)

Expresiones regulares y distancia de edici´ on.

19 de agosto de 2015

22 / 31

¿Qu´e es?

Supongamos que quiere saber qu´e tan parecidas son dos palabras. Hay varias operaciones que se pueden usar para transformar una palabra. La distancia m´ınima de edici´ on es el m´ınimo de operaciones necesarias para llegar de una palabra a la otra.

Ediciones permitidas Insertion: Insertar un caracter. Por ejemplo ’Oscuro’ → ’Obscuro’. Deletion: Borrar un caracter. Por ejemplo ’Mortal’ → ’Moral’. Sustituci´ on: Reemplazar un caracter por otro. Por ejemplo ’Carta’ → ’Carga’

Francisco Barreras (QUANTIL S.A.S.)

Expresiones regulares y distancia de edici´ on.

19 de agosto de 2015

23 / 31

Distancia entre dos palabras

Se le puede asignar un costo a cada operaci´ on. Insertion y Deletion tienen un costo de 1. Usualmente la sustituci´ on tiene un costo de 2. Francisco Barreras (QUANTIL S.A.S.)

Expresiones regulares y distancia de edici´ on.

19 de agosto de 2015

24 / 31

¿Para qu´e sirve?

Correcci´on ortogr´afica: Dado un error ortogr´afico, ¿Qu´e palabra es la que verdaderamente quer´ıa ponef el usuario? Biolog´ıa computacional: Dados los genomas de varias especies, ¿Cu´ales especies son m´as cercanas de acuerdo a sus genomas? Reconocimiento de lenguaje:Dada una transcripci´on de sonidos, ¿A qu´e palabras de un diccionario son m´as cercanas las transcripciones?

Francisco Barreras (QUANTIL S.A.S.)

Expresiones regulares y distancia de edici´ on.

19 de agosto de 2015

25 / 31

Programaci´on din´amica Programaci´ on din´ amica es el nombre de una clase de algoritmos. La intuici´on consiste en resolver los problemas recursivamente. Se solucionan problemas m´as complejos, solucionando problemas m´as sencillos primero.

Francisco Barreras (QUANTIL S.A.S.)

Expresiones regulares y distancia de edici´ on.

19 de agosto de 2015

26 / 31

Algoritmo de distancia de edici´on

Las distancias m´as f´aciles de calcular son entre una palabra vac´ıa y una palabra. Es claro que: D(0, i) = i D(i, 0) = i La intuici´on nos dice que D(i, j) = 1 + D(i − 1, j) si hay una insertion. Igualmente D(i, j) = 1 + D(i, j − 1) si hay una deletion Si hay un sustituci´ on entonces D(i, j) = 2 + D(i − 1, j − 1)

Francisco Barreras (QUANTIL S.A.S.)

Expresiones regulares y distancia de edici´ on.

19 de agosto de 2015

27 / 31

Algoritmo de distancia de edici´on

Francisco Barreras (QUANTIL S.A.S.)

Expresiones regulares y distancia de edici´ on.

19 de agosto de 2015

28 / 31

Tabla de distancia minima de edici´on

Francisco Barreras (QUANTIL S.A.S.)

Expresiones regulares y distancia de edici´ on.

19 de agosto de 2015

29 / 31

Tabla de distancia m´ınima de edici´on

Francisco Barreras (QUANTIL S.A.S.)

Expresiones regulares y distancia de edici´ on.

19 de agosto de 2015

30 / 31

Tareas

Tareas Hacer el ejercicio 3 de aplicaciones en R. Calcule la distancia de edici´ on entre ”Lomalinda” y ”Millonada” llenando la matriz de distancia m´ınima de edici´ on. Averiguar que palabra est´a m´as cerca a ”Agrario” entre ”Gracias” y ”Ar´abigo”. Escribir un programa en R que obtenga la palabra m´as frecuente que empieza por a y termina en n, de un corpus grande de su escogencia.

Francisco Barreras (QUANTIL S.A.S.)

Expresiones regulares y distancia de edici´ on.

19 de agosto de 2015

31 / 31