Técnicas de Intercalación

La ordenación de datos por intercalación es un proceso muy frecuente en programación. Esta operación es también un proceso que las personas encuentran comúnmente en sus rutinas diarias. Por ejemplo, cada elemento de la colección de datos de una agenda telefónica tiene un campo nombre, dirección y un número de teléfono. Una colección de datos clasificados se puede almacenar en un archivo, un vector o tabla, una lista enlazada o un árbol. Cuando los datos están almacenados en vectores, tablas (arrays), lista enlazadas o arboles, la ordenación se denomina ordenación interna. Cuando los datos a clasificar se encuentran almacenados en archivos, en soporte de almacenamiento masivo (cintas o discos) el proceso de ordenación se denomina ordenación externa.

Es un proceso utilizado en sistema de actualización, y en casos en que es necesario varias listas ordenadas. También es la única forma que hay para el ordenamiento de archivos, debido a la imposibilidad de almacenarlos en memoria y a limitaciones en el tiempo, por la cantidad de elementos a ordenar.

Es el caso más simple, cuando se intercalan dos listas o archivos. Suponga que se tienen los arreglos ordenados A1 y A2 con elementos n1 y n2 respectivamente. Se desean intercalar en el arreglo A3.

El problema de ordenamiento se puede reducir a uno de intercalación. Si se quiere ordenar una lista muy grande, se puede pensar en subdividir esa lista en sublistas de un elemento, luego intercalar dos sublistas, para obtener sublistas ordenadas de dos elementos, luego de cuatro, etc., hasta obtener la lista ordenada, o tomar sublistas de L elementos, ordenarlas por cualquier algoritmo de ordenamiento y luego intercalarlas.

Existe diferentes tipos de métodos de intercalación, entre ellos se destacarán los siguientes:

Intercalación Simple: 

Se tienen dos archivos ordenados y se obtiene al final un solo archivo ordenado que contiene los elementos de los dos archivos iniciales.

Para utilizar el método se inicia con un vector de n posiciones. Comencemos con el subíndice i en la segunda posición incrementa en 1, el elemento del subíndice del vctor se elimina de la secuencia y se reinserta en el vector en la posición adecuada.

Ejemplo:

Intercalación Binaria:
El algoritmo de ordenación por intercalación simple requiere una exploración o búsqueda secuencial para localizar la posición de un elemento en la sublista ordenada, si en lugar de considerar una búsqueda secuencial se realizara una búsqueda binaria se mejoraría considerablemente el algoritmo y se aumentaría la velocidad de ejecución. Esta modificación se conoce como método de intercalación binaria. Este algoritmo utiliza la técnica de dividir y conquistar por lo tanto, divide al vector y toma un elemento pivote y compara contra él los elementos del vector dividido.

Intercalación Balanceada:

Una intercalación balanceada de m vías utiliza m archivos de entrada y m archivos de de salida. Las k listas ordenadas se distribuyen en forma uniforme en los m archivos de entrada. Se intercalan las listas de cada uno de los archivos, distribuyendo en forma uniforme las listas resultantes en los archivos de salida (de mayor tamaño que las iniciales). Se repite el último paso hasta que un archivo de salida contiene una lista ordenada.

Intercalación Polifásica:
Una intercalación polifásica de m vías utiliza 2*m-1 archivos de entrada y 1 archivo de salida. Las k listas se distribuyen en forma no uniforme en los 2*m-1 archivos de entrada.

Se intercalan las listas (de mayor tamaño) en el archivo de salida. El archivo de entrada que primero queda vacío pasa a ser archivo de salida y el archivo de salida pasa a ser de entrada. Se repiten los 2 últimos pasos hasta que un archivo de salida contenga la lista ordenada.

Técnicas de Extracción 

Son extracción de frases principales, cuyo objetivo es seleccionar palabras o frases individuales para "etiquetar" un documento, y sumarización de documentos, cuyo objetivo es seleccionar oraciones enteras para crear sumarios formados por párrafos cortos. 

Una extracción de frases principales posiblemente extraiga: Álvaro García Linera, río Iténez, cien mil tortugas fueron liberadas. Estas están presentes en el texto. En contraste, un sistema de extracción abstracta de alguna forma interiorizaría el contenido y las frases generadas posiblemente serían más descriptivas y más parecidas a lo que un humano generaría, protección de las tortugas, negligencia humana pone en peligro la existencia de las tortugas, acciones de protección y cuidado de la naturaleza. Se puede notar que estas frases no están presentes en el texto y requieren una comprensión de este, lo cual hace difícil para las computadoras producir tales frases.

Luego los clasificadores pueden aprender en función de las características de los textos y discriminar entre ejemplos negativos y positivos. Algunos clasificadores realizan una clasificación binaria para un ejemplo testeado, mientras que otros asignan probabilidades a las frases. Por ejemplo del ejemplo anterior puede aprender que las frases que comienzan con mayúsculas pueden ser frases principales.Después de entrar, se pueden seleccionar frases principales para testear los documentos de la siguiente manera. Se aplica la misma estrategia de generación de ejemplos para los documentos de prueba, luego se corre cada ejemplo. Se pueden determinar las frases principales mirando las decisiones dadas por el clasificador binario o las probabilidades o el modelo aprendido. Si las probabilidades son dadas, un umbral es utilizado para seleccionar las frases principales.

Los sistemas encargados de extraer frases principales por lo general son evaluados usando la precisión y el recobrado. La precisión mide cuantas frases propuestas son realmente correctas. El recobrado mide cuantas frases de las correctas en el sistema son brindadas. Las dos medidas pueden ser combinadas en la F-Medida, la cual combina armónicamente las dos (F=2PR/(P+R)). Las comprobaciones entre las frases propuestas y las conocidas pueden ser chequeadas después de procesos de lematización u otras estrategias de normalización de textos.

Técnicas de Búsqueda

La búsqueda es la operación más importante en el procesamiento de información, ya que permite recuperar datos previamente almacenados. El resultado de una búsqueda puede ser un éxito, si se encuentra la información o un fracaso, si no la encuentra.

La búsqueda se puede aplicar sobre elementos previamente ordenados o sobre elementos desordenados, en el primer caso la búsqueda es más fácil, en cambio en el segundo se dificulta un poco más el proceso, sobre todo cuando se trata de encontrar un cantidad de elementos similares.

Para recuperar los datos, es necesario únicamente conocer la clave del elemento, a la cual se le aplica la función resumen. El valor obtenido se mapea al espacio de direcciones de la tabla.

Si el elemento existente en la posición indicada en el paso anterior tiene la misma clave que la empleada en la búsqueda, entonces es el deseado. Si la clave es distinta, se ha de buscar el elemento según la técnica empleada para resolver el problema de las colisiones al almacenar el elemento.

La recuperación de información es una de las aplicaciones más importantes de las computadoras, La búsqueda de información está relacionada con las tablas para consultas, Estas tablas contienen una cantidad de información que se almacenan en forma de lista de parejas de datos. Por ejemplo un catalogo con una lista de libros de matemáticas, en donde es necesario buscar con frecuencia elementos de una lista. Existen diferentes tipos de búsqueda, tipo Secuencial y Binaria.

Búsqueda Interna:

Es aquella en la que todos los elementos de la estructura estática (arreglo) o dinámica (lista ligada o árbol) se encuentran almacenados en la memoria principal de la computadora.

Los métodos de búsqueda interna más importante son:

• Secuencial o Lineal.
• Binaria.
• Hash (transformación de claves).

Búsqueda Externa:

La búsqueda externa es aquella e la que todos los elementos se encuentran almacenados en un archivo, el cual se encuentran en un dispositivo de almacenamiento secundario como un disco duro, una cinta o una memoria usb.

Los métodos de búsqueda externa más importante son:

• Secuencial.
• Binaria.
• Hash (transformación de claves).

Búsqueda Secuencial

El método de búsqueda secuencial consiste en revisar la estructura de datos elemento por elemento hasta encontrar el dato que estamos buscando, o hasta llegar al final de la estructura de datos. Normalmente cuando una función de búsqueda concluye con éxito, lo que interesa es conocer en qué posición fue encontrado el elemento buscado. La búsqueda secuencial se puede aplicar a estructuras de datos ordenadas o desordenadas.

Se aplica a una estructura desordenada y el elemento que se está buscando existe más de una vez en la estructura, el proceso de búsqueda debe continuar hasta que se llegue al fin de la estructura.

Este método se usa para buscar un elemento de un vector, es explorar secuencialmente el vector. es decir, recorrer el vector desde el prior elemento hasta el último. Si se encuentra el elemento buscado se debe visualizar un mensaje similar a "Fin de Búsqueda" o "Elemento Encontrado" y otro que diga "posición=" en caso contrario, visualizar un mensaje similar a "Elemento no existe en la Lista". Este tipo de búsqueda compara cada elemento del vector con el valor a encontrar hasta que este se consiga o se termine de leer el vector completo.

Si la búsqueda se aplica a un archivo desordenado y el elemento que se está buscando existe más de una vez, el proceso de búsqueda debe continuar hasta que se llegue al fin del archivo.

Es un método sumamente simple que resulta útil cuando se tiene un conjunto de datos pequeños (hasta aproximadamente 500 elementos). Consiste en:

• Almacenar todos los registros e un arreglo o lista.
• Insertar cada registro al final del arreglo o lista.
• Recorrer sobre el arreglo o lista hasta conseguir el elemento requerido.

Búsqueda Directa

Cuando la información almacenada en una base de datos es homogénea, por ejemplo alfanumericamente, es posible utilizar algoritmos tradicionales de búsqueda (arreglos ordenados, búsqueda binaria, árboles balanceados, hashing. etc) para recuperar un registro dado una llave.

En una base de datos tradicional la información es ordenada solo por algunos campos, que son llamados "campos llave", mientras que se deja en la libertad el resto de los campos de un registro. Cuando se indexa por cualquier campo también se realiza búsqueda directa. Es incluso posible hacer con cargos en cualquiera de los campos, por ejemplo:

selec nombre, apellido, edad from DATOSPERSONAL

El arreglo de palabras definidas en el diccionario se encuentra ordenado alfabéticamente no tiene palabras repetidas, pero tiene una variable para almacenar las ocurrencias de la palabra en el texto y la posición en que se encuentra cada ocurrencia.

Se puede definir de manera más general el concepto de búsqueda directa, teniendo en cuenta que nuestra implementación fue hecha utilizando las bases de datos de un diccionario. Dada una llave (palabra), buscamos los documentos (conceptos) que contienen las palabras definidas en el diccionario. Si la palabra encontró, devolver la definición que corresponde a la palabra, si no, regresar un mensaje de palabras no encontrada o simplemente nada.

Técnicas de Hashing

Las técnicas de búsqueda basadas en comparaciones, tal como los enfoques secuencuales no son muy eficientes en velocidad y recuperación de información. Hashing es una metodología altamente eficiente para ambas operaciones.

Consiste en una transformación matemática de una clave k con una función h(k) que da como resultado la posición de k en una tabla (llamada también transformación key-to-address o KAT). La función hash h(k) toma como entrada una clave k y produce como resultado un valor entero distribuido uniformemente en un arreglo determinado. este valor se usa como indice para la búsqueda o inserción de un dato en un arreglo llamado también "tabla de hash" o también "tabla dispersa".

Una desventaja de hashing es que el conjunto de posibles claves es siempre mayor al número de espacios disponibles, es decir, dos o más claves pueden asignarse a la misma dirección en la tabla hash. Cuando dos claves se direccionan a la misma dirección o bucket se dice que hay una colisión y a las claves se les denomina sinónimos.

Cuando hay unas colisiones se requieren de un proceso adicional para encontrar una posición disponible para la clave. Esto obviamente degrada la eficiencia del método, por lo que se trata de evitar al máximo esta situación.

q

Ventajas:

• Se pueden usar los valores naturales de la llave, puesto que se traducen internamente a direcciones fáciles de localizar.
• Se logra independencia lógica y física, debido a que los valores de las llaves son independientes del espacio de direcciones.
• No se requiere almacenamiento adicional para los índices.

Desventajas:

• El archivo no está clasificado.
• No permite llaves repetidas.
• Solo permite acceso por una sola llave.
• Costos.
• Tiempo de procesamiento requerido para la aplicación de la función hash.

Búsqueda Binaria

El método de búsqueda binaria divide el total de los elementos en dos, comparando el elemento buscado con el central, en caso de no ser iguales, se determina si el elemento buscado es menor o mayor al central, para determinar si la búsqueda continua del lado izquierdo (menor) o derecho (mayor) del central, repitiendo el mismo proceso de división y comparación, hasta encontrar el elemento buscado o que la división ya no sea posible.

Debemos destacar que este método de búsqueda solo funciona con estructuras de datos previamente ordenadas, dividiendo cada vez a la mitad el proceso de búsqueda, lo que hace que el método sea más eficiente.

Ejemplo: si tenemos una estructura ordenada 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 y estamos buscando el número 5, el resultado de la búsqueda nos mostraría la  posición 4 y el proceso terminaría ya que el elemento buscado no es diferente al que está en la posición central.

Este proceso debe sumar la posición inicial y la final, dividiendo el resultado de la suma entre dos para obtener la posición central generada por el cociente de la división, en este caso es (0+9)/2=4, esta posición se compara con el elemento que estamos buscando y como son iguales la búsqueda se detiene mostrando la posición donde lo encontró.

Técnicas de Ruptura

La búsqueda binaria consiste en dividir el intervalo de búsqueda en dos partes, comparando el elemento buscado con el que ocupa la posición central en el arreglo, y se utiliza para acortar el tiempo de búsqueda.

Ubicando el elemento central de array sumado la primera y la segunda posición de este y lo divide entre dos. Si el dato es menor al elemento central, usa el sub-array de la izquierda, si el dato es mayor al elemento central, usa el sub-array de la derecha y realiza el mismo proceso hasta encontrar el elemento buscado.

Técnicas de Sumarización

(con archivos secuenciales y directos)

Es el proceso de reducir un texto con un programa secuencial con el fin de crear de los puntos más importantes del documento original. El gran volumen de información y la sobrecarga que existe de este recurso en el mundo actual, han incrementado el interés en la sumarización automática y sus beneficios. Variables tales como la longitud, el estilo de escritura y la sintaxis deben ser tenidas en cuenta por aquellas tecnologías capaces de obtener resúmenes coherentes.

La sumarización automática: 

• Extracción 
• Abstracción. 

Los métodos de extracción: trabajan seleccionando un subconjunto de palabras, frases u oraciones, presentes en el texto original, para colocarlas en el resumen o sumario.

Los métodos de abstracción: trabajan en la representación semántica interna, y luego usan técnicas de generación de lenguaje natural para crear resúmenes cercanos a los que un humano generaría.