System and method for text analysis

1. A computer implemented method for generating a Directed Acyclic Graph (DAG) from an initial multi-chain subject to a constraint, the method comprising:

expressing the initial multi-chain as a character string that serves as a current input string, wherein the input string expressing the initial multi-chain violates the constraint, and wherein the constraint with respect to a given input string expresses a condition that the given string either satisfies or violates;

providing at least one regular expression that expresses the constraint, said at least one regular expression being in a character string format and being denoted as P;

applying P to the current input string to generate at least one output string, wherein each generated output string violates the constraint to a lesser extent than does the input string or does not violate the constraint, and wherein each generated output string violating the constraint will serve as a current input string to which the constraint is subsequently applied;

if the at least one output string violates the constraint as a result of said applying P then responsive to the at least one output string violating the constraint, recursively repeating said applying P to each current input string that had been determined from applying P previously, until said applying P does not generate any more output strings violating the constraint, wherein a set of the generated output strings that do not violate the constraint represents the DAG; and

displaying, on a display device, the set of the generated output strings that do not violate the constraint,

wherein said recursively repeating said applying P is performed at least once.

2. The method of claim 1 , wherein said applying P comprises:

identifying a substring of the input string violating the at least one constraint and not being the input string;

deriving from the substring all strings not violating the at least one constraint; and

for each derived string, replacing the substring in the input string with each derived string to generate each output string.

3. The method of claim 2 , wherein said deriving comprises deleting at least one character from the substring to generate each derived string.

4. The method of claim 1 , wherein the at least one output string resulting from applying P to the character string that expresses the initial multi-chain violates the at least one constraint.

5. The method of claim 1 , wherein the at least one output string resulting from applying P to the character string that expresses the initial multi-chain does not violate the at least one constraint.

6. The method of claim 1 , wherein a first output string of the at least one output string generated from applying P to the input string expressing the initial multi-chain violates the at least one constraint to a lesser extent than does the input string expressing the initial multi-chain.

7. The method of claim 6 , wherein the at least one output string generated from applying P to the input string expressing the initial multi-chain comprises a plurality of output strings, and wherein a second output string of the at least one output string generated from applying P to the input string expressing the initial multi-chain violates the at least one constraint to a lesser extent than does the input string expressing the initial multi-chain.

8. A computer program product stored on a computer readable storage medium comprising a computer program product stored thereon, said computer program product comprising computer readable program code adapted to perform a method for generating a Directed Acyclic Graph (DAG) from an initial multi-chain subject to at least one constraint, the method comprising:

expressing the initial multi-chain as a character string that serves as a current input string, wherein the input string expressing the initial multi-chain violates the constraint, and wherein the constraint with respect to a given input string expresses a condition that the given string either satisfies or violates;

providing at least one regular expression that expresses the constraint, said at least one regular expression being in a character string format and being denoted as P;

applying P to the current input string to generate at least one output string, wherein each generated output string violates the constraint to a lesser extent than does the input string or does not violate the constraint, and wherein each generated output string violating the constraint will serve as a current input string to which the constraint is subsequently applied;

if the at least one output string violates the constraint as a result of said applying P then responsive to the at least one output string violating the constraint, recursively repeating said applying P to each current input string that had been determined from applying P previously, until said applying P does not generate any more output strings violating the constraint, wherein a set of the generated output strings that do not violate the constraint represents the DAG; and

displaying, on a display device, the set of the generated output strings that do not violate the constraint,

wherein said recursively repeating said applying P is performed at least once.

9. The computer program product of claim 8 , wherein said applying P comprises:

identifying a substring of the input string violating the at least one constraint and not being the input string;

deriving from the substring all strings not violating the at least one constraint; and

for each derived string, replacing the substring in the input string with each derived string to generate each output string.

10. The computer program product of claim 9 , wherein said deriving comprises deleting at least one character from the substring to generate each derived string.

11. The computer program product of claim 8 , wherein the at least one output string resulting from applying P to the character string that expresses the initial multi-chain violates the at least one constraint.

12. The computer program product of claim 8 , wherein the at least one output string resulting from applying P to the character string that expresses the initial multi-chain does not violate the at least one constraint.

13. The computer program product of claim 8 , wherein a first output string of the at least one output string generated from applying P to the input string expressing the initial multi-chain violates the at least one constraint to a lesser extent than does the input string expressing the initial multi-chain.

14. The computer program product of claim 13 , wherein the at least one output string generated from applying P to the input string expressing the initial multi-chain comprises a plurality of output strings, and wherein a second output string of the at least one output string generated from applying P to the input string expressing the initial multi-chain violates the at least one constraint to a lesser extent than does the input string expressing the initial multi-chain.

15. A computer system comprising a processor and a computer usable memory, said memory storing computer readable program code which when executed by the processor performs a method for generating a Directed Acyclic Graph (DAG) from an initial multi-chain subject to at least one constraint, the method comprising:

expressing the initial multi-chain as a character string that serves as a current input string, wherein the input string expressing the initial multi-chain violates the constraint, and wherein the constraint with respect to a given input string expresses a condition that the given string either satisfies or violates;

providing at least one regular expression that expresses the constraint, said at least one regular expression being in a character string format and being denoted as P;

applying P to the current input string to generate at least one output string, wherein each generated output string violates the constraint to a lesser extent than does the input string or does not violate the constraint, and wherein each generated output string violating the constraint will serve as a current input string to which the constraint is subsequently applied;

if the at least one output string violates the constraint as a result of said applying P then responsive to the at least one output string violating the constraint, recursively repeating said applying P to each current input string that had been determined from applying P previously, until said applying P does not generate any more output strings violating the constraint, wherein a set of the generated output strings that do not violate the constraint represents the DAG; and

displaying, on a display device, the set of the generated output strings that do not violate the constraint,

wherein said recursively repeating said applying P is performed at least once.

16. The computer system of claim 15 , wherein said applying P comprises:

identifying a substring of the input string violating the at least one constraint and not being the input string;

deriving from the substring all strings not violating the at least one constraint; and

for each derived string, replacing the substring in the input string with each derived string to generate each output string.

17. The computer system of claim 16 , wherein said deriving comprises deleting at least one character from the substring to generate each derived string.

18. The computer system of claim 15 , wherein the at least one output string resulting from applying P to the character string that expresses the initial multi-chain violates the at least one constraint.

19. The computer system of claim 15 , wherein the at least one output string resulting from applying P to the character string that expresses the initial multi-chain does not violate the at least one constraint.

20. The computer system of claim 15 , wherein a first output string of the at least one output string generated from applying P to the input string expressing the initial multi-chain violates the at least one constraint to a lesser extent than does the input string expressing the initial multi-chain.

21. The computer system of claim 20 , wherein the at least one output string generated from applying P to the input string expressing the initial multi-chain comprises a plurality of output strings, and wherein a second output string of the at least one output string generated from applying P to the input string expressing the initial multi-chain violates the at least one constraint to a lesser extent than does the input string expressing the initial multi-chain.