OCRed 文档中的文本搜索，包含单词/行/字符的边界框信息

Question

我们有一个包含数百张扫描图像的集合形式的文档。完成 OCR 后，我们保存了字符级、单词级和行级的边界框以及坐标（本质上我们得到了字符边界框，我们将它们组合起来形成单词边界框，然后形成行边界框）。

我们的问题 - 用户可能会搜索跨越字符、单词、行的文本。我们需要显示搜索结果，其中查询短语（如果存在）应在右侧页面中突出显示。

在这张图中，我们有所有的字符/单词，所有单词、字符和线条的边界框。现在用户正在搜索“was a real”。问题是 - 我们可以在运行时使用什么样的数据结构和算法来快速显示搜索结果，并突出显示整个搜索文本？

注意：短语也跨越多个字符，例如 “his was a rea”，或行，例如 “deal.How abou”（假设下一行以 “How about a new one”开头） ）。

我们是否应该只存储字符级边界框，并且所有三个边界框都可以由此构建？或者，存储所有三个级别是否会帮助我们提高整体性能，即使这意味着在运行时使用更多内存将所有三个级别中保存的数据加载到内存中以进行搜索？

Answer 1

你说你必须“突出显示搜索”。考虑到要求，您必须存储字符边界框，因为您需要这些边界框才能在字符级别正确突出显示。

您描述的搜索是简单的线性文本搜索，其中搜索的文本本质上是一个长字符串。您可以使用 Boyer-Moore 或 Knuth-Morris-Pratt 算法来快速获取搜索文本所在的位置（如果有）。如果空间不是太大的问题，您还可以考虑 N-gram 索引。

如果我误解了，而你没有有线性文本——第一次构建它。在一堆单个字母中进行搜索是完全不值得的。这意味着您必须管理小的错位并根据需要添加空格；我在处理 PDF 时经常这样做，您可以在此处找到一些“算法”片段和见解，或者随时提出更多问题。

假设您已经进行了搜索，现在需要快速检索边界框以执行突出显示。

您可以例如将边界框存储为坐标的四元组；也许您可以调整数据大小以节省空间（例如，对于 x 和 y 坐标，16 位几乎肯定足够，对于 w 和 h 大小，8 位就足够了；因此 3 个 16 位字（48 位）可以轻松地包含您的边界框。

此设置的简单性意味着，一旦您在文件中的位置 13,984,283 处找到了 22 个字符的字符串的匹配项，您只需将该偏移量乘以 6，即可获得边界框数据库中的偏移量。从那里读取 22*6 字节，您很快就可以准备好所有字符。

如果您需要性能，请不要继续阅读。通过存储已知单词的索引，有可能的增强功能，但如果您希望能够查找部分字符，那么平均情况可能不值得。优化 Boyer-Moore 算法 以加快搜索速度也是一种可能性。 为了节省空间，您可以减少存储要求和/或使用压缩。

通过接受轻微的错误，您可以为 y 和 x 提供 11 位，为 h 和 w 提供 5 位，并以 32 位存储完整的边界框。

您还可以使用增量算法压缩边界框的“页面”，以便在

大多数

情况下您可以存储较小的值，可以容纳更少的字节。 简单压缩

为了节省空间，您可以对边界框数据库进行划分、索引和压缩。很可能只需简单的 gzip 压缩就能使大小平均减少 8 倍。因此，如果您有 1 GB 的 TXT 文件，那么您就有一个带有边界框的 6 Gb 二进制文件。将其分为 16 Kb 块，每个块将压缩为 2-3 Kb 块。将其写入压缩文件，并将其 64 位偏移量保存到索引文件中。您最终将得到大约 40 万个块、大约 800 Mb 的空间和 3 Mb 的索引。

假设您需要偏移量 3,373,256,576 处的字节：将其除以 16Kb 块大小，您会得到它们位于偏移量 3968 处的压缩块 205887 中（有时您需要两个相邻块）。读取索引文件中偏移205887*8处的8个字节，得到压缩块在大二进制文件中的地址。在那里开始解压缩，直到获得 16K 的数据，寻求偏移 3968 就可以了。现在，您需要从索引文件中读取一次，并从二进制文件中读取一次 2-3 Kb 的大数据，但整个文件占用的空间不到 2 GB，而不是 7 GB。