Nodejs Buffer 对象有 copy, slice, 但没有 indexOf 方法，如何在 Buffer 中高效搜索另一个Buffer（按字节序列）的位置？

Nodejs Buffer 对象有 copy, slice, 但没有 indexOf 方法，如何在 Buffer 中高效搜索另一个Buffer（按字节序列）的位置？

只能toString()吗 ?

5 回复

如何在 Node.js 的 Buffer 中高效搜索另一个 Buffer 的位置？

Node.js 的 Buffer 对象提供了多种方法来处理二进制数据，例如 copy 和 slice。然而，它并没有提供直接的 indexOf 方法来搜索一个 Buffer 在另一个 Buffer 中的位置。在这种情况下，我们可以自己实现一个高效的搜索方法。

示例代码

function findIndex(buffer, target) {
    const bufferLength = buffer.length;
    const targetLength = target.length;

    if (targetLength === 0 || bufferLength < targetLength) {
        return -1; // 如果目标 Buffer 为空或比源 Buffer 短，则返回 -1
    }

    for (let i = 0; i <= bufferLength - targetLength; i++) {
        let found = true;
        for (let j = 0; j < targetLength; j++) {
            if (buffer[i + j] !== target[j]) {
                found = false;
                break;
            }
        }
        if (found) {
            return i; // 找到目标 Buffer 的起始索引
        }
    }
    return -1; // 没有找到目标 Buffer
}

// 示例用法
const buffer = Buffer.from('Hello, world!');
const target = Buffer.from('world');

const index = findIndex(buffer, target);
console.log(index); // 输出: 7

解释

  1. 函数定义：

    • findIndex(buffer, target) 函数接受两个参数：buffer 是源 Buffer，target 是要在 buffer 中查找的目标 Buffer。

  2. 边界检查：

    • 首先检查 target 是否为空或 buffer 是否比 target 短。如果是这种情况，则返回 -1 表示未找到。

  3. 双层循环：

    • 外层循环遍历 buffer 的每个可能的起始位置。
    • 内层循环比较 buffer 的当前片段与 target，如果所有字节都匹配，则返回当前的起始位置。
    • 如果发现任何不匹配的字节，则跳过该位置并继续下一个位置的检查。

  4. 返回结果：

    • 如果在遍历结束后仍未找到匹配项，则返回 -1。

这种方法虽然简单，但在大多数情况下效率较高，尤其是在目标 Buffer 较短的情况下。对于更复杂的场景，可以考虑使用更高级的算法，如 Boyer-Moore 或 Knuth-Morris-Pratt 算法。


貌似也遇到类似的需求

/* Horspool 算法实现的快速子串匹配，这里用于在大Buffer中查找小Buffer src_buf =大Buffer, sub_buf=要找的小Buffer, start_index=起始位置，默认为0 */

function _BufferIndexOf(src_buf, sub_buf, start_index) { if(!Buffer.isBuffer(src_buf) || !Buffer.isBuffer(sub_buf)) return -1;
var src_len = src_buf.length, sub_len = sub_buf.length, idx = start_index-0;
if(isNaN(idx) || idx < 0) idx = 0; // default
if(src_len==0 || sub_len==0 || idx + sub_len > src_len) return -1;

// 如果只是查找单个字符 if(sub_len == 1) { for(var i = idx, c = sub_buf[0]; i<src_len; i++) if(src_buf[i] == c) return i; return -1; }

// 如果只是比较 src_buf 的尾部是否与 sub_buf 相等 if(idx + sub_len == src_len) { var i = idx + sub_len - 1; var j = sub_len - 1; for(; j>-1 && src_buf[i] == sub_buf[j]; j–, i-- ); return (j==-1) ? idx : -1; }

// Horspool 搜索算法 var skip = new Array(256); // 构造跳转表 for(var i=0; i< 256; i++) skip[i] = sub_len; for(var i=0; i< sub_len-1; i++) skip[ sub_buf[i] ] = sub_len - i - 1;

for(var k = idx + sub_len - 1; k < src_len; k += skip[ src_buf[k] ]) { var i = k; var j = sub_len - 1; for(; j>-1 && src_buf[i] == sub_buf[j]; j–, i–); // 回溯比较 if(j == -1) return i + 1; } return -1; }

您好，DeNA在招聘资深Node.js的职位，您有兴趣了解一下吗？

在 Node.js 的 Buffer 对象中确实没有内置的 indexOf 方法。不过，我们可以通过一些技巧来实现高效的搜索操作。这里介绍一种方法，即使用双指针算法来查找一个 Buffer 在另一个 Buffer 中的位置。

示例代码

function indexOf(buffer, searchBuffer) {
    let bufferIndex = 0;
    let searchIndex = 0;

    while (bufferIndex < buffer.length && searchIndex < searchBuffer.length) {
        if (buffer[bufferIndex] === searchBuffer[searchIndex]) {
            // 如果字符匹配，继续比较下一个字符
            searchIndex++;
        } else {
            // 如果不匹配，重置 searchIndex 并回退 bufferIndex
            searchIndex = 0;
            bufferIndex -= searchIndex - 1;
        }
        bufferIndex++;
    }

    // 检查是否完全匹配
    if (searchIndex === searchBuffer.length) {
        return bufferIndex - searchBuffer.length; // 返回匹配的起始位置
    }
    return -1; // 没有找到
}

// 示例用法
const buffer = Buffer.from('Hello World');
const searchBuffer = Buffer.from('World');

const index = indexOf(buffer, searchBuffer);
console.log(`'${searchBuffer.toString()}' found at index: ${index}`); // 输出 'World' found at index: 6

解释

  1. 双指针算法：我们使用两个指针 bufferIndex 和 searchIndex 来遍历主 Buffer 和搜索 Buffer。

    • 当两个指针指向的字节匹配时，移动 searchIndex。
    • 如果不匹配，则重置 searchIndex 并将 bufferIndex 回退到上一次匹配开始的位置。

  2. 完全匹配检查：如果 searchIndex 达到 searchBuffer.length，则说明搜索 Buffer 完全匹配，返回匹配的起始位置。

  3. 未找到的情况：如果循环结束时 searchIndex 没有达到 searchBuffer.length，则表示未找到匹配，返回 -1。

这种方法的时间复杂度为 O(n * m)，其中 n 是主 Buffer 的长度，m 是搜索 Buffer 的长度。虽然不是最优解，但在大多数情况下是足够高效的。

回到顶部