Method and device for searching character string

• US 10,546,024 B2
• Filed: 03/20/2017
• Issued: 01/28/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
• Primary Examiner(s): Trujillo, James
• Assistant Examiner(s): Shechtman, Cheryl M
• Application Number:
  US15/463,010
• Publication Number:
  US 20170270114A1
• Time in Patent Office: 1,044 Days
• Field of Search: None
• 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 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 both 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.

2. The method according to claim 1, wherein the determining comprises:

determining a plurality of sets of documents including a plurality of tokens in the character string; and

selecting the first and second sets of documents from the plurality of sets of documents in an ascending order of the numbers of documents included in the plurality of sets of documents.

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

selecting a candidate document included in both the first and second sets of documents;

determining whether a candidate distance between the first and second tokens in the candidate document is equal to the distance between the first and second tokens 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.

4. The method according to claim 3, wherein the selecting comprises:

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

selecting the candidate document from the intersection.

5. The method according to claim 3, wherein the determining whether a candidate distance is equal to the distance 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 and second sets of positions, whether the candidate distance is equal to the distance between the first and second tokens in the character string.

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

determining a fourth set of documents including a third token in the character string;

generating a fifth set of documents based on the third and fourth sets of documents, in the fifth set of documents;

i) a document being included in both the third and fourth sets of documents, and

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

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

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

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

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

10. The method according to claim 1, wherein the distance between the first and second tokens in the document is one.

11. The method according to claim 1, wherein the first and second tokens are adjacent to each other.

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

13. An electronic device comprising:

a processing unit configured to;

determine 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 both 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.

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

determine a plurality of sets of documents including a plurality of tokens in the character string; and

select the first and second sets of documents from the plurality of set of documents in an ascending order of the numbers of documents included in the plurality of sets of documents.

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

Select a candidate document included in both the first and second sets of documents;

determine whether a candidate distance between the first and second tokens in the candidate document is equal to the distance between the first and second tokens 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.

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

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

select the candidate document from the intersection.

17. The device according to claim 15, 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 and second sets of positions, whether the candidate distance is equal to the distance between the first and second tokens in the character string.

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

determine a fourth set of documents including a third token in the character string;

generate a fifth set of documents based on the third and fourth sets of documents, in the fifth set of documents;

i) a document being included in both the third and fourth sets of documents, and

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

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

obtain the first and second tokens by segmenting the character string.

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 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 both 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.