如何拆分搜索查詢

Question

我正在開發CCG的搜索引擎。我希望用戶能夠根據如"blue brigade hero enhancements that can discard ec's"或"purple kings of israel"的查詢查找卡片。搜索有很多變數：旅（紫色，藍色），類型（英雄，邪惡角色[ec's]），特殊能力（丟棄）和標識符（以色列國王）。我在考慮尋找常見的搜索參數。我知道這並不容易，調整需要很長時間，但是有人能指出我的方向嗎？是正則表達式甚至推薦的解決方案？我不知道它是否重要，但我使用的是PHP和MySQL。

Answer 1

你必須編寫一個解析器來解析這樣的查詢字符串。

正則表達式將是有益的發現「動詞」，並在查詢字符串「名詞」，但你可能還需要一個非語境語法描述您的查詢語言，例如像這樣：

<QUERY> := <TARGET_SPEC> 
<TARGET_SPEC> := <OBJECT> 'that can' <ABILITY> 
<TARGET_SPEC> := <OBJECT> 
<OBJECT> := <COLOR> <WHAT> 
<OBJECT> := <WHAT> 
<COLOR> := 'blue' | 'red' | 'purple' | 'green' 
<WHAT> := <ITEM> | <HERO> 
<ITEM> := <ADJECTIVE> <ITEM> 
<ADJECTIVE> := 'brigade' | 'hero' | 'magic' | 'enhanced' | 'rustproof' 
<ITEM> := 'enhancements' | 'sword' | 'potion' 
<HERO> := <HERO> 'of' <COUNTRY> 
<HERO> := 'kings' | 'knights' | 'thiefs' 
<COUNTRY> := 'israel' | 'palestine' | 'jordan' | 'egypt' 
<ABILITY> := <ABILITY> 'and' <ABILITY> 
<ABILITY> := 'swim' | 'dance' | discard <DISCARDABLE> | 'kill' <HERO> | 'use' <ITEM> 
<DISCARDABLE> := 'ec's' | 'et's' | 'etc' 

圍繞這樣的語法構建的解析器將能夠確定您的查詢的哪一部分是一個對象，這是一種能力，顏色，國家等。例如，給定輸入字符串'可以游泳的約旦紅騎士'，解析器將選擇正確的規則並應用它們：

<QUERY> := 'red knights of jordan that can swim' 
<TARGET_SPEC> := 'red knights of jordan that can swim' 
<TARGET_SPEC> := 'red knights of jordan' 'that can' 'swim' 
<OBJECT> := 'red knights of jordan' 
<ABILITY> := 'swim' 
<COLOR> := 'red' 
<WHAT> := 'knights of jordan' 
<HERO> := 'knights' 'of' 'jordan' 
<HERO> := 'knights' 
<COUNTRY> := 'jordan' 

根據提取的信息，您將能夠創建搜索條件。

使用語法還有一個額外的好處，就是可以解決一些難以用其他方式解決的歧義 - 例如，如果用戶要求「可以殺死白色騎士的紅色國王」，簡單的算法只需通過查找顏色將每個單詞與可用顏色列表進行匹配將會失敗。

我推薦閱讀一本關於編譯器設計的書 - Dragon Book是一個經典選擇（你不必閱讀全部內容，只是關於詞法分析器和解析器的部分）。

如果您不想自己編寫整個解析器（因爲這可能相當耗時且容易出錯），您需要一個解析器生成器（即，創建解析器源代碼的程序給定語法）; here對PHP有一些建議。

你也應該考慮閱讀自然語言處理技術。有一個來自斯坦福大學的在線課程here，我現在「參加」它，並且可以全心全意地推薦它。

Answer 2

我真的很喜歡socha's suggestion，但我會考慮一個更簡單的。

如果您有已知搜索字詞的字典並能夠更正它們的語法和語法（提示：使用您的數據庫，並使用OED作爲緩存層，並在Google中拋出任何緩存未命中），則可以執行搜索binary bucket sorting每個術語變成已知類型的集合。使用你的例子，每個桶將是：brigade_purple，brigade_blue，type_hero，type_evil，你的每一個特殊能力，以及你的特殊類型標識符。

對於每張卡片，構建一個符合您的存儲桶的位域。對於每個用戶查詢，構建相同的。然後，通過按位遍歷數據庫返回符合您的位掩碼的結果，我假設這個玩具示例的形狀類似於B+ tree，按主位順序最接近掩碼的結果進行排序。這樣做的好處是可以擴展到您的後臺位域的最大長度，在許多數據庫實現中實際上可以是無限的。

好的，這有點技術性。無論如何，我都會構建搜索數據庫。

Answer 3

與TierTempCur

由於

--/*Use Rela table to get the offspring of the parent*/ 

     (
      SELECT Rela.ID_RSSD_PARENT 
       , Rela.ID_RSSD_OFFSPRING 
       , '12/31/2011' AS REPORT_DATE 
       , 1 As TREE_LVL 
       , CHECKSUM(ID_RSSD_PARENT, ID_RSSD_OFFSPRING) As CHKSUM 
       , RIGHT('000000000'+ CONVERT(VARCHAR(MAX),ID_RSSD_OFFSPRING),9) AS RSSD_PATH 
      FROM CUV_RELATIONSHIPS As Rela 
      WHERE ID_RSSD_PARENT = 451965 AND '12/31/2011' BETWEEN D_DT_START AND D_DT_END 
       AND Rela.CTRL_IND = 1  --/* indicates subsidiary */ 
       AND Rela.OTHER_BASIS_IND not in (3,8) --/* Per DM's job */ 

      UNION ALL 

      SELECT Rela.ID_RSSD_PARENT 
       , Rela.ID_RSSD_OFFSPRING 
       , REPORT_DATE 
       , TREE_LVL + 1 As TREE_LVL 
       , CHECKSUM(Rela.ID_RSSD_PARENT, Rela.ID_RSSD_OFFSPRING) As CHKSUM 
       , Tmp.RSSD_PATH + '\' + RIGHT('000000000'+ CONVERT(VARCHAR(MAX),Rela.ID_RSSD_OFFSPRING),9) AS RSSD_PATH 
      FROM CUV_RELATIONSHIPS As Rela 
      INNER JOIN TierTempCur As Tmp 
       ON Rela.ID_RSSD_PARENT = Tmp.ID_RSSD_OFFSPRING 
       AND REPORT_DATE BETWEEN Rela.D_DT_START AND Rela.D_DT_END 
      WHERE TREE_LVL < 20   --/*max depth for the tier is 20 -- to end self referencing parent/child relationships */ 
       AND Rela.CTRL_IND = 1  --/* indicates subsidiary */ 
       AND Rela.OTHER_BASIS_IND not in (3,8) 
     ),