Xerox Corporation

Martin Kay

Ronald M Kaplan

Per-Kristian G Halvorsen

John Maxwell

Todd A Cass

Jan O Pedersen

Daniel P Huttenlocher

M Margaret Withgott

William M Newman

John Seely Brown

Lauri J Karttunen

Douglass R Cutting

Steven C Bagley

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.

Word/number and number/word mapping

A method and apparatus for applying morphological image criteria that identify image units in an undecoded document image having significant information content, and for retrieving related data that supplements the document either from elsewhere within the document or a source external to the document. The retrieved data can result from character code recognition or template matching of the identified significant image units, or the retrieved data can result directly from an analysis of the morphological image characteristics of the identified significant image units. A reading machine can allow a user to browse and select documents or segments thereof, and to obtain interactive retrieval of documents and supplemental data.

Method and apparatus for supplementing significant portions of a

The present invention solves a number of problems in using stems (canonical indicators of word meanings) in full-text retrieval of natural language documents, and thus permits recall to be improved without sacrificing precision. It uses various arrangements of finite-state transducers to accurately encode a number of desirable ways of mapping back and forth between words and stems, taking into account both systematic aspects of a language's morphological rule system and also the word-by-word irregularities that also occur. The techniques described apply generally across the languages of the world and are not just limited to simple suffixing languages like English. Although the resulting transducers can have many states and transitions or arcs, they can be compacted by finite-state compression algorithms so that they can be used effectively in resource-limited applications. The invention contemplates the information retrieval system comprising the novel finite state transducer as a database and a processor for responding to user queries, for searching the database, and for outputting proper responses, if they exist, as well as the novel database used in such a system and methods for constructing the novel database.

Finite-state transduction of related word forms for text indexing and

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.

Stored string data with element data units and pointer data units in

Stored string data with next and alternative information a processor can

Stored string data with encoded data units from subranges of values that

Stored mapping data with information for skipping branches while keeping

A thesaurus receives a word and uses a word list to obtain a corresponding number. The corresponding number is then compared with numbers grouped in sequence to represent synonym groups. For each match, information about the group including the matching number is determined based on the sequential position of the matching number. This information may include the group's part of speech, its length, and the positions of its members. The numbers in the group are retrieved and the corresponding synonymous words are obtained, again using the word list. Tables contain data used to determine the information about a group containing a matching number. The groups are sorted by part of speech and one table contains information about the ending position of each part of speech so that a group's part of speech can be determined from the position of any number in it. The groups within each part of speech are sorted by length and another table contains the number of groups of each length so that a group's length and the positions of its numbers can be determined from the position of any number in it. Each group is also sorted by number so that if a candidate number is less than a number being compared, the remaining numbers in that group can be skipped. The groups of equal length within a part of speech are sorted by first number so that if a candidate number is less than the first number of a group, the remaining groups of that length can be skipped. Each number is in one or more parts, at least one of which may be less than a full byte. The full byte is an integral multiple of each part's length, so that each part can be accessed and compared in a single cycle.

Thesaurus with compactly stored word groups

Finite state machine data storage where data transition is accomplished

Growing community of inventors

Menlo Park, CA, United States of America

Martin Kay