# US 10,769,192 B2 · Method and equipment for determining common subsequence of text strings > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 10,769,192 B2 - Document ID: US10769192B2 - Status: Granted - Kind: B2 - Application number: 15/770,486 - Filed: 2016-09-21 - Published: 2019-02-21 - Granted: 2020-09-08 - Earliest claimed: 2015-10-21 - Assignees: Beijing Hansight Tech Co., Ltd. - Applicants: Beijing Hansight Tech Co., Ltd. - Inventors: Xiaochuan Wan; Hanzhao Gao - Web page: https://patentgrep.com/patent/US10769192B2 ## CPC - G06F 16/35: Clustering; Classification - G06F 16/00: Information retrieval; Database structures therefor; File system structures therefor - G06F 16/325: {Hash tables} - G06F 21/552: {involving long-term monitoring or reporting} - G06F 40/186: Templates - G06F 40/279: Recognition of textual entities - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## 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. ## Claims ### Claim 1 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. ### Claim 2 (depends on 1) The method according to claim 1, wherein the longest common subsequence operation further includes: deleting the first word sequence from the category if all lengths of the longest common subsequences obtained are not greater than the second threshold, and continuing the longest common subsequence operation. ### Claim 3 (depends on 2) The method according to claim 2, wherein the longest common subsequence having a length greater than the second threshold is determined as a text string template. ### Claim 4 (depends on 3) The method according to claim 3, wherein the text string template is used to calculate the longest common subsequence in turn with other word sequences in the 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. ### Claim 5 (depends on 4) The method according to claim 4, wherein a final text string template is output, and the word sequence in the category which can match the final text string template is deleted. ### Claim 6 (depends on 5) The method according to claim 5, wherein the longest common subsequence operation is continued until the category is empty. ### Claim 7 (depends on 1) The method according to claim 1, wherein a final text string template is output, and a word sequence in the category which can match the final text string template is deleted. ### Claim 8 (depends on 7) The method according to claim 7, wherein the longest common subsequence operation is continued until the category is empty. ### Claim 9 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.