Approximate Dictionary Searching at a Scale using Ternary Search Trees and Implicit Levenshtein Automata

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

60 Downloads (Pure)

Abstract

Approximate Dictionary Searching refers to the problem of finding entries in a dictionary that match a search word either exactly or with a certain allowed distance between entry and search word.
Extant computationally efficient data structures and algorithms addressing this problem typically do not scale well to large alphabets and/or dictionaries, often requiring prohibitive amounts of memory as the sizes of alphabets and dictionaries increase.
This paper presents a data structure and an algorithm for approximate dictionary searching that rely on ternary search trees and implicit Levenshtein automata and scale well with the sizes of both alphabets and dictionaries.
Original languageEnglish
Title of host publicationProceedings of the 17th International Conference on Software Technologies - ICSOFT
PublisherInstitute for Systems and Technologies of Information, Control and Communication
Publication dateJul 2022
Pages657-662
ISBN (Electronic)978-989-758-588-3
DOIs
Publication statusPublished - Jul 2022
Event17th International Conference on Software Technologies - Lisbon, Portugal
Duration: 11. Jul 202213. Jul 2022

Conference

Conference17th International Conference on Software Technologies
Country/TerritoryPortugal
CityLisbon
Period11/07/202213/07/2022

Fingerprint

Dive into the research topics of 'Approximate Dictionary Searching at a Scale using Ternary Search Trees and Implicit Levenshtein Automata'. Together they form a unique fingerprint.

Cite this