Stored string data with next and alternative information a proce

Details Stored string data with next and alternative information a proce Stored string data with next and alternative information a proce

1995-05-25

1996-12-03

Bowler, Alyssa H.

Boots, shoes, and leggings

36494342, 364DIG2, 395793, 395795, G06F 900

Patent

active

055817807

ABSTRACT:
An FSM data structure is encoded by generating a transition unit of data corresponding to each transition which leads ultimately to a final state of the FSM. Information about the states is included in the transition units, so that the encoded data structure can be written without state units of data. The incoming transition units to a final state each contain an indication of finality. The incoming transition units to a state which has no outgoing transition units each contain a branch ending indication. The outgoing transition units of each state are ordered into a comparison sequence for comparison with a received element, and all but the last outgoing transition unit contain an alternative indication of a subsequent alternative outgoing transition. The indications are incorporated with the label of each transition unit into a single byte, and the remaining byte values are allocated among a number of pointer data units, some of which begin full length pointers and some of which begin pointer indexes to tables where pointers are entered. The pointers may be used where a state has a large number of incoming transitions or where the block of transition units depending from a state is broken down to speed access. The first outgoing transition unit of a state is positioned immediately after one of the incoming transitions so that it may be found without a pointer. Each alternative outgoing transition unit is stored immediately after the block beginning with the previous outgoing transition unit so that it may be found by proceeding through the transition units until the number of alternative bits and the number of branch ending bits balance.

REFERENCES:
patent: Re31287 (1983-06-01), Patic
patent: 4241402 (1980-12-01), Mayper et al.
patent: 4285049 (1981-08-01), Bird et al.
patent: 4293783 (1981-10-01), Patil
patent: 4366551 (1982-12-01), Holtz
patent: 4376982 (1983-03-01), Bantz et al.
patent: 4450520 (1984-05-01), Hollaar et al.
patent: 4644461 (1987-02-01), Jennings
patent: 4713754 (1987-12-01), Agarwal et al.
patent: 4723211 (1988-02-01), Barker et al.
patent: 4739477 (1988-04-01), Barker et al.
patent: 4758955 (1988-07-01), Chen
patent: 4771385 (1988-09-01), Egami et al.
patent: 4782464 (1988-11-01), Gray et al.
patent: 4783761 (1988-11-01), Gray et al.
patent: 4866605 (1989-09-01), Nakano et al.
patent: 4882703 (1989-11-01), Nicolai
patent: 4991135 (1991-02-01), Yoshimura et al.
patent: 5325091 (1994-06-01), Kaplan
Haskin, R. L., and Hollar, L. A., "Operational Characteristics of a Hardware-Based Pattern Matcher", ACM Transactions on Database Systems, vol. 8, No. 1, Mar. 1983, pp. 15-40.
Srihari, N. S.; Hull, J. J.; Choudhari, R., "Integrating Diverse Knowledge Sources in Text Recognition", ACM Transactions on Office Information Systems, vol. 1, No. 1, Jan. 1983, pp. 68-87.
Carlgren, R. G., "Language-Independent Dictionary Storage and Access Technique", IBM Technical Disclosure Bulletin, vol. 26, No. 11, Apr. 1984, pp. 6085-6086.
Turba, T. N., "Checking for Spelling and Typographical Errors in Computer-Based Text", Sigplan Notices, vol. 16, No. 6, Jun. 1981, pp. 51-60.
Liang, "Word Hy-phen-a-tion by Com-put-er", Stanford University, Department of Computer Science; 1983, pp. 8-28 and 39-44.
Hull et al., "An Integrated Algorithm for Text Recognition: Comparison with a Cascaded Algorithm", IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. PAMI-5, No. 4, Jul. 1983, pp. 384-395.
Knuth, "The Art of Computer Programming", vol. 3; Sorting and Searching, Addison-Wesley, 1973, pp. 481-505.
Peterson, "Computer Programs for Spelling Correction: An Experiment in Program Design", Lecture Notes in Computer Science 96, Springer-Verzag, New York, Oct. 1980, pp. 57-66.
Maly, "Compressed Tries", Communications of the ACM, vol. 19, No. 7, Jul. 1976, pp. 409-415.
Agerwala, "Putting Pelvi Nets to Work", IEEE Computer, Dec. 1979, pp. 85-94 .

Affiliated with

Also associated with

Rating

Stored string data with next and alternative information a proce does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Stored string data with next and alternative information a proce, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Stored string data with next and alternative information a proce will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-795422