我正在寻找一种内容寻址数据结构。

Question

3

我正在尝试设计一种数据结构，可以有效地从其内容的一部分中提取条目。

假设我正在寻找与此匹配的条目：[ x 2 3 x x ] 如果我的数据结构中有[ 0 2 3 4 5 ]或[ 3 2 3 7 8 ]，它们应该被我的查找函数返回。

我编写了这样一个数据结构，其中我将“模式”与数据结构的所有条目进行比较，但是这当然需要太长时间。我有一些想法，可以更快地完成这项任务，但它们实现起来相当复杂。是否已经存在类似于这样的东西？如果没有，您会如何处理？

- Ben

你现在是在进行哈希操作，还是在每次查找时迭代并检查特定的模式？ - Tim Post

+1给这个，我刚想问类似的问题 :) - Tim Post

@tinkertim 不，我没有进行哈希处理，那只是一个我忘记修改标题的想法。 - Ben

4个回答

4

嗯，一个后缀树可以在O(1)的时间内完成，但需要大量的内存。

- Vilx-

假设您有多个条目，您真正需要的是称为广义后缀树的数据结构，该数据结构通过将所有条目连接在一起，并在每个条目之间使用不同（唯一）的分隔符符号来形成。后缀数组是一种理论上更慢但内存效率更高的替代方案。 - j_random_hacker

后缀树和后缀数组非常强大，但它们难以实现。如果找不到现有的实现，请给自己充足的两周时间来尝试理解Ukkonnen或McCreight的线性时间构建算法的原始论文。 - j_random_hacker

它如何在O(1)时间复杂度内实现呢？如果您的意思是检索包含特定子字符串的所有条目，则可以在O(length(substring))时间内完成。我认为，给定的问题并不限制已知位必须是单个连续子字符串。 - Darius Bacon

我认为它确实限制了单个连续子字符串，但是是的，这一点并不是很清楚。至于O(1) - 嗯，这取决于你如何看待它。在这种情况下，大O符号仅取决于子字符串的长度，而不是字典中条目的数量。 - Vilx-

经典地，当人们谈论搜索/排序算法时，他们将大O表示法与条目数量相关联，而不是它们的长度。从这个角度来看，它是O(1)。 - Vilx-

2

你正在尝试实现的东西看起来很像元组空间。

- vartec

是的，这实际上是我想要做的，但我需要一个实现它的提示。我猜我得看看代码！谢谢 - Ben

我有具体的需求，但为了提问简化了问题。现有的解决方案并不完全符合我的要求，但它们是实现的好起点，我正在努力。 - Ben

0

您可以看一下 RETE 算法。这个通用问题在70年代的人工智能系统中出现了；AI编程范例的第14章涵盖了它。（如果我没记错，主要是 starblue 的回答和决策树的阐述。）

- Darius Bacon

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- starblue · Accepted Answer

首先想到的是为元组中的每个位置设置一个哈希表。要进行搜索，需要将所有具有指定值的位置的结果进行交集运算。