在流上使用正则表达式而不是字符串？

Question

假设您想在管道上执行正则表达式搜索和提取，但模式可能跨越多行，怎么办？有没有适用于流的正则表达式库？

我希望使用Python库来完成这项工作。但任何解决方案都可以，当然不是命令行工具。

顺便说一下，我知道如何解决我的当前问题，只是寻求一个通用解决方案。

如果不存在这样的库，为什么正则库不能与流一起工作，因为正则匹配算法从不需要向后扫描？

- user1733712

---

你能发布一些样例输入和期望的输出吗？ - pogo

你可以让正则表达式跨越多行匹配，但通常情况下，你需要所有内容都在那里才能进行匹配。 - nhahtdh

Answer 1

如果你需要一个普适的解决方案，你的算法需要如下步骤：

1. 将数据流读取到缓存中
2. 在缓存中查找正则表达式
3. 如果匹配到了，对匹配结果进行处理，丢弃缓存中从匹配结果起点到match.end()的部分，然后回到步骤2。
4. 如果未匹配成功，则从数据流中获取更多数据来扩充缓存。

该算法如果找不到匹配结果，可能会占用大量内存，但是在特定情况下（比如在一个大文件中，只有最后一个字符为x时尝试匹配.*x），很难做到更好。

如果你对正则表达式有更多了解，也许还有其他情况可以丢弃缓存的一部分。

- James Henstridge

---

看了@ITNinja的回答，我给出的算法也不完美。例如，如果您有一个表达式x*并且缓冲区以x结尾，则如果流包含更多的x字符，则该算法可能会给出错误的匹配。但希望这足以让您了解如何使用re库处理这种情况。 - James Henstridge

现在我明白了 @ITNinja 的观点。的确，一旦出现“.*”，所有流很可能都需要缓冲。但是，如果库的设计得当，它们仍然在流上工作具有优势，它们可以将数据生成和匹配进行管道化。但是适当的实现需要在更低层面重写 RE 库，这超出了我的耐心和能力范围。 - user1733712

我刚找到另一个解决方案：pexpect http://pexpect.readthedocs.org/en/latest/api/pexpect.html - Giovanni Funchal

@GiovanniFunchal 我不明白你提供的 pexpect 链接与原帖问题有什么关系。 - Gabriel Fair

pexpect 是一个 Python 库。您可以将 OP 拥有的管道文件描述符传递给它，然后使用带有正则表达式的 .expect() 进行解析。pexpect 添加的价值在于为您处理缓冲和阻塞管道。 - Giovanni Funchal

Answer 2

我曾经用经典的模式匹配方法解决了一个类似的搜索流问题。您可能想要继承我的解决方案 streamsearch-py 中的Matcher类，并在缓冲区中执行正则表达式匹配。请查看下面包含的kmp_example.py模板。如果您只需要经典的Knuth-Morris-Pratt匹配，那么使用这个小型开源库就可以解决您的问题了 :-)

#!/usr/bin/env python

# Copyright 2014-2015 @gitagon. For alternative licenses contact the author.
# 
# This file is part of streamsearch-py.
# streamsearch-py is free software: you can redistribute it and/or modify
# it under the terms of the GNU Affero General Public License as published by
# the Free Software Foundation, either version 3 of the License, or
# (at your option) any later version.
# 
# streamsearch-py is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
# GNU Affero General Public License for more details.
# You should have received a copy of the GNU Affero General Public License
# along with streamsearch-py.  If not, see <http://www.gnu.org/licenses/>.


from streamsearch.matcher_kmp import MatcherKMP
from streamsearch.buffer_reader import BufferReader

class StringReader():
    """for providing an example read() from string required by BufferReader"""
    def __init__(self, string):
        self.s = string
        self.i = 0

    def read(self, buf, cnt):
        if self.i >= len(self.s): return -1
        r = self.s[self.i]
        buf[0] = r
        result = 1
        print "read @%s" % self.i, chr(r), "->", result
        self.i+=1
        return result

def main():

    w = bytearray("abbab")
    print "pattern of length %i:" % len(w), w
    s = bytearray("aabbaabbabababbbc")
    print "text:", s
    m = MatcherKMP(w)
    r = StringReader(s)
    b = BufferReader(r.read, 200)
    m.find(b)
    print "found:%s, pos=%s " % (m.found(), m.get_index())


if __name__ == '__main__':
    main()

输出是

pattern of length 5: abbab
text: aabbaabbabababbbc
read @0 a -> 1
read @1 a -> 1
read @2 b -> 1
read @3 b -> 1
read @4 a -> 1
read @5 a -> 1
read @6 b -> 1
read @7 b -> 1
read @8 a -> 1
read @9 b -> 1
found:True, pos=5 

- gitagon

---

虽然这个链接可能回答了问题，但最好在此处包含答案的基本部分并提供参考链接。如果链接页面更改，仅有链接的答案可能会失效。 - Rustam Gasanov

kmp_example.py 的内容如下： - gitagon

Answer 3

我不相信在流上使用正则表达式是可能的，因为没有整个数据块，你无法进行准确匹配。这意味着你只能得到一个可能的匹配。

然而，正如@James Henstridge所说，你可以使用缓冲区来克服这个问题。

- IT Ninja

---

这听起来不正确。一个简单的正则表达式是一个DFA。每个输入字符在该DFA中都是状态转换。特定的转换表示匹配。除了高级功能或实现性能限制，完整的字符串不需要用于评估DFA在字符串上的结果。 - alexei