| Revista: | Computación y sistemas |
| Base de datos: | PERIÓDICA |
| Número de sistema: | 000204694 |
| ISSN: | 1405-5546 |
| Autores: | Gelbukh, Alexander1 |
| Instituciones: | 1Instituto Politécnico Nacional, Centro de Investigación en Computación, México, Distrito Federal. México |
| Año: | 2003 |
| Periodo: | Ene-Mar |
| Volumen: | 6 |
| Número: | 3 |
| Paginación: | 167-182 |
| País: | México |
| Idioma: | Inglés |
| Tipo de documento: | Artículo |
| Enfoque: | Analítico |
| Resumen en español | Se presenta una estructura de datos que es útil para la búsqueda de prefijos en un diccionario muy grande con una petición de entrada no limitada. Este problema es importante para el análisis morfológico de los lenguajes fiexivos, incluyendo los casos particularmente difíciles tales como encadenamiento de palabras en el alemán o el sistema de la escritura japonés que no utiliza espacios; las tareas similares se presentan en el procesamiento computational de ADN. La estructura de datos es optimizada para el acceso local: para encontrar todos los registros necesarios, se garantiza el acceso a sólo un bloque (página) del dispositivo principal de almacenamiento de datos, lo que significadamente mejora el rendimiento. Para ilustrar su utilidad, se describen los algoritmos de la búsqueda exacta y aproximada, aplicados al análisis morfológico y la corrección de ortografía. Se explican los algoritmos para la construcción, exportación y actualización de la estructura de datos |
| Resumen en inglés | A data structure useful for prefix search in a very large dictionary with an unlimited query string is discussed. This problem is important for morphological analysis of inflective languages, including particularly difficult cases such as German word concatenation or Japanese writing system that does not use spaces; similar tasks arise in DNA computing. The data structure is optimized for locality of access: to find all necessary records, access to only one block (page) of the main data storage is guaranteed, which significantly improves performance. To illustrate its usefulness, the algorithms of exact and approximate search are described, with application to morphological analysis and spelling correction. The algorithms for building, exporting, and updating the data structure are explained |
| Disciplinas: | Ciencias de la computación |
| Palabras clave: | Búsqueda de prefijos, Comparación de cadenas, Análisis morfológico, Corrección de ortografía, Lenguaje natural, ADN |
| Keyword: | Computer science, Prefix search, String matching, Morphological analysis, Spelling correction, Natural language, DNA |
| Texto completo: | Texto completo (Ver PDF) |
