Back to results
US 10,241,998 B1Granted
Method and system for tokenizing documents
AssigneeEMC IP Holding Company LLC
InventorsLei Zhang, Chao Chen, Jingjing Liu, Kunwu Huang, Hongtao Dai, Ying Teng
Life of this patent
Estimating the term…
Abstract
A method for tokenizing documents. The method includes obtaining a document comprising text to be tokenized, isolating a first string of consecutive characters in the document, searching, in a token tree, for an expression that matches the first string, making a determination that a matching expression exists in the token tree and, based on the determination, storing the matching expression as an extracted token.
Claims16
A method for tokenizing documents, the method comprising:
- obtaining a document comprising text to be tokenized;
- isolating a first string of consecutive characters in the document;
- generating a plurality of strings based on the first string, wherein generating the plurality of strings comprises:
- (a) dropping the last character of a copy of the first string to obtain a modified first string,
- (b) adding the modified first string to the plurality of strings,
- (c) dropping the last character of the modified first string to obtain a second modified first string,
- (d) adding the second modified first string to the plurality of strings,
- (e) repeating (c) and (d) until the second modified first string does not include any characters,
- (f) dropping the first character of a second copy of the first string to obtain a third modified first string,
- (g) dropping the last character of the third modified first string to obtain a fourth modified first string,
- (h) adding the fourth modified first string to the plurality of strings, and
- (i) repeating (g) and (h) until the third modified first string does not include any characters;
- searching, in a token tree, for expressions that match respective strings of the plurality of strings to obtain matching expressions;
- and
- store the matching expressions as extracted tokens,
- wherein the token tree comprises branches corresponding to different expressions,
- wherein a branch of the branches of the token tree comprises a plurality of nodes,
- wherein each of the plurality of nodes corresponds to a respective bit of a binary representation of an expression of the different expressions corresponding to the branch,
- wherein reading each branch of the branches from a top to a bottom of the token tree obtains a single expression of the different expressions,
- wherein searching for the expression that matches the respective strings comprises reading a branch of the branches.
17 more elements
A system for tokenizing documents, comprising:
- a computing device comprising a document tokenization engine that:
- obtains a document comprising text to be tokenized;
- isolates a first string of consecutive characters in the document;
- generates a plurality of strings based on the first string, wherein generating the plurality of strings comprises:
- (a) dropping the last character of a copy of the first string to obtain a modified first string,
- (b) adding the modified first string to the plurality of strings,
- (c) dropping the last character of the modified first string to obtain a second modified first string,
- (d) adding the second modified first string to the plurality of strings,
- (e) repeating (c) and (d) until the second modified first string does not include any characters,
- (f) dropping the first character of a second copy of the first string to obtain a third modified first string,
- (g) dropping the last character of the third modified first string to obtain a fourth modified first string,
- (h) adding the fourth modified first string to the plurality of strings, and
- (i) repeating (g) and (h) until the third modified first string does not include any characters;
- searches, in a token tree, for expressions that match respective strings of the plurality of strings to obtain matching expressions;
- and
- stores the matching expressions as extracted tokens,
- wherein the token tree comprises branches corresponding to different expressions,
- wherein a branch of the branches of the token tree comprises a plurality of nodes,
- wherein each of the plurality of nodes corresponds to a respective bit of a binary representation of an expression of the different expressions corresponding to the branch,
- wherein reading each branch of the branches from a top to a bottom of the token tree obtains a single expression of the different expressions,
- wherein searching for the expression that matches the respective strings comprises reading a branch of the branches.
18 more elements
A non-transitory computer readable medium (CRM) comprising instructions that enable a system for tokenizing documents to:
- obtain a document comprising text to be tokenized;
- isolate a first string of consecutive characters in the document;
- generate a plurality of strings based on the first string, wherein generating the plurality of strings comprises:
- (a) dropping the last character of a copy of the first string to obtain a modified first string,
- (b) adding the modified first string to the plurality of strings,
- (c) dropping the last character of the modified first string to obtain a second modified first string,
- (d) adding the second modified first string to the plurality of strings,
- (e) repeating (c) and (d) until the second modified first string does not include any characters,
- (f) dropping the first character of a second copy of the first string to obtain a third modified first string,
- (g) dropping the last character of the third modified first string to obtain a fourth modified first string,
- (h) adding the fourth modified first string to the plurality of strings, and
- (i) repeating (g) and (h) until the third modified first string does not include any characters;
- search, in a token tree, for expressions that match respective strings of the plurality of strings to obtain matching expressions;
- and
- store the matching expressions as extracted tokens,
- wherein the token tree comprises branches corresponding to different expressions,
- wherein a branch of the branches of the token tree comprises a plurality of nodes,
- wherein each of the plurality of nodes corresponds to a respective bit of a binary representation of an expression of the different expressions corresponding to the branch,
- wherein reading each branch of the branches from a top to a bottom of the token tree obtains a single expression of the different expressions,
- wherein searching for the expression that matches the respective strings comprises reading a branch of the branches.
17 more elements
Dependencies are inferred from the claim text.