Method and equipment for determining common subsequence of text strings
AssigneeBeijing Hansight Tech Co., Ltd.
InventorsXiaochuan Wan, Hanzhao Gao
Life of this patent
Estimating the term…
Abstract
A method for determining a longest common subsequence in a plurality of text strings. The method comprises: separately converting a plurality of text strings into word sequences (S100); classifying the word sequences (S400); and performing longest common subsequence computation on every class (S500). The time needed by LCS computation can be saved by classifying text strings.
Claims9
A computer-implemented method for determining a longest common subsequence among a plurality of text strings, comprising:
- converting, by a first conversion device, a plurality of the text strings into word sequences respectively;
- converting, by a second conversion device, the word sequences into corresponding word sets respectively;
- calculating, by an operation device, a minimum hash value for each word set of the corresponding word sets;
- classifying, by a classification device, the word sequences into categories according to the minimum hash value;
- and
- performing, by the operation device, a longest common subsequence operation in each category,
- wherein two word sequences with a minimum hash distance less than a first threshold are classified into same category,
- wherein the longest common subsequence operation includes:
- selecting a word sequence in the same category as a first word sequence, and respectively calculating the longest common subsequence of the first word sequence with other word sequences in the same category until a length of the longest common subsequence obtained is greater than a second threshold,
- wherein the longest common subsequence having a length greater than the second threshold is determined as a text string template,
- wherein the text string template is used to calculate the longest common subsequence in turn with other word sequences in the same category, and during the calculation of the longest common subsequence, the longest common subsequence having a length greater than the second threshold is determined as a new text string template and the calculation of the longest common subsequence is continued.
An apparatus for determining a longest common subsequence among a plurality of text strings, comprising a hardware wherein the hardware is configured to perform following operations including:
- converting, by a first conversion device, a plurality of the text strings into word sequences respectively;
- converting, by a second coversion device, the word sequences into corresponding word sets respectively;
- calculating, by the operation device, a minimum hash value for each word set of the corresponding word sets;
- classifying, by a classification device, the word sequences into categories according to the minimum hash value;
- and
- performing longest common subsequence operation in each category, wherein two word sequences with a minimum hash distance less than a first threshold are classified into same category,
- wherein the longest common subsequence operation includes:
- selecting a word sequence in the same category as a first word sequence, and respectively calculating the longest common subsequence of the first word sequence with other word sequences in the same category until a length of the longest common subsequence obtained is greater than a second threshold,
- wherein the longest common subsequence having a length greater than the second threshold is determined as a text string template,
- wherein the text string template is used to calculate the longest common subsequence in turn with other word sequences in the same category, and during the calculation of the longest common subsequence, the longest common subsequence having a length greater than the second threshold is determined as a next text string template and the calculation of the longest common subsequence is continued.
Dependencies are inferred from the claim text.