1991-10-16
1998-05-19
Kulik, Paul V.
395612, 395760, G06F 1730
Patent
active
057548471
ABSTRACT:
A compactly stored word list that includes a directed graph data structure is used for word to number (W/N) and number to word (N/W) mapping. Each word accepted by the data structure is mapped to a unique corresponding number within a dense set of numbers ranging from zero to one less than the total number of acceptable words. Some common suffixes are collapsed into shared branches, which is possible because the numbers are not stored within the word list. In addition, some branches of the data structure can be skipped during mapping because of information associated with branch points. That information permits the mapping scan to continue with a next branch or with an alternative branch. That information also indicates the number of suffix endings in the next branch; this number is used to keep a count of the word endings during word to number mapping; it is also used both to determine whether to continue with the next branch and also to reduce the number being mapped during number to word mapping. The branching information includes a full length pointer to the next branch or a shorter length pointer index to a table in which the pointer is stored. In either case, the number of suffix endings in the next branch is annexed to the pointer. The pointers and pointer indexes are assigned iteratively, the shortest pointer indexes first, then longer pointer indexes, and finally the full length pointers. In each case, a pointer or pointer index is assigned only if beneficial, and the assignment of pointers and pointer indexes is cleared and redone if a better assignment can be made.
REFERENCES:
patent: 4074235 (1978-02-01), Thomas
patent: 4092729 (1978-05-01), Rosenbaum et al.
patent: 4241402 (1980-12-01), Mayper, Jr. et al.
patent: 4366551 (1982-12-01), Holtz
patent: 4374625 (1983-02-01), Hanft et al.
patent: 4384329 (1983-05-01), Rosenbaum et al.
patent: 4450520 (1984-05-01), Hollaar et al.
patent: 4597055 (1986-06-01), Hashimoto et al.
patent: 4608665 (1986-08-01), Yoshida
patent: 4685060 (1987-08-01), Yamano et al.
patent: 4744050 (1988-05-01), Hirosawa et al.
patent: 4758955 (1988-07-01), Chen
patent: 4771385 (1988-09-01), Egami et al.
patent: 4777617 (1988-10-01), Frisch et al.
patent: 4782464 (1988-11-01), Gray et al.
patent: 4783761 (1988-11-01), Gray et al.
patent: 4796185 (1986-12-01), Yoshimura et al.
patent: 5113340 (1992-05-01), McWherter
patent: 5229936 (1993-07-01), Decker et al.
patent: 5450598 (1995-09-01), Kaplan et al.
Haskin, R.L. and Hollaar, L.A., "Operational Characteristics of a Hardware-Based Pattern Matcher," ACM Transactions on Database Systems, vol. 8, No. 2, Mar. 1983, pp. 15-40.
European Search Report and Annex, Application No. EP 93 30 8298, dated Mar. 4,1994.
Katajainen, J. and Raita, T., "An Approximation Algorithm for Space-optimal Encoding of a Text,"The Computer Journal, vol. 32, No. 3, 1989, pp. 228-237.
Srihari, S.N., Hull, J.J. Choudhari, R., "Integration of bottom-up and top-down contextual knowledge in text error correction," AFIPS Conference Proceedings, 1982 National Computer Conference Jun. 7-10, 1982, Huston, Texas, pp. 501-508.
Hull, J.J., Srihari, S.N. and Choudhari, R., "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.
Lucchesi, C.L. and Kowaltowski, T., "Applications of Finite Automata Representing Large Vocabularies," Software--Practice and Experience, vol. 23, No. 1, January 1993, pp. 15-30.
Revuz, D., "Minimisation of acyclic deterministic automata in linear time," Theoretical Computer Science, vol. 92, No. 1, Jan. 1992, pp. 181-189.
"Lecture Notes in Computer Science - Computer Programs for Spelling Correction," James L. Peterson, 1980, pp. 57-66.
"Applied Discret Structures for Computer Science," by Doerr, Alan W., et al. -Science Research Associates, Inc. 1985, pp. 176-178.
Report R77-008, Bird et al., Operating Systems, Inc., 1977.
IEEE Computer Magazine, article entitled Text Retrieval Computers by Lee A. Hollaar, 1979, pp. 40-50.
Appel, A.W. and Jacobson, G.J., "The World's Fastest Scrabble Program", Communications of the ACM, vol. 31, No. 5, May 1988 pp. 572-579.
Ainon, R.N., "Storing Text Using Integer Codes", Proceedings of the 11th International Conference on Computational Linguistics, Bonn, West Germany, Aug. 1986, pp. 418-420.
"Type Right Catches Errors As You Type (Beep Beep)", Xerox Corporation 1986.
"Product Overview for the Memex Information Engine," Memex Information Engines Ltd., Jun. 1986, pp. 7-10, 31-35.
Kaplan Ronald M.
Kay Martin
Kulik Paul V.
Xerox Corporation
LandOfFree
Word/number and number/word mapping does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Word/number and number/word mapping, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Word/number and number/word mapping will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-1864223