近似容忍映射
Approximation-tolerant map
我正在处理整数数组，它们的大小都相同 l。
我有一组静态的它们，我需要构建一个函数来有效地查找它们。
棘手的部分是我需要搜索的数组中的元素可能会偏移 1.
给定数组 {A_1, A_2, ..., A_n} 和一个数组 S，我需要一个函数 search这样：
search(S)=x iff ∀i: A_x[i] ∈ {S[i]-1, S[i], S[i]+1}.
一个可能的解决方案是将每个向量视为 l 维 space 中的一个点并寻找最近的点，但它的成本约为 O(l*n) space 和 O(l*log(n)) 及时。
是否有更复杂 space 的解决方案（当然 and/or 时间）？
我的阵列各不相同，良好的启发式方法可能就足够了。
如果维数不是很小，那么最好的解决方案可能是构建一个决策树，沿着不同的维数递归地划分集合。
每个节点，包括根节点，都是一个散列table，从某个维度的可能值到：
- 在公差范围内匹配该值的点列表，如果它足够小；或
- 相似树中的相同点在剩余维度上进行分区。
由于每一层完全消去一维，树的深度最多为L，查找时间为O(L)。
沿着每条路径选择维度的顺序当然很重要——错误的选择可能会导致数据结构的大小爆炸，每个点都会出现多次。
虽然你的分数是 "pretty different"，但应该可以构建一个重复最少的树。我会尝试使用 ID3 算法来选择维度：https://en.wikipedia.org/wiki/ID3_algorithm。这基本上意味着你贪婪地选择了使用熵度量最大化集合大小整体减少的维度。
考虑具有以下值的搜索数组 S：
S = [s1, s2, s3, ... , sl]
和平均值：
s̅ = (s1 + s2 + s3 + ... + sl) / l
和两个匹配数组，一个是每个值都比 S 中的相应值大一，另一个是每个值都小一：
A1 = [s1+1, s2+1, s3+1, ... , sl+1]
A2 = [s1−1, s2−1, s3−1, ... , sl−1]
这两个数组的平均值为：
a̅1 = (s1 + 1 + s2 + 1 + s3 + 1 + ... + sl + 1) / l = s̅ + 1
a̅2 = (s1 − 1 + s2 − 1 + s3 − 1 + ... + sl − 1) / l = s̅ − 1
所以每个匹配数组，其值与搜索数组中的对应值最多相差 1，其平均值与搜索数组的平均值最多相差 1。
如果你计算并存储每个数组的平均值，然后根据它们的平均值对数组进行排序（或者使用额外的数据结构，使你能够找到具有某个平均值的所有数组），你可以快速识别哪些数组的平均值在搜索数组平均值的 1 以内。根据数据，这可能会大大减少您必须检查相似性的数组数量。
在对数组进行预处理并存储它们的平均值之后，执行搜索将意味着遍历搜索数组以计算平均值，查找哪些数组具有相似的平均值，然后遍历这些数组检查每个值。
如果您希望许多数组具有相似的平均值，则可以使用多个平均值来检测局部差异很大但平均相似的数组。你可以例如计算这四个平均值：
- the first half of the array
- the second half of the array
- the odd-numbered elements
- the even-numbered elements
实际数据的分析应该会给你更多关于如何划分数组和组合不同的平均数才能最有效的信息。
如果一个数组的总和不能超过整数大小，可以存储每个数组的总和，并检查它是否在搜索数组总和的l以内，而不是使用平均值。这将避免必须使用浮点数和除法。
（您可以通过存储其他易于计算且不会占用太多 space 存储的属性来扩展这个想法，例如最高值和最低值，最大jump, ...他们可以帮助创建每个阵列的指纹，这取决于数据。)
我会亲自为查找创建类似 Trie 的内容。我说 "something like" 是因为每个索引最多有 3 个可能匹配的值。所以我们不是在创建决策树，而是在创建 DAG。有时我们有选择。
这很简单，将 运行（带回溯）在最长时间内 O(k*l)。
但这就是诀窍。每当我们看到可以进入下一个匹配状态的选择时，我们就可以创建一个合并状态来尝试所有这些状态。我们可以创建一些或很多这样的合并状态。每个人都会将选择推迟 1 步。如果我们仔细跟踪我们创建的合并状态，我们可以一遍又一遍地重复使用相同的状态。
理论上，我们可以为数组的任意子集生成部分匹配。这可以在阵列数量上呈指数增长。在实践中，很可能只会结束其中的几个合并状态。但我们仍然可以保证权衡——更多的状态在前面 运行s 之后更快。所以我们优化直到我们完成或达到我们想要的数据量的限制。
这是 Python 中的一些概念验证代码。它可能会及时构建匹配器 O(n*l) 并及时匹配 O(l)。但是只能保证及时构建匹配器 O(n^2 * l^2) 并及时匹配 O(n * l).
import pprint
class Matcher:
def __init__ (self, arrays, optimize_limit=None):
# These are the partial states we could be in during a match.
self.states = [{}]
# By state, this is what we would be trying to match.
self.state_for = ['start']
# By combination we could try to match for, which state it is.
self.comb_state = {'start': 0}
for i in range(len(arrays)):
arr = arrays[i]
# Set up "matched the end".
state_index = len(self.states)
this_state = {'matched': [i]}
self.comb_state[(i, len(arr))] = state_index
self.states.append(this_state)
self.state_for.append((i, len(arr)))
for j in reversed(range(len(arr))):
this_for = (i, j)
prev_state = {}
if 0 == j:
prev_state = self.states[0]
matching_values = set((arr[k] for k in range(max(j-1, 0), min(j+2, len(arr)))))
for v in matching_values:
if v in prev_state:
prev_state[v].append(state_index)
else:
prev_state[v] = [state_index]
if 0 < j:
state_index = len(self.states)
self.states.append(prev_state)
self.state_for.append(this_for)
self.comb_state[this_for] = state_index
# Theoretically optimization can take space
# O(2**len(arrays) * len(arrays[0]))
# We will optimize until we are done or hit a more reasonable limit.
if optimize_limit is None:
# Normally
optimize_limit = len(self.states)**2
# First we find all of the choices at the root.
# This will be an array of arrays with format:
# [state, key, values]
todo = []
for k, v in self.states[0].iteritems():
if 1 < len(v):
todo.append([self.states[0], k, tuple(v)])
while len(todo) and len(self.states) < optimize_limit:
this_state, this_key, this_match = todo.pop(0)
if this_key == 'matched':
pass # We do not need to optimize this!
elif this_match in self.comb_state:
this_state[this_key] = self.comb_state[this_match]
else:
# Construct a new state that is all of these.
new_state = {}
for state_ind in this_match:
for k, v in self.states[state_ind].iteritems():
if k in new_state:
new_state[k] = new_state[k] + v
else:
new_state[k] = v
i = len(self.states)
self.states.append(new_state)
self.comb_state[this_match] = i
self.state_for.append(this_match)
this_state[this_key] = [i]
for k, v in new_state.iteritems():
if 1 < len(v):
todo.append([new_state, k, tuple(v)])
#pp = pprint.PrettyPrinter()
#pp.pprint(self.states)
#pp.pprint(self.comb_state)
#pp.pprint(self.state_for)
def match (self, list1, ind=0, state=0):
this_state = self.states[state]
if 'matched' in this_state:
return this_state['matched']
elif list1[ind] in this_state:
answer = []
for next_state in this_state[list1[ind]]:
answer = answer + self.match(list1, ind+1, next_state)
return answer;
else:
return []
foo = Matcher([[1, 2, 3], [2, 3, 4]])
print(foo.match([2, 2, 3]))
请注意，我故意设置了一个有 2 个匹配项的情况。它报告了他们两个。 :-)
我想出了一个从 派生的进一步方法：构建一个简单的决策树，它可能在多个分支中有某些数组。即使我正在搜索的数组中的错误大于 1，它也能正常工作。
思路如下：给定数组集As...
选择一个 index 和一个 pivot。
我将枢轴固定为一个常量值，该值适用于我的数据，并尝试了所有索引以找到最佳索引。尝试多个支点可能会更好，但我不需要。
将 As 划分为两个可能相交的子集，一个用于数组（其第 index 个元素）小于主元，一个用于较大的数组。非常接近枢轴的数组被添加到两个集合中：
function partition( As, pivot, index ):
return {
As.filter( A => A[index] <= pivot + 1 ),
As.filter( A => A[index] >= pivot - 1 ),
}
递归地将前面的两个步骤应用于每个子集，当子集只包含一个元素时停止。
这里是一个用这个算法生成的可能树的例子（注意A2同时出现在根节点的左右子节点上）：
{A1, A2, A3, A4}
pivot:15
index:73
/ \
/ \
{A1, A2} {A2, A3, A4}
pivot:7 pivot:33
index:54 index:0
/ \ / \
/ \ / \
A1 A2 {A2, A3} A4
pivot:5
index:48
/ \
/ \
A2 A3
然后搜索函数将其用作普通决策树：它从根节点开始，递归到左子节点或右子节点，具体取决于其在索引 currentNode.index 处的值是大于还是小于currentNode.pivot。它递归地进行，直到到达叶子。
一旦构建了决策树，时间复杂度在最坏情况下为 O(n)，但在实践中，如果我们选择好的索引和枢轴（并且如果数据集足够多样化）并找到一个相当平衡的树。
space 的复杂度在最坏的情况下可能真的很糟糕 (O(2^n))，但它更接近于平衡树的 O(n)。
我正在处理整数数组，它们的大小都相同 l。
我有一组静态的它们，我需要构建一个函数来有效地查找它们。
棘手的部分是我需要搜索的数组中的元素可能会偏移 1.
给定数组 {A_1, A_2, ..., A_n} 和一个数组 S，我需要一个函数 search这样：
search(S)=x iff ∀i: A_x[i] ∈ {S[i]-1, S[i], S[i]+1}.
一个可能的解决方案是将每个向量视为 l 维 space 中的一个点并寻找最近的点，但它的成本约为 O(l*n) space 和 O(l*log(n)) 及时。
是否有更复杂 space 的解决方案（当然 and/or 时间）？
我的阵列各不相同，良好的启发式方法可能就足够了。
如果维数不是很小，那么最好的解决方案可能是构建一个决策树，沿着不同的维数递归地划分集合。
每个节点，包括根节点，都是一个散列table，从某个维度的可能值到：
- 在公差范围内匹配该值的点列表，如果它足够小；或
- 相似树中的相同点在剩余维度上进行分区。
由于每一层完全消去一维，树的深度最多为L，查找时间为O(L)。
沿着每条路径选择维度的顺序当然很重要——错误的选择可能会导致数据结构的大小爆炸，每个点都会出现多次。
虽然你的分数是 "pretty different"，但应该可以构建一个重复最少的树。我会尝试使用 ID3 算法来选择维度：https://en.wikipedia.org/wiki/ID3_algorithm。这基本上意味着你贪婪地选择了使用熵度量最大化集合大小整体减少的维度。
考虑具有以下值的搜索数组 S：
S = [s1, s2, s3, ... , sl]
和平均值：
s̅ = (s1 + s2 + s3 + ... + sl) / l
和两个匹配数组，一个是每个值都比 S 中的相应值大一，另一个是每个值都小一：
A1 = [s1+1, s2+1, s3+1, ... , sl+1]
A2 = [s1−1, s2−1, s3−1, ... , sl−1]
这两个数组的平均值为：
a̅1 = (s1 + 1 + s2 + 1 + s3 + 1 + ... + sl + 1) / l = s̅ + 1
a̅2 = (s1 − 1 + s2 − 1 + s3 − 1 + ... + sl − 1) / l = s̅ − 1
所以每个匹配数组，其值与搜索数组中的对应值最多相差 1，其平均值与搜索数组的平均值最多相差 1。
如果你计算并存储每个数组的平均值，然后根据它们的平均值对数组进行排序（或者使用额外的数据结构，使你能够找到具有某个平均值的所有数组），你可以快速识别哪些数组的平均值在搜索数组平均值的 1 以内。根据数据，这可能会大大减少您必须检查相似性的数组数量。
在对数组进行预处理并存储它们的平均值之后，执行搜索将意味着遍历搜索数组以计算平均值，查找哪些数组具有相似的平均值，然后遍历这些数组检查每个值。
如果您希望许多数组具有相似的平均值，则可以使用多个平均值来检测局部差异很大但平均相似的数组。你可以例如计算这四个平均值：
- the first half of the array
- the second half of the array
- the odd-numbered elements
- the even-numbered elements
实际数据的分析应该会给你更多关于如何划分数组和组合不同的平均数才能最有效的信息。
如果一个数组的总和不能超过整数大小，可以存储每个数组的总和，并检查它是否在搜索数组总和的l以内，而不是使用平均值。这将避免必须使用浮点数和除法。
（您可以通过存储其他易于计算且不会占用太多 space 存储的属性来扩展这个想法，例如最高值和最低值，最大jump, ...他们可以帮助创建每个阵列的指纹，这取决于数据。)
我会亲自为查找创建类似 Trie 的内容。我说 "something like" 是因为每个索引最多有 3 个可能匹配的值。所以我们不是在创建决策树，而是在创建 DAG。有时我们有选择。
这很简单，将 运行（带回溯）在最长时间内 O(k*l)。
但这就是诀窍。每当我们看到可以进入下一个匹配状态的选择时，我们就可以创建一个合并状态来尝试所有这些状态。我们可以创建一些或很多这样的合并状态。每个人都会将选择推迟 1 步。如果我们仔细跟踪我们创建的合并状态，我们可以一遍又一遍地重复使用相同的状态。
理论上，我们可以为数组的任意子集生成部分匹配。这可以在阵列数量上呈指数增长。在实践中，很可能只会结束其中的几个合并状态。但我们仍然可以保证权衡——更多的状态在前面 运行s 之后更快。所以我们优化直到我们完成或达到我们想要的数据量的限制。
这是 Python 中的一些概念验证代码。它可能会及时构建匹配器 O(n*l) 并及时匹配 O(l)。但是只能保证及时构建匹配器 O(n^2 * l^2) 并及时匹配 O(n * l).
import pprint
class Matcher:
def __init__ (self, arrays, optimize_limit=None):
# These are the partial states we could be in during a match.
self.states = [{}]
# By state, this is what we would be trying to match.
self.state_for = ['start']
# By combination we could try to match for, which state it is.
self.comb_state = {'start': 0}
for i in range(len(arrays)):
arr = arrays[i]
# Set up "matched the end".
state_index = len(self.states)
this_state = {'matched': [i]}
self.comb_state[(i, len(arr))] = state_index
self.states.append(this_state)
self.state_for.append((i, len(arr)))
for j in reversed(range(len(arr))):
this_for = (i, j)
prev_state = {}
if 0 == j:
prev_state = self.states[0]
matching_values = set((arr[k] for k in range(max(j-1, 0), min(j+2, len(arr)))))
for v in matching_values:
if v in prev_state:
prev_state[v].append(state_index)
else:
prev_state[v] = [state_index]
if 0 < j:
state_index = len(self.states)
self.states.append(prev_state)
self.state_for.append(this_for)
self.comb_state[this_for] = state_index
# Theoretically optimization can take space
# O(2**len(arrays) * len(arrays[0]))
# We will optimize until we are done or hit a more reasonable limit.
if optimize_limit is None:
# Normally
optimize_limit = len(self.states)**2
# First we find all of the choices at the root.
# This will be an array of arrays with format:
# [state, key, values]
todo = []
for k, v in self.states[0].iteritems():
if 1 < len(v):
todo.append([self.states[0], k, tuple(v)])
while len(todo) and len(self.states) < optimize_limit:
this_state, this_key, this_match = todo.pop(0)
if this_key == 'matched':
pass # We do not need to optimize this!
elif this_match in self.comb_state:
this_state[this_key] = self.comb_state[this_match]
else:
# Construct a new state that is all of these.
new_state = {}
for state_ind in this_match:
for k, v in self.states[state_ind].iteritems():
if k in new_state:
new_state[k] = new_state[k] + v
else:
new_state[k] = v
i = len(self.states)
self.states.append(new_state)
self.comb_state[this_match] = i
self.state_for.append(this_match)
this_state[this_key] = [i]
for k, v in new_state.iteritems():
if 1 < len(v):
todo.append([new_state, k, tuple(v)])
#pp = pprint.PrettyPrinter()
#pp.pprint(self.states)
#pp.pprint(self.comb_state)
#pp.pprint(self.state_for)
def match (self, list1, ind=0, state=0):
this_state = self.states[state]
if 'matched' in this_state:
return this_state['matched']
elif list1[ind] in this_state:
answer = []
for next_state in this_state[list1[ind]]:
answer = answer + self.match(list1, ind+1, next_state)
return answer;
else:
return []
foo = Matcher([[1, 2, 3], [2, 3, 4]])
print(foo.match([2, 2, 3]))
请注意，我故意设置了一个有 2 个匹配项的情况。它报告了他们两个。 :-)
我想出了一个从
思路如下：给定数组集As...
选择一个
index和一个pivot。
我将枢轴固定为一个常量值，该值适用于我的数据，并尝试了所有索引以找到最佳索引。尝试多个支点可能会更好，但我不需要。将
As划分为两个可能相交的子集，一个用于数组（其第index个元素）小于主元，一个用于较大的数组。非常接近枢轴的数组被添加到两个集合中：function partition( As, pivot, index ): return { As.filter( A => A[index] <= pivot + 1 ), As.filter( A => A[index] >= pivot - 1 ), }递归地将前面的两个步骤应用于每个子集，当子集只包含一个元素时停止。
这里是一个用这个算法生成的可能树的例子（注意A2同时出现在根节点的左右子节点上）：
{A1, A2, A3, A4}
pivot:15
index:73
/ \
/ \
{A1, A2} {A2, A3, A4}
pivot:7 pivot:33
index:54 index:0
/ \ / \
/ \ / \
A1 A2 {A2, A3} A4
pivot:5
index:48
/ \
/ \
A2 A3
然后搜索函数将其用作普通决策树：它从根节点开始，递归到左子节点或右子节点，具体取决于其在索引 currentNode.index 处的值是大于还是小于currentNode.pivot。它递归地进行，直到到达叶子。
一旦构建了决策树，时间复杂度在最坏情况下为 O(n)，但在实践中，如果我们选择好的索引和枢轴（并且如果数据集足够多样化）并找到一个相当平衡的树。
space 的复杂度在最坏的情况下可能真的很糟糕 (O(2^n))，但它更接近于平衡树的 O(n)。