高效的数据存储/算法来模式匹配 0 和 1 的二进制字符串

Question

我生成了一个包含数百行的 .txt 文件。每行如下所示：

0000000000000000000000000000000000000000100000000010000000001000000000100000000010000000000000000000

现在我有一个输入函数，可以提交这样的字符串：

0000000000000000000000000000000000000000000011000010000000001000000000100000000010000000000000000000

如果输入字符串为 1 而 .txt 中的字符串为 0 则无关紧要。该算法应解决的问题如下：

在 .txt 中找到“最佳匹配”行，其中输入字符串在行具有的相同索引处具有尽可能多的 1
索引论文“最佳匹配行”有 1 而输入没有的输出

情况：

.txt每行最多5个1
输入字符串中最多可以有一百个1。
每一行和输入的长度正好是 100 个字符。
每一行和输入总是只包含 0 或 1；没有其他字符。

这是一个比实际问题更小的例子，假设长度为 6，最多 3 个（对于这个例子，我将从 1 开始计算索引，而不是 0）：

rows.txt

输入字符串：

算法的预期输出

Closest matching rows are:

Row 1: two matching 1s; your input misses a 1 on index 6
Row 4: two matching 1s; your input misses a 1 on index 4

问题/可能的解决方案：

我选择 0 和 1 来表示我计划将它们放入二进制文件中所需的信息。在代码中使用二进制表示和无符号整数 (Java/Kotlin) 时，我期待更好的性能和更小的文件大小。但是继续 uInt8;我需要在每一行上添加“0000”以使每一行长 104 个字符，可以被 8 整除。这当然是可能的，但比起我将所有内容都保存为整数，我只是无法理解如何在字节表示级别上比较它们以基本上进行我在代码中需要的模式匹配。

正在为给定问题寻找性能最佳的 storage/pattern 匹配解决方案。

这就是我这样做的原因：我有一个带有可点击网格的前端。未选中的项目用 0 表示。单击一个项目并因此 selecting 它由 1 表示。用户最多可以 select 100 个可用项目中的 50 个。但是，有些项目依赖于其他项目。每个项目总是依赖于其他 4 个项目。这些是（当前）.txt 文件的行。这就是为什么我需要弄清楚缺少哪些来推荐完全依赖五个 1 工作的配置，而我不需要关心是否有额外的 selections (1s)。也许这个用例阐明了像这样的抽象问题是一个现实世界的问题而不是学校作业。先前的解决方案涉及用矩阵表示网格，但使用二进制字符串似乎更有效。

澄清问题：二进制三：

00000011

二进制十三：

00001101

如果有一行表示二进制3，输入为二进制13，我怎么比较

val row: uint8 = 3u
val input: uint8 = 13u

得到结果

missing value 2 (-> a one on index 7

Answer 1

不要使用“0”、“1”文本，使用二进制表示。

使用按位 & 将 'input' 与每个 'row' 进行比较，然后通过从此处的一个答案中得出可接受的解决方案来计算结果中的个数：Count number of 1's in binary representation.

编辑：

为了回应@gidds 的评论，稍微扩展一下这个想法：

您已表示愿意用零填充 ('to go on uInt8; I would need to add "0000"')，因此可以使用 int（太糟糕了，每行的长度不是 96！），这会带来一些 space 为了方便在一个原始操作中比较 32 列。实际上，它不会浪费太多 space，因为您可以在一个循环中将文件的每一行读取到一个可重复使用的 ByteBuffer 中。 ByteBuffer#allocate 已经初始化为零，因此会处理填充。没有理由不能使用 long、int 和 byte 总共 104 位，但这可能不值得麻烦 - [= 中没有半字节35=] 所以没办法准确地得到 100。我选择了 4 int 而不是 2 long 只是为了能够利用上面的 bitCount 算法 link.

这是一个相当全面的纯素描 Java:

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.nio.ByteBuffer;
import java.nio.channels.Channels;
import java.nio.channels.ReadableByteChannel;

public class BitSimilarityChecker {
    
    public void main(String[] args) throws Exception {
        
        // int[] input = ... 
        assert input.length == 4;
        
        try (ByteFileReader reader = new ByteFileReader(args[0])) {
            while (/* TODO: When has file been fully read? */) {
                int[] row = reader.read(); 
                assert row.length == 4;
                int sum = 0;
                for (int i = 0; i < 4; ++i) {
                    sum += bitCount(and(input[i], row[i]));
                }
                // TODO: Keep track of the max sum, row pair...
            }
        }
    }
    
    private static int and(int left, int right) {
        return left & right;
    }
    
    // Taken from  - unverified.
    private static int bitCount(int u) {
         int uCount = u - ((u >> 1) & 033333333333) - ((u >> 2) & 011111111111);
         return ((uCount + (uCount >> 3)) & 030707070707) % 63;
    }
    
    private static class ByteFileReader implements AutoCloseable {

        private static final int CAPACITY = 4 * 8 * Integer.BYTES;
        private static final int LIMIT = 100;
        
        private final ReadableByteChannel channel;
        private final ByteBuffer buffer;
        
        @SuppressWarnings("resource")
        public ByteFileReader(String file) throws FileNotFoundException {
            channel = Channels.newChannel(new FileInputStream(file));
            buffer = ByteBuffer.allocate(CAPACITY);
        }
        
        public int[] read() throws IOException {
            buffer.position(0);
            buffer.limit(LIMIT);
            int bytesRead = channel.read(buffer);
            buffer.limit(CAPACITY);
            // TODO: Check bytesRead to see the status of the read.
            // Pass this information on to the caller somehow. 
            return new int[] {
                    buffer.getInt(),
                    buffer.getInt(),
                    buffer.getInt(),
                    buffer.getInt()
            };
        }

        @Override
        public void close() throws Exception {
            channel.close();
        }
    }
}

高效的数据存储/算法来模式匹配 0 和 1 的二进制字符串

Efficient data store / algorithm to pattern match binary strings of 0s and 1s

java

kotlin

binary