Premium
Implementing dynamic minimal‐prefix tries
Author(s) -
Dundas John A.
Publication year - 1991
Publication title -
software: practice and experience
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.437
H-Index - 70
eISSN - 1097-024X
pISSN - 0038-0644
DOI - 10.1002/spe.4380211004
Subject(s) - symbol (formal) , trie , prefix , computer science , algorithm , dynamic programming , theoretical computer science , arithmetic , data structure , mathematics , programming language , linguistics , philosophy
Abstract A modified trie‐searching algorithm and corresponding data structure are introduced which permit rapid search of a dictionary for a symbol or a valid abbreviation. The dictionary‐insertion algorithm automatically determines disambiguation points, where possible, for each symbol. The search operation will classify a symbol as one of the following: unknown (i.e. not a valid symbol), ambiguous (i.e. is a prefix of more than one valid symbol) or known. The search operation is performed in linear time proportional to the length of the input symbol, rather than the complexity of the trie. An example implementation is given in the C programming language.