这个正则表达式能否进一步优化？

Question

这个正则表达式能否进一步优化？

4

我编写了这个正则表达式来解析SRT文件中的条目。

(?s)^\d++\s{1,2}(.{12}) --> (.{12})\s{1,2}(.+)\r?$

我不知道这是否重要，但这是使用Scala编程语言完成的（Java引擎，但使用文字字符串以便我不必双倍反斜杠）。

使用s{1,2}是因为某些文件仅具有换行符\n，而其他文件则具有换行符和回车符\n\r。第一个(?s)启用DOTALL模式，以使第三个捕获组也可以匹配换行符。

我的程序基本上使用\n\r?\n作为分隔符来拆分srt文件，并使用Scala很好的模式匹配功能来读取每个条目以进行进一步处理：

val EntryRegex = """(?s)^\d++\s{1,2}(.{12}) --> (.{12})\s{1,2}(.+)\r?$""".r

def apply(string: String): Entry = string match {
  case EntryRegex(start, end, text) => Entry(0, timeFormat.parse(start),
    timeFormat.parse(end), text);
}

样例输入:

一行：

1073
01:46:43,024 --> 01:46:45,015
I am your father.

两行：

160
00:20:16,400 --> 00:20:19,312
<i>Help me, Obi-Wan Kenobi.
You're my only hope.</i>

问题在于，分析器显示这种解析方法是我应用程序中耗时最长的操作（该应用程序进行密集的时间数学运算，甚至可以比读取和解析条目所需的时间快几倍重新编码文件）。

那么，有任何正则表达式专家可以帮助我优化吗？或者我应该牺牲正则表达式/模式匹配的简洁性，尝试一种老派的java.util.Scanner方法？

干杯！

- Anthony Accioly

4个回答

2

我并不是很乐观，但你可以尝试以下两个方法：

将 (?s) 移到需要它的位置之前。
删除 \r?$ 并使用贪婪的 .++ 来匹配文本 .+

^\d++\s{1,2}(.{12}) --> (.{12})\s{1,2}(?s)(.++)$

要真正实现良好的性能，我会重构代码和正则表达式以使用 findAllIn。目前的代码对于文件中的每个 Entry 都要进行一次正则表达式匹配。我想单个 findAllIn 正则表达式的性能会更好……但也许不会。

- Jacob Eggers

我非常确定占有量词不起作用 :D... 好吧，它确实起作用了，并且进一步提高了平均时间约5％（很难测量，但我肯定它更快，平均时间约为25ms）。关于findAllin，您知道它的迭代器是惰性还是严格的吗？我不想将整个文件读入内存，因为它们可能非常大。 - Anthony Accioly

无论如何，我接受你的答案，因为它更好地优化了正则表达式:D。 - Anthony Accioly

1

@Anthony Accioly，使用扫描器会比使用缓冲读取器并自行解析要影响性能更大。请参见此帖子。由于格式非常简单易解析，我建议先尝试一种没有正则表达式开销的基准测试。 - Voo

@Anthony Accioly几乎了解 - 我会边解析边进行。我没有找到srt格式的明确定义，只有一个论坛帖子。但是我认为你的第一行始终是唯一的整数ID（这只是一个parseInt()），第二行是具有时间+可选位置的复杂行，然后只需读取行，直到您获得空行（即完整文本）。解析第二行有点更复杂，但是您可以在“-->”处拆分它并使用（缓存！不要每次创建新的）SimpleDateFormatter。 - Voo

@Voo。非常感谢您的建议。我想您是正确的，逐行命令式解析可能是这种任务所能达到的最快速度。我正在使用SimpleDateFormatter（在上面的代码中，timeFormat正在执行此操作）。我将看看用自定义分隔符替换我的Scanner与BufferedReader +逐行解析如何运作：）。 - Anthony Accioly

显示剩余4条评论

2

看这个：

(?m)^\d++\r?+\n(.{12}) --> (.{12})\r?+\n(.++(?>\r?+\n.++)*+)$

这个正则表达式可以完整匹配一个.srt文件条目，而且无需先将内容拆分成行；这是一种极大的资源浪费。

该正则表达式利用了一个事实，即在条目内部有恰好一个行分隔符（\n或\r\n），而多个行分隔符用于将条目与彼此分开。使用\r?+\n而不是\s{1,2}意味着您永远不会意外匹配两个行分隔符（\n\n），而只想匹配一个。

这样，您也不必依赖(?s)模式中的.。@Jacob对此是正确的：它实际上并没有帮助您，反而影响了性能。但是，(?m)模式非常有用，既可以提高正确性，也可以提高性能。

您提到了java.util.Scanner；这个正则表达式可以非常好地与findWithinHorizon(0)一起使用。但是，如果Scala没有提供一种漂亮的、惯用的方法来使用它，我会感到惊讶。

- Alan Moore

Alan，非常感谢您提供的替代方案。我在原问题中忘记提到我实际上不需要一次性读取整个文件。同时，我确实需要times。尽管如此，我还是会点赞，因为您嵌套的非捕获组内包含捕获组的疯狂正则表达式技能真的很厉害。这就是区分正则表达式巫师和我们其他人的东西:D。 - Anthony Accioly

你的意思是需要捕获表示时间的 .{12} 部分吗？我没有有意地删除那些括号，只是专注于性能而不是副作用。我已经把它们加回去了。如果你只将正则表达式应用于单个条目，我认为性能不会成为大问题——但无论如何我都会避免使用 DOTALL 模式。 - Alan Moore

Alan，我觉得我表达不够清楚。我的应用程序超过70％的时间都在这个方法中，所以我正在重点关注它。我不一次性读取整个文件的原因是因为它可能非常大（几个GB），所以我只是一次读取一个条目，解析、处理、写入输出并丢弃。 - Anthony Accioly

但是这种方法不仅仅是正则表达式匹配。它在这两个调用 timeFormat.parse() 中花费了多少时间？ - Alan Moore

比看起来少的时间。好的、老式且冗长的java.util.Scanner实际上会将时间减半（而解析方法仍在使用）...但我想这就是正则表达式的工作方式。简洁以换取一点性能。看起来很公平。 - Anthony Accioly

1

我不会使用java.util.Scanner甚至字符串。只要您可以假定文件的UTF-8编码（或缺乏Unicode），则您正在执行的所有操作都将在字节流上完美运行。您应该能够将速度提高至少5倍。

编辑：这只是对字节和索引进行了大量低级操作。以下是基于我之前做过的事情稍微松散地组合而成的内容，速度大约快2倍至5倍，具体取决于文件大小、缓存等因素。我这里没有进行日期解析，只返回字符串，并假设文件小到可以放在单个内存块中（即<2G）。这样做非常谨慎；如果您知道例如日期字符串格式总是正确的，则解析可能更快（只需计算第一行数字后的字符数）。

import java.io._
abstract class Entry {
  def isDefined: Boolean
  def date1: String
  def date2: String
  def text: String
}
case class ValidEntry(date1: String, date2: String, text: String) extends Entry {
  def isDefined = true
}
object NoEntry extends Entry {
  def isDefined = false
  def date1 = ""
  def date2 = ""
  def text = ""
}

final class Seeker(f: File) {
  private val buffer = {
    val buf = new Array[Byte](f.length.toInt)
    val fis = new FileInputStream(f)
    fis.read(buf)
    fis.close()
    buf
  }
  private var i = 0
  private var d1,d2 = 0
  private var txt,n = 0
  def isDig(b: Byte) = ('0':Byte) <= b && ('9':Byte) >= b
  def nextNL() {
    while (i < buffer.length && buffer(i) != '\n') i += 1
    i += 1
    if (i < buffer.length && buffer(i) == '\r') i += 1
  }
  def digits() = {
    val zero = i
    while (i < buffer.length && isDig(buffer(i))) i += 1
    if (i==zero || i >= buffer.length || buffer(i) != '\n') {
      nextNL()
      false
    }
    else {
      nextNL()
      true
    }
  }
  def dates(): Boolean = {
    if (i+30 >= buffer.length) {
      i = buffer.length
      false
    }
    else {
      d1 = i
      while (i < d1+12 && buffer(i) != '\n') i += 1
      if (i < d1+12 || buffer(i)!=' ' || buffer(i+1)!='-' || buffer(i+2)!='-' || buffer(i+3)!='>' || buffer(i+4)!=' ') {
        nextNL()
        false
      }
      else {
        i += 5
        d2 = i
        while (i < d2+12 && buffer(i) != '\n') i += 1
        if (i < d2+12 || buffer(i) != '\n') {
          nextNL()
          false
        }
        else {
          nextNL()
          true
        }
      }
    }
  }
  def gatherText() {
    txt = i
    while (i < buffer.length && buffer(i) != '\n') {
      i += 1
      nextNL()
    }
    n = i-txt
    nextNL()
  }
  def getNext: Entry = {
    while (i < buffer.length) {
      if (digits()) {
        if (dates()) {
          gatherText()
          return ValidEntry(new String(buffer,d1,12), new String(buffer,d2,12), new String(buffer,txt,n))
        }
      }
    }
    return NoEntry
  }
}

现在你看到了，难道不为正则表达式的解决方案编写代码的快速性感到高兴吗？

- Rex Kerr

非常感谢，但我对从字节流中“解析”一事感到非常困惑...您介意分享一些代码吗？ - Anthony Accioly

哇，这是一些非常底层的解析 :) 但实际上，我想这就是优化意味着变得更原始的情况。出于学习目的，我将尝试深入了解。只是一个快速的问题，为了避免一次性加载整个文件，我正在考虑使用BufferedStream（例如100k缓冲区），并使每个方法在找到输入时已经返回Option [Type]，如果没有则返回None。我能用这个策略获得类似的性能吗？ - Anthony Accioly

@Anthony Accioly - 通过生成一堆Option实例，您将会失去一些性能，但它仍然应该可以正常工作。只需小心始终将字节存储在字节数组中并直接访问它们，而不是通过方便的Scala集合方法访问它们。这些方法需要装箱，因此会导致相当大的性能损失。 - Rex Kerr

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Mike Samuel · Accepted Answer

(?s)^\d++\s{1,2}(.{12}) --> (.{12})\s{1,2}(.+)\r?$

在Java中，$表示输入的结尾或者是在输入的结束处立即换行的开始。如果在Scala中的语义也是这样的话，那么\z就可以明确地表示输入的结尾，因此\r?$是多余的，只需要使用$即可。如果你真的只想在结尾添加CR而不是CRLF，那么\r?\z可能更好。 (?s)也应该使(.+)\r?变得多余，因为+是贪婪的，.应该始终扩展到包括\r。如果你不希望第三个捕获组中包含\r，那么可以将匹配方式改为懒惰模式：(.+?)代替(.+)。

也许

(?s)^\d++\s\s?(.{12}) --> (.{12})\s\s?(.+?)\r?\z

除了在JVM&|CLR内运行的正则表达式外，其他优秀的高性能替代方案包括JavaCC和ANTLR。对于仅适用于Scala的解决方案，请参见http://jim-mcbeath.blogspot.com/2008/09/scala-parser-combinators.html