Story Transcript
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