# US 2017/0255692 A1 · Method for providing search suggestion candidates for input key and method for creating database dfa

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2017/0255692 A1
- Document ID: US20170255692A1
- Status: Published application
- Kind: A1
- Application number: 15/444,267
- Filed: 2017-02-27
- Published: 2017-09-07
- Earliest claimed: 2016-03-03
- Assignees: Qijian Software (Beijing) Co., Ltd.
- Applicants: Qijian Software (Beijing) Co., Ltd.
- Inventors: Peng LEI
- Web page: https://patentgrep.com/patent/US20170255692A1

## CPC

- G06F 16/3337: {Translation of the query language, e.g. Chinese to English}
- G06F 16/3323: {using document space presentation or visualization, e.g. category, hierarchy or range presentation and selection}
- G06F 16/3331: Query processing
- G06F 16/334: Query execution (filtering based on additional data G06F16/335)
- G06F 40/47: Machine-assisted translation, e.g. using translation memory
- G06F 40/53: Processing of non-Latin text (kana-to-kanji conversion G06F40/129; vowelisation G06F40/232)
- G06N 3/004: Artificial life, i.e. computing arrangements simulating life
- G10L 15/02: Feature extraction for speech recognition; Selection of recognition unit
- G10L 15/26: Speech to text systems (G10L15/08 takes precedence)
- G10L 15/00: Speech recognition (G10L17/00 takes precedence)
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- G06N: COMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS
- G10L: SPEECH ANALYSIS TECHNIQUES OR SPEECH SYNTHESIS; SPEECH RECOGNITION; SPEECH OR VOICE PROCESSING TECHNIQUES; SPEECH OR AUDIO CODING OR DECODING

## Abstract

A method for providing one or more search suggestion candidates for an input key comprises: (1) acquiring characteristic information of the input key; (2) creating a characteristic DFA (Deterministic Finite Automaton) of the input key based on the characteristic information of the input key; (3) searching the characteristic DFA of the input key in a predetermined database DFA having a plurality of bridge transitions each linking a bridge head state with a bridge tail state, so as to identify a bridge head state that matches the characteristic DFA of the input key, wherein each bridge head state of the predetermined database DFA corresponds to a final state of a characteristic DFA of a target candidate which is created based on characteristic information of the target candidate; and (4) outputting one or more target candidates corresponding to a bridge tail state linked with the identified bridge head state as the search suggestion candidate for the input key.

## Claims

### Claim 1

A method for providing one or more search suggestion candidates for an input key, comprising:
(1) acquiring characteristic information of the input key;
(2) creating a characteristic DFA (Deterministic Finite Automaton) of the input key based on the characteristic information of the input key;
(3) searching the characteristic DFA of the input key in a predetermined database DFA having a plurality of bridge transitions each linking a bridge head state with a bridge tail state, so as to identify a bridge head state that matches the characteristic DFA of the input key, wherein each bridge head state of the predetermined database DFA corresponds to a final state of a characteristic DFA of a target candidate which is created based on characteristic information of the target candidate; and
(4) outputting one or more target candidates corresponding to a bridge tail state linked with the identified bridge head state as the search suggestion candidate for the input key.

### Claim 2 (depends on 1)

The method of claim 1, wherein the characteristic information of the input key is obtained from a predefined characteristic information database, and wherein step (1) further comprises:
creating the predefined characteristic information database, said database storing data items and respective characteristic information associated with said data items;
determining characteristic information of all data items of the input key based on the predefined characteristic information database.

### Claim 3 (depends on 1)

The method of claim 1, wherein step (2) further comprises:
creating one or more characteristic sub-DFAs for respective data items of the input key, based on the characteristic information of the data items of the input key;
linking the characteristic sub-DFAs to obtain a characteristic NFA6 (Non-deterministic Finite Automaton) corresponding to the input key; and
converting the characteristic NFA into the characteristic DFA.

### Claim 4 (depends on 1)

The method of claim 1, wherein the predetermined database DFA is created by:
(A) acquiring a target candidate;
(B) acquiring characteristic information of the target candidate;
(C) creating a characteristic DFA of the target candidate based on the characteristic information of the target candidate;
(D) linking a final state of the characteristic DFA of the target candidate with the target candidate by a bridge transition of the plurality of bridge transitions; and
(E) adding the linked target candidate and its characteristic DFA into the predetermined database DFA, such that a final state of the characteristic DFA of the target candidate is corresponding to a bridge head state of the database DFA.

### Claim 5 (depends on 4)

The method of claim 4, wherein the target candidate is stored in DFA form, and the final state of the characteristic DFA of the target candidate is linked with the initial state of the target candidate in DFA form by the bridge transition.

### Claim 6 (depends on 4)

The method of claim 4, wherein step (E) further comprises:
adding the linked target candidate and its characteristic DFA into the database DFA incrementally.

### Claim 7 (depends on 4)

The method of claim 4, wherein step (E) further comprises:
reversing the linked target candidate and its characteristic DFA;
adding the reversed linked target candidate and its characteristic DFA into an intermediate database DFA in reverse topological order; and
reversing the intermediate database DFA to obtain the database DFA, wherein a final state of a characteristic DFA of each target candidate is prior to the initial state of the target candidate in DFA form linked therewith.

### Claim 8 (depends on 1)

The method of claim 1, further comprising:
receiving a user selection input;
selecting a search suggestion candidate according to the user selection input.

### Claim 9 (depends on 1)

The method of claim 1, wherein the method is used for user-input error correction, wherein
both of the input key and the target candidate comprise a string of Chinese characters, and
the characteristic information of the input key comprises pinyins, foreign language corresponding words, or stem components of said string of Chinese characters.

### Claim 10 (depends on 1)

The method of claim 1, wherein the method is used for Chinese text input method, wherein
the input key comprises a string of pinyin characters,
the characteristic information of the input key comprises characteristic pinyin information, and
the target candidate comprises Chinese characters.

### Claim 11 (depends on 1)

The method of claim 1, wherein the method is used for language translation, wherein
the input key comprises a text string of first language,
the characteristic information of the input key comprises characteristic information of first language, and
the target candidate comprises a text string of second language.

### Claim 12 (depends on 1)

The method of claim 1, wherein the method is used for voice recognition, wherein
the input key comprises voice input,
the characteristic information of the input key comprises vocal characteristic of the voice input, and
the target candidate comprises text.

### Claim 13

A method for creating a database DFA, wherein the database DFA has a plurality of bridge transitions each linking a bridge head state and a bridge tail state, and the method comprises:
(A) acquiring a target candidate;
(B) acquiring characteristic information of the target candidate;
(C) creating a characteristic DFA of the target candidate based on the characteristic information of the target candidate;
(D) linking a final state of the characteristic DFA of the target candidate with the target candidate by a bridge transition of the plurality of bridge transitions; and
(E) adding the linked target candidate and its characteristic DFA into the database DFA, such that the final state of the characteristic DFA is corresponding to a bridge head state of the database DFA.

### Claim 14 (depends on 13)

The method of claim 13, wherein step (B) further comprises:
creating a predefined characteristic information database, said database storing data items and respective characteristic information associated with said data items; and
determining characteristic information of all data items of the target candidate based on the predefined characteristic information database.

### Claim 15 (depends on 13)

The method of claim 13, wherein step (C) further comprises:
creating one or more characteristic sub-DFA for respective data items of the target candidate, based on the characteristic information of the data items of the target candidate;
linking the characteristic sub-DFAs to obtain a characteristic NFA corresponding to the target candidate; and
converting the characteristic NFA into the characteristic DFA.

### Claim 16 (depends on 15)

The method of claim 15, wherein the target candidate is stored in DFA form, and the final state of the characteristic DFA of the target candidate is linked with the initial state of the target candidate in DFA form by the bridge transition, and the initial state of the target candidate corresponds to a bridge tail state.

### Claim 17 (depends on 13)

The method of claim 13, wherein step (E) further comprises:
reversing the linked target candidate and its characteristic DFA;
adding the reversed linked target candidate and its characteristic DFA into an intermediate database DFA in reverse topological order; and
reversing the intermediate database DFA to obtain the database DFA, wherein a final state of a characteristic DFA of each target candidate is prior to the initial state of the target candidate in DFA form linked therewith.

### Claim 18 (depends on 13)

The method of claim 13, wherein the database DFA is used for user-input error correction, and wherein
the target candidate comprises a string of Chinese characters, and
the characteristic information of the target candidate comprises pinyin information, foreign language corresponding words, or stem components of said string of Chinese characters.

### Claim 19 (depends on 13)

The method of claim 13, wherein the database DFA is used for Chinese text input method, and wherein
the target candidate comprises Chinese characters, and
the characteristic information of the target candidate comprises characteristic pinyin information of the Chinese characters.

### Claim 20 (depends on 13)

The method of claim 13, wherein the database DFA is used for language translation, and wherein the target candidate comprises a text string of first language.

### Claim 21 (depends on 13)

The method of claim 13, wherein the database DFA is used for voice recognition, and wherein
the target candidate comprises text, and
the characteristic information of the target candidate comprises vocal characteristic of the text.

### Claim 22

An apparatus for providing one or more search suggestion candidates for an input key, comprising:
an acquisition unit for acquiring characteristic information of the input key;
a DFA creating unit for creating a characteristic DFA of the input key based on the characteristic information of the input key;
a searching unit for searching the characteristic DFA of the input key in a predetermined database DFA having a plurality of bridge transitions each linking a bridge head state with a bridge tail state, so as to identify a bridge head state that matches the characteristic DFA of the input key, wherein each bridge head state of the predetermined database DFA corresponds to a final state of a characteristic DFA of a target candidate which is created based on characteristic information of the target candidate; and
an output unit for outputting one or more target candidates corresponding to a bridge tail state linked with the identified bridge head state as the search suggestion candidate for the input key.

### Claim 23

An apparatus for creating a database DFA, wherein the database DFA has a plurality of bridge transitions each linking a bridge head state and a bridge tail state, and the apparatus comprises:
a data acquisition unit for acquiring a target candidate;
an information acquisition unit for acquiring characteristic information of the target candidate;
a creating unit for creating a characteristic DFA of the target candidate based on the characteristic information of the target candidate;
a linking unit for linking a final state of the characteristic DFA of the target candidate with the target candidate by a bridge transition of the plurality of bridge transitions; and
an adding unit for adding the linked target candidate and its characteristic DFA into the database DFA, such that the final state of the characteristic DFA is corresponding to a bridge head state of the database DFA.

### Claim 24

A computer program product for providing one or more search suggestion candidates for an input key, wherein the computer program product comprising a non-transitory computer readable storage medium including instructions executable by a processor to cause the processor to perform:
(1) acquiring characteristic information of the input key;
(2) creating a characteristic DFA (Deterministic Finite Automaton) of the input key based on the characteristic information of the input key;
(3) searching the characteristic DFA of the input key in a predetermined database DFA having a plurality of bridge transitions each linking a bridge head state with a bridge tail state, so as to identify a bridge head state that matches the characteristic DFA of the input key, wherein each bridge head state of the predetermined database DFA corresponds to a final state of a characteristic DFA of a target candidate which is created based on characteristic information of the target candidate; and
(4) outputting one or more target candidates corresponding to a bridge tail state linked with the identified bridge head state as the search suggestion candidate for the input key.

### Claim 25

A computer program product for creating a database DFA having a plurality of bridge transitions each linking a bridge head state and a bridge tail state, wherein the computer program product comprising a non-transitory computer readable storage medium including instructions for performing:
(A) acquiring a target candidate;
(B) acquiring characteristic information of the target candidate;
(C) creating a characteristic DFA of the target candidate based on the characteristic information of the target candidate;
(D) linking a final state of the characteristic DFA of the target candidate with the target candidate by a bridge transition of the plurality of bridge transitions; and
(E) adding the linked target candidate and its characteristic DFA into the database DFA, such that the final state of the characteristic DFA is corresponding to a bridge head state of the database DFA.