Directory lookup method and apparatus

• US 4,453,217 A
• Filed: 01/04/1982
• Issued: 06/05/1984
• Est. Priority Date: 01/04/1982
• Status: Expired due to Term

• Current Assignee: Bell Telephone Laboratories, Inc. (Nokia Corporation)
• Original Assignee: Bell Telephone Laboratories, Inc. (Nokia Corporation)
• Inventors: Boivie, Richard H.
• Primary Examiner(s): NOT, DEFINED
• Application Number:
  US06/337,093
• Time in Patent Office: 883 Days
• Field of Search: 364/200, 364/300, 364/900
• US Class Current: 1/1
• CPC Class Codes: G06F 16/90344 by using string matching techniques
• CPC Class Codes: G06F 40/232 Orthographic correction, e.g. spell checking or vowelisation
• CPC Class Codes: H04M 1/2748 by matching character strings
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access

Abstract

There is disclosed a spelling correction arrangement for use in directory lookup applications. The arrangement corrects errors by finding the name in the directory that most closely resembles the name requested by the user. The arrangement is based on a recursive routine that continually subdivides the problem of finding a given name in a given directory into smaller subproblems in which shorter names are to be found in smaller directories. Multiple spelling errors are easily accommodated since the technique uses the given directory of names to limit the search. The technique allows the algorithm to find the closest name in the directory without actually considering the vast majority of the names that appear in the directory.

Claims

1. 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.

2. 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.

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

4. 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.

5. 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.

6. 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.

7. 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.

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

9. 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.

10. 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.

11. 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.

12. 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.

13. 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.

14. 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.

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

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

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

18. 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.

19. 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.

20. 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.

21. 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.

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

23. 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.

24. 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.

25. 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.

26. 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.

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

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

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

30. 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.

31. The invention set forth in claim 30 further comprising

means for substituting in said text each said presented word for the corresponding misspelled word.

32. 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.

33. 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.

34. 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.

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

36. 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.

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

38. 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.

39. 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.

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

41. 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.

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

43. 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.

44. 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.

45. 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.

46. 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.

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

48. 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.

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

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

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

52. 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.

53. 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.

54. 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.

55. 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.

56. 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.

57. 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.

58. 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.

59. 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.