US4453217A — Directory lookup method and apparatus

Claim 1

Independent Claim 58 words

A directory lookup method comprising the steps of subdividing a given directory of character strings into at least one subdirectory of character strings having bounds defined by a character of a presented character string, and examining said subdirectory for matches between a particular character of said presented character string and a particular character of said subdirectory character string.

Claim 2

Dependent Claim 58 words

A directory lookup method comprising the steps of subdividing a given directory of character strings into at least one subdirectory of character strings having bounds defined by a character of a presented character string, and examining said subdirectory for matches between a particular character of said presented character string and a particular character of said subdirectory character string.

Claim 3

Dependent Claim 28 words

The invention set forth in claim 1 wherein said subdividing and said examining steps are performed recursively by changing either said presented word character or said directory character.

Claim 4

Dependent Claim 20 words

The invention set forth in claim 2 further comprising the step of identifying directory strings of characters where matches occur.

Claim 5

Dependent Claim 42 words

The invention set forth in claim 3 wherein said method further includes the step of utilizing said identified character strings one string at a time dependent upon the number of mismatched characters between said directory character string and said presented character string.

Claim 6

Dependent Claim 31 words

The invention set forth in claim 3 wherein said method further comprises the step of performing said subdividing and said examining steps individually on separate portions of said presented character string.

Claim 7

Dependent Claim 44 words

The invention set forth in claim 5 wherein said arrangement further includes the steps of calculating an error number for each said identified character string, utilizing said identified character strings one string at a time in an order determined by said calculated error number.

Claim 8

Dependent Claim 52 words

The invention set forth in claim 6 wherein said error number is calculated separately for each said separate portion of said presented character string, and wherein said determined order of utilizing said matched character strings is established jointly by said error number calculations of each said portion of said presented character string.

Claim 9

Dependent Claim 24 words

The invention set forth in claim 7 wherein said error number calculation is made using different criteria for each said presented character string portion.

Claim 10

Dependent Claim 82 words

The invention set forth in claim 8 wherein the criterion for calculating said error number for a first portion of each said identified character string is the number of mismatched characters between said directory character string and said presented character string, and wherein the criterion for calculating said error number for a second portion of each said identified character string is based on the number of characters that must be removed from one string to make it an abbreviation of the other.

Claim 11

Dependent Claim 41 words

The invention set forth in claim 9 wherein said second portion error calculating criterion is further defined as the number of initial characters skipped plus the smaller of the number of input characters skipped and the number of directory characters skipped.

Claim 12

Dependent Claim 30 words

The invention set forth in claim 3 wherein said identifying step includes the step of terminating said subdividing and said examining step when a preset number of character mismatches occur.

Claim 13

Dependent Claim 27 words

The invention set forth in claim 11 wherein said terminating step includes the distribution of character mismatches between said presented character string and said directory character string.

Claim 14

Dependent Claim 29 words

The invention set forth in claim 3 wherein said identifying step includes the step of limiting said subdividing and examining steps as a result of identified character string matches.

Claim 15

Independent Claim 109 words

A method of providing directory look up, said method comprising the steps of continually subdividing a given directory into a subdirectory of character strings having bounds defined by certain characters of a presented name, recursively examining said subdirectory character strings for matches between a certain presented name character and a certain subdirectory character, said examination to cease when the last character of the presented name characters has been examined and when the first character string in the subdirectory is zero, calculating an error number for each subdirectory string of characters where matches occur, and sequentially providing indications of the subdirectory names having error numbers lower than a preestablished number.

Claim 16

Independent Claim 109 words

A method of providing directory look up, said method comprising the steps of continually subdividing a given directory into a subdirectory of character strings having bounds defined by certain characters of a presented name, recursively examining said subdirectory character strings for matches between a certain presented name character and a certain subdirectory character, said examination to cease when the last character of the presented name characters has been examined and when the first character string in the subdirectory is zero, calculating an error number for each subdirectory string of characters where matches occur, and sequentially providing indications of the subdirectory names having error numbers lower than a preestablished number.

Claim 17

Dependent Claim 17 words

The invention set forth in claim 14 wherein the sequence is controlled by said error number calculation.

Claim 18

Dependent Claim 21 words

The invention set forth in claim 14 wherein the examination of a subdirectory stops when a preset error number is calculated.

Claim 19

Dependent Claim 18 words

The invention set forth in claim 15 wherein said subdividing step is directed by said calculated error number.

Claim 20

Independent Claim 70 words

The method of identifying from a directory of character strings a particular one of said character strings that most closely matches an input character string, said method comprising the steps of recursively defining the limits of a directory that is to be searched, and recursively defining a character index in each said defined directory and a character index of said input character string and comparing said defined characters for mismatches.

Claim 21

Independent Claim 70 words

The method of identifying from a directory of character strings a particular one of said character strings that most closely matches an input character string, said method comprising the steps of recursively defining the limits of a directory that is to be searched, and recursively defining a character index in each said defined directory and a character index of said input character string and comparing said defined characters for mismatches.

Claim 22

Dependent Claim 29 words

The invention set forth in claim 18 further comprises the steps of generating from said recursive steps a string of directory characters having the lowest number of mismatched characters.

Claim 23

Dependent Claim 94 words

The invention set forth in claim 18 wherein said recursive steps are arranged to divide the problem of finding the character string in said directory that most closely resembles said input character string into classes of subproblems based on the following assumptions: (a) that the next character in said input string is actually the next character in said input string, (b) that the next character in said input strings is an extraneous character, and (c) that the input string may be missing a character that should preceed the next character in said input string.

Claim 24

Dependent Claim 38 words

The invention set forth in claim 19 wherein said input character string and said directory of character strings are divided into parts, and wherein said recursive steps are performed individually, on each said part of said input string.

Claim 25

Dependent Claim 22 words

The invention set forth in claim 21 wherein said generated mismatched character string is dependent upon mismatches in both of said parts.

Claim 26

Dependent Claim 30 words

The invention set forth in claim 22 wherein the criteria for mismatches between said input string of characters and said directory string of characters is different for each said part.

Claim 27

Dependent Claim 55 words

The invention set forth in claim 18 further comprising the steps of calculating the mismatch distance, in terms of character mismatches, between a currently defined character index and other possible character indexes subservient to said index, and limiting said recursive steps when it is determined that further recursions can only result in increased mismatched distances.

Claim 28

Dependent Claim 26 words

The invention set forth in claim 19 wherein said generating step includes the step of terminating said recursion when a particular number of character mismatches occur.

Claim 29

Dependent Claim 30 words

The invention set forth in claim 25 wherein said terminating step includes distributing mismatches caused by missing characters in either the input string or directory string between each said string.

Claim 30

Dependent Claim 21 words

The invention set forth in claim 25 wherein said terminating step includes tracking substitutional errors between said input and directory strings.

Claim 31

Dependent Claim 21 words

The invention set forth in claim 25 wherein said terminating step includes tracking transpositional errors between said input and directory strings.

Claim 32

Dependent Claim 22 words

The invention set forth in claim 18 further comprising the step of modifying said character indexes dependent upon said compared character strings.

Claim 33

Dependent Claim 71 words

In a text editing system an arrangement for controlling spelling errors in said text, said arrangement comprising means for identifying words in said text which are misspelled, means for comparing each said identified misspelled word with a dictionary of correctly spelled words, and means cooperating with said comparing means for presenting a word from said dictionary corresponding to the closest match between said misspelled word and a word in said dictionary.

Claim 34

Dependent Claim 71 words

In a text editing system an arrangement for controlling spelling errors in said text, said arrangement comprising means for identifying words in said text which are misspelled, means for comparing each said identified misspelled word with a dictionary of correctly spelled words, and means cooperating with said comparing means for presenting a word from said dictionary corresponding to the closest match between said misspelled word and a word in said dictionary.

Claim 35

Dependent Claim 24 words

The invention set forth in claim 30 further comprising means for substituting in said text each said presented word for the corresponding misspelled word.

Claim 36

Dependent Claim 32 words

The invention set forth in claim 30 wherein said closest match is defined as the word in said dictionary requiring the smallest number of modifications to be transformed into said misspelled word.

Claim 37

Dependent Claim 86 words

The invention set forth in claim 30 wherein said dictionary of words includes strings of characters and said misspelled word is a string of characters, and wherein said comparing means includes means for subdividing each said dictionary of character strings into at least subdictionary of character strings having bounds defined by a character of each said misspelled character string, and means for examining said subdictionary for mismatches between a particular character of said misspelled character string and a particular character of each said subdictionary character string.

Claim 38

Dependent Claim 28 words

The invention set forth in claim 33 wherein said subdividing and said examining means are recursively enabled by changing either the misspelled word character or the dictionary character.

Claim 39

Dependent Claim 21 words

The invention set forth in claim 30 wherein said comparing means includes means for identifying strings of characters having low mismatches.

Claim 40

Dependent Claim 31 words

The invention set forth in claim 35 wherein said comparing means includes means for terminating the analysis of a particular line of investigation when a preset number of character mismatches occur.

Claim 41

Dependent Claim 23 words

The invention set forth in claim 36 wherein said preset number is distributed between said misspelled character string and said dictionary character strings.

Claim 42

Dependent Claim 29 words

The invention set forth in claim 36 wherein said terminating means includes means for tracking substitutional errors between characters of said misspelled word and characters of said dictionary words.

Claim 43

Dependent Claim 29 words

The invention set forth in claim 36 wherein said terminating means includes means for tracking transpositional errors between characters of said misspelled word and characters of said dictionary words.

Claim 44

Dependent Claim 20 words

The invention set forth in claim 30 further comprising means for changing said comparing sequence dependent upon prior compared words.

Claim 45

Dependent Claim 80 words

In a communication system, an arrangement for communicating between at least two terminals of said system, said arrangement comprising means for accepting at a first terminal, a name to which communication is to be directed, means for comparing an accepted name to a directory of defined names, means for selecting from said directory the closest name to said accepted name, and means controlled by said selection means for retrieving from said directory control information associated with said closest directory name.

Claim 46

Dependent Claim 80 words

In a communication system, an arrangement for communicating between at least two terminals of said system, said arrangement comprising means for accepting at a first terminal, a name to which communication is to be directed, means for comparing an accepted name to a directory of defined names, means for selecting from said directory the closest name to said accepted name, and means controlled by said selection means for retrieving from said directory control information associated with said closest directory name.

Claim 47

Dependent Claim 20 words

The invention set forth in claim 41 further comprising means for changing said comparing sequence dependent upon prior compared names.

Claim 48

Dependent Claim 31 words

The invention set forth in claim 41 further comprising means controlled by said retrieved control information for establishing communication between said first terminal and other terminals associated with said presented name.

Claim 49

Dependent Claim 32 words

The invention set forth in claim 41 wherein said closest name is defined as the name in said directory requiring the smallest number of modifications to be transformed into said accepted name.

Claim 50

Dependent Claim 83 words

The invention set forth in claim 41 wherein each said directory name includes strings of characters and said accepted name includes strings of characters, and wherein said comparing means includes means for subdividing said directory of character strings into at least one subdirectory of character strings having bounds defined by a character of said provided character string, and means for examining said subdirectory for matches between a particular character of said provided character string and a particular character of said subdirectory character string.

Claim 51

Dependent Claim 29 words

The invention set forth in claim 45 wherein said subdividing and said examining means are recursively enabled by changing either the provided name character or the directory name character.

Claim 52

Dependent Claim 18 words

The invention set forth in claim 41 wherein said selecting means includes means for identifying matches between characters.

Claim 53

Independent Claim 111 words

A system for providing directory look up, said system comprising means for subdividing a given directory into a subdirectory of names having bounds defined by a certain character of a presented name, means for recursively examining said subdirectory names for matches between a certain presented name character and a certain subdirectory character, said examination to cease when the last character of the presented name has been examined and when the first character string in the subdirectory is zero, means for calculating an error number for each subdirectory string of characters where matches occur, and means for sequentially providing indications of the directory names having error numbers lower than a preestablished number.

Claim 54

Independent Claim 111 words

A system for providing directory look up, said system comprising means for subdividing a given directory into a subdirectory of names having bounds defined by a certain character of a presented name, means for recursively examining said subdirectory names for matches between a certain presented name character and a certain subdirectory character, said examination to cease when the last character of the presented name has been examined and when the first character string in the subdirectory is zero, means for calculating an error number for each subdirectory string of characters where matches occur, and means for sequentially providing indications of the directory names having error numbers lower than a preestablished number.

Claim 55

Dependent Claim 20 words

The invention set forth in claim 48 wherein said sequentially providing means includes means controlled by said error number calculation.

Claim 56

Dependent Claim 18 words

The invention set forth in claim 48 wherein said recursive means is controlled by said error number calculation.

Claim 57

Dependent Claim 21 words

The invention set forth in claim 48 wherein said examination of a subdirectory ceases when a preset error number is reached.

Claim 58

Dependent Claim 85 words

In a computer system, an algorithm for solving the problem of identifying from a set of character strings a particular character string that most closely resembles an input character string, said algorithm comprising the steps of decomposing said original problem into smaller subproblems in which smaller subdirectories, consisting of characters from said original directory, are searched to identify character strings closely resembling character strings obtained by removing characters from said input character string, and selecting from any said identified character strings, said particular character string.

Claim 59

Dependent Claim 85 words

In a computer system, an algorithm for solving the problem of identifying from a set of character strings a particular character string that most closely resembles an input character string, said algorithm comprising the steps of decomposing said original problem into smaller subproblems in which smaller subdirectories, consisting of characters from said original directory, are searched to identify character strings closely resembling character strings obtained by removing characters from said input character string, and selecting from any said identified character strings, said particular character string.

Claim 60

Dependent Claim 44 words

The invention set forth in claim 52 wherein said subproblems are recursively decomposed into smaller subproblems until the resulting subproblems are ones in which a string with no characters is to be found in a directory in which the first string has no characters.

Claim 61

Dependent Claim 69 words

The invention set forth in claim 52 wherein three classes of subproblems are defined based on the following possibilities, (a) that the first character of each input string is correct, (b) that the first character of each input string is an extraneous character which should be discarded, and (c) that each input string is missing a character that should be inserted before the first character of that input string.

Claim 62

Dependent Claim 95 words

The invention set forth in claim 54 wherein said first class (a) of subproblems is investigated by a method comprising the steps of identifying the portion of the directory in which the first character of the input string is matched by the first character of the directory strings, said portion to be known as the matching portion of the directory, and searching a directory obtained from the matching portion by removing the first character from each string in said matching portion for a character string closely resembling the input string with its first character removed.

Claim 63

Dependent Claim 34 words

The invention set forth in claim 55 wherein said second class (b) of subproblems is investigated by finding a string in the directory that closely resembles the input string with its first character removed.

Claim 64

Dependent Claim 44 words

The invention set forth in claim 55 wherein said third class (c) of the subproblems is investigated by searching for a string that closely resembles the input string in a directory obtained from the original directory by removing the first character from each string.

Claim 65

Dependent Claim 64 words

The invention set forth in claim 57 wherein the string in the original directory corresponding to the first string the directory of a trivial subproblem is defined to be at a distance of n from the original input string if the sequence of subproblems from the original problem to the trivial subproblem involves some number of class (b) and class (c) subproblems totaling n.

Claim 66

Dependent Claim 50 words

The invention set forth in claim 58 wherein a subproblem is not investigated if the number of class (b) and class (c) subproblem from the original problems to the current subproblem is greater than or equal to the distance between the original input string and some previously identified directory string.

Annuity Stage	Window Opens	Payment Deadline	Surcharge Period Until	Estimated Fee	Status
3.5 Years (Year 4)	1987-06-05	1987-12-05	1988-06-05	$2000.00	Window Closed / Lapsed
7.5 Years (Year 8)	1991-06-05	1991-12-05	1992-06-05	$3760.00	Window Closed / Lapsed
11.5 Years (Year 12)	1995-06-05	1995-12-05	1996-06-05	$7700.00	Window Closed / Lapsed

Directory lookup method and apparatus

Abstract

Inventors

Bibliographic Details

Claims Analysis

References Cited (Backward Citations)

USPTO Annuity & Maintenance Windows

Assigned Categories & Tags

Assign Category Tag