System and method for rectifying a typographical error in a text file

• US 9,734,234 B2
• Filed: 10/10/2014
• Issued: 08/15/2017
• Est. Priority Date: 03/07/2014
• Status: Active Grant

• Current Assignee: TATA Consultancy Services Limited (Tata Sons Pvt Ltd.)
• Original Assignee: TATA Consultancy Services Limited (Tata Sons Pvt Ltd.)
• Inventors: Patil, Sangameshwar Suryakant
• Primary Examiner(s): Hill, Stanley K
• Assistant Examiner(s): Lee, Tsu-Chang
• Application Number:
  US14/512,049
• Publication Number:
  US 20150254327A1
• Time in Patent Office: 1,040 Days
• CPC Class Codes: G06F 16/13 File access structures, e.g. distributed indices arrangements of input from, or output to, record carriers G06F3/06
• CPC Class Codes: G06F 16/24578 using ranking
• CPC Class Codes: G06F 16/285 Clustering or classification
• CPC Class Codes: G06F 16/3335 Syntactic pre-processing, e.g. stopword elimination, stemming
• CPC Class Codes: G06F 16/355 Class or cluster creation or modification
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence
• CPC Class Codes: G06F 40/232 Orthographic correction, e.g. spell checking or vowelisation
• CPC Class Codes: G06F 40/30 Semantic analysis

Abstract

Disclosed is a system for rectifying a typographical error in a text file. The system includes a network generating module for generating a linguistic network of a plurality of words present in the text file. A computation module configured to compute the similarity between each pair of words based on a set of parameters. A weight assignment module for assigning a weight to the edge present between the each pair of words based the set of parameters. A categorization module configured to categorize one or more words present in the linguistic network in a category. A word identification module configured to identify a reference word from the category. A word substitution module configured to substitute each word of the category deemed as erroneous with corresponding reference word for rectifying the typographical error.

Claims

1. A method for rectifying a typographical error in a text file, the method comprising:

generating a linguistic network of a plurality of words present in the text file, wherein each pair of words of the plurality of words in the linguistic network is interconnected via an edge;

computing similarity between each pair of words based on a set of parameters associated with words of each pair, wherein the set of parameters comprises distance between the words, phonetic similarity between the words, consonant skeleton distance, presence of the words in lexicon, morphological root form of the words, frequency of the words in the text file, probability of occurrence of the words in the context, domain similarity of the words, and a flag associated to similar starting character of the words;

assigning a weight to the edge between the each pair of words based on the similarity computed from the set of parameters;

categorizing one or more words present in the linguistic network in a category, wherein the one or more words are categorized based on the weight assigned to each edge connecting the each pair of words of the one or more words;

identifying a reference word for each word which is deemed to have the typographical error from the category; and

substituting each word of the category, having the typographical error, with the reference word corresponding to the word having typographical error in the text file for rectifying the typographical error, wherein the generating, the computing, the assigning, the categorizing, the identifying and the substituting are performed by a processor using programmed instructions stored in a memory.

2. The method of claim 1, wherein computing the distance comprises:

transforming a first word to a second word of the each pair of words by inserting, deleting, substituting, transpositioning characters present in the first word.

3. The method of claim 1, wherein the phonetic similarity is computed by at least one of a metaphone algorithm, a double metaphone algorithm, a Metaphone 3, a Daitch-Mokotoff and a Soundex, Caverphone.

4. The method of claim 1, wherein the categorizing comprising running a community detection algorithm on the weight assigned to the edge connecting one or more pairs of words of the one or more words and wherein the community detection algorithm may be selected from a group comprising a minimum-cut method, a hierarchical clustering, a Girvan-Newman algorithm, a modularity maximization, and a clique based methods.

5. The method of claim 1, wherein the identification of the reference word is based on the set of parameters, and wherein the identifying further comprises:

comparing each word of the category with a lexicon vocabulary to verify at least one word of the category is present in the lexicon vocabulary, wherein the at least one word is assigned a flag, and wherein the flag associated to the at least one word is indicated as the reference word;

or

selecting the reference word from the lexicon database by computing the at least one of the distance and the phonetic similarity between each word of the category and the lexicon vocabulary, wherein the reference word is selected when the at least one word of the category is not present in the lexicon database;

or

determining a number of instances associated to each word of the category in the text file, wherein the number of instances is determined to select the reference word having highest number of instances in the text file and wherein the number of instances is determined when the reference word is not selected based on the computing.

6. The method of claim 5, wherein the lexicon vocabulary is stored in a lexicon database.

7. The method of claim 1 further comprising executing a graph sparsification technique on the linguistic network after assigning the weight to the edge present between the each pair of words in the linguistic network, wherein the graph sparsification technique facilitates in simplifying the linguistic network by eliminating one or more edges of the linguistic network having the weight 0 or less than a pre-defined threshold value.

8. A system for rectifying a typographical error in a text file, the system comprising:

a processor; and

a memory coupled to the processor, wherein the processor is capable of executing a plurality of modules stored in the memory, and wherein the plurality of module comprising;

a network generating module configured to generate a linguistic network of a plurality of words present in the text file, wherein each pair of words of the plurality of words in the linguistic network is interconnected via an edge;

a computation module coupled to the network generating module, the computation module configured to compute similarity between the each pair of words based on a set of parameters associated with words of each pair, wherein the set of parameters comprises distance between the words, phonetic similarity between the words, consonant skeleton distance, presence of the words in lexicon, morphological root form of the words, frequency of the words in the text file, probability of occurrence of the words in the context, domain similarity of the words, and a flag associated to similar starting character of the words;

a weight assignment module configured to assign a weight to the edge between the each pair of words based on the similarity computed from the set of parameters;

a categorization module configured to categorize one or more words present in the linguistic network in a category, wherein the one or more words are categorized based on the weight assigned to each edge connecting the each pair of words of the one or more words;

a word identification module configured to identify a reference word for each word which is deemed to have the typographical error from the category; and

a word substitution module configured to substitute each word of the category, having the typographical error, with the corresponding reference word in the text file for rectifying the typographical error.

9. The system of claim 8, wherein the computation module is further configured to compute the distance by transforming a first word to a second word of the each pair of words by inserting, deleting, substituting, transpositioning characters present in the first word.

10. The system of claim 8, wherein the computation module is further configured to compute the phonetic similarity by at least one of a metaphone algorithm, a double metaphone algorithm, a Metaphone 3, a Daitch-Mokotoff Soundex, and a Caverphone.

11. The system of claim 8, wherein the word identification module is further configured to:

compare each word of the category with a lexicon vocabulary to verify at least one word of the category is present in the lexicon vocabulary, wherein the at least one word is assigned a flag, and wherein the flag associated to the at least one word is indicated as the reference word;

or

select the reference word from the lexicon database by computing the at least one of the distance and the phonetic similarity between each word of the category and the lexicon vocabulary, wherein the reference word is selected when the at least one word of the category is not present in the lexicon database;

or

determine a number of instances associated to each word of the category in the text file, wherein the number of instances is determined to select the reference word having highest number of instances in the text file and wherein the number of instances is determined when the reference word is not selected based on the computing.

12. The system of claim 11, wherein the lexicon vocabulary is stored in a lexicon database.

13. A non-transitory computer readable medium having embodied thereon a computer program for rectifying a typographical error in a text file, the computer program comprising instructions for:

generating a linguistic network of a plurality of words present in the text file, wherein each pair of words of the plurality of words in the linguistic network is interconnected via an edge;

computing similarity between the each pair of words based on a set of parameters associated with words of each pair, wherein the set of parameters comprises distance between the words, phonetic similarity between the words, consonant skeleton distance, presence of the words in lexicon, morphological root form of the words, frequency of the words in the text file, probability of occurrence of the words in the context, domain similarity of the words, and a flag associated to similar starting character of the words;

assigning a weight to the edge between the each pair of words based on the similarity computed from the set of parameters;

categorizing one or more words present in the linguistic network in a category, wherein the one or more words are categorized based on the weight assigned to each edge connecting the each pair of words of the one or more words;

identifying a reference word for each word which is deemed to have the typographical error from the category; and

substituting each word of the category, having the typographical error, with the corresponding reference word in the text file for rectifying the typographical error.