5

我正在寻求实现一些算法来帮助我匹配不完美的序列。

假设我有一个存储的 ABBABABBA 序列,我想在大量字符流中找到“看起来像”的东西。

如果我允许我的算法有 2 个通配符(差异),我如何使用正则表达式来匹配如下内容: where ( 和 ) 标记差异:

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

我的困境是我希望在一大串字符中找到这些潜在的目标匹配(有缺陷)。所以在类似的情况下:

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

我必须能够搜索这些“足够接近”的匹配项。
其中括号表示:(The Good enough Match with the (Differences))

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

我以前使用过正则表达式,但只是为了找到完美的序列——而不是为了“看起来像”的东西。

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

4

7 回答 7

3

您可以使用 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)

这会跳过前 2 个结果。

Any()

如果还有任何结果,则返回 true,否则返回 false。因为 linq 在 this 为 false 的那一刻推迟执行,所以函数退出而不是评估字符串的其余部分。

然后通过前缀“!”来否定整个测试 表示我们想知道哪里没有更多的结果。

现在为了匹配为子字符串,您需要表现得类似于正则表达式回溯......

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();
}

更新解释

Enumerable.Range(0,test.Length - source.Length)

这会创建一个从 0 到 test.Length - source.Length 的数字序列,不需要从 test 中的每个字符开始检查,因为一旦长度变短,答案就无效。

从我...

基本上迭代集合,每次都将 i 分配为当前值

其中 IsValid(source, !test.Skip(i).Take(source.Length))

过滤结果以仅包括在测试中从索引 i 开始(因此跳过)并继续 source.Length 字符(因此 take.Length 字符)匹配的结果。

选择我

返回我

这将返回一个可枚举的测试中存在匹配项的索引,您可以使用

GetMatches(source,test).Select(i => 
                      new string(test.Skip(i).Take(source.Length).ToArray()));
于 2013-06-27T14:46:16.387 回答
2

我认为这不能用正则表达式来完成(如果可以的话,我不熟悉语法)。但是,您可以对Levenshtein distance使用动态规划算法。

编辑:如果您不需要处理已切换位置的字母,一种更简单的方法是只比较两个字符串中的每对字符,然后计算差异的数量。

于 2013-06-27T13:18:47.963 回答
2

我想不出你会如何用正则表达式来做,但它的代码应该很简单。

我可能只是将字符串拆分并逐个字符地比较它们。如果您有差异,请计算并移至下一个字符。如果超过 2 个差异,则继续下一个完整字符串。

于 2013-06-27T13:40:32.810 回答
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;
}

大多数时候,不要担心你的字符串太长而无法进入循环。在幕后,任何评估字符串每个字符的代码都会以某种形式循环。直到您确实有数百万个字符要处理,循环应该可以很好地解决问题。

于 2013-06-27T13:40:36.563 回答
1

我将绕过“正则表达式”部分并专注于:

有没有比对每个位置进行通配符嵌套循环更好的方法?

听起来有一种程序化方式可能会对您有所帮助。 请参阅这篇关于迭代两个 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();
}
于 2013-06-27T13:46:13.920 回答
0

AB和的任何组合都(有效)吗?

bool isMatch = Regex.IsMatch(inputString, "^[AB()]+$")
于 2013-06-27T13:18:13.143 回答
0

对于足够小的模式(ABCD),您可以生成一个正则表达式:

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

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

于 2013-06-27T13:51:06.753 回答