より大きなシーケンス内のパターンのすべての出現を見つけるための効率的なアルゴリズムが必要です。
たとえば、次の入力があるとします。
パターン: GAS
シーケンス: ASDFGASDFGASDFADFASDFGA
期待される出力: {4, 9}
同様の質問に対する受け入れられた回答によると、目的のタスクを達成するためのアルゴリズムが実装されています。ただし、あるコメントは、アルゴリズムが「大きなバイト配列で遅い」と報告しています。
読んだ後、これを行うための最良のアルゴリズムは、CodeProject の C# で実装されたBoyer - Moore 文字列検索アルゴリズムであるように見えますが、一般的な列挙型に対して実装するのに問題があります。
Boyer-Moore アルゴリズムに基づいて、.NETの一般的なシーケンスでパターンのすべての出現を見つける既存のソリューションはありますか?
注:
この例では文字列を使用しましたが、IEnumerable を実装するすべてのデータで機能する回答が必要です。つまり、文字列だけでなく、あらゆるタイプで機能するはずです。
シーケンスがパターンの繰り返しであり、パターンが m 回繰り返される別のパターンである場合、最悪の場合のパフォーマンスは O(nm) (n = seq.Count) です (間違っている場合は訂正してください)。
List<int> LookFor<T>( IEnumerable<T> seq, T[ ] pattern )
where T : IEquatable<T> {
var partialMatches = new LinkedList<int>( );
var matches = new List<int>( );
int i = 0;
foreach ( T item in seq ) {
if ( item.Equals( pattern[ 0 ] ) )
partialMatches.AddLast( 0 );
var n = partialMatches.First;
while(n != null) {
if ( item.Equals( pattern[ n.Value ] ) ) {
n.Value += 1;
if ( n.Value == pattern.Length ) {
matches.Add( i - pattern.Length + 1 );
var next = n.Next;
partialMatches.Remove( n );
n = next;
continue;
}
}
else partialMatches.Remove( n );
n = n.Next;
}
i += 1;
}
return matches;
}
テスト:
void Main()
{
var matches = LookFor( "abcabcabcabcabcabcabc",
new char[ ] { 'a', 'b', 'c', 'a', 'b', 'c', 'a', 'b', 'c' } );
foreach ( var x in matches )
Console.WriteLine( "{0}", x );
}
出力：
0
3
6
9
12
Boyer-Moore アルゴリズムを理解するのに苦労した後、より大きなコレクションに対して 1 回のパスでパターン マッチングを行うこのコードをまとめました。
Boyer-Moore アルゴリズムに対してテストすることはできませんでしたが、シーケンス全体がパターンの繰り返しである場合の最悪の場合のパフォーマンスとしてO(nm)で、非常に効率的に動作します。
これが私の実装です。それについてのあなたの見解を教えてください。
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace ConsoleApplication1
{
class Program
{
static void Main(string[] args)
{
Console.WriteLine("Enter the string you want to search within.");
string hayStack = Console.ReadLine();
Console.WriteLine("Enter the string you want to search for.");
string needle = Console.ReadLine();
var ps = new PatternSearch<char>(needle.ToCharArray());
Console.WriteLine();
Console.WriteLine();
Console.WriteLine(hayStack);
var matches = ps.Matches(hayStack.ToCharArray()).ToList();
for (int i = 0; i < hayStack.Length; i++)
Console.Write(matches.Contains(i) ? "↑" : " ");
Console.WriteLine();
Console.ReadLine();
}
}
/// <summary>Implements a pattern searching algorithm with <b>O(nm)</b> worst-case performance.</summary>
/// <typeparam name="T">The data type of the array to search.</typeparam>
public class PatternSearch<T>
{
private struct MatchInfo
{
public MatchInfo(int startIndex, int matchLength)
{
this.StartIndex = startIndex;
this.MatchLength = matchLength;
}
public int StartIndex;
public int MatchLength;
}
private IEnumerable<T> pattern;
private List<MatchInfo> found;
private Func<T, T, bool> eqComp;
//optimization for IEnumerables that do not implement IList
int patLen = -1;
int seqLen = -1;
/// <summary>Initializes a new instance of the <see cref="PatternSearch{T}" /> class.</summary>
/// <param name="pattern">The pattern that will be searched for.</param>
public PatternSearch(T[] pattern) : this(pattern, (x, y) => x.Equals(y)) { }
/// <summary>
/// Initializes a new instance of the <see cref="PatternSearch{T}"/> class with the specified equality comparer.
/// </summary>
/// <param name="pattern">The pattern to be searched for.</param>
/// <param name="equalityComparer">The equality comparer to use for matching elements in the array.</param>
public PatternSearch(T[] pattern, Func<T, T, bool> equalityComparer)
{
patLen = pattern.Length;
if (pattern == null)
throw new ArgumentNullException("pattern", "The search pattern cannot be null.");
if (equalityComparer == null)
throw new ArgumentNullException("equalityComparer", "The equality comparer cannot be null.");
if (patLen <= 0)
throw new ArgumentException("pattern", "The pattern cannot be empty.");
// assign the values
this.pattern = pattern;
found = new List<MatchInfo>();
eqComp = equalityComparer;
}
/// <summary>
/// Returns the start index of all occurrences of the search pattern within the specified array.
/// </summary>
/// <param name="seq">The larger sequence to find occurrences of the search pattern within.</param>
public IEnumerable<int> Matches(IEnumerable<T> seq)
{
seqLen = seqLen == -1 ? seq.Count() : seqLen;
return this.Matches(seq, 0, seqLen);
}
/// <summary>
/// Returns the start index of all occurrences of the search pattern within the specified array.
/// </summary>
/// <param name="seq">The larger sequence to find occurrences of the search pattern within.</param>
/// <param name="startIndex">The index in <paramref name="seq"/> to start searching at.</param>
public IEnumerable<int> Matches(IEnumerable<T> seq, int startIndex)
{
seqLen = seqLen == -1 ? seq.Count() : seqLen;
return this.Matches(seq, startIndex, seqLen);
}
/// <summary>
/// Returns the start index of all occurrences of the search pattern within the specified array.
/// </summary>
/// <param name="seq">The larger sequence to find occurrences of the search pattern within.</param>
/// <param name="count">The maximum number of items in <paramref name="seq"/> to match.</param>
public IEnumerable<int> Matches(IEnumerable<T> seq, int startIndex, int count)
{
patLen = patLen == -1 ? pattern.Count() : patLen;
seqLen = seqLen == -1 ? seq.Count() : seqLen;
bool addedNew = false;
var endPoint = Math.Min(seqLen, startIndex + count);
if (seq == null || // sequence cannot be null
seqLen < patLen || // pattern cannot be longer than sequence
(endPoint - startIndex) < patLen) // start to end cannot be less than pattern
yield break;
for (int i = startIndex; i < endPoint; i++)
{
addedNew = false;
// add the first item if a match is found
if (eqComp(seq.ElementAt(i), pattern.ElementAt(0)))
{
if (patLen == 1)
yield return i;
found.Add(new MatchInfo(i, 1));
addedNew = true;
}
// check incomplete matches
for (int m = found.Count - 1; m >= 0; m--)
{
//skip the last item added
if (addedNew && m == found.Count - 1)
continue;
var match = found[m];
// check incomplete matches
if ((i - match.StartIndex < patLen) &&
eqComp(seq.ElementAt(i), pattern.ElementAt(match.MatchLength)))
{
match.MatchLength += 1;
found[m] = match;
// determine if a complete match has been found
if (match.MatchLength == patLen)
{
yield return match.StartIndex;
found.RemoveAt(m);
}
}
else
found.RemoveAt(m);
}
}
}
}
}