12

我刚刚开始了解正则表达式，但是在阅读了很多内容（并且学到了很多东西）之后，我仍然无法找到解决这个问题的好方法。

让我说清楚，我知道不使用正则表达式可能会更好地解决这个特定问题，但为了简洁起见，我只想说我需要使用正则表达式（相信我，我知道有更好的方法来解决这个问题）。

这就是问题所在。我得到了一个大文件，每行正好有 4 个字符长。

这是一个定义“有效”行的正则表达式：

"/^[AB][CD][EF][GH]$/m"

在英语中，每行在位置 0 处有 A 或 B，在位置 1 处有 C 或 D，在位置 2 处有 E 或 F，在位置 3 处有 G 或 H。我可以假设每行正好是 4 个字符长。

我正在尝试做的是给定这些行之一，匹配包含 2 个或更多常见字符的所有其他行。

以下示例假定以下内容：

  1. $line始终是有效格式
  2. BigFileOfLines.txt仅包含有效行

例子：

// Matches all other lines in string that share 2 or more characters in common
// with "$line"
function findMatchingLines($line, $subject) {
    $regex = "magic regex I'm looking for here";
    $matchingLines = array();
    preg_match_all($regex, $subject, $matchingLines);
    return $matchingLines;
}

// Example Usage
$fileContents = file_get_contents("BigFileOfLines.txt");
$matchingLines = findMatchingLines("ACFG", $fileContents);

/*
 * Desired return value (Note: this is an example set, there 
 * could be more or less than this)
 * 
 * BCEG
 * ADFG
 * BCFG
 * BDFG
*/

我知道可行的一种方法是使用如下正则表达式（以下正则表达式仅适用于“ACFG”：

"/^(?:AC.{2}|.CF.|.{2}FG|A.F.|A.{2}G|.C.G)$/m"

这工作正常，性能是可以接受的。令我困扰的是，我必须基于 生成它$line，我宁愿让它不知道具体参数是什么。此外，如果稍后修改代码以匹配 3 个或更多字符，或者如果每行的大小从 4 增长到 16，则此解决方案的扩展性不佳。

感觉就像我忽略了一些非常简单的事情。似乎这可能是一个重复的问题，但我看过的其他问题似乎都没有真正解决这个特定问题。

提前致谢！

更新：

似乎正则表达式答案的规范是让 SO 用户简单地发布一个正则表达式并说“这应该适合你”。

我认为这是一个半途而废的答案。我真的很想了解正则表达式，所以如果您可以在答案中包含对为什么该正则表达式的彻底（合理）解释：

  • A. 作品
  • B. 是最有效的（我觉得可以对主题字符串做出足够多的假设，可以进行相当多的优化）。

当然，如果您给出一个有效的答案，并且没有其他人*用* 解决方案发布答案​​，我会将其标记为答案 :)

更新 2：

谢谢大家的精彩回复，很多有用的信息，你们中的很多人都有有效的解决方案。我选择了我所做的答案，因为在运行性能测试之后，它是最好的解决方案，平均运行时间与其他解决方案相同。

我赞成这个答案的原因：

  1. 给定的正则表达式为更长的行提供了出色的可伸缩性
  2. 正则表达式看起来更干净，对于像我这样的凡人来说更容易解释。

但是，很多功劳归功于以下答案，因为他们非常彻底地解释了为什么他们的解决方案是最好的。如果您遇到这个问题是因为这是您想要弄清楚的问题，请给他们全部阅读，这对我有很大帮助。

4

7 回答 7

4

你为什么不直接使用这个正则表达式$regex = "/.*[$line].*[$line].*/m";？

对于您的示例，这转化为$regex = "/.*[ACFG].*[ACFG].*/m";

于 2012-04-22T23:38:23.027 回答
2

这是一个定义“有效”行的正则表达式：

/^[A|B]{1}|[C|D]{1}|[E|F]{1}|[G|H]{1}$/m

在英语中，每行在位置 0 处有 A 或 B，在位置 1 处有 C 或 D，在位置 2 处有 E 或 F，在位置 3 处有 G 或 H。我可以假设每行正好是 4 个字符长。

那不是那个正则表达式的意思。该正则表达式意味着每行都有 A 或 B 或位置 0 的管道、C 或 D 或位置 1 的管道等； [A|B]意思是“'A'或'|' 或'B'”。'|' 仅表示字符类 之外的“或​​”。

此外，{1}是无操作；缺少任何量词，一切都必须恰好出现一次。因此，上述英语的正确正则表达式是：

/^[AB][CD][EF][GH]$/

或者，或者：

/^(A|B)(C|D)(E|F)(G|H)$/

第二个具有捕获每个位置的字母的副作用，因此第一个捕获的组会告诉您第一个字符是 A 还是 B，依此类推。如果您不想捕获，可以使用非捕获分组：

/^(?:A|B)(?:C|D)(?:E|F)(?:G|H)$/

但是字符类版本是迄今为止写这个的常用方式。

至于你的问题，它不适合正则表达式；当你解构字符串，用适当的正则表达式语法将它重新组合在一起，编译正则表达式并进行测试时，你可能会更好地进行逐个字符的比较。

我会重写你的“ACFG”正则表达式：/^(?:AC|A.F|A..G|.CF|.C.G|..FG)$/，但这只是外观；我想不出使用正则表达式的更好解决方案。（尽管正如迈克·瑞安（Mike Ryan）所指出的那样，最好还是/^(?:A(?:C|.E|..G))|(?:.C(?:E|.G))|(?:..EG)$/- 但这仍然是相同的解决方案，只是以更有效的处理形式。）

于 2012-04-22T23:34:08.757 回答
1

您已经回答了如何使用正则表达式进行操作，并指出了它的缺点和无法扩展，所以我认为没有必要鞭打死马。相反，这是一种无需正则表达式即可工作的方法：

function findMatchingLines($line) {
    static $file = null;
    if( !$file) $file = file("BigFileOfLines.txt");

    $search = str_split($line);
    foreach($file as $l) {
        $test = str_split($l);
        $matches = count(array_intersect($search,$test));
        if( $matches > 2) // define number of matches required here - optionally make it an argument
            return true;
    }
    // no matches
    return false;
}
于 2012-04-22T23:39:19.070 回答
1

人们可能会对您的第一个正则表达式感到困惑。你给：

"/^[A|B]{1}|[C|D]{1}|[E|F]{1}|[G|H]{1}$/m"

然后说：

在英语中，每行在位置 0 处有 A 或 B，在位置 1 处有 C 或 D，在位置 2 处有 E 或 F，在位置 3 处有 G 或 H。我可以假设每行正好是 4 个字符长。

但这根本不是那个正则表达式的意思。

这是因为|运算符在这里具有最高优先级。因此，该正则表达式在英语中真正所说的是：要么A或|或B在第一个位置，要么或或在第一个位置，或或C或在第一个位置，或或'| H`在第一个位置。|DE|FGor

这是因为[A|B]表示具有三个给定字符之一的字符类（包括|. 并且因为{1}表示一个字符（它也是完全多余的，可以删除），并且因为|它周围的一切都在外部交替出现。在我上面的英语表达中每个大写的 OR 代表你的一个交替|的。（我开始从 1 开始计算位置，而不是 0——我不想输入第 0 位置。）

要将您的英语描述作为正则表达式，您需要：

/^[AB][CD][EF][GH]$/

正则表达式将通过并检查A或B（在字符类中）的第一个位置，然后检查C或D在下一个位置等。

--

编辑：

您只想测试这四个字符中的两个是否匹配。

非常严格地说，从@Mark Reed 的回答中，最快的正则表达式（在它被解析之后）可能是：

/^(A(C|.E|..G))|(.C(E)|(.G))|(..EG)$/

相比于：

/^(AC|A.E|A..G|.CE|.C.G|..EG)$/

这是因为正则表达式实现如何通过文本逐步执行。您首先测试是否A在第一个位置。如果成功，那么您测试子案例。如果失败了，那么你就完成了所有这些可能的情况（或者有 3 个）。如果您还没有匹配，则测试 C 是否处于第二位。如果成功，那么您测试这两个子案例。如果这些都没有成功，你测试，'EG 在第 3 和第 4 位置。

这个正则表达式是专门为尽快失败而创建的。分别列出每个案例，意味着失败，您将测试 6 个不同的案例（六个备选方案中的每一个），而不是 3 个案例（至少）。如果A不是第一名，你会立即去测试第二名，而不是再打两次。等等。

（请注意，我不确切知道 PHP 是如何编译正则表达式的——它们可能编译为相同的内部表示，尽管我怀疑不是。）

--

编辑：关于附加点。最快的正则表达式是一个有点模棱两可的术语。最快失败？最快成功？并给出成功行和失败行的样本数据的可能范围？必须澄清所有这些，才能真正确定您所说的最快标准是什么。

于 2012-04-22T23:40:23.667 回答
1

这是使用Levenshtein 距离而不是正则表达式的东西，并且应该足够可扩展以满足您的要求：

$lines = array_map('rtrim', file('file.txt')); // load file into array removing \n
$common = 2; // number of common characters required
$match = 'ACFG'; // string to match

$matchingLines = array_filter($lines, function ($line) use ($common, $match) {
    // error checking here if necessary - $line and $match must be same length
    return (levenshtein($line, $match) <= (strlen($line) - $common));
});

var_dump($matchingLines);
于 2012-04-22T23:42:47.400 回答
1

有 6 种可能性， 4 个字符中至少有两个字符匹配：MM..、MM、M..M、.MM.、.MM 和 ..MM（“M”表示匹配，“.”表示不匹配-匹配）。

因此，您只需要将输入转换为匹配任何这些可能性的正则表达式。对于 的输入ACFG，您将使用以下命令：

"/^(AC..|A.F.|A..G|.CF.|.C.G|..FG)$/m"

当然，这是您已经得出的结论——到目前为止非常好。

关键问题是 Regex 不是一种用于比较的语言two strings，它是一种用于将字符串与模式进行比较的语言。因此，您的比较字符串必须是模式的一部分（您已经找到），或者它必须是input 的一部分。后一种方法允许您使用通用匹配，但确实需要您修改输入。

function findMatchingLines($line, $subject) {
  $regex = "/(?<=^([AB])([CD])([EF])([GH])[.\n]+)"
      + "(\1\2..|\1.\3.|\1..\4|.\2\3.|.\2.\4|..\3\4)/m";
  $matchingLines = array();
  preg_match_all($regex, $line + "\n" + $subject, $matchingLines);
  return $matchingLines;
}

这个函数的作用是在你的输入字符串前面加上你想要匹配的行，然后使用一个模式将第一行之后的每一行（即工作+后[.\n]）与第一行的 4 个字符进行比较。

如果您还想根据“规则”验证这些匹配行，只需将.每个模式中的 替换为适当的字符类（\1\2[EF][GH]等）。

于 2012-04-22T23:51:14.473 回答
1

我昨天晚上将问题添加为书签以今天发布答案，但似乎我有点晚了^^无论如何这是我的解决方案：

/^[^ACFG]*+(?:[ACFG][^ACFG]*+){2}$/m

ACFG它查找被任何其他字符包围的字符之一的两次出现。循环展开并使用所有格量词，以稍微提高性能。

可以使用以下方法生成：

function getRegexMatchingNCharactersOfLine($line, $num) {
    return "/^[^$line]*+(?:[$line][^$line]*+){$num}$/m";
}
于 2012-04-23T17:47:28.813 回答