IMPLEMENTING DYNAMIC MINIMAL-PREFIX TRIES

被引:21
作者
DUNDAS, JA
机构
[1] Jet Propulsion Laboratory, California Institute of Technology, Pasadena, California, 91109
关键词
TREES; SEARCHING; PATTERN MATCHING; DICTIONARY;
D O I
10.1002/spe.4380211004
中图分类号
TP31 [计算机软件];
学科分类号
081202 ; 0835 ;
摘要
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.
引用
收藏
页码:1027 / 1040
页数:14
相关论文
共 2 条
[1]  
KNUTH DE, 1973, ART COMPUTER PROGRAM, V3, P481
[2]  
LEVY E, 1988, SIGPLAN NOTICES, V23, P93, DOI 10.1145/47907.47915