无需编写 Boyer-Moore 实现即可在类型化数组中查找字节序列

Question

我必须在用户加载的文件中找到一些标记（文本序列）。这些文件中有 85% 是 UTF-8 编码文本，但也会有二进制文件。这些标记现在是文本序列，但将来可能会使用正则表达式（可能不适用于二进制文件，但我还不知道）。

我将文件内容作为 ArrayBuffer 数组，我必须在该数据中找到标记。我有以下选择：

使用类型化数组 (UInt8Array) 和 TextDecoder('ascii')，并对解码数据使用 String.indexOf()。我不喜欢这样，因为至少在原则上这可以复制 TextDecoder.decode() 之后文件内容使用的内存。但这很简单也很直接。也适用于二进制文件，因为标记将是二进制数据中的 ASCII 字节。
再次使用类型化数组（UInt8Array）并编写我自己的 Boyer-Moore 版本或其他快速字符串搜索函数，以找到我需要的字节序列。快速，内存最佳...但我宁愿不编写另一个 Boyer-Moore 实现或复制一个。请记住，将来我可能想使用正则表达式，所以...
将文件作为文本而不是 ArrayBuffer 读取，因为大约 85% 的文件将是 UTF-8 编码的文本，并尝试对少数真正的二进制文件进行临时处理遇到。这意味着我可以从一开始就使用正则表达式或 String.indexOf()，没什么大不了的，但另一方面，在找到标记后处理二进制文件可能是个问题，因为原始数据将被转换为文本。

由于以后几乎可以保证使用正则表达式，所以我唯一明确的路径是第一个，但我很担心内存占用，因为有些文件可能很大（大约 100 MB 或所以)，或者使用第三个选项，看看如何在将原始字节转换为文本后获取原始字节...

有什么建议吗？我是否漏掉了一些明显的东西？

提前致谢！

Answer 1

您可以将 ArrayBuffer 解码为文本流。
有一个 TextDecoderStream,，但它在 FF 中仍然不受支持，它需要将您的 ArrayBuffers 复制到 Blob 中以便它们可以被流式传输。

因此，在您拥有 ArrayBuffer 的情况下，您可以使用 TextDecoder.decode() 方法的 stream 选项并按小块读取 ArrayBuffer：

const buffer_1 = new TextEncoder().encode( "AAABCBAB" ).buffer;
// expected indices: [2,6]                    ^   ^
const indices_1 = getAllIndices( buffer_1, "AB", 3 /* 3 bytes at a time */ );
console.log( "buffer 1",
  JSON.stringify( indices_1 ),
  // check they're all "AB"
  JSON.stringify( extractContent( buffer_1, indices_1, 2 ) )
);

// A more complex test, with random binary data (read as UTF-8)
const buffer_2 = Uint32Array.from(
  { length: 1024 * 1024 },
  () => Math.random() * 0xFFFFFFFF
).buffer;
const indices_2 = getAllIndices( buffer_2, "AB" );
console.log( "buffer 2",
  JSON.stringify( indices_2 ),
  // check they're all "AB"
  JSON.stringify( extractContent( buffer_2, indices_2, 2 ) )
);

function getAllIndices( buffer, marker, chunksize = 1024 /* Bytes */ ) {

  if( !marker ) { return null; }
  if( !(marker instanceof RegExp) ) {
    marker = new RegExp( marker, "g" );
  }
  marker.global = true;
  
  // The marker could get split over two chunks.
  // So, at every chunk we prepend the last few characters
  // of the last chunk.
  const marker_length = marker.source.length;
  const positions = [];
  const arr = new Uint8Array( buffer );
  const decoder = new TextDecoder();

  let current_index = 0;
  let full_length = 0;
  let marker_buffer = "";

  while( current_index < arr.length ) {
    const next_index = current_index + chunksize;
    // subarray doesn't copy
    const chunk = arr.subarray( current_index, next_index );
    const decoded = decoder.decode( chunk, { stream: true } );

    const text = marker_buffer + decoded;

    let match;
    let last_index = -1;
    while ((match = marker.exec( text )) !== null) {
      last_index = match.index - marker_buffer.length;
      positions.push( full_length + last_index );
    }

    current_index = next_index;
    full_length += decoded.length;

    // Check that the buffer doesn't itself include the marker
    // this would cause duplicate finds (we could also use a Set to avoid that)
    const marker_index = last_index > -1 ?
      (last_index + marker_length) :
      (decoded.length - marker_length);
    marker_buffer = decoded.slice( marker_index );
  }
  return positions;

}
// for demo only
function extractContent( buffer, indexes, length ) {
  const full_str = new TextDecoder().decode( buffer );
  return indexes.map( (index) => full_str.slice( index, index + length ) );
}

然而，虽然此方法适用于简单的标记，但复杂的 RegExp 可能会导致一些问题。例如，如果您的 RegExp 同时使用行首和行尾，则块可以拆分通常匹配的值。

无需编写 Boyer-Moore 实现即可在类型化数组中查找字节序列

Find byte sequence in typed array without writing a Boyer-Moore implementation

javascript

fileapi

typed-arrays

arraybuffer