如何分解搜索查询

Question

我正在为CCG开发搜索引擎.我希望用户能够根据"blue brigade hero enhancements that can discard ec's"或等查询找到卡片"purple kings of israel".有许多变量需要搜索:旅(紫色,蓝色),类型(英雄,邪恶角色[ec]),特殊能力(丢弃)和标识符(以色列国王).我正在考虑重新寻找常见的搜索参数.我知道这并不容易,微调需要很长时间,但是有人能指出我正确的方向吗？正则表达式甚至是推荐的解决方案吗？我不知道它是否重要,但我使用的是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是一个经典的选择(你不必阅读所有这些,只是关于词法分析器和解析器的部分).

如果您不想自己编写整个解析器(因为这可能非常耗时且容易出错),您将需要一个解析器生成器(即,为给定语法创建解析器源代码的程序); 这是一个有关PHP的一些建议的问题.

您还应该考虑阅读自然语言处理技术.有来自斯坦福大学的网络课程在这里,我"参加"现在,可以全心全意地推荐它.