Methods and apparatus related to automatically rewriting strings of text

• US 9,864,738 B2
• Filed: 01/07/2015
• Issued: 01/09/2018
• Est. Priority Date: 09/02/2014
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google LLC (Alphabet Inc.)
• Inventors: Mengle, Advay, Patterson, Anna, Dogrultan, Ertan, Davidson, James Christopher
• Primary Examiner(s): Cordero, Marivelisse Santiago
• Assistant Examiner(s): Brinich, Stephen
• Application Number:
  US14/591,700
• Publication Number:
  US 20160062969A1
• Time in Patent Office: 1,098 Days
• Field of Search: 704 1- 10, 704235, 704257, 704254
• CPC Class Codes: G06F 40/169 Annotation, e.g. comment data or footnotes
• CPC Class Codes: G06F 40/221 Parsing markup language streams streaming G06F40/149
• CPC Class Codes: G06F 40/253 Grammatical analysis; Style critique
• CPC Class Codes: G06F 40/30 Semantic analysis
• CPC Class Codes: G06Q 30/0241 Advertisements

Abstract

Methods and apparatus related to automatically rewriting a string of text utilizing one or more rewrite rules. Some implementations are directed to scoring rewrite rules based at least in part on user interactions with rewrites that are generated by applying the rewrite rules. Some implementations are directed to determining the effectiveness of a rewrite generated based on applying one or more rewrite rules to a string of text. In some of those implementations, the determination may be based at least in part on one or more characteristics of the string of text, one or more characteristics of the rewrite, and/or scores associated with the rewrite rules.

Claims

1. A computer-implemented method, comprising:

identifying a string of text from a first electronic resource, wherein the string includes one or more tokens;

identifying one or more rewrite rules;

identifying a set of the rewrite rules for the string;

generating a rewrite of the string based on the tokens and the set of the rewrite rules;

providing, via one or more networks, the rewrite to computing devices, the rewrite being provided to the computing devices for presentation, via applications executing on the computing devices, of the rewrite to users of the computing devices, and the rewrite being provided for potential interaction, by the users via the applications, with content associated with the rewrite;

identifying one or more interactions with the rewrite, of the string from the first electronic resource, in response to the providing,

wherein each of the interactions indicates user interest in the content associated with the rewrite, and wherein each of the interactions are identified in response to corresponding user interface input provided via a corresponding one of the applications;

scoring the set of the rewrite rules based on the one or more interactions with the rewrite of the string from the first electronic resource;

after the scoring of the set of the rewrite rules, identifying an additional string of text from an additional electronic resource;

based on the scoring of the set of the rewrite rules, that is based on the one or more interactions with the rewrite of the string from the first electronic resource, selecting the set of the rewrite rules for generating an additional string rewrite of the additional string that is from the additional electronic resource, the selecting comprising selecting the set of the rewrite rules in lieu of other sets of the rewrite rules;

generating the additional string rewrite of the additional string, that is from the additional electronic resource, based on the set of the rewrite rules; and

providing the additional string rewrite to one or more additional computing devices for presentation of the additional string rewrite to additional users of the additional computing devices.

2. The method of claim 1, further comprising:

identifying a second set of the rewrite rules for the string;

generating a second rewrite of the string based on the tokens and the second set of the rewrite rules;

identifying one or more second interactions with the second rewrite in response to providing the second rewrite for potential interaction with content associated with the second rewrite, wherein each of the second interactions indicates user interest in the content associated with the second rewrite; and

scoring the second set of the rewrite rules based on the one or more second interactions.

3. The method of claim 2, wherein the second set of the rewrite rules includes the rewrite rules of the set of rewrite rules and at least one additional rewrite rule of the rewrite rules.

4. The method of claim 1, further comprising:

determining one or more string characteristics for the string;

wherein scoring the set of the rewrite rules based on the one or more interactions comprises scoring the set of rewrite rules for the one or more string characteristics.

5. The method of claim 1, further comprising:

identifying interactions with the string, wherein each of the interactions with the string indicates user interest in content associated with the string, wherein scoring the set of the rewrite rules is further based on the interactions with the string.

6. The method of claim 1, further comprising:

identifying a second string of text from a second electronic resource, wherein the second string includes one or more second string tokens;

generating a second rewrite of the second string based on the tokens and the set of the rewrite rules;

identifying one or more second interactions with the second rewrite in response to providing the second rewrite for potential computer-based interaction with content associated with the second rewrite, wherein each of the second interactions indicates user interest in the content associated with the second rewrite; and

wherein scoring the set of rewrite rules is further based on the one or more second string interactions.

7. The method of claim 1, wherein scoring the set of the rewrite rules based on the one or more interactions comprises scoring the set of rewrite rules based on comparison of a quantity of the one or more interactions to a quantity of non-interactions of users with the rewrite in response to the providing, wherein each of the non-interactions indicates lack of user interest in the content associated with the rewrite.

8. The method of claim 1, wherein identifying the set of the rewrite rules comprises:

selecting the rewrite rules for inclusion in the set based on the rewrite rules preserving sentiment between the string and the rewrite.

9. The method of claim 1, wherein identifying the set of the rewrite rules comprises:

selecting the rewrite rules for inclusion in the set based on the rewrite rules minimizing information loss between the string and the rewrite.

10. The method of claim 1, wherein identifying the set of the rewrite rules comprises:

selecting the rewrite rules for inclusion in the set based on the rewrite rules minimizing the length of the rewrite.

11. The method of claim 1, wherein identifying the set of the rewrite rules includes identifying an order of application of the one or more rewrite rules for the set.

12. The method of claim 11, wherein the set of the rewrite rules includes a first rewrite rule of the rewrite rules and a second rewrite rule of the rewrite rules, wherein the order of application indicates application of the first rewrite rule before application of the second rewrite rule, and wherein generating the rewrite includes:

generating an intermediate rewrite of the string based on the tokens and the first rewrite rule; and

generating the rewrite of the string based on the intermediate rewrite of the string and the second rewrite rule.

13. The method of claim 1, wherein at least one of the rewrite rules of the set rearranges two or more of the tokens of the string.

14. The method of claim 1, wherein generating the rewrite of the string based on the tokens and the set of the rewrite rules includes:

identifying a set of the tokens that belong to a subtree of the string; and

wherein generating the rewrite is based on the subtree and the set of rewrite rules.

15. The method of claim 1, wherein generating the rewrite includes:

generating an intermediate rewrite of the string based on a given rewrite rule of the rewrite rules; and

generating the rewrite of the string based on the intermediate rewrite of the string and a second application of the given rewrite rule.

16. The method of claim 1, further comprising:

determining one or more string characteristics for the string;

wherein scoring the set of the rewrite rules based on the one or more interactions comprises scoring the set of the rewrite rules for the one or more string characteristics; and

wherein selecting the set of the rewrite rules for generating the second string rewrite of the rewrite rules is further based on the scoring being for the one or more string characteristics and the second string having the one or more string characteristics.

17. The method of claim 16, wherein the string characteristics include a use characteristic, the use characteristic being one of an anchor text use and an advertisement use.

18. A computer-implemented method, comprising:

generating a first score for a first set of rewrite rules, generating the first score comprising;

rewriting multiple first strings of text based on the first set of rewrite rules,

transmitting the rewrites of the multiple first strings of text over one or more networks,

and generating the score based on user interactions with the transmitted rewrites of the multiple first strings of text;

generating a second score for a second set of rewrite rules, generating the second score comprising;

rewriting multiple second strings of text based on the second set of rewrite rules,

transmitting the rewrites of the multiple second strings of text over one or more of the networks,

and generating the second score based on second user interactions with the transmitted rewrites of the multiple second strings of text;

identifying a future string of text from a given electronic resource, the given electronic resource being in addition to electronic resources that include the multiple first strings of text and the multiple second strings of text;

selecting, for the future string of text from the given electronic resource, the first set of rewrite rules and the second set of rewrite rules based on;

the first score for the first set of rewrite rules that is based on the first user interactions with the transmitted rewrites of the multiple first strings of text, and

the second score for the set of rewrite rules that is based on the second user interactions with the transmitted rewrites of the multiple second strings of text,

wherein the selecting comprises selecting the first set of rewrite rules and the second set of rewrite rules in lieu of other sets of the rewrite rules;

generating one or more first rewrites of the future string of text based on the first set of rewrite rules and the future string of text;

generating one or more second rewrites of the future string of text based on the second set of rewrite rules and the future string of text;

determining effectiveness scores for each of the first rewrites and the second rewrites based on one or more objective functions;

selecting a subset of the first and second rewrites based on the effectiveness scores; and

providing the subset to one or more computing devices.

19. The method of claim 18, wherein the first set of rewrite rules includes at least a first rewrite rule and a second rewrite rule, and wherein generating the first rewrites comprises:

generating an intermediate rewrite by applying first rewrite rule; and

generating a final rewrite of the first rewrites based on applying the second rewrite rule to the intermediate rewrite.

20. The method of claim 18, wherein first set of rewrite rules includes at least a first rewrite rule and the second set of rewrite rules includes the first set of rewrite rules and at least one additional rewrite rule, and wherein generating the one or more second rewrites is based on the one or more first rewrites.

21. The method of claim 20, wherein selecting the subset includes selecting one or more of the first rewrite rules if none of the effectiveness scores of the second set of rewrites satisfies a threshold value.

22. The method of claim 18, wherein determining the effectiveness scores for each of the first rewrites and the second rewrites based on one or more objective functions comprises:

determining the effectiveness scores for each of the first rewrites based in part on one or more scores associated with the first set of rewrite rules; and

determining the effectiveness scores for each of the second rewrites based in part on one or more scores associated with the second set of rewrite rules.

23. The method of claim 18, wherein the second set of rewrite rules includes the rewrite rules of the first set of rewrite rules and one or more additional rewrite rules.

24. The method of claim 18, wherein the first set of the rewrite rules and the second set of the rewrite rules include a first rewrite rule and a second rewrite rule;

wherein the order of application of the first set of rewrite rules indicates application of the first rewrite rule before application of the second rewrite rule, and wherein the order of application of the second set of rewrite rules indicates application of the second rewrite rule before the first rewrite rule.

25. A system, comprising:

memory storing instructions;

one or more processors operable to execute the instructions in the memory, wherein the instructions comprise instructions to;

identify a string of text from a first electronic resource, wherein the string includes one or more tokens;

identify one or more rewrite rules;

identify a set of the rewrite rules for the string;

generate a rewrite of the string based on the tokens and the set of the rewrite rules;

provide, via one or more networks, the rewrite to computing devices, the rewrite being provided to the computing devices for presentation, via applications executing on the computing devices, of the rewrite to users of the computing devices, and the rewrite being provided for potential interaction, by the users via the applications, with content associated with the rewrite;

identify one or more interactions with the rewrite, of the string from the first electronic resource, in response to the providing,

wherein each of the interactions indicates user interest in the content associated with the rewrite, and wherein each of the interactions are identified in response to corresponding user interface input provided via a corresponding one of the applications;

score the set of the rewrite rules based on the one or more interactions with the rewrite of the string from the first electronic resource;

after the scoring of the set of the rewrite rules, identify an additional string of text from an additional electronic resource;

based on the scoring of the set of the rewrite rules, that is based on the one or more interactions with the rewrite of the string from the first electronic resource, select the set of the rewrite rules for generating an additional string rewrite of the additional string that is from the additional electronic resource, the selecting comprising selecting the set of the rewrite rules in lieu of other sets of the rewrite rules;

generate the additional string rewrite of the additional string, that is from the additional electronic resource, based on the set of the rewrite rules; and

provide the additional string rewrite to one or more additional computing devices for presentation of the additional string rewrite to additional users of the additional computing devices.