TWI486797B - Methods and devices for sorting search results - Google Patents

Description

Method and apparatus for sorting search results

The application relates to the field of computer data processing technology, and in particular to a method and device for sorting search results.

In the search engine, it is necessary to estimate the degree of matching between the search result and the query string according to the position distance of several words of the query string appearing in the search result (target string), and the distance is generally higher. Thus get a more advanced ranking. For example, the query string is a "disinfector", and the search result containing the "disinfector" is usually closer to the user's intention than the "disinfecting industrial washing machine", which is closer to the user than the "disinfection equipment, dehydrator, dryer". Intention, this will affect the ranking of the search results.

A conventional implementation for calculating the distance of a plurality of words of a query string in a target string is a minimum sliding window, that is, finding a segment having a length as small as possible in the target string, the interval containing the query string For each word and word, the length of the interval is used to describe the distance of the query term in the target string. For example, the query string is "I|Look|Landscape", the target string is "I|在|桥|上|看|风景|,|看|风景|的|人|在|桥|下|看|我| "The vertical line represents the result of the word segmentation." The minimum sliding window is "I | In | Bridge | On | Look | Landscape", with a length of 6 words.

Another way to calculate the length of a word is to edit the distance. Unlike the minimum sliding window, it is not to calculate the length of the word of a single string, but to calculate the sum of the lengths of the difference between the two strings. For example, the difference between "I and you" and "big and small" is two words (first and third words), and the editing distance is 2.

At present, the matching degree between the query string and the target string is usually determined according to the length or the distance, that is, if the minimum sliding window length or the editing distance is smaller, the matching degree is higher, and vice versa, the matching degree is low.

However, in some cases, a simple length or distance does not accurately reflect the degree of matching. For example, the query string is "Nokia battery", the search result A is "Nokia battery", B is "Nokia mobile phone, free battery", C is "Nokia n73 mobile phone original battery". According to the simple distance calculation, the distance between A's "Nokia" and "Battery" is 0, and the matching degree is the best; the distance between "Nokia" and "Battery" of B and C is 3 words, matching degree Not good enough. But in fact, C's "n73 mobile phone" is a strong word related to "Nokia". "Original" is also a word strongly related to "battery". Although there are 3 words in the middle, the matching degree of C is higher than B. a lot of.

Considering the different influences of different words on distance calculation, previous studies have been conducted, for example, word weights can be set according to part of speech (POS). However, this method of setting weights according to part of speech is still too simple. It does not involve an essential question, that is, whether the query string and the target string semantics are related, and thus the obtained length or distance cannot accurately reflect the query string and the target word. The degree of matching of the strings, that is, the target string associated with the query string semantics is not guaranteed to be ranked first.

The present application provides a method and apparatus for sorting search results. By querying the semantic relevance of a string and a target string, the target string can be more accurately sorted, reflecting the target string and the query string. Matching degree.

The present application provides a method for sorting search results, including: the server pre-calculates the semantic association weight between each two words in the statistical sample, obtains and saves the word weight table, and the method further includes: receiving by the server The query string input by the user terminal searches according to the query string and obtains the target string; the server separately separates the query string and the target string, and sequentially segments the word segment of the query string with the target string. Combining word segmentation two-two; querying a word weight table, obtaining a weight value of each word segment combination; and obtaining a weighted word length according to the weight value, sorting each target word string according to the weighted word length, and feeding back User terminal.

The server pre-calculates the semantic association weight between each two words in the statistical sample. The step of obtaining the word weight table includes: the server acquires a statistical sample; and selects the first word and the second word from the statistical sample. , counting the number C (first word, second word) in which the first word and the second word co-occur in the statistical sample; and counting the number of occurrences of the second word in the statistical sample ΣC (Yi, second word), Wherein the Yi represents each word that appears together with the second word; and calculates a probability P of the first word under the condition of occurrence of the second word ( First word|second word>=C (first word, second word)/ΣC(Yi, second word); when querying the second word, take the semantic correlation weight of the first word and the second word as W =1-P, wherein the W is a weight, the P is a probability that the first word appears under the condition of the second word; and repeating the above steps, sequentially obtaining the semantics of each word in the statistical sample relative to other words Related weights are obtained to the word weight table.

Wherein, the source of the statistical sample includes any form of text or symbol, the text including webpage text, user search log, and user click log.

The weighted word length is a minimum sliding window weighting length; and the step of obtaining the weighted word length according to the weight value to sort each target string comprises: respectively taking each word segment of the target string in each part of the query string The minimum value of the weight; or, respectively, the minimum weight of each participle of the query string in the target string; for each target string, the minimum sliding window weighted length is calculated according to the minimum value of the weight; and each target is compared The minimum sliding window weighting length of the string, the length is small, the order is first, and vice versa, the sorting is later.

The calculation of the minimum sliding window weighting length of each target string specifically includes: a minimum sliding window weighting length Where W represents the weight, Ti represents the i-th participle in the target string, k and h represent the start position and end position of the minimum sliding window of the target string, respectively, and Qj represents the j-th participle in the query string. m represents the number of query word segmentation words.

The application also provides a method for sorting search results. The server pre-calculates the semantic association weight between each two words in the statistical sample, obtains and saves the word weight table, and the method further includes: the server receives the user The query input string is searched according to the query string and obtains the target string; the server separates the query string and the target string respectively; the server calculates the inserted words according to the stored word weight table Corresponding to the minimum weight of each word segment of the query string; the server calculates the minimum weight of each word segmentation of the deleted word relative to the target word string according to the stored word weight table; and calculates the total editing distance according to the minimum value of the weight, according to The total edit distance sorts each target string and feeds back to the user terminal.

The step of calculating the minimum weight of each of the inserted words relative to the word segmentation of the query string according to the word weight table includes: obtaining a weight value of each of the inserted words relative to the query word according to the word weight table; and calculating The minimum weight of the inserted words relative to the word segmentation of the query string is

Where W represents the weight, I _t represents the t-th part of the inserted string, n represents the number of inserted participles, Qj represents the j-th part of the query string, and m represents the number of the query-word participle .

According to the word weight table, the step of calculating the weight minimum value of the deleted word relative to each word segment of the target word string includes: obtaining, according to the word weight table, the weight value of each word segment of the deleted word relative to the target word string; The minimum weight of each word of the word relative to the target string is

Where W represents the weight, Ti represents the i-th part of the target string, q represents the number of target word segmentation, D _d represents the d-th part of the deleted word, and p represents the number of deleted participles.

The step of sorting each target string according to the weight minimum value, the step of sorting each target string includes: determining, for each target string, a total edit distance, where the total edit distance is:

W _total = W _I + W _D

Wherein, W _always represents the total edit distance, W _I represents the minimum weight of each word segmentation of the inserted word relative to the query string, W _D represents the minimum weight of each word segmentation of the deleted word relative target string; and compares the total of each target string The editing distance, the total editing distance is small, the sorting is in front, and vice versa, the sorting is in the back.

Before calculating the total edit distance length, the method further includes: calculating a weight minimum value of the edit distance of the replacement word; calculating a total edit distance according to the weight minimum value, determining a matching degree between the query string and the target string; The step includes: determining a total edit distance for each target string, the total edit distance is: W _total = W _I + W _D + W _C

Where W _always represents the total edit distance, W _I represents the minimum weight of each word segmentation of the inserted word relative to the query string, W _D represents the minimum weight of each word segmentation of the deleted word relative to the target string, and W _C represents the replacement word relative query word. The minimum weight of each word segment of the string and/or target string; and the total editing distance of each target string is compared, and the total editing distance is small, and the order is first; otherwise, the sorting is followed.

The manner of obtaining the minimum weight of the edit distance of the replacement word includes: making the minimum value of the edit distance of the replacement word equal to the preset fixed value, or making the edit distance of the replacement word equal to the inserted word relative query string The sum of the minimum weight of each word segment and the minimum value of the weight of each word segmentation of the deleted word relative to the target word string, or the average value, or the maximum of the two.

The application further provides an apparatus for sorting search results, comprising: a word weight table obtaining module, configured to calculate a semantic association weight between each two words in a statistical sample, obtain and save a word weight table; The module is configured to receive a query string input by the user terminal, perform a search according to the query string and obtain a target string; and a word segmentation module, configured to: after the server obtains the query string and the target string, the query The word string and the target string are respectively segmented; The combination module is configured to combine the word segments of the query string with the word segmentation of the target string in turn, and the query module is configured to query the word weight table to obtain the weight value of each word segment combination; and the matching module And obtaining a weighted word length according to the weight value, sorting each target string, and feeding back to the user terminal.

The word weight table obtaining module includes: a sample obtaining module, configured to obtain a statistical sample;

a first statistic module, configured to select a first word and a second word from the statistical sample, and count the number C (first word, second word) in which the first word and the second word co-occur in the statistical sample )

a second statistical module, configured to count the number of occurrences of the second word in the statistical sample ΣC(Yi, second word), wherein the Yi represents each word that appears together with the second word; the probability calculation module, a probability P (first word|second word) = C (first word, second word) / ΣC (Yi, second word) for calculating the first word under the condition of occurrence of the second word

a weight calculation module, configured to: when querying the second word, take a semantic correlation weight of the first word and the second word as W=1-P, where the W is a weight, and the P is a first word in the first The probability of occurrence of the two words; and generating a module for obtaining a semantic weight of each word in the statistical sample relative to other words, and generating a word weight table.

Wherein, when the length of the weighted word is the minimum sliding window weighting length, the matching module comprises: a weight minimum obtaining module for respectively taking the weight minimum of each participle of the target string in the query string Or, respectively, taking the minimum weight of each participle of the query string in the target string; the first calculating module is configured to calculate the minimum sliding window weighting length according to the weight minimum for each target string; And a sorting module for comparing the minimum sliding window weighting length of each target string, the length is small, the sorting is first, and vice versa, the sorting is followed.

The application further provides an apparatus for sorting search results, comprising: a word weight table obtaining module, configured to calculate a semantic association weight between each two words in the statistical sample, to obtain and save a word weight table; Obtaining a module, configured to receive a query string input by the user terminal, perform a search according to the query string and obtain a target string; and a word segmentation module, after the server obtains the query string and the target string, The query string and the target string are respectively segmented; the first weight minimum calculation module is configured to calculate the minimum weight of the inserted words relative to the word segmentation of the query string; and the second weight minimum calculation module is used for calculating the deletion. And a matching module, configured to calculate a total editing distance according to the minimum value of the weight, sort each target string, and feed back to the user terminal.

The matching module includes: a first total editing distance calculation module, configured to determine a total editing distance for each target string, where the total editing distance is: W _total = W _I + W _D W _always indicates the total editing distance, W _I indicates the minimum weight of each word segmentation of the inserted words relative to the query string, W _D indicates the minimum weight of each word segmentation of the deleted words relative to the target string; and the sorting module is used to compare each The total edit distance of the target string. If the total edit distance is small, the sort is first. Otherwise, the sort is after.

The device further includes: a third weight minimum calculation module, configured to obtain a minimum weight of the edit distance of the replacement word before calculating the total edit distance length; the matching module includes: a second chief editor The distance calculation module is configured to determine a total edit distance for each target string, and the total edit distance is: W _total = W _I + W _D + W _C where W _always indicates the total edit distance, W _I represents the minimum weight of each word segmentation of the inserted word relative to the query string, W _D represents the minimum weight of each word segmentation of the deleted word relative to the target string, and W _C represents the weight of the replacement word relative to the query word string and/or the word segmentation word segmentation word segmentation. The minimum value; and the sorting module is used to compare the total editing distance of each target string, and the total editing distance is small, and the sorting is in the front, and vice versa.

Applying the present application, the semantic association of the words in the target string with the query term is not considered in relation to the conventional simple term length or distance calculation, and the present application introduces a semantic association representing the query string and the target string. The weight of the words is more accurately sorted by the target string, and the target string related to the semantics of the query string is ranked in front, reflecting the degree of matching between each target string and the query string. In practical applications, the application is simple and the effect is good.

The technical solutions in the embodiments of the present application will be clearly and completely described in conjunction with the accompanying drawings in the embodiments of the present application. It is obvious that the described embodiments are only a part of the embodiments of the present application, rather than All embodiments. All other embodiments obtained by a person of ordinary skill in the art based on the embodiments of the present application without departing from the inventive scope are the scope of protection of the present application.

In this application, a semantic factor is added in calculating the word distance or the length of the word, considering the semantic association between the query string and the target string, and the degree of matching between the query string and the target string is better measured, so that the search engine Search results in can get a more reasonable ranking. Of course, this application can be applied to any place where the string matching degree is calculated, and is not limited to the search engine.

Due to the semantics between the strings considered in this application, the semantic association weight between each two words is required. First, how to obtain the semantic association weight between each two words to obtain the word weight table, see the figure 1, the method includes the following steps: Step 101: The server obtains a statistical sample; the source of the statistical sample includes any form of text or symbol, wherein the text includes webpage text, a user search log, a user click log, and the like.

In general, the more the first word and the second word appear together in the statistical sample, the more relevant the first word and the second word are. For example, in the text "Nokia" and "mobile phone" often appear together, or users often search for "Nokia" and then click on the result with "mobile phone", can be said to some extent that "Nokia" and "mobile phone" are highly correlated Therefore, if the user searches for "Nokia", the result contains "mobile phone" is not an accident for us.

Step 102: Select a first word and a second word from the statistical sample, and count the number C (first word, second word) in which the first word and the second word appear together in the statistical sample; for example, statistics “mobile phone The number of co-occurrences with "Nokia" C (mobile phone, Nokia), and then can be derived, and finally the weight of all words (when searching for each word).

Step 103: Count the number of occurrences of the second word in the statistical sample ΣC(Yi, second word), wherein the Yi represents each word that appears together with the second word; for example, the statistics "Nokia" and other words The total number of times is the total number of occurrences of "Nokia") ΣC (Yi, Nokia), where Yi represents each word that is co-occurring with "Nokia".

Step 104: Calculate a probability P (first word|second word)=C (first word, second word)/ΣC (Yi, second word) of the first word under the condition of occurrence of the second word; for example, Get the probability of "mobile phone" in the presence of "Nokia" P (Mobile | Nokia) = C (Mobile, Nokia) / Σ C (Yi, Nokia).

Step 105: When querying the second word, taking the semantic relevance weight of the first word and the second word as W=1-P; wherein W is a weight, and P is a probability that the first word appears under the condition that the second word appears.

For example, take W=1-P as the semantically related weight of “mobile phone” and “Nokia” when querying “Nokia”.

In this example, the weight is 1 minus the conditional probability that the first word appears in the second word. In other embodiments, the weight may be expressed in other ways, such as directly using P as the weight.

Step 106: Determine whether all words in the statistical sample are processed. If yes, execute step 107. Otherwise, repeat the above steps to sequentially obtain semantic relevance weights of each word in the statistical sample relative to other words. In step 107, the output includes statistical samples. The semantic relevance weight of each word in relation to other words to obtain a word weight table.

For example, one of the possible forms of the word weight table can be as shown in Table 1:

It should be noted that the word weight table shown in Table 1 is only a specific embodiment. In practice, the word weight table may have other forms of expression. Here, the expression form of the word weight table is not limited.

At this point, the word weight table is obtained, that is, the weight of the first word when the second word is queried is obtained.

It should be noted that the word weight can be obtained in any manner. FIG. 1 is only a specific embodiment obtained by using the statistical language model. In actual applications, other methods can also be used, such as any automatic The manner of calculation or manual setting, here, does not limit the way in which the word weight table is obtained.

FIG. 2 is a flowchart of a method for sorting search results according to an embodiment of the present application, which specifically includes the following steps: Step 201: A server obtains a query string and a target string.

The query string is usually input by the user, and the target string is usually a string related to the query string obtained by the server after searching, for example, the query string, that is, the user input is “Nokia battery”, the server The target string obtained after the retrieval is A "Nokia battery", B "Nokia mobile phone, free battery", C "Nokia n73 mobile phone original battery", then the above A, B, C obtained through the search are the target words string. The purpose of the embodiment of the present application is to determine the degree of matching between each target string (such as the retrieval structure A, B, C) and the query string. That is to say, the server receives the query string input by the user terminal, searches according to the query string and obtains the target string.

In this embodiment, the query string is “Nokia battery”, and the target string is C “Nokia n73 mobile phone original battery” as an example for description. For the target string A "Nokia battery" and B "Nokia mobile phone, free battery" and the target string C "Nokia n73 mobile phone original battery" processing process is basically the same, no longer detailed.

Step 202: The server separately separates the query string and the target string to obtain a word segment constituting the query string and a word segment constituting the target string.

Here, the query string is Q, the target string is T, Q1Q2...Qm can be obtained after segmentation of the query string, and T1T2...Tn can be obtained after segmentation of the target string. In this embodiment, after the word segmentation of the query string is obtained: Q1Q2=Nokia|Battery, after the target word segmentation, T1T2T3T4T5=Nokia|n73|Mobile|Original|Battery.

The word segmentation in the present application may be a segmentation of any method of the string, may be divided into words in the linguistic sense, or may be divided into single words or letters, symbols, and the like.

Step 203: Combine each word segment of the query string with the word segmentation of the target string in turn, and obtain a plurality of word segment combinations consisting of a query word segmentation word and a target word segment word segment; specifically, obtaining (Ti , Q1), (Ti, Q2)... (Ti, Qm).

The word segment combinations obtained in this embodiment include: (T1, Q1), (T1, Q2), (T2, Q1), (T2, Q2), (T3, Q1), (T3, Q2), (T4, Q1). ), (T4, Q2), (T5, Q1), (T5, Q2).

Step 204: Query a word weight table to obtain a weight value of each word segment combination; here, let W denote a weight, and each word segment obtained according to the weight table The combined weight values are: W(T1, Q1), W(T1, Q2), W(T2, Q1), W(T2, Q2), W(T3, Q1), W(T3, Q2), W ( T4, Q1), W(T4, Q2), W(T5, Q1), W(T5, Q2).

Let W(T1,Q1)=W1 W(T1,Q2)=W1’

W(T2,Q1)=W2 W(T2,Q2)=W2’

W(T3,Q1))=W3 W(T3,Q2)=W3’

W(T4,Q1)=W4 W(T4,Q2)=W4’

W(T5,Q1)=W5 W(T5,Q2)=W5’

Wherein, if Ti is in Q, then Wi=0, for example, T1 is Nokia, Q1 is also Nokia, then W(T1, Q1)=W1=0, similarly, W(T5, Q2)=W5'= 0.

Step 205: Obtain a weighted word length according to the weight value. In this embodiment, the weighted word length is a minimum sliding window weighting length. In this case, step 205 specifically includes the following steps:

i) respectively obtaining the minimum weights of each participle of the target string and each participle of the query string; or, respectively, obtaining the minimum weight of each participle of the query string and each participle of the target string; since each participle of the target string is obtained It is very similar to the processing of the minimum value of the weights of each word segmentation of the query string and the weight of each word segmentation of the target word string and the word segmentation of the target word string. The following only the word segmentation of the target word string and the word segmentation of the query string are obtained. The minimum weight is explained as an example.

Specifically to the above embodiment, that is, it is necessary to obtain the minimum of the two weights of T1 with respect to Q1 and Q2, and the minimum of T2 with respect to the two weights of Q1 and Q2, ... Here, assume W(T1, Q1) and The minimum weights of W(T1, Q2) are W1, the minimum weights of W(T2, Q1) and W(T2, Q2) are the minimum weights of W2, W(T3, Q1) and W(T3, Q2). The minimum weights for W3, W(T4, Q1) and W(T4, Q2) are W4, and the minimum weights of W(T5, Q1) and W(T5, Q2) are W5'.

Ii) for each target string, respectively calculating a minimum sliding window weighting length according to the minimum value of the weight; determining a minimum sliding window weighting length of each target string specifically includes: a minimum sliding window weighting length Where W represents the weight, Ti represents the i-th part of the target string, k and h represent the start and end positions of the minimum sliding window of the target string, respectively, and Qj represents the j-th participle in the query string. , m represents the number of query word segmentation.

For the above embodiment, the minimum sliding window weighting length ΣWi=W1+W2+W3+W4+W5' repeats the above steps 202 to 205, and the minimum sliding window weighting length of the query string with respect to each target string can be obtained.

Step 206: Determine a matching degree of the query string and the target string according to the weighted word length, that is, sort each target string according to the weighted word length, and feed back to the user terminal.

Specifically, the minimum sliding window weighting length of each target string is compared. The smaller the length, the higher the matching degree. On the contrary, the lower the matching degree, that is, the smaller the length, the higher the ranking, and vice versa. .

So far, the degree of matching between the query string and each target string is determined. The traditional simple word length calculation does not consider the semantic relevance of the words in the target string to the query words, and thus the length of the obtained words cannot accurately reflect the degree of matching between the query and the target. Such as "Nokia battery" and "Nokia n73 mobile phone original battery", although the length varies greatly, but if the query word is "Nokia battery", there is no significant difference between the two. By introducing word weights indicating the semantic relevance of the query string and the target string, the present application more accurately sorts the target string, and ranks the target string related to the query string semantics in front, reflecting each The degree to which the target string matches the query string. In practical applications, the application is simple and the effect is good.

FIG. 3 is a flowchart of another method for sorting search results according to an embodiment of the present application. The present embodiment calculates a difference between a query string and a target string based on an edit distance, wherein the edit distance refers to a word from one word. The minimum number of basic operations required to change a string to another string, or the sum of the lengths of the difference between the two strings. Common basic operations include inserting a word/word, deleting a word/word, replacing a word/word, or other operations as needed. For example, from "I love you" to "I don't love her" at least need to insert a "no", replace "you" with "her" two basic operations, so the editing distance of the two is 2, the same reason, " The invisible wings and the delicious chicken wings are edited at a distance of 3. The process shown in FIG. 3 specifically includes the following steps: Step 301, the server obtains a query string and a target string.

The query string is usually input by the user, and the target string is usually a string related to the query string obtained by the server after being retrieved. For example, the query string is "Nokia mobile phone battery", the target string is "original Nokia mobile phone battery" and "Nokia mobile phone, free battery." That is to say, the server receives the query string input by the user terminal, searches according to the query string and obtains the target string.

The purpose of the embodiment of the present application is to determine the degree of matching between each target string and the query string.

In this embodiment, the query string is “Nokia mobile phone battery”, and the target string is “original Nokia mobile phone battery” as an example for description. For the target string "Nokia mobile phone, free battery", because it is basically the same as the target string "original Nokia mobile phone battery", it will not be detailed.

Step 302: The server separately separates the query string and the target string to obtain a word segment constituting the query string and a word segment constituting the target string.

Here, the query string is Q, the target string is T, Q1Q2...Qm can be obtained after segmentation of the query string, and T1T2...Tn can be obtained after segmentation of the target string. In this embodiment, after the word segmentation is performed, the Q1Q2Q3=Nokia|phone|battery is obtained, and the target word string is divided to obtain T1T2T3=original|Nokia|battery.

The word segmentation in the present application may be a segmentation of any method of the string, may be divided into words in the linguistic sense, or may be divided into single words or letters, symbols, and the like.

Step 303: The server calculates, according to the word weight table, a minimum weight of each of the inserted words relative to the word segment of the query string; specifically, according to the word weight table, obtaining the weight value of each of the inserted words relative to the query word segment, In this example, the word "original" is inserted so that the inserted word is I, and the weight value of the inserted word relative to the word segmentation of the query string can be obtained: W(I1, Q1), W(I1, Q2), W (I1, Q3); Calculate the minimum weight of the inserted words relative to the word segmentation of the query string:

Where W represents the weight, I _t represents the t-th part of the inserted string, n represents the number of inserted participles, Qj represents the j-th part of the query string, and m represents the number of the query-word participle .

Step 304: Calculate, according to the word weight table, a minimum weight of each word segment of the deleted word relative to the target word string; specifically, according to the word weight table, obtain the weight value of each word segment of the deleted word relative to the target word string, in this example, Delete the word "mobile phone", so that the deleted word is D, you can get the weight value of the deleted words relative to the target word segmentation: W (D1, T1), W (D1, T2), W (D1, T3) ); calculating the minimum weight of the deleted words relative to the word segmentation of the query string is

Where W represents the weight, Ti represents the i-th part of the target string, q represents the number of target word segmentation, D _d represents the d-th part of the deleted word, and p represents the number of deleted participles.

Step 305: Calculate a total edit distance according to the weight minimum value, determine a matching degree of the query string and the target string, that is, sort each target string according to the total edit distance, and feed back to the user terminal. .

Specifically, for each target string, the total edit distance is determined, and the total edit distance for a target string is:

W _total = W _I + W _D

Where W _always represents the total edit distance, W _I represents the minimum weight of each word segmentation of the inserted words relative to the query string, W _D represents the minimum weight of each word segmentation of the deleted words relative to the target string; and the total of each target string is compared Editing distance, the smaller the total editing distance is, the higher the matching degree is. On the contrary, the lower the matching degree, that is, the smaller the total editing distance is, the higher the ranking is, and vice versa.

So far, the degree of matching between the query string and each target string is determined. The traditional simple word distance calculation does not consider the degree of semantic association between the words in the target string and the query words, and thus the resulting word distance cannot accurately reflect the degree of matching between the query and the target. By introducing word weights indicating the semantic relevance of the query string and the target string, the present application more accurately sorts the target string, and ranks the target string related to the query string semantics in front, reflecting each The degree to which the target string matches the query string. In practical applications, the application is simple and the effect is good.

It should be noted that, for the embodiment shown in FIG. 3, there is still a case of word replacement. For example, when "I and you" are changed to "I and him", "you" can be considered as being replaced by "he". Here, the case of word substitution can be handled as follows: Method 1: The replacement operation is considered as a combination of the addition and deletion operations, that is, the replacement operation is considered to be non-existent, for example, "I and you" is changed to "I and When he is, he thinks that "you" is deleted, and "he" is added, that is, all transformations are insertion and deletion operations. Therefore, the embodiment shown in Fig. 3 can be well solved.

In the second way, the replacement operation is regarded as a third operation other than insertion and deletion. For example, when "I and you" is changed to "I and him", it is considered to replace "you" with "he". When calculating the minimum value of the edit distance of the replacement word, there are two calculation methods: a) the weight of the edit distance of the replacement word is equal to the preset fixed value, for example, the weight of the edit distance of the replacement word The minimum value is fixed to be equal to 1; or, b) the edit distance of the replacement word is equal to the sum of the weight minimum value of the inserted word relative to each word segment of the query word and the weight minimum value of each word segment of the deleted word relative target word string, or The edit distance of the replacement word is equal to the average of the sum of the minimum weight of each word segmentation of the inserted word relative to the query word string and the minimum value of the weight of each word segment of the deleted word relative target word string, or the edit distance of the replacement word is equal to the inserted word relative Query the minimum value of the weight of each participle of the word string and the minimum value of the weight of each participle of the deleted word relative to the target word string, or any other combination .

For example, the edit distance of the word "he" is replaced = the minimum value of the weight of the "he" relative to the query word "I and you" of the inserted word + the word "you" relative to the target word "me and he" The minimum value of the weight; or, the edit distance of the word "he" = (the minimum value of the weight of each participle of the "he" relative query string "I and you" inserted + the word "you" relative target string "I and His "the minimum weight of each participle"/2. and many more.

In the case of the second mode, the step 305 specifically includes: determining, for each target string, a total edit distance, where the total edit distance is:

W _total = W _I + W _D + W _C

Where W _always represents the total edit distance, W _I represents the minimum weight of each word segmentation of the inserted word relative to the query string, W _D represents the minimum weight of each word segmentation of the deleted word relative to the target string, and W _C represents the replacement word relative query word. The minimum weight of each word segment of the string and/or the target string; comparing the total editing distance of each target string, the smaller the total editing distance, the higher the matching degree, and vice versa, the lower the matching degree, that is, the total The smaller the edit distance, the higher the sorting. On the contrary, the lower the sort.

It should be noted that the weights may be calculated according to the query string and the target string in an interleaved manner. In the embodiment shown in FIG. 3, for the inserted string, the weight is calculated according to the query string, and for the deleted string, according to the target word. The string calculates the weight.

It should be noted that, for the embodiment shown in FIG. 2 and FIG. 3, the word segmentation may be a segmentation of any method of the string, and may be divided into words in the language sense, or may be divided into single words or letters and symbols.

It should be noted that, for the embodiment shown in FIG. 2 and FIG. 3, any form of calculation or transformation of the weight may be performed, such as taking a logarithm or the like; or the maximum value, average value of the weight of the target word for each query term or Other forms of operation are used as weights (weighted lengths) for the word.

It should be noted that, for the embodiment shown in FIG. 2 and FIG. 3, the target string can be used as the query string and the query string as the target string without substantial difference.

It should be noted that, for the embodiment shown in FIG. 2 and FIG. 3, the calculation interval of the word distance or length may be the entire string or any interval selected according to the algorithm, such as selecting a difference between another string and another string. section.

It should be noted that the matching method does not have to use the minimum sliding window or the editing distance, and can be any calculation about the weighted word distance or the word length.

It should be noted that the present application is not limited to a retrieval system such as a search engine, and can be applied to any system for calculating the degree of matching of two strings.

The application also discloses an apparatus for sorting search results. Referring to FIG. 4, the method further includes: a word weight table obtaining module 401, configured to calculate a semantic association weight between each two words in the statistical sample, and obtain and save a word weighting module 402, configured to receive a query string input by a user terminal, perform a search according to the query string and obtain a target string; a word segmentation module 403, configured to obtain a query string and a target on the server After the string, the query string and the target string are separately segmented; the combination module 404 is configured to combine the word segments of the query string with the word segmentation of the target string in sequence; the query module 405 is configured to Querying the word weight table to obtain a weight value of each word segment combination; the matching module 406 is configured to obtain a weighted word length according to the weight value, sort each target word string, and feed back to the user terminal.

The word weight table obtaining module 401 may specifically include: a sample obtaining module, configured to obtain a statistical sample;

a first statistic module, configured to select a first word and a second word from the statistical sample, and count the number C (first word, second word) in which the first word and the second word co-occur in the statistical sample )

a second statistical module, configured to count the number of occurrences of the second word in the statistical sample ΣC(Yi, second word), wherein the Yi represents each word that appears together with the second word; the probability calculation module, a probability P (first word|second word) = C (first word, second word) / ΣC (Yi, second word) for calculating the first word under the condition of occurrence of the second word

a weight calculation module, configured to: when querying the second word, take a semantic correlation weight of the first word and the second word as W=1-P, where the W is a weight, and the P is a first word in the first The probability of occurrence of the two words; generating a module for obtaining a semantic weight of each word in the statistical sample relative to other words, and generating a word weight table.

When the length of the weighted word is the minimum sliding window weighting length, the matching module 405 may specifically include: The weight minimum obtaining module is configured to respectively obtain the minimum weight of each participle of the target string in the query string; or, respectively, the weight of each participle of the query string in the target string; a computing module for calculating a minimum sliding window weighting length according to the weight minimum for each target string; a sorting module for comparing the minimum sliding window weighting length of each target string, and the length is small Before, on the contrary, after sorting, that is, the smaller the length, the higher the degree of matching is determined, and conversely, the lower the degree of matching is determined.

Applying the embodiment shown in FIG. 4, by introducing word weights indicating the semantic relevance of the query string and the target string, the degree of matching between the target string and the query string is more accurately reflected. In practical applications, the application is simple and the effect is good.

The embodiment of the present application further provides an apparatus for sorting search results. Referring to FIG. 5, the method includes: a word weight table obtaining module 501, configured to calculate a semantic association weight between each two words in the statistical sample, and obtain The word weighting module 502 is configured to receive a query string input by the user terminal, perform a search according to the query string, and obtain a target string; the word segmentation module 503 is configured to obtain the query string and the target on the server. After the string, the query string and the target string are respectively segmented; the first weight minimum calculation module 504 is configured to calculate the minimum weight of the inserted words relative to each part of the query string; the second weight minimum The calculation module 505 is configured to calculate a minimum weight of each of the deleted words relative to the target word segment; the matching module 506 is configured to calculate a total edit distance according to the weight minimum value, and sort each target string. And feedback to the user terminal.

The matching module 506 may specifically include: a first total editing distance calculation module, configured to determine a total editing distance for each target string, where the total editing distance is: W _total = W _I + W _D W _always indicates the total editing distance, W _I indicates the minimum weight of each word segmentation of the inserted words relative to the query string, W _D indicates the minimum weight of each word segmentation of the deleted words relative to the target string; and the ranking module is used to compare the targets. The total editing distance of the string, the total editing distance is small, the ranking is first, and vice versa, that is, the smaller the total editing distance is, the higher the matching degree is. Otherwise, the lower the matching degree is.

The device of FIG. 5 may further include: a third weight minimum calculation module, configured to obtain a minimum weight of the edit distance of the replacement word before calculating the total edit distance length; at this time, the matching module 505 may be specific The method includes: a second total edit distance calculation module, configured to determine a total edit distance for each target string, where the total edit distance is: W _total = W _I + W _D + W _C where W is _always represented The total edit distance, W _I represents the minimum weight of each word segmentation of the inserted word relative to the query string, W _D represents the minimum weight of each word segmentation of the deleted word relative to the target string, and W _C represents the replacement word relative to the query string and/or target The minimum weight of each word segment of the string; the sorting module is used to compare the total editing distance of each target string, and the total editing distance is small, and the sorting is backward, that is, the total editing distance is smaller. It is determined that the degree of matching is higher, and conversely, the degree of matching is determined to be lower.

By applying the device shown in FIG. 5, the degree of matching between each target string and the query string is more accurately reflected by introducing word weights indicating the semantic relevance of the query string and the target string. In practical applications, the application is simple and the effect is good.

It should be noted that, for the convenience of description, the above devices are described by function into various modules separately. Of course, the functions of each module can be implemented in the same software or software and/or hardware in the implementation of the present application.

It should be noted that, for the system embodiment, since it is basically similar to the method embodiment, the description is relatively simple, and the relevant parts can be referred to the description of the method embodiment.

It should be noted that, in this context, relational terms such as first and second are used merely to distinguish one entity or operation from another entity or operation, and do not necessarily require or imply such entities or operations. There is any such actual relationship or order between them. Furthermore, the term "comprises" or "comprises" or "comprises" or any other variations thereof is intended to encompass a non-exclusive inclusion, such that a process, method, article, or device that comprises a plurality of elements includes not only those elements but also Other elements, or elements that are inherent to such a process, method, item, or device. An element that is defined by the phrase "comprising a ..." does not exclude the presence of additional equivalent elements in the process, method, item, or device that comprises the element.

It will be apparent to those skilled in the art from the above description of the embodiments that the present application can be implemented by means of a software plus a necessary general hardware platform. Based on such understanding, the technical solution of the present application may be embodied in the form of a software product in essence or in a contribution to the prior art, and the computer software product may be stored in a storage medium such as a ROM/RAM or a disk. , optical discs, etc., including instructions for causing a computer device (which may be a personal computer, server, or network device, etc.) to perform the methods described in various embodiments of the present application or portions of the embodiments.

This application can be used in many general purpose or special purpose computing system environments or configurations. For example: personal computers, server computers, handheld or portable devices, tablet devices, multiprocessor systems, microprocessor-based systems, set-top boxes, programmable consumer electronics, network PCs, small computers, large Computer, decentralized computing environment including any of the above systems or devices, and so on.

The application can be described in the general context of computer-executable instructions executed by a computer, such as a program module. Generally, a program module includes routines, programs, objects, components, data structures, and the like that perform particular tasks or implement particular abstract data types. The present application can also be practiced in a decentralized computing environment in which tasks are performed by remote processing devices that are coupled through a communication network. In a distributed computing environment, program modules can be located in local and remote computer storage media, including storage devices.

The above description is only the preferred embodiment of the present application, and is not intended to limit the scope of protection of the present application. Any modifications, equivalent substitutions, improvements, etc. made within the spirit and principles of the present application are included in the scope of the present application.

401. . . Word weight table acquisition module

402. . . Word acquisition module

403. . . Word segmentation module

404. . . Combination module

405. . . Query module

406. . . Matching module

501. . . Word weight table acquisition module

502. . . Word acquisition module

503. . . Word segmentation module

504. . . First weight minimum calculation module

505. . . Second weight minimum calculation module

506. . . Matching module

In order to more clearly illustrate the technical solutions in the embodiments of the present application, the drawings to be used in the embodiments will be briefly described below. Obviously, the drawings in the following description are only some implementations of the present application. For example, other drawings may be obtained from those of ordinary skill in the art in light of the inventive work.

1 is a flow chart of obtaining a word weight table according to an embodiment of the present application;

2 is a flow chart of a method for sorting search results according to an embodiment of the present application;

3 is a flow chart of another method for sorting search results according to an embodiment of the present application;

4 is a schematic diagram of an apparatus for sorting search results according to an embodiment of the present application;

FIG. 5 is a schematic diagram of another apparatus for sorting search results according to an embodiment of the present application.

Claims (13)

A method for sorting search results, wherein the server pre-calculates the semantic association weight between each two words in the statistical sample to obtain and save the word weight table, the method further comprising: the server receiving the user terminal Entering a query string, searching according to the query string and obtaining a target string; the server separately segmentes the query string and the target string, and sequentially segments the word segment of the query string with the target word The word segmentation of the string is combined; the word weight table is queried to obtain the weight value of each word segment combination; and the weighted word length is obtained according to the weight value, and each target word string is sorted according to the weighted word length, and feedback Giving the user terminal, wherein the weighted word length is a minimum sliding window weighting length; obtaining the weighted word length according to the weighting value to sort each target word string comprises: respectively taking each word segment of the target string The minimum weight of each word segment of the query string; or, each word segment of the query string is respectively scored in the target string The minimum value of the weight; for each target string, the minimum sliding window weighting length is calculated according to the minimum value of the weight; and the minimum sliding window weighting length of each target string is compared, and the length is small, the ranking is prior; The calculation of the minimum sliding window weighting length of each target string specifically includes: the minimum sliding window weighting length Where W represents the weight, Ti represents the i-th part of the target string, k and h represent the start position and end position of the minimum sliding window of the target string, respectively, and Qj represents the jth in the query string. The word segmentation, m indicates the number of word segmentation of the query string. The method of claim 1, wherein the server pre-calculates a semantic association weight between each two words in the statistical sample to obtain a word weight table, the method comprising: obtaining, by the server, a statistical sample; Selecting the first word and the second word in the statistical sample to count the number C (first word, second word) in which the first word and the second word co-occur in the statistical sample; counting the second word in The number of occurrences ΣC(Yi, second word) appearing in the statistical sample, wherein the Yi represents each word that appears together with the second word; and the probability P of the first word under the condition of occurrence of the second word is calculated ( First word|second word>=C (first word, second word)/ΣC (Yi, second word); when querying the second word, taking the semantic relationship between the first word and the second word The weight is W=1-P, where W is a weight, the P is the probability that the first word appears under the condition of the second word; and the above steps are repeated, and each word in the statistical sample is sequentially obtained relative to other words. Semantic related weights to get to the word Weight table. The method of claim 2, wherein the statistic The source of the sample includes any form of text or symbol, including web page text, user search logs, and user click logs. A method for sorting search results, wherein the server pre-calculates the semantic association weight between each two words in the statistical sample to obtain and save the word weight table, the method further comprising: the server receiving the user terminal Inputting a query string, searching according to the query string and obtaining a target string; the server separately segmenting the query string and the target string; the server calculates the inserted according to the stored word weight table The minimum weight of the word relative to each participle of the query string; the server calculates the minimum weight of the deleted word relative to each participle of the target string according to the word weight table; and calculates the total editing distance according to the minimum value of the weight And sorting each target string according to the total editing distance, and feeding back to the user terminal, wherein, according to the word weight table, calculating a minimum weight of the inserted words relative to each participle of the query string The step includes: obtaining, according to the word weight table, a weight value of the inserted word relative to each word segment of the query string; and calculating the insertion The right words to the query string relative weight of each word of a minimum of Where W represents the weight, I _t represents the t-th part of the inserted string, n represents the number of inserted participles, Qj represents the j-th part of the query string, and m represents the part of the query string Number. The method of claim 4, wherein, according to the word weight table, the step of calculating a minimum value of the weight of the deleted word relative to each participle of the target string comprises: obtaining the deleted word according to the word weight table a weight value of each participle of the target string; and a minimum weight of the word of the deleted word relative to each part of the target string is Where W represents the weight, Ti represents the i-th part of the target string, q represents the number of the target word segmentation, D _d represents the d-th part of the deleted word, and p represents the part of the deleted participle number. The method of claim 4, wherein the total edit distance is calculated according to the weight minimum value, and the step of sorting each target string comprises: determining the total edit for each target string separately Distance, the total editing distance is: W _total = W _I + W _D where W _always represents the total editing distance, W _I represents the minimum weight of the inserted words relative to the word segmentation of the query string, W _D represents the deletion The minimum weight of the words relative to the word segmentation of the target string; and comparing the total editing distance of each target string, the total editing distance is small, and the sorting is followed by the sorting. The method of claim 4, wherein before calculating the total edit distance length, further comprising: calculating a weight minimum value of the edit distance of the replacement word; calculating the total edit distance according to the weight minimum value The step of determining the degree of matching between the query string and the target string includes: determining, for each target string, the total edit distance, the total edit distance is: W _total = W _I + W _D + W _C, where W _always represents the total edit distance, W _I represents the minimum weight of the inserted words relative to each participle of the query string, and W _D represents the minimum weight of the deleted words relative to each part of the target string, W _C represents a minimum weight of the replacement word relative to each of the query string and/or the target word segmentation; and comparing the total edit distance of each target string, the total edit distance is less prior to sorting, and vice versa, Rear. The method of claim 7, wherein the calculating the minimum weight of the edit distance of the replacement word comprises: making the minimum value of the edit distance of the replacement word equal to a preset fixed value, or The edit distance of the replacement word is equal to a sum of a minimum value of the weight of the inserted word relative to each participle of the query string and a minimum value of the weight of the deleted word relative to each part of the target string, or an average value, or a maximum of the two . An apparatus for sorting search results, comprising: a word weight table obtaining module, configured to calculate a semantic association weight between each two words in a statistical sample, obtain and save a word weight table; and a word acquisition module The method is configured to receive a query string input by the user terminal, perform a search according to the query string, and obtain a target string; the word segmentation module is configured to: after the server obtains the query string and the target string, the query The word string and the target word string are respectively segmented; the combination module is configured to combine the word segments of the query string with the word segmentation of the target string in turn; the query module is configured to query the word weight table to obtain a weighting value of each word segment combination; and a matching module for obtaining a weighted word length according to the weight value, sorting each target word string, and feeding back to the user terminal, wherein when the weighted word length is minimum When the window weighting length is swiped, the matching module includes: a weight minimum obtaining module for respectively taking weights of each participle of the target string in each part of the query string a small value; or, respectively, a minimum weight of each participle of the query string in each target word segment; a first computing module, configured to calculate the minimum for each target string according to the minimum value of the weight a sliding window weighting length; and a sorting module for comparing the minimum sliding window weighting length of each target string, the length is small, the sorting is first, and vice versa, after sorting, wherein the minimum sliding window of each target string is calculated The weighted length specifically includes: the minimum sliding window weighted length Where W represents the weight, Ti represents the i-th part of the target string, k and h represent the start position and end position of the minimum sliding window of the target string, respectively, and Qj represents the jth in the query string. The word segmentation, m indicates the number of word segmentation of the query string. The device of claim 9, wherein the word weight table acquisition module comprises: a sample acquisition module, configured to acquire the statistical sample; and a first statistical module, configured to select the statistical sample from the statistical sample a word and a second word, a second statistical module for counting the number C (first word, second word) of the first word and the second word co-occurring in the statistical sample, for counting the second word The number of occurrences ΣC(Yi, second word) in the statistical sample, wherein the Yi represents each word that appears together with the second word; the probability calculation module is configured to calculate the first word in the second word a probability P (first word|second word)=C (first word, second word)/ΣC (Yi, second word) weight calculation module under the condition of occurrence, when querying the second word, Taking the semantic correlation weight of the first word and the second word as W=1-P, wherein the W is a weight, and the P is a probability that the first word appears under the condition of the second word; and generating a module To obtain the semantic relevance of each word in the statistical sample relative to other words After re-generating the word weight table. An apparatus for sorting search results, comprising: a word weight table obtaining module, configured to calculate a semantic association weight between each two words in a statistical sample, obtain and save a word weight table; and a word acquisition module The method is configured to receive a query string input by the user terminal, perform a search according to the query string, and obtain a target string; the word segmentation module is configured to: after the server obtains the query string and the target string, the query The word string and the target string are respectively segmented; the first weight minimum calculation module is configured to calculate a minimum weight of the inserted words relative to each word segment of the query string; and the second weight minimum calculation module is configured to calculate The minimum weight of the deleted words relative to the word segmentation of the target string; and the matching module, configured to calculate the total editing distance according to the minimum value of the weight, sort each target string, and feed back to the user terminal, wherein According to the word weight table, the step of calculating the minimum weight of the inserted words relative to each participle of the query string includes: obtaining the insertion according to the word weight table Right opposite the query word string weight value of each word; and calculating the weights of the query words inserted opposite of each word string of the minimum weight Where W represents the weight, I _t represents the t-th part of the inserted string, n represents the number of inserted participles, Qj represents the j-th part of the query string, and m represents the part of the query string Number. The device of claim 11, wherein the matching module comprises: a first total editing distance calculation module, configured to determine the total editing distance for each target string, the total editing distance, Is: W _total = W _I + W _D where W _always represents the total edit distance, W _I represents the minimum weight of the inserted words relative to the word segmentation of the query string, and W _D represents the deleted word relative to the target string The minimum weight of each word segment; and a sorting module for comparing the total editing distance of each target string, the total editing distance is small, and the sorting is followed by the sorting. The device of claim 11, wherein the device further comprises: a third weight minimum calculation module, configured to obtain a minimum weight of the edit distance of the replacement word before calculating the total edit distance length The matching module includes: a second total editing distance calculation module, configured to determine the total editing distance for each target string, the total editing distance is: W _total = W _I + W _D + W _C Wherein, W _always represents the total edit distance, W _I represents the minimum weight of the inserted words relative to each participle of the query string, and W _D represents the minimum weight of the deleted words relative to the word segmentation of the target string, W _C represents a minimum weight of the replacement word relative to each of the query string and/or the target word segmentation; and a sorting module for comparing the total edit distance of each target string, the total edit distance being less than Before, on the contrary, sorting is after.