Natural language understanding using vocabularies with compressed serialized tries

Patent metadata

Field	Value
Publication number	US-10445429-B2
Application number	US-201815867480-A
Country	US
Kind code	B2
Filing date	Jan 10, 2018
Priority date	Sep 21, 2017
Publication date	Oct 15, 2019
Grant date	Oct 15, 2019

Abstract

Systems and processes for natural language processing using vocabularies with compressed serialized tries are described in the present disclosure. In one example process, natural language input is received. The natural language input is parsed, using a vocabulary, to determine a corresponding user intent. The parsing includes using a data structure of the vocabulary to map a first word of the natural language input to first semantic information and a second word of the natural language input to second semantic information. The data structure includes pointers that map to a same semantic data object of the vocabulary. The first semantic information and the second semantic information are determined using the same semantic data object. The user intent is determined based on the first semantic information and the second semantic information. Performance of a task corresponding to the determined user intent is initiated.

First claim

What is claimed is:

1. An electronic device, comprising:
one or more processors;
memory; and
one or more programs, wherein the one or more programs are stored in the memory and configured to be executed by the one or more processors, the one or more programs including instructions for:
receiving natural language input;
determining, using a vocabulary, first semantic information for a first word of the natural language input;
determining, using the vocabulary, second semantic information for a second word of the natural language input, wherein a portion of the first semantic information is identical to a portion of the second semantic information, and wherein:
the vocabulary includes a data structure comprising a first sequence of states representing the first word and a second sequence of states representing the second word;
a state of the first sequence of states includes a pointer to a semantic data object of the vocabulary;
a state of the second sequence of states includes a pointer to the semantic data object; and
the portion of the first semantic information and the portion of the second semantic information are determined from the semantic data object;

determining, using the first semantic information and the second semantic information, a user intent corresponding to the natural language input; and
initiating performance of a task corresponding to the determined user intent.

2. The device of claim 1 , wherein the semantic data object is a unique data object in the vocabulary.

3. The device of claim 1 , wherein the semantic data object is stored separately from the data structure.

4. The device of any of claim 1 , wherein the data structure is a compressed serialized trie.

5. The device of claim 1 , wherein the state of the first sequence of states includes a plurality of data pointers that each point to a respective data value of a plurality of data values in a binary data object, and wherein each data value of the plurality of data values contains a respective portion of the first semantic information.

6. The device of claim 5 , wherein each data pointer of the plurality of data points includes a start address and an end address that defines a location of the respective data value in the binary data object.

7. The device of claim 5 , wherein each respective data value of the plurality of data values is allocated a memory amount in the binary data object that is equal to the minimum amount of memory required to store the respective data value.

8. The device of claim 1 , wherein the data structure is generated by an external device separate from the electronic device.

9. The device of claim 8 , wherein the data structure is generated from one or more unstructured vocabulary flat files.

10. The device of claim 8 , further comprising:
receiving the data structure from the external device; and
initializing a natural language processing service of the electronic device by loading the data structure.

11. The device of claim 10 , further comprising:
receiving an updated data structure generated by the external device; and
after receiving the updated data structure, re-initializing a natural language processing service of the electronic device by loading the updated data structure in lieu of the data structure.

12. The device of claim 1 , wherein the data structure is a character trie.

13. The device of claim 1 , wherein the state of the first sequence of states and the state of the second sequence of states are each terminal states of the data structure.

14. The device of claim 1 , wherein the state of the first sequence of states maps to a plurality of semantic interpretations of the first word, and wherein each semantic interpretation of the plurality of semantic interpretations includes a respective domain of an ontology and one or more properties of the respective domain.

15. The device of claim 14 , wherein each semantic interpretation of the plurality of semantic interpretations further includes a respective saliency value of the first word.

16. The device of claim 14 , wherein each semantic interpretation of the plurality of semantic interpretations further includes a respective confidence value for the respective domain.

17. The device of claim 14 , wherein each semantic interpretation of the plurality of semantic interpretations further includes one or more interpretation rules.

18. The device of claim 1 , wherein the state of the first sequence of states includes one or more first data pointers that each point to a respective semantic data object of a plurality of semantic data objects, wherein the state of the second sequence of states includes one or more second data pointers that each point to a respective semantic data object of the plurality of semantic data objects, and wherein each semantic data object of the plurality of semantic data objects is a unique in the vocabulary.

19. A method for performing natural language processing, the method comprising:
at an electronic device having a processor and memory:
receiving natural language input;
determining, using a vocabulary, first semantic information for a first word of the natural language input;
determining, using the vocabulary, second semantic information for a second word of the natural language input, wherein a portion of the first semantic information is identical to a portion of the second semantic information, and wherein:
the vocabulary includes a data structure comprising a first sequence of states representing the first word and a second sequence of states representing the second word;
a state of the first sequence of states includes a pointer to a semantic data object of the vocabulary;
a state of the second sequence of states includes a pointer to the semantic data object; and
the portion of the first semantic information and the portion of the second semantic information are determined from the semantic data object;

determining, using the first semantic information and the second semantic information, a user intent corresponding to the natural language input; and
initiating performance of a task corresponding to the determined user intent.

20. A non-transitory computer-readable storage medium storing one or more programs configured to be executed by one or more processors of an electronic device, the one or more programs including instructions for:
receiving natural language input;
determining, using a vocabulary, first semantic information for a first word of the natural language input;
determining, using the vocabulary, second semantic information for a second word of the natural language input, wherein a portion of the first semantic information is identical to a portion of the second semantic information, and wherein:
the vocabulary includes a data structure comprising a first sequence of states representing the first word and a second sequence of states representing the second word;
a state of the first sequence of states includes a pointer to a semantic data object of the vocabulary;
a state of the second sequence of states includes a pointer to the semantic data object; and
the portion of the first semantic information and the portion of the second semantic information are determined from the semantic data object;

determining, using the first semantic information and the second semantic information, a user intent corresponding to the natural language input; and
initiating performance of a task corresponding to the determined user intent.

Assignees

• Apple Inc

Inventors

• Seyed Ibrahim Mubarak Ali
• Garcia Juan C
• Shah Rushin N
• Treadgold Nicholas K
• Brinegar Justin J
• Aneja Gagan
• Qian Alan

Classifications

• G06F40/30 Primary

  Semantic analysis · CPC title

• G06F40/205

  Parsing · CPC title

• G10L15/1815

  Semantic context, e.g. disambiguation of the recognition hypotheses based on word meaning · CPC title

• G10L15/26

  Speech to text systems (G10L15/08 takes precedence) · CPC title

• G10L15/22

  Procedures used during a speech recognition process, e.g. man-machine dialogue · CPC title