User-modifiable word lattice display for editing documents and search queries

• US 8,972,240 B2
• Filed: 08/18/2011
• Issued: 03/03/2015
• Est. Priority Date: 05/19/2011
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Brockett, Christopher John, Dolan, William Brennan
• Primary Examiner(s): Shah, Paras D
• Assistant Examiner(s): THOMAS-HOMESCU, ANNE L
• Application Number:
  US13/212,973
• Publication Number:
  US 20120296635A1
• Time in Patent Office: 1,293 Days
• Field of Search: 704/9, 704/276, 704/10, 704/277, 704/255, 707/769, 707/722, 707/723, 707/706, 707/786, 707/740, 707/736, 707/705, 707/728, 707/748, 707/749, 707/771, 707/739, 707/738, 707/609, 707/758, 707/702, 715/762, 715/835, 715/753, 715/738, 715/854, 715/716, 715/708, 715/769, 715/828, 715/810, 715/760, 715/781, 715/712, 715/766, 715/234, 715/841, 715/764, 715/711, 715/705, 715/700, 715/822, 715/838, 715/763, 715/236
• US Class Current: 704/9
• CPC Class Codes: G06F 16/332 Query formulation
• CPC Class Codes: G06F 40/131 Fragmentation of text files, e.g. creating reusable text-blocks; Linking to fragments, e.g. using XInclude; Namespaces
• CPC Class Codes: G06F 40/166 Editing, e.g. inserting or deleting
• CPC Class Codes: G06F 40/247 Thesauruses; Synonyms
• CPC Class Codes: G06F 40/47 Machine-assisted translation, e.g. using translation memory

Abstract

An “Interactive Word Lattice” provides a user interface for interacting with and selecting user-modifiable paths through a lattice-based representation of alternative suggested text segments in response to a user'"'"'s text segment input, such as phrases, sentences, paragraphs, entire documents, etc. More specifically, the user input is provided to a trained paraphrase generation model that returns a plurality of alternative text segments having the same or similar meaning as the original user input. An interactive graphical lattice-based representation of the alternative text segments is then presented to the user. One or more words of each alternative text segment represents a “node” of the lattice, while each connection between nodes represents a lattice “edge. Both nodes and edges are user modifiable. Each possible path through the lattice corresponds to a different alternative text segment. Users select a path through the lattice to select an alternative text to the original input.

Claims

1. A computer-readable storage device having computer executable instructions stored therein for implementing an interactive user interface for providing alternative suggested text segments to a user, said instructions causing a computing device to perform actions comprising:

receiving an input text segment comprising a sequence of two or more words, said input text segment having a linguistic meaning;

processing the input text segment without the use of wildcards using one or more contextual semantic similarity generation modules to generate a plurality of suggested alternative text segments, each alternative text segment comprising a different sequence of words, each alternative text segment having a linguistic meaning similar to the linguistic meaning of the input text segment such that each alternative text segment is related to input text segment by linguistic context;

constructing a lattice-based representation of the plurality of suggested alternative text segments as parallel text segments connected by linguistic context, and wherein each node of a plurality of nodes of the lattice includes one or more contiguous words of one of the alternative suggested text segments, and wherein edges of the lattice connect each node to one or more other nodes of the lattice such that each of the plurality of suggested alternative text segments are fully represented by the lattice;

displaying the lattice in a user interface window;

providing a user interface to select one of the suggested alternative text segments by selecting a path that traverses the lattice through a plurality of connected nodes from a beginning of the displayed lattice to an end of the displayed lattice; and

wherein each possible path through the lattice corresponds to a sequence of nodes and edges that represents a different one of the suggested alternative text segments.

2. The computer-readable storage device of claim 1 wherein the user interface allows the user to add one or more nodes to the lattice, with each added node including one or more contiguous words, along with edges to connect the added nodes to one or more existing nodes in the lattice.

3. The computer-readable storage device of claim 1 wherein the user interface allows the user to edit the words in one or more nodes of the lattice.

4. The computer-readable storage device of claim 1 wherein the user interface allows the user to delete one or more nodes and corresponding edges from the lattice.

5. The computer-readable storage device of claim 1 wherein the user interface allows the user to add one or more edges between nodes of the lattice.

6. The computer-readable storage device of claim 1 wherein the user interface allows the user to delete one or more edges between nodes of the lattice.

7. The computer-readable storage device of claim 1 wherein the suggested alternative text segments are provided in a language style that differs from a language style of the input text segment.

8. The computer-readable storage device of claim 1 wherein the suggested alternative text segments are provided in a language different from a language of the input text segment.

9. The computer-readable storage device of claim 1 further comprising storing user path selection information with the corresponding alternative text segment in combination with the user input text segment for use in updating one or more of the contextual semantic similarity generation modules.

10. The computer-readable storage device of claim 1 further comprising using the alternative text segment corresponding to the user path selection as a new user text segment input for use in generating a new set of one or more suggested alternative text segments and constructing and displaying a new lattice-based representation of the new set of suggested alternative text segments.

11. The computer-readable storage device of claim 1 wherein at least a portion of the computer executable instructions are executed within a distributed computing environment.

12. The computer-readable storage device of claim 1 wherein the user interface is embedded within an application program to allow the user to modify text segments within that application by selecting a path through the displayed lattice via the user interface.

13. The computer-readable storage device of claim 1 further comprising instructions for translating the nodes and edges of the lattice into a structured query, and providing that structured query to a search engine for use in performing parallel searches for two or more of the different text segments of the set of suggested alternative text segments.

14. The computer-readable storage device of claim 1 further comprising instructions for receiving inputs from multiple users to enable crowdsourcing-based selection of a path through the lattice.

15. A system for implementing an interactive user interface for providing alternative suggested text segments to a user:

a device for receiving an input text segment comprising a sequence of two or more words and not including wildcards, said input text segment having a linguistic meaning;

a device for processing the input text segment to generate a plurality of suggested alternative text segments, each alternative text segment comprising a different sequence of words having a linguistic meaning similar to the linguistic meaning of the input text segment such that each alternative text segment is related to input text segment by linguistic context;

a device for constructing a lattice-based representation of the plurality of suggested alternative text segments as parallel text segments connected by the linguistic context, and wherein each of a plurality of nodes of the lattice includes one or more contiguous words of one of the alternative suggested text segments, and wherein edges of the lattice connect each node to one or more other nodes of the lattice such that each of the plurality of suggested alternative text segments are fully represented by the lattice;

a device for displaying the lattice in a user interface window; and

wherein the user interface further allows the user to select a path that traverses the lattice through a plurality of connected nodes from a beginning of the displayed lattice to an end of the displayed lattice, and wherein each possible path through the lattice corresponds to a sequence of nodes and edges that represents a different one of the suggested alternative text segments.

16. The system of claim 15 wherein the user interface is embedded within an application program to allow the user to modify text segments within that application by selecting a path through the displayed lattice via the user interface.

17. The system of claim 15 further comprising a device for translating the nodes and edges of the lattice into a structured query, and a device for providing that structured query to a search engine for use in performing parallel searches for two or more of the different text segments of the set of suggested alternative text segments.

18. A method for providing alternative suggested text segments to a user, comprising using a computing device for:

receiving an input text segment comprising a sequence of two or more words, said input text segment having a linguistic meaning;

processing the input text segment without the use of wildcards to generate a plurality of suggested alternative text segments, each alternative text segment comprising a different sequence of words having a linguistic meaning similar to the linguistic meaning of the input text segment such that each alternative is related to input text segment by linguistic context;

constructing a lattice-based representation of the plurality of suggested alternative text segments as parallel text segments connected by the linguistic context, and wherein each node of a plurality of nodes of the lattice includes one or more contiguous words of one of the alternative suggested text segments, and wherein edges of the lattice connect each node to one or more other nodes of the lattice such that each of the plurality of suggested alternative text segments are fully represented by the lattice;

displaying the lattice in a user interface window; and

selecting an alternative text segment by identifying a path that traverses the lattice through a plurality of connected nodes from a beginning of the displayed lattice to an end of the displayed lattice, and wherein each possible path through the lattice corresponds to a different one of the suggested alternative text segments.

19. The method of claim 18 further comprising receiving inputs from a plurality of users to enable crowdsourcing-based selection of a path through the lattice.

20. The method of claim 18 wherein the user interface is embedded within an application program to allow the user to modify text segments within that application by selecting a path through the displayed lattice via the user interface.