匹配二进制模式，包括“不关心”
我有一组位模式，并希望在集合中找到与给定输入匹配的元素的索引。位模式包含“不关心”位，即与0和1匹配的x。
示例位模式集为
index abcd
0 00x1
1 01xx
2 100x
3 1010
4 1x11然后，试图匹配0110应该返回索引1，而1011应该返回索引4。
如何才能比通过元素进行线性搜索更快地解决这个问题呢？我想可以做一种二叉树，但是怎样才能创造出这样一棵树呢？对于这样的问题，是否有其他有效的数据结构/算法，主要是在查询效率和存储需求方面。
- 比特模式将是64位(或更多)
- 集合中的元素数将按10^5 - 10^7的顺序排列。
- 并不是所有的位组合都表示在集合中，例如在示例0000中没有表示。
- 数据集中将有大量的x-es。
- 位字符串将只匹配集合中的一个元素。
我有两个不同的例子需要解决这个问题
- 案例1:我有可能做大量的预计算
- 案例2:新元素将动态添加到集合中。
x-es比其他位位置更有可能出现在某些位置，即有些位置将被x-es所支配，而其他位置则主要是0/1。
回答 5
Stack Overflow用户
发布于 2014-02-10 12:03:00
我认为您可以为位模式构建一个trie树，节点包含模式的原始索引。
要完成匹配，只需在trie树中搜索，当trie节点包含相同的“x”位时，转到下一个节点。结果可能包含特定输入的多个索引。
这是我的解决办法
public class Solution {
public static class Trie<T> {
private final Character WILD = 'x';
private Map<Character, Trie> children;
private boolean isNode;
private T value;
public Trie() {
children = new HashMap<Character, Trie>();
isNode = false;
value = null;
}
public void insert(String key, T value) {
Trie<T> current = this;
for (int i = 0; i < key.length(); i++) {
char c = key.charAt(i);
if (current.children.containsKey(c)) {
current = current.children.get(c);
} else {
Trie<T> next = new Trie();
current.children.put(c, next);
current = next;
}
}
current.isNode = true;
current.value = value;
}
public List<T> get(String key) {
List<T> result = new ArrayList<T>();
get(this, key.toCharArray(), 0, result);
return result;
}
private void get(Trie<T> trie, char[] chars, int index, List<T> result) {
if (index == chars.length) {
if (trie != null && trie.isNode) {
result.add(trie.value);
}
return;
}
char c = chars[index];
if (trie.children.containsKey(c)) {
get(trie.children.get(c), chars, index + 1, result);
}
if (trie.children.containsKey(WILD)) {
get(trie.children.get(WILD), chars, index + 1, result);
}
}
}
public static void main(String[] args) {
Trie<Integer> trie = new Trie<Integer>();
trie.insert("00x1", 0);
trie.insert("01xx", 1);
trie.insert("100x", 2);
trie.insert("1010", 3);
trie.insert("1x11", 4);
System.out.println(trie.get("0110")); // [1]
System.out.println(trie.get("1011")); // [4]
}
}Stack Overflow用户
发布于 2014-02-10 18:30:03
您可以在这里构建一个与字符串长度成线性的字符串匹配的自动机。例如，您可以将一组字符串--或者，实际上是字符串上的一个函数--存储在一个(精简、有序的) 二元决策图中。我怀疑任意一组字符串的BDD --有--不关心--在符号总数中的大小是线性的，但是我没有证据。
BDD解决方案将类似于强进的优秀解决方案，但略有不同，在这种解决方案中，构造肯定需要线性空间，但在最坏的情况下查询速度并不明显(对我来说)。
Stack Overflow用户
发布于 2014-02-10 10:38:41
我认为，模式容器的解决方案将是一个特定的有序树。
- 树的节点会说：
- 它是关于什么位置(node.position)
- 这个位置的位是什么(0,1，x) (node.value)
- 只有叶节点才能有x作为值。
- 子级的位置应该总是大于父级的位置--以排除重复分支。
- 如果一个节点有多个子节点，则排序如下：
- 先按位置
- 在两个位置相同的子项目中，第一个是值为0的。
- 这样的树的根节点是空的。
- 树是这样读的：
- 从根开始，得到一条通往叶子的路径，取1和0，并将它们放在适当的位置。
- 当我们到达x时，用x-es填充所有的自由位置。
- 如果我们不到达x，叶子有1/0的值，并且模式被填充。如果未填充，则会发生错误。
该节点中的匹配不应由叶子来完成，而应通过级别来完成。一个级别将是一组父级的子级。
Take first level of the children as current level
Take the first child on the level for current
read currentnode.position
check the appropriate position in the matched string against child value.
If it fits, go higher up the tree.
If it doesn't fit, go to next child.
If we are out of children on the level, go down the tree.模式添加和二进制字符串匹配的复杂性在这里是log(n)，如果存在x‘as的%，则时间大约会缩短1%，而不是@Qiang的解决方案。多分枝树的搜索速度比仅三分枝树快。
我会将该树实现为列表的层次结构。
https://stackoverflow.com/questions/21673723
复制相似问题
腾讯云开发者
