Efficient high speed trie search process

Details Efficient high speed trie search process Efficient high speed trie search process

1993-04-14

1997-06-17

Black, Thomas G.

Pulse or digital communications

Repeaters

Testing

395800, 375240, G06F 1730

Patent

active

056405510

ABSTRACT:
An efficient speed trie search process which generates a sequence of pointers for each family of children in a trie, the sequences of pointers being organized in a predefined order according to a detected data type information of the input data stream. In response to the detected data type information, the trie search process selects a pointer sequence organization from one or more predefined organization sequences, such as an organization sequence from the most recently matched data in a family of nodes to the least recently matched data in that family of nodes, an organization in accordance to a predetermined frequency distribution of a predefined set of data symbol, or an adaptive frequency distribution sequence of a set of symbols detected in an input data stream. Such arrangement of pointers, in response to the detected input data type, reduces significantly the process time to search through a trie for matching data strings. In an another alternative embodiment, a lookup table is provided for the first level search, comprising searching the family consisting the children of the root of the trie.

REFERENCES:
patent: 3394352 (1968-07-01), Wernikoff et al.
patent: 3729712 (1973-04-01), Glanssman
patent: 4558302 (1985-12-01), Welch
patent: 4588302 (1986-05-01), Welch
patent: 4829423 (1989-05-01), Tenna et al.
patent: 5010345 (1991-04-01), Nagy
patent: 5045852 (1991-09-01), Mitchell, et al.
patent: 5058144 (1991-10-01), Fiala et al.
patent: 5179711 (1993-01-01), Vreeland
patent: 5184126 (1993-02-01), Nagy
patent: 5220417 (1993-06-01), Sugiura
patent: 5247638 (1993-09-01), O'Brien et al.
patent: 5355505 (1994-10-01), Suzuki
Ph. Jacquet & W. Szpankowski, "Analysis of Digital Tries with Markovian Dependency", IEEE Transactions on Information Theory Sep., 1991. pp. 1470-1475, vol. 37, No. 5.
Donald R. Monison, "Patricia-Practical Algorithm to retrieve Information Coded in Alphanumeric", Journal of Association of Computing Machinery Oct. 1968, vol. 15, No. 4, pp. 514-534.
IEEE, Computer, Jun. 1984, pp. 8-19, Terry A. Welch, Sperry Research Center, "A Technique for High-Performance Data Compression.".
IEEE, Transactions On Information Theory, vol. II 23, No. 3, May 1977, pp. 337-343 J. Ziv, A. Lempel, "A Universal Algorithm for Sequential Data Compression".
IEEE, Transactions On Information Theory, vol. II 24, No. 5, Sep. 1978, pp. 530-536, J. Ziv. Lempel, "Compression of Individual Sequences via Variable-Rate Coding".
IEEE Transactions on Information Theory vol. II, 21, No. 2, Mar. 1975, pp. 194-203. Peter Elias, "Universal Codeword Sets and Representations of the Integers".
Communications of the ACM, Apr. 1989 vol. 32 No. 4, pp. 490-504, Edward R. Riala and Daniel H. Greene, "Data Compression with Finite Windows".
Timothy C. Bell, John G. Cleary, Ian H. Witten, Text Compression, Prentice Hall, Englewood Cliffs, New Jersey, 1990, pp. 206-243.
Jacob Ziv, et al. "A Universal Algorithm for Sequential Data Compression" IEEE Information Theory, vol. IT-23, Bi. 3, May 1977, pp. 337-343.
Edward R, Fiala, et al. "Data Compression with Finite Windows", Communications of the ACM, vol. 32, No. 4, Apr. 1989, pp. 490-505.
Timothy C. Bell, et al. "Text Compression" Prentice Hall Advanced Reference Series, pp. 206-243, 1990.
Peter Elias, "Universal Codeword Sets and Representations of the Integers" Information Theory, vol. IT21, No. 2, Mar. 1975, pp. 194-202.
Jacob Ziv, et al. "Compression of Individual Sequences via Variable-Rate Coding" Information Theory, vol. IT24, No. 5, Sep. 1978, pp. 530-536.
Terry A. Welch, "A Technique for High Performance Data Compression" IEEE Information Theory, Handout 14, pp. 8-18, 1984.
"ARC File Archive Utility; Version 5.1" 1986, 1986 System Enhancement Associates.

Affiliated with

Also associated with

Rating

Efficient high speed trie search process does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Efficient high speed trie search process, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Efficient high speed trie search process will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2165365