Arañas distribuidas --Asignación Efectiva de Trabajo Evitando Duplicidad de Espacio y Tiempo

Ésta es la tesis de maestría de Luis Antonio Olguín Aguilar. El documento comleto se encuentra aquí.
RESUMEN. La computación desde sus inicios, como en la actualidad, es utilizada como una herramienta que le ayuda al hombre a resolver problemas de su vida diaria. Tanto la computación clásica como la computación cuántica, bajo distintos paradigmas, están orientados a resolver problemas que a una o varias personas le tomaría mucho tiempo resolver. Uno de los problemas a los que se enfrenta el hombre en la realización de sus actividades está en que una, dos o más personas pueden llegar a realizar la misma actividad y por ende generar los mismos resultados. Esto se conoce como duplicidad de trabajo. La duplicidad de trabajo no sólo es costosa por el hecho de hacer la misma tarea múltiples veces sin la necesidad de requerirlo, sino que también desde el punto de vista de un mundo capitalista puede llegar a costar mucho dinero: pagar sueldos a personas que realicen la misma actividad, gastos de mantenimiento, gastos de operación, entre otros, dependiendo de la actividad que se realice.

Con la llegada de la Web se abrió una etapa en la que la información se puso disponible para cualquier persona que desee conectarse a la Internet. Con el paso del tiempo esta información ha ido creciendo y se hizo necesario crear programas que examinaran constantemente la información que los usuarios ponían disponible día a día. Estos programas son conocidos como “Web crawlers” o “arañas”. Un Web crawler es un programa que inspecciona de manera metódica y automatizada las páginas de la Internet. Para un Web crawler es sumamente importante no duplicar trabajo, pues una dirección URL duplicada puede originarle perder varias horas o incluso días de trabajo ya que otra de sus tareas es extraer direcciones URL incluidas dentro de ella y procesarlas de igual manera.

El presente trabajo muestra el análisis, diseño, implementación, pruebas y resultados de una aplicación que resuelve el problema de duplicidad de trabajo evitando la duplicidad en espacio de almacenamiento, así como de tiempo de procesamiento en la extracción de documentos de la Internet permitiendo que por cada página Web se asocie a ella 4 de los principales temas de los que trata el documento. De manera particular el trabajo que cada araña hace, sin duplicación, es el siguiente: “buscar en cada página indicada por una lista de URLs, documentos que contengan suficiente texto, e indizar tanto la página como el documento (si existe). Si en cierta página hay apuntadores, éstos señalan nuevas páginas, las que a su vez reciben el mismo tratamiento, hasta un cierto nivel de profundidad, 4 en nuestro caso. Repetir este procedimiento periódicamente, variando dinámicamente el período de visita, según la actividad que muestre la página. Evitar volver a indizar un documento que no ha cambiado.”

En el capítulo 1 se presenta una introducción a nuestro tema de tesis. Se incluye el planteamiento del problema que vamos a resolver, mostramos los objetivos planteados tanto de manera general como de manera particular. Mostramos una breve justificación respecto a construir un sistema que resuelve el problema planteado y finalmente mostramos los alcances y límites que pretendemos lograr. En el capítulo 2 mostramos lo que es un Web Crawler, conocemos el estado del arte y finalmente mostramos las características generales que tiene. En el capítulo 3 describimos lo que es un sistema distribuido. Presentamos sus ventajas y desventajas. También explicamos la arquitectura RMI (Remote Method Invocation, Invocación de Métodos Remotos) de Java que es utilizada para implementar sistemas distribuidos. Se muestran las capas con que cuenta esta arquitectura, las clases que deben ser implementadas y algunos ejemplos que son de utilidad para su entendimiento. En el capítulo 4 se describe el problema planteado, mostramos la arquitectura propuesta que lo resuelve, así como un ejemplo práctico del funcionamiento que debe implementarse.

En el capítulo 5 se muestra el diseño de la aplicación. En él se describen los distintos procesos involucrados en la realización de las tareas tanto del servidor como de la araña. El capítulo 6 muestra la implementación de la aplicación. Esta implementación muestra el esquema de comunicación del servidor y de la araña. Finalmente, se explica la manera en que obtenemos los temas que trata cada documento mediante Clasitex. El capítulo 7 muestra la fase de pruebas. En este capítulo se muestran varias pruebas realizadas a la aplicación así como sus resultados. El capítulo 8 es dedicado a presentar las conclusiones a las que llegamos después de haber obtenido los resultados, producto de las pruebas realizadas en el capítulo 7.

ABSTRACT. (The full document is here) The computation since the begining to today is used as a tool that helps people to resolve a lot of problems of their daily life. Classic computing as well as Quantum computing, under differt paradigms, are oriented to solve problems that for a single person could take a lof of years to answer. One of the main problems that people has to deal is about to do the same work many times at different times for more than one person. This is known as duplicity.

The duplicity of the work costs a lot of money in a capitalistic world, for example paying a salary to people who has to do the work, maintain costs, operation costs and many others.

When the World Wide Web (www) came to our lifes it opened a new style of life because the information was online just with a simple click. Since 80’s to our days this information has grown exponentially and it had new necesities like to organize those millions of Web Pages. That was the main reason to build Web Crawlers or Spiders. A Web Crawler is a program which explores the Web Pages on the Internet. One of the main characteristics of a Web Crawler is not to duplicate the work because when it crawls the Web, with a simple URL, a Web Crawler could spend a lot of hours and maybe days doing its work.

This thesis shows the analysis, design, implementation, tests and results of an application which solve the problem of the duplicity of work avoiding the duplicity of the space used to save the Web Pages and the time crawling the Internet making possible to associate to every Web Page four of the main topics of that document The work of a spider is the next: “looking for documents with enough text, in every Web page that contains the list of URLs, to index that page and the document. When the page has links to anothers pages these new ones receive the same tratement with a level of deep 4. This procedure must be repited everyday, changing the time of visit depending the time of change of that Web page. It`s very important not to process tha same document twice or more”.

Chapter 1 shows an introduction to the thesis. It includes the problem to resolve, the objetives and the main reasons to build this system and finally the limits and goals to reach. Chapter 2 shows what a web crawler is and its main characteristics. Chapter 3 shows what a distributed crawler is. We explain the RMI architecture, that allows to build a Distributed System and finally shows an example of it. Chapter 4 shows the problem to solve and the way to solution it. Chapter 5 shows the design of the application. Chapter 6 shows the implementation of the application. It shows the architecture of the Server, the clients and their comunication. It shows the way to obtain the main topics of a document through Clasitex.Chapter 7 shows several tests of the system and their results. Chapter 8 shows conclusions.

Requisitos que deben cubrir las tesis dirigidas por A. Guzmán

Las tesis que yo dirijo deben llenar los siguientes requisitos:

1. (Para tesis sobre Computación) Abajo del Resumen, en esa misma hoja, poner de tres a seis palabras clave, de las cuales dos o tres deben ser tomadas de la Clasificación del ACM (abajo), cítelas así:
Palabras clave: I.2 Inteligencia Artificial; I.2.4 Formalismos y métodos para representar el conocimiento; Calculando con palabras; Solución de problemas aritméticos
Primero van los descriptores del ACM, con su clave al principio: H.2 Database management. Luego van las palabras clave que el tesista inventa y que no están en la clasificación del ACM. El descriptor que va primero es el descriptor primario: es el tema principal de su tesis.
Bajo "Resumen" poner descriptores en español, bajo "Abstract" poner descriptores en inglés.
2. Las referencias deben ir en un formato estándar. Use el Chicago Style Manual (abajo).
3. (Requisito del CIC) Debe entregar una copia de su tesis en archivo digital (CD, por ejemplo) a la biblioteca del CIC, conteniendo su tesis completa en formato de documento (Word, PDF...). Opcional: ponga en el CD los programas que usted usó, fuentes y ejecutables, ejemplos, instructivo de cómo cargar su programa y cómo usarlo.

====ACM computer classification system=======
A. La más reciente es la de 1988, pero está actualizada al día (cada año se actualiza): http://www.acm.org/about/class/ Pulse aquí
B. Una versión más antigua pero traducida al español está aquí (URL: http://www.divshare.com/download/7752920-cbe). Trae descriptores en inglés y español, pero use (A) para las claves correctas de los decriptores. O ignórela y traduzca del inglés al español usted mismo.

=====Chicago Style manual============
chicago Manual of style http://www.libs.uga.edu/ref/chicago.html Pulse aquí.
Chicago manual of style on line http://www.chicagomanualofstyle.org/tools_citationguide.html Pulse aquí

Computing with words -Computando con palabras

Este trabajo es la tesis de maestría de Patricia Bautista en el Centro de Investigación en Computación del IPN. Resuelve problemas aritméticos expresados en lenguaje natural (español). Para ver el documento completo (en español) pulsa aquí.
This is the M. Sc. thesis of Patricia Bautista at the Centro de Investigación en Computación, Instituto Politécnico Nacional. It solves arithmetic problems posed in natural language. The full document (in Spanish) can be seen here.
ABSTRACT: Computing with words (CW) is an auxiliary methodology for the natural language processing. It uses vague quantities, expressed through words, to solve arithmetical operations. The results of such operations are notions or approximations; though, this methodology enables result generation in situations where precise results are not possible at all. Some examples of vaguely expressed quantities (in Spanish) are: “Hace mucho frío”, “Roberto tiene algunos libros” and “México tiene mucho petróleo”.
Computing with words is based on fuzzy logic. It was introduced by Lotfi Asker Zadeh in 1965. As part of the Computing with words’ methodology, words that represent quantities are used. These are identified and related to fuzzy sets. Under the context of Computing with words, these sets are known as linguistic variables.
Natural language is the computer science’s area in charge of studying human language. It studies the processing of words, phrases and other language figures. From this processing it is meant to obtain a meaningful representation for its use in computer programs.
The main contribution of the present work is the creation of a new methodology for Computing with words and the designe of the software that uses this methodology. It has as its goal to make calculations with phrases in Spanish (following some restrictions). The core part of the software is a parser. It uses a lemmatizer as a helper for the lexical analysis. The syntactic analysis is done through some proposed rules. The parser allows detection of operations among the text. These are calculated through tables based on a set of linguistic variables. This set is defined through a statistical analysis.
Some potential applications of the proposed software are: clinical diagnosis problems, educative programs, control systems and, in general, decision making problems. Such software is particularly useful in situations where no precise data exists or a flexible user input is desired.
KEYWORDS: I. Computing Methodologies, I.2 Artificial Intelligence, I.2.7 Natural Language Processing, Language parsing and understanding, Solving arithmetical operations using words: Computing with Words.
RESUMEN: La Computación con palabras o Computing with words (CW) es una metodología auxiliar al procesamiento del lenguaje natural. Ésta utiliza cantidades expresadas vagamente, por medio de palabras, para realizar operaciones aritméticas. El resultado de estas operaciones son nociones o aproximaciones; sin embargo, esta metodología permite obtener resultados en algunas situaciones donde los cálculos precisos son imposibles. Ejemplos de cuantificaciones vagas (o difusas) son las siguientes frases: “Hace mucho frio”, “Roberto tiene algunos libros” y “México tiene mucho petróleo”.
La Computación con palabras se basa en la lógica difusa. Ésta fue introducida por Lotfi Asker Zadeh en 1965. Como parte de la metodología de Computación con palabras se identifican palabras que representan cantidades y se les relaciona con conjuntos difusos. Bajo el contexto de Computación con palabras a estos conjuntos se les conoce como variables lingüísticas.
Lenguaje natural es el área de las ciencias de la computación que se encarga del estudio del lenguaje humano. Esta área se encarga del procesamiento de palabras, frases y otras figuras del lenguaje. De este procesamiento se pretende obtener alguna representación significativa para su uso en programas de cómputo.
La aportación principal del presente trabajo es la creación de una nueva metodología para la computación con palabras; así como el diseño de un software basado en dicha metodología. Éste tiene como finalidad realizar cálculos con oraciones escritas español (siguiendo algunas restricciones). La parte nuclear del software es un parser. Éste utiliza un lematizador como apoyo para el análisis léxico del texto. El análisis sintáctico se realiza por medio de una serie de reglas propuestas. El parser permite detectar operaciones dentro del texto. Éstas son calculadas por medio de tablas basadas en un conjunto de variables lingüísticas. Este conjunto se determina estadísticamente.
Algunas potenciales aplicaciones del software propuesto son: problemas de diagnostico clínico, programas educativos, sistemas de control y, en general, problemas de toma de decisión. El software resulta potencialmente útil en situaciones en las que no existen datos precisos disponibles o se desea ser flexible ante la entrada de datos del usuario.
PALABRAS CLAVE: I. Metodologías de cómputo, I.2 Inteligencia artificial, I.2.7 Procesamiento de lenguaje natural, Análisis y compresión del lenguaje, Resolviendo problemas aritméticos usando palabras: Computing with Words