配列の中から配列を検索する

Question

お世話になります。
主題の通りなのですが、配列から配列を検索する手法、または直接的なメソッドを探しています。

現在はとりあえず以下のようなコードで実現していますが、よりよい方法があればぜひお教えください。
また、C#に限らず他の言語でも、「この言語なら一行で書ける」等ございましたらお聞かせください。

// 拡張メソッド定義
public static class IEnumerableExtensions
{
    public static int IndexOf<T>(this IEnumerable<T> source, IList<T> list)
    {
        if (list == null || list.Count == 0) return -1;

        int index = 0;
        foreach (T item in source)
        {
            if (item != null && item.Equals(list[0]))
            {
                // 最初の1要素が一致したら切り出して比較
                var part = source.Skip(index).Take(list.Count);
                if (part.SequenceEqual(list)) return index;
            }
            ++index;
        }
        return -1;
    }
}

var sentence = "Lorem ipsum dolor sit amet, consectetur adipisicing elit".Select(Convert.ToByte);
byte[] searchBytes = { 0x6f, 0x6c }; // 'o', 'l'
Console.WriteLine(sentence.IndexOf(searchBytes)); // ==> 13

Answer 1

不具合あるかもしれませんが

public static class IEnumerableExtensions
{
    public static IEnumerable<int> IndicesOf<T>(this IEnumerable<T> source, IList<T> target)
    {
        if (target == null || target.Count == 0)
            return Enumerable.Empty<int>();
        return source
            .Select((x, i) => new { index = i, value = source.Skip(i).Take(target.Count) })
            .Where(x => x.value.SequenceEqual(target))
            .Select(x => x.index);
    }

    public static int IndexOf<T>(this IEnumerable<T> source, IList<T> target)
    {
        return source.IndicesOf(target).DefaultIfEmpty(-1).First();
    }
}

var source = new int[] { 0, 1, 2, 3, 4, 0, 1, 2, 3, 4, };
var target = new int[] { 3, 4 };

foreach(var x in source.IndicesOf(target))
{
    Console.WriteLine(x);
}
//3
//8

Console.WriteLine(source.IndexOf(target));
//3

Comments

[htsign]

ありがとうございます。
私が書いたコードと本質的に同じでありながら、より洗練されていますね。
しかもIndicesOfで複数の結果が欲しいケースも考慮されていて素晴らしいです。

[len_souko]

調べて試してる間により汎用的でいいものが上がっていました
きもはLinqのSelectで第2引数にindexを取得することができるのでそれを利用してindexとほしいデータのセットを匿名クラスでまとめると以後のメソッドチェーンでいい感じに利用できるって処です
ちなみに自分は以下のサイトを参考にして使ってました
http://qiita.com/RyotaMurohoshi/items/118d4aa4d5be8c71c9ce

[htsign]

Selectメソッドの第二引数を使って匿名クラスを作るテクニックは時折役に立ちますよね。
便利なのですが、場合によっては逆に見にくくなることもあり難しいところです…。

Answer 2

力押しでいいならRubyだと何も考えずに一行でかけます。

sentence = "Lorem ipsum dolor sit amet, consectetur adipisicing elit".each_byte.to_a
searchBytes = [0x6f, 0x6c] # 'o', 'l'
puts sentence.each_cons(searchBytes.size).find_index(searchBytes) # ==> 13

最悪計算量はO(mn)ですし、最悪m個もArray生成するし、速度は度外視です。
(yubaさんが言っているKMP法やBM法を応用したやりかたはちょっと後から試そうかな)

Comments

[htsign]

ありがとうございます。
なるほど。each_consメソッドは初めて知りましたが、先頭を1ずつ進めながら指定の長さの配列を列挙するというものですね。そしてfind_indexで一致するまで進める、と。
確かに効率がいいとは言えないでしょうが、Rubyらしい面白い解法だと思いました。
効率度外視であれば流れるように書けるのはRubyのよいところですね。

Answer 3

C#よりもC++の方が得意なので、まずはC++だとこんな感じというのをお見せします。

#include <iostream>
#include <algorithm>
#include <vector>

int main()
{
	std::string sentenceText = "Lorem ipsum dolor sit amet, consectetur adipisicing elit";
	std::vector<uint8_t> sentence(sentenceText.begin(), sentenceText.end());
	std::vector<uint8_t> searchBytes = {0x6f, 0x6c};

	// 1行で書けます
	auto iter = std::search(sentence.begin(), sentence.end(), searchBytes.begin(), searchBytes.end());

	// 結果は13
	std::cout << iter - sentence.begin() << std::endl;
    return 0;
}

C#でこんな感じに書けるのかどうか、私も興味あります。

Comments

[htsign]

ありがとうございます。
C++は勉強し始めたばかりで理解が浅いですが、いただいたコードをググりながら咀嚼しました。vectorはものすごく便利ですね…。
型が制限されていないことも汎用性が高くて素晴らしいと思います。

Answer 4

文字列探索という課題になりますね。
質問文中でお示しの方法は、長さmの文字列中で長さnの文字列を探すのに最悪でほぼmn回の比較が発生し、効率的ではありません。

よく知られている（情報科学の講義で教わる）効率的な手法としてはKMP法、BM法というのがあります。その他に、BM法の改良型で実装しやすく効率も良い手法としてSunday法、またの名をクイックサーチと呼ぶものがあり、以前C#で書いたコードがあるので明日まだ質問が開いていたら載せます。

.NET Frameworkには文字列探索のメソッド用意されてないんですよね。

--- 追記

/// <summary>
/// byte配列の中からbyteパターンと一致する並びを検索する。
/// アルゴリズムはSunday法。
/// </summary>
/// <param name="pattern">探すパターン</param>
/// <param name="text">探索範囲となる配列</param>
/// <returns>発見した場合は開始位置、発見できなかった場合は-1</returns>
public static int SearchBytes(this byte[] text, byte[] pattern)
{
	int patternLen = pattern.Length, textLen = text.Length;

	// 移動量テーブルの作成
	int[] qs_table = new int[byte.MaxValue + 1];

	// デフォルト（パターン中に存在しないキャラクタが比較範囲の直後にあった）の場合、
	// 次の比較範囲はそのキャラクタの次。（＝比較範囲ずらし幅はパターン長＋１）
    for (int i = qs_table.Length; i-- > 0; ) qs_table[i] = patternLen + 1;

	// パターンに存在するキャラクタが比較範囲の直後にあった場合、
	// 次の比較範囲は、そのキャラクタとパターン中のキャラクタを一致させる位置に。
	for (int n = 0; n < patternLen; ++n) qs_table[pattern[n]] = patternLen - n;

	int pos;

	// 移動量テーブルを用いて、文章の末尾に達しない範囲で比較を繰り返す
	for (pos = 0; pos < textLen - patternLen; pos += qs_table[text[pos + patternLen]])
	{
		// 一致するか比較。一致したら、そのときの比較位置を返す。
        if (CompareBytes(text, pos, pattern, patternLen)) return pos;
	}

	// 文章の末尾がまだ未比較なら、そこも比較しておく
	if (pos == textLen - patternLen)
	{
		// 一致するか比較。一致したら、そのときの比較位置を返す。
        if (CompareBytes(text, pos, pattern, patternLen)) return pos;
	}

	// 一致する位置はなかった。
	return -1;
}

/// <summary>
/// 配列(pattern)が別の配列(text)に含まれているかを判定する。
/// 
/// pos + patternLen が text.Length より大きかったり
/// pos や patternLen が 0 未満だったり、
/// needdleLen が pattern.Length より大きかったりすると
/// ArrayOutOfBoundException が発生する。
/// </summary>
/// <param name="text">この配列の pos 番目からを pattern と比較する</param>
/// <param name="pos">text のどこから比較するか</param>
/// <param name="pattern">この配列全体が、text の pos 番目からと一致しているかを判定する</param>
/// <param name="patternLen">patternのうち一致判定する長さ</param>
/// <returns></returns>
static bool CompareBytes(byte[] text, int pos, byte[] pattern, int patternLen)
{
	for (int comparer = 0; comparer < patternLen; ++comparer)
	{
		if (text[comparer + pos] != pattern[comparer]) return false;
	}
	return true;
}

Comments

[htsign]

ありがとうございます。
本質問は、例として示したコードがたまたま文字列探索になっていただけでして、最終的な目標は型に制限されない配列の検索です。
ただ文字列から検索すればよいだけであれば
System.String#IndexOf(string value)
で事足りる話ですので…。

とはいえ私はアルゴリズム方面にはとても疎いので、KMP法・BM法等キーワードを出していただいただけでもとても参考になります。
時間を見つけつつ調べてみたいと思います。

[catsforepaw]

> 効率的ではありません。
実際問題として、論理的には効率的でも実装してみると期待したほど速くなかったというケースが意外と多いです。KMP法というのはよく知らないのですが、BM法はたぶん典型例かと。
検索対象と検索パターンのサイズが十分に長ければ威力を発揮しますが、質問にあるコード例のように検索パターンが短い場合は、オーバーヘッドがない分力任せの方が速くなる可能性が高いでしょう。比較してみるのも面白いかもしれません。
速さを追求するなら、用途や状況に応じてアルゴリズムを変える必要があります。

[yuba]

Sunday法で書いた配列内配列探索のコードを置きました。

これはByte配列についてのものになっていまして、文字ごとのジャンプ量というのをテーブル化しているのでこのままだと文字や整数型の配列についてしか探索できませんが、ジャンプ量テーブルをDictionayで実装すればIComparableなすべての型に応用できます。

＞ catsforepaw さん

短いテキストとパターンではナイーブアルゴリズムの方が効率的な場合があると言うのはおっしゃるとおりです。
この課題の性質の良いところは、ランタイムにテキストとパターンをもらった時点で長さを見てどちらか選択できるところなので、長いテキストが来たときだけテーブル生成方式を使うといったやり方ができます。

[catsforepaw]

コード拝見しました。基本はBM法ですね。
さて、このコード例（他でよく見かけるコード例も）はbyteなのでテーブルのサイズは256ですが、charの場合はサイズ65536になってしまいます。検索のたびに256KiBの領域を初期化することになるのですが。また、このエントリーでは型を特定していないので、もしintだったら？　連想配列使う？
Windowsは早い時期からネイティブ文字コードがUTF-16になっているので、同様の問題（疑問）がありまして、私としてはメモリ内で文字列検索をするのにBM法（亜種も含めて）は適さないと考えております。素直に標準の機能（クラスライブラリ等）を使うのが無難かと。

汎用のデータベースの検索エンジンを自前で実装するというのであれば役に立つのかもしれませんが。

[yuba]

intどころか、==だけが定義されたクラスかもしれません。ですのでコメントにもあります通り連想配列を使うのを提案しています。

標準クラスライブラリとおっしゃいますが、.NET Frameworkにはそういうメソッドがないので自前で書くしかないんですよ。

[catsforepaw]

単純な方法ならポインタ（インデックス）を進めるのにアセンブリ命令1個（0.5クロックぐらい）ですみますが、連想配列となると実装にもよるでしょうが、まずテーブル作成に時間がかかりますし、値を参照するにも数十クロックぐらい（あるいはそれ以上？）かかるのではないでしょうか。場合によっては連想配列も自分で作らないといけなくなるかもしれません。

ですので、こういうことはアルゴリズムの速さ（O(n)とか）だけを見ても無意味で、実際に実装して計測して比較しないと判らないのです。
で、実際の業務においてはそこまでやる価値があるのかどうかを見極める必要があり、大抵はそんな価値はないので、実装コストが最も低い（単純な）方法で実装することになります。

[htsign]

コードの追記ありがとうございます。
平日はあまり時間が取れないので休日にググって考え方の大枠でも読みながらゆっくり咀嚼していきたいと思います。

ところでIComparableを実装したすべての型で応用可能であると仰いますが、nullを含んだ配列にも使えるのでしょうか。
pattern[n]を添え字に取るqs_tableがあることを考えると、あるいはそれがNullableなTKeyを持つDictionaryを使うことにつながるのかとも推測しましたが…。

またcatsforepaw様が仰るように検索する配列の型が取りうる範囲の初期化を毎回行うということですが、連想配列を使うとこれが回避できるのでしょうか？
Dictionaryも要素数が増えればそれだけメモリを消費することには違いないのでは、と思ってしまいます。
近年は富豪的プログラミングが主流であるようにリソースの消費に対して気を払わなくてもよい、という感じでしょうか。

[yuba]

連想配列なら全領域をpatternLen+1で初期化する必要はなくなります。キーが見つからなければpatternLen+1が取れたことにすればいいので。null含みのパターン・テキストを扱うにはDictionaryには入りませんのでqs_table_nullなんて変数を1個用意してここに置いておけば解決です。

連想配列のサイズはパターン中の文字種類数だけですので、言うほど富豪的とはならないかと。

[htsign]

なるほど。そういう意図だったのですね。
そしてやはりnullは特別扱いですか。nullがある場合も処理を工夫すれば可能であることが分かりましたので、このアルゴリズムの利用価値は高そうだと感じました。
本質問の目的のひとつは「よりよい解決方法」を問いかけるものであったため、もう少し募集して特にこれ以上なければ、この回答をBAとさせていただきたいと思います。

[htsign]

本質問をクローズさせていただきました。
C++のcatsforepaw様やRubyのraccy様の回答も非常に興味深いものでしたが、今回はyuba様をBAとさせていただきました。
皆様ありがとうございました。

Answer 5

すみません、大勘違いしてしまいました...

---

var elm = sentence.Select((v, i) => new {val = (byte)v, idx = i}).FirstOrDefault(f => searchBytes.Contains(f.val));
var index = (elm == null) ? -1 : elm.idx;

Comments

[htsign]

ありがとうございます。
そうですね、このコードですとやりたいことと違う結果が返ってきますね…。
質問にご興味を持っていただいて感謝します。