Error correction in tables using discovered functional dependencies

• US 9,164,977 B2
• Filed: 06/24/2013
• Issued: 10/20/2015
• Est. Priority Date: 06/24/2013
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Byron, Donna K., Gerard, Scott N., Pikovsky, Alexander, Winkler, Timothy P.
• Primary Examiner(s): LE, HUNG D
• Application Number:
  US13/925,015
• Publication Number:
  US 20140379666A1
• Time in Patent Office: 848 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2365 Ensuring data consistency and integrity
• CPC Class Codes: G06F 16/93 Document management systems
• CPC Class Codes: G06F 40/177 of tables; using ruled lines
• CPC Class Codes: G06F 40/18 of spreadsheets form-filling G06F40/174

Abstract

Mechanisms are provided for performing tabular data correction in a document. Tabular data is received and analyzed to identify at least one portion of the tabular data having an erroneous/missing data value. A functional dependency of the at least one portion of the tabular data on one or more other portions of the tabular data is determined. A correct data value for the erroneous or missing data value of the at least one portion of the tabular data is determined based on the functional dependency of the at least one portion. In addition, the tabular data is modified to replace the erroneous or missing data value with the correct data value and thereby generate a modified table data. A processing operation is then performed on the modified table data to generate a resulting output.

Claims

1. A computer program product comprising a computer readable storage medium having a computer readable program stored therein, wherein the computer readable program, when executed on a computing device, causes the computing device to:

receive a natural language document comprising tabular data;

analyze the tabular data within the natural language document to identify at least one portion of the tabular data comprising an erroneous or missing data value;

determine, for the at least one portion, a functional dependency of the at least one portion of the tabular data on one or more other portions of the tabular data by reference to the natural language document;

determine for the at least one portion, a correct data value for the erroneous or missing data value of the at least one portion of the tabular data based on the determined functional dependency of the at least one portion;

modify the tabular data to replace the erroneous or missing data value with the correct data value and thereby generate a modified tabular data structure; and

perform a processing operation on the modified tabular data structure to generate a resulting output.

2. The computer program product of claim 1, wherein the natural language document is an original document of a corpus of information, and wherein the modified tabular data structure is part of a modified document that replaces the original document in the corpus of information.

3. The computer program product of claim 2, wherein the processing operation is a natural language processing operation that is applied to the modified document.

4. The computer program product of claim 3, wherein the natural language processing operation is part of a question answering operation of a Question and Answer (QA) system.

5. The computer program product of claim 1, wherein the natural language document is received as part of at least one of an optical character reading operation, a natural language processing operation, or a user input of the tabular data.

6. The computer program product of claim 1, wherein the computer readable program causes the computing device to analyze the tabular data to identify at least one portion of the tabular data comprising an erroneous or missing data value at least by identifying the at least one portion of the tabular data as comprising an erroneous or missing data value due to an absence of a homogenous cell block criteria for the at least one portion of the tabular data.

7. The computer program product of claim 1, wherein the computer readable program causes the computing device to analyze the tabular data to identify at least one portion of the tabular data comprising an erroneous or missing data value at least by:

analyzing the at least one portion of the tabular data to determine whether the at least one portion of tabular data comprises a regular structure having a repeated pattern of data or an identifiable dependency between cells in the at least one portion of the tabular data; and

in response to a regular structure being identified in the at least one portion of the tabular data, performing further analysis to determine if one or more cells within the at least one portion of the tabular data do not conform with the regular structure.

8. The computer program product of claim 1, wherein the computer readable program causes the computing device to determining for the at least one portion, a correct data value for the erroneous or missing data value of the at least one portion of the tabular data based on the functional dependency of the at least one portion by at least one of inverting the functional dependency of the at least one portion to generate the corrected data value or approximating the corrected data value using an iterative procedure.

9. The computer program product of claim 1, wherein the computer readable program causes the computing device to analyze the tabular data to identify at least one portion of the tabular data comprising an erroneous or missing data value at least by identifying the at least one portion of the tabular data as comprising an erroneous or missing data value due to a discrepancy between a data value type specified by information in a header of one or more columns or rows associated with the at least one portion of the tabular data and the erroneous or missing data value.

10. The computer program product of claim 1, wherein the computer readable program further causes the computing device to:

output a notification to a user indicating the portion of the tabular data comprising the erroneous or missing data value and the corrected data value as a suggested replacement for the erroneous or missing data value, wherein the modifying of the tabular data is performed in response to receiving user input approving the corrected data value for replacing the erroneous or missing data value.

11. An apparatus comprising:

a processor; and

a memory coupled to the processor, wherein the memory comprises instructions which, when executed by the processor, cause the processor to;

receive a natural language document comprising tabular data;

analyze the tabular data within the natural language document to identify at least one portion of the tabular data comprising an erroneous or missing data value;

determine, for the at least one portion, a functional dependency of the at least one portion of the tabular data on one or more other portions of the tabular data by reference to the natural language document;

determine for the at least one portion, a correct data value for the erroneous or missing data value of the at least one portion of the tabular data based on the determined functional dependency of the at least one portion;

modify the tabular data to replace the erroneous or missing data value with the correct data value and thereby generate a modified tabular data structure; and

perform a processing operation on the modified tabular data structure to generate a resulting output.

12. The apparatus of claim 11, wherein the natural language document is an original document of a corpus of information, and wherein the modified tabular data structure is part of a modified document that replaces the original document in the corpus of information.

13. The apparatus of claim 12, wherein the processing operation is a natural language processing operation that is applied to the modified document.

14. The apparatus of claim 13, wherein the natural language processing operation is part of a question answering operation of a Question and Answer (QA) system.

15. The apparatus of claim 11, wherein the natural language document is received as part of at least one of an optical character reading operation, a natural language processing operation, or a user input of the tabular data.

16. The apparatus of claim 11, wherein the instructions cause the processor to analyze the tabular data to identify at least one portion of the tabular data comprising an erroneous or missing data value at least by identifying the at least one portion of the tabular data as comprising an erroneous or missing data value due to an absence of a homogenous cell block criteria for the at least one portion of the tabular data.

17. The apparatus of claim 11, wherein the instructions cause the processor to analyze the tabular data to identify at least one portion of the tabular data comprising an erroneous or missing data value at least by:

analyzing the at least one portion of the tabular data to determine whether the at least one portion of tabular data comprises a regular structure having a repeated pattern of data or an identifiable dependency between cells in the at least one portion of the tabular data; and

in response to a regular structure being identified in the at least one portion of the tabular data, performing further analysis to determine if one or more cells within the at least one portion of the tabular data do not conform with the regular structure.

18. The apparatus of claim 11, wherein the instructions cause the processor to determining for the at least one portion, a correct data value for the erroneous or missing data value of the at least one portion of the tabular data based on the functional dependency of the at least one portion by at least one of inverting the functional dependency of the at least one portion to generate the corrected data value or approximating the corrected data value using an iterative procedure.

19. The apparatus of claim 11, wherein the instructions cause the processor to analyze the tabular data to identify at least one portion of the tabular data comprising an erroneous or missing data value at least by identifying the at least one portion of the tabular data as comprising an erroneous or missing data value due to a discrepancy between a data value type specified by information in a header of one or more columns or rows associated with the at least one portion of the tabular data and the erroneous or missing data value.

20. The apparatus of claim 11, wherein the instructions cause the processor to:

output a notification to a user indicating the portion of the tabular data comprising the erroneous or missing data value and the corrected data value as a suggested replacement for the erroneous or missing data value, wherein the modifying of the tabular data is performed in response to receiving user input approving the corrected data value for replacing the erroneous or missing data value.