如何拆分搜索查询

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) 
     ),