OPTIMALLY SORTING A LIST OF ELEMENTS BASED ON THEIR SINGLETONS

• US 20130166281A1
• Filed: 10/08/2012
• Published: 06/27/2013
• Est. Priority Date: 12/22/2011
• Status: Active Grant

• Current Assignee: Continental Automotive Systems, Inc. (Continental AG)
• Original Assignee: Continental Automotive Systems, Inc. (Continental AG)
• Inventors: Lamy, Guillaume
• Granted Patent: US 9,086,863 B2
• Time in Patent Office: Days
• US Class Current: 704/9
• CPC Class Codes: G06F 7/24 Sorting, i.e. extracting data from one or more carriers, rearranging the data in numerical or other ordered sequence, and rerecording the sorted data on the original carrier or on a different carrier or set of carriers sorting methods in generalG06F7/36 takes precedence
• CPC Class Codes: G10L 15/06 Creation of reference templates; Training of speech recognition systems, e.g. adaptation to the characteristics of the speaker's voice G10L15/14 takes precedence
• CPC Class Codes: G10L 15/065 Adaptation
• CPC Class Codes: G10L 15/075 supervised, i.e. under machine guidance
• CPC Class Codes: G10L 2015/0633 using lexical or orthographic knowledge sources

Abstract

A method provides a non-optimized list of elements, with some of the elements having multiple terms. A table of sub-elements is generated from the elements list, with each sub-element having one term only and with a number of times a sub-element appears in the elements list being weighted in the sub-elements table. A weighted singleton histogram table is generated using a singleton dictionary, and a total popularity score of each singleton is computed from the sub-elements table. For each element from the elements list, an elements score is generated based on the total popularity score of each singleton within the element. An optimally sorted list of the elements list is generated based on the elements scores.

Claims

1. A method for sorting a list of elements, the method comprising:

providing a non-optimized list of elements, with some of the elements having multiple terms,

generating, by a processor circuit, a table of sub-elements from the elements list, with each sub-element having one term only and with a number of times a sub-element appears in the elements list being weighted in the sub-elements table,

generating, by the processor circuit, a weighted singleton histogram table using a singleton dictionary, and computing a total popularity score of each singleton from the sub-elements table,

for each element from the elements list, generating by the processor circuit, an elements score based on the total popularity score of each singleton within the element, and

generating, by the processor circuit, an optimally sorted list of the elements list based on the elements scores.

2. The method of claim 1, wherein the step of generating the weighted singleton histogram includes:

ordering the singletons from a largest total characters to a smallest total characters of the singletons.

3. The method of claim 2, wherein, in the step of computing the total popularity score of each singleton, the popularity of a small character singleton does not increase if it is part of a larger character singleton.

4. The method of claim 3, wherein, in the step of computing the total popularity score of each singleton, a popularity score of each singleton is equal to its number of repetition within a sub-element of the sub-element table multiplied by the weight of the associated sub-element of the sub-elements table, with the total popularity score being computed by adding up the popularity scores from all of the sub-elements in the sub-elements table.

5. The method of claim 1, wherein the step of generating the optimized list further includes performing the following steps in sequence until all elements have been sorted:

a) computing, by the processor circuit, for each element of the elements list, an added singleton coverage increase so that the higher number of singleton the element contains, the higher the coverage increase,

b) regardless of the elements score, placing, by the processor circuit, the element with the highest coverage at a bottom of a sorted list,

c) repeating steps a) and b) until singleton coverage cannot be increased anymore,

d) removing ordered elements from the elements list, and

e) repeating step a) until the elements list is fully depleted.

6. The method of claim 5, wherein in the placing step, if several elements have the same coverage increase, the method includes placing the element with highest total popularity score at the bottom of the sorted list.

7. Logic encoded in one or more non-transitory tangible media for execution and when executed operable for:

providing a non-optimized list of elements, with some of the elements having multiple terms,

generating, by a processor circuit, a table of sub-elements from the elements list, with each sub-element having one term only and with a number of times a sub-element appears in the elements list being weighted in the sub-elements table,

generating, by the processor circuit, a weighted singleton histogram table using a singleton dictionary, and computing a total popularity score of each singleton from the sub-elements table,

for each element from the elements list, generating by the processor circuit, an elements score based on the total popularity score of each singleton within the element, and generating, by the processor circuit, an optimally sorted list of the elements list based on the elements scores.

8. The encoded logic of claim 7, wherein the step of generating the weighted singleton histogram includes:

ordering the singletons from a largest total characters to a smallest total characters of the singletons.

9. The encoded logic of claim 8, wherein, in the step of computing the total popularity score of each singleton, the popularity of a small character singleton does not increase if it is part of a larger character singleton.

10. The encoded logic of claim 9, wherein, in the step of computing the total popularity score of each singleton, a popularity score of each singleton is equal to its number of repetition within a sub-element of the sub-element table multiplied by the weight of the associated sub-element of the sub-elements table, with the total popularity score being computed by adding up the popularity scores from all of the sub-elements in the sub-elements table.

11. The encoded logic of claim 7, wherein the step of generating the optimized list further includes performing the following steps in sequence until all elements have been sorted:

a) computing, by the processor circuit, for each element of the elements list, an added singleton coverage increase so that the higher number of singleton the element contains, the higher the coverage increase,

b) regardless of the elements score, placing, by the processor circuit, the element with the highest coverage at a bottom of a sorted list,

c) repeating steps a) and b) until singleton coverage cannot be increased anymore,

d) removing ordered elements from the elements list, and

e) repeating step a) until the elements list is fully depleted.

12. The encoded logic of claim 11, wherein in the placing step, if several elements have the same coverage increase, the element with highest total popularity score is placed at the bottom of the sorted list.

13. An apparatus for sorting a list of elements, the apparatus comprising:

a processor circuit configured for generating a table of sub-elements from an elements list, with each sub-element having one term only and with a number of times a sub-element appears in the elements list being weighted in the sub-elements table,

the processor circuit configured for generating a weighted singleton histogram table using a singleton dictionary, and computing a total popularity score of each singleton from the sub-elements table,

the processor circuit configured for generating for each element from the elements list, an elements score based on the total popularity score of each singleton within the element,

the processor circuit configured for generating an optimally sorted list of the elements list based on the elements scores, and

a memory circuit configured for storing the table of sub-elements, the weighted singleton histogram, the elements scores, and the optimally sorted list.

14. The apparatus of claim 13, wherein the processor circuit is configured, during the generation of the weighted singleton histogram, for ordering the singletons from a largest total characters to a smallest total characters of the singletons.

15. The apparatus of claim 14, wherein, in computing the total popularity score of each singleton, the processor circuit is configured to ensure that the popularity of a small character singleton does not increase if it is part of a larger character singleton.

16. The apparatus of claim 15, wherein, in computing the total popularity score of each singleton, the processor circuit is configured to ensure that a popularity score of each singleton is equal to its number of repetition within a sub-element of the sub-element table multiplied by the weight of the associated sub-element of the sub-elements table, with the total popularity score being computed by adding up the popularity scores from all of the sub-elements in the sub-elements table.

17. The apparatus of claim 13, wherein in generating the optimized list the processor circuit is configured, until all elements have been sorted, for:

a) computing for each element of the elements list, an added singleton coverage increase so that the higher number of singleton the element contains, the higher the coverage increase,

b) regardless of the elements score, placing the element with the highest coverage at a bottom of a sorted list,

c) repeating steps a) and b) until singleton coverage cannot be increased anymore,

d) removing ordered elements from the elements list, and

e) repeating step a) until the elements list is fully depleted.

18. The apparatus of claim 13, wherein in the placing step, if several elements have the same coverage increase, the processor circuit is configured for placing the element with highest total popularity score at the bottom of the sorted list.