0

データのコレクションと、そのデータに対して実行したい検索フィルターのコレクションがあります。フィルターは LDAP 検索フィルター形式に従い、式ツリーに解析されます。データは一度に 1 項目ずつ読み取られ、すべてのフィルターを介して処理されます。中間一致結果は、すべてのデータが処理されるまで、ツリーの各リーフ ノードに格納されます。次に、ツリーをトラバースし、論理演算子を各リーフ ノードの中間結果に適用することによって、最終結果が取得されます。たとえば、フィルターがある(&(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一致です。それに対して2 番目のstudentノードを実行します。root.right.left一致です。次に、ツリーをトラバースして、すべてのノードが一致したことを確認し、最終結果が一致することを確認します。

問題は、共通性に基づいて中間一致を制限する必要があることです。同じオブジェクトに一致する場合にのみ中間一致を保存するには、フィルターstudent.ageとstudent.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ノードを1 回だけ評価する必要があります。個々のレコードのプロパティを参照するものは、ツリー内のノードの下のどこかに表示される必要があることに注意してください。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 生徒の両方が含まれている場合は「yes」、そうでない場合は「no」と報告します。私が提案したように満足のいく記録を追跡すれば、「はい」の答えの場合にこれらを捨てることもできます.

また、2 番目の演算子タイプ を追加することもできますforAll。これは、その部分式がすべての入力レコードに対して true であることを確認します。しかし、これはおそらくそれほど有用ではなく、いずれにしても でシミュレートできforAll(expr)ますnot(thereExists(not(expr)))。

于 2013-10-23T21:06:15.063 に答える