Character string distance calculation method and device

1. A computer-implemented method executed by a system of one or more computers, the method comprising:

receiving a target character string;

comparing target characters in the target character string to model characters in a model character string that comprises a sequence of a plurality of characters to produce a target bitmap indicating characters that are common between the target character string and the model character string, the target bitmap comprising a plurality of first flag bits, each first flag bit being associated with a respective character of the target character string and having a first value or a second value, wherein a first flag bit having the first value indicates that a respective target character in the target character string matches a corresponding model character in the model character string, and the first flag bit having the second value indicates that a respective target character in the target character string is different from a corresponding model character in the model character string;

calculating a target bitmap weight associated with the target character string, the target bitmap weight indicating a number of first flag bits that have the first value in the target bitmap;

obtaining an initial candidate bitmap and an initial candidate bitmap weight associated with an initial candidate character string, the initial candidate bitmap comprising two character string bitmaps;

determining that the two character string bitmaps of the initial candidate bitmap weight differs from the target bitmap weight by more than a distance threshold value;

determining that the initial candidate bitmap weight differs from the target bitmap weight by more than a first threshold value;

in response to determining that the two character string bitmaps of the initial candidate bitmap weight differs from the target bitmap weight by more than a distance threshold value and in response to determining that the initial candidate bitmap weight differs from the target bitmap weight by more than the first threshold value, screening out the initial candidate bitmap;

obtaining a candidate bitmap and a candidate bitmap weight associated with a candidate character string, the candidate bitmap comprising a plurality of second flag bits, each second flag bit having the first value or the second value, the candidate bitmap weight indicating a number of second flag bits that have the first value in the candidate bitmap;

determining that the candidate bitmap weight differs from the target bitmap weight by less than the first threshold value;

in response to determining that the candidate bitmap weight differs from the target bitmap weight by less than the first threshold value, adding the candidate character string in a first set of candidate character strings;

performing an exclusive OR operation to provide a bitmap-difference associated with the candidate character string, the exclusive OR operation being performed between the target bitmap and the candidate bitmap;

determining that a number of ones in the bitmap-difference is less than a second threshold value;

in response to determining that the number of ones in the bitmap-difference is less than a second threshold value, adding the candidate character string in a second set of candidate character strings;

calculating a character string distance between the target character string and each character string in the second set of candidate character strings;

generating a message verification response based on the character string distance between the target character string and each character string in the second set of candidate character strings; and

displaying the message verification response.

2. The computer-implemented method of claim 1 , further comprising:

determining one or more closest character strings from the second set of candidate character strings to the target character string based on the character string distance.

3. The computer-implemented method of claim 1 , wherein the candidate character string is included in a plurality of character strings and the method further comprises:

comparing a length of the candidate character string with a target length of the target character string; and

moving to a next character string from the plurality of character strings in response to determining that the length of the candidate character string differs from the target length of the target character string for more than a third threshold value.

4. The computer-implemented method of claim 1 , wherein obtaining the candidate bitmap includes comparing characters in the candidate character string to model characters in a model character string that includes a sequence of a plurality of characters, wherein the first value of a flag bit on the candidate bitmap indicates that a respective character in the candidate character string matches a corresponding model character in the model character string, and the second value of the flag bit on the candidate bitmap indicates that a respective character in the candidate character string does not match a corresponding model character in the model character string.

5. The computer-implemented method of claim 1 , wherein the candidate character string is included in a plurality of character strings and the method further comprises:

in response to determining that the candidate bitmap weight differs from the target bitmap weight by more than the first threshold value or is equal to the first threshold value, moving to a second character string in the plurality of character strings.

6. The computer-implemented method of claim 5 , wherein the method further comprises:

in response to determining that the number of ones on the bitmap-difference is greater than the second threshold value or is equal to the second threshold value, moving to the second character string in the plurality of character strings.

7. The computer-implemented method of claim 1 , wherein the first value is 1 and the second value is 0.

8. A non-transitory, computer-readable medium storing one or more instructions executable by a computer system to perform operations comprising:

receiving a target character string;

comparing target characters in the target character string to model characters in a model character string that comprises a sequence of a plurality of characters to produce a target bitmap indicating characters that are common between the target character string and the model character string, the target bitmap comprising a plurality of first flag bits, each first flag bit being associated with a respective character of the target character string and having a first value or a second value, wherein a first flag bit having the first value indicates that a respective target character in the target character string matches a corresponding model character in the model character string, and the first flag bit having the second value indicates that a respective target character in the target character string is different from a corresponding model character in the model character string;

calculating a target bitmap weight associated with the target character string, the target bitmap weight indicating a number of first flag bits that have the first value in the target bitmap;

obtaining an initial candidate bitmap and an initial candidate bitmap weight associated with an initial candidate character string, the initial candidate bitmap comprising two character string bitmaps;

determining that the two character string bitmaps of the initial candidate bitmap weight differs from the target bitmap weight by more than a distance threshold value;

determining that the initial candidate bitmap weight differs from the target bitmap weight by more than a first threshold value;

in response to determining that the two character string bitmaps of the initial candidate bitmap weight differs from the target bitmap weight by more than a distance threshold value and in response to determining that the initial candidate bitmap weight differs from the target bitmap weight by more than the first threshold value, screening out the initial candidate bitmap;

obtaining a candidate bitmap and a candidate bitmap weight associated with a candidate character string, the candidate bitmap comprising a plurality of second flag bits, each second flag bit having the first value or the second value, the candidate bitmap weight indicating a number of second flag bits that have the first value in the candidate bitmap;

determining that the candidate bitmap weight differs from the target bitmap weight by less than the first threshold value;

in response to determining that the candidate bitmap weight differs from the target bitmap weight by less than the first threshold value, adding the candidate character string in a first set of candidate character strings;

performing an exclusive OR operation to provide a bitmap-difference associated with the candidate character string, the exclusive OR operation being performed between the target bitmap and the candidate bitmap;

determining that a number of ones in the bitmap-difference is less than a second threshold value;

in response to determining that the number of ones in the bitmap-difference is less than a second threshold value, adding the candidate character string in a second set of candidate character strings;

calculating a character string distance between the target character string and each character string in the second set of candidate character strings;

generating a message verification response based on the character string distance between the target character string and each character string in the second set of candidate character strings; and

displaying the message verification response.

9. The non-transitory, computer-readable medium of claim 8 , wherein the operations further comprise:

determining one or more closest character strings from the second set of candidate character strings to the target character string based on the character string distance.

10. The non-transitory, computer-readable medium of claim 8 , wherein the candidate character string is included in a plurality of character strings and the operations further comprise:

comparing a length of the candidate character string with a target length of the target character string; and

moving to a next character string from the plurality of character strings in response to determining that the length of the candidate character string differs from the target length of the target character string for more than a third threshold value.

11. The non-transitory, computer-readable medium of claim 8 , wherein obtaining the candidate bitmap includes comparing characters in the candidate character string to model characters in a model character string that includes a sequence of a plurality of characters, wherein the first value of a flag bit on the candidate bitmap indicates that a respective character in the candidate character string matches a corresponding model character in the model character string, and the second value of the flag bit on the candidate bitmap indicates that a respective character in the candidate character string does not match a corresponding model character in the model character string.

12. The non-transitory, computer-readable medium of claim 8 , wherein the candidate character string is included in a plurality of character strings and the operations further comprise:

in response to determining that the candidate bitmap weight differs from the target bitmap weight by more than the first threshold value or is equal to the first threshold value, moving to a second character string in the plurality of character strings.

13. The non-transitory, computer-readable medium of claim 12 , wherein the operations further comprises:

in response to determining that the number of ones on the bitmap-difference is greater than the second threshold value or is equal to the second threshold value, moving to the second character string in the plurality of character strings.

14. The non-transitory, computer-readable medium of claim 8 , wherein the first value is 1 and the second value is 0.

15. A computer-implemented system, comprising:

one or more computers; and

one or more computer memory devices interoperably coupled with the one or more computers and having tangible, non-transitory, machine-readable media storing one or more instructions that, when executed by the one or more computers, perform one or more operations comprising:

receiving a target character string;

comparing target characters in the target character string to model characters in a model character string that comprises a sequence of a plurality of characters to produce a target bitmap indicating characters that are common between the target character string and the model character string, the target bitmap comprising a plurality of first flag bits, each first flag bit being associated with a respective character of the target character string and having a first value or a second value, wherein a first flag bit having the first value indicates that a respective target character in the target character string matches a corresponding model character in the model character string, and the first flag bit having the second value indicates that a respective target character in the target character string is different from a corresponding model character in the model character string;

calculating a target bitmap weight associated with the target character string, the target bitmap weight indicating a number of first flag bits that have the first value in the target bitmap;

obtaining an initial candidate bitmap and an initial candidate bitmap weight associated with an initial candidate character string, the initial candidate bitmap comprising two character string bitmaps;

determining that the two character string bitmaps of the initial candidate bitmap weight differs from the target bitmap weight by more than a distance threshold value;

determining that the initial candidate bitmap weight differs from the target bitmap weight by more than a first threshold value;

in response to determining that the two character string bitmaps of the initial candidate bitmap weight differs from the target bitmap weight by more than a distance threshold value and in response to determining that the initial candidate bitmap weight differs from the target bitmap weight by more than the first threshold value, screening out the initial candidate bitmap;

obtaining a candidate bitmap and a candidate bitmap weight associated with a candidate character string, the candidate bitmap comprising a plurality of second flag bits, each second flag bit having the first value or the second value, the candidate bitmap weight indicating a number of second flag bits that have the first value in the candidate bitmap;

determining that the candidate bitmap weight differs from the target bitmap weight by less than the first threshold value;

in response to determining that the candidate bitmap weight differs from the target bitmap weight by less than the first threshold value, adding the candidate character string in a first set of candidate character strings;

performing an exclusive OR operation to provide a bitmap-difference associated with the candidate character string, the exclusive OR operation being performed between the target bitmap and the candidate bitmap;

determining that a number of ones in the bitmap-difference is less than a second threshold value;

in response to determining that the number of ones in the bitmap-difference is less than a second threshold value, adding the candidate character string in a second set of candidate character strings;

calculating a character string distance between the target character string and each character string in the second set of candidate character strings;

generating a message verification response based on the character string distance between the target character string and each character string in the second set of candidate character strings; and

displaying the message verification response.

16. The computer-implemented system of claim 15 , wherein the operations further comprise:

determining one or more closest character strings from the second set of candidate character strings to the target character string based on the character string distance.

17. The computer-implemented system of claim 15 , wherein the candidate character string is included in a plurality of character strings and the operations further comprise:

comparing a length of the candidate character string with a target length of the target character string; and

moving to a next character string from the plurality of character strings in response to determining that the length of the candidate character string differs from the target length of the target character string for more than a third threshold value.

18. The computer-implemented system of claim 15 , wherein obtaining the candidate bitmap includes comparing characters in the candidate character string to model characters in a model character string that includes a sequence of a plurality of characters, wherein the first value of a flag bit on the candidate bitmap indicates that a respective character in the candidate character string matches a corresponding model character in the model character string, and the second value of the flag bit on the candidate bitmap indicates that a respective character in the candidate character string does not match a corresponding model character in the model character string.

19. The computer-implemented system of claim 15 , wherein the candidate character string is included in a plurality of character strings and the operations further comprise:

in response to determining that the candidate bitmap weight differs from the target bitmap weight by more than the first threshold value or is equal to the first threshold value, moving to a second character string in the plurality of character strings.

20. The computer-implemented system of claim 19 , wherein the operations further comprise:

in response to determining that the number of ones on the bitmap-difference is greater than the second threshold value or is equal to the second threshold value, moving to the second character string in the plurality of character strings.