如何在JavaScript中高效搜索大二进制数据中的目标字符串数组？

我从文件加载了混合字符串与二进制数据的二进制内容，创建了对应的DataView。需要实现一个函数，从数据的指定范围内找出目标字符串数组中存在的字符串，将结果存入返回数组。函数框架如下：

function findStrings(data, startIdx, endIdx, matchStrings) {
  let returnStrings = [];

  ...

  return returnStrings;
}

需求说明 #

• 目标字符串可能被任意8位字节包围
• 数据大小可达1Mb，目标字符串数组通常包含10-100个字符串
• 核心要求：时间与内存效率优先，避免不必要的数据副本，仅遍历缓冲区一次，额外内存占用最小，时间复杂度与缓冲区大小呈线性关系，不随目标字符串数量增长

示例输入输出 #

// 目标字符串数组
matchStrings = [
    'String1\x00',
    'String2\x00',
    'String\x00',
]

// 二进制数据（示例）
data = '\x00String\x00\x1b\x0c\x00String\x00String2\x00\x04'

示例输出：[0, 1]（对应matchStrings的索引）或['String', 'String2']（对应匹配的字符串）

现有实现的问题 #

目前有一个基于正则表达式的实现，但该方案效率较低：会产生额外的数据副本（如buffer.slice和TextDecoder.decode），且正则多模式匹配的时间复杂度会随目标字符串数量上升，不符合高效要求：

const matchStrings = [
    'String1\x00',
    'String2\x00',
    'String\x00',
];

function findStrings(buffer, startIdx, endIdx, matchStrings) {
    let returnStrings = [];

    const data = new TextDecoder("latin1").decode(buffer.slice(startIdx, endIdx));
    const re = new RegExp('('+matchStrings.join(')|(?:')+')', 'g');
    const matches = data.match(re);
    if(matches){
        for(let m of matches){
            if(!returnStrings.includes(m)){
                returnStrings.push(m);
            }
        }
    }
  
    return returnStrings;
}

高效实现方案：AC自动机多模式匹配 #

要满足线性时间复杂度、无额外数据副本的要求，可使用**AC自动机（Aho-Corasick）**处理多模式字符串匹配，直接遍历二进制缓冲区的指定范围，无需解码整个数据。

实现逻辑

1. 构建AC自动机状态树：包含所有目标字符串的前缀，同时记录失败指针和匹配标记
2. 遍历指定范围的二进制数据：逐个字节推进AC自动机状态
3. 匹配校验：到达匹配状态时记录结果，通过集合去重

代码实现

function buildACAutomaton(patterns) {
    // 根节点
    const root = { children: {}, fail: null, matches: [] };
    let nodes = [root];

    // 第一步：构建前缀树
    for (let patternIdx = 0; patternIdx < patterns.length; patternIdx++) {
        const pattern = patterns[patternIdx];
        let current = root;
        for (let i = 0; i < pattern.length; i++) {
            const charCode = pattern.charCodeAt(i);
            if (!current.children[charCode]) {
                const newNode = { children: {}, fail: null, matches: [] };
                current.children[charCode] = newNode;
                nodes.push(newNode);
            }
            current = current.children[charCode];
        }
        // 记录该节点对应的模式索引和字符串
        current.matches.push({ index: patternIdx, string: pattern });
    }

    // 第二步：构建失败指针（BFS）
    const queue = [];
    root.fail = null;
    for (const charCode in root.children) {
        const child = root.children[charCode];
        child.fail = root;
        queue.push(child);
    }

    while (queue.length > 0) {
        const currentNode = queue.shift();
        for (const charCode in currentNode.children) {
            const child = currentNode.children[charCode];
            let failNode = currentNode.fail;
            // 找到合适的失败指针
            while (failNode && !failNode.children[charCode]) {
                failNode = failNode.fail;
            }
            child.fail = failNode ? failNode.children[charCode] : root;
            // 合并匹配结果（失败节点的匹配也属于当前节点的匹配）
            child.matches.push(...child.fail.matches);
            queue.push(child);
        }
    }

    return root;
}

function findStrings(data, startIdx, endIdx, matchStrings) {
    const returnStrings = [];
    const foundSet = new Set(); // 用于去重

    if (matchStrings.length === 0 || startIdx >= endIdx) {
        return returnStrings;
    }

    // 构建AC自动机
    const root = buildACAutomaton(matchStrings);
    let currentNode = root;

    // 遍历指定范围的二进制数据（直接操作DataView）
    for (let i = startIdx; i < endIdx; i++) {
        const charCode = data.getUint8(i);

        // 根据当前字符推进自动机状态
        while (currentNode && !currentNode.children[charCode]) {
            currentNode = currentNode.fail;
        }
        currentNode = currentNode ? currentNode.children[charCode] : root;

        // 检查是否有匹配项
        if (currentNode.matches.length > 0) {
            for (const match of currentNode.matches) {
                if (!foundSet.has(match.index)) {
                    foundSet.add(match.index);
                    // 可选择返回索引或字符串，这里示例返回去掉末尾null的字符串
                    returnStrings.push(match.string.replace(/\x00$/, ''));
                    // 若需返回索引：returnStrings.push(match.index);
                }
            }
        }
    }

    return returnStrings;
}

// 测试示例
const matchStrings = [
    'String1\x00',
    'String2\x00',
    'String\x00',
];
// 模拟二进制数据转为DataView
const dataBuffer = new TextEncoder().encode('\x00String\x00\x1b\x0c\x00String\x00String2\x00\x04');
const dataView = new DataView(dataBuffer.buffer);

console.log(findStrings(dataView, 0, dataBuffer.length, matchStrings));
// 输出：["String", "String2"]

实现优势

• 线性时间复杂度：构建AC自动机的时间为O(M)（M为所有目标字符串总长度），遍历数据时间为O(N)（N为指定范围字节数），整体复杂度O(M+N)，符合线性要求
• 无额外数据副本：直接通过DataView读取指定范围字节，无需解码整个缓冲区或创建切片
• 内存占用低：仅维护AC自动机状态树和去重集合，内存开销可控
• 自动去重：通过Set记录已匹配项，避免重复添加

内容的提问来源于stack exchange，提问作者Jules