如何比较两个字符串数组，并找到所有连续的匹配和保存索引

本文关键字：连续 索引 保存 比较 何比较 两个 数组 字符串 | 更新日期: 2023-09-27 18:18:20

例如，如果我有以下两个数组:

string[] userSelect = new string[] {"the", "quick", "brown", "dog", "jumps", "over"};
string[] original = new string[] {"the", "quick", "brown", "fox", "jumps", "over", "the", "lazy", "dog"};

我试图将userSelect数组与原始数组进行比较，并根据索引获得所有连续匹配。userSelect数组将始终由原始数组中的字符串组成。因此输出如下所示:

int[] match0 = new int[] {0, 1, 2}; // indices for "the quick brown"
int[] match2 = new int[] {4, 5}; // indices for "jumps over"
int[] match1 = new int[] {3}; // index for "dog"

userSelect数组的长度永远不会超过原始数组的长度，但是它可以更短，单词可以按任何顺序排列。我该怎么做呢?

如何比较两个字符串数组，并找到所有连续的匹配和保存索引

我是这么想的

var matches = 
    (from l in userSelect.Select((s, i) => new { s, i })
     join r in original.Select((s, i) => new { s, i }) 
     on l.s equals r.s 
     group l by r.i - l.i into g
     from m in g.Select((l, j) => new { l.i, j = l.i - j, k = g.Key })
     group m by new { m.j, m.k } into h
     select h.Select(t => t.i).ToArray())
    .ToArray();

这将输出

matches[0] // { 0, 1, 2 } the quick brown
matches[1] // { 4, 5 } jumps over
matches[2] // { 0 } the 
matches[3] // { 3 } dog

使用输入{"the", "quick", "brown", "the", "lazy", "dog"}产率:

matches[0] // { 0, 1, 2 } the quick brown
matches[1] // { 0 } the 
matches[2] // { 3 } the
matches[3] // { 3, 4, 5 } the lazy dog

注意对ToArray的调用是可选的。如果你实际上不需要数组中的结果，你可以省略它，节省一点处理时间。

要过滤掉完全包含与其他大序列的任何序列，您可以运行以下代码(注意修改后的查询中的orderby):

var matches = 
    (from l in userSelect.Select((s, i) => new { s, i })
     join r in original.Select((s, i) => new { s, i }) 
     on l.s equals r.s 
     group l by r.i - l.i into g
     from m in g.Select((l, j) => new { l.i, j = l.i - j, k = g.Key })
     group m by new { m.j, m.k } into h
     orderby h.Count() descending
     select h.Select(t => t.i).ToArray());
int take = 0;
var filtered = matches.Where(m => !matches.Take(take++)
                                          .Any(n => m.All(i => n.Contains(i))))
    .ToArray();

如果单词不能重复，这将更容易…

一般的想法是从原始单词列表创建一个Dictionary<string, List<int>>。它会告诉你哪些单词在什么位置使用。示例的字典为:

key="the", value={0, 6}
key="quick", value={1}
key="brown", value={2}
... etc

现在，当您获得用户的输入时，您将按顺序遍历它，在字典中查找单词以获得位置列表。

你查一个单词，它在字典里。保存从字典返回的位置。查下一个单词。您需要处理以下三种情况:

    这个词在字典里找不到。保存之前的连续分组，然后转到下一个单词，在那里您可能会开始一个新组。
  1. 单词在字典中，但是返回的位置都不匹配预期位置(预期位置比最后一个单词保存的位置多一个)。保存之前的连续组，然后转到下一个单词，在那里你可能会开始一个新组。
  2. 单词在字典中，并且返回的位置之一与期望的位置匹配。保存这些位置并转到下一个单词。
我希望你能明白。

这并不完全是你想要的，但这是一个非常干净和简单的方法来获得一个包含所有常见字符串的新数组(即取两个数组的交集)。

var results = array1.Intersect(array2, StringComparer.OrdinalIgnoreCase);

执行resutls后，数组将包含array1和array2中出现的所有字符串(忽略大小写)。

如果你想要一点理论，相交方法是基于你在λ微积分中对集合进行的相交操作。c#中的集合实现了所有常见的集合操作，所以对它们有一些熟悉是值得的。这是维基文章的链接;http://en.wikipedia.org/wiki/Intersection_(set_theory)

这不是很优雅但很有效。当涉及到索引时，Linq使它比简单的循环更复杂，效率更低。

string[] userSelect = new string[] { "the", "quick", "brown", "dog", "jumps", "over" };
string[] original = new string[] { "the", "quick", "brown", "fox", "jumps", "over", "the", "lazy", "dog" };
var consecutiveGroups = new Dictionary<int, IList<string>>();
IList<Tuple<int, string>> uniques = new List<Tuple<int, string>>();
int maxIndex = Math.Min(userSelect.Length, original.Length);
if (maxIndex > 0)
{
    int minIndex = 0;
    int lastMatch = int.MinValue;
    for (int i = 0; i < maxIndex; i++)
    {
        var us = userSelect[i];
        var o = original[i];
        if (us == o)
        {
            if (lastMatch == i - 1)
                consecutiveGroups[minIndex].Add(us);
            else
            {
                minIndex = i;
                consecutiveGroups.Add(minIndex, new List<string>() { us });
            }
            lastMatch = i;
        }
        else
            uniques.Add(Tuple.Create(i, us));
    }
}

输出连续组的索引+唯一组的索引:

var consecutiveGroupsIndices = consecutiveGroups
    .OrderByDescending(kv => kv.Value.Count)
    .Select(kv => Enumerable.Range(kv.Key, kv.Value.Count).ToArray()
    .ToArray());
foreach(var consIndexGroup in consecutiveGroupsIndices)
    Console.WriteLine(string.Join(",", consIndexGroup));
Console.WriteLine(string.Join(",", uniques.Select(u => u.Item1)));

使用LINQ添加乐趣

经过几次尝试后，我想出了一个纯LINQ解决方案，理论上可以是一个一行程序。我确实试图使它高效，但当然函数式解决方案将导致重复计算，因为你不能保持状态。

我们首先进行一些预处理，以节省以后的重复计算。是的，我知道我对index所做的是一个有问题的做法，但如果你小心的话，它是有效的，并且它很快到达那里:

var index = 0;
var lookup = original.ToLookup(s => s, s => index++);

怪物

var occurrences = userSelect
  .Where(lookup.Contains)
  .SelectMany((s, i) => lookup[s]
    .Select(j => new {
      User = userSelect.Skip(i),
      Original = original.Skip(j),
      Skipped = i
    })
    .Select(t => t.User.Zip(t.Original, (u, v) => Tuple.Create(u, v, t.Skipped))
                       .TakeWhile(tuple => tuple.Item1 == tuple.Item2)
    )
    .Select(u => new { 
      Word = s, 
      Start = u.Select(v => v.Item3).Min(), 
      Length = u.Count()
    })
  )
  .GroupBy(v => v.Start + v.Length)
  .Select(g => g.OrderBy(u => u.Start).First())
  .GroupBy(v => v.Word)
  .Select(g => g.OrderByDescending(u => u.Length).First())
  .Select(w => Enumerable.Range(w.Start, w.Length).ToArray())
  .ToList();

用

打印
foreach (var occurrence in occurrences) {
  Console.WriteLine(
    "Maximal match starting with '{0}': [{1}]",
    userSelect[occurrence[0]],
    string.Join(", ", occurrence)
  );
}

为

Maximal match starting with 'the': [0, 1, 2]
Maximal match starting with 'dog': [3]
Maximal match starting with 'jumps': [4, 5]
很明显，您不希望在生产中使用此代码，到目前为止，另一种(过程化的)解决方案更可取。然而，除了lookup之外，这个解决方案的区别在于它是纯功能性的。当然，这也可以用函数方式写: 
var lookup = original.Select((s, i) => Tuple.Create)
                     .ToLookup(t => t.Item1, t => t.Item2);

工作原理

预热，它创建一个类似字典的结构，将original中的每个单词与其在同一集合中出现的索引关联起来。这将在稍后用于从userSelect中的每个单词创建尽可能多的匹配序列(例如:"the"将产生两个匹配的序列，因为它在original中出现了两次。

: 

.Where(lookup.Contains)

这很简单，它会从userSelect中删除所有没有出现在original中的单词。

 // For each place where the word s appears in original...
.SelectMany((s, i) => lookup[s]
  // Define the two subsequences of userSelect and original to work on.
  // We are trying to find the number of identical elements until first mismatch.
  .Select(j => new { User = userSelect.Skip(i), Original = original.Skip(j), Skipped = j })
  // Use .Zip to find this subsequence
  .Select(t => t.User.Zip(t.Original, (u, v) => Tuple.Create(u, v, t.Skipped)).TakeWhile(tuple => tuple.Item1 == tuple.Item2))
  // Note the index in original where the subsequence started and its length
  .Select(u => new { Word = s, Start = u.Select(v => v.Item3).Min(), Length = u.Count() })
)

此时，我们已经将userSelect中的每个匹配词投影到具有Start和Length属性的匿名对象。然而，匹配长度为N的序列也会产生更小的匹配序列，长度为N-1, N-2，…1 .

这里的关键是要意识到对于这些集合中的所有子序列Start + Length都是相同的;而且，不同集合的子序列的Start + Length的和也不同。因此，让我们利用这个优势来精简结果:

// Obvious from the above
.GroupBy(v => v.Start + v.Length)
// We want to keep the longest subsequence. Since Start + Length is constant for
// all, it follows the one with the largest Length has the smallest Start:
.Select(g => g.OrderBy(u => u.Start).First())

这仍然会使我们在userSelect中每个单词的匹配次数与该单词在original中出现的次数相同。让我们把它缩减到最长匹配:

.GroupBy(v => v.Word)
.Select(g => g.OrderByDescending(u => u.Length).First())

我们现在有一个像{ Word = "the", Start = 0, Length = 3 }这样的对象。让我们将其转换为userSelect中的索引数组:

.Select(w => Enumerable.Range(w.Start, w.Length).ToArray())

最后把所有这些数组放到同一个集合中，任务完成了!

相关文章：