Hash Tables for a Digital Lexicon

Fábio Carlos Moreno, Cinthyan Sachs C. de Barbosa, Edio Roberto Manfio

Abstract


This paper deals with the construction of digital lexicons within the scope of Natural Language Processing. Data Structures called Hash Tables have demonstrated to generate good results for Natural Language Interface for Databases and have data dispersion, response speed and programming simplicity as main features. The storage of the desired information is done by associating a key through the hashing functions that is responsible for distributing the information in this table. The objective of this paper is to present the tool called Visual TaHs that uses a sparse table to a real lexicon (Lexicon of Herbs), improving performance results of several implemented hash functions. Such structure has achieved satisfactory results in terms of speed and storage when compared to conventional databases and can work in various media, such as desktop, Web and mobile.


Keywords


Hash; Lexicon; Natural Language Processing

Full Text:

PDF

References


BARROS, L. A.; ISQUERDO, A. N. O léxico em foco. São Paulo: Cultura Acadêmica, 2010.

VASQUES, P.; AGUILERA, V. Uma análise semântica do léxico em documentos históricos do Paraná. In: X Seminário de Pesquisa em Ciências Humanas. Londrina: Universidade Estadual de Londrina, 2017. p. 477–491.

GONZALEZ, M.; LIMA, V. L. S. Recuperação de informação e processamento da linguagem natural. In: XXIII Congresso da Sociedade Brasileira de Computaçao. São Paulo: SBC, 2003. p. 347–395.

PAIM, A. M. Inferência de personalidade a partir de textos em português brasileiro utilizando léxicos. Dissertação (Mestrado em Ciência da Computação) — Programa de Pós-Graduação em Informática Pontifícia Universidade Católica do Paraná, Curitiba, 2016.

SOUZA, E. N. P. Classificação de relações semânticas abertas baseada em similaridade de estruturas gramaticais na Língua Portuguesa. Dissertação (Mestrado Multiinstitucional) — Pós-Graduação em Ciência da Computação. Universidade Federal da Bahia, Salvador, 2014.

GREGHI, J. G. Projeto e desenvolvimento de uma base de dados lexicais do português. Dissertação (Mestrado) — Instituto de Ciências Matemática e de Computação. Universidade de São Paulo, São Carlos, 2002.

LISBÔA, A. R.; BARBOSA, C. R. S. C. Lexicon of orchids. Procedia-Social and Behavioral Sciences, Elsevier, Amsterdã, v. 95, p. 81–88, 2013.

VILLAVICENCIO, A.; CASELI, H. M.; MACHADO, A. Identification of multiword expressions in technical domains: Investigating statistical and alignment-based approaches. In: VII Brazilian Symposium in Information and Human Language Technology. São Paulo: USP, 2009. p. 27–35.

RIZVI, S. J.; HUSSAIN, M.; QAISER, N. Comparison of hash table verses lexical transducer based implementations of Urdu lexicon. In: IEEE. Student Conference on Engineering, Sciences and Technology. Piscataway, 2004. p. 29–29. Disponível em: .

MANFIO, E. R.; MORENO, F. C.; BARBOSA, C. R. S. C. Professor Tical e Alib: Interação humano computador em diferente campo. In: XIX Conferência Internacional sobre Informática na Educação. Fortaleza: Nuevas Ideas en Informática Educativa, 2014. p. 782–787.

MORENO, F. et al. Tical: Chatbot sobre o Atlas Linguístico do Brasil no WhatsApp. In: XXX Brazilian Symposium on Computers in Education. Maceió: SBC, 2015. p. 279–288.

CARDOSO, S. A. Atlas linguístico do Brasil. Londrina: SciELO-EDUEL, 2014. v. 1.

CARDOSO, S. A. M. et al. Atlas linguístico do Brasil: Cartas linguísticas 1. Londrina: SciELO-EDUEL, 2014. v. 2.

ALMEIDA, J. E. B. Para a história do português paranaense. Revista da ABRALIN, São Cristóvão, v. 12, n. 2, 2013.

MANFIO, E. R.; MORENO, F. C.; BARBOSA, C. R. S. C. Tical: Um chatbot que versa sobre assuntos linguísticos. In: XIV Encontro Linguística de Corpus. São Leopoldo: UFRGS, 2017. p. 51–51.

CORMEN, T. H. et al. Algoritmos: Teoria e prática. Rio de Janeiro: Campus, 2002. v. 2.

MACHADO, A. et al. Personalitatem lexicon: Um léxico em português brasileiro para mineração de traços de personalidade em textos. In: XXX Brazilian Symposium on Computers in Education. Maceió: SBC, 2015. p. 1122–1126.

ZOCK, M.; SCHWAB, D.; RAKOTONANAHARY, N. Lexical access, a search-problem. In: II Workshop on Cognitive Aspects of the Lexicon. Beijing, China: Colling Organizing Committee, 2010. p. 75–84.

CERCONE, N.; KRAUSE, M.; BOATES, J. Minimal and almost minimal perfect hash function search with application to natural language lexicon design. XXX Computers & Mathematics with Applications, Elsevier, Amsterdã, v. 9, n. 1, p. 215–231, 1983.

CICHELLI, R. J. Minimal perfect hash functions made simple. Communications of the ACM, ACM, New York, USA, v. 23, n. 1, p. 17–19, 1980.

SPECIA, L.; RINO, L. H. M. O desenvolvimento de um léxico para a geração de estruturas conceituais unl. In: Série de Relatórios Técnicos do NILC. São Carlos: NILC-ICMC-USP, 2002. p. 25.

BOTELHO, F. C. Estudo comparativo do uso de hashing perfeito mínimo. Dissertação (Ciência da Computação) — Programa de Pós Graduação em Ciência da Computação. Universidade Federal de Minas Gerais, Belo Horizonte, 2004.

ZIVIANI, N. Projetos de algoritmos com implementações em Pascal e C. São Paulo: Cengage Learning, 2011.

KNUTH, D. E. The art of computer programming 3: Sorting and searching. Massachusetts: Addison-Wesley, Reading, 1973.

CARRERAS-RIUDAVETS, F. J. et al. A morphological analyzer using hash tables in main memory (MAHT) and a lexical knowledge base. In: GELBUKH, A. (Ed.). Computational Linguistics and Intelligent Text Processing. Berlin, Heidelberg: Springer, 2012. p. 80–91.

EL-ABBADI, N.; KHDHAIR, A. N.; AL-NASRAWI, A. Build electronic arabic lexicon. The International Arab Journal of Information Technology, Zarqa, v. 8, p. 137–140, 2011.

JENKINS, R. J. New hash function for hash table lookup. 2013. Acesso em: 30 de jun. de 2020. Disponível em: .

MANFIO, E. R.; MORENO, F. C.; BARBOSA, C. R. S. C. Professor Tical: Robô de conversação sobre dialetologia e geossociolinguística. In: III Congresso Internacional de Dialetologia e Sociolinguística–Variação, Atitudes Linguísticas e Ensino. Londrina: UEL, 2014. p. 48–48.

GIL, A. C. Como elaborar projetos de pesquisa. São Paulo: Atlas, 2010. v. 5.

AHO, A. V.; SETHI, R.; ULLMAN, J. D. Compiladores: Princípios técnicas e ferramentas. Rio de Janeiro: LTC, 1995.

KOTHE, H. W. Léxico das Ervas. 1. ed. Lisboa: Dinalivro, 2009.

JENKINS, B. ALGORITHM ALLEY: What makes one hash function better than another? Bob knows the answer, and he has used his knowledge to design a new hash function that may be better than what you’re using now. Dr Dobb’s Journal-Software Tools for the Professional Programmer, Redwood City, CA, v. 22, n. 9, p. 107–110, 1997.

JENKINS, R. J. Hash functions for hash table lookup: Burtleburtle. 1997. Acesso em: 30 de jun. de 2020. Disponível em: .

JENKINS, R. J. Lookup3: Burtleburtle. 2006. Acesso em: 30 de jun. de 2020. Disponível em: .

JENKINS, R. J. Hash CRC: Burtleburtle. 2006. Acesso em: 30 de jun. de 2020. Disponível em: .

JENKINS, R. J. Generic CRC: Burtleburtle. 2006. Acesso em: 30 de jun. de 2020. Disponível em: .

ZOBRIST, A. A new hashing method with application for game playing. International Computer-Chess Association Journal, Amsterdã, v. 13, n. 2, p. 69–73, 1990.

FLECK, M. Hash functions. 2000. Acesso em: 30 de jun. de 2020. Disponível em: .

SILBERSCHATZ, A.; KORTH, H.; SUDARSHAN, S. Database Systems Concepts. Nova Iorque: McGraw-Hill, Inc., 2005.

SAWAYA, M. R. Dicionário de informática & Internet. São Paulo: NBL, 2002.

SZWARCFITER, J. L.; MARKENZON, L. Estruturas de Dados e seus Algoritmos. Rio de Janeiro: LTC, 2010.

MADEIRA, D. Uma estrutura baseada em hash table para buscas otimizadas em octree em GPU. Dissertação (Computação) — Universidade Federal Fluminense, Rio de Janeiro, 2010.

BARBOSA, W. A.; PARREIRA JÚNIOR, P. A. Um mapeamento sistemático sobre ferramentas de apoio ao ensino de algoritmo e estruturas de dados. In: II Congresso Brasileiro de Informática na Educação. Campinas: Unicamp, 2013. p. 406–415.




DOI: https://doi.org/10.22456/2175-2745.107128

Copyright (c) 2021 Fábio Carlos Moreno, Cinthyan Sachs Barbosa, Edio Roberto Manfio

Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Indexing databases:
        

Acknowledgments: