Claims:WE CLAIM:
1. A method for n-gram identification and extraction, the method comprising:
identifying, by a computing device, at least one n-gram from a sentence inputted by a user based on a confidence score associated with each of the at least one n-gram, wherein a confidence score for an n-gram is computed based on comparison of the n-gram with existing word patterns;
determining, by the computing device, a direction context entropy coefficient for each of the at least one n-gram, based on the existing word patterns;
iteratively expanding, by the computing device, one or more of the at least one n-gram by the smallest n-gram unit at each iteration in a predefined direction in the sentence to generate at least one expanded n-gram, based on an associated direction context entropy coefficient;
extracting at each expanding iteration, by the computing device, one or more of the at least one expanded n-gram based on a confidence score associated with each of the one or more of the at least one expanded n-gram, wherein a confidence score for an expanded n-gram is computed based on comparison of the expanded n-gram with the existing word patterns; and
grouping, by the computing device, semantically linked n-grams from the one or more of the at least one expanded n-gram.
2. The method of claim 1, further comprising removing one or more n-grams from the at least one n-gram, wherein the one or more n-grams cannot be expanded by the smallest n-gram unit based on the associated direction context entropy coefficient.
3. The method of claim 1, wherein the predefined direction comprises one of left direction and right direction in the sentence with respect to an n-gram from the at least one n-gram.
4. The method of claim 1, wherein the smallest n-gram unit is a unigram, and wherein an n-gram is expanded by a unigram in the predefined direction in each iteration to generate an (n+1)-gram.
5. The method of claim 1, wherein the confidence score for an n-gram is computed based on association coefficient computed for degree of association of an n-gram relative to at least one adjacent word when compared with the existing word patterns.
6. The method of claim 1, wherein the direction context entropy coefficient for an n-gram comprises at least one of a left context entropy coefficient and a right context entropy coefficient,
wherein the n-gram is expanded in the left direction in the sentence, when the left context entropy coefficient for the n-gram is higher than an associated predefined context threshold, and
wherein the n-gram is expanded in the right direction in the sentence, when the right context entropy coefficient for the n-gram is higher than an associated predefined context threshold.
7. The method of claim 1, further comprising validating expansion of an n-gram in the predefined direction based on at least one of a cross context entropy coefficient and a reverse cross context entropy coefficient.
8. The method of claim 1, further comprising filtering one or more of the at least one n-gram and one or more of the at least one expanded n-gram based on associated at least one context divergence coefficient.
9. The method of claim 8, wherein each of one or more filtered n-grams comprise low relevancy confidence score determined based on the associated at least one context divergence coefficient.
10. The method of claim 1, further comprising limiting the number of expanding iterations based on a predefined iteration threshold.
11. A computing device for n-gram identification and extraction, the computing device comprises:
a processor; and
a memory communicatively coupled to the processor, wherein the memory stores processor instructions, which, on execution, causes the processor to:
identify at least one n-gram from a sentence inputted by a user based on a confidence score associated with each of the at least one n-gram, wherein a confidence score for an n-gram is computed based on comparison of the n-gram with existing word patterns;
determine a direction context entropy coefficient for each of the at least one n-gram, based on the existing word patterns;
iteratively expand one or more of the at least one n-gram by the smallest n-gram unit at each iteration in a predefined direction in the sentence to generate at least one expanded n-gram, based on an associated direction context entropy coefficient;
extract at each expanding iteration one or more of the at least one expanded n-gram based on a confidence score associated with each of the one or more of the at least one expanded n-gram, wherein a confidence score for an expanded n-gram is computed based on comparison of the expanded n-gram with the existing word patterns; and
group semantically linked n-grams from the one or more of the at least one expanded n-gram.
12. The computing device of claim 11, wherein the processor instructions further cause the processor to remove one or more n-grams from the at least one n-gram, wherein the one or more n-grams cannot be expanded by the smallest n-gram unit based on the associated direction context entropy coefficient.
13. The computing device of claim 11, wherein the predefined direction comprises one of left direction and right direction in the sentence with respect to an n-gram from the at least one n-gram.
14. The computing device of claim 11, wherein the confidence score for an n-gram is computed based on association coefficient computed for degree of association of an n-gram relative to at least one adjacent word when compared with the existing word patterns.
15. The computing device of claim 1, wherein the direction context entropy coefficient for an n-gram comprises at least one of a left context entropy coefficient and a right context entropy coefficient,
wherein the n-gram is expanded in the left direction in the sentence, when the left context entropy coefficient for the n-gram is higher than an associated predefined context threshold, and
wherein the n-gram is expanded in the right direction in the sentence, when the right context entropy coefficient for the n-gram is higher than an associated predefined context threshold.
16. The computing device of claim 11, wherein the processor instructions further cause the processor to validate expansion of an n-gram in the predefined direction based on at least one of a cross context entropy coefficient and a reverse cross context entropy coefficient.
17. The computing device of claim 11, wherein the processor instructions further cause the processor to filter one or more of the at least one n-gram and one or more of the at least one expanded n-gram based on associated at least one context divergence coefficient.
18. The computing device of claim 17, wherein each of one or more filtered n-grams comprise low relevancy confidence score determined based on the associated at least one context divergence coefficient.
19. The computing device of claim 11, wherein the processor instructions further cause the processor to limit the number of expanding iterations based on a predefined iteration threshold.

Dated this 20th day of March, 2018

Swetha SN
Of K&S Partners
Agent for the Applicant
IN/PA-2123
, Description:TECHNICAL FIELD
This disclosure relates generally to n-grams and more particularly to method and device for n-gram identification and extraction.