Inference methods for word or wordpiece tokenization

Patent metadata

Field	Value
Publication number	US-12456012-B2
Application number	US-202318205609-A
Country	US
Kind code	B2
Filing date	Jun 5, 2023
Priority date	May 18, 2020
Publication date	Oct 28, 2025
Grant date	Oct 28, 2025

Abstract

Systems and methods for performing inference for word or wordpiece tokenization are disclosed using a left-to-right longest-match-first greedy process. In some examples, the vocabulary may be organized into a trie structure in which each node includes a precomputed token or token_ID and a fail link, so that the tokenizer can parse the trie in a single pass to generate a list of only those tokens or token_IDs that correspond to the longest matching vocabulary entries in the sample string, without the need for backtracking. In some examples, the vocabulary may be organized into a trie in which each node has a fail link, and any node that would share token(s) or token_ID(s) of a preceding node is instead given a prev_match link that points back to a chain of nodes with those token(s) or token_ID(s).

First claim

The invention claimed is:

1. A computer-implemented method comprising:
performing, by one or more processors of a processing system, tokenization of a string of text, comprising:
analyzing a set of nodes of a vocabulary trie structure to identify one or more links between nodes of the vocabulary trie structure corresponding to one or more characters of the string;
identifying a fail link between a pair of nodes in the set of nodes;
storing, based on the fail link, a first token representing a word or wordpiece comprised of a pair of characters of the string;
storing a second token representing a word or wordpiece comprised of another character of the string; and
concatenating the first token and the second token to form an array of tokens; and

providing, by the one or more processors, the array of tokens to a neural network for natural language processing.

2. The method of claim 1 , wherein identifying the fail link between the pair of nodes in the set of nodes includes analyzing one of the pair of nodes to determine whether that node has no link corresponding to a given character of the string.

3. The method of claim 1 , wherein the first token comprises a word or wordpiece including a first character and a second character of the string.

4. The method of claim 3 , wherein the second token includes a third character of the string.

5. The method of claim 1 , wherein the first token identifies an entry in a vocabulary for a word or wordpiece including a first character and a second character of the string.

6. The method of claim 5 , wherein the second token identifies an entry in the vocabulary for a third character of the string.

7. The method of claim 1 , wherein the string further comprises a given character that is a symbol representing the end of the string.

8. The method of claim 1 , further comprising performing the natural language processing on a segment of text using the neural network.

9. The method of claim 1 , further comprising using the fail link to arrive at a next node of the vocabulary trie structure.

10. A processing system comprising:
a memory; and
one or more processors coupled to the memory and configured to:
perform tokenization of a string of text, comprising:
analyze a set of nodes of a vocabulary trie structure to identify one or more links between nodes of the vocabulary trie structure corresponding to one or more characters of the string;
identify a fail link between a pair of nodes in the set of nodes;
store in the memory, based on the fail link, a first token representing a word or wordpiece comprised of a pair of characters of the string;
store in the memory a second token representing a word or wordpiece comprised of another character of the string; and
concatenate the first token and the second token to form an array of tokens; and

provide the array of tokens to a neural network for natural language processing.

11. The system of claim 10 , wherein identification of the fail link between the pair of nodes in the set of nodes includes analysis of one of the pair of nodes to determine whether that node has no link corresponding to a given character of the string.

12. The system of claim 10 , wherein the first token comprises a word or wordpiece including a first character and a second character of the string.

13. The system of claim 12 , wherein the second token includes a third character of the string.

14. The system of claim 10 , wherein the first token identifies an entry in a vocabulary for a word or wordpiece including a first character and a second character of the string.

15. The system of claim 14 , wherein the second token identifies an entry in the vocabulary for a third character of the string.

16. The system of claim 10 , wherein the string further comprises a given character that is a symbol representing the end of the string.

17. The system of claim 10 , wherein the one or more processors are further configured to perform the natural language processing on a segment of text via the neural network.

18. The system of claim 10 , wherein the one or more processors are further configured to us the fail link to arrive at a next node of the vocabulary trie structure.

19. A non-transitory recording medium having computer-readable instructions stored thereon, the instructions, when executed by one or more processors of a processing system:
performing tokenization of a string of text, comprising:
analyzing a set of nodes of a vocabulary trie structure to identify one or more links between nodes of the vocabulary trie structure corresponding to one or more characters of the string;
identifying a fail link between a pair of nodes in the set of nodes;
storing, based on the fail link, a first token representing a word or wordpiece comprised of a pair of characters of the string;
storing a second token representing a word or wordpiece comprised of another character of the string; and
concatenating the first token and the second token to form an array of tokens; and

providing the array of tokens to a neural network for natural language processing.

20. The recording medium of claim 19 , wherein identifying the fail link between the pair of nodes in the set of nodes includes analyzing one of the pair of nodes to determine whether that node has no link corresponding to a given character of the string.

Assignees

• Google Llc

Inventors

• Song Xinying
• Song Yang

Classifications

• G06F40/40

  Processing or translation of natural language (natural language analysis G06F40/20; semantic analysis G06F40/30) · CPC title

• G06F16/322

  Trees · CPC title

• G06F16/3334

  Selection or weighting of terms from queries, including natural language queries · CPC title

• G06F40/284 Primary

  Lexical analysis, e.g. tokenisation or collocates · CPC title

• G06F40/237 Primary

  Lexical tools · CPC title