0

我有一个 5 MB XML 平面结构，我想稍后访问它的数据。我在 Java 中使用 XOM Parser 来解析 XML，并且我不想每次要检索数据时都在整个 Tree 上循环，因为文件大小需要一段时间。

XML 看起来像这样

<TypeDesc Type="Person" Id="1" PKey="X0" xml:lang="EN" ShDes="t1" LongDes="test 1"/>
<TypeDesc Type="Person" Id="2" PKey="X1" xml:lang="EN" ShDes="t2" LongDes="test 2"/>
<TypeDesc Type="Person" Id="3" PKey="X3" xml:lang="EN" ShDes="t3" LongDes="test 2"/>
...
<TypeDesc Type="Person" Id="n" PKey="PAYMN" xml:lang="EN" ShDes="PAYMN" LongDes="payment"/>
<TypeDesc Type="Student" Id="1" PKey="X0" xml:lang="EN" ShDes="t1" LongDes="good"/>
<TypeDesc Type="Student" Id="2" PKey="X1" xml:lang="EN" ShDes="t2" LongDes="bad"/>
<TypeDesc Type="Student" Id="3" PKey="X3" xml:lang="EN" ShDes="t3" LongDes="fair"/>
...
<TypeDesc Type="Student" Id="n" PKey="PAYMN" xml:lang="EN" ShDes="PAYMN" LongDes="fair"/>

在我的逻辑中，如果 PKEY = SOMESTUFF AND Type = OtherStuff，我想检索节点的 longDes

如果满足其他属性，则循环整个事物并检索 longDes 是非常昂贵的。

如何存储我的数据，以便我可以在 O(1) 而不是 O(n) 中访问它们，以便我在整个 XML 上循环一次并访问数据结构以供以后迭代。

4

2 回答 2

1

您不太可能找到一个恒定时间的查找过程来满足其当前形式。此外，恒定时间查找是一项特定要求，还是您将其作为项目状态/设置的盲目观点的一部分？又名“XY 问题”。您可能会找到最好的算法是O(n log n)或O(log n)算法；查看Big O 备忘单

我建议您查看能够解析此结构的现有框架：

  1. Xstream
  2. JAXB
  3. XML Bean

如果您对 XOM 感到满意，请不要费心移动，但我相信您在搜索时需要考虑数据的结构，例如使用索引，或者以有效的形式存储它——例如前缀Tree/Trie——然后将其序列化到磁盘/存储中，以便通过明显的空间/时间折衷重新解析更快？

除此之外，您的数据是否必须采用 XML 格式？你能把它转换成另一种格式吗？例如协议缓冲区，或将数据放入数据库（SQL 或 NoSQL）中，尽管这可能会根据您的操作而过大？

我还会问自己以下问题：

  1. 我如何获得这些数据？我是否丢失了可能有助于查找的信息？
  2. 一个有效的搜索算法在这里有帮助吗？
  3. 这些数据是否排序？我可以有效地对其进行排序，以便后续查找更有效吗？
于 2013-09-18T11:00:21.190 回答
0

我使用哈希表来存储数据。为每种类型构造了一个哈希表。每个哈希表的键是我要检查的所有属性的串联，存储的值就是我要检索的值。它非常高效且接近 O(1)

于 2013-09-18T16:35:24.500 回答