PERL: 跳转到大型文本文件中的行

Question

我有一个非常大的文本文件（约4GB）。 它的结构如下：

S=1
3 lines of metadata of block where S=1
a number of lines of data of this block
S=2
3 lines of metadata of block where S=2
a number of lines of data of this block
S=4
3 lines of metadata of block where S=4
a number of lines of data of this block
etc.

我正在编写一份PERL程序，用于读取另一个文件。对于那个文件中的每一行（必须包含数字），我将搜索巨大的文件以查找数字减1的S值，并分析属于该S值的块的数据行。

问题在于，文本文件非常庞大，因此无法有效地处理每一行。

foreach $line {...} loop

非常缓慢。由于S=值严格递增，是否有任何方法跳转到所需S值的特定行？

- Nissa

---

尝试使用 while。如果不行，读取特定大小的MB到缓冲区中，并计算换行符数量以定位所需行。 - mpapec

每个记录中的字节数是否相同？ - AnFi

你需要在文件中找到很多个S值（以分析它们的文本），还是不需要那么多？ - zdim

你可以使用S-value/filepos在该文件上创建索引，通过二分查找在索引中查找该值，然后seek()到该文件位置。如果没有索引，你可以直接在文件中进行某种形式的二分查找 - 即seek()到文件的一半位置，从该位置开始扫描第一个S，并不断重复，直到找到S。这将需要多次文件读取(log n)，而使用索引只需要一次读取大文件。两种解决方案都几乎不会使用大文件的内存（第一种解决方案仅使用索引的大小，第二种解决方案则完全不使用）。 - Danny_ds

文件有改动吗？如果没有，将其转换为更好的格式。 - Schwern

S值已排序吗？如果是，您可以使用二分查找。 - ikegami

Answer 1

有没有办法跳转到所需S值的特定行？

是的，如果文件不改变，则可以创建索引。这需要读取整个文件并使用 tell 记录所有 S=# 行的位置。将其 存储在DBM文件 中，键为数字，值为文件中的字节位置。然后，您可以使用 seek 跳转到文件中的那个位置并从那里读取。

但是如果你要这样做，最好将数据导出到一个适当的数据库中，例如SQLite。编写一个程序将数据插入到数据库中并添加普通SQL索引。这可能比编写索引更简单。然后，您可以使用普通SQL高效地查询数据，并进行复杂的查询。如果文件更改，您可以重新执行导出操作，或使用常规的insert和update SQL更新数据库。对于任何熟悉SQL的人来说，这都很容易处理，而不是一堆自定义索引和搜索代码。

- Schwern

Answer 2

如果文本块的长度相同（以字节或字符计），则可以计算所需S值在文件中的位置，然后进行seek操作，接着读取。否则，原则上需要逐行阅读以找到S值。

但是，如果只需要找到几个S值，可以估计所需位置并进行seek操作，然后read足够多的内容来捕获一个S值。然后分析所读内容以查看偏差有多大，然后再次进行seek操作或使用<>逐行读取以获取S值。

use warnings;
use strict;
use feature 'say';

use Fcntl qw(:seek);

my ($file, $s_target) = @ARGV;
die "Usage: $0 filename\n" if not $file or not -f $file;
$s_target //= 5;  #/ default, S=5

open my $fh, '<', $file or die $!; 

my $est_text_len = 1024;
my $jump_by      = $est_text_len * $s_target;  # to seek forward in file

my ($buff, $found);

seek $fh, $jump_by, SEEK_CUR;  # get in the vicinity

while (1) {

    my $rd = read $fh, $buff, $est_text_len;
    warn "error reading: $!" if not defined $rd;
    last if $rd == 0;

    while ($buff =~ /S=([0-9]+)/g) {
        my $s_val = $1;

        # Analyze $s_val and $buff:
        # (1) if overshot $s_target adjust $jump_by and seek back
        # (2) if in front of $s_target read with <> to get to it
        # (3) if $s_target is in $buff extract needed text

        if ($s_val == $s_target) {
            say "--> Found S=$s_val at pos ", pos $buff, " in buffer";
            seek $fh, - $est_text_len + pos($buff) + 1, SEEK_CUR;
            while (<$fh>) {
                last if /S=[0-9]+/;  # next block
                print $_;
            }
            $found = 1;
            last;
        }
    }   
    last if $found;
}

通过使用您的示例进行测试，进行了扩展和清理（将文本中的S = n更改为与条件相同！），并将$est_text_len和$jump_by设置为100和20。

这是一个草图。完整的实现需要就代码中概述的过度和不足寻求进行协商。如果文本块大小变化不大，它可以在两次寻找和读取之前获得所需的S值，然后使用<>进行读取或使用正则表达式，如示例中所示。

一些评论

上述的“分析”需要仔细进行。首先，一个缓冲区可能包含多个S值行。此外，注意如果缓冲区中没有S值，代码将继续读取。

一旦您靠近并位于$s_target前面，请通过<>>读取行以到达它。

读取可能不会得到所请求的那么多，因此您应该真正将其放在循环中。最近有相关的帖子。

为了提高效率，请从read更改为sysread。在这种情况下，请使用sysseek，并且不要与<>>混合使用（这是缓冲的）。

上面的代码假定要查找一个S值；请根据需要进行调整。它绝对假定S值已排序。

这显然比阅读行复杂得多，但如果有一个非常大的文件和只需要找到几个S值，它会运行得更快。如果有许多值，则可能不会有所帮助。

---

在问题中指出的 foreach (<$fh>) 会导致整个文件先被读取（以建立列表供 foreach 遍历），应改用 while (<$fh>)。

---

如果文件没有改变（或者同一个文件需要被多次搜索），你可以先处理一次，建立S值精确位置的索引。感谢Danny_ds的评论。

- zdim

---

+1 - 另一个创建并使用索引（S-value/filepos）的示例/答案也会很棒。 （我不懂Perl，所以无法提供代码）。 索引可以创建一次并存储在磁盘上，只要文件不改变就可以一直使用。 而且由于S已经按顺序排列，创建该索引将非常容易（只需继续添加S-value/filepos即可）。 然后只需在内存中进行二进制搜索即可。 - Danny_ds

@Danny_ds 确实。我假设每次都是（少量查询）一个新文件。添加了一条注释。 - zdim

Answer 3

我知道楼主已经接受了一个答案，但是有一个方法对我很有用，就是根据改变的“记录分隔符”($/)将文件读入数组中。

如果你像这样做（没有测试过，但这应该很接近）：

$/ = "S=";
my @records=<fh>;
print $records[4];

输出应该是第五条完整记录（数组从0开始，但您的数据从1开始），从一个单独的行（您可能需要稍后剥离它）开始，记录编号为5，接下来是该记录中的所有剩余行。这非常简单快速，虽然它会占用大量内存...

- jimtut

Answer 4

有序列表的二分查找是一项O(log N)操作。使用seek可以实现类似以下代码：

open my $fh, '>>+', $big_file;
$target = 123_456_789;

$low = 0;
$high = -s $big_file;

while ($high - $low > 0.01 * -s $big_file) {
    $mid = ($low + $high) / 2;
    seek $fh, $mid, 0;
    while (<$fh>) {
        if (/^S=(\d+)/) {
            if ($1 < $target) { $low = $mid; }
            else              { $high = $mid }
            last;
        }
    }
}

seek $fh, $low, 0;
while (<$fh>) {
    # now you are searching through the 1% of the file that contains
    # your target S
}

- mob

Answer 5

将第二个文件中的数字进行排序。现在您可以按顺序处理巨大的文件，根据需要处理每个S值。

- shawnhcorey