TW575813B - System and method using external search engine as foundation for segmentation of word - Google Patents

Description

575813

FIELD OF THE INVENTION ... This invention uses external search to guide the integration of the arrogant system and method, which can be applied to knowledge management or text, and the basis of word segmentation. The present invention is about search (including data mini ng) search including ， Or special 疋 • xishu or file photo S3 Μ

Uilarity) processing of file vector operations. Off

Data mining or search technology often uses keywords ^ iL: However, the recent mainstream technology takes the entire file as input: 杳 ^ files, to search for other related files, this is the file difficulty: difference; However, for the purpose of document correlation calculation, we must first convert all the text to a vector type, that is, select the meaningful words and phrases in an article as the components in the file vector, and then count the components in a document. The number of occurrences in a file can form a file vector in this way; but how to obtain an effective vocabulary to quickly convert a file into a vector must rely on more efficient word segmentation techniques (s egmen tat i on of word). It can be applied to the correlation analysis of documents, and the effective vocabulary broken out can also provide applications such as auto abstract, document classification, and information retrieval. However, before processing word segmentation, statistics and calculations must be performed in the document database, various possible groups of words must be tested, and the most commonly used words must be screened to form the thesaurus. Vocabulary breaks sentences in a file into a set of meaningful and effective words

V. Description of the invention (2) File vector; if the file is large at this time, the number of valid words in the thesaurus indicates that the more the statistical basis is, the more the keywords of the file are cut off, and the more complete and rapid the statistical basis is. The smaller it is, the smaller it is. On the contrary, if the database is smaller, it means that the entire document will be closed ^ ^ "The number of vocabulary is also small, usually it ca n’t complete the fruit and loses its meaning.… The company broke it out, making the files related. "The two huge texts of sexual operations" must be established before the time and the time, will be both ;; if this word segmentation is different, the cost it takes is a problem. This has become the primary solution of the present invention to make the largest and largest database of = ok "Internet tennis. The database provided by A, 罔 1v, and the Internet itself is an inexhaustible source of network resources. Source: t save cost, ==== basis, statistics come = statistics source text finder :: engine to do data and data 'through the calculation of word feature values, library ::-come, not only the thesaurus is more complete, ΐ :; 厐 The cost of Big Baker's library and the use of computer resources. A brief description of Deng a The main purpose of the present invention is a system of word segmentation and to provide an external search engine as a method to enable it to filter out effective words. Form the word 575813 V. Description of the invention (3) The library further converts the file into a vector, and provides the file correlation operation. ^ In order to achieve the above purpose, first set the threshold value of the word feature ^ in the local system in advance, and then separately Enter the word you want to test and all of it may be grouped into an external search engine for a general query, and wait for the external search engine to return: After the title page, receive the statistics and perform the word feature value calculation. If the feature value of a word is greater than or equal to a preset threshold, the 5 divisions are regarded as valid vocabulary and added to the thesaurus. The purpose of establishing a thesaurus with this system is to quickly break an article 1 to 4 Word vectors combined with words and phrases, so that related documents can be converted into file vectors combined with commonly used words. For example, all the common words (words) appearing in the file are arranged. The group can be two-letter letters. Sundial ·, Thousand poles: Gan group (blgram), such as the common words "patent", "quote /. Work" can also be a single word (unigram, three-letter group = g ^ am) or more. The letter group is used as the basis for the demonstration. Taxi ΐ = ί its application range. Then, calculate the value of the two components that appear in each word group. The component values of all the word groups are combined in the file. The example of Gua / Zhongbaili's type tragedy is as follows. For example, a group of documents is now "Special 2, and arranged as (patent, trademark, work). The number of times that" work "appears in the document is 7 times, and" Trademarks "3 times, 5), is ^ Is five times, the article of the vector of documents (7, 3, a vector of dimension (3-dimensional vector).

From page 6, the correlation between two file vectors shows that after converting a file into a vector, you can use the inner product value of the two files J and X 'as the similarity value. The larger the inner product value: Do the inner product. 4 The greater the degree of similarity; for example, if one or more represents the operation between two files, it is the number between files: ',,, and the other file is D, and the inner product value is added up; for example: file β, its, and M Are multiplied by the median value, and then the D vector of the file is = (dl, 廿 2 is set to = (bl, b2, ......, bm), and

The correlation is its inner product value = β,..., Dm), m is the number of dimensions, BikD can be seen from the above, to make the text ^^ d1 + b2xd2 + ..... + bfflxdffl, convert the file to a vector, Document direction =: enough to do correlation calculations, you must first base. An efficient approach is to use the components of Ergu, which are based on commonly used vocabularies. For example,-= Kuoku will use "Common fields", all possible two-letter two: "Newly discovered oil land in mainland China", "Lu Xin", "Xinfa ,,, * China", "National University", "Big Oil", "Oilfield", If the words ▲ Second Discovery, Present, Mainland China, Discovery, and Common vocabulary are: "China", 〒, and the remaining "National University" and "Heart", these words will continue one after another Words such as “broken oil” will be discarded and ^ new '', `` new '', `` present '', vocabulary, and what will be used as the beam ^; however, how to determine which is the search engine's postback data In the present invention, compared with the threshold of the feature word of the external word, column 2 = poor material, after the calculation, it is compared with the preset vocabulary. No No is not greater than the threshold value common vocabulary Cloth 'as it is often the use of external search engines, then made mountain qe external search?丨 Engine $ system must be connected to the Internet's oral materials, and then delivered to the system 575813 V. Invention Description ⑸ _______ The system and external structure of the terminal are described below. As shown in FIG. 1, the present invention is applied to a computer type. The first aspect of the present invention is to program the present invention to include but is not limited to: the middle-brain instruction software and install it on a computer 101 ±, a non-production computer. Or notebook computer; the software 102 of the computer = desktop systems, application software, various components, and databases are included in the system of the present invention. The system also belongs to computer software-=== or data, and memory 104. Wait until the computer can read the media, and place it in the storage device 103 and the memory 106. The user will see the local device = two hard disk drives, enter the input port 108r of the computer :: = 7 : Keyboard or software, through the motherboard as the interface, 109, 1 j electric instructions, Xuan X, Lanshan Shi A and other hardware components to communicate, and the central processing saponin (Central PrQcessi =? Operation All machine instructions 'this computer instruction' are processed and the result is displayed on the display interface card 丨 丨 丨 to be displayed on the screen 丨 丨 2. The system user can choose to operate the system on the local computer or through the network. ; If the system user is from a local area network (LAN) 113, The device 114 enters the local network interface card 115 to execute the authority of this computer command. The system can also connect to the Internet through the local area network and communicate with it. If the system user is from a wide area network (w AN ) 丨 丨 6 (or the Internet), you can enter the local network interface card 115 through the network device 114, or through, the modem 11 7 logs in to another input / output port i 丨 8 to execute the instructions of this computer The car body system can also connect to the Internet and communicate with it via this WAN.

$ 8 页 575813 V. Description of the invention (6) # ΐi 所 i P: The application of the present invention can exist in various computer readable media including but not limited to floppy disks, hard disks, optical disks, flash Memory ROM, nonvolatile memory (nonvolat i le R0M) and each J access memory UAM); the installation is not limited to the computer for load balancing calculations. # @ As shown in Figure 2, this is one of the two ways of connecting the system and the network of the present invention. First, the present invention is designed as a computer system 204 and installed on the notebook. The system can be accessed through the network. The Web server 203 is connected to the Internet system 202, and then communicates and transmits messages with the external search engine 200m. When the external search engine 201 returns data, it also passes the Internet system 2 0 2 is transmitted to the local server 203, and then the local computer system 204 receives the message and processes it. As shown in FIG. 3, this is the main flow of the present invention. First, in step 3101, a threshold value of a word feature value is set; the "word feature value" is sufficient to represent the degree to which a word is commonly used in a document. The present invention uses mutual information (Mutual lnf0rmati0n; MI) as one of the statistical methods for calculating the feature value of a word, and the formula is as follows: MI (ab) two Log (F (ab))-Log (F (a))-Log ( F (b)) The right word is a two-letter group, a is the first word in the vocabulary, b is the second word in the two-letter group; F (ab) is the frequency (number of times) of the two-letter group pyr. , F (a) is the frequency (number of times) that a appears, and F (b) gb appears (frequency). The formula of mutual information M I will be adjusted by adding coefficients before the logarithmic values in practice, making the system of the present invention easier to screen vocabulary.

575813 V. The description of the invention (7) is as follows: MI (ab) = w · Log (F (ab))-x • Log (F (a))-y -Log (F (b))-z where w, x, y, and z are consistent coefficients, which means that the mutual information values are adjusted by using the coefficients as weights. The optimized coefficient values have been calculated by recent people, and are also used in the practice of the present invention. The MI formula is as follows: MI (ab) = 0.39 · Log (F (ab))-0. 28 · Log (F (a))-0. 23 -Log (F (b))-0.32; coefficients are all close to 0.3. Step 301 sets the threshold value of the feature value of the word, such as threshold mj >-19; step 302, enter a word into the system, such as "oil field"; step 303, send the word and the words that form the word to External search engine query; currently the external search engines are: "Google" (www.google.com), r0penfind "(www.openfind.com.tw)," AltaVista "(www.altavista.com)," Excite "(www .excite.com), "Lycos" (www.lycos.com), the system can be specified arbitrarily. In this example, 0 penfind is used as the external search engine. Step 3 0 4: Receive and interpret the external search engine's return message. For example, Query the word "oilfield" in Openf ind. The web page returned by the search engine contains "Open find 1 2, 9 28 related pages", of which 12,928 is F (ab), and other F (a) = l, 630,526, F (b) = 1,1 82, 6 78, in other words, F (ab), F (a), F (b), all three are provided by the search engine; Step 3 0 5, calculate the use of the vocabulary Word feature value, here the word feature value is taken as the mutual information MI as an example, MI (Π field ·,) = Log (F (n oil field n))-Log

Page 10 575813 V. Description of the invention (8) (F (n oil ,,))-Log (F (n field, 1)) = -18 · 82 0 6; Step 3 0 6 to determine the feature value of the term If it is greater than the threshold value, then go to the next step, otherwise end; because -1 8. 82 > -19, that is, the word feature value MI (Πfield ") is greater than the threshold value mi, so proceed to step 3 0 7; step 3 0 7, treat the word as a valid word and add it to the thesaurus. The present invention further illustrates the screening process of effective vocabulary by using an embodiment; for example, a sentence sentence plant newly discovered oil field in mainland China ", all possible vocabulary (two-letter group) are the plant China J ^ National University", "Mainland" , Plant Luxin J Plant, Xinfa J Plant Found "," Current "," Oil ", and Plant Oilfield J were entered into Google search from external search engines, and the results of the check and the calculated data are shown in Figure 4. The feature values of its replies are based on Μj. The list of ΜI values is as follows: Vocabulary ΜΙ Plant China j -14. 6 Plant Guoda j -18. 3 Plant mainland j -14 · 4 Plant Luxin j -1 8 · 6 new plant j -17. 9 plant found j -13. 9 plant present j -18. 6 plant oil j -19. 6 plant oil field j -16. 6

P.11 575813 V. Description of the invention (9) The vocabularies after their values are arranged are: "discovery", "mainland", "China", "oil field", "new development", "National University", "present" "," Lu Xin ", and" Oil ", the values of which are consistent with the general impression of word frequency. The words that are more in front are more commonly used, and the words that are later are less commonly used. If the default feature word threshold is mi =-1 5, the three words "discovery", "mainland", and "China" will be selected as valid words; if mi = -17, the four words "discovery", "mainland", "China", and "oil field" will be selected Will be selected as a valid vocabulary, and the remaining vocabularies "National University", "Lu Xin", "Xin Fa", "present", and "oil" will not be selected as valid vocabulary. In addition to using the “reciprocal information” statistical method as the basis for calculation, word eigenvalues can be calculated in other ways. The second statistical method for word eigenvalues is vocabulary frequency (Term F requency; TF). The number of results of the vocabulary returned by the external search engine is used as the feature value of the word; as in the previous embodiment as an example, the TF value is shown in the F (ab) -column shown in Fig. 4, which is extracted from the following table: Vocabulary TF "China" 1,910,000 "National University" 3 5,5 0 0 "Mainland" 568,000 "Lu Xin" 8, 530 "Sin Fat" 6 3, 6 0 0

Page 12 575813

925, 000 40,200 20,600 77, 6 0 0 5. Description of the invention (ί) “Discovery” “Current” “Oil” “Oil Field” If the preset threshold is 1 0 0, 0 0 0, the valid words are "Chinese" discovery "," Mainland ". The third statistical method of word eigenvalues is Information Gain (IG). The IG formula is: IG (t) two-EPr (ci) Log (Pr (ci)) + Pr (t) ΣPr (ci I t) Log (Pr (ciIt)) + Pr (t ') EPr (ci | t,) Log (Pr (cilt,)) where ci is the classification in the file, iM ~ m, m is the number of classifications, pr ( ci) is the probability, frequency or number of occurrences of the classification in the overall file, t is a pair of letters, Pr (t) is the frequency of the occurrence of the two letters in the overall file, and pr (ci | t) is the double The frequency of the letter group in the classification ci, ρ factory (seven,) is the frequency of the two-letter group that does not appear in the total file (the number of results), Pr ^ (cilt ') is the two-letter group does not appear in the classification Frequency; 'This ^ information gain statistical method is more suitable for classified document databases. General search engines allow users to limit the search to specific categories of content, such as Yah〇〇! If there is no category, the overall data can be The library is considered a category. '' In the formula of the information gain IG, it can be adjusted after a long time ^ soil, to make it easier for the computer to screen the vocabulary, and b) the value a is added with the coefficient IG (t) ^ w.EPr (cl) L0g (Pr (ci)) " ^^^^^^

Page 13 575813 V. Description of the invention (11) + x -Pr (t) ZPr (ci | t) Log (pr (ci | t)) + y · Pr (t ') EPr (ci | t') L. g (Pr (ci | t ')) where w, x, y, and z are real coefficients, which means that the coefficients are used as weights to adjust the information gain. The fourth statistical method for the feature value of words is Chi-square Statistic (CHI), which counts the number of occurrences of the two-letter group ab, the number of occurrences of the first letter a of the two-letter group a, and the number of times B does not appear. The number of times that the word b appears without the preceding word a, and the number of times that the two characters ab do not appear simultaneously d; Step 70 3, calculate the CHI values of all two-letter groups: CHI (ab) = [NX (AD-CB) 2] + [(A + C) x (B + D) x (A + B) x (C + D)] where N is the total number of documents; general large search engines will provide the "advanced search" function provided For the user, you can choose to enter "exclude specified words". In this way, you can search for the number of occurrences of a without dagger, and the number of occurrences of b without a. The method for breaking words of "breaking words" mentioned above in the present invention, which is based on the principle of breaking at the same time, is described as an example provided later, and the actual word breaking is treated: for example, the letter group (bigram) ), It can also be applied to two-character long-word breaks in order. First, you must choose the way to split words, such as the η word sentence into a long word consisting of the first word to (η_1) words, and The second word excludes the two parts of the long word composed of the nth word, and uses the data returned by the external search engine to calculate the respective word feature values, and then uses the threshold value to determine which one is the first

Page 14 575813 V. Description of the invention (12) If the long word is judged to be a valid long word, it will be interrupted by the sentence. Otherwise, it will return to the word splitting mode, continue to disassemble the long word and judge it, and repeat the process in this way. Until nothing can be processed. The thesaurus calculated by the present invention using an external search engine as a database has a wide range of applications, such as: 1. Dynamically updating the thesaurus to keep the thesaurus up-to-date at all times, which can make queries and classification more accurate. 2. Problem-Solution, word bag >%, action

analysis), if users use the "question" query, they can get a response from system 1. H library Λ as the basis of classification 'After having a complete thesaurus, you can categorize the vocabulary, analyze the $ in the file, and then use the file as a Π · dynamic summary, using the thesaurus as the basis for finding the key words in the file! The key points are that users who become the summary of the file can quickly browse the automatic summary and read the file more efficiently. In combination with the above, the main technique of the present invention is to use an external search engine as a screen for effective vocabulary :: automation

It saves a lot of statistical bases, including the cost of building a database of ghost files. The present invention can be applied to computer information systems, and its transmission is limited to any medium, such as the Internet, wireless transmission devices, etc .: Dagger-the technical content and technical characteristics of the present invention. As disclosed above, people with this technology may still However, people still do this based on the teaching and disclosure of the present invention.

Page 15 575813 V. Description of the invention (13) Replacement and modification without departing from the spirit of the invention; therefore, the protection scope of the invention should not be limited to those disclosed in the embodiments, but should include various substitutions and modifications without departing from the invention. It is covered by the following patent applications.

Page 575813 Brief Description of Drawings Figure 1 is a structural diagram of the present invention applied to a computer; Figure 2 is a system and network connection diagram of the present invention; Figure 3 is a main flowchart of the present invention; and Figure 4 is the present invention The data sheet of the embodiment.

Page 17

Claims (1)

575813 6. The scope of patent application β is also +7, + _ word basis method 1 · An external search engine is used as money "^ Step: To verify whether a word is a valid word, including the following y == 特-有 字Pass the query string from the external search engine; (c) Receive the external search engine to send back the net tribute, and get the statistics, "" at least include the number of query results; (d) calculate the word according to the above statistical data The feature value of a word is regarded as a valid word if the feature value of the word is greater than the $ threshold of the feature value of the word. 2 · The method as described in item 1 of the scope of patent application, wherein the Lusi in step (b) All the words in the dish are all words whose number of words is less than the number of words in the vocabulary, and the words at least include single words. ^ ^ The method described in item 1 of the scope of patent application, wherein the word characteristic value :, f method The log value of the query result of the vocabulary minus the entire search result of the word group ★, the log value of the number of small and small numbers. Wan Ling described in the above item, where each log value is added with the word characteristic value Adjusted, and the word features 佶 l and τ plus each can be multiplied by the third term one Real number coefficient ^ = will be adjusted by the feature value of the word progress will be adjusted by the feature value of ㈣ f the formula described in item 1 of the range "Ten different ways for the query result of the word ^: the characteristics of the word 575813 6. The scope of patent application 6. The method described in item 1 of the Chinese patent I, where the term feature value is calculated as IG, IG (t) = ~ SPr (ci) L0g (pr ( ci)) + Calculate (t) ZPr (c1 | t) Log (Pr (cllt)) + Pr (t,) ΣPr (cχ, t,) L0g (Pr (ci It,)), where t is one Vocabulary, C1 is the classification in the file, i = i ~ m, m is the total number of classifications, PrCcU is the frequency of the classification in the overall file, pr (t) g the number of occurrences of the two-letter group in the overall file, pr (ci 丨 t) is the number of occurrences of the two-letter group in category C1, Pr (t,) is the number of occurrences of the two-letter group in the total file, and PrUi | t,) is the two-letter group Number of pens that do not appear in category ci. 7. The method as described in item 1 of the scope of patent application, wherein the feature value of the term is calculated as CHI value: CHI (ab) = [Nx (AD —CB) 2] + [(A + C) x (B + D) x (A + B) x (C + D)], where the word ab appears simultaneously with the number of pens A, the word a appears before the word b, and the number of pens B not appearing, the word b appears before The number of pens c in which the word a does not appear, and the number of pens d in which the two characters ab do not appear at the same time. 8. — A computer system for using an external search engine as a word segmentation system. The system includes: (a) — a network connection module to connect the central processing module and the Internet; (b) — central processing Module to perform the following steps 575813 VI. Patent Application ^ -------- threshold for storing word feature values;-input a vocabulary and all words in the vocabulary into the query string of an external search engine through a network connection module ; Receive a web page returned by an external search engine through a network connection module, and obtain statistical data, including at least the number of query results; calculate the word feature value of the word according to the above statistical data, if the word feature value is greater than Using a threshold of a wide eigenvalue is considered a valid vocabulary. 9. The computer system as described in item 8 of the scope of patent application, wherein all the words in the vocabulary in module (b) are all words with the number of words less than the number of words in the vocabulary, and the word i rarely includes a single word. 10. The computer system as described in item 8 of the scope of patent application, wherein the feature value of the word in the central processing module is calculated by querying the log of the last name & number minus the query of each word group The logarithm of the number of results is 11. The computer system described in item 10 of the scope of the patent application, where each value can be multiplied by a real number coefficient to adjust the word feature value, and a real number coefficient is added. _Step will be adjusted with word feature values. . 12. The computer system according to item 8 of the scope of patent application, wherein the feature value of the term in the management module is the number of query results of the term. 13. The computer system described in item 8 of the scope of patent application, wherein the central office 575813 VI. The feature value of the word in the patent application scope management module is calculated as follows: G, JG (t) = — Σ pr (ci) Log (pr (ci)) + Pr (t) IPr (ciIt) Log (Pr (ciIt)) + Pr (t ') EPr (ci I t,) Log (Pr (ci I t')) 'where t is a word, Ci is the classification in the file, i = Bu ^, m is The total number of classifications' Pr (ci) is the frequency of occurrence of the classification in the total file, pr (t) is the number of occurrences of the two-letter group in the total file, and Pr (ci I t) is the number of the two-letter group in the classification The number of pens appearing in ci, Pr (t,) is the number of pens not appearing in the total file for the two-letter group, and pr (ci | t,) is the number of pens not appearing in class ci for the two-letter group. 14. The computer system as described in item 8 of the scope of patent application, wherein the feature value of the term in the central processing module is calculated as CHI value: cHI (ab) = [Nx (AD-CB) 2]-[( Α + 〇χ (B + D) x (A + B) x (C + D)], where the word ab appears simultaneously with the number of pens A, the word before the word a appears, and the word b does not appear after the number of words B, the last word Number of occurrences of b appearing without the preceding character c and number of occurrences of the ab not appearing at the same time d. 1 5 · The computer system described in item 8 of the declared patent scope, wherein the central processing module includes at least the central processing Units and computer-readable media. 1 6. A computer-readable medium that can store computer fingers, programs, or software 'and use it with a computer device to perform method 1 using external search engines as a basis for word segmentation to verify Whether a vocabulary is valid, the method includes the following steps: 575813 6. Scope of patent application (a) Set thresholds for word feature values; (b) Enter a vocabulary and all the words in the vocabulary in an external search engine query string; (c) Receive an external search engine Return the webpage and obtain statistical data, including at least the number of query results; (d) Calculate the word feature value of the word according to the above statistical data. If the word feature value is greater than the threshold value of the word feature value, then consider Is a valid vocabulary. 17. The computer-readable medium as described in item 16 of the scope of patent application, wherein all the words in the vocabulary in step (b) are all words whose number is less than the number of words in the vocabulary, and the words include at least a single word . 18. The computer-readable medium as described in item 16 of the scope of patent application, wherein the feature value of the term is calculated by the logarithm of the query result of the word minus the query result of each word group. The logarithmic value. 19. The computer-readable medium as described in item 18 of the scope of patent application, where each logarithmic value can be multiplied by a real number coefficient to adjust the word characteristic value, and a real number coefficient can be added to further Adjust with word feature values. 20. The computer-readable medium as described in item 16 of the scope of patent application, wherein the term feature value is calculated by the number of query results of the term. Page 22 575813 VI. Patent application scope 21, such as the computer-readable media described in item 16 of the patent application scope, in which the term characteristic value is calculated by IG, IG (t) =-EPr (ci) Log (Pr (ci)) + Pr (t) ZPr (ci | t) Log (Pr (ci | t)) + Pr (t ') EPr (ci | t') Log (Pr (ci | t ')) , Where t is a vocabulary, ci is the classification in the file, i = 1 ~ m, m is the total number of classifications, Pr (ci) is the frequency of the classification in the overall file, and Pr (t) is the two-letter group The number of occurrences in the total file, Pr (ci | t) is the number of occurrences of the two-letter group in the classification ci, and Pr (t ') is the number of occurrences of the two-letter group in the total file, P r (ci | t ') is the number of pens in which the two-letter group does not appear in the classification ci. 22. The computer-readable medium as described in item 16 of the scope of patent application, wherein the term feature value is calculated as CHI value. CHI (ab) = [NX (AD-CB) 2] ^ [( A + C) x (B + D) x (A + B) x (C + D)], where the word ab appears simultaneously in the number of pens A, the word a appears before and the word b does not appear after the number of pens B, The number of pens C where the word b appears but the word a does not appear a, and the number of pens D where neither word ab appears. Page 23