CN102779189B - Method and system for analyzing expressions - Google Patents
Method and system for analyzing expressions Download PDFInfo
- Publication number
- CN102779189B CN102779189B CN201210227200.1A CN201210227200A CN102779189B CN 102779189 B CN102779189 B CN 102779189B CN 201210227200 A CN201210227200 A CN 201210227200A CN 102779189 B CN102779189 B CN 102779189B
- Authority
- CN
- China
- Prior art keywords
- prefix
- character string
- character
- expression
- binary tree
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Active
Links
- 230000014509 gene expression Effects 0.000 title claims abstract description 138
- 238000000034 method Methods 0.000 title claims abstract description 27
- 238000000605 extraction Methods 0.000 claims description 13
- 238000010276 construction Methods 0.000 claims description 9
- 239000000203 mixture Substances 0.000 claims description 6
- 239000000284 extract Substances 0.000 claims description 4
- 238000010586 diagram Methods 0.000 description 4
- 230000009286 beneficial effect Effects 0.000 description 1
- 238000004891 communication Methods 0.000 description 1
- 230000007423 decrease Effects 0.000 description 1
- 238000005516 engineering process Methods 0.000 description 1
- 239000004615 ingredient Substances 0.000 description 1
Landscapes
- Machine Translation (AREA)
Abstract
The invention discloses a method and a system for analyzing expressions. The method comprises the steps of: constructing an expression balanced binary tree and a prefix balanced binary tree according to expression codes, wherein nodes in the expression balanced binary tree are expression codes, and nodes in the prefix balanced binary tree are prefix sub character clusters; and retrieving a target text from the target text by using the expression balanced binary tree and the prefix balanced binary tree and analyzing the expression codes from the target text. The method and the system for analyzing expressions can solve the problem of low expression analyzing speed.
Description
Technical field
The present invention relates to computer realm, particularly a kind of method and system of resolving of expressing one's feelings.
Background technology
IM(Instant Message, instant message) instrument become means of communication indispensable in people's daily life and work.Along with the increasing of user of smart mobile phone, operate in IM instrument on smart mobile phone also more and more abundanter etc.Can send and receive expression is that IM applies an important ingredient, and the IM application lacking expression can bring the decline of Consumer's Experience.On intelligent mobile phone platform, processor speed is limited, and internal memory is also comparatively nervous, in this case, how to improve the speed that expression is resolved, takies less internal memory, just seem particularly important.
When carrying out expression parsing in prior art, multiway tree is used to travel through.For given expression code collection, when creating the multiway tree for storing expression code, needing in a program to use hard coded to each expression code, being unfavorable for the expansion of expressing one's feelings.When this multiway tree of use carries out expression parsing, traversal speed causes expression resolution speed slow slowly.
Summary of the invention
The invention provides a kind of method and system of resolving of expressing one's feelings, to solve the slow problem of expression resolution speed.
The invention discloses a kind of method of resolving of expressing one's feelings, described method comprises:
According to expression code construction expression balanced binary tree and prefix balanced binary tree, expression balanced binary tree interior joint is expression code; Prefix balanced binary tree interior joint is prefix substring in expression code;
Utilize expression balanced binary tree and prefix balanced binary tree to retrieve target text from target text, from target text, parse expression code.
Wherein, described utilization expression balanced binary tree and prefix balanced binary tree are retrieved from target text target text, parse expression code and specifically comprise from target text:
From target text, get the original character of character as current parse character string, resolve current parse character string as follows,
Step 1, retrieves current parse character string in expression balanced binary tree, if retrieved, then performs step 2, if do not retrieved, then performs step 3;
Step 2, determines that current parse character string is for expression code;
Step 3, retrieves current parse character string in prefix balanced binary tree, if retrieved, then from target text, gets character late add in current parse character string, performs step 1, if do not retrieved, then performs step 4;
Step 4, determines that current parse character string is not expression code.
Wherein, describedly specifically to comprise according to expression code construction prefix balanced binary tree:
Prefix substring is extracted, composition prefix sets from each expression code;
For same prefix substring multiple in prefix sets, retain one in prefix sets;
Prefix balanced binary tree is built according to prefix sets.
Wherein, described character of getting from target text specifically comprises as the original character of current parse character string:
If the current parse character string of resolving last time is expression code, then from target text, get the character late of last character in the current parse character string of resolving last time, as the original character of the current parse character string that this is resolved.
Wherein, described character of getting from target text specifically comprises as the original character of current parse character string:
If the current parse character string of resolving last time is not expression code, then from target text, get the character late of the original character of the current parse character string that last time resolves, as the original character of the current parse character string that this is resolved.
Wherein, described step 2 also comprises:
According to the expression of the expression code determination current parse character string representative retrieved.
The invention also discloses a kind of system of resolving of expressing one's feelings, described system comprises:
Balanced binary tree builds module, and for express one's feelings according to expression code construction balanced binary tree and prefix balanced binary tree, expression balanced binary tree interior joint is expression code; Prefix balanced binary tree interior joint is prefix substring in expression code;
Text resolution module, for utilizing expression balanced binary tree and prefix balanced binary tree to retrieve from target text target text, parses expression code from target text.
Wherein, described text resolution module specifically comprises:
Character extraction unit, for getting the original character of character as current parse character string from target text, calling expression judging unit and starting to resolve current parse character string,
Expression judging unit, for retrieving current parse character string in expression balanced binary tree, if retrieved, then determines that current parse character string is for expression code, and calls character extraction unit, if do not retrieved, then call prefix judging unit;
Prefix judging unit, for retrieving current parse character string in prefix balanced binary tree, if retrieved, from target text, then get character late adds in current parse character string, call expression judging unit, if do not retrieved, then determine that current parse character string is not expression code, and call character extraction unit.
Wherein, described balanced binary tree build module specifically for: from each expression code, extract prefix substring, composition prefix sets; For same prefix substring multiple in prefix sets, retain one in prefix sets; Prefix balanced binary tree is built according to prefix sets.
Wherein, described character extraction unit specifically for:
If the current parse character string of resolving last time is expression code, then from target text, get the character late of last character in the current parse character string of resolving last time, as the original character of the current parse character string that this is resolved;
And/or,
If the current parse character string of resolving last time is not expression code, then from target text, get the character late of the original character of the current parse character string that last time resolves, as the original character of the current parse character string that this is resolved.
The invention has the beneficial effects as follows: by building expression balanced binary tree and prefix balanced binary tree, in expression balanced binary tree and prefix balanced binary tree, carry out retrieval to resolve expression from target text, the speed that expression is resolved can be improved, more adapt to the limited terminal device of the processing speeds such as smart mobile phone.
Accompanying drawing explanation
Fig. 1 is that the present invention expresses one's feelings the process flow diagram of method of resolving.
Fig. 2 is the method flow diagram of resolving current parse character string in the specific embodiment of the invention.
Fig. 3 is that the present invention expresses one's feelings the process flow diagram of embodiment of the method for resolving.
Fig. 4 is that the present invention expresses one's feelings the structural drawing of system of resolving.
Fig. 5 is the structural drawing of specific embodiment of the invention Chinese version parsing module.
Embodiment
For making the object, technical solutions and advantages of the present invention clearly, below in conjunction with accompanying drawing, embodiment of the present invention is described further in detail.
See Fig. 1, it is the flow process of the method that expression provided by the invention is resolved.
Described method comprises the steps.
Step S100, according to expression code construction expression balanced binary tree and prefix balanced binary tree.
Expression balanced binary tree interior joint is expression code; Prefix balanced binary tree interior joint is prefix substring in expression code.
Step S200, utilizes expression balanced binary tree and prefix balanced binary tree to retrieve target text, parses expression code from target text.
Wherein, prefix substring be in expression code first character to the character string of each character except last character.Namely coded representation of expressing one's feelings is: E
0e
1... E
i... E
m, wherein E
ifor i-th character of this emoticon, then the prefix substring of this expression code comprises: E
0, E
0e
1..., E
0e
1... E
i..., E
0e
1... E
i... E
m-1.
In the present invention, character string can be a character or multiple character.
In an embodiment, the idiographic flow that described step S200 realizes as shown in Figure 2.
From target text, get the original character of character as current parse character string, resolve current parse character string as follows.
Step S210, retrieves current parse character string in expression balanced binary tree, if retrieved, then performs step S220, if do not retrieved, then performs step S230.
Step S220, determines that current parse character string is for expression code.
Step S230, retrieves current parse character string in prefix balanced binary tree, if retrieved, then performs step S250, if do not retrieved, then performs step S240.
Step S240, determines that current parse character string is not expression code.
Step S250, gets character late and adds in current parse character string from target text, performs step S210
Further, step S220 also comprises: according to the expression of the expression code determination current parse character string representative retrieved.
In an embodiment, describedly specifically to comprise according to expression code construction prefix balanced binary tree:
Step S110, extracts prefix substring, composition prefix sets from each expression code.
Step S120, for same prefix substring multiple in prefix sets, retains one in prefix sets.
Step S130, builds prefix balanced binary tree according to prefix sets.
Such as, the set that code of expressing one's feelings forms is { ab, abc, abd, ba, bd, bca, bcd}.Utilize the method for known structure balanced binary tree according to this set, build expression balanced binary tree.
The prefix substring of expression code ab comprises: a.
The prefix substring of expression code abc comprises: a, ab.
The prefix substring of expression code abd comprises: a, ab.
The prefix substring of expression code ba comprises: b.
The prefix substring of expression code bd comprises: b.
The prefix substring of expression code bca comprises: b, bc.
The prefix substring of expression code bcd comprises: b, bc.
Remove wherein repeating part, final prefix sets { a, ab, b, bc}.
Initial prefix balanced binary tree is empty, by known balanced binary tree constructing method, character string in prefix sets is inserted in prefix balanced binary tree.
In one preferably embodiment, described character of getting from target text specifically comprises as the original character of current parse character string:
If the current parse character string of resolving last time is expression code, then from target text, get the character late of last character in the current parse character string of resolving last time, as the original character of the current parse character string that this is resolved.
In one preferably embodiment, described character of getting from target text specifically comprises as the original character of current parse character string:
If the current parse character string of resolving last time is not expression code, then from target text, get the character late of the original character of the current parse character string that last time resolves, as the original character of the current parse character string that this is resolved.
Embodiment
See Fig. 3, for the present invention expresses one's feelings the process flow diagram of embodiment of the method for resolving.
In an embodiment, text parameter text is set, for preserving the non-expression character string parsed, prefix parameter prefix is set, for preserving the current parse character string that this is resolved.Step S301, carries out initialization, and parameter text and prefix is put sky.
Step S302, judges that whether target text is scanned, if so, then performs step S308, otherwise, perform step S303.
Step S303, adds current character in got target text in prefix.
When initial, get first character in target text and add in prefix.
After initial, at every turn all for the character late getting current character is current character, add prefix.
Step S304, retrieves prefix in expression balanced binary tree, judges whether prefix is expression code, if so, then performs step S305, otherwise, perform step S306.
Step S305, preserves text, is preserved by prefix, empties text and prefix.
Step S306, retrieves prefix in prefix balanced binary tree, judges whether prefix is prefix substring, if so, then performs step S302, otherwise, perform step S307.
Step S307, is pressed onto in text by the first character of prefix, current character backtracking length(prefix)-1 position, empty prefix.
Step S308, is pressed into prefix in text, is preserved by text, empties prefix.
To technical scheme of the present invention (hereinafter referred to as redaction) be used to carry out Performance comparision with using the old technical scheme (hereinafter referred to as legacy version) of multiway tree, result be as follows.
1, test case comprises 500 general character, not expression
Legacy version: run this test case 1000 times, 7000 milliseconds consuming time;
Redaction: run this test case 2000 times, 3000 milliseconds consuming time;
2, test case only comprises 200 expressions:
Legacy version: run this test case 2000 times, 117000 milliseconds consuming time;
Redaction: run this test case 2000 times, 27000 milliseconds consuming time;
3, test case comprises 400 characters, wherein expression and plain text mixing:
Legacy version: run this test case 2000 times, 29000 milliseconds consuming time;
Redaction: run this test case 2000 times, 9000 milliseconds consuming time.
A kind of structure of the system of resolving of expressing one's feelings as shown in Figure 4.
Balanced binary tree builds module 100, and for express one's feelings according to expression code construction balanced binary tree and prefix balanced binary tree, expression balanced binary tree interior joint is expression code; Prefix balanced binary tree interior joint is prefix substring in expression code;
Text resolution module 200, for utilizing expression balanced binary tree and prefix balanced binary tree to retrieve from target text target text, parses expression code from target text.
See Fig. 5, it is the structural drawing of specific embodiment of the invention Chinese version parsing module.
In one preferably embodiment, described text resolution module 200 specifically comprises:
Character extraction unit 210, for getting the original character of character as current parse character string from target text, calling expression judging unit 220 and starting to resolve current parse character string.
Expression judging unit 220, for retrieving current parse character string in expression balanced binary tree, if retrieved, then determines that current parse character string is for expression code, and calls character extraction unit 210, if do not retrieved, then call prefix judging unit 230.
Prefix judging unit 230, for retrieving current parse character string in prefix balanced binary tree, if retrieved, from target text, then get character late adds in current parse character string, call expression judging unit 220, if do not retrieved, then determine that current parse character string is not expression code, and call character extraction unit 210.
In one preferably embodiment, described balanced binary tree build module 100 specifically for: from each expression code, extract prefix substring, composition prefix sets; For same prefix substring multiple in prefix sets, retain one in prefix sets; Prefix balanced binary tree is built according to prefix sets.
In one preferably embodiment, described character extraction unit 210 specifically for:
If the current parse character string of resolving last time is expression code, then from target text, get the character late of last character in the current parse character string of resolving last time, as the original character of the current parse character string that this is resolved;
In one preferably embodiment, described character extraction unit 210 specifically for:
If the current parse character string of resolving last time is not expression code, then from target text, get the character late of the original character of the current parse character string that last time resolves, as the original character of the current parse character string that this is resolved.
The foregoing is only preferred embodiment of the present invention, be not intended to limit protection scope of the present invention.All any amendments done within the spirit and principles in the present invention, equivalent replacement, improvement etc., be all included in protection scope of the present invention.
Claims (8)
1. express one's feelings resolve a method, it is characterized in that, described method comprises:
According to expression code construction expression balanced binary tree and prefix balanced binary tree, expression balanced binary tree interior joint is expression code; Prefix balanced binary tree interior joint is prefix substring in expression code;
Utilize expression balanced binary tree and prefix balanced binary tree to retrieve target text from target text, from target text, parse expression code;
Wherein, describedly specifically to comprise according to expression code construction prefix balanced binary tree:
Prefix substring is extracted, composition prefix sets from each expression code;
For same prefix substring multiple in prefix sets, retain one in prefix sets;
Prefix balanced binary tree is built according to prefix sets.
2. method according to claim 1, is characterized in that,
Described utilization expression balanced binary tree and prefix balanced binary tree are retrieved from target text target text, parse expression code and specifically comprise from target text:
From target text, get the original character of character as current parse character string, resolve current parse character string as follows,
Step 1, retrieves current parse character string in expression balanced binary tree, if retrieved, then performs step 2, if do not retrieved, then performs step 3;
Step 2, determines that current parse character string is for expression code;
Step 3, retrieves current parse character string in prefix balanced binary tree, if retrieved, then from target text, gets character late add in current parse character string, performs step 1, if do not retrieved, then performs step 4;
Step 4, determines that current parse character string is not expression code.
3. method according to claim 2, is characterized in that,
Described character of getting from target text specifically comprises as the original character of current parse character string:
If the current parse character string of resolving last time is expression code, then from target text, get the character late of last character in the current parse character string of resolving last time, as the original character of the current parse character string that this is resolved.
4. method according to claim 2, is characterized in that,
Described character of getting from target text specifically comprises as the original character of current parse character string:
If the current parse character string of resolving last time is not expression code, then from target text, get the character late of the original character of the current parse character string that last time resolves, as the original character of the current parse character string that this is resolved.
5. method according to claim 2, is characterized in that,
Described step 2 also comprises:
According to the expression of the expression code determination current parse character string representative retrieved.
6. express one's feelings resolve a system, it is characterized in that, described system comprises:
Balanced binary tree builds module, and for express one's feelings according to expression code construction balanced binary tree and prefix balanced binary tree, expression balanced binary tree interior joint is expression code; Prefix balanced binary tree interior joint is prefix substring in expression code;
Text resolution module, for utilizing expression balanced binary tree and prefix balanced binary tree to retrieve from target text target text, parses expression code from target text;
Wherein, described balanced binary tree build module specifically for: from each expression code, extract prefix substring, composition prefix sets; For same prefix substring multiple in prefix sets, retain one in prefix sets; Prefix balanced binary tree is built according to prefix sets.
7. system according to claim 6, is characterized in that,
Described text resolution module specifically comprises:
Character extraction unit, for getting the original character of character as current parse character string from target text, calling expression judging unit and starting to resolve current parse character string,
Expression judging unit, for retrieving current parse character string in expression balanced binary tree, if retrieved, then determines that current parse character string is for expression code, and calls character extraction unit, if do not retrieved, then call prefix judging unit;
Prefix judging unit, for retrieving current parse character string in prefix balanced binary tree, if retrieved, from target text, then get character late adds in current parse character string, call expression judging unit, if do not retrieved, then determine that current parse character string is not expression code, and call character extraction unit.
8. system according to claim 7, is characterized in that,
Described character extraction unit specifically for:
If the current parse character string of resolving last time is expression code, then from target text, get the character late of last character in the current parse character string of resolving last time, as the original character of the current parse character string that this is resolved;
And/or,
If the current parse character string of resolving last time is not expression code, then from target text, get the character late of the original character of the current parse character string that last time resolves, as the original character of the current parse character string that this is resolved.
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN201210227200.1A CN102779189B (en) | 2012-06-30 | 2012-06-30 | Method and system for analyzing expressions |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN201210227200.1A CN102779189B (en) | 2012-06-30 | 2012-06-30 | Method and system for analyzing expressions |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| CN102779189A CN102779189A (en) | 2012-11-14 |
| CN102779189B true CN102779189B (en) | 2015-01-14 |
Family
ID=47124101
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN201210227200.1A Active CN102779189B (en) | 2012-06-30 | 2012-06-30 | Method and system for analyzing expressions |
Country Status (1)
| Country | Link |
|---|---|
| CN (1) | CN102779189B (en) |
Families Citing this family (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN107886568B (en) * | 2017-12-09 | 2020-03-03 | 东方梦幻文化产业投资有限公司 | Method and system for reconstructing facial expression by using 3D Avatar |
Citations (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN1504912A (en) * | 2002-12-05 | 2004-06-16 | �Ҵ���˾ | Performance and memory bandwidth utilization for tree searches using tree fragmentation |
| CN101089810A (en) * | 2006-06-13 | 2007-12-19 | 上海海加网络科技有限公司 | A SessionCache Method Based on Binary Balanced Tree |
| CN101567014A (en) * | 2009-06-04 | 2009-10-28 | 福建星网锐捷网络有限公司 | Equipment information retrieval method, device and cable fastener |
-
2012
- 2012-06-30 CN CN201210227200.1A patent/CN102779189B/en active Active
Patent Citations (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN1504912A (en) * | 2002-12-05 | 2004-06-16 | �Ҵ���˾ | Performance and memory bandwidth utilization for tree searches using tree fragmentation |
| CN101089810A (en) * | 2006-06-13 | 2007-12-19 | 上海海加网络科技有限公司 | A SessionCache Method Based on Binary Balanced Tree |
| CN101567014A (en) * | 2009-06-04 | 2009-10-28 | 福建星网锐捷网络有限公司 | Equipment information retrieval method, device and cable fastener |
Also Published As
| Publication number | Publication date |
|---|---|
| CN102779189A (en) | 2012-11-14 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| CN107561564B (en) | A kind of compression implementation method of big-dipper satellite information transmission | |
| CN102111505B (en) | Short message prompting display method for mobile terminal | |
| CN103037072A (en) | Implementation method of extracting short message contents to apply to scene | |
| CN102801859B (en) | Method and device for identifying junk short message, and mobile communication terminal with device | |
| CN103167167B (en) | Mobile terminal and extraction method of communication contact person information | |
| CN103488796B (en) | Based on context the method and mobile terminal inputted | |
| CN102135814A (en) | Word input method and system | |
| CN103853703A (en) | Information processing method and electronic equipment | |
| CN102821182B (en) | Automatic phone directory contact matching method for handheld device | |
| CN102946474B (en) | Method and device for automatically sharing contact information of contacts and mobile terminal | |
| CN105323392A (en) | Method and apparatus for quickly entering IVR menu | |
| CN108932069A (en) | Input method candidate entry determines method, apparatus, equipment and readable storage medium storing program for executing | |
| CN103838713A (en) | Semantics analyzing method based on regular expression | |
| CN115061751A (en) | Plug-in loading method, plug-in loading device, electronic device and storage medium | |
| CN102170618A (en) | Short message processing method and equipment | |
| CN102779189B (en) | Method and system for analyzing expressions | |
| CN109660672A (en) | Conversion method, equipment and the computer readable storage medium of sound-type | |
| CN104765727A (en) | Text translation method and device | |
| CN105120046A (en) | Method and device for creating address book according to note information of new number | |
| WO2017071190A1 (en) | Input data processing method, apparatus and device, and non-volatile computer storage medium | |
| CN1322401C (en) | Communications terminal apparatus, reception apparatus, and method therefor | |
| CN116894016A (en) | Log compression method and device for rail transit signals | |
| CN100440778C (en) | Device and method for recognizing quick response codes run on mobile terminals | |
| CN110941946A (en) | Information extraction method, device, equipment and storage medium | |
| CN104935716A (en) | Method and device for displaying Uigur-Kazaksatan-Khalkas language of mobile phone call area |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| C06 | Publication | ||
| PB01 | Publication | ||
| C10 | Entry into substantive examination | ||
| SE01 | Entry into force of request for substantive examination | ||
| C14 | Grant of patent or utility model | ||
| GR01 | Patent grant | ||
| CP02 | Change in the address of a patent holder |
Address after: Room 818, 8 / F, 34 Haidian Street, Haidian District, Beijing 100080 Patentee after: BEIJING ULTRAPOWER SOFTWARE Co.,Ltd. Address before: 100089 Beijing city Haidian District wanquanzhuang Road No. 28 Wanliu new building 6 storey block A Room 601 Patentee before: BEIJING ULTRAPOWER SOFTWARE Co.,Ltd. |
|
| CP02 | Change in the address of a patent holder |