Translating source locale input string to target locale output string

• US 8,296,125 B2
• Filed: 10/17/2008
• Issued: 10/23/2012
• Est. Priority Date: 10/17/2008
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Shetty, Rohit, Ramakrishnan, Arun, Dravid, Saurabh, Shastry, Krishna
• Primary Examiner(s): Colucci, Michael
• Application Number:
  US12/253,300
• Publication Number:
  US 20100100369A1
• Time in Patent Office: 1,467 Days
• Field of Search: 704/2, 704/6, 704/9, 704/5, 704/3, 704/4, 704/7, 704/8, 704/273, 704/277, 706/50, 706/55, 707/737, 715/259
• US Class Current: 704/4
• CPC Class Codes: G06F 40/242 Dictionaries
• CPC Class Codes: G06F 40/40 Processing or translation of natural language natural language analysis G06F40/20; semantic analysis G06F40/30
• CPC Class Codes: G06F 9/454 Multi-language systems; Localisation; Internationalisation

Abstract

A dictionary mapping source locale strings to target locale strings is constructed. A tree is constructed from the dictionary. The tree has nodes including a start node, end nodes, and string nodes. The nodes form node chains of the tree that correspond to the source locale strings. Each node chain links a collection of the nodes from the start node to a string node. Each node other than the start node has a parent node and corresponds to a character of the source locale strings. Each node other than the end nodes has one or more child nodes. Each string node ends a node chain, and corresponds to a mapping within the dictionary of a source locale string to a target locale string. An input string having the source locale is processed against the tree to generate an output string having the target locale.

Claims

1. A method to translate an input string having a source locale to an output string having a target locale comprising:

constructing, by a processor of a computing device, a dictionary mapping source locale strings of the source locale to target locale strings of the target locale;

constructing, by the processor, a tree from the dictionary, the tree having a plurality of nodes including a start node, one or more end nodes, and one or more string nodes, the nodes forming one or more node chains of the tree, the node chains corresponding to the source locale strings,

each node chain linking a collection of the nodes from the start node to one of the string nodes, each node within the collection of the nodes being linked to another node within the collection of nodes,

each node other than the start node having a parent node, each node other than the start node corresponding to a character of the source locale strings;

each node other than the end nodes having one or more child nodes,

each string node ending one of the node chains of the tree, each string node corresponding to a mapping within the dictionary of one of the source locale strings to one of the target locale strings;

processing, by the processor, the input string against the tree to generate the output string, the input string having a plurality of characters, the characters processed on a character-by-character basis against the tree to match each sub-plurality of one or more sub-pluralities of the characters to one of the node chains within the tree to translate the sub-plurality of the characters from the source locale to the target locale; and

,

outputting, by the processor, the output string,

wherein processing the input string against the tree comprises;

for each character of the input string,

appending the character to a read buffer;

processing one or more active states based on the character,

where each active state represents a procession through the tree such that the procession encompasses a linked number of the nodes of the tree matching previous characters of the input string that have already been processed,

where processing the active states results in a first list of new states;

clearing the active states;

setting the new states within the first list as the active states;

creating a new state representing the start node and processing new state based on the character in a same manner in which the active states are processed based on the character, where processing the new state results in a second list of new states;

adding the new states within the second list to the active states;

pruning the active states;

where there are no active states after pruning, processing one or more completed states,

where each completed state represents a procession through the tree corresponding to one of the node chains ending in one of the string nodes,

where processing the completed states results in translation of one of the sub-pluralities of the characters of the input string from the source locale to the target locale within the output string;

otherwise, where there are active states after pruning,

determining one or more candidate states, where each candidate state represents a completed state;

processing the candidate states in a same manner in which the completed states are processed;

performing a replace operation in relation to the completed states; and

,

writing any remaining characters within the read buffer to the output string.

2. The method of claim 1, wherein at least one of the string nodes is an end node, and at least one of the string nodes is not an end node.

3. The method of claim 1, wherein at least one of the node chains shares one or more of the nodes with at least one other of the node chains.

4. The method of claim 1, wherein at least one of the source locale strings comprises a wildcard character, such that one of the nodes within the tree corresponds to the wildcard character and is a wildcard node within the tree.

5. The method of claim 4, wherein each node of the node chain to which the sub-plurality of the characters matches, other than the start node and other than the node of the node chain to which the sub-plurality of the characters matches that corresponds to the wildcard character, corresponds to a single character within the sub-plurality of the characters of the input string, and

wherein the node of the node chain to which the sub-plurality of the characters matches that corresponds to the wildcard character corresponds to more than one character within the sub-plurality of the characters of the input string.

6. The method of claim 1, wherein constructing the dictionary comprises:

reading a source locale file, the source locale file having the source locale strings identified by property names;

reading a target locale file, the target locale file having the target locale strings identified by the property names; and

,

for each property name,

creating a table entry for the property name, the table entry created within a table, the table entry mapping the source locale string identified by the property name to the target locale string identified by the property name.

7. The method of claim 6, wherein constructing the dictionary further comprises, for each property name, where source locale string has a plurality of consecutive wildcard characters, replacing the plurality of consecutive wildcard characters with a single wildcard character within the source locale string as stored in the table entry.

8. The method of claim 1, wherein constructing the tree from the dictionary comprises:

creating the start node of the tree;

for each source locale string within the dictionary,

setting a current node of the tree equal to the start node;

for each character of a plurality of characters of the source locale string,

where the current node has a child node corresponding to the character, setting the current node to the child node;

otherwise, where the current node does not have a child node corresponding to the character, creating a new child node of the current node and setting the current node to the new child node; and

,

mapping the target locale string to which the source locale string corresponds to the current node.

9. The method of claim 8, wherein constructing the tree from the dictionary further comprises, where the character of the source locale string is a wildcard character, and where the current node is the start node or where the current node is a wildcard node, skipping the character.

10. The method of claim 1, wherein processing the input string against the tree further comprises, for each character of the input string,

where a size of the read buffer is greater than a maximum buffer size,

setting a number of characters to flush from the read buffer equal to the buffer size;

for each active state, where a state identifier of the active state is less than the number of characters to flush from the read buffer, setting the number of characters to flush from the read buffer equal to the state identifier of the active state;

for each completed state, where a state identifier of the completed state is less than the number of characters to flush from the read buffer, setting the number of characters to flush from the read buffer equal to the state identifier of the completed state;

retrieving a string to be flushed from the buffer, starting from a first character within the buffer, the string having a number of characters equal to the number of characters to flush from the read buffer;

writing the string to the output string;

flushing the string from the buffer; and

,

decrementing the state identifier of each active state and the state identifier of each completed state by the number of characters flushed from the read buffer.

11. The method of claim 1, The method of claim 10, wherein processing the active states based on the character comprises, for each active state:

for each child node of the node within the tree corresponding to the active state,

creating a new state having all wildcards of the active state to the first list of new states;

where the new state corresponds to a wildcard node within the tree, adding a wildcard to the new state to represent the active state;

where the new state corresponds to a string node within the tree,

adding the new state to the completed states;

where the new state has a child node,

adding the new state to the first list of new states;

where the active state corresponds to a wildcard node within the tree,

incrementing a length of the active state and adding the active state to the first list of new states.

12. The method of claim 1, wherein pruning the active states comprises:

where there is at least one non-active state,

creating a list of wildcard states, the list of wildcard states being initially empty;

for each active state,

where the active state is a wildcard state having one or more wildcard characters, for each wildcard character within the active state, adding the state of the wildcard character to the list of wildcard states; and

,

for each non-active state,

where the non-active state is a wildcard state having one or more wildcard characters, for each wildcard character within the active state, where the state of the wildcard character is present within the list of wildcard states, removing the state of the wildcard character from the active states.

13. The method of claim 1, wherein processing the completed states comprises:

sorting the completed states by increasing order of a state identifier, where each completed state has a state identifier;

setting an index start counter to zero;

for each completed state, in an order in which the completed states have been sorted,

extracting from the read buffer a string from a first character of the read buffer to a character of the read buffer corresponding to the state identifier of the completed state;

retrieving a replacement string from the string node to which the completed state corresponds;

replacing any wildcard characters within the replacement string with corresponding characters from the read buffer;

writing the replacement string to the output string;

setting the index start counter to the state identifier of the completed state plus a length of the completed state;

for each non-active state of one or more non-active states,

where a state identifier of the non-active state is less than the index start counter, removing the non-active state from the non-active states;

clearing the completed states; and

,

flushing the read buffer from the first character of the read buffer to a character of the read buffer corresponding to the index start counter.

14. The method of claim 1, wherein determining the candidate states comprises:

creating a list of candidate states, the list of candidate states being initially empty;

for each completed state,

setting a flag to true;

for each active state,

where the completed state and the active state overlap,

where the active state is a wildcard state, removing the active state from the active states;

otherwise, where the active state is not a wildcard state, setting the flag to false; and

,

where the flag is true,

adding the completed state to the list of candidate states and removing the completed state from the completed states.

15. The method of claim 1, wherein outputting the output string comprises one or more of:

storing the output string on a computer-readable medium;

displaying the output string on a display device for viewing by a user;

printing the output string using a printing device for viewing by the user; and

,

communicating the output string over a network.

16. The method of claim 1, wherein the input string is part of an error log file generated by an application computer program having the source locale.

17. A system for translating an input string having a source locale to an output string having a target locale, the system comprising:

hardware;

a dictionary-construction component implemented at least by the hardware, the dictionary-construction component to construct a dictionary by mapping source locale strings of the source locale to target locale strings of the target locale;

a tree-construction component implemented at least by the hardware, the tree-construction component to construct a tree from the dictionary, the tree having a plurality of nodes including a start node, one or more end nodes, and one or more string nodes, the nodes forming one or more node chains of the tree, the node chains corresponding to the source locale strings,

each node chain linking a collection of the nodes from the start node to one of the string nodes, each node within the collection of the nodes being linked to another node within the collection of nodes,

each node other than the start node having a parent node, each node other than the start node corresponding to a character of the source locale strings;

each node other than the end nodes having one or more child nodes,

each string node ending one of the node chains of the tree, each string node corresponding to a mapping within the dictionary of one of the source locale strings to one of the target locale strings; and

,

a translation component implemented at least by the hardware to process the input string against the tree to generate the output string, the input string having a plurality of characters, the translation component to process the characters on a character-by-character basis against the tree to match each sub-plurality of one or more sub-pluralities of the characters to one of the node chains within the tree to translate the sub-plurality of the characters from the source locale to the target locale,

wherein the translation component is to process the input string against the tree by;

for each character of the input string,

appending the character to a read buffer;

processing one or more active states based on the character,

where each active state represents a procession through the tree such that the procession encompasses a linked number of the nodes of the tree matching previous characters of the input string that have already been processed,

where processing the active states results in a first list of new states;

clearing the active states;

setting the new states within the first list as the active states;

creating a new state representing the start node and processing the new state based on the character in a same manner in which the active states are processed based on the character, where processing the new state results in a second list of new states;

adding the new states within the second list to the active states;

pruning the active states;

where there are no active states after pruning, processing one or more completed states,

where each completed state represents a procession through the tree corresponding to one of the node chains ending in one of the string nodes,

where processing the completed states results in translation of one of the sub-pluralities of the characters of the input string from the source locale to the target locale within the output string;

otherwise, where there are active states after pruning,

determining one or more candidate states, where each candidate state represents a completed state;

processing the candidate states in a same manner in which the completed states are processed;

performing a replace operation in relation to the completed states; and

,

writing any remaining characters within the read buffer to the output string.

18. The system of claim 17, wherein the input string is part of an error log file generated by an application computer program having the source locale.

19. A computer-readable medium having one or more computer programs stored thereon for execution by one or more processors to perform a method to translate an input string having a source locale to an output string having a target locale comprising:

constructing a dictionary mapping source locale strings of the source locale to target locale strings of the target locale;

constructing a tree from the dictionary, the tree having a plurality of nodes including a start node, one or more end nodes, and one or more string nodes, the nodes forming one or more node chains of the tree, the node chains corresponding to the source locale strings,

each node chain linking a collection of the nodes from the start node to one of the string nodes, each node within the collection of the nodes being linked to another node within the collection of nodes,

each node other than the start node having a parent node, each node other than the start node corresponding to a character of the source locale strings;

each node other than the end nodes having one or more child nodes,

each string node ending one of the node chains of the tree, each string node corresponding to a mapping within the dictionary of one of the source locale strings to one of the target locale strings; and

,

processing the input string against the tree to generate the output string, the input string having a plurality of characters, the characters processed on a character-by-character basis against the tree to match each sub-plurality of one or more sub-pluralities of the characters to one of the node chains within the tree to translate the sub-plurality of the characters from the source locale to the target locale,

wherein processing the input string against the tree comprises;

for each character of the input string,

appending the character to a read buffer;

processing one or more active states based on the character,

where each active state represents a procession through the tree such that the procession encompasses a linked number of the nodes of the tree matching previous characters of the input string that have already been processed,

where processing the active states results in a first list of new states;

clearing the active states;

setting the new states within the first list as the active states;

creating a new state representing the start node and processing the new state based on the character in a same manner in which the active states are processed based on the character, where processing the new state results in a second list of new states;

adding the new states within the second list to the active states;

pruning the active states;

where there are no active states after pruning, processing one or more completed states,

where each completed state represents a procession through the tree corresponding to one of the node chains ending in one of the string nodes,

where processing the completed states results in translation of one of the sub-pluralities of the characters of the input string from the source locale to the target locale within the output string;

otherwise, where there are active states after pruning,

determining one or more candidate states, where each candidate state represents a completed state;

processing the candidate states in a same manner in which the completed states are processed;

performing a replace operation in relation to the completed states; and

,

writing any remaining characters within the read buffer to the output string.