algorithm - 匹配二进制模式包括 "don' t cares"

Question

我有一组位模式，想在该组中找到与给定输入匹配的元素的索引。位模式包含“无关”位，即匹配 0 和 1 的 x-es。

例子 位模式集是

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 支配，而其他位将主要是零/一。

Answer 1

我认为你可以为位模式构建一棵特里树，节点包含模式的原始索引。

完成匹配只是在一个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]
    }
}