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

Question

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

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

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

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

有什么建议么？我错过了一些明显的东西吗？

提前致谢！

标签： javascriptfileapiarraybuffertyped-arrays

Answer 1

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

因此，在您拥有 ArrayBuffers 的情况下，您可以使用该方法的stream选项TextDecoder.decode()并按小块读取 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同时使用 line-start 和 line-end，则块可以拆分通常匹配的值。