做個夠用的搜索,其實也很簡單(一)搜索的原理

1. 信息和信息量

在介紹搜索之前,先介紹兩個概念:信息和信息量。

(採用的均是自以為比較通俗易懂的解釋,如果感興趣可以讀相關書籍)

1.1 信息是減少不確定性的東西,信息也是增加確定性的東西。

前半句是香農信息定義,後半句是逆香農信息定義。舉個栗子,回想下,和一個異性交往的過程。在你遇到TA之前,你不知道這個世界上有這個人的存在,後來你看到了TA的樣子,後來你了解了TA的性格、口頭禪,往事。然後一步一步,你對TA從絲毫不了解,到逐漸熟識。這期間就是一個你不斷獲取TA信息的過程,正是這些信息,讓你從完全不確定TA是怎樣的人,到完全確定TA很適合你。

1.2 信息量是一個信息能減少不確定性的度量,信息量也是一個信息能增加確定性的度量。

關於信息量,有很多數學的描述,但是通俗來講,可以這麼簡單理解。舉個栗子,證人描述嫌疑犯。A證人的信息是「他是個男人」。B證人的信息是「TA是個高中男生」,C證人的信息是「TA是個長發170左右的高中生。」D證人的信息是「我認識他,他是學校的扛把子陳浩南」。我們直覺能感受到信息量的大小關係為:A<B<C<D。顯然這是正確的。

翻譯為計算機可以理解的數學邏輯:當地男人的比例是50%,當地高中男生的比例為8%,當地長發170左右的高中男生的比例是4%,當地叫陳浩南的扛把子的比例是0.0001%。因為P(A)>P(B)>P(C)>P(D),所以信息量的大小關係為:A<B<C<D。

2. 搜索的產品邏輯

搜索滿足了用戶迅速找到自己感興趣內容的需求。用戶輸入一個query,搜索系統根據用戶的輸入的信息,篩選出系統認為用戶感興趣的內容,同時按照系統認定的重要性進行排序展示。請注意這個表述,簡單而言,搜索可以分為三步。

  • Step1:對用戶輸入信息的解讀

  • Step2:根據用戶輸入信息對內容進行篩選

  • Step3:對篩選後的結果進行排序

而要了解這三步怎麼在搜索系統中完成,就需要先了解搜索的伺服器怎麼存儲信息。

3. 搜索數據的存儲原理

上一張圖,假設我們做了一個新聞網站,那麼它的結構就是下圖。內容進行了簡化,假設一個新聞,文本只有標題,導語,正文。數據只有閱讀量,評論數,分享數。

————————【圖1-1】————————

差不多就是上圖右邊的這種結構。右邊標識的是新聞內容的存儲:就像圖書館的書一樣,整整齊齊按順序排好,方便查找(這個存儲結構的名字叫做索引,就是來自於圖書館的用語)。左邊是詞庫:只要一次搜索的輸入詞能匹配到詞庫,就可以快速的查找詞庫到對應的內容。

每個搜索系統都有自己的詞庫,無法對應到分詞的搜索行為就會沒有結果。每個搜索系統都會根據目標用戶的不同,有對應的一套詞庫,就像字典一樣,《冶金專業詞典》和《生物學大辭典》收錄的詞條是不同的,知乎的詞庫和淘寶的詞庫也不同。搜索的很多優化都是集中在詞庫的優化上。

簡單總結下,搜索的存儲原理就是:一個系統詞庫,一個排列整齊的內容索引庫,同時系統詞庫和內容索引庫之間可以快速關聯。

在這個搜索系統的儲存結構的基礎上,我們提到的搜索三步驟將依次展開。

4. Step1:對用戶輸入信息的解讀

前面提到,搜索的詞庫是有限的,但是用戶的輸入卻是沒有限制的。那麼怎麼把無限制的搜索轉化為有限的詞庫,並且匹配到對應的結果呢?這裡需要介紹一個新的概念:分詞,簡單來說就是對輸入字元串進行分拆。

同樣以【圖1-1】中的新聞搜索系統為例。如果用戶輸入的query為「中國的轉基因食物」,系統中其實沒有這個詞。如果沒有分詞功能,這個搜索就會立即結束,即使系統里確實有對應的內容。分詞的工作原理是在無法精確匹配的情況下,會對用戶的輸入進行進一步的拆分。於是我們得到了下面的結果。

「中國的轉基因食物」——「中國」、「的」、「轉基因」、「食物」。

並不是所有的詞都有信息量,如果召回「的『』的結果,那麼幾乎所有的新聞內容裡面都會有這個字,召回這麼多結果顯然是不對的。比如這個query里的「的」,這個詞實際上在分詞系統中會被直接忽略掉。正是因為出現在內容中的概率不同,一個詞出現的新聞越多,這個詞的信息量就越小,信息量太小的詞會被忽略,也就是停用詞。同時包含信息量越大的詞的新聞內容,會更更要。那麼去掉停用詞之後,結果就進一步簡化。

「中國的轉基因食物」——「中國」、「轉基因」、「食物」。

經過處理,用戶非標準的query就被轉化為標準的詞庫,就可以快速找到對應的內容了。如【圖1-1】所示。

5. Step2: 根據用戶輸入信息對內容進行篩選

經過對用戶的query解讀之後,其實就得到了一些標準化的詞,而這些詞就會對應一些搜索目標內容,接下來就是對於內容的篩選。

用戶進行了一次搜索,一部分結果被搜索了出來。那麼所有的內容根據「內容是否相關」、「內容是否被召回」兩個維度,就被分為了四部分。

A:召回的相關內容:搜索出來的內容中,和用戶搜索相關的部分。

B:召回的不相關內容:搜索出來的內容中,和用戶搜索不相關的部分。

C:未召回的相關內容:沒有搜索出來的內容中,和用戶搜索相關的部分。

D:未召回的不相關內容:沒有搜索出來的內容中,和用戶搜索不相關的部分。

搜索一般而言,決定是否篩選出來,會從兩個角度衡量,準確率,和召回率。

準確率就是所有搜到的內容裡面,相關的內容的比例。準確率alpha=A/(A+ B)

召回率就是所有應該搜到的內容裡面,真正被搜出來的比例。召回率beta =A/(A+ C)

準確率和召回率是一對存在矛盾的指標。需要權衡。最終衡量會取兩個的調和平均數作為目標函數。即F值F=2alpha times beta /(alpha +beta )

這三個概念在搜索優化中是關鍵性指標,牽扯到人工打分和更高級的優化。這裡不展開更多。我們只需要記住一點:並不是所有的包含用戶query關鍵詞的結果都應該被召回。

6. Step3:對篩選後的結果進行排序

排序影響著搜索的結果質量,越往前的結果約容易獲得用戶的點擊。好的搜索不僅僅是把應該搜索的內容儘可能的搜索出來,同時還要考慮應該把最容易吸引用戶的內容展示在前面。

搜索排序比較大的基礎邏輯是通用的:

用戶輸入一個文本轉化為標準詞庫中的詞,搜索系統根據每個具體內容是否包含這些詞決定是否展示這些內容,同時搜索系統根據文本相關性給這些要展示的內容一個分數。而最終排序則根據每個內容的分數排序。

這個Lucene的的核心排序公式的原理,網上有介紹。但是實際的情況其實更為複雜。還是以我們之前提到的新聞搜索系統為例(方便理解,再貼一遍圖)

如果用戶搜索「轉基因」,那麼這個轉基因的文本出現在標題中,還是出現在導語中,還是出現在正文中,體現在分數上應該是不一樣的。顯然出現在標題中應該有更高的分數。同樣也需要考慮業務數據,比如一個閱讀量10萬+的帖子和一個閱讀量3的帖子相比,即使閱讀量低的帖子文本相關性更強,但是顯然10萬+的帖子應該在前面。

其實所有的數據都可以分為兩類,文本和數據。文本用於計算內容的相關性,這部分的打分交給Lucene成熟的演算法解決,目前市面上也都有成型的開源解決方案。而怎麼處理文本之間的關係,以及數據之間的關係,才是一個搜索系統設計最核心的部分。

基於Lucene的Solr系統為例,文本和數據配置代碼其實很簡單。在<str name="bf">和<str name="qf">標籤中只需要幾行代碼就能完成。

<str name="bf">中是對於業務數據賦予權重。

<str name="qf">中是對於文本數據賦予權重。

在研究過Solr系統這個機制之後,對Solr核心公式進行變形,就得到了一個公式:

score=dfrac{S cdot sum N_xcdot M_x+sum K_ycdot L_y}{sqrt{sum N_x^2+sum K_y^2}}

  • N_x 代表針對文本x,我們給出的文本分數權重。比如這個系統中有三種文本,標題,導語,正文。根據重要性,標題權重為10,導語權重為5,正文權重為1。

  • M_x 代表針對文本x,Lucene演算法給出的文本相關性分數,這個會綜合考慮文本的字數,這個搜索詞在所有文本中出現的概率等等因素(想進一步了原理的同學,可以看下TF-IDF餘弦相似性的介紹)。

  • K_y 代表針對數據y,我們給出的數據權重。比如這個系統中有三種數據,評論量,分享數,閱讀量。根據重要性,標題評論數權重為100,分享數權重為200,閱讀量權重為1。(一般而言會引入log時間衰減性,這裡暫不討論)

  • L_y 代表針對數據y,具體的值。比如這個系統得三種數據,評論量,分享數,閱讀量。
  • sqrt{sum N_x^2+sum K_y^2}代表歸一化係數,意味著權重可以給的非常大,最後總的分值也會在一個合理的範圍內。

  • S 是本次根據演算法索引判斷出的。代表本次打分,用戶輸入query提供信息的信息量大小。如果輸入query提供了越多的信息,則S越大。

  • S增加,sqrt{sum N_x^2+sum K_y^2}不變,sum K_ycdot L_y之前的係數不變,sum N_xcdot M_x之前的係數增加。而sum N_xcdot M_x代表文本數據的對整體分數的貢獻,則S 越大,就說明文本數據相比於業務數據就佔有更大的權重。比如:輸入「北京國慶交通擁堵」,和輸入「交通擁堵」相比,「北京國慶交通擁堵」提供給了系統更多的信息,S值更大,文本的打分在總分數匯總佔比越大。

所以我們可以看到,其實最終影響排序的,是我們對於文本數據和業務數據的賦予的權重,即:N_x 代表針對文本x的權重,和K_y 代表針對數據y的權重。

這兩組數據,影響了搜索最終的排序,而這組數據的賦值,正是搜索系統的對業務的理解。

7. 小結:

本篇文章是對於搜索系統工作原理一個整體的介紹,對於原理的理解,是設計系統舉重若輕的基礎。

在這些基礎原理之上,搜索系統還有很多標準功能。那麼一個比較完備的搜索系統應該具備怎樣的標準功能?這些功能又有著怎麼的原理?移動時代,搜索前端設計應該如何規劃?歡迎關注專欄,繼續收看下期。(下期保證沒有公式=。=)

------------------------------------

下期預告:做個夠用的搜索,其實也很簡單(二)搜索功能大盤點

推薦閱讀:

沒有產品經理的經歷,怎麼寫產品經理的求職簡歷呢?應該突出什麼特質或經歷
PMcom種子項目報道:出海做印度最大的TMT資訊平台:極光球
馬力的知乎 Live: 設計師和產品經理

TAG:产品经理 | 搜索 | 策略 |