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

Peter Schneider-Kamp

2022

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.

Paper Citation

in Harvard Style

Schneider-Kamp P. (2022). Approximate Dictionary Searching at a Scale using Ternary Search Trees and Implicit Levenshtein Automata. In Proceedings of the 17th International Conference on Software Technologies - Volume 1: ICSOFT, ISBN 978-989-758-588-3, pages 657-662. DOI: 10.5220/0011312300003266

in Bibtex Style

@conference{icsoft22,
author={Peter Schneider-Kamp},
title={Approximate Dictionary Searching at a Scale using Ternary Search Trees and Implicit Levenshtein Automata},
booktitle={Proceedings of the 17th International Conference on Software Technologies - Volume 1: ICSOFT,},
year={2022},
pages={657-662},
publisher={SciTePress},
organization={INSTICC},
doi={10.5220/0011312300003266},
isbn={978-989-758-588-3},
}

in EndNote Style

TY - CONF

JO - Proceedings of the 17th International Conference on Software Technologies - Volume 1: ICSOFT,
TI - Approximate Dictionary Searching at a Scale using Ternary Search Trees and Implicit Levenshtein Automata
SN - 978-989-758-588-3
AU - Schneider-Kamp P.
PY - 2022
SP - 657
EP - 662
DO - 10.5220/0011312300003266