Morphological search and replace

• US 5,873,660 A
• Filed: 06/19/1995
• Issued: 02/23/1999
• Est. Priority Date: 06/19/1995
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Walsh, James E., Fein, Ronald A.
• Primary Examiner(s): HILTEN, JOHN S
• Application Number:
  US08/491,750
• Time in Patent Office: 1,345 Days
• Field of Search: 400/63, 400/74, 364/419.13, 364/419.14, 395/794, 395/795
• US Class Current: 400/63
• CPC Class Codes: B41J 5/30 Character or syllable selection controlled by recorded information
• CPC Class Codes: G06F 40/166 Editing, e.g. inserting or deleting

Abstract

A morphological find and replace editing tool for a word processor replaces inflected forms of a user-specified find word in a text document with inflected forms of a user-specified replacement word having matching parts of speech. The tool retrieves sets of word forms having a same root word as the find and replacement words, respectively, from a word forms database. The tool selects a single set of word forms with a common root word for each of the find and replacement words such that the find and replacement words are matching parts of speech. Where word forms in the find word'"'"'s set are found in the text document, they are replaced with a word form from the replacement word'"'"'s set with a best matching part of speech.

Claims

1. In a word processor for a computer system, a method of finding and replacing forms of a find word with forms of a replace word in a text document, the method comprising:

storing a plurality of word form sets in a word forms database, each word form set comprising a plurality of word forms having a same word base, each word form being associated with at least one part-of-speech identifier;

searching the word forms database for any word form sets that contain a word form matching the find word, and for any word form sets that contain a word form matching the replace word;

in a case where multiple word form sets each contain a word form matching the find word, selecting a single find word form set out of the multiple word form sets that contain a word form matching the find word;

in a case where multiple word form sets each contain a word form matching the replace word, selecting a single replace word form set out of the multiple word form sets that contain a word form matching the replace word;

searching the text document for a target word that matches any word form in the find word form set, the matched word form in the find word form set being a found word form;

searching the replace word form set for a replacement word form whose associated part-of-speech identifier matches a part-of-speech identifier associated with the found word form; and

replacing the target word with the replacement word form.

2. The method of claim 1 wherein the step of selecting the find word form set in the case where multiple word form sets each contain a word form matching the find word, comprises:

searching the word forms database for any word forms that match the find word;

searching the word forms database for any word forms that match the replace word;

selecting out of the word forms that match the find word, a single find word form whose associated part-of-speech identifier best matches a part-of-speech identifier associated with the word forms that match the replace word; and

selecting a word form set that contains the single selected find word form as the find word form set.

3. A computer-readable medium having computer-executable instructions for performing the steps recited in claim 2.

4. The method of claim 2 wherein the step of selecting the single find word form comprises:

selecting as the single find word form, a word form whose associated part-of speech identifier best matches a part-of-speech identifier associated with one of the word forms that match the replace word according to a predetermined ranking.

5. The method of claim 2 wherein the step of selecting the replace word form set in the case where multiple word form sets each contain a word form matching the replace word, comprises:

selecting out of the word forms that match the replace word, a single replace word form whose associated part-of-speech identifier best matches a part-of-speech identifier associated with the word forms that match the find word; and

selecting a word form set that contains the single selected replace word form as the replace word form set.

6. The method of claim 1 wherein the step of selecting the replace word form set in the case where multiple word form sets each contain a word form matching the replace word, comprises:

searching the word forms database for any word forms that match the find word;

searching the word forms database for any word forms that match the replace word;

selecting out of the word forms that match the replace word, a single replace word form whose associated part-of-speech identifier best matches a part-of-speech identifier associated with the word forms that match the find word; and

selecting a word form set that contains the single selected replace word form as the replace word form set.

7. The method of claim 6 wherein the step of selecting the single replace word form comprises:

selecting as the single replace word form, a word form whose associated part-of-speech identifier exactly matches a part-of-speech identifier associated with one of the word forms that match the find word.

8. The method of claim 6 wherein the step of selecting the single replace word form comprises:

selecting as the single replace word form, a word form whose associated part-of speech identifier best matches a part-of-speech identifier associated with one of the word forms that match the find word according to a predetermined ranking.

9. The method of claim 6 wherein the step of selecting the find word form set in the case where multiple word form sets each contain a word form matching the find word, comprises:

selecting out of the word forms that match the find word, a single find word form whose associated part-of-speech identifier best matches a part-of-speech identifier associated with the word forms that match the replace word; and

selecting a word form set that contains the single selected find word form as the find word form set.

10. The method of claim 1 comprising:

in a case where part-of-speech identifiers of multiple word forms in the replace word form set match part-of-speech identifiers associated with the found word form, selecting a single replacement word form whose part-of-speech identifier best matches the part-of-speech identifiers associated with the found word form.

11. The method of claim 10 wherein the step of selecting the single replacement word form comprises:

selecting a word form in the replace word form set whose part-of-speech identifiers exactly match the part-of-speech identifiers of the found word as the single replacement word form.

12. The method of claim 10 wherein the step of selecting the single replacement word form comprises:

scoring each of the word forms in the replace word form whose part-of-speech identifier matches at least one of the part-of-speech identifiers associated with the found word form according to a predetermined ranking of any part-of-speech identifiers that match the part-of-speech identifiers associated with the found word form; and

selecting a highest scoring word form as the single replacement word form.

13. The method of claim 1 comprising:

in a case where first and second word forms in the find word form set match the target word, searching the replace word form set for a replacement word form whose part-of-speech identifier matches a part-of-speech identifier associated with the first word form; and

if no word form in the replace word form set has an associated part-of-speech that matches a part-of-speech identifier associated with the first word form, searching the replace word form set for a replacement word form whose part-of-speech identifier matches a part-of-speech identifier associated with the second word form.

14. A computer-readable medium having computer-executable instructions for performing the steps recited in claim 6.

15. A computer-readable medium having computer-executable instructions for performing the steps recited in claim 1.

16. In a word processor for a computer system, a method of finding and replacing forms of a find word with forms of a replace word in a text document, the method comprising:

storing a plurality of word form sets in a word forms database, each word form set comprising a plurality of word forms having a same word base, each word form being associated with at least one part-of-speech identifier;

searching the word forms database for a find word form set that contains a word form matching the find word, and for a replace word form set that contains a word form matching the replace word;

searching the text document for a target word that matches any word form in the find word form set, the matched word form in the find word form set being a found word form;

searching the replace word form set for a replacement word form whose associated part-of-speech identifier matches a part-of-speech identifier associated with the found word form;

in a case where part-of-speech identifiers of multiple word forms in the replace word form set match part-of-speech identifiers associated with the found word form, selecting a single replacement word form whose part-of-speech identifier best matches the part-of-speech identifiers associated with the found word form; and

replacing the target word with the replacement word form.

17. The method of claim 16 wherein the step of selecting the single replacement word form comprises:

selecting a word form in the replace word form set whose part-of-speech identifiers exactly match the part-of-speech identifiers of the found word as the single replacement word form.

18. The method of claim 16 wherein the step of selecting the single replacement word form comprises:

scoring each of the word forms in the replace word form whose part-of-speech identifier matches at least one of the part-of-speech identifiers associated with the found word form according to a predetermined ranking of any part-of-speech identifiers that match the part-of-speech identifiers associated with the found word form; and

selecting a highest scoring word form as the single replacement word form.

19. A computer-readable medium having computer-executable instructions for performing the steps recited in claim 16.

20. In a word processor for a computer system, a method of finding and replacing forms of a find word with forms of a replace word in a text document, the method comprising:

storing a plurality of word form sets in a word forms database, each word form set comprising a plurality of word forms having a same word base, each word form being associated with at least one part-of-speech identifier;

searching the word forms database for a find word form set that contains a word form matching the find word, and for a replace word form set that contains a word form matching the replace word;

searching the text document for a target word that matches any word form in the find word form set, the matched word form in the find word form set being a found word form;

in a case where first and second word forms in the find word form set match the target word, searching the replace word form set for a replacement word form whose part-of-speech identifier matches a part-of-speech identifier associated with the first word form; and

if no word form in the replace word form set has an associated part-of-speech that matches a part-of-speech identifier associated with the first word form, searching the replace word form set for a replacement word form whose part-of-speech identifier matches a part-of-speech identifier associated with the second word form; and

replacing the target word with the replacement word form.

21. A computer-readable medium having computer-executable instructions for performing the steps recited in claim 20.

22. A word processor in a computer system, comprising:

a first user interface control operable by a user to select morphological find and replace editing of forms of a find word with forms of a replace word within a text document;

a word forms database for storing a plurality of word form sets, each word form set comprising a plurality of word forms having a same word base, each word form being associated with at least one part-of-speech identifier;

a morphological word database engine for searching the word forms database for find word form sets that contain word forms matching the find word, and for replace word form sets that contain word forms matching the replace word;

a morphological find and replace editing service operative responsive to the first user interface control;

(a) to cause the morphological word database engine to search for the find word form sets and the replace word form sets;

(b) to select only a single find word form set and only a single replace word form set that contain word forms matching the find word and the replace word, respectively;

(c) to search the text document for a target word matching any word form of the selected single find word form set, the matched word form of the selected single find word form set being a found word form;

(d) to select a replacement word form from the selected single replace word form set whose associated part-of-speech identifier matches a part-of-speech identifier of the found word form; and

(e) to replace the target word with the replacement word form.

23. The word processor of claim 22 comprising:

a second user interface control operable by the user to select morphological find and replace editing of all target words matching forms of the find word with forms of the replace word within at least a portion of the text document;

a user interface dialog displayed responsive to the second user interface control and comprising a recommendation against selecting morphological find and replace editing of all target words; and

a third user interface control associated with the user interface dialog operable by the user to confirm selection of morphological find and replace editing of all target words.

24. The word processor of claim 22 wherein the morphological find and replace editing service selects the single find word form set that contains a word form matching the find word whose associated part-of-speech identifier best matches an associated part-of-speech identifier of a word form matching the replace word in the replace word form sets.

25. The word processor of claim 22 wherein the morphological find and replace editing service selects the single replace word form set that contains a word form matching the replace word whose associated part-of-speech identifier best matches an associated part-of-speech identifier of a word form matching the find word in the find word form sets.

26. The word processor of claim 22 wherein the morphological find and replace editing service selects the found word form out of the single find word form set whose part-of-speech identifier matches a part-of-speech identifier of any word form in the single replace word form set.

27. The word processor of claim 22 wherein the morphological find and replace editing service selects the replacement word form out of the word forms in the single replace word form set whose part-of-speech identifier best matches the found word form'"'"'s part-of-speech identifier.

28. The word processor of claim 27 wherein at least one of the word form sets in the word forms database comprises a word form variant of a dialect associated with a part-of-speech identifier indicative of the dialect, and wherein the morphological find and replace editing service selects the replacement word form associated with a part-of-speech identifier indicative of the dialect out of a plurality of replace word forms associated with part-of-speech identifiers that match the found word form'"'"'s part-of-speech identifier as the replacement word form whose part-of-speech identifier best matches the found word form'"'"'s part-of-speech identifier.

29. The word processor of claim 27 wherein the morphological find and replace editing service scores each word form in the single replace word form set whose part-of-speech identifier matches the found word form'"'"'s part-of-speech identifier according to a predetermined ranking of part-of-speech identifiers that match the found word form'"'"'s part-of-speech identifier, and selects the highest scoring part-of-speech identifier as the best-matching part-of-speech identifier.

30. In a word processor for a computer system, a method of finding and replacing forms of a find word with forms of a replace word in a text document, the method comprising:

storing a plurality of word form sets in a word forms database, each word form set comprising a plurality of word forms having a same word base, each word form being associated with at least one part-of-speech identifier;

searching the word forms database for any word form sets that contain a word form matching the find word, and for any word form sets that contain a word form matching the replace word;

in a case where multiple word form sets each contain a word form matching the find word, selecting only a single find word form set out of the multiple word form sets that contain a word form matching the find word;

searching the text document for a target word that matches any word form in the find word form set, the matched word form in the find word form set being a found word form;

searching the replace word form set for a replacement word form whose associated part-of-speech identifier matches a part-of-speech identifier associated with the found word form; and

replacing the target word with the replacement word form;

wherein the step of selecting the find word form set in the case where multiple word form sets each contain a word form matching the find word, comprises;

searching the word forms database for any word forms that match the find word;

searching the word forms database for any word forms that match the replace word;

selecting out of the word forms that match the find word, a single word form whose associated part-of-speech identifier exactly matches a part-of-speech identifier associated with one of the word forms that match the replace word; and

selecting a word form set that contains the single selected find word form as the find word form set.