algorithm - 如何根据增量数据评估复杂的表达式树？

Question

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

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

因此，如果 a=b 和 c=d 则左右子节点都匹配，因此过滤器匹配。

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

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.age 和 student.grade 过滤器需要以某种方式绑定(bind)在一起以便存储仅当它们匹配同一对象时才为中间匹配。我一辈子都想不出该怎么做。

我的过滤节点抽象基类:

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 语句应该仅在子项匹配同一对象时才匹配。

Answer 1

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

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

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

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

在所有输入记录都按上述方式处理后，您只需要对 thereExists 节点上方的树节点求值一次。请注意，任何引用单个记录属性的内容必须出现在树中thereExists 节点下方的某处。树中 thereExists 节点之上的所有内容都只允许测试集合的“全局”属性，或使用逻辑运算符(AND、OR、异或、非等)。逻辑运算符本身可以出现在树中的任何位置。

使用它，您现在可以评估像这样的表达式

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 学生，则报告"is"，否则为“否”。如果您按照我的建议跟踪令人满意的记录，您也可以在回答"is"的情况下将这些记录转储。

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