0

我有一组数据和一组要针对该数据运行的搜索过滤器。过滤器遵循 LDAP 搜索过滤器格式并被解析为表达式树。数据一次读取一项，并通过所有过滤器进行处理。中间匹配结果存储在树的每个叶节点中，直到处理完所有数据。然后通过遍历树并将逻辑运算符应用于每个叶子节点的中间结果来获得最终结果。例如，如果我有过滤器，(&(a=b)(c=d))那么我的树将如下所示：

root = "&"
    left = "a=b"
    right = "c=d"

因此，如果a=b然后c=d左右子节点都是匹配的，因此过滤器是匹配的。

数据是不同类型对象的集合，每个对象都有自己的字段。例如，假设集合代表学校的一个班级：

class { name = "math" room = "12A" }
teacher { name = "John" age = "35" }
student { name = "Billy" age = "6" grade = "A" }
student { name = "Jane" age = "7" grade = "B" }

所以一个过滤器可能看起来像这样(&(teacher.name=John)(student.age>6)(student.grade=A))被解析：

root = "&"
    left = "teacher.name=John"
    right = "&"
        left = "student.age>6"
        right = "student.grade=A"

我将class对象运行在它上面；无匹配。我将teacher对象运行在它上面；root.left是一场比赛。我针对它运行第一个student节点；root.right.right是一场比赛。我针对它运行第二个student节点；root.right.left是一场比赛。然后我遍历树并确定所有节点都匹配，因此最终结果是匹配的。

问题是中间匹配需要基于共性进行约束：student.ageandstudent.grade过滤器需要以某种方式绑定在一起，以便仅当它们与同一对象匹配时才存储中间匹配。我无法为我的生活弄清楚如何做到这一点。

我的过滤器节点抽象基类：

class FilterNode
{
public:
    virtual void Evaluate(string ObjectName, map<string, string> Attributes) = 0;
    virtual bool IsMatch() = 0;
};

我有一个LogicalFilterNode处理逻辑 AND、OR 和 NOT 操作的类；它的实现非常简单：

void LogicalFilterNode::Evaluate(string ObjectName, map<string, string> Attributes)
{
    m_Left->Evaluate(ObjectName, Attributes);
    m_Right->Evaluate(ObjectName, Attributes);
}

bool LogicalFilterNode::IsMatch()
{
    switch(m_Operator)
    {
    case AND:
        return m_Left->IsMatch() && m_Right->IsMatch();
    case OR:
        return m_Left->IsMatch() || m_Right->IsMatch();
    case NOT:
        return !m_Left->IsMatch();
    }
    return false;
}

然后我有一个ComparisonFilterNode处理叶节点的类：

void ComparisonFilterNode::Evaluate(string ObjectName, map<string, string> Attributes)
{
    if(ObjectName == m_ObjectName) // e.g. "teacher", "student", etc.
    {
        foreach(string_pair Attribute in Attributes)
        {
            Evaluate(Attribute.Name, Attribute.Value);
        }
    }
}

void ComparisonFilterNode::Evaluate(string AttributeName, string AttributeValue)
{
    if(AttributeName == m_AttributeName) // e.g. "age", "grade", etc.
    {
        if(Compare(AttributeValue, m_AttributeValue) // e.g. "6", "A", etc.
        {
            m_IsMatch = true;
        }
    }
}

bool ComparisonFilterNode::IsMatch() { return m_IsMatch; }

如何使用：

FilterNode* Root = Parse(...);
foreach(Object item in Data)
{
    Root->Evaluate(item.Name, item.Attributes);
}
bool Match = Root->IsMatch();

本质上，我需要的是子级具有相同对象名称的 AND 语句，只有当子级与同一对象匹配时，AND 语句才应匹配。

4

1 回答 1

1

创建一个新的一元“运算符”，我们称之为thereExists：

  1. 有状态，并且
  2. 声明其子子表达式必须由单个输入记录满足。

具体来说，对于表达式树中运算符的每个实例，thereExists您应该存储一个位，指示该树节点下的子表达式是否已被迄今为止看到的任何输入记录满足。这些标志最初将设置为false.

要继续有效地处理您的数据集（即逐个输入记录，而不必将整个数据集加载到内存中），您应该首先预处理查询表达式树以提取thereExists运算符的所有实例的列表。然后，当您读取每个输入记录时，针对每个仍将其satisfied标志设置为的运算符的子子表达式对其进行测试false。现在满足的任何子表达式都应将其父thereExists节点的satisfied标志切换为--如果您希望实际看到的不仅仅是“是”，那么true最好将满足记录的副本附加到新满足的节点thereExists或“否”回答整个查询。

在如上所述处理了所有输入记录之后，您只需评估节点上方的树节点thereExists一次。请注意，引用单个记录的属性的任何内容都必须thereExists出现在树中某个节点下方的某个位置。树中节点上方的所有thereExists内容仅允许测试集合的“全局”属性，或thereExists使用逻辑运算符（AND、OR、XOR、NOT 等）组合节点的结果。逻辑运算符本身可以出现在树中的任何位置。

使用它，您现在可以评估表达式，例如

root = "&"
    left = thereExists
        child = "teacher.name=John"
    right = "|"
        left = thereExists
            child = "&"
                left = "student.age>6"
                right = "student.grade=A"
        right = thereExists
            child = "student.name = Billy"

如果记录集合包含名为“John”的教师和名为“Billy”的学生或 6 岁以上的 A 学生，则这将报告“是”，否则为“否”。如果您按照我的建议跟踪令人满意的记录，您还可以在回答“是”的情况下将这些记录丢弃。

您还可以添加第二个运算符类型 ，forAll它检查每个输入记录的子表达式是否为真。但这可能没有那么有用，无论如何您都可以forAll(expr)使用not(thereExists(not(expr))).

于 2013-10-23T21:06:15.063 回答