Как правильно выполнить модульное тестирование алгоритма дерева суффиксов?

Question

Я работаю над реализацией алгоритма построения дерева линейных суффиксов Укконена и планирую реализовать улучшения, предложенные, например, Курц и Н. Дж. Ларссон (например, краевые ссылки вместо суффиксных ссылок).

Во время тестирования я испытывал смешанные зеленые и красные огни, основанные на конкретных тестируемых мной строках, и имел аналогичный опыт с несколькими алгоритмами, которые я нашел в Интернете. Что заставило меня задуматься:

• Существуют ли какие-либо известные, специально построенные (предпочтительно простые / короткие) строки для дерева суффиксов модульного тестирования, чтобы гарантировать, что алгоритм работает точно во всех сценариях ветвления?

• Кроме того, есть ли хорошие методы, чтобы отделить тестирование алгоритма построения дерева от тестирования алгоритма обхода / поиска?

Я знаю, что на этот вопрос нет единственного правильного ответа, но я думаю, что он может послужить хорошим ориентиром для людей, работающих над подобными алгоритмами.

Мой текущий подход к модульному тестированию довольно примитивен (C # с NUnit):

[TestCase]
public void Contains_Simple_ShouldReturnTrue()
{
    var s = "bananasbanananananananananabananas";
    var st = SuffixTree.Build(s);

    var t1 = s.Substring(0, 10);
    Assert.IsTrue(st.Contains(t1));
}

// ... Other simple test cases


[TestCase]
// This test fails, but it's not particularly helpful for bugfixing
public void Contains_DynamicBarrage_OnLongString_ShouldReturnTrue()
{
    const int   CYCLES = 200,
                MAXLEN = 200;

    var s = "olbafuynhfcxzqhnebecxjrfwfttw"; // Shortened for sanity
    var st = SuffixTree.Build(s);
    var r = new Random();

    for (int i = 0; i < CYCLES; i++)
    {
        var pos = r.Next(0, s.Length - 2);
        var len = r.Next(1, Math.Min(s.Length - pos, MAXLEN));

        Assert.IsTrue(st.Contains(s.Substring(pos, len)));
    }
}