Regex查找'；足够好'；序列

本文关键字：序列 Regex 查找 | 更新日期: 2023-09-27 18:20:11

我想实现一些算法来帮助我匹配不完美的序列。

假设我有一个ABBABABA的存储序列，我想在一大串字符中找到"看起来像"的东西。

如果我允许我的算法有2个通配符（差异），我如何使用Regex来匹配这样的东西：在哪里（和）标记差异：

A(A)BABAB(A)A 
or 
(B)BBA(A)ABBA

我的困境是，我希望在一大串角色中找到这些潜在的目标匹配（有缺陷）。因此，在类似的情况下

ABBDBABDBCBDBABDB(A(A)BABAB(A)A)DBDBABDBCBDBAB
ADBDBABDBDBDBCBDBABCBDBABCBDBABCBDBABABBBDBABABBCD
DBABCBDABDBABCBCBDBABABDABDBABCBDBABABDDABCBDBABAB

我必须能够搜索这些"足够接近"的匹配项
括号中表示：（与（差异）的充分匹配）

编辑：在本例中，为了更正式，如果N-2个字符与原始（2个差异）相同，则可以接受长度为N的匹配

我以前用过Regex，但只是为了找到完美的序列——而不是"看起来像"的序列。

希望这一点足够清楚，可以得到一些建议。感谢您的阅读和任何帮助！

Regex查找'；足够好'；序列

您可以使用LINQ来表现出色。

为了使用它，请确保在代码的顶部有一个using System.Linq。

假设

  • source是存储的目标模式
  • test是要测试的字符串

然后你可以做

public static bool IsValid(string source, string test) 
{
  return test != null  
         && source != null 
         && test.Length == source.Length 
         && test.Where((x,i) => source[i] != x).Count() <=2
}

还有一个快捷方式版本，它在失败时退出false，从而避免迭代字符串的其余部分。

public static bool IsValid(string source, string test) 
{
   return test != null  
          && source != null 
          && test.Length == source.Length 
          && !test.Where((x,i) => source[i] != x).Skip(2).Any();
}

根据评论中的要求，对其工作原理进行一点解释

在C#中，字符串可以被视为一个字符数组，这意味着Linq方法可以用于它

test.Where((x,i) => source[i] != x)

这使用了Where的重载，即对于测试中的每个字符，x被分配给该字符，而i被分配给索引。如果源中位置i处的条件字符不等于x，则输出到结果中。

Skip(2)

这跳过前两个结果。

Any()

如果还有任何结果，则返回true；如果没有，则返回false。因为linq会在这是false的时候延迟执行，所以函数会退出，而不是计算字符串的其余部分。

然后通过在整个测试前面加一个"！"来否定它表示我们想知道哪里没有更多的结果。

现在，为了匹配为子字符串，您需要类似于regex回溯的行为。。。

public static IEnumerable<int> GetMatches(string source, string test)
{
   return from i in Enumerable.Range(0,test.Length - source.Length)
      where IsValid(source, !test.Skip(i).Take(source.Length))
          select i;
}
public static bool IsValid(string source, IEnumerable<char> test) 
{
   return test.Where((x,i) => source[i] != x).Skip(2).Any();
}

更新解释

可枚举.范围（0，test.Length-源.Length）

这将创建一个从0到测试的数字序列。长度-来源。长度，不需要从测试中的每个字符开始检查，因为一旦长度变短，答案就无效。

从我在。。。。

基本上是在每次时对集合进行迭代，将i指定为当前值

其中IsValid（source，！test.Skip（i）.Take（source.Length））

过滤结果，只包括在测试中从索引i开始（因此跳过）并对源进行匹配的结果。长度字符（因此取.

选择i

返回i

这将在测试中返回一个可枚举的索引，如果有匹配，您可以使用提取它们

GetMatches(source,test).Select(i => 
                      new string(test.Skip(i).Take(source.Length).ToArray()));

我认为这不能用正则表达式完成（如果可以的话，我不熟悉语法）。但是，您可以使用Levenstein距离的动态编程算法。

编辑：如果你不需要处理位置转换的字母，一个简单得多的方法是只比较两个字符串中的每一对字符，然后计算差异的数量。

我想不出如何使用regex，但它的代码应该非常简单。

我可能只是把字符串分开，逐个比较。如果你得到一个差异，计算它并移动到下一个字符。如果超过2个差异，则转到下一个完整字符串。

我认为没有一个好的正则表达式来处理这种情况。（或者至少，没有一个不会占用三行文字并导致多个子弹击中你的脚。）然而，这并不意味着你不能解决这个问题。

根据你的字符串有多大（我假设每个字符串不会有数百万个字符），我看不出有什么能阻止你使用单个循环按顺序比较单个字符，同时记录差异：

int differences = 0;    // Count of discrepancies you've detected
int tolerance = 7;    // Limit of discrepancies you'll allow
CheckStrings(int differences, int tolerance) {
    for (i = 0; i < StringA.Length; i++)
    {
        if (StringA[i] != StringB[i]) {
            differences++;
            if (differences > tolerance) {
                return false;
            }
        }
    }
    return true;
}

大多数时候，不要担心你的字符串太长而无法放入循环中。在幕后，任何评估字符串中每个字符的代码都会以某种形式循环。除非你真的有数百万个字符要处理，否则循环应该可以很好地完成任务。

我将绕过"regex"部分，专注于：

有没有比嵌套循环更好的方法来通配符化每个位置？

听起来有一种程序化的方式可能会对你有所帮助。请参阅这篇关于迭代两个IEnumerables的文章。通过同时对两个字符串进行迭代，可以在O（n）时间内完成任务。更好的是，如果你知道你的容忍度（最多2个错误），你有时可以比O（n）更快地完成。

这是我写的一个简单的例子。它可能需要根据你自己的情况进行调整，但这可能是一个很好的起点。

static void imperfectMatch(String original, String testCase, int tolerance)
{
    int mistakes = 0;
    if (original.Length == testCase.Length)
    {
        using (CharEnumerator enumerator1 = original.GetEnumerator())
        using (CharEnumerator enumerator2 = testCase.GetEnumerator())
        {
            while (enumerator1.MoveNext() && enumerator2.MoveNext())
            {
                if (mistakes >= tolerance)
                    break;
                if (enumerator1.Current != enumerator2.Current)
                    mistakes++;
            }
        }
    }
    else
        mistakes = -1;
    Console.WriteLine(String.Format("Original String: {0}", original));
    Console.WriteLine(String.Format("Test Case String: {0}", testCase));
    Console.WriteLine(String.Format("Number of errors: {0}", mistakes));
    Console.WriteLine();
}

A、B、(和)的任何组合都有效吗？

bool isMatch = Regex.IsMatch(inputString, "^[AB()]+$")

对于足够小的模式（ABCD），您可以生成一个正则表达式：

..CD|.B.D|.BC.|A..D|A.C.|AB..

您还可以编写一个自定义比较循环

相关文章：