[發(fā)明專利]基于逆波蘭和多叉樹的搜索引擎查詢語句解析方法

有效

• 申請?zhí)枺?/td>: 201310399206.1
• 申請日: 2013-09-05
• 公開（公告）號: CN103440331B
• 公開（公告）日: 2017-02-08
• 發(fā)明（設(shè)計）人: 劉凱
• 申請（專利權(quán)）人: 五八同城信息技術(shù)有限公司
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 北京律恒立業(yè)知識產(chǎn)權(quán)代理事務(wù)所(特殊普通合伙)11416
• 代理人: 顧珊,陳軼蘭

技術(shù)領(lǐng)域

本發(fā)明涉及搜索引擎的查詢語句解析領(lǐng)域，特別是一種基于逆波蘭和多叉樹的搜索引擎查詢語句解析方法。

背景技術(shù)

搜索引擎是指根據(jù)一定的策略、運用特定的計算機程序從互聯(lián)網(wǎng)上搜集信息，在對信息進行組織和處理后，為用戶提供檢索服務(wù)，將用戶檢索相關(guān)的信息展示給用戶的系統(tǒng)。搜索引擎包括全文索引、目錄索引、元搜索引擎、垂直搜索引擎、集合式搜索引擎、門戶搜索引擎與免費鏈接列表等。百度和谷歌等是搜索引擎的代表。

解析查詢語句是搜索引擎進行信息檢索的一個重要步驟。在用戶使用搜索引擎進行搜索時，通常輸入由多個關(guān)鍵字以及關(guān)鍵字之間的邏輯關(guān)系構(gòu)成的檢索式。搜索引擎常用的邏輯關(guān)系語法一般為布爾運算，即“邏輯與”、“邏輯非”和“邏輯或”。“邏輯與”的檢索式“Q1AND?Q2”（其中Q1、Q2為輸入的關(guān)鍵詞），即查找既包含關(guān)鍵詞Q1又包含關(guān)鍵詞Q2目標搜索結(jié)果。“邏輯非”的檢索式“！Q1”，即查找不既包含關(guān)鍵詞Q1的目標搜索結(jié)果。“邏輯或”的檢索式“Q1OR?Q2”，即查找或者包含關(guān)鍵詞Q1或者包含關(guān)鍵詞Q2的目標搜索結(jié)果。舉例來說，若搜索所有包含關(guān)鍵詞“搜索引擎”和“歷史”的目標結(jié)果，則可以輸入檢索式搜索：“搜索引擎AND歷史”。如在上述搜索結(jié)果中，發(fā)現(xiàn)大量的搜索結(jié)果是涉及“文化歷史”、“藝術(shù)歷史”等和搜索引擎歷史無關(guān)的內(nèi)容，則可以改進檢索式為“搜索引擎AND歷史！文化！藝術(shù)”，即可以將目標結(jié)果中涉及文化歷史的內(nèi)容去掉，進一步篩選搜索結(jié)果。在有的情況下，如果進行關(guān)鍵字邏輯與的查詢時，發(fā)現(xiàn)幾乎無法命中目標結(jié)果，或僅命中有限的結(jié)果但無法令人滿意，則多采用邏輯或的檢索式以擴大目標結(jié)果的命中范圍，查找用戶所需要的檢索結(jié)果。

現(xiàn)有的搜索引擎對查詢語句解析的方法是將查詢語句以逆波蘭方式解析后，生成一棵以二叉樹表示的查詢語法樹，然后以先序遍歷二叉樹的方式進行邏輯操作及結(jié)果集的合并，每次輸出最小的文檔編號。

然而，在現(xiàn)有的搜索引擎查詢語句的解析過程中，如果有多個連續(xù)或者并列的邏輯或(OR)查詢操作，則會導(dǎo)致生成的二叉樹的深度較大。由于遍歷操作是從葉子節(jié)點向根節(jié)點聚合，每次比較后輸出一個元素，這樣樹的深度以及葉節(jié)點在樹中的位置不同都會影響比較的次數(shù)，樹的深度越大比較次數(shù)越多，結(jié)果集大的葉子節(jié)點越深查詢時間越長。而且，二叉樹每個節(jié)點最多只有左右兩個子節(jié)點，每次只對不超過兩個元素操作，也是制約了查詢速度的因素之一。

因此，需要一種能夠優(yōu)化查詢操作，減少計算量，從而降低響應(yīng)延遲的搜索引擎查詢語句解析方法。

發(fā)明內(nèi)容

本發(fā)明的目的是提供一種基于逆波蘭和多叉樹的搜索引擎查詢語句解析方法。

根據(jù)本發(fā)明的一個方面，提供了一種基于逆波蘭和多叉樹的搜索引擎查詢語句解析方法，其特征在于，包括如下步驟：a)將查詢語句轉(zhuǎn)化為逆波蘭表達式;b)遍歷所述逆波蘭表達式，生成多叉樹;c)遍歷所述多叉樹；d)輸出遍歷后的查詢結(jié)果。

優(yōu)選地，所述步驟b)的生成多叉樹的過程包括如下子步驟：a)按從左到右的順序遍歷逆波蘭表達式的一個元素；b)判斷是否完成對逆波蘭式的遍歷，是則遍歷過程結(jié)束，此時生成的多叉樹即為所述多叉樹；否則，提取當前遍歷到的一個元素，進入步驟c)；c)判斷所提取的元素是否為查詢詞，是則將該查詢詞入棧，返回步驟a)，否則所提取的元素為操作符，并將棧頂元素出棧，進入步驟d)；d)將所述操作符作為臨時多叉樹的根節(jié)點，并將出棧元素作為葉子節(jié)點進行組合，形成臨時多叉樹；e)將生成的臨時多叉樹的根節(jié)點及其葉子節(jié)點重新入棧，返回步驟a)。

優(yōu)選地，在所述步驟c)中，若遍歷到單目操作符則出棧一個棧頂元素，若遍歷到雙目操作符則出棧兩個棧頂元素。

優(yōu)選地，在所述步驟d)中，當所有出棧元素均為查詢詞時，則將所述查詢詞直接作為臨時多叉樹的子節(jié)點；當其中至少一個出棧元素為操作符，并且與當前遍歷到的操作符相同時，則將相同操作符的子節(jié)點合并；當其中至少一個出棧元素為操作符元素并且與遍歷到的操作符不同時，該出棧的操作符元素附帶其子節(jié)點直接作為當前遍歷到的操作符的子節(jié)點。

優(yōu)選地，在所述步驟c)的遍歷多叉樹的過程包括如下子步驟：a)將所述多叉樹的根節(jié)點的所有子節(jié)點構(gòu)成小根堆；b)提取所述根堆的堆頂節(jié)點的元素，更新查詢結(jié)果；c)將所述堆定節(jié)點出堆，判斷所述出堆節(jié)點的元素是否為空，是則進入步驟d)，否則將所述出堆節(jié)點重新入堆并調(diào)整，返回步驟b)；d)判斷所述跟堆中的節(jié)點是否為空，是則結(jié)束遍歷，否則返回步驟b)。

優(yōu)選地，所述節(jié)點的元素包含查詢詞對應(yīng)的編號為從小到大排序的有序文檔列表。