JP7615608B2 - Similar character string detection device, method, program, and system - Google Patents

Description

The present invention relates to a similar string detection device, method, program, and system.

Conventionally, a method for detecting a string similar to a given string from among multiple strings is known (Patent Document 1). Examples of similarity measures used when detecting similar strings include the Levenshtein distance and the Jaro-Winkler distance.

The Levenshtein distance expresses similarity in terms of the number of edits (insertion, deletion, or substitution of a single character) required to turn one string into the other. The Jaro-Winkler distance expresses similarity in terms of the number of characters that match between the strings and whether or not substitutions were necessary. Therefore, the Levenshtein and Jaro-Winkler distance methods are suitable for detecting strings that have slight differences (for example, a difference of only one character) due to typos, etc.

JP 2018-36744 A

However, using the Levenshtein distance and Jaro-Winkler distance methods, it is difficult to detect strings in which the order of multiple words is reversed. For example, suppose there are strings "50% solution" and "solution (50%)." Assume that "50% solution" and "solution (50%)" mean the same thing, in other words, they should be judged to be similar. However, using the Levenshtein distance and Jaro-Winkler distance methods, strings in which the order of multiple words is reversed are judged to be completely different strings.

Therefore, the present invention aims to improve the accuracy of detecting similar strings.

[1] a first score calculation unit that calculates a first score by dividing a sum of lengths of character strings common to a first character string and a second character string by a longer length of the first character string and the second character string; and
and an output unit that outputs a combination of similar strings based on the first score.
[2] The method further includes a second score calculation unit that calculates a second score by dividing the longest number of characters in a portion common to the first character string and the second character string by a shorter length of the first character string and the second character string,
The similar string detection device according to [1], wherein the output unit outputs a combination of similar strings based on the second score.
[3] The similar string detection device according to [1], wherein the length of each of the strings common to the first string and the second string is two or more.
[4] The similar string detection device according to [2], wherein the longest number of characters in the common portion between the first string and the second string is the length of a continuous string.
[5] A computer-implemented method comprising:
calculating a first score by dividing a sum of lengths of character strings common to a first character string and a second character string by a longer length of the first character string and the second character string;
and outputting similar string combinations based on the first scores.
[6] A computer,
a first score calculation unit that calculates a first score by dividing a sum of lengths of character strings common to a first character string and a second character string by a longer length of the first character string and the second character string;
and a program for causing the computer to function as an output unit that outputs combinations of similar character strings based on the first score.
[7] A system including a similar string detection device and a user terminal,
The similar character string detection device comprises:
a first score calculation unit that calculates a first score by dividing a sum of lengths of character strings common to a first character string and a second character string by a longer length of the first character string and the second character string;
an output unit that outputs a combination of similar character strings based on the first score,
The user terminal,
The system displays the similar string combinations.

The present invention can improve the accuracy of detecting similar strings.

1 is a diagram showing an overall system configuration including a similar string detection device according to an embodiment of the present invention. 1 is a diagram showing functional blocks of a similar string detection device according to an embodiment of the present invention. 10 is a flowchart showing the flow of similar string detection processing according to an embodiment of the present invention. 11 is a flowchart showing a flow of a first score calculation process according to an embodiment of the present invention. 13 is a flowchart showing a flow of a second score calculation process according to an embodiment of the present invention. 11 is a flowchart showing the flow of a common substring length calculation process according to an embodiment of the present invention. FIG. 11 is a diagram for explaining a calculation of a common substring length according to an embodiment of the present invention. FIG. 11 is a diagram for explaining a calculation of a common substring length according to an embodiment of the present invention. FIG. 11 is a diagram for explaining a calculation of a common substring length according to an embodiment of the present invention. FIG. 11 is a diagram for explaining a calculation of a common substring length according to an embodiment of the present invention. FIG. 11 is a diagram for explaining a calculation of a common substring length according to an embodiment of the present invention. FIG. 11 is a diagram for explaining a calculation of a common substring length according to an embodiment of the present invention. FIG. 11 is a diagram for comparing the accuracy of similar string detection. FIG. 11 is a diagram for comparing the accuracy of similar string detection. FIG. 11 is a diagram for comparing the accuracy of similar string detection. 1 is a diagram illustrating a hardware configuration of a similar string detection device and a user terminal according to an embodiment of the present invention.

Each embodiment will be described below with reference to the accompanying drawings. Note that in this specification and the drawings, components having substantially the same functional configuration are designated by the same reference numerals, and redundant description will be omitted.

<Terminology>
・A "character string" refers to a sequence of one or more characters.
A "string group" is a collection of multiple strings.

In this embodiment, a comparison is described between strings contained in two string groups (hereinafter referred to as string group 1 and string group 2) (i.e., strings contained in string group 1 and string group 2). String group 1 and string group 2 may be different string groups or may be the same string group. However, this embodiment can also be applied to a comparison between a string specified by a user or the like and a string contained in a certain string group.

<System Configuration>
Fig. 1 is a diagram showing an overall system configuration including a similar string detection device 10 according to an embodiment of the present invention. As shown in Fig. 1, the similar string detection system 1 includes the similar string detection device 10 and a user terminal 20. The similar string detection device 10 can transmit and receive data to and from the user terminal 20 via any network. Each of these will be described below.

The similar string detection device 10 is a device (e.g., a server) that performs a process of detecting similar strings (hereinafter also referred to as "similar strings"). Specifically, the similar string detection device 10 detects strings that are similar to a certain string from a group of strings.

The user terminal 20 is a terminal used by a user who wants the similar string detection device 10 to detect similar strings. Specifically, the user terminal 20 accepts the specification of a group of strings input by the user. The user terminal 20 also notifies the similar string detection device 10 of the accepted specification of the group of strings. For example, the user terminal 20 is a personal computer, etc.

The similar string detection device 10 may have some or all of the functions of the user terminal 20.

<Function block>
The similar string detection device 10 includes a first score calculation unit 104 and an output unit 107. The similar string detection device 10 will be described in detail below with reference to FIG.

Figure 2 is a diagram showing the functional blocks of a similar string detection device 10 according to one embodiment of the present invention. As shown in Figure 2, the similar string detection device 10 can include a string group acquisition unit 101, a string selection unit 102, a common substring length calculation unit 103, a first score calculation unit 104, a second score calculation unit 105, a similar string detection unit 106, and an output unit 107. Each of these units is realized by a process executed by a CPU of the similar string detection device 10 by a program installed in the similar string detection device 10. Each unit will be described below.

The string group acquisition unit 101 acquires two string groups (say, string group 1 and string group 2) to be compared. For example, the string group acquisition unit 101 acquires two string groups specified by a user on the user terminal 20. Note that each string group may be stored in the similar string detection device 10, or may be stored outside the similar string detection device 10.

The string selection unit 102 selects one string each from each of the string groups acquired by the string group acquisition unit 101 (i.e., from each of string group 1 and string group 2).

The common part string length calculation unit 103 calculates the length of the string common to the two strings selected by the string selection unit 102 (hereinafter also referred to as the "common part string length").

The first score calculation unit 104 calculates the first score using the result calculated by the common part string length calculation unit 103.

The second score calculation unit 105 calculates the second score using the result calculated by the common part string length calculation unit 103.

The similar string detection unit 106 detects similar strings based on the scores calculated by the first score calculation unit 104 or the second score calculation unit 105. Only the first score may be used, or both the first score and the second score may be used. For example, the similar string detection unit 106 detects combinations of strings (i.e., combinations of similar strings) in descending order of score.

The output unit 107 outputs the similar strings detected by the similar string detection unit 106 (e.g., displaying them on the user terminal 20, storing them in the similar string detection device 10, etc.). For example, the output unit 107 outputs combinations of strings (i.e., combinations of similar strings) in descending order of scores.

<Processing method>
FIG. 3 is a flowchart showing the flow of similar string detection processing according to an embodiment of the present invention.

In step 1 (S1), the string group acquisition unit 101 acquires two string groups (called string group 1 and string group 2) to be compared.

In step 2-1 (S2-1), the string selection unit 102 selects an unprocessed string from the string group 1 acquired in S1. The i-th string in the string group 1 is designated as S1i.

In step 2-2 (S2-2), the string selection unit 102 selects an unprocessed string from the string group 2 acquired in S1. The j-th string in the string group 2 is denoted as S2j.

In step 3 (S3), the common portion string length calculation unit 103 and the first score calculation unit 104 (or the second score calculation unit 105) calculate the scores. Specifically, the common portion string length calculation unit 103 and the first score calculation unit 104 (or the second score calculation unit 105) calculate the scores of S1i and S2j.

In step 4 (S4), the first score calculation unit 104 or the second score calculation unit 105 determines whether or not the scores of all the strings included in the string group 2 have been calculated. If the scores have been calculated, the process proceeds to step 5. If the scores have not been calculated, the process returns to step 2-2, and the string selection unit 102 adds 1 to j and selects the j+1th string from the string group 2.

In step 5 (S5), the similar string detection unit 106 saves one or more strings with high scores (e.g., the string with the highest score) from among the strings included in string group 2 as strings corresponding to S1i.

In step 6 (S6), the first score calculation unit 104 or the second score calculation unit 105 determines whether or not the scores of all the strings included in the string group 1 have been calculated. If the scores have been calculated, the process proceeds to step 7. If the scores have not been calculated, the process returns to step 2-1, and the string selection unit 102 adds 1 to i and selects the (i+1)th string from the string group 1.

In step 7 (S7), the similar string detection unit 106 detects similar strings based on the scores. Note that only the first score may be used, or both the first score and the second score may be used. For example, the similar string detection unit 106 detects combinations of strings (i.e., combinations of similar strings) in descending order of score.

In step 8 (S8), the output unit 107 outputs the similar strings detected in S5 and S7.

Next, details of S3 in FIG. 3 will be described. FIG. 4 is a flowchart showing the flow of the first score calculation process according to one embodiment of the present invention.

In step 11 (S11), the common substring length calculation unit 103 calculates the common substring length of S1i (the i-th string in string group 1) and S2j (the j-th string in string group 2). If there are multiple common strings between S1i and S2j, the string length of each string is calculated as the common substring length. Therefore, multiple common substring lengths can be calculated.

In step 12 (S12), the first score calculation unit 104 divides the sum of the common substring lengths calculated in S11 by the longer of the length of the string S1i (the i-th string in string group 1) and the length of the string S2j (the j-th string in string group 2). The first score calculation unit 104 determines the value obtained by dividing the sum of the common substring lengths by the longer of the length of the string S1i and the length of the string S2j as the first score. A larger first score indicates that the strings are more similar.

Figure 5 is a flowchart showing the flow of the second score calculation process according to one embodiment of the present invention.

In step 21 (S21), the common substring length calculation unit 103 calculates the common substring length of S1i (the i-th string in string group 1) and S2j (the j-th string in string group 2). As in S11, multiple common substring lengths can be calculated.

In step 22 (S22), the second score calculation unit 105 divides the longest common substring length (hereinafter also referred to as the "longest common substring length") among the common substring lengths calculated in S21 by the shorter of the length of the string S1i (the i-th string in string group 1) and the length of the string S2j (the j-th string in string group 2). The second score calculation unit 105 determines the value obtained by dividing the longest common substring length by the shorter of the length of the string S1i and the length of the string S2j as the second score. A larger second score indicates that the strings are more similar.

In addition, instead of the above longest common substring length, the longest common subsequence length may be used. The longest common subsequence length is the number of characters common to two strings, and these characters do not need to be consecutive.

Next, details of S11 in FIG. 4 and S21 in FIG. 5 will be described. FIG. 6 is a flowchart showing the flow of the common part string length calculation process according to one embodiment of the present invention. As shown in FIG. 7, a table for storing data is used in which the number of columns is the length of string S1 + 1 and the number of rows is the length of string S2 + 1. The common part string length calculation unit 103 assigns each character of string S1 starting from the second column from the left. The common part string length calculation unit 103 also assigns each character of string S2 starting from the second row from the top.

In step 101 (S101), the common substring length calculation unit 103 initializes the longest substring length to 0. Specifically, the common substring length calculation unit 103 sets the values of each column in the first row (top row) and each row in the first column (leftmost column) to 0. In other words, the longest substring length at this point is 0.

The common part string length calculation unit 103 starts the search from the first characters of strings S1 and S2. i indicates that it is the i-th character from the first character of string S1. j indicates that it is the j-th character from the first character of string S2. The search is performed from i=0, j=0 (i.e., the first character).

In step 102 (S102), common substring length calculation unit 103 determines whether the i-th character of string S1 is equal to the j-th character of string S2. If they are equal, the process proceeds to step 103; if they are not equal, the process proceeds to step 104. In step 104 (S104), common substring length calculation unit 103 inputs 0 into the box in the j+1th row and i+1th column of the table, and proceeds to step 105.

In step 103 (S103), the common substring length calculation unit 103 inputs the value obtained by adding 1 to the value in the box in the jth row and the ith column of the table, into the box in the jth row and the i+1th column of the table. If the value is greater than the longest substring length at that point in time, the value is updated as the longest substring length.

In step 105 (S105), the common substring length calculation unit 103 determines whether the search has reached the last character of the string S1. If the search has reached the last character, the process proceeds to step 106. If the search has not reached the last character, the process adds 1 to i and returns to S102.

In step 106 (S106), the common substring length calculation unit 103 determines whether the search has reached the last character of the string S2. If the search has reached the last character, the process ends. If the search has not reached the last character, the process adds 1 to j and returns to S102.

The comparison of all characters is completed by the processes of S101 to S106. In the table, the common substring length is the value of the cell in which the bottom right cell is 0, or the cell in which there is no bottom right cell and a value other than 0 has been entered. The longest common substring length is the largest value among the values entered in the table.

<Calculation of common substring length>
7 to 12 are diagrams for explaining a calculation of a common substring length according to an embodiment of the present invention. Suppose that a comparison is made between two strings, a string S1 "ABCDEFG" and a string S2 "AbcDE".

As shown in Figures 7 to 12, a data storage table is used in which the number of columns is the length of string S1 + 1 (in this example, the length of "ABCDEFG": 7 plus 1 = 8) and the number of rows is the length of string S2 + 1 (in this example, the length of "AbcDE": 5 plus 1 = 6). Starting from the second column from the left, each character of string S1 (in this example, "A", "B", "C", "D", "E", "F", "G") is assigned. Also, starting from the second row from the top, each character of string S2 (in this example, "A", "b", "c", "D", "E") is assigned.

First, initialize the longest substring length to 0. Specifically, set the values of each column in the first row (top row) and each row in the first column (leftmost column) to 0. In other words, the longest substring length at this point is 0.

Below, the values resulting from comparing each character in the two strings are entered into the squares where the compared characters intersect. Specifically, if the two characters are equal, the value of the square to the top left of the square where the compared characters intersect plus 1 is entered into the square where the compared characters intersect. If the two characters are not equal, 0 is entered into the square where the compared characters intersect. When a value greater than the current longest substring length is entered, that value is updated as the longest substring length.

First, the first character of each string (in this example, "A" in string S1 and "A" in string S2) is compared. In this example, the two are equal, so the value of the cell to the top left of the cell where the compared characters intersect is added by 1 and entered into the cell where the compared characters intersect (see Figure 7).

Next, the first character of one string is compared with the second and subsequent characters of the other string. First, in this example, the second character "B" of string S1 is compared with the first character "A" of string S2. In this example, since the two are not equal, a 0 is entered in the square where the compared characters intersect (see Figure 8). The same process is repeated until the comparison of each character in string S1 with the first character of string S2 is complete (see Figure 9).

Next, the second character of one string is compared with each character in the other string. First, in this example, the first character "A" of string S1 is compared with the second character "b" of string S2. In this example, since the two are not equal, a 0 is entered in the square where the compared characters intersect (see Figure 10). The same process is repeated until the comparison of each character in string S1 with the second character in string S2 is complete (see Figure 11).

In this way, the values resulting from comparing each character in the two strings are entered into the squares where those characters intersect. In Figure 12, comparison of all characters has been completed. The common substring length is the value of the square where the bottom right square is 0, or where there is no bottom right square and a value other than 0 has been entered (in the example of Figure 12, it is "1" in the square where A intersects with A, and "2" in the square where E intersects with E). That is, in the example of Figure 12, the sum of the common substring lengths is 3 (the sum of "1" and "2"). The longest common substring length is the largest value entered in the table (2 in the example of Figure 12).

The method described in Figures 7 to 12 can be used to quickly calculate the length of the common substring. Suppose we want to compare two strings, string S1 and string S2. Let us assume that the length of each string is

とする。２つの文字列に共通する文字列を取得するために全探索的なアルゴリズムを用いると、文字列Ｓ２からの文字列の切り出し方が、

If a brute-force algorithm is used to obtain a common string between two strings, the method of extracting a string from string S2 is as follows:

通りある。そして、切り出した文字列が文字列Ｓ１に含まれるか否かを確認する組み合わせが、各切り出しについて、

The combinations for checking whether the extracted character string is included in the character string S1 are as follows for each extracted character string:

通りある。したがって、２つの文字列に共通する文字列を取得するための組み合わせは、

Therefore, the combinations to get the common string between two strings are as follows:

通りある。Ｎ文字の比較にはＮ回の演算が必要なので、必要な比較のための演算の回数の合計は、

Since a comparison of N characters requires N operations, the total number of comparison operations required is:

である。つまり、演算コストは、

That is, the computation cost is

で示される演算の回数に比例する。一方、図７～図１２で説明した手法の演算コストは

On the other hand, the computational cost of the methods described in Figs.

で示される演算の回数に比例し、本発明の演算原理の方が高速であるといえる。なお、演算コストは、

It can be said that the calculation principle of the present invention is faster in proportion to the number of calculations shown by

と

and

の積の演算の回数に比例する。

is proportional to the number of multiplication operations.

<Other embodiments>
When calculating score 1, a restriction may be placed on the common substring length. Specifically, common substrings with a length of 1 are excluded. For example, in the tables described in FIG. 7 to FIG. 12, the value of the upper left cell having a value of 1 or more (and the lower right cell having a value of 0, or the lower right cell not existing and having a value other than 0) is set as the common substring length, so that common substrings with a length of 1 can be excluded. When a common substring with a length of 1 is used, the similarity between the strings S1 and S2 containing one common character increases. By eliminating common substrings with a length of 1, a score specialized for word replacement can be calculated. Note that when many strings are composed of a small number of characters, such as 2 to 5 characters, it is more useful to include common substrings with a length of 1.

[Example]
<Accuracy of similar string detection>
The accuracy of similar string detection based on this embodiment will be described below as an example. Figures 13 to 15 are diagrams for comparing the accuracy of similar string detection. Four methods were compared: the Levenshtein distance and the Jaro-Winkler distance, which are conventional techniques, and the first score and second score of the present invention.

The smaller the Levenshtein distance, the more similar the strings are. However, in this comparison, the Levenshtein distance was standardized by dividing it by the longer of the lengths of the two strings.

The larger the Jaro-Winkler distance, the more similar the strings are.

As mentioned above, the larger the first score and second score, the more similar the strings are.

<<Comparison 1>>
FIG. 13 shows the results of comparison 1 of the accuracy of similar string detection. The top row shows the similarity between string 1 "Product 1 Evaluation Recipe (space is full-width space)" and string 2 "Evaluation Recipe Product 1 (space is half-width space)", and the bottom row shows the similarity between string 1 "Product 1 Evaluation Recipe (space is full-width space)" and string 3 "Recipe Product 2 (space is half-width space)". In order to determine that strings in which the word order of multiple words is switched are similar, string 1 and string 2 should be determined to be more similar than string 1 and string 3. The results of comparison 1 show that the first score is appropriate.

<<Comparison 2>>
FIG. 14 shows the results of comparison 2 of the accuracy of similar string detection. The top row shows the similarity between string 1 "Evaluation recipe Product 1 (space is half-width space)" and string 2 "Product 1 Evaluation recipe (space is full-width space)", and the bottom row shows the similarity between string 1 "Evaluation recipe Product 1 (space is half-width space)" and string 3 "Recipe Product 2 (space is half-width space)". In order to determine that strings in which the word order of multiple words is switched are similar, string 1 and string 2 should be determined to be more similar than string 1 and string 3. The results of comparison 2 show that the first score is appropriate.

<<Comparison 3>>
FIG. 15 shows the results of comparison 3 of the accuracy of similar string detection. The upper row shows the similarity between string 1 "Product 1 Evaluation Recipe (spacing is half-width space)" and string 2 "Product 1 Evaluation (spacing is half-width space)", and the lower row shows the similarity between string 1 "Product 1 Evaluation Recipe (spacing is half-width space)" and string 3 "Product 2 Evaluation Recipe (spacing is half-width space)". In order to determine that a string in which words are not omitted and a string in which words are omitted are similar, string 1 and string 2 should be determined to be more similar than string 1 and string 3. The results of comparison 3 show that the second score is appropriate.

＜Effects＞
In this way, in one embodiment of the present invention, character strings in which the word order of a plurality of words has been changed can be determined to be similar to each other, and therefore a character string in which the word order of a plurality of words has been changed can be detected from an original character string. Also, in one embodiment of the present invention, a character string in which words are not omitted and a character string in which words are omitted can be determined to be similar to each other, and therefore a character string in which words are omitted (or a character string in which words are not omitted) can be detected from an original character string.

<Hardware Configuration>
16 is a hardware configuration diagram of the similar string detection device 10 and the user terminal 20 according to an embodiment of the present invention. The similar string detection device 10 and the user terminal 20 have a CPU (Central Processing Unit) 1001, a ROM (Read Only Memory) 1002, and a RAM (Random Access Memory) 1003. The CPU 1001, the ROM 1002, and the RAM 1003 form a so-called computer.

Furthermore, the similar string detection device 10 and the user terminal 20 may have an auxiliary storage device 1004, a display device 1005, an operation device 1006, an I/F (Interface) device 1007, and a drive device 1008.

The hardware components of the similar string detection device 10 and the user terminal 20 are connected to each other via bus B.

The CPU 1001 is a computing device that executes various programs installed in the auxiliary storage device 1004.

The ROM 1002 is a non-volatile memory. The ROM 1002 functions as a primary storage device that stores various programs, data, etc. required for the CPU 1001 to execute various programs installed in the auxiliary storage device 1004. Specifically, the ROM 1002 functions as a primary storage device that stores boot programs such as the Basic Input/Output System (BIOS) and the Extensible Firmware Interface (EFI).

RAM 1003 is a volatile memory such as a dynamic random access memory (DRAM) or a static random access memory (SRAM). RAM 1003 functions as a primary storage device that provides a working area in which various programs installed in the auxiliary storage device 1004 are expanded when they are executed by the CPU 1001.

The auxiliary storage device 1004 is an auxiliary storage device that stores various programs and information used when the various programs are executed.

The display device 1005 is a display device that displays the internal state of the similar string detection device 10 and the user terminal 20, etc.

The operation device 1006 is an input device through which the person operating the similar string detection device 10 and the user terminal 20 inputs various instructions to the similar string detection device 10 and the user terminal 20.

The I/F device 1007 is a communication device that connects to a network and communicates with other devices.

The drive unit 1008 is a device for setting the storage medium 1009. The storage medium 1009 here includes media that record information optically, electrically, or magnetically, such as CD-ROMs, flexible disks, and magneto-optical disks. The storage medium 1009 may also include semiconductor memory that records information electrically, such as EPROM (Erasable Programmable Read Only Memory) and flash memory.

The various programs to be installed in the auxiliary storage device 1004 are installed, for example, by setting the distributed storage medium 1009 in the drive device 1008 and reading the various programs recorded on the storage medium 1009 by the drive device 1008. Alternatively, the various programs to be installed in the auxiliary storage device 1004 may be installed by downloading them from a network via the I/F device 1007.

Although the examples of the present invention have been described in detail above, the present invention is not limited to the specific embodiments described above, and various modifications and variations are possible within the scope of the gist of the present invention as described in the claims.

REFERENCE SIGNS LIST 1 Similar string detection system 10 Similar string detection device 20 User terminal 101 String group acquisition unit 102 String selection unit 103 Common part string length calculation unit 104 First score calculation unit 105 Second score calculation unit 106 Similar string detection unit 107 Output unit 1001 CPU
1002 ROM
1003 RAM
1004 Auxiliary storage device 1005 Display device 1006 Operation device 1007 I/F device 1008 Drive device 1009 Storage medium

Claims (8)

a first score calculation unit that calculates a first score by dividing a sum of lengths of character strings common to a first character string and a second character string by a longer length of the first character string and the second character string;
an output unit that outputs a combination of similar character strings based on the first score ,
The first score calculation unit,
In a table having a number of columns equal to the length of the first character string plus 1 and a number of rows equal to the length of the second character string plus 1, the top row and the leftmost column are set to 0;
assigning each character of the first character string in order from the second column from the left end, and assigning each character of the second character string in order from the second row from the top end;
If the character of the first character string and the character of the second character string are not equal, input 0 into the cell where the compared characters intersect, and if the character of the first character string and the character of the second character string are equal, input into the cell where the compared characters intersect a value obtained by adding 1 to the value of the cell to the upper left of the cell where the compared characters intersect;
A similar string detection device that determines the length of each of the common strings as the value of a cell whose bottom right cell is 0, or a cell that does not exist and has a value other than 0 input . a second score calculation unit that calculates a second score by dividing the longest number of characters in a portion common to the first character string and the second character string by a shorter length of the first character string and the second character string,
The similar string detection device according to claim 1 , wherein the output unit outputs a combination of similar strings based on the second score. The similar string detection device according to claim 1, wherein the length of each of the common strings between the first string and the second string is 2 or more. The similar string detection device according to claim 2, wherein the longest number of characters in the common portion between the first string and the second string is the length of a continuous string. 2. The similar string detection device according to claim 1, wherein a string common to the first string and the second string is excluded if the string has a length of 1. 1. A computer-implemented method comprising:
calculating a first score by dividing a sum of lengths of character strings common to a first character string and a second character string by the longer of a length of the first character string and a length of the second character string;
and outputting a combination of similar strings based on the first score,
In the step of calculating the first score,
In a table having a number of columns equal to the length of the first character string plus 1 and a number of rows equal to the length of the second character string plus 1, the top row and the leftmost column are set to 0;
assigning each character of the first character string in order from the second column from the left end, and assigning each character of the second character string in order from the second row from the top end;
If the character of the first character string and the character of the second character string are not equal, input 0 into the cell where the compared characters intersect, and if the character of the first character string and the character of the second character string are equal, input into the cell where the compared characters intersect a value obtained by adding 1 to the value of the cell to the upper left of the cell where the compared characters intersect;
A method in which the value of a cell whose bottom right cell is 0, or a cell that does not exist bottom right and has a value other than 0 input, is set as the length of each of the common character strings . Computer,
a first score calculation unit that calculates a first score by dividing a sum of lengths of character strings common to a first character string and a second character string by a longer length of the first character string and the second character string;
an output unit that outputs a combination of similar character strings based on the first score ;
The first score calculation unit,
In a table having a number of columns equal to the length of the first character string plus 1 and a number of rows equal to the length of the second character string plus 1, the top row and the leftmost column are set to 0;
assigning each character of the first character string in order from the second column from the left end, and assigning each character of the second character string in order from the second row from the top end;
If the character of the first character string and the character of the second character string are not equal, input 0 into the cell where the compared characters intersect, and if the character of the first character string and the character of the second character string are equal, input into the cell where the compared characters intersect a value obtained by adding 1 to the value of the cell to the upper left of the cell where the compared characters intersect;
A program that sets the value of a cell whose bottom right cell is 0, or a cell that does not exist bottom right and has a value other than 0 entered, as the length of each of the common character strings . A system including a similar string detection device and a user terminal,
The similar character string detection device comprises:
a first score calculation unit that calculates a first score by dividing a sum of lengths of character strings common to a first character string and a second character string by a longer length of the first character string and the second character string;
an output unit that outputs a combination of similar character strings based on the first score,
The first score calculation unit,
In a table having a number of columns equal to the length of the first character string plus 1 and a number of rows equal to the length of the second character string plus 1, the top row and the leftmost column are set to 0;
assigning each character of the first character string in order from the second column from the left end, and assigning each character of the second character string in order from the second row from the top end;
If the character of the first character string and the character of the second character string are not equal, input 0 into the cell where the compared characters intersect, and if the character of the first character string and the character of the second character string are equal, input into the cell where the compared characters intersect a value obtained by adding 1 to the value of the cell to the upper left of the cell where the compared characters intersect;
The value of a cell whose bottom right cell is 0 or a cell whose bottom right cell does not exist and into which a value other than 0 is input is set as the length of each of the common character strings;
The user terminal,
The system displays the similar string combinations.

Images