Exact and Approximate Prefix Search under Access Locality Requirements for Morphological Analysis and Spelling Correction
Alexander F. Gelbukh · LA Referencia (Red Federada de Repositorios Institucionales de Publicaciones Científicas) · 2003
A DATA STRUCTURE USEFUL FOR PREFIX SEARCH IN A VERY LARGE DICTIONARY WITH AN ANLIMITED QUERY STRING IS DISCUSSED. THIS PROBLEM IS IMPORTANT FOR MORPHOLOGICAL ANALYSIS OF INFLECTIVE LANGUAGES, INCLUDING PARTICULARY DIFFICULT CASES SUCH AS GERMAN WORD CONCATENATION OR JAPANESE WRITING SYSTEM THAT DOES NOT USE SPACES; SIMILAR TASKS ARISE IN AND COMPUTING. THE DATA STRUCTURES IS OPTIMIZED FOR LOCALITY OF ACCESS; TO THE MAIN DATA STORAGE IS USEFULNESS, THE ALGORITHMS OF EXACT AND APROXIMATE SEARH ARE DESCRIBED, WITH APPLICATION TO MORPHOLOGICAL ANALYSIS AND SPELLING CORRECTION. THE ANGORITHMS FOR BUILDIN, EXPORTING, AND UPDAITING THE DATA STRUCTURE ARE EXPLAINED.