Computer program, method, and apparatus for detecting duplicate data

• US 20080027916A1
• Filed: 11/14/2006
• Published: 01/31/2008
• Est. Priority Date: 07/31/2006
• Status: Abandoned Application

• Current Assignee: Fujitsu Limited
• Original Assignee: Fujitsu Limited
• Inventors: Asai, Tatsuya, Okamoto, Seishi
• Application Number:
  US11/599,534
• Publication Number:
  US 20080027916A1
• Time in Patent Office: Days
• US Class Current: 707/3
• CPC Class Codes: G06F 16/215 Improving data quality; Data cleansing, e.g. de-duplication, removing invalid entries or correcting typographical errors
• CPC Class Codes: G06F 16/322 Trees

Abstract

A computer program, method, and apparatus for narrowing data down to detect duplicate data in a short time. A computer functions as a syntax tree constructor for creating a syntax tree by extracting a plurality of letters existing at prescribed discrete positions from the character string of each of the data and a duplicate data detector for detecting some data as possible duplicate data if the data have reached a same leaf node of the syntax tree.

Claims

1. A computer-readable recording medium containing a duplicate data detection program for detecting duplicate data out of a plurality of data each including a character string, the duplicate data detection program causing a computer to perform as:

syntax tree construction means for creating a syntax tree by extracting a plurality of letters existing at prescribed discrete positions from the character string of each of the plurality of data; and

duplicate data detection means for searching each leaf node of the syntax tree to find some of the plurality of data that have reached the leaf node, and detecting the some of the plurality of data as possible duplicate data.

2. The computer-readable recording medium according to claim 1, wherein:

the syntax tree construction means creates a detailed syntax tree by extracting all letters one by one from the character string of each of the possible duplicate data in order from the first or the last letter; and

the duplicate data detection means searches each leaf node of the detailed syntax tree to find some of the possible duplicate data that have reached the leaf node of the detailed syntax tree and detects the some of the possible duplicate data as duplicate data.

3. The computer-readable recording medium according to claim 1, wherein the syntax tree construction means creates the syntax tree by extracting a prescribed number of letters existing at the prescribed discrete positions.

4. A method for detecting duplicate data out of a plurality of data each having a character string, comprising the steps of:

creating a syntax tree by extracting a plurality of letters existing at prescribed discrete positions from the character string of each of the plurality of data;

searching each leaf node of the syntax tree to find some of the plurality of data that have reached the leaf node of the syntax tree; and

detecting the some of the plurality of data as possible duplicate data.

5. An apparatus for detecting duplicate data out of a plurality of data each having a character string, comprising:

syntax tree construction means for creating a syntax tree by extracting a plurality of letters existing at prescribed discrete positions from the character string of each of the plurality of data; and

duplicate data detection means for searching each leaf node of the syntax tree to find some of the plurality of data that have reached the leaf node of the syntax tree and detecting the some of the plurality of data as possible duplicate data.