用于子集索引搜索的数据结构

我正在研究一个时间：2019-03-17 标签：c#jqueryimplementation我正在尝试找出一种有效的算法来在整个 DOM 的子集中定位元素（例如子选择器）。目前，我正在构建 DOM 时创建常用选择器的索引：class、id 和 tag。

正如人们所期望的那样，基本数据结构是一棵树Elements其中包含IEnumerable<Element> Children and a Parent。当使用搜索整个域时，这很简单Dictonary<string,HashSet<Element>>来存储索引。

我无法理解使用索引搜索元素子集的最有效方法。我使用术语“子集”来指代链中后续选择器将针对其运行的起始集。以下是我想到的方法：

1. 从子查询的整个 DOM 中检索匹配项，并消除不属于子集的匹配项。这需要遍历每个匹配的父级，直到找到根（并且将其消除）或找到子集的成员（并且它是子集，因此包含在内）
2. 为每个元素单独维护索引。
3. 为每个元素维护一组父元素（通过消除遍历使#1 更快）
4. 为每个子查询重建整个索引。
5. 除了主要选择器之外，只需手动搜索即可。

每种可能技术的成本很大程度上取决于所进行的具体操作。 #1 在大多数情况下可能相当不错，因为大多数情况下，当您进行子选择时，您的目标是特定元素。所需的迭代次数为结果数 * 每个元素的平均深度。

第二种方法是迄今为止最快的选择方法，但代价是存储需求随着深度呈指数级增长，并且索引维护困难。我几乎已经消除了这个。

第三种方法的内存占用相当糟糕（尽管比第二种方法好得多）——它可能是合理的，但除了存储要求之外，添加和删除元素变得更加昂贵和复杂。

第四种方法无论如何都需要遍历整个选择，因此它似乎毫无意义，因为大多数子查询只会运行一次。仅当希望重复子查询时，这才有用。 （或者，我可以在遍历子集时执行此操作 - 除非某些选择器不需要搜索整个子域，例如 ID 和位置选择器）。

第五种方法对于有限的子集来说很好，但对于占 DOM 大部分的子集来说比第一种方法要差得多。

关于如何最好地实现这一目标有什么想法或其他想法吗？考虑到正在搜索的子集的大小与 DOM 的大小，我可以通过猜测哪个更有效来混合 #1 和 #4，但这非常模糊，我宁愿找到一些通用的解决方案。现在我只使用#4（只有完整 DOM 查询使用索引），这很好，但如果你决定做类似的事情，那就太糟糕了$('body').Find('#id')

免责声明：这是早期优化。我没有需要解决的瓶颈，但作为一个学术问题我无法停止思考......

Solution

这是答案中提出的数据结构的实现。非常适合作为字典的近乎直接替代品。

interface IRangeSortedDictionary<TValue>: IDictionary<string, TValue>
{
    IEnumerable<string> GetRangeKeys(string subKey);
    IEnumerable<TValue> GetRange(string subKey);

}
public class RangeSortedDictionary<TValue> : IRangeSortedDictionary<TValue>
{
    protected SortedSet<string> Keys = new SortedSet<string>();
    protected Dictionary<string,TValue> Index = 
        new Dictionary<string,TValue>();
    public IEnumerable<string> GetRangeKeys(string subkey)
    {
        if (string.IsNullOrEmpty(subkey)) {
            yield break;
        }
        // create the next possible string match
        string lastKey = subkey.Substring(0,subkey.Length - 1) +
            Convert.ToChar(Convert.ToInt32(subkey[subkey.Length - 1]) + 1);

        foreach (var key in Keys.GetViewBetween(subkey, lastKey))
        {
            // GetViewBetween is inclusive, exclude the last key just in case
            // there's one with the next value
            if (key != lastKey)
            {
                yield return key;
            }
        }
    }

    public IEnumerable<TValue> GetRange(string subKey)
    {
        foreach (var key in GetRangeKeys(subKey))
        {
            yield return Index[key];
        }
    }
    // implement dictionary interface against internal collections
}

代码在这里：http://ideone.com/UIp9R

如果您怀疑名称冲突并不常见，那么只需走上树就可以足够快。

如果冲突很常见，那么使用擅长有序前缀搜索的数据结构（例如树）可能会更快。您的各种子集组成了前缀。然后，您的索引键将包括选择器和总路径。

对于 DOM：

<path>
  <to>
    <element id="someid" class="someclass" someattribute="1"/>
  </to>
</path>

您将拥有以下索引键：

<element>/path/to/element
#someid>/path/to/element
.someclass>/path/to/element
@someattribute>/path/to/element

现在，如果您根据前缀搜索这些键，您可以将查询限制为您想要的任何子集：

<element>           ; finds all <element>, regardless of path
.someclass>         ; finds all .someclass, regardless of path
.someclass>/path    ; finds all .someclass that exist in the subset /path
.someclass>/path/to ; finds all .someclass that exist in the subset /path/to
#id>/body           ; finds all #id that exist in the subset /body

树可以找到下界（第一个元素> =您的搜索值）O(log n），并且因为它是从那里排序的，所以您只需迭代，直到找到不再与前缀匹配的键。会非常快！

.NET 没有合适的树结构（它有 SortedDictionary 但不幸的是没有公开所需的LowerBound方法），因此您需要编写自己的方法或使用现有的第三方方法。优秀的C5通用集合库具有适合的特征树木Range方法。