Ciencias de la Computación FAMAF

Herramientas de usuario

Herramientas del sitio

Traza:
introalg:taller07_6

Diferencias

Muestra las diferencias entre dos versiones de la página.

Enlace a la vista de comparación

Ambos lados, revisión anteriorRevisión previa
Próxima revisión		Revisión previa
introalg:taller07_6 [2007/06/12 02:00] – nicolaswintroalg:taller07_6 [2018/08/10 03:03] (actual) – editor externo 127.0.0.1
Línea 2: Línea 2:
  
 Nos proponemos hacer un programa funcional que **cuente la frecuencia de las ocurrencias de palabras** en un texto. Nos proponemos hacer un programa funcional que **cuente la frecuencia de las ocurrencias de palabras** en un texto.
-El tipo de la función es es siguiente:+El tipo de la función es el siguiente:
  
 <code> <code>
Línea 8: Línea 8:
 </code> </code>
  
-Donde ''Palabra'' es un **sinónimo de tipo**, en este caso de un ''String'', y sirve para mejorar la legibilidad del código.+Donde ''Palabra'' es un **sinónimo de tipo**, en este caso de un ''String'', y sirve para mejorar la legibilidad del código. Para crear este sinónimo, tenemos que escribir:
  
 <code> <code>
Línea 19: Línea 19:
   [("hola",2),("que",1)]   [("hola",2),("que",1)]
  
-Esta función resulta de gran utilidad para **análisis estadístico de textos**, como el que se utiliza para comprimir archivos, dar importancia a las palabras en las búsquedas, detectar palabras significativas, etc.+Esta función resulta de gran utilidad para **análisis estadístico de textos**, como el que se utiliza para comprimir archivos, dar importancia a las palabras en las búsquedas en colecciones de documentos (o internet), detectar palabras significativas en documentos, etc.
  
  
Línea 26: Línea 26:
 ===== División en Palabras ===== ===== División en Palabras =====
  
-Para hacer más fácil el uso de esta función tomamos de [[http://www.cs.kent.ac.uk/people/staff/sjt/craft2e/|Haskell The Craft of Functional Programming]] por Simon Thompson, la definción de una función que **parte una cadena en palabras**, para no tener que meter a mano palabra por palabra.+Para hacer más fácil el uso de esta función tomamos de [[http://www.cs.kent.ac.uk/people/staff/sjt/craft2e/|Haskell The Craft of Functional Programming]] por Simon Thompson, la definción de una función que **parte una cadena en palabras**, para no tener que meter a mano palabra por palabra, con el formato de una lista de Strings, que sería bastante pesado.
  
 Veamos el código de "arriba para abajo" //top-down//, empezando desde la definición principal y terminando en las funciones básicas. Veamos el código de "arriba para abajo" //top-down//, empezando desde la definición principal y terminando en las funciones básicas.
Línea 64: Línea 64:
 espacio = ['\r','\n','\t',' '] espacio = ['\r','\n','\t',' ']
 </code> </code>
 +
  
 ==== Ejercicios ==== ==== Ejercicios ====
Línea 69: Línea 70:
   * Definir la función politípica //elemento :: Eq a => a -> [a] -> Bool//, donde //elemento a xs// decide si //a// está en la lista //xs//. Ejemplo: //elemento 'a' "Abracadabra" = True//, //elemento 10 [1..9] = False//.   * Definir la función politípica //elemento :: Eq a => a -> [a] -> Bool//, donde //elemento a xs// decide si //a// está en la lista //xs//. Ejemplo: //elemento 'a' "Abracadabra" = True//, //elemento 10 [1..9] = False//.
 Casos de Test: ''elemento [] [ [1,2],[],[3,4] ]'', ''elemento "sandia" ["pera","melon","uva"]''. Casos de Test: ''elemento [] [ [1,2],[],[3,4] ]'', ''elemento "sandia" ["pera","melon","uva"]''.
-  * Usando la definición de esta función probar //tomarPalabra//, //tirarEspacio//.+  * Habiendo definido //elemento//, probar las funciones //tomarPalabra//, //tirarEspacio//.
 Casos de Test: Casos de Test:
 <code> <code>
Línea 80: Línea 81:
 ... ...
 </code> </code>
-  * Las funciones //tiraEspacio//, //tiraPalabras// y //tomaPalabra// pueden ser generalizadas.+  * Las funciones //tiraEspacio//, //tiraPalabras// y //tomaPalabra// pueden ser **generalizadas**.
     * Defina la función //tomaMientras :: (a -> Bool) -> [a] -> [a]//, donde //tomaMientras p xs// devuelve todos los elementos mientras cumplan con el predicado //p//, al primero que no cumpla se para. Ejemplo: //tomaMientras (>0) [1,2,3,-1,3,2,1] = [1,2,3]//, //tomaMientras (=='a') "nada por aqui" = []//.     * Defina la función //tomaMientras :: (a -> Bool) -> [a] -> [a]//, donde //tomaMientras p xs// devuelve todos los elementos mientras cumplan con el predicado //p//, al primero que no cumpla se para. Ejemplo: //tomaMientras (>0) [1,2,3,-1,3,2,1] = [1,2,3]//, //tomaMientras (=='a') "nada por aqui" = []//.
     * Defina la función //tiraMientras :: (a -> Bool) -> [a] -> [a]//, donde //tiraMientras p xs// descarta todos los elementos mientras cumplan con el predicado //p//, al primero que no cumpla se para. Ejemplo: //tiraMientras (>0) [1,2,3,-1,3,2,1] = [-1,3,2,3]//, //tiraMientras (=='a') "nada por aqui" = "nada por aqui"//.     * Defina la función //tiraMientras :: (a -> Bool) -> [a] -> [a]//, donde //tiraMientras p xs// descarta todos los elementos mientras cumplan con el predicado //p//, al primero que no cumpla se para. Ejemplo: //tiraMientras (>0) [1,2,3,-1,3,2,1] = [-1,3,2,3]//, //tiraMientras (=='a') "nada por aqui" = "nada por aqui"//.
-    * ?Como se llaman //tomaMientras// y //tiraMientras// en el preámbulo standard? +    * ¿Cómo se llaman //tomaMientras// y //tiraMientras// en el preámbulo estándar? 
-  * Defina //tomaPalabra//, //tomaEspacio//, //tiraPalabra//, usando las anteriores. +  * Defina //tomaPalabra//, //tomaEspacio//, //tiraPalabra//, usando //tomaMientras//, //tiraMientras//.
- +
  
 ===== Lectura del Archivo ===== ===== Lectura del Archivo =====
Línea 114: Línea 113:
   ((take 100).partePalabras.leeArchivo) "14765-utf8.txt"   ((take 100).partePalabras.leeArchivo) "14765-utf8.txt"
   ["The","Project","Gutenberg","EBook","of","El","Gaucho","Mart\237n","Fierro, ...   ["The","Project","Gutenberg","EBook","of","El","Gaucho","Mart\237n","Fierro, ...
 +
  
  
 ==== Ejercicios ==== ==== Ejercicios ====
  
-  * Contar cuantas palabras hay en total.+  * Contar cuántas palabras hay en "El Gaucho Martín Fierro".
   * Obtener las palabras de "El Gaucho Martín Fierro" que tienen más de 15 letras.   * Obtener las palabras de "El Gaucho Martín Fierro" que tienen más de 15 letras.
-  * Observar que hay problemas con //partePalabras// y los signos de puntuación. ?Cómo mejoraría este aspecto de la función?+  * Observar que hay problemas con //partePalabras// y los signos de puntuación. ¿Cómo mejoraría este aspecto de la función?
  
  
Línea 138: Línea 138:
 agregaOcurrencia :: Palabra -> [(Palabra,Int)] -> [(Palabra,Int)] agregaOcurrencia :: Palabra -> [(Palabra,Int)] -> [(Palabra,Int)]
 </code> </code>
-que procesa una palabra, la definición de //frecuencia// es simplemente acumular toda la lista con esta función.+que procesa una palabra, sumando 1 al entero cada vez que se encuentra una ocurrencia de la palabra. La definición de //frecuencia// es simplemente acumular toda la lista con esta función. 
  
  
Línea 145: Línea 146:
 ==== Ejercicios ==== ==== Ejercicios ====
  
-  * Definir la función //agregaOcurrencia :: Palabra -> [(Palabra,Int)] -> [(Palabra,Int)]//, donde //agregarOcurrencia palabra xs// toma la lista //xs// de pares //(p,n)// y actualiza la lista de frecuencias para incorporar una nueva ocurrencia de //palabra//. Ejemplos: //agregaOcurrencia "hola" [] = [("hola",1)]//, //agregaOcurrencia "hola" [("hola",1),("que",1)] = [("hola",2),("que",1)]//.+  * Definir la función //agregaOcurrencia :: Palabra -> [(Palabra,Int)] -> [(Palabra,Int)]//, donde //agregaOcurrencia palabra xs// toma la lista //xs// de pares //(p,n)// y actualiza la lista de frecuencias para incorporar una nueva ocurrencia de //palabra//. Ejemplos: //agregaOcurrencia "hola" [] = [("hola",1)]//, //agregaOcurrencia "hola" [("hola",1),("que",1)] = [("hola",2),("que",1)]//.
 Casos de test: ''agregaOcurrencia "hola" [("hola",1)]'', ''agregaOcurrencia "que" [("hola",1)]''. Casos de test: ''agregaOcurrencia "hola" [("hola",1)]'', ''agregaOcurrencia "que" [("hola",1)]''.
   * A partir de //agregaOcurrencia// y //foldr// definir la función //frecuencia :: [Palabra] -> [(Palabra,Int)]//, donde //frecuencia xs// retorna la lista de frecuencias de cada una de las palabras de //xs//. Ejemplo: //frecuencia ["hola", "que", "hola"] = [("hola",2),("que",1)]//.   * A partir de //agregaOcurrencia// y //foldr// definir la función //frecuencia :: [Palabra] -> [(Palabra,Int)]//, donde //frecuencia xs// retorna la lista de frecuencias de cada una de las palabras de //xs//. Ejemplo: //frecuencia ["hola", "que", "hola"] = [("hola",2),("que",1)]//.
 Caso de test: ''frecuencia (partePalabras "Cantando me he de morir Cantando me han de enterrar") = [("enterrar",1),("de",2),("han",1),("me",2),("Cantando",2),("morir",1),("he",1)]'' Caso de test: ''frecuencia (partePalabras "Cantando me he de morir Cantando me han de enterrar") = [("enterrar",1),("de",2),("han",1),("me",2),("Cantando",2),("morir",1),("he",1)]''
   * Componer //frecuencia//, //take//, //partePalabras// y //leeArchivo// para computar la frecuencia de las primeras 10, 100, 1000 y 10000 palabras de "El Gaucho Martín Fierro". Cuidado, con 1000 y 10000 puede demorar un buen rato.   * Componer //frecuencia//, //take//, //partePalabras// y //leeArchivo// para computar la frecuencia de las primeras 10, 100, 1000 y 10000 palabras de "El Gaucho Martín Fierro". Cuidado, con 1000 y 10000 puede demorar un buen rato.
 +
  
  
 ===== Ordenando por frecuencias ===== ===== Ordenando por frecuencias =====
  
-El esquema presentado hasta ahora (''frecuencia.partePalabras.leeArchivo'') resulta poco útil, debido a que resulta esencial, conocer cuales son, por ejemplo, las **10 palabras más frecuentes** porque para:+El esquema presentado hasta ahora (''frecuencia.partePalabras.leeArchivo'') resulta poco útil, debido a que resulta esencial, conocer cuales son, por ejemplo, las **10 palabras más frecuentes**. Veamos la utilidad en distintos contextos:
  
   * Compresión de texto: estas palabras se deben codificar "cortito".   * Compresión de texto: estas palabras se deben codificar "cortito".
   * Relevancia de palabras para búsquedas: a estas palabras no hay que darles peso.   * Relevancia de palabras para búsquedas: a estas palabras no hay que darles peso.
-  * Detectar palabras significatias: simplemente son irrelevantes, se descartan.+  * Detectar palabras significativas: simplemente son irrelevantes, se descartan.
  
 La lista que devuelve //frecuencia// está ordenada según aparecen las palabras. La lista que devuelve //frecuencia// está ordenada según aparecen las palabras.
Línea 177: Línea 179:
 ordenaIns _      = [] ordenaIns _      = []
 </code> </code>
- 
- 
  
 ==== Ejercicios ==== ==== Ejercicios ====
Línea 187: Línea 187:
   * Agregar //ordenaInsFrec// como un eslabón más a la cadena de funciones ''(frecuencia.(take 1000).partePalabras.leeArchivo) "14765-utf8.txt" '' para obtener en forma creciente la frecuencia de las primeras 1000 palabras de "El Gaucho Martín Fierro".   * Agregar //ordenaInsFrec// como un eslabón más a la cadena de funciones ''(frecuencia.(take 1000).partePalabras.leeArchivo) "14765-utf8.txt" '' para obtener en forma creciente la frecuencia de las primeras 1000 palabras de "El Gaucho Martín Fierro".
   * Redefinir //ordenaInsFrec// a partir de //insertaOrdFrec// y **//foldr//**.   * Redefinir //ordenaInsFrec// a partir de //insertaOrdFrec// y **//foldr//**.
 +
 +
 +
  
  
Línea 195: Línea 198:
 ===== Optimización del Cómputo ===== ===== Optimización del Cómputo =====
  
-El cálculo de la frecuencia resulta ineficiente, por cada palabra tenemos que recorrer toda la lista de frecuencias ''[(Palabra,Int)]'' a fin de computar la nueva ocurrencia.+El cálculo de la frecuencia resulta ineficiente. Por cada palabra tenemos que recorrer toda la lista de frecuencias ''[(Palabra,Int)]'' a fin de incluir la nueva ocurrencia.
 De hecho para las aproximadamente 15000 palabras que contiene "El Gaucho Martín Fierro", este proceso toma su tiempo. De hecho para las aproximadamente 15000 palabras que contiene "El Gaucho Martín Fierro", este proceso toma su tiempo.
  
Línea 206: Línea 209:
 agregaOcurrenciaOrd palabra [] = [(palabra,1)] agregaOcurrenciaOrd palabra [] = [(palabra,1)]
 agregaOcurrenciaOrd palabra ((p,n):xs) | p==palabra = (p,n+1) : xs agregaOcurrenciaOrd palabra ((p,n):xs) | p==palabra = (p,n+1) : xs
-        | p<palabra  = (p,n) : agregaOcurrenciaOrd palabra xs+        | p<palabra  = (p,n)   : agregaOcurrenciaOrd palabra xs
         | p>palabra  = (palabra,1) : (p,n) : xs         | p>palabra  = (palabra,1) : (p,n) : xs
  
Línea 232: Línea 235:
  
 Podemos intentar cambiar de manera salvaje la **estructura de datos**, es decir cambiar la //lista de pares// por otra estructura que **mejore el tiempo de búsqueda de una palabra**. Podemos intentar cambiar de manera salvaje la **estructura de datos**, es decir cambiar la //lista de pares// por otra estructura que **mejore el tiempo de búsqueda de una palabra**.
 +
 Una de las estructuras de datos más comunes que mejora de manera dramática el tiempo de búsqueda son los [[http://es.wikipedia.org/wiki/%C3%81rbol_binario_de_b%C3%BAsqueda|Árboles Binarios de Búsqueda]] o ABB. Una de las estructuras de datos más comunes que mejora de manera dramática el tiempo de búsqueda son los [[http://es.wikipedia.org/wiki/%C3%81rbol_binario_de_b%C3%BAsqueda|Árboles Binarios de Búsqueda]] o ABB.
  
Línea 272: Línea 276:
   Main> :set -u   Main> :set -u
   Main> (frecuencia''.(take 100).partePalabras.leeArchivo) "14765-utf8.txt"   Main> (frecuencia''.(take 100).partePalabras.leeArchivo) "14765-utf8.txt"
-ArbolFrec_Nodo ("Palacio.",1) (ArbolFrec_Nodo ("by",3) (ArbolFrec_Nodo ("formatted",1) (ArbolFrec_Nodo ("set",1) (ArbolFrec_Nodo ("www.gutenberg.net",1) ArbolFrec_Nulo (ArbolFrec_Nodo ("this",1) (ArbolFrec_Nodo ("with",2) ...+  ArbolFrec_Nodo ("Palacio.",1) (ArbolFrec_Nodo ("by",3) (ArbolFrec_Nodo ("formatted",1) (ArbolFrec_Nodo ("set",1) (ArbolFrec_Nodo ("www.gutenberg.net",1) ArbolFrec_Nulo (ArbolFrec_Nodo ("this",1) (ArbolFrec_Nodo ("with",2) ...
  
-... y esto no se entiende nada.+... y esto no se entiende nada!
 Entonces definimos una función que "aplana" el árbol en una lista, de forma tal que lo podamos leer y también ordenarlo. Entonces definimos una función que "aplana" el árbol en una lista, de forma tal que lo podamos leer y también ordenarlo.
  
Línea 288: Línea 292:
   [("Palacio.",1),("by",3),("formatted",1),("set",1),("www.gutenberg.net",1), ...   [("Palacio.",1),("by",3),("formatted",1),("set",1),("www.gutenberg.net",1), ...
   (58403 reductions, 104322 cells)   (58403 reductions, 104322 cells)
 +
  
 Woohoo! Woohoo!
Línea 298: Línea 303:
 | frecuencia'' | 58K | 0.66M | 8.42M | | frecuencia'' | 58K | 0.66M | 8.42M |
  
-Notar que la mejora de //frecuencia''// es mucho más que lineal, para 100 palabras es 1.17 veces más rápido que el standard //frecuencia//, para 1000 es 2.43 veces más rápido y finalmente para 10000 palabras es 7.24 veces más rápido.+Notar que la mejora de //frecuencia' '// es mucho más que lineal, para 100 palabras es 1.17 veces más rápido que el standard //frecuencia//, para 1000 es 2.43 veces más rápido y finalmente para 10000 palabras es 7.24 veces más rápido.
  
  
introalg/taller07_6.1181613617.txt.gz · Última modificación: 2018/08/10 03:03 (editor externo)