JP7601220B2 - Name data matching device, name data matching method, and name data matching program - Google Patents

Description

Embodiments of the present invention relate to a name data matching device, a name data matching method, and a name data matching program.

In database-based operations, it is sometimes possible to perform more multifaceted and comprehensive analyses by integrating databases under different management and using the stored name data side-by-side. To do this, a process known as "name matching" is required, in which name data that represents the same thing between the databases being integrated is integrated by assigning the same identification information to the data.

However, the method of entering name data depends on the database administrator. As a result, there are often situations in which the same thing is represented in different spellings (spelling variations) between the databases being integrated. If databases that contain spelling variations are integrated, when carrying out the analysis described above, the information related to one thing will be missing in the areas where spelling variations have occurred.

As a technique for dealing with such variations in notation, Non-Patent Document 1 and Non-Patent Document 2 propose a method for searching for the most similar character string by quantitatively calculating the similarity between the strings to be searched. Non-Patent Document 3 proposes a method for accurately and efficiently finding character strings that express the same thing by creating a search dictionary. Patent Document 1 also discloses a linking method that uses peripheral information about the data to be matched.

Hiroshi Nakagawa et al., "Terminology Extraction Based on Frequency of Occurrence and Concatenation," Natural Language Processing, 2003, Vol. 10, No. 1, pp. 27-45 Hiroaki Tabuchi et al., "Example-Based Parallel Text Retrieval Method Based on N-grams," IEICE Technical Report, Artificial Intelligence and Knowledge Processing Research Group, Vol.108, No.441, pp.43-48, 2009. Surajit Chaudhuri, Venkatesh Ganti, and Dong Xin. 2009. "Mining document collections to facilitate accurate approximate entity matching". Proc. VLDB Endow. 2, 1 (August 2009), 395-406. DOI: https://doi.org /10.14778/1687627.1687673

Japanese Patent Application Publication No. 2020-123210

There are variations in the way the data is written, including an abbreviation of the registered data name, and names (nicknames) used by users based on local rules.

The methods disclosed in Non-Patent Documents 1 and 2 are popular and effective when only the former abbreviated spellings are present as spelling variations. However, in situations where the latter common names are mixed, each common name is linked to a name that is similar in character string to the common name, which makes it highly likely that erroneous results will be presented. This is because the common name is often significantly different from the name to which it should be linked.

Even when dealing only with the former abbreviations, the methods disclosed in Non-Patent Documents 1 and 2 are designed for use with Japanese, so the scope of their application is limited. This is because the characteristics of abbreviations in Japanese do not all match the characteristics of other languages, so the methods disclosed in Non-Patent Documents 1 and 2 may not be applicable without problem to name data entered in other languages.

Therefore, it is thought that the best method for dealing with common names is to create a dictionary, as disclosed in Non-Patent Document 3. However, as the number of databases to be integrated increases, the dictionary must be expanded accordingly, which has the drawback that it takes time to deal with variations in spelling.

Therefore, Patent Document 1 proposes a technology that makes it possible to match common names by using information surrounding the target data for matching (e.g., data A and data B in the same database are connected) without relying on dictionaries. However, the technology disclosed in Patent Document 1 requires that the graph that can be constructed from the name data of each database satisfy a kind of inclusion relationship (an edge corresponding to an edge in one graph must exist in the other graph). As a result, there is a problem that it is difficult to match name data that results in a graph with a structure that does not maintain the inclusion relationship, and even if it is possible, a large number of candidate names will appear.

This invention aims to provide technology that can accurately match synonymous name data that has spelling variations between the databases being integrated without requiring human labor.

In order to solve the above problem, a name data matching device according to one aspect of the present invention is a name data matching device that matches synonymous name data having different notations between a first database that holds a plurality of name data and adjacency information indicating a logical or physical adjacency relationship between the name data and a second database that holds a plurality of name data, the adjacency information of the name data, and path identification information indicating a path to which the name data belongs, and includes a common data extraction unit, a path creation unit, and a matching unit. The common data extraction unit extracts name data that has the same notation between the first database and the second database as common data. The path creation unit extracts partial paths that have the common data extracted by the common data extraction unit as endpoints and non-common data as vertices between the endpoints from paths represented by path identification information held by the second database, and creates paths for each partial path that have the same endpoints of the common data as the endpoints of the partial path and have a length equal to or greater than the length of the partial path, based on information held by the first database. The matching unit matches the name data held in the first database with the name data held in the second database by searching for combinations of each vertex on the partial path and a vertex on the path created by the path creation unit for each partial path extracted by the path creation unit.

According to one aspect of the present invention, a technology can be provided that can accurately match synonymous name data that has spelling variations between the databases being integrated without requiring human labor.

FIG. 1 is a block diagram showing an example of the configuration of a name data associating device according to an embodiment of the present invention. FIG. 2 is a diagram illustrating an example of a hardware configuration of the name data associating device. FIG. 3 is a diagram showing an example of information held in the basic database stored in the basic database storage unit. FIG. 4 is a diagram illustrating an example of information held in a derivative database stored in a derivative database storage unit. FIG. 5 is a flowchart showing an example of a processing operation related to the association of name data in the name data association device. FIG. 6 is a schematic diagram for explaining a method of associating names. FIG. 7 is a diagram showing an example of information held in the basic database in the operation example. FIG. 8 is a diagram showing an example of information held in the derivative database in the operation example. FIG. 9 is a schematic diagram showing an example of a cycle graph created by the graph creation unit from information held in the basic database in the operation example. FIG. 10 is a schematic diagram showing an example of a path generated from a cycle graph generated by the graph generating unit from information held in the derivation database in the operation example. FIG. 11 is a diagram showing an example of output information stored in the output information storage unit in the operation example.

Below, an embodiment of the present invention is described with reference to the drawings.

In this embodiment, a plurality of databases hold synonymous name data with different notations, and data columns to which name data is to be associated in these databases are assumed to be known. Each data column can include name data and character string data corresponding to the name data, such as measurement values, measurement dates and times, sales dates and times, and sales amounts. It is also assumed that each database holds logical or physical adjacent information indicating the adjacent relationship of the name data. Here, the adjacent information indicating the adjacent relationship of the name data refers to information on how data is connected to each other, such as personal connections (person A and person B are acquaintances) and connection relationships on a network (building A and building B are connected by a cable). In this invention, there is no particular limit to the number of databases to which name data is associated, but in this embodiment, for the sake of simplicity, it is assumed that there are two target databases. It is also assumed that there is a connection relationship on a network between the name data in each database. Specifically, each database has columns named "upper building" and "lower building", and the name data stored in the "upper building" and the name data stored in the "lower building" are adjacent on a certain network. In addition, it is assumed that at least one of the plurality of databases has, in addition to the adjacent information, path identification information indicating the path to which the name data belongs.

(Configuration example)
1 is a block diagram showing an example of the configuration of a name data matching device according to an embodiment of the present invention. The name data matching device has a basic database (database is abbreviated as DB in the figure) 1, a derived database 2, a graph creation unit 3, a common data extraction unit 4, a path information extraction unit 5, a path creation unit 6, a matching unit 7, and a data output unit 8.

The basic database 1 is a first database that holds a plurality of name data and adjacent information that indicates the adjacent relationship of the name data. The derived database 2 is a second database that holds a plurality of name data, adjacent information of the name data, and path identification information that indicates the path to which the name data belongs.

The graph creation unit 3 creates an undirected graph with name data as vertices based on the information held in the basic database 1 and the derived database 2.

The common data extraction unit 4 extracts name data that is written in the same way between the basic database 1 and the derived database 2 as common data.

Based on the path identification information held by the derivative database 2, the path information extraction unit 5 generates all paths that start from one of the common data extracted by the common data extraction unit 4 and have the name data held by the derivative database 2 as their vertices. The end point of a path may be the same common data as the start point, or it may be common data different from the start point. Then, the path information extraction unit 5 extracts path information for each of these paths, including the number of vertices, the name data of the vertices included, and their positions on the path. For example, the path information extraction unit 5 can extract path information based on the undirected graph created by the graph creation unit 3 and the path identification information held by the derivative database 2.

For each path indicated by the path information extracted by the path information extraction unit 5, the path creation unit 6 extracts partial paths whose endpoints are the common data, i.e., the start and end points. Then, based on the information held by the basic database 1, the path creation unit 6 counts up all paths whose endpoints are common data matching each partial path and which are of a specified length. For example, the path creation unit 6 can enumerate paths based on the undirected graph created by the graph creation unit 3 from the basic database 1.

The matching unit 7 searches for combinations of vertex name data from the partial paths extracted by the path creation unit 6 and the counted paths based on string similarity such as edit distance. Then, based on the searched combinations, the matching unit 7 matches the name data held in the basic database 1 with the name data held in the derived database 2.

The data output unit 8 generates output information based on the results of the matching in the matching unit 7 and outputs it. For example, the data output unit 8 can generate a correspondence table showing the correspondence of name data as output information based on the results of the matching in the matching unit 7. The data output unit 8 may also convert name data for the information held in the basic database 1 based on the results of the matching in the matching unit 7, create a new database, and use this as output information. Alternatively, the data output unit 8 may integrate the information held in the basic database 1 and the derived database 2 based on the results of the matching in the matching unit 7, create a new database, and use this as output information.

Figure 2 shows an example of the hardware configuration of a name data matching device.

2, the name data matching device is configured with a computer such as a server computer or a personal computer, and has a hardware processor 101 such as a CPU (Central Processing Unit). In the name data matching device, program memory 102, data memory 103, communication interface 104, and input/output interface (referred to as input/output IF in FIG. 2) 105 are connected to this processor 101 via bus 106.

The communication interface 104 may include, for example, one or more wired or wireless communication modules. When the basic database 1 and/or the derived database 2 are configured as data servers connected via a network such as a LAN (Local Area Network) or the Internet, the communication interface 104 can communicate with the data servers and acquire data from the data servers. The communication interface 104 can also communicate with an external data processing device and receive requests from the data processing device and return data processing results in response to the requests to the data processing device.

The input/output interface 105 is connected to an input unit 107 and a display unit 108. The input unit 107 and the display unit 108 may be a so-called tablet-type input/display device in which an input detection sheet using an electrostatic or pressure method is arranged on the display screen of a display device using, for example, liquid crystal or organic EL (Electro Luminescence). The input unit 107 and the display unit 108 may be configured as independent devices. The input/output interface 105 inputs operation information inputted in the input unit 107 to the processor 101, and causes the display unit 108 to display display information generated by the processor 101.

It should be noted that the input unit 107 and the display unit 108 do not have to be connected to the input/output interface 105. The input unit 107 and the display unit 108 can transmit and receive information between the processor 101 and the input unit 107 and the display unit 108 by being provided with a communication unit for connecting to the communication interface 104 directly or via a network.

In addition, the input/output interface 105 may have a function for reading/writing a recording medium such as a semiconductor memory such as a flash memory, or may have a function for connecting to a reader/writer having a function for reading/writing such a recording medium. This allows a recording medium that is detachable from the name data matching device to be used as a database that holds name data. The input/output interface 105 may further have a function for connecting to other devices.

The program memory 102 is a non-transient tangible computer-readable storage medium that is a combination of a non-volatile memory that can be written and read at any time, such as a hard disk drive (HDD) or a solid state drive (SSD), and a non-volatile memory such as a ROM. The program memory 102 stores programs necessary for the processor 101 to execute various control processes according to an embodiment. That is, the processing function units in each of the graph creation unit 3, the common data extraction unit 4, the path information extraction unit 5, the path creation unit 6, the correspondence unit 7, and the data output unit 8 can all be realized by having the processor 101 read and execute the programs stored in the program memory 102. Note that some or all of these processing function units may be realized in various other forms, including integrated circuits such as application specific integrated circuits (ASICs) or field-programmable gate arrays (FPGAs).

The data memory 103 is a tangible computer-readable storage medium, for example, a combination of the above-mentioned non-volatile memory and a volatile memory such as a RAM (Random Access Memory). This data memory 103 is used to store various data acquired and created in the course of various processes. That is, areas are secured in the data memory 103 for storing various data as appropriate in the course of various processes. As such areas, the data memory 103 may be provided with, for example, a basic database storage unit 1031, a derived database storage unit 1032, a temporary storage unit 1033, and an output information storage unit 1034.

The basic database storage unit 1031 stores information on basic database 1, and the derived database storage unit 1032 stores information on derived database 2. In other words, the basic database 1 and the derived database 2 can be configured in the basic database storage unit 1031 and the derived database storage unit 1032.

FIG. 3 is a diagram showing an example of information held by the basic database 1 stored in the basic database storage unit 1031, and FIG. 4 is a diagram showing an example of information held by the derivative database 2 stored in the derivative database storage unit 1032. Here, an example is shown in which the name data is the name of a building. In the basic database 1 stored in the basic database storage unit 1031, a higher-level building and a lower-level building are adjacent to each other. In the derivative database 2 stored in the derivative database storage unit 1032, a combination of buildings having the same path identifier (in the figure, the identifier is abbreviated as ID) constitutes one path (Shinjuku Building → Minami-Shinjuku Building → Gaien Building → Yotsuya Building → Shinjuku Building). Hereinafter, the building names in the derivative database 2 are represented by c _i (i ∈ {1, 2, ..., n}), and the building names in the basic database 1 are represented by d _j (j ∈ {1, 2, ..., m}). Here, n and m are the numbers of building names in each database.

The information stored in the basic database storage unit 1031 and the derived database storage unit 1032 can be, for example, information on the basic database 1 and the derived database 2 received by the processor 101 via the input/output interface 105 and input from the input unit 107. That is, the basic database 1 and the derived database 2 can be constructed in the data memory 103. In addition, all or part of the information held by the basic database 1 and the derived database 2 constructed in an external data server may be stored in the basic database storage unit 1031 and the derived database storage unit 1032. In this case, for example, the processor 101 acquires information accumulated in the database server via the communication interface 104 in response to an instruction by a user operation from the input unit 107, and stores the information in the storage units 1031 and 1032. Alternatively, the processor 101 may acquire information recorded on a recording medium via the input/output interface 105. In addition, the processor 101 may receive a request for matching information of the basic database 1 and derived database 2 with name data from an external data processing device or the like via the communication interface 104, and store the received database information in the memory units 1031 and 1032 as information to be processed.

The temporary memory unit 1033 stores the undirected graph created by the processor 101 when it operates as the graph creation unit 3, the common data extracted when it operates as the common data extraction unit 4, the path information for all paths extracted when it operates as the path information extraction unit 5, the partial paths extracted and counted paths when it operates as the path creation unit 6, the name data matching results obtained when it operates as the matching unit 7, and the like.

The output information storage unit 1034 stores the output information obtained when the processor 101 performs operation as the data output unit 8.

(Operation)
Next, the operation of the name data associating device will be described.

Figure 5 is a flowchart showing an example of processing operations related to matching of name data in the name data matching device. Here, it is assumed that information of basic database 1 is already stored in basic database storage unit 1031, and information of derived database 2 is already stored in derived database storage unit 1032. When an instruction to perform matching of name data is received from input unit 107 via input/output interface 105, or from an external data processing device via communication interface 104, processor 101 of the name data matching device begins the operations shown in this flowchart.

First, the processor 101 executes the operation of the graph creation unit 3. That is, the processor 101 uses the adjacency information for each of the information of the derived database 2 stored in the derived database storage unit 1032 and the information of the basic database 1 stored in the basic database storage unit 1031 to generate cycle graphs _Gc and _Gd having name data as vertices (step S1). The generated cycle graphs _Gc and _Gd are stored in the temporary storage unit 1033 of the data memory 103.

If we consider the building name c _i in the derived database 2 and the building name d _j in the basic database 1 as vertices, and assume that adjacent vertices are connected by edges, then we can construct the undirected cycle graphs G _c and G _d as follows: Here, a cycle is a subgraph of the cycle graph G _c , and refers to a path whose start and end points are the same vertex.

E _d : A set of edges obtained from the adjacent information of the basic database 1. g _d : E _d →P(V _d ) A mapping that associates a subset of the vertex set V _d with the elements of E _d . Here, P(V _d ) is a power set of the vertex set V _d .
G _d :=(g _d , V _d , E _d )

_Ec : A set of edges obtained from the adjacent information of the derived database 2. _gc : _Ec → P( _Vc ) A mapping that associates a subset of the vertex set _Vc with an element of _Ec . Note that P( _Vc ) is a power set of the vertex set _Vc .
G _c :=(g _c , V _c , E _c )

In addition, the processor 101 of the name data matching device executes the operation as the common data extraction unit 4. That is, the processor 101 extracts common name data between the information of the basic database 1 stored in the basic database storage unit 1031 and the information of the derived database 2 stored in the derived database storage unit 1032 (step S2). The extracted common name data is stored in the temporary storage unit 1033 of the data memory 103.

Next, the processor 101 executes the operation as the path information extraction unit 5. That is, the processor 101 extracts paths Γ _k (k ∈ {1, 2, ..., K}, K is the total number of paths in the closed-loop graph G c ) from the closed-loop graph G _c of the derived database 2 based on the common name data and the path identification information stored in the derived database ₂ (step S3). Path information indicating the extracted path Γ _k is stored in the temporary storage unit 1033 of the data memory 103. The path information can include the number of vertices of the extracted path Γ _k , the name data of the vertices included therein, and the positions on the path.

Here, the path Γ _k is the k-th path in the cycle graph G _c of the derived database 2, the starting point of which is the vertex s _k ∈V _c .
Γ _k [l]: The l-th vertex (l-th element) among the vertices that make up Γ _k
|Γ _k |: Length of path Γ _k (number of vertices that make up path Γ _k )
Γ _k =(s _k ,..., t _k ),
(Γ _k [l], Γ _k [l+1])∈E _c ,
l∈{1,2,…, |Γ _k |}

There may be any number of paths in the cycle graph G _c , but each path must satisfy the following three conditions.
1. For all s _{k ,} there exists d _j ∈ V _d , d _l such that s _k =d _j , t _k =d _l .
2. All edges in the path Γ _k exist in E _c .
3. ∀c _i ∈V _c belongs to any path Γ _k .

Here, the set of building names extracted in step S2 that are expressed the same in _Vc and _Vd is defined as S:={ _ci ∈ _Vc |∃dj ∈ _{Vd stci} = _dj }. For each _ci and _dj that are not elements of this set S, the name _data matching device performs matching using closed loop graphs _Gc and _Gd as follows.

Here, one of the paths constituting the closed-path graph _Gc is denoted as _Γk , and the array of vertices included in the set S among the vertices constituting the path _Γk is denoted as _Ik , which is defined as follows.
I _k :=(Γ _k [i] | Γ _k [i]∈S, Γ _k [i]≠s _k , i=1, 2, ..., | Γ _k |)

Next, the processor 101 executes the operation of the path creation unit 6 .
That is, the processor 101 first extracts, for one path Γ _k , partial paths having each element of the set S as an end point from the closed-path graph G _c based on the path information extracted in step S3.

(Step S4). That is, L _k ⁱ is a partial path from vertex l _k [i] to vertex l _k [i+1] in path Γ _k . Also, l _k [i] is the i-th element of array l _k .

Next, based on the extracted partial paths, the processor 101 counts up all paths in the closed-loop graph _Gd of the basic database 1, whose start point is _lk [i] and whose end point is _lk [i+1], and whose length is greater than or equal to | _Lki ^| (i=1, 2, ..., | _Γk }) and less than or equal to | _Lki ^| +x (step S5), where x is a positive integer greater than or equal to 0 specified by the user. Note that when enumerating these paths, the same vertices and edges are not passed through twice. The set of enumerated partial paths is

It is written as

Next, the processor 101 executes the operation of the association unit 7 .
That is, the processor 101 first designates a path of length |L _k ⁱ | as α if there is a path of length |L k i | in the set of paths A _k ⁱ counted up in step S5 above. Under this, the processor 101 selects combinations of names as follows (step S6).
(L _k ⁱ [j], α[j]), j=1, 2,..., |L _k ⁱ |
Here, L _k ⁱ [j], α[j] is the j-th vertex of each path.

Furthermore, if there is any combination among the selected combinations whose length is longer than |L _k ⁱ | and is equal to or less than |L _k ⁱ |+x, the processor 101 searches for and associates the combination of name data using a name search technique based on string similarity (e.g., edit distance) as shown in Fig. 6, and stores the result in the temporary storage unit 1033 of the data memory 103 (step S7). The edit distance is disclosed, for example, in D. Gusfield. "Algorithms on strings, trees and sequences: computer science and computational biology." Cambridge university press, 1997.

6 is a schematic diagram for explaining a method of matching names. There is name data (A building, B building, ... n building) of building BL _d stored in the basic database 1 and the name (α building, β building, ... v building) of building BL _c stored in the derived database 2, and as shown by the dashed dotted line in the figure, A building and α building, and n building and v building are already matched by the same name or by a different path. In such a case, the processor 101 can search for a combination of name data by the following procedure.

1. Initialize x=0.
2. Count up the paths of length |L _k ⁱ |+x.
3. Among the vertices of the counted path, names that have already been associated are removed.
4. If the length of the obtained path is greater than |L _k ⁱ |, a building with the shortest edit distance from a building (γ building) that has not yet been associated among the buildings BL _c in the derived database 2 to the building BL _d in the basic database 1 is found. For example, as shown by the solid arrow, building C is searched for as the building with the shortest edit distance from γ building, and it can be associated.
5. Set x=x+1 and repeat steps 2 to 4 above until x reaches the upper limit value designated in advance by the user.
When searching for the building BL _d with the shortest edit distance, the search starts from the building next to the already associated building BL _d , as indicated by the dashed arrow.

In this way, if there is only one combination, the output result is the same, and for the rest, the name data for which an output result has already been obtained is excluded from the candidates. Of the remaining candidates after the exclusion, those that are consistent are kept and used as the matching result. Consistency here means that when there are multiple candidate names for a certain name A, and a name B is excluded from the candidate names by the above-mentioned operation, there is always a path P that was the basis for outputting the excluded name B and the combination (A, B) of name A. From this path P, the name combination (C, D) is also given for a name C that is different from name A. As the name combination (A, B) has been excluded, the combination (C, D) is also excluded. A more specific example will be described later as an operation example.

When the process for one path Γ _k is completed in this manner, the processor 101 judges whether or not all paths Γ _k based on the path information extracted in step S3 have been processed (step S8). That is, the processor 101 judges whether or not the process for all vertices of all paths Γ _k has been completed. If the processor 101 judges that there is a path Γ _k that has not yet been processed, the processor 101 updates k and proceeds to the process of step S4, and repeats the processes of steps S4 to S7.

Then, when it is determined in step S8 that all of the paths Γ _k have been processed, the processor 101 executes the operation of the data output unit 8 to output the association information of the name data (step S9). That is, the processor 101 generates output information in a form instructed from the input unit 107 or an external data processing device from the association results stored in the temporary storage unit 1033 of the data memory 103, and stores the generated output information in the output information storage unit 1034 of the data memory 103. The processor 101 can then display this output information on the display unit 108 via the input/output interface 105, or transmit it to the external data processing device via the communication interface 104.

In the name data matching device according to the embodiment described above, the path creation unit 6 extracts partial paths with common data as end points and non-common data as vertices between the end points, creates a path for each partial path that has the same end point of the common data as the end point and has a length equal to or greater than the length of the partial path, and the matching unit 7 searches for combinations of each vertex on the partial path and a vertex on the path for each partial path, thereby matching the name data held by the basic database 1 with the name data held by the derived database 2. This allows synonymous name data with spelling variations between the databases to be integrated to be accurately matched without human labor, even if the character string data corresponding to the name data does not have a correspondence relationship between the databases. This makes it possible to collect information on a certain matter without omissions between different databases. In addition, the reduction in human labor is expected to have the effect of improving business efficiency.

In addition, in the name data association device according to the embodiment, the graph creation unit 3 creates closed-loop graphs _Gd and _Gc , which are undirected graphs of the basic database 1 and the derived database 2, with name data as vertices, and the path information extraction unit 5 generates all paths _Γk with common data as end points and name data held in the derived database 2 as vertices, and extracts path information including the number of vertices, name data of included vertices, and positions on the path for each of the paths _Γk . Then, the path creation unit 6 extracts a partial path from the closed-loop graph _Gc based on the path information for one of the paths _Γk , and creates a path from the closed-loop graph _Gd for each of the partial paths, which has end points of common data that are the same as the end points of the partial path and includes vertices equal to or greater than the number of vertices that the partial path has. Thus, it is possible to create a path that includes vertices that may be associated with name data held in the basic database 1 and the name data held in the derived database 2, in other words, excludes vertices that may not be associated with name data held in the derived database 2.

Furthermore, the path creation unit 6 creates a path that contains a number of vertices equal to or greater than the number of vertices of the path Γ _k and equal to or less than the number designated by the user. Thus, by limiting the number of vertices contained in a path, it is possible to shorten the processing time.

In addition, in a name data matching device according to one embodiment, for each vertex on the path created by the path creation unit 6, if the position on the path corresponds to a vertex on the partial path, the matching unit 7 matches the name data corresponding to the vertex on the path among the name data held by the basic database 1 with the name data of the vertex on the partial path among the name data held by the derived database 2. If the position on the path does not correspond to a vertex on the partial path, the matching unit 7 matches the name data corresponding to the vertex on the path among the name data held by the basic database 1 with the name data of the vertex on the partial path among the name data held by the derived database 2 based on the character string similarity between the name data. Thus, the name data held by the basic database 1 can be easily matched with the name data held by the derived database 2.

Furthermore, the name data association device according to an embodiment repeats the processes of the path creation unit 6 and the association unit 7 until the processes are completed for all of the paths Γ _k generated by the path information extraction unit 5. This makes it possible to reduce the probability of failing to associate the name data held in the derived database 2 with the name data held in the basic database 1.

In addition, the name data matching device according to one embodiment generates output information including a name data correspondence table based on the result of matching the name data by the data output unit 8. This output information can therefore be used to implement database integration processing. In addition, the name data matching device according to one embodiment may generate information of the integrated database as output information.

[Example of operation]
As an operation example of this embodiment, an overview of the applied name data and the results will be described.

7 is a diagram showing an example of information held by the basic database 1 stored in the basic database storage unit 1031 in the operation example. The adjacent information obtained from this basic database is as follows. Here, the notation (A, B) indicates that the data name A and the data name B are related to each other.
・(Fukuoka Hanazono Building, Tatsukoyama Building)
・(Tatsukoyama Building, Fukuyama Date Building)
・(Fukuyama Date Building, Kuwabara Building)
・(Kuwabara Building, Fukui Fujita Building)
・(Fukui Fujita Building, Fukuchi Yanagawa Building)
・(Fukuchi Yanagawa Building, Hoshina Building)
・(Hoshina Building, Osorezan Building)
・(Hoshina Building, Fukuoka Hanazono Building)
・(Osorezan Building, Fukuoka Hanazono Building)
・(Osorezan Building, Tsukidate Building)
・(Tsukidate Building, Fukushima Kawamata Building)
・(Fukushima Kawamata Building, Fukuoka Hanazono Building)

8 is a diagram showing an example of information held by the derivative database 2 stored in the derivative database storage unit 1032 in the operation example. The adjacent information obtained from this derivative database is as follows. The path of this adjacent information is Γ _k , and since there is only one path handled in this operation example, k = 1. Here, the notation (A → B) indicates that there is a path from data name A to data name B.
・(Hanazono Building → Date Building)
・(Date Building → Kuwabara Building)
・(Kuwabara Building → Fujita Building)
・(Fujita Building → Yanagawa Building)
・(Yanagawa Building → Hoshina Building)
・(Hoshina Building → Osorezan Building)
・(Osorezan Building → Tsukikan Building)
・(Tsukikan Building → Kawamata Building)
・(Kawamata Building → Hanazono Building)

In this operation example, for the name data of path ID=2, the vertex sets V _c and V _d are as follows:
_Vc = {Fukuoka Hanazono Building, Tatsukoyama Building, Fukuyama Date Building, Kuwabara Building, Fukui Fujita Building, Fukuchi Yanagawa Building, Hoshina Building, Osorezan Building, Tsukidate Building, Fukushima Kawamata Building}
V _d = {Hanazono Building, Date Building, Kuwabara Building, Fujita Building, Yanagawa Building, Hoshina Building, Osorezan Building, Tsukidate Building, Kawamata Building}

In this operation example, the correct combination of notations of the name data, that is, the association of the name data, is as follows:
{(Tsukidate Building, Tsukidate Building), (Fukushima Kawamata Building, Kawamata Building), (Fukuoka Hanazono Building, Hanazono Building), (Fukuyama Date Building, Date Building), (Fukui Fujita Building, Fujita Building), (Fukuchi Yanagawa Building, Yanagawa Building)}

We confirmed whether the name data matching device of the embodiment can perform this matching correctly.

In step S1, the processor 101 of the name data association device performs the operation of the graph creation unit 3 to create a cycle graph. Fig. 9 is a schematic diagram showing an example of a cycle graph _Gd created from information held in the basic database 1 in the operation example.

In step S2, the processor 101 operates as the common data extraction unit 4 and extracts name data common to the closed-loop graphs _Gc and _Gd . Here, the name data with the same notation, that is, the building name set S, is as follows:
S: = {Kuwabara Building, Hoshina Building, Osorezan Building}

Therefore, in step S3, the processor 101 operates as the path information extraction unit 5 to extract path information from the derivative database 2, and in step S4, operates as the path creation unit 6 to extract a partial path. Fig. 10 is a schematic diagram showing an example of a path Γ1 generated from a cycle graph _Gc created from information held in the derivative database 2 in the operation example. The processor 101 extracts partial paths Γ1 from the cycle graph _Gc , the end points of which are each element of the building name set S.

Extract.
L ₁ ¹ : = (Kuwabara Building, Fujita Building, Yanagawa Building, Hoshina Building)
L ₁ ² : = (Hoshina Building, Osorezan Building)
L ₁ ³ : = (Osorezan Building, Tsukidate Building, Kawamata Building, Hanazono Building, Date Building, Kuwabara Building)

Then, in step S5, the processor 101 counts up, for the partial path L ₁ ¹ , paths in the closed graph G _d that have "Kuwabara Building" and "Hoshina Building" as their end points and have a length of 3 or more and 3+x or less.

For this example, let's set the parameter x = 1. Then,
Length 3: (Kuwabara Building, Fukui Fujita Building, Fukuchi Yanagawa Building, Hoshina Building)
Length 4: (Kuwabara Building, Fukuyama Date Building, Tatsukoyama Building, Fukuoka Hanazono Building, Hoshina Building)
It becomes.

For the length 3 case, combining the corresponding vertex names of the enumerated paths and the partial path L ₁ ¹ gives
(Fukui Fujita Building, Fujita Building), (Fukuchi Yanagawa Building, Yanagawa Building)
Get candidates.

In the case of length 4, the edit distance of every combination is 1, so
Candidates for "Fujita Building" are: "Fukuyama Date Building", "Tatsukoyama Building", "Fukui Fujita Building"
Candidates for "Yanagawa Building" are: "Fukuoka Hanazono Building", "Tatsukoyama Building", "Fukuchi Yanagawa Building"
It is possible that:

The partial path L ₁ ² has a length of 1 and is therefore omitted.

For ^the partial path _L13 , the processor 101 counts up the paths in the closed graph _Gd that have "Osorezan Building" and "Kuwabara Building" as their end points and have a length of 5 or more and 5+x=6 or less. Then,
Length 5: N/A
Length 6: (Osorezan Building, Tsukidate Building, Fukushima Kawamata Building, Fukuoka Hanazono Building, Tatsukoyama Building, Fukuyama Date Building, Kuwabara Building)
get.

From the path of length 6, a point that has the shortest edit distance with each vertex of the partial path L ₁ ³ is selected.
(Tsukidate Building, Tsukidate Building), (Fukushima Kawamata Building, Kawamata Building), (Fukuoka Hanazono Building, Hanazono Building), (Fukuyama Date Building, Date Building)
Get candidates.

From the above, the combination with one candidate is the answer, so
(Tsukidate Building, Tsukidate Building), (Fukushima Kawamata Building, Kawamata Building), (Fukuoka Hanazono Building, Hanazono Building), (Fukuyama Date Building, Date Building)
is the answer.

And from the answers of "Hanazono Building" and "Date Building", the candidates of "Fujita Building" and "Yanakawa Building" are,
Candidates for "Fujita Building" are: "Tatsukoyama Building" and "Fukui Fujita Building"
Candidates for "Yasagawa Building" are: "Tatsukoyama Building", "Fukuchi Yanagawa Building"
At this point, since the candidates for "Fukuoka Hanazono Building" and "Fukuyama Date Building" were eliminated,
Path: (Kuwabara Building, Fukuyama Date Building, Tatsukoyama Building, Fukuoka Hanazono Building, Hoshina Building)
cannot be a corresponding path in the cyclic graph G _d of the partial path L ₁ ^1. Therefore, the "Tatsukoyama Building" is also excluded from the candidates of the "Fujita Building" and the "Yanagagawa Building", so
(Fukui Fujita Building, Fujita Building), (Fukuchi Yanagawa Building, Yanagawa Building)
gets as an answer.

Thereafter, the processor 101 generates output information based on the results of the above-mentioned correspondence stored in the temporary storage unit 1033 of the data memory 103, and stores the output information in the output information storage unit 1034 of the data memory 103. Figure 11 is a diagram showing an example of the output information stored in the output information storage unit 1034. Note that, although the output information is shown here as a correspondence table showing the correspondence of the name data, it is of course not limited to this.

From the above, it was verified that the name data matching device can accurately match name data by using partial paths.

[Other embodiments]
In the embodiment described above, the number of target databases is two, but the number may be three or more. In other words, if at least one of the three or more databases holds path identification information, it is possible to associate name data with the remaining two or more databases.

In addition, in the above embodiment, a path was used as an example, but it is of course also possible to handle a closed circuit (where the start and end points are the same vertex) rather than a path.

In the above embodiment, the processing is carried out by storing all or part of the information held by basic database 1 and derived database 2 in basic database storage unit 1031 and derived database storage unit 1032 of data memory 103, but this is not limiting. Processor 101 may access an external data server as appropriate via communication interface 104, and use the information stored in basic database 1 and derived database 2 constructed there to carry out processing, storing only the processing results of each step in temporary storage unit 1033. This makes it possible to reduce the capacity of data memory 103 provided in the name data matching device, making it possible to configure a name data matching device at low cost.

In addition, in the above embodiment, an example was described in which output information was generated and output to the display unit 108 or an external data processing device, but it is also possible to output the matching results stored in the temporary storage unit 1033 without generating output information. This makes it possible to reduce the capacity of the data memory 103 provided in the name data matching device, making it possible to configure a name data matching device at low cost. It is also possible to provide a service that only matches name data to a data processing device that performs database integration processing.

The methods described in each embodiment can be stored as a program (software means) that can be executed by a calculator (computer) on a recording medium such as a magnetic disk (floppy disk, hard disk, etc.), optical disk (CD-ROM, DVD, MO, etc.), semiconductor memory (ROM, RAM, flash memory, etc.), and can also be distributed by transmitting it via a communication medium. The programs stored on the medium also include a setting program that configures the software means (including not only execution programs but also tables and data structures) that the calculator executes. The computer that realizes this device reads the program recorded on the recording medium, and in some cases, constructs the software means using the setting program, and executes the above-mentioned processing by controlling the operation of the software means. Note that the recording medium referred to in this specification is not limited to a recording medium for distribution, but also includes storage media such as a magnetic disk or semiconductor memory installed inside the computer or in a device connected via a network.

In short, this invention is not limited to the above-described embodiments, and various modifications can be made in the implementation stage without departing from the gist of the invention. Furthermore, the embodiments may be implemented in appropriate combinations as far as possible, in which case the combined effects can be obtained. Furthermore, the above-described embodiments include inventions at various stages, and various inventions can be extracted by appropriate combinations of the multiple constituent elements disclosed.

REFERENCE SIGNS LIST 1...basic database 2...derived database 3...graph creation section 4...common data extraction section 5...path information extraction section 6...path creation section 7...association section 8...data output section 101...processor 102...program memory 103...data memory 104...communication interface 105...input/output interface 106...bus 107...input section 108...display section 1031...basic database storage section 1032...derived database storage section 1033...temporary storage section 1034...output information storage section

Claims (8)

A name data associating device for associating synonymous name data having different notations between a first database that holds a plurality of name data and adjacency information indicating a logical or physical adjacency relationship between the name data and a second database that holds a plurality of name data, adjacency information for the name data, and path identification information indicating a path to which the name data belongs, comprising:
a common data extraction unit that extracts name data having the same notation between the first database and the second database as common data;
a path creation unit that extracts partial paths, from the paths represented by the path identification information stored in the second database, that have the common data extracted by the common data extraction unit as endpoints and non-common data as vertices between the endpoints, and creates, for each of the partial paths, a path that has endpoints of common data that are the same as the endpoints of the partial paths and has a length equal to or greater than the length of the partial paths, based on the information stored in the first database;
a correspondence unit that associates the name data held in the first database with the name data held in the second database by searching for a combination of each vertex on the partial path and a vertex on the path created by the path creation unit for each of the partial paths extracted by the path creation unit;
A name data association device comprising: a graph creation unit that creates an undirected graph of the first database and the second database, with the name data as a vertex, based on information held in the first database and the second database;
a path information extraction unit that generates all paths having the common data extracted by the common data extraction unit as an end point and the name data stored in the second database as a vertex based on the undirected graph of the second database created by the graph creation unit and the path identification information stored in the second database, and extracts path information for each of the paths including the number of vertices, name data of the vertices included, and positions on the path;
Further comprising:
2. The name data matching device of claim 1, wherein the path creation unit extracts the partial path from the undirected graph of the second database created by the graph creation unit based on the path information for one of the paths generated by the path information extraction unit, and creates, for each of the partial paths, a path from the undirected graph of the first database that has the same common data endpoint as the endpoint of the partial path and includes more vertices than the number of vertices the partial path has. The name data matching device of claim 2, wherein the path creation unit creates a path that includes a number of vertices that is equal to or greater than the number of vertices and is equal to or less than a number specified by a user with respect to the number of vertices. The association unit, for each of the vertices on the path created by the path creation unit,
if the position on the path corresponds to the vertex on the partial path, then associating name data corresponding to the vertex on the path among the name data held in the first database with name data of the vertex on the partial path among the name data held in the second database;
if the position on the path does not correspond to the vertex on the partial path, then, based on a character string similarity between the name data, name data corresponding to the vertex on the path among the name data held in the first database is associated with name data of the vertex on the partial path among the name data held in the second database;
4. The name data correlating device according to claim 1. A name data matching device as described in claim 2 or 3, wherein the path creation unit and the matching unit repeat the process until processing is completed for all paths generated by the path information extraction unit. A name data matching device as described in any one of claims 1 to 5, further comprising an output unit that generates output information including a name data matching table based on the result of matching by the matching unit. A name data matching method in a name data matching device comprising a processor, a first database that holds a plurality of name data and adjacency information indicating a logical or physical adjacency relationship between the name data, and a second database that holds a plurality of name data, adjacency information for the name data, and path identification information indicating a path to which the name data belongs, the method comprising: matching synonymous name data having different notations between the first database and the second database, the method comprising:
extracting, by the processor, name data having the same notation between the first database and the second database stored in the memory as common data;
extracting, by the processor, a partial path having the extracted common data as an end point and non-common data as a vertex between the end points from the path represented by the path identification information held in the second database stored in the memory;
by the processor, based on information held in the first database stored in the memory, creating, for each of the extracted partial paths, a path having an end point of common data that is the same as the end point of the partial path and having a length equal to or greater than the length of the partial path;
by the processor, for each of the extracted partial paths, searching for a combination of each vertex on the partial path and a vertex on the created path, thereby associating the name data held in the first database stored in the memory with the name data held in the second database stored in the memory;
Name data matching method. 7. A name data associating program that causes a processor to function as each of said units of the name data associating device according to claim 1.

Images