1

2 つの XML ファイルがあり、そのサブセクションが等しいかどうかを比較したいと考えています。XML ファイルは非常に異なる場合がありますが、例を示します。次の XML ファイルがあります。

<EXECUTION_SET>
  <RESULT query_id="7" >
    <OP>
      <PROJ>
        <COLUMN col_name="City.ID" col_type="3" col_length="11" />
        <OP>
          <JOIN>
            <OP>
              <TABLE name="City" alias="City" access_type="5" total_record_length="67">
                <COLUMN col_name="ID" col_type="3" col_length="11" raw_length="4" /> 
                <COLUMN col_name="Name" col_type="254" col_length="35" raw_length="35" /> 
                <COLUMN col_name="CountryCode" col_type="254" col_length="3" raw_length="3" /> 
                <COLUMN col_name="District" col_type="254" col_length="20" raw_length="20" /> 
                <COLUMN col_name="Population" col_type="3" col_length="11" raw_length="4" /> 
              </TABLE>
            </OP>
            <OP>
              <SEL>
                <COND>
                  <COND>
                    <VALUE><VARIABLE>Country.Population</VARIABLE></VALUE>
                  </COND>
                  <BOP><![CDATA[>]]></BOP>
                  <COND>
                    <VALUE><CONSTANT>80000000</CONSTANT></VALUE>
                  </COND>
                </COND>
                <OP>
                <OP>
                  <TABLE name="Country" alias="Country" access_type="5" total_record_length="261">
                    <COLUMN col_name="Code" col_type="254" col_length="3" raw_length="3" /> 
                    <COLUMN col_name="Name" col_type="254" col_length="52" raw_length="52" /> 
                    <COLUMN col_name="Continent" col_type="254" col_length="13" raw_length="1" /> 
                    <COLUMN col_name="Region" col_type="254" col_length="26" raw_length="26" /> 
                    <COLUMN col_name="SurfaceArea" col_type="4" col_length="10" raw_length="4" /> 
                    <COLUMN col_name="IndepYear" col_type="2" col_length="6" raw_length="2" /> 
                    <COLUMN col_name="Population" col_type="3" col_length="11" raw_length="4" /> 
                    <COLUMN col_name="LifeExpectancy" col_type="4" col_length="3" raw_length="4" /> 
                    <COLUMN col_name="GNP" col_type="4" col_length="10" raw_length="4" /> 
                    <COLUMN col_name="GNPOld" col_type="4" col_length="10" raw_length="4" /> 
                    <COLUMN col_name="LocalName" col_type="254" col_length="45" raw_length="45" /> 
                    <COLUMN col_name="GovernmentForm" col_type="254" col_length="45" raw_length="45" /> 
                    <COLUMN col_name="HeadOfState" col_type="254" col_length="60" raw_length="60" /> 
                    <COLUMN col_name="Capital" col_type="3" col_length="11" raw_length="4" /> 
                    <COLUMN col_name="Code2" col_type="254" col_length="2" raw_length="2" /> 
                  </TABLE>
                </OP>
                </OP>
              </SEL>
            </OP>
          </JOIN>
        </OP>
      </PROJ>
    </OP>
  </RESULT>
</EXECUTION_SET>

そして 2 番目の XML ファイル:

<EXECUTION_SET>
  <RESULT query_id="13" >
    <OP>
      <PROJ>
        <COLUMN col_name="Country.Code" col_type="254" col_length="3" />
        <OP>
          <SEL>
            <COND>
              <COND>
                <VALUE><VARIABLE>Country.Population</VARIABLE></VALUE>
              </COND>
              <BOP><![CDATA[>]]></BOP>
              <COND>
                <VALUE><CONSTANT>80000000</CONSTANT></VALUE>
              </COND>
            </COND>
            <OP>
            <OP>
              <TABLE name="Country" alias="Country" access_type="5" total_record_length="261">
                <COLUMN col_name="Code" col_type="254" col_length="3" raw_length="3" /> 
                <COLUMN col_name="Name" col_type="254" col_length="52" raw_length="52" /> 
                <COLUMN col_name="Continent" col_type="254" col_length="13" raw_length="1" /> 
                <COLUMN col_name="Region" col_type="254" col_length="26" raw_length="26" /> 
                <COLUMN col_name="SurfaceArea" col_type="4" col_length="10" raw_length="4" /> 
                <COLUMN col_name="IndepYear" col_type="2" col_length="6" raw_length="2" /> 
                <COLUMN col_name="Population" col_type="3" col_length="11" raw_length="4" /> 
                <COLUMN col_name="LifeExpectancy" col_type="4" col_length="3" raw_length="4" /> 
                <COLUMN col_name="GNP" col_type="4" col_length="10" raw_length="4" /> 
                <COLUMN col_name="GNPOld" col_type="4" col_length="10" raw_length="4" /> 
                <COLUMN col_name="LocalName" col_type="254" col_length="45" raw_length="45" /> 
                <COLUMN col_name="GovernmentForm" col_type="254" col_length="45" raw_length="45" /> 
                <COLUMN col_name="HeadOfState" col_type="254" col_length="60" raw_length="60" /> 
                <COLUMN col_name="Capital" col_type="3" col_length="11" raw_length="4" /> 
                <COLUMN col_name="Code2" col_type="254" col_length="2" raw_length="2" /> 
              </TABLE>
            </OP>
            </OP>
          </SEL>
        </OP>
      </PROJ>
    </OP>
  </RESULT>
</EXECUTION_SET>

この 2 つの XML ファイルで、このサブセクションが等しいかどうか、タグの下のサブセクションを比較したいと思います。そのために、次の両方の xpath クエリに対して実行doc.select_nodes(std::string("//TABLE[@name='Country']/ancestor::SEL/COND").c_str());し、それを変数pugi::xpath_node_set partialTree1とに書き込みますpartialTree2。

したがって、両方の xml ファイルのサブセクションを取得します。ここで、両方のサブセクションを比較したいと思います。それは良い効率的な方法でなければなりません。

解決策はありますが、多くの時間とスペースが必要なため、好きではありません。現時点では、traverse関数を使用してサブセクションをスローし、両方のサブセクションのすべてを文字列に書き込みます。それから私はそれを比較します。しかし、それにはもっと良い方法があるはずです。

誰かが何かアイデアを持っているといいですね。

4

1 に答える 1

3

クエリの結果、さまざまなドキュメントから一連のノードが得られます。各ノードには一定量の子孫があり、2 つのノードを比較するには、すべての子孫を比較する必要があります。1 つでも見逃すと、ツリーが等しいかどうかわかりません。

これは、ノードの文字列ダンプを比較するアプローチが、時間の観点から複雑さに関して最適であることを示唆しています。スペースの観点からは最適ではありません。スペースの観点から最適なアルゴリズムは、両方のツリーを同期して通過し、値を直接比較します。このようなものが動作するはずです：

template <typename It, typename Pred>
bool rangeEquals(It lb, It le, It rb, It re, Pred pred)
{
    It li = lb, ri = rb;

    for (; li != le && ri != re; ++li, ++ri)
        if (!pred(*li, *ri))
            return false;

    return li == le && ri == re;
}

bool attrEquals(pugi::xml_attribute la, pugi::xml_attribute ra)
{
    return
        strcmp(la.name(), ra.name()) == 0 &&
        strcmp(la.value(), ra.value()) == 0;
}

bool nodeEquals(pugi::xml_node ln, pugi::xml_node rn)
{
    return
        ln.type() == rn.type() &&
        strcmp(ln.name(), rn.name()) == 0 &&
        strcmp(ln.value(), rn.value()) == 0 &&
        rangeEquals(ln.attributes_begin(), ln.attributes_end(), rn.attributes_begin(), rn.attributes_end(), attrEquals) &&
        rangeEquals(ln.begin(), ln.end(), rn.begin(), rn.end(), nodeEquals);
}
于 2014-08-05T16:07:23.630 に答える