Font substitution using unsupervised clustering techniques

• US 8,910,041 B1
• Filed: 02/23/2012
• Issued: 12/09/2014
• Est. Priority Date: 02/23/2012
• Status: Expired due to Fees

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Buryak, Kirill, Shah, Vinay, Gill, Stuart George
• Primary Examiner(s): Debrow, James J
• Application Number:
  US13/403,607
• Time in Patent Office: 1,020 Days
• Field of Search: 715/269
• US Class Current: 715/269
• CPC Class Codes: G06F 40/109 Font handling; Temporal or kinetic typography

Abstract

Methods, systems, and apparatuses for determining a font substitution hierarchy using unsupervised clustering techniques are provided. A font substitution hierarchy may be determined by identifying a plurality of font request files associated with web-based application documents. Determining an association between a plurality of font requests within the plurality of font request files based on a clustering analysis, and determining a font substitution hierarchy for an individual font request based on the association.

Claims

1. A method for determining a font substitution hierarchy, the method comprising:

identifying a plurality of font request files associated with web-based application documents;

generating n-gram strings of hierarchically ordered font request subsequences for a plurality of font requests within the plurality of font request files;

determining a parameter associated with a secondary attribute of the plurality of font requests based on a frequency of instances where two or more font requests appear in sequence in the plurality of font request files;

determining an association between the plurality of font requests based on a clustering analysis and the parameter, wherein the clustering analysis is based at least in part on one or more of the n-gram strings; and

determining a font substitution hierarchy for an individual font request based on the association between the plurality of font requests based on the clustering analysis and the parameter.

2. The method of claim 1, wherein the clustering analysis comprises generating a plurality of font substitution strings based on the one or more n-grams.

3. The method of claim 2, wherein the font substitution strings are based on a hierarchical ordering of font requests of the one or more n-grams.

4. The method of claim 1, wherein the clustering analysis comprises executing one of a hierarchical agglomerative clustering, k-means clustering or distributed exchange algorithm.

5. The method of claim 1, wherein the secondary attribute is one of a stylistic, contextual or frequency attribute.

6. The method of claim 5, further comprising determining a bias for one or more parameters associated with the frequency attribute based on a commonality between the plurality of font request files.

7. A non-transitory computer-readable medium having program instructions stored thereon, the instructions capable of execution by a processor and defining the steps of:

identifying a plurality of font request files associated with web-based application documents;

generating n-gram strings of hierarchically ordered font request subsequences for a plurality of font requests within the plurality of font request files;

determining a parameter associated with a secondary attribute of the plurality of font requests based on a frequency of instances where two or more font requests appear in sequence in the plurality of font request files;

determining an association between the plurality of font requests based on a clustering analysis and the parameter, wherein the clustering analysis is based at least in part on one or more of the n-gram strings; and

determining a font substitution hierarchy an individual font request based on the association between the plurality of font requests based on the clustering analysis and the parameter.

8. The non-transitory computer-readable medium of claim 7, wherein the clustering analysis comprises generating a plurality of font substitution strings based on the one or more n-grams.

9. The non-transitory computer-readable medium of claim 8, wherein the font substitution strings are based on a hierarchical ordering of font requests of the one or more n-grams.

10. The non-transitory computer-readable medium of claim 7, wherein the clustering analysis comprises executing one of a hierarchical agglomerative clustering, k-means clustering or distributed exchange algorithm.

11. The non-transitory computer-readable medium of claim 7, wherein the secondary attribute is one of a stylistic, contextual or frequency attribute.

12. The non-transitory computer-readable medium of claim 11, further comprising instructions defining the step of:

determining a bias for one or more parameters associated with the frequency attribute based on a commonality between the plurality of font request files.

13. A method, comprising:

receiving a request for an application document;

retrieving the application document, wherein the application document includes a font request;

determining that a primary font specified in the font request cannot be displayed;

selecting a font substitution hierarchy for the primary font, wherein the font substitution hierarchy is determined by;

identifying a plurality of font request files associated with web-based application documents;

generating n-gram strings of hierarchically ordered font request subsequences for a plurality of font requests within the plurality of font request files;

determining a parameter associated with a secondary attribute of the plurality of font requests based on a frequency of instances where two or more font requests appear in sequence in the plurality of font request files;

determining an association between the plurality of font requests based on a clustering analysis and the parameter, wherein the clustering analysis is based at least in part on one or more of the n-gram strings; and

determining the font substitution hierarchy based on the association between the plurality of font requests based on the clustering analysis and the parameter; and

substituting the primary font with a font that can be displayed based on the font substitution hierarchy.

14. An apparatus, comprising:

means for receiving a request for an application document;

means for retrieving the application document, wherein the application document includes a font request;

means for determining that a primary font specified in the font request cannot be displayed;

means for selecting a font substitution hierarchy for the primary font, wherein the means for selecting comprises;

means for identifying a plurality of font request files associated with web-based application documents;

means for generating n-gram strings of hierarchically ordered font request subsequences for a plurality of font requests within the plurality of font request files;

means for determining a parameter associated with a secondary attribute of the plurality of font requests based on a frequency of instances where two or more font requests appear in sequence in the plurality of font request files;

means for determining an association between the plurality of font requests based on a clustering analysis and the parameter, wherein the clustering analysis is based at least in part on one or more of the n-gram strings; and

means for determining the font substitution hierarchy based on the association between the plurality of font requests based on the clustering analysis and the parameter; and

means for substituting the primary font with a font that can be displayed based on the font substitution hierarchy.