Adaptive parser-centric text normalization

BACKGROUND

0001Embodiments of the present invention relate to text normalization, and more specifically, to a customizable text normalization framework providing for domain adaptability through modular replacement generators.

BRIEF SUMMARY

0002According to one embodiment of the present invention, a method of and computer program product for text normalization are provided. An input sequence comprising a plurality of tokens is received. A plurality of generators is applied to the input sequence to generate a set of candidate replacements of the tokens of the sequence. A plurality of subsets of the set of candidate replacements is determined such that the candidate replacements of each subset are syntactically consistent. A probability is determined for each of the subsets. A subset of the plurality of subsets having the highest probability is selected. Each candidate replacement of the selected subset is applied to the input sequence to generate an output sequence. The output sequence is outputted.

BRIEF DESCRIPTION OF THE SEVERAL VIEWS OF THE DRAWINGS

0003<figref idref="DRAWINGS">FIG. 1</figref> depicts an exemplary set of replacement generators according to an embodiment of the present disclosure.

0004<figref idref="DRAWINGS">FIG. 2</figref> depicts a normalization graph according to an embodiment of the present disclosure.

0005<figref idref="DRAWINGS">FIG. 3</figref> depicts exemplary performance metrics according to an embodiment of the present disclosure.

0006<figref idref="DRAWINGS">FIG. 4</figref> depicts a computing node according to an embodiment of the present invention.

DETAILED DESCRIPTION

0007Text normalization is the process of transforming informal or malformed writing into a standard form. For example, transforming transcribed slang into standard English poses a text normalization problem. Text normalization may provide a preprocessing step in text-to-speech, speech recognition, named entity recognition, information extraction, parsing, and machine translation. In general, text normalization may be applied in computing tasks that involve natural language in order to provide a standardized input form.

0008Text normalization may include mapping all out-of-vocabulary non-standard word tokens to their in-vocabulary standard forms. However, the generalized text normalization task has a broader scope, encompassing the conversion of input text to a grammatically correct phrase in addition to replacement of non-standard tokens. Correction of grammar may include modifying punctuation and capitalization as well as adding, removing and reordering words.

0009Styles of informal text may vary between domains. For example, the style of writing appearing on Twitter is distinct from the style of text drawn from a transcript of a spoken conversation. An SMS message has its own stylistic conventions, which are in turn distinct from those of Twitter. A text normalization approach may be tailored to a particular domain, and trained using data from that domain. However, while tailoring to a particular domain may increase performance within that domain, it may also reduce the adaptability of the approach to other domains.

0010Accordingly, the present disclosure provides a customizable text normalization framework. The framework provides for domain adaptability through modular replacement generators, which produce fully grammatical sentences. The introduction of a small set of domain-specific generators allows the framework to outperform other approaches, including word-to-word normalization. The flexibility of the model also allows it to produce fully grammatical sentences, which is beyond the capability of a word-to-word normalization approach.

0011The framework of the present disclosure builds a statistical model over a series of heuristic replacement generators. By doing so, it allows a designer to quickly adapt a generic model to a new domain with the inclusion of a small set of domain-specific generators.

0012As noted above, text normalization may be applied to provide clean text for downstream processing applications, such as syntactic parsing. Thus, there is a need for evaluation metrics that capture the effect of text normalization on these downstream processing applications. Evaluating text normalization in terms of word error rate or BLEU (Bilingual Evaluation Understudy) score may not provide an accurate evaluation of performance on a parsing task, where a well-placed punctuation mark may provide more substantial improvements than changing a non-standard word form.

0013Accordingly, an evaluation metric is provided that ties normalization performance directly to the performance of a downstream dependency parser. This evaluation metric allows for a deeper understanding of how certain normalization actions affect the output of the parser.

0014In some embodiments, the original input text (un-normalized) may be represented as a sequence x=x₁, x₂, . . . , x_nof tokens x_i. An exemplary input, referred to further below, is the sequence x=Ay₁woudent₂of₃see₄'em_s(in which commas have been omitted for readability).

0015In embodiments of the present disclosure, a series of replacement generators are applied to the input sequence x. A replacement generator is a function that takes the sequence x as an input, and produces a collection of replacements. A replacement is generally of the form “replace tokens x_i, . . . , x_j-1with s.” More precisely, a replacement is a triple <img file="US2015186355A1_D0001.tif" />i,j, s<img file="US2015186355A1_D0002.tif" />, where 1≦i≦j≦n+1 and s is a sequence of tokens. In cases where i=j, the sequence s is inserted before x_i. In cases where s is empty, x_i, . . . , x_j-1are deleted. With reference to the above exemplary input sequence, the replacement <img file="US2015186355A1_D0003.tif" />2,3, would not<img file="US2015186355A1_D0004.tif" /> replaces x₂=woudent with would not; <img file="US2015186355A1_D0005.tif" />1,2, Ay<img file="US2015186355A1_D0006.tif" /> replaces x₁with itself (thus resulting in no change to input sequence x); <img file="US2015186355A1_D0007.tif" />1,2, ε<img file="US2015186355A1_D0008.tif" /> (where ε is the empty sequence) deletes x₁; and <img file="US2015186355A1_D0009.tif" />6,6, .<img file="US2015186355A1_D0010.tif" /> inserts a period at the end of sequence x. Replacement generators may be provided that are generic (cross-domain) or domain-specific, allowing domain customization.

0016The use of replacement generators allows for great flexibility. Each generator may be viewed as a black box, allowing replacements that are created heuristically, statistically, or by external tools to be incorporated within the same framework as one another.

0017An exemplary set of generators is depicted in <figref idref="DRAWINGS">FIG. 1</figref>. Generator <b>101</b> (keep original) transforms an input to itself—resulting in no change. Generator <b>102</b> (edit distance) transforms an input into a dictionary word that has a minimal edit distance from the input. For example, mapping “bac” to “back” by inserting the missing “k”. A variety of methods are known for calculating an edit distance, including Levenshtein distance, Hamming distance, Damerau-Levenshtein distance, and Jaro-Winkler distance. The edit distance generator may be backed by a variety of dictionaries corresponding to general language or domain specific language. Generator <b>103</b> (lowercase) transforms an input string into its lower case equivalent. Generator <b>104</b> (capitalize) capitalizes an input string. Generator <b>105</b> (spelling) performs a spell check on the input to determine the output. Various generators may use external spell checker services, or any spell checking algorithm known in the art. Generator <b>106</b> (contraction) expands a contraction into a complete phrase. For example, “wouldn't” is transformed into “would not”. The contraction generator may be backed by a general dictionary of contractions, or a domain specific dictionary. Generator <b>107</b> (slang language) transforms a slang phrase into a standard phrase. The slang language generator may be backed by a general dictionary or a domain specific dictionary reflecting common usage in a particular medium or region. Generator <b>108</b> (insert punctuation) takes the empty sequence (ε), and inserts a punctuation mark. Generator <b>109</b> (duplicated punctuation) takes multiple punctuation marks in sequence, and replaces them with a single punctuation mark. For example, “!?” may be replaced with “!”. Generator <b>110</b> (delete filler) removes words, replacing them with the empty sequence (ε). For example, the abbreviation “lmao” may not be considered to have any informational value in certain domains, and thus should be removed.

0018Taken together, generators <b>101</b>-<b>110</b> cover a variety of normalization behavior, from changing non-standard word forms to inserting and deleting tokens. These particular generators are presented as examples, and a variety of additional generators may be included in a given embodiment. As an example of a specialized generator, a Twitter-specific generator may focus on the Twitter-specific notions of hashtags (#), ats (@), and retweets (RT). Generators may be implemented that allow for either the initial symbol or the entire token to be deleted (e.g., @Hertz to Hertz, @Hertz to ε). In various embodiments of the present disclosure, generators may be specialized to SMS, Twitter, Call-center transcripts, or other any other communications medium. A given domain-adapted embodiment of the framework may include a combination of generic and domain specific generators.

0019Domain transfer according to the present disclosure is possible with only a small amount of effort. A relatively modest set of additional replacement generators included in each data set allow each domain-specific embodiment to significantly outperform the generic approach.

0020The flexibility of the model allows for the generation of as many or as few candidates as desired. For instance, the framework may be applied with generators that proposed every word for every token. This avoids the potential problem that reliance on largely heuristically produced generators could result in poor coverage. Second, the reliance on a small number of generators allows the system to consider n-to-m transitions that may be too combinatorially expensive if all possible tokens were considered.

0021With reference to <figref idref="DRAWINGS">FIG. 2</figref>, a normalization graph according to an exemplary embodiment of the present disclosure is provided. Graph <b>200</b> comprises a plurality of nodes <b>201</b> . . . <b>211</b>. Each node lies along a path from start node <b>201</b> to end node <b>211</b>. Each node has an associated replacement, depicted in the notation discussed above.

0022Given the input x and the set of replacements produced by the generators, a unique variable X_ris associated with each replacement r. The variable X_ris boolean. Where X_ris true, the replacement r takes place in producing the output sequence. Dependencies among variables may be determined as follows. To determine syntactic consistency among truth assignments, let r₁=<img file="US2015186355A1_D0011.tif" />i₁, j₁, s₁<img file="US2015186355A1_D0012.tif" /> and r₂=<img file="US2015186355A1_D0013.tif" />i₂, j₂, s₂<img file="US2015186355A1_D0014.tif" /> be two replacements. Replacements r₁and r₂are considered locally consistent if the intervals [i₁,j₁) and [i₂, j₂) are disjoint. Locally consistent pairs of replacements can fire simultaneously (disregarding any other replacements). Two insertions are not allowed at the same position, therefore [i₁,j₁) and [i₂, j₂) are excluded from the definition of local consistency where i₁=j₁=i₂=j₂. Where r₁and r₂are locally consistent and j₁=i₂, r₂is a consistent follower of r₁.

0023An assignment α to variables X_ris sound if every two replacements r₁and r₂α(r₁)=α(r₂)=true are locally consistent. An assignment α is complete if every token of x is captured by at least one replacement r with α(r)=true. Finally, α is legal if it is sound and complete. The output (normalized sequence) defined by a legal assignment is the concatenation of the strings s of the true replacement. For example, in <figref idref="DRAWINGS">FIG. 2</figref>, if bold nodes <b>202</b> . . . <b>206</b> correspond to true values, the output would be I would not have seen them.

0024The graphs of <figref idref="DRAWINGS">FIG. 2</figref> depicts two types of interdependencies among replacements. First, semantic dependencies capture the correlation among replacements. For example, replacing o f with have, makes it more likely that the next see token be replaced with seen. In some embodiments, semantic dependencies are restricted to pairs that consist of a replacement and a consistent follower thereof. A syntactic dependency is due to the fact that an assignment is required to be legal.

0025As depicted in <figref idref="DRAWINGS">FIG. 2</figref>, dependencies may be modeled as a directed graph. Semantic dependencies are modeled by an edge from X_rto X_r′ whenever r′ is a consistent follower of r. In addition, start node <b>201</b> and end node <b>211</b> are included in graph <b>200</b>, with an edge from start node <b>101</b> to each variable that corresponds to a prefix of x, and an edge from each variable that corresponds to a suffix of x to end node <b>211</b>.

0026In other embodiments, dependencies may be modeled using other graphs, such as an undirected graph using Conditional Random Field. However, modeling the dependencies in a directed graph as discussed above provides that the legal assignments are in one-to-one correspondence with the paths from start to end.

0027The probability of an assignment is defined using the log-linear model formulation. The conditional probability of an assignment a given an input sequence x is defined in Equation 1, where L(α, x) is 1 if α is legal and 0 otherwise, Z(x) is the partition function, φ_j(X, Y, x) is a real valued feature function that fires when both X and Y are true, and θ is the weight vector. The legal function L(α, x) ensures that only legal assignments have a positive probability.

0000<maths id="MATH-US-00001" num="00001"><math overflow="scroll"><mtable><mtr><mtd><mrow><mrow><mi>p</mi><mo></mo><mrow><mo>(</mo><mrow><mi>α</mi><mo>|</mo><mi>x</mi></mrow><mo>)</mo></mrow></mrow><mo>=</mo><mrow><mfrac><mn>1</mn><mrow><mi>Z</mi><mo></mo><mrow><mo>(</mo><mi>x</mi><mo>)</mo></mrow></mrow></mfrac><mo></mo><mrow><mi>L</mi><mo></mo><mrow><mo>(</mo><mrow><mi>α</mi><mo>,</mo><mi>x</mi></mrow><mo>)</mo></mrow></mrow><mo></mo><mrow><munderover><mo>∏</mo><mrow><mi>X</mi><mo>-></mo><mi>Y</mi></mrow><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle></munderover><mo></mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo></mo><mrow><mi>exp</mi><mo>(</mo><mrow><munderover><mo>∑</mo><mi>j</mi><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle></munderover><mo></mo><mrow><msub><mi>θ</mi><mi>j</mi></msub><mo></mo><mrow><msub><mi>φ</mi><mi>j</mi></msub><mo></mo><mrow><mo>(</mo><mrow><mi>X</mi><mo>,</mo><mi>Y</mi><mo>,</mo><mi>x</mi></mrow><mo>)</mo></mrow></mrow></mrow></mrow><mo>)</mo></mrow></mrow></mrow></mrow></mtd><mtd><mrow><mi>Equation</mi><mo></mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo></mo><mn>1</mn></mrow></mtd></mtr></mtable></math></maths>

0028According to embodiments of the present disclosure, in an inference step the output sequence with the highest probability is selected given the input sequence (i.e., maximum a posteriori probability (MAP) inference). In particular, the highest probability output sequence is given by an assignment α*=arg max_αp(a|x). While exact inference is generally hard on general graph models, in the above model, inference is equivalent to finding the longest path in a weighted and acyclic directed graph.

0029The directed graph described above is acyclic (hence, a DAG). In particular, given any positive and/or negative weights on the edges, there exists a longest path (i.e., there are no positive cycles) between every pair of nodes. A real value Σ_jθ_jφ_j(X, Y, x) may then be put as the weight for the edge X→Y. As noted above, a legal assignment α corresponds to a path from start to end. It may be shown that the summed weights of any path from start to end is equal to log p(α|x)+log Z(x). In particular, a longer path corresponds to an assignment with greater probability. Therefore, the MAP inference may be solved for the above model by finding the weighted longest path in the directed acyclic graph, which is a tractable problem.

0030In some embodiments of the present disclosure, edge weights are determined through a machine learning algorithm. In general, the items in a training set are pairs (x_i, α_i^gold) for i=1, . . . , n where α_i^goldis a gold-standard assignment with respect to x_i. In some embodiments, α_i^goldis computed from a manually normalized sequence using a dynamic programming algorithm. Learning may be done via maximum likelihood estimation per Equation 2. The result of the partial derivative is given in Equation 3, where Φ_j(α, x)=Σ_X→Yφ_j(X, Y, x), i.e., the sum of feature j along the path of α. The expected value of the sum of feature j, with respect to the probability of assignment with the current weight vector is given by E_p(α_{<sub2>i</sub2>}_|x_{<sub2>i</sub2>}_,θ)Φ_j(α_i,x_i).

0000<maths id="MATH-US-00002" num="00002"><math overflow="scroll"><mtable><mtr><mtd><mrow><mrow><mi>L</mi><mo></mo><mrow><mo>(</mo><mi>θ</mi><mo>)</mo></mrow></mrow><mo>=</mo><mrow><mi>log</mi><mo></mo><mrow><munderover><mo>∏</mo><mi>i</mi><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle></munderover><mo></mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo></mo><mrow><mi>p</mi><mo></mo><mrow><mo>(</mo><mrow><mrow><msub><mi>α</mi><mi>i</mi></msub><mo>=</mo><mrow><msubsup><mi>α</mi><mi>i</mi><mi>gold</mi></msubsup><mo>|</mo><msub><mi>x</mi><mi>i</mi></msub></mrow></mrow><mo>,</mo><mi>θ</mi></mrow><mo>)</mo></mrow></mrow></mrow></mrow></mrow></mtd><mtd><mrow><mi>Equation</mi><mo></mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo></mo><mn>2</mn></mrow></mtd></mtr><mtr><mtd><mrow><munderover><mo>∑</mo><mi>i</mi><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle></munderover><mo></mo><mrow><mo>(</mo><mrow><mrow><msub><mi>Φ</mi><mi>j</mi></msub><mo></mo><mrow><mo>(</mo><mrow><msubsup><mi>α</mi><mi>i</mi><mi>gold</mi></msubsup><mo>,</mo><msub><mi>x</mi><mi>i</mi></msub></mrow><mo>)</mo></mrow></mrow><mo>-</mo><mrow><msub><mi>E</mi><mrow><mi>p</mi><mo></mo><mrow><mo>(</mo><mrow><mrow><msub><mi>α</mi><mi>i</mi></msub><mo>|</mo><msub><mi>x</mi><mi>i</mi></msub></mrow><mo>,</mo><mi>θ</mi></mrow><mo>)</mo></mrow></mrow></msub><mo></mo><mrow><msub><mi>Φ</mi><mi>j</mi></msub><mo></mo><mrow><mo>(</mo><mrow><msub><mi>α</mi><mi>i</mi></msub><mo>,</mo><msub><mi>x</mi><mi>i</mi></msub></mrow><mo>)</mo></mrow></mrow></mrow></mrow><mo>)</mo></mrow></mrow></mtd><mtd><mrow><mi>Equation</mi><mo></mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo></mo><mn>3</mn></mrow></mtd></mtr></mtable></math></maths>

0031Due to the inclusion of n-to-m transitions and the syntactic dependencies, naïve computation of E_p(α_{<sub2>i</sub2>}_|x_{<sub2>i</sub2>}_,θ)Φ_j(α_i,x_i) requires enumerating all legal assignments. A less computationally intensive perceptron-style algorithm may be used instead. In such an approach, instead of computing the expectation, Φ_j(α_i*,x_i) is computed, where α_i* is the most probable assignment generated using the current weight vector. The resulting approximated derivative is given in Equation 4.

0000<maths id="MATH-US-00003" num="00003"><math overflow="scroll"><mtable><mtr><mtd><mrow><munderover><mo>∑</mo><mi>i</mi><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle></munderover><mo></mo><mrow><mo>(</mo><mrow><mrow><msub><mi>Φ</mi><mi>j</mi></msub><mo></mo><mrow><mo>(</mo><mrow><msubsup><mi>α</mi><mi>i</mi><mi>gold</mi></msubsup><mo>,</mo><msub><mi>x</mi><mi>i</mi></msub></mrow><mo>)</mo></mrow></mrow><mo>-</mo><mrow><msub><mi>Φ</mi><mi>j</mi></msub><mo></mo><mrow><mo>(</mo><mrow><msubsup><mi>α</mi><mi>i</mi><mo>*</mo></msubsup><mo>,</mo><msub><mi>x</mi><mi>i</mi></msub></mrow><mo>)</mo></mrow></mrow></mrow><mo>)</mo></mrow></mrow></mtd><mtd><mrow><mi>Equation</mi><mo></mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo></mo><mn>4</mn></mrow></mtd></mtr></mtable></math></maths>

0032According to some embodiments of the present disclosure, the perceptron-style learning applies the following two steps iteratively: (1) Generate the most probable sequence within the current weights; and (2) Update the weights by comparing the path generated in the previous step to the gold standard path.

0033In another aspect of the present disclosure, systems and methods are provided for evaluating the performance of a normalizer based on how it effects the performance of downstream applications. As observed above, evaluation metrics based on word-to-word mapping may not be suitable to evaluate downstream performance. First, different words are unlikely to have equal weights, contrary to the assumption inherent in word-to-word mapping. Second, word-to-word metrics do not take into account potentially important non-word information such as punctuation or capitalization. In addition, word-to-word metrics do not take into account other aspects that may affect downstream performance, such as word reordering.

0034An evaluation metric that directly equates normalization performance with the performance of a common downstream application—dependency parsing is provided. First, gold standard normalized data is created by manually normalizing sentences to their full grammatically correct form. In addition to the word-to-word mapping performed in typical normalization gold standard generation, this annotation procedure includes all actions necessary to make the sentence grammatical, such as word reordering, modifying capitalization, and removing emoticons. A dependency parser is then run on the gold standard normalized data to produce gold standard parses. Although the parser could still produce mistakes on the grammatical sentences, this provides a realistic benchmark for comparison, as it represents an upper bound on the possible performance of the parser, and avoids an expensive second round of manual annotation.

0035To compare the parses produced over automatically normalized data to the gold standard, an analysis is performed of the subjects, verbs, and objects (SVO) identified in each parse. The metric in Equations 5 and 6 is based on the identified subjects and objects in those parses. The set of identified subjects and objects are denoted SO whereas SO^golddenotes the set of subjects and objects identified when parsing the gold standard normalization.

0000<maths id="MATH-US-00004" num="00004"><math overflow="scroll"><mtable><mtr><mtd><mrow><msub><mi>precision</mi><mi>SO</mi></msub><mo>=</mo><mfrac><mrow><mo></mo><mrow><mi>SO</mi><mo>⋂</mo><msup><mi>SO</mi><mi>gold</mi></msup></mrow><mo></mo></mrow><mrow><mo></mo><mi>SO</mi><mo></mo></mrow></mfrac></mrow></mtd><mtd><mrow><mi>Equation</mi><mo></mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo></mo><mn>5</mn></mrow></mtd></mtr><mtr><mtd><mrow><msub><mi>recall</mi><mi>SO</mi></msub><mo>=</mo><mfrac><mrow><mo></mo><mrow><mi>SO</mi><mo>⋂</mo><msup><mi>SO</mi><mi>gold</mi></msup></mrow><mo></mo></mrow><msup><mrow><mo></mo><mi>SO</mi><mo></mo></mrow><mi>gold</mi></msup></mfrac></mrow></mtd><mtd><mrow><mi>Equation</mi><mo></mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo></mo><mn>6</mn></mrow></mtd></mtr></mtable></math></maths>

0036Referring to <figref idref="DRAWINGS">FIG. 3</figref>, subjects, verbs and objects identified on example test/gold text are shown with their corresponding metric scores. The metrics for precision_vand recall_vwhere the set V of identified verbs is compared to V^goldof those found in the gold-standard normalization, are defined as for the SO metrics above.

0037In an exemplary embodiment of the disclosed framework, although real valued features are supported, all features are binary. The feature set pulls information from several different sources. Information from n-grams is used to compare the candidate normalization to the original tokens, and to compare candidate capitalizations. N-gram information may be produced from sources such as the Corpus of Contemporary English (COCA). In this embodiment, part-of-speech information is used to produce features that discourage certain behavior, such as the deletion of noun phrases. Part-of-speech information over the original raw text may ge generated using an external part-of-speech tagger. The part of speech information obtained this way may be noisy, but if this leads to unreliable features then the learning algorithm will weight them accordingly. Positional information is used primarily to handle capitalization and punctuation insertion, for example, by incorporating features for capitalized words after stop punctuation or the insertion of stop punctuation at the end of the sentence. Finally, this exemplary embodiment includes binary features that indicate which generator spawned the replacement.

0038Referring now to <figref idref="DRAWINGS">FIG. 4</figref>, a schematic of an example of a computing node according to an embodiment of the present invention is provided. Computing node <b>10</b> is only one example of a suitable computing node and is not intended to suggest any limitation as to the scope of use or functionality of embodiments of the invention described herein. Regardless, computing node <b>10</b> is capable of being implemented and/or performing any of the functionality set forth hereinabove.

0039In computing node <b>10</b> there is a computer system/server <b>12</b>, which is operational with numerous other general purpose or special purpose computing system environments or configurations. Examples of well-known computing systems, environments, and/or configurations that may be suitable for use with computer system/server <b>12</b> include, but are not limited to, personal computer systems, server computer systems, thin clients, thick clients, handheld or laptop devices, multiprocessor systems, microprocessor-based systems, set top boxes, programmable consumer electronics, network PCs, minicomputer systems, mainframe computer systems, and distributed cloud computing environments that include any of the above systems or devices, and the like.

0040Computer system/server <b>12</b> may be described in the general context of computer system-executable instructions, such as program modules, being executed by a computer system. Generally, program modules may include routines, programs, objects, components, logic, data structures, and so on that perform particular tasks or implement particular abstract data types. Computer system/server <b>12</b> may be practiced in distributed computing environments where tasks are performed by remote processing devices that are linked through a communications network. In a distributed computing environment, program modules may be located in both local and remote computer system storage media including memory storage devices.

0041As shown in <figref idref="DRAWINGS">FIG. 4</figref>, computer system/server <b>12</b> in computing node <b>10</b> is shown in the form of a general-purpose computing device. The components of computer system/server <b>12</b> may include, but are not limited to, one or more processors or processing units <b>16</b>, a system memory <b>28</b>, and a bus <b>18</b> that couples various system components including system memory <b>28</b> to processor <b>16</b>.

0042Bus <b>18</b> represents one or more of any of several types of bus structures, including a memory bus or memory controller, a peripheral bus, an accelerated graphics port, and a processor or local bus using any of a variety of bus architectures. By way of example, and not limitation, such architectures include Industry Standard Architecture (ISA) bus, Micro Channel Architecture (MCA) bus, Enhanced ISA (EISA) bus, Video Electronics Standards Association (VESA) local bus, and Peripheral Component Interconnect (PCI) bus.

0043Computer system/server <b>12</b> typically includes a variety of computer system readable media. Such media may be any available media that is accessible by computer system/server <b>12</b>, and it includes both volatile and non-volatile media, removable and non-removable media.

0044System memory <b>28</b> can include computer system readable media in the form of volatile memory, such as random access memory (RAM) <b>30</b> and/or cache memory <b>32</b>. Computer system/server <b>12</b> may further include other removable/non-removable, volatile/non-volatile computer system storage media. By way of example only, storage system <b>34</b> can be provided for reading from and writing to a non-removable, non-volatile magnetic media (not shown and typically called a “hard drive”). Although not shown, a magnetic disk drive for reading from and writing to a removable, non-volatile magnetic disk (e.g., a “floppy disk”), and an optical disk drive for reading from or writing to a removable, non-volatile optical disk such as a CD-ROM, DVD-ROM or other optical media can be provided. In such instances, each can be connected to bus <b>18</b> by one or more data media interfaces. As will be further depicted and described below, memory <b>28</b> may include at least one program product having a set (e.g., at least one) of program modules that are configured to carry out the functions of embodiments of the invention.

0045Program/utility <b>40</b>, having a set (at least one) of program modules <b>42</b>, may be stored in memory <b>28</b> by way of example, and not limitation, as well as an operating system, one or more application programs, other program modules, and program data. Each of the operating system, one or more application programs, other program modules, and program data or some combination thereof, may include an implementation of a networking environment. Program modules <b>42</b> generally carry out the functions and/or methodologies of embodiments of the invention as described herein.

0046Computer system/server <b>12</b> may also communicate with one or more external devices <b>14</b> such as a keyboard, a pointing device, a display <b>24</b>, etc.; one or more devices that enable a user to interact with computer system/server <b>12</b>; and/or any devices (e.g., network card, modem, etc.) that enable computer system/server <b>12</b> to communicate with one or more other computing devices. Such communication can occur via Input/Output (I/O) interfaces <b>22</b>. Still yet, computer system/server <b>12</b> can communicate with one or more networks such as a local area network (LAN), a general wide area network (WAN), and/or a public network (e.g., the Internet) via network adapter <b>20</b>. As depicted, network adapter <b>20</b> communicates with the other components of computer system/server <b>12</b> via bus <b>18</b>. It should be understood that although not shown, other hardware and/or software components could be used in conjunction with computer system/server <b>12</b>. Examples, include, but are not limited to: microcode, device drivers, redundant processing units, external disk drive arrays, RAID systems, tape drives, and data archival storage systems, etc.

0047As will be appreciated by one skilled in the art, aspects of the present invention may be embodied as a system, method or computer program product. Accordingly, aspects of the present invention may take the form of an entirely hardware embodiment, an entirely software embodiment (including firmware, resident software, micro-code, etc.) or an embodiment combining software and hardware aspects that may all generally be referred to herein as a “circuit,” “module” or “system.” Furthermore, aspects of the present invention may take the form of a computer program product embodied in one or more computer readable medium(s) having computer readable program code embodied thereon.

0048Any combination of one or more computer readable medium(s) may be utilized. The computer readable medium may be a computer readable signal medium or a computer readable storage medium. A computer readable storage medium may be, for example, but not limited to, an electronic, magnetic, optical, electromagnetic, infrared, or semiconductor system, apparatus, or device, or any suitable combination of the foregoing. More specific examples (a non-exhaustive list) of the computer readable storage medium would include the following: an electrical connection having one or more wires, a portable computer diskette, a hard disk, a random access memory (RAM), a read-only memory (ROM), an erasable programmable read-only memory (EPROM or Flash memory), an optical fiber, a portable compact disc read-only memory (CD-ROM), an optical storage device, a magnetic storage device, or any suitable combination of the foregoing. In the context of this document, a computer readable storage medium may be any tangible medium that can contain, or store a program for use by or in connection with an instruction execution system, apparatus, or device.

0049A computer readable signal medium may include a propagated data signal with computer readable program code embodied therein, for example, in baseband or as part of a carrier wave. Such a propagated signal may take any of a variety of forms, including, but not limited to, electro-magnetic, optical, or any suitable combination thereof. A computer readable signal medium may be any computer readable medium that is not a computer readable storage medium and that can communicate, propagate, or transport a program for use by or in connection with an instruction execution system, apparatus, or device.

0050Program code embodied on a computer readable medium may be transmitted using any appropriate medium, including but not limited to wireless, wireline, optical fiber cable, RF, etc., or any suitable combination of the foregoing.

0051Computer program code for carrying out operations for aspects of the present invention may be written in any combination of one or more programming languages, including an object oriented programming language such as Java, Smalltalk, C++ or the like and conventional procedural programming languages, such as the “C” programming language or similar programming languages. The program code may execute entirely on the user's computer, partly on the user's computer, as a stand-alone software package, partly on the user's computer and partly on a remote computer or entirely on the remote computer or server. In the latter scenario, the remote computer may be connected to the user's computer through any type of network, including a local area network (LAN) or a wide area network (WAN), or the connection may be made to an external computer (for example, through the Internet using an Internet Service Provider).

0052Aspects of the present invention are described below with reference to flowchart illustrations and/or block diagrams of methods, apparatus (systems) and computer program products according to embodiments of the invention. It will be understood that each block of the flowchart illustrations and/or block diagrams, and combinations of blocks in the flowchart illustrations and/or block diagrams, can be implemented by computer program instructions. These computer program instructions may be provided to a processor of a general purpose computer, special purpose computer, or other programmable data processing apparatus to produce a machine, such that the instructions, which execute via the processor of the computer or other programmable data processing apparatus, create means for implementing the functions/acts specified in the flowchart and/or block diagram block or blocks.

0053These computer program instructions may also be stored in a computer readable medium that can direct a computer, other programmable data processing apparatus, or other devices to function in a particular manner, such that the instructions stored in the computer readable medium produce an article of manufacture including instructions which implement the function/act specified in the flowchart and/or block diagram block or blocks.

0054The computer program instructions may also be loaded onto a computer, other programmable data processing apparatus, or other devices to cause a series of operational steps to be performed on the computer, other programmable apparatus or other devices to produce a computer implemented process such that the instructions which execute on the computer or other programmable apparatus provide processes for implementing the functions/acts specified in the flowchart and/or block diagram block or blocks.

0055The flowchart and block diagrams in the Figures illustrate the architecture, functionality, and operation of possible implementations of systems, methods and computer program products according to various embodiments of the present invention. In this regard, each block in the flowchart or block diagrams may represent a module, segment, or portion of code, which comprises one or more executable instructions for implementing the specified logical function(s). It should also be noted that, in some alternative implementations, the functions noted in the block may occur out of the order noted in the figures. For example, two blocks shown in succession may, in fact, be executed substantially concurrently, or the blocks may sometimes be executed in the reverse order, depending upon the functionality involved. It will also be noted that each block of the block diagrams and/or flowchart illustration, and combinations of blocks in the block diagrams and/or flowchart illustration, can be implemented by special purpose hardware-based systems that perform the specified functions or acts, or combinations of special purpose hardware and computer instructions.

0056The descriptions of the various embodiments of the present invention have been presented for purposes of illustration, but are not intended to be exhaustive or limited to the embodiments disclosed. Many modifications and variations will be apparent to those of ordinary skill in the art without departing from the scope and spirit of the described embodiments. The terminology used herein was chosen to best explain the principles of the embodiments, the practical application or technical improvement over technologies found in the marketplace, or to enable others of ordinary skill in the art to understand the embodiments disclosed herein.