Максимизация числа различных подслов
Наверно, наиболее очевидный способ интерпретации «как можно более разнообразного поведения» слова — это наличие у него как можно большего числа различных подслов.
В слове длины N имеется всего
N + (N-1) + (N-2) + … + 2 + 1 = N(N+1)/2 (*)
подслов (слагаемые соответствуют подсловам длины 1, 2 и т.д.). Можно попытаться максимизировать количество разных подслов, сделав все подслова какой-то длины k различными. При этом все подслова большей длины тоже автоматически будут различны, т.е. мы получим как минимум (N-k+1)(N-k+2)/2 разных подслов длины k и больше. Значение k при этом можно выбрать так, чтобы максимизировать полученное выражение при фиксированном N, т.е. как можно меньше.
При этом имеется всего mk разных m-слов длины k, а если они все реализуются как подслова одного слова, длина этого слова должна быть не меньше mk+k-1. Предположим, что существуют такие «наиболее плотные» слова, что все их подслова длины k различны и в то же время включают в себя все возможные m-слова длины k, и они нам известны. Тогда для заданного N можно найти минимальное k, такое, что N ? mk+k-1, т.е. m(k-1)+(k-1)-1 < N ? mk+k-1, и в качестве искомого слова взять начало длины N соответствующего «наиболее плотного» слова. Это гарантирует различие всех подслов длины k в нем.
Для того, чтобы еще увеличить количество разных подслов в нашем слове, можно попытаться найти «наиболее плотное» слово для (k-1), которое продолжается в «наиболее плотное» слово для k. Взяв начало этого последнего мы получим наилучший результат — в полученном слове длины N все подслова минимально возможной длины k различны, и в то же время в нем в качестве подслов содержатся все возможные слова длины (k-1) и, соответственно, меньшие — все слагаемые в формуле (*) имеют максимальные возможные значения.
Осталось выяснить два момента.
- Существуют ли «наиболее плотные» слова для всех m и k, и если это так, можно ли их продолжать до «наиболее плотных» слов для m и (k+1)? Есть ли достаточно эффективные алгоритмы для построения таких слов?
- Какой тестовой гипотезе, т.е.
какому допущению относительно свойств тестируемой системы, соответствует выбранное понимание «наиболее разнообразного» поведения слова? Для какого рода систем этот подход дает действительно оптимальное покрытие различных возможных ситуаций?
