Cap 2: Aplicacion Practica

Tutores: Luis Antonio Chamba ErasEdison Leonardo Coronel Romero

Carrera de Ingenierıa en SistemasUniversidad Nacional de Loja

Octubre 2012

1 / 18

Busqueda de Texto - Antecedentes

• Un problema habitual en la Web y otros repositorios de textoes el siguiente:

• ”Dado un conjunto de palabras, determinar todos los documen-tos que contengan una de dicha palabras (o todas)”.

• Un motor de busqueda, utiliza una tecnologıa concreta conocidacomo ”ındices invertidos”, en la que para cada palabra queaparece en la Web existen 100000000 de palabras diferentes, sealmacena una lista de todos los lugares donde aparecen dichapalabra, servidores mantienen disponibles la informacion.

• Las tecnicas de ındices invertidos no emplean automatas finitos,los agentes de busqueda invierten mucho tiempo en el proceso.

• Existen tecnicas de busqueda que utilizan automatas, para ellose necesita cumplir las siguientes caracterısticas:

2 / 18

Busqueda de Texto - Antecedentes

• Un problema habitual en la Web y otros repositorios de textoes el siguiente:

• ”Dado un conjunto de palabras, determinar todos los documen-tos que contengan una de dicha palabras (o todas)”.

• Un motor de busqueda, utiliza una tecnologıa concreta conocidacomo ”ındices invertidos”, en la que para cada palabra queaparece en la Web existen 100000000 de palabras diferentes, sealmacena una lista de todos los lugares donde aparecen dichapalabra, servidores mantienen disponibles la informacion.

• Las tecnicas de ındices invertidos no emplean automatas finitos,los agentes de busqueda invierten mucho tiempo en el proceso.

• Existen tecnicas de busqueda que utilizan automatas, para ellose necesita cumplir las siguientes caracterısticas:

3 / 18

Busqueda de Texto - Antecedentes

• Un problema habitual en la Web y otros repositorios de textoes el siguiente:

• ”Dado un conjunto de palabras, determinar todos los documen-tos que contengan una de dicha palabras (o todas)”.

• Un motor de busqueda, utiliza una tecnologıa concreta conocidacomo ”ındices invertidos”, en la que para cada palabra queaparece en la Web existen 100000000 de palabras diferentes, sealmacena una lista de todos los lugares donde aparecen dichapalabra, servidores mantienen disponibles la informacion.

• Las tecnicas de ındices invertidos no emplean automatas finitos,los agentes de busqueda invierten mucho tiempo en el proceso.

• Existen tecnicas de busqueda que utilizan automatas, para ellose necesita cumplir las siguientes caracterısticas:

4 / 18

Busqueda de Texto - Antecedentes

• Un problema habitual en la Web y otros repositorios de textoes el siguiente:

• ”Dado un conjunto de palabras, determinar todos los documen-tos que contengan una de dicha palabras (o todas)”.

• Un motor de busqueda, utiliza una tecnologıa concreta conocidacomo ”ındices invertidos”, en la que para cada palabra queaparece en la Web existen 100000000 de palabras diferentes, sealmacena una lista de todos los lugares donde aparecen dichapalabra, servidores mantienen disponibles la informacion.

• Las tecnicas de ındices invertidos no emplean automatas finitos,los agentes de busqueda invierten mucho tiempo en el proceso.

• Existen tecnicas de busqueda que utilizan automatas, para ellose necesita cumplir las siguientes caracterısticas:

5 / 18

Busqueda de Texto - Antecedentes

• Un problema habitual en la Web y otros repositorios de textoes el siguiente:

• ”Dado un conjunto de palabras, determinar todos los documen-tos que contengan una de dicha palabras (o todas)”.

• Un motor de busqueda, utiliza una tecnologıa concreta conocidacomo ”ındices invertidos”, en la que para cada palabra queaparece en la Web existen 100000000 de palabras diferentes, sealmacena una lista de todos los lugares donde aparecen dichapalabra, servidores mantienen disponibles la informacion.

• Las tecnicas de ındices invertidos no emplean automatas finitos,los agentes de busqueda invierten mucho tiempo en el proceso.

• Existen tecnicas de busqueda que utilizan automatas, para ellose necesita cumplir las siguientes caracterısticas:

6 / 18

Busqueda de Texto - Antecedentes

• El repositorio cambia rapidamente:noticias al dıa, rastreadoresWeb.

• Documentos no clasificados, paginas sobre la marcha en res-puesta a consultas.

7 / 18

Busqueda de Texto - Antecedentes

• El repositorio cambia rapidamente:noticias al dıa, rastreadoresWeb.

• Documentos no clasificados, paginas sobre la marcha en res-puesta a consultas.

8 / 18

Busqueda de Texto - Antecedentes

• El repositorio cambia rapidamente:noticias al dıa, rastreadoresWeb.

• Documentos no clasificados, paginas sobre la marcha en res-puesta a consultas.

9 / 18

Busqueda de Texto - Automatas Finitos No Deterministas

• Conjunto de palabras denominadas ”palabras clave ”, deseamosencontrar las apariciones de cualquiera de estas palabras, lo masutil es disenar un AFND que indique mediante un estado deaceptacion que se ha encontrado una de las ”palabras clave”,el texto de un documento se introduce caracter por caracter enel AFND que permitira reconocer las apariciones de las palabrasclaves en el texto.

• Estado inicial con una transicion a sı mismo para cada uno de lossımbolos de entrada, por ejemplo el alfabeto ASCII, este estadoinicial representa una conjetura de que no se ha detectado unapalabra clave, incluso aunque hayamos encontrado algunas delas letras de una de esas palabras.

• Para cada palabra a1a2...ak hay k estados, q1,q2,...,qk.

10 / 18

Busqueda de Texto - Automatas Finitos No Deterministas

• Conjunto de palabras denominadas ”palabras clave ”, deseamosencontrar las apariciones de cualquiera de estas palabras, lo masutil es disenar un AFND que indique mediante un estado deaceptacion que se ha encontrado una de las ”palabras clave”,el texto de un documento se introduce caracter por caracter enel AFND que permitira reconocer las apariciones de las palabrasclaves en el texto.

• Estado inicial con una transicion a sı mismo para cada uno de lossımbolos de entrada, por ejemplo el alfabeto ASCII, este estadoinicial representa una conjetura de que no se ha detectado unapalabra clave, incluso aunque hayamos encontrado algunas delas letras de una de esas palabras.

• Para cada palabra a1a2...ak hay k estados, q1,q2,...,qk.

11 / 18

Busqueda de Texto - Automatas Finitos No Deterministas

• Conjunto de palabras denominadas ”palabras clave ”, deseamosencontrar las apariciones de cualquiera de estas palabras, lo masutil es disenar un AFND que indique mediante un estado deaceptacion que se ha encontrado una de las ”palabras clave”,el texto de un documento se introduce caracter por caracter enel AFND que permitira reconocer las apariciones de las palabrasclaves en el texto.

• Estado inicial con una transicion a sı mismo para cada uno de lossımbolos de entrada, por ejemplo el alfabeto ASCII, este estadoinicial representa una conjetura de que no se ha detectado unapalabra clave, incluso aunque hayamos encontrado algunas delas letras de una de esas palabras.

• Para cada palabra a1a2...ak hay k estados, q1,q2,...,qk.

12 / 18

Busqueda de Texto - Automatas Finitos No Deterministas

• Existe una transicion desde el estado inicial a q1 para a1, unatransicion desde q1 a q2 para a2..., el estado qk es un estadode aceptacion que indica que se ha encontrado la palabra clavea1a2...ak.

• Google.

• Amazon.

• AFND.

• AFD.

13 / 18

Busqueda de Texto - Automatas Finitos No Deterministas

• Existe una transicion desde el estado inicial a q1 para a1, unatransicion desde q1 a q2 para a2..., el estado qk es un estadode aceptacion que indica que se ha encontrado la palabra clavea1a2...ak.

• Google.

• Amazon.

• AFND.

• AFD.

14 / 18

Busqueda de Texto - Automatas Finitos No Deterministas

• Existe una transicion desde el estado inicial a q1 para a1, unatransicion desde q1 a q2 para a2..., el estado qk es un estadode aceptacion que indica que se ha encontrado la palabra clavea1a2...ak.

• Google.

• Amazon.

• AFND.

• AFD.

15 / 18

Busqueda de Texto - Automatas Finitos No Deterministas

• Existe una transicion desde el estado inicial a q1 para a1, unatransicion desde q1 a q2 para a2..., el estado qk es un estadode aceptacion que indica que se ha encontrado la palabra clavea1a2...ak.

• Google.

• Amazon.

• AFND.

• AFD.

16 / 18

Busqueda de Texto - Automatas Finitos No Deterministas

• Existe una transicion desde el estado inicial a q1 para a1, unatransicion desde q1 a q2 para a2..., el estado qk es un estadode aceptacion que indica que se ha encontrado la palabra clavea1a2...ak.

• Google.

• Amazon.

• AFND.

• AFD.

17 / 18

Bibliografıa

[1] John E. Hopcroft, Rajeev Motwani y Jeffrey D. UllmanTeorıa de Automatas, lenguajes y computacionPearson, 2008.

18 / 18