EPED Practica2015

Estrategias de Programación
y Estructuras de Datos
Grado en Ingeniería Informática
Grado en Tecnologías de la Información

Práctica curso 2014-2015
Enunciado

Índice
1. Presentación del problema................................................................................................................3
2.Diseño...............................................................................................................................................3
2.1 Tipo de datos de referencia........................................................................................................3
2.2 Primera aproximación: lista de consultas ordenadas alfabéticamente.......................................5
Preguntas teóricas (trabajo delestudiante)..................................................................................6
2.3 Segunda aproximación: árbol de caracteres...............................................................................6
Preguntas teóricas (trabajo del estudiante)..................................................................................7
3.Implementación................................................................................................................................8
3.1 Parámetros de entrada................................................................................................................8
3.2 Estructura del fichero de consultas............................................................................................8
3.3 Estructura del fichero deoperaciones........................................................................................9
3.4 Medición de tiempos................................................................................................................10
Estudio empírico del coste temporal (trabajo del estudiante)...................................................10
3.5 Salida delprograma.................................................................................................................10
4. Ejecución y juegos de prueba.........................................................................................................11
5. Documentación y plazos de entrega...............................................................................................11

1. Presentación del problema
Cuando tecleamos nuestra consulta en un buscador Web, el buscadorpuede proporcionarnos
sugerencias de búsqueda mientras escribimos basándose en las consultas más frecuentes que han
hecho otros usuarios. En la imagen 1 vemos un ejemplo: El usuario está tecleando “practicas de
pro” y el buscador sugiere consultas como “practicas de programación en c”, que es una de las
consultas más frecuentes de los usuarios que tienen ese comienzo.

Imagen 1: Ejemplo desugerencias de búsqueda proporcionadas por Google

El objetivo de la práctica es simular un sistema de sugerencias de ese estilo. A partir de un histórico
de búsquedas (una lista de consultas – queries – realizadas con anterioridad) y una búsqueda
(query) incompleta, nuestro programa debe proporcionar una lista, ordenada por frecuencia
descendente, de las consultas compatibles con esa consultaincompleta.
El aspecto clave del programa es la elección de la estructura de datos con la que vamos a
representar el histórico de consultas:




Por un lado, el tamaño del histórico de búsquedas en un buscador Web es muy grande: de
hecho, puede ser varios órdenes de magnitud más grande que la propia Web. Por ello hay
que diseñar una estructura de datos que almacene toda la información sobre lasconsultas
usando el espacio en memoria de forma eficiente.
Por otro lado, las sugerencias de búsqueda hay que realizarlas dinámicamente (según el
usuario va tecleando) así que la estructura de datos debe permitir una consulta muy rápida.

2. Diseño.
En esta práctica trabajaremos con dos diseños alternativos para la estructura de datos: uno
inmediato pero poco eficiente, y otro más eficiente que tiene...