METHOD AND DEVICE FOR SEARCHING CHARACTER STRING

• US 20200133981A1
• Filed: 12/31/2019
• Published: 04/30/2020
• Est. Priority Date: 03/18/2016
• Status: Active Grant

• Current Assignee: Emc IP Holding Company LLC (Dell Technologies Inc.)
• Original Assignee: Emc IP Holding Company LLC (Dell Technologies Inc.)
• Inventors: Dai, Duke Hongtao, Zhang, Winston Lei, Chen, Chao, Huang, Kun Wu, Liu, Jingjing
• Granted Patent: US 11,048,763 B2
• Time in Patent Office: Days
• CPC Class Codes: G06F 16/319 Inverted lists
• CPC Class Codes: G06F 16/334 Query execution G06F16/335 takes precedence
• CPC Class Codes: G06F 16/38 Retrieval characterised by using metadata, e.g. metadata not derived from the content or metadata generated manually
• CPC Class Codes: G06F 16/90344 by using string matching techniques
• CPC Class Codes: G06F 16/93 Document management systems

Abstract

Techniques for searching a character string involve: determining a first set of documents including a first token in the character string, and a second set of documents including a second token in the character string; and generating a third set of documents based on the first and second sets of documents, in the third set of documents: i) a document being included in the first and second sets of documents, and ii) a distance between the first and second tokens in the document being equal to a distance between the first and second tokens in the character string.

Claims

1. A method of searching a character string, comprising:

determining a plurality of sets of documents at least in part by, for each token in the character string, determining a set of documents including the token;

sorting the sets of documents in the plurality of sets of documents according to the number of documents included in each set of documents;

responsive to the sorting of the sets of documents, selecting a first set of documents including a first token in the character string, and a second set of documents including a second token in the character string, wherein the first set of documents and the second set of documents have the least numbers of documents in the plurality of sets of documents; and

generating a third set of documents based on the first and second sets of documents, wherein for each document in the third set of documents;

i) the document is included in both the first set of documents and the second set of documents, and

ii) a distance between the first token and the second token in the document is equal to a distance between the first token and the second token in the character string.

2. The method according to claim 1, wherein generating the third set of documents comprises:

selecting a candidate document that is included in both the first set of documents and the second set of documents;

determining whether a candidate distance between the first token and the second token in the candidate document is equal to the distance between the first token and the second token in the character string; and

adding the candidate document into the third set of documents in response to the candidate distance being equal to the distance between the first token and the second token in the character string.

3. The method according to claim 2, wherein selecting the candidate document that is included in both the first set of documents and the second set of documents comprises:

obtaining an intersection of the first set of documents and the second set of documents; and

selecting the candidate document from the intersection of the first set of documents and the second set of documents.

4. The method according to claim 2, wherein determining whether the candidate distance is equal to the distance between the first token and the second token in the character string comprises:

determining a first set of positions of the first token in the candidate document;

determining a second set of positions of the second token in the candidate document; and

determining, based on the first set of positions and the second set of positions, whether the candidate distance is equal to the distance between the first token and the second token in the character string.

5. The method according to claim 1, further comprising:

further responsive to the sorting of the sets of documents, selecting a fourth set of documents including a third token in the character string, wherein the fourth set of documents has the least number of documents in the remaining sets of documents;

generating a fifth set of documents based on the third set of documents and the fourth set of documents, wherein for each document in the fifth set of documents;

i) the document is included in both the third set of documents and the fourth set of documents, and

ii) a distance between the first token and the third token in the document is equal to a distance between the first token and the third token in the character string, and a distance between the second token and the third token in the document is equal to a distance between the second token and the third token in the character string.

6. The method according to claim 1, further comprising:

obtaining the first token and the second token by segmenting the character string.

7. The method according to claim 1, further comprising:

generating new sets of documents until at least one document including all tokens in the character string is found.

8. The method according to claim 1, further comprising:

generating new sets of documents until a number of documents in a newly generated set of documents is less than a predetermined threshold.

9. The method according to claim 1, wherein the distance between the first token and the second token in the document is a Euclidian distance.

10. The method according to claim 1, wherein the distance between the first token and the second token in the document is a Hamming distance.

11. The method according to claim 1, wherein the first token and second token are adjacent to each other in the document;

and

wherein the distance between the first token and the second token in the document is one.

12. The method according to claim 1, further comprising searching a position list for each document that records token positions in the document.

13. An electronic device comprising:

a processing unit configured to;

determine a plurality of sets of documents at least in part by, for each token in the character string, determining a set of documents including the token;

sort the sets of documents in the plurality of sets of documents according to the number of documents included in each set of documents;

responsive to the sorted sets of documents, select a first set of documents including a first token in the character string, and a second set of documents including a second token in the character string, wherein the first set of documents and the second set of documents have the least numbers of documents in the plurality of sets of documents; and

generate a third set of documents based on the first set of documents and the second set of documents, wherein for each document in the third set of documents;

i) the document is included in both the first set of documents and the second set of documents, and

ii) a distance between the first token and the second token in the document is equal to a distance between the first token and the second token in the character string.

14. The device according to claim 13, wherein the processing unit is further configured to:

select a candidate document that is included in both the first set of documents and the second set of documents;

determine whether a candidate distance between the first token and the second token in the candidate document is equal to the distance between the first token and the second token in the character string; and

add the candidate document into the third set of documents in response to the candidate distance being equal to the distance between the first token and the second token in the character string.

15. The device according to claim 14, wherein the processing unit is configured to:

obtain an intersection of the first set of documents and the second set of documents; and

select the candidate document from the intersection of the first set of documents and the second set of documents.

16. The device according to claim 14, wherein the processing unit is configured to:

determine a first set of positions of the first token in the candidate document;

determine a second set of positions of the second token in the candidate document; and

determine, based on the first set of positions and the second set of positions, whether the candidate distance is equal to the distance between the first token and the second token in the character string.

17. The device according to claim 13, wherein the processing unit is further configured to:

select, responsive to the sorted sets of documents, a fourth set of documents including a third token in the character string, wherein the fourth set of documents has the least number of documents in the remaining sets of documents;

generate a fifth set of documents based on the third set of documents and the fourth set of documents, wherein for each document in the fifth set of documents;

i) the document is included in both the third set of documents and the fourth set of documents, and

ii) a distance between the first token and the third token in the document is equal to a distance between the first token and the third token in the character string, and a distance between the second token and the third token in the document is equal to a distance between the second token and the third token in the character string.

18. The device according to claim 13, wherein the processing unit is further configured to:

generate new sets of documents until at least one document including all tokens in the character string is found.

19. The device according to claim 13, wherein the processing unit is further configured to:

generate new sets of documents until a number of documents in a newly generated set of documents is less than a predetermined threshold.

20. A computer program product for searching a character string, the computer program product comprising:

a non-transitory computer readable medium encoded with computer-executable code, the code configured to enable the execution of;

determining a plurality of sets of documents at least in part by, for each token in the character string, determining a set of documents including the token;

sorting the sets of documents in the plurality of sets of documents according to the number of documents in each set of documents;

responsive to the sorting of the sets of documents, selecting a first set of documents including a first token in the character string, and a second set of documents including a second token in the character string, wherein the first set of documents and the second set of documents have the least numbers of documents in the plurality of sets of documents; and

generating a third set of documents based on the first and second sets of documents, wherein for each document in the third set of documents;

i) the document is included in both the first set of documents and the second set of documents, and

ii) a distance between the first token and the second token in the document is equal to a distance between the first token and the second token in the character string.