?
О количестве перекрытий слов в паттернах
Изучалась задача оценки количества перекрытий в паттерне – наборе слов в некотором алфавите A, имеющих одну и ту же длину m. Получены теоретические и экспериментальные оценки количества перекрытий для паттернов двух видов. Первый из них – это случайные паттерны, для которых верна равномерная вероятностная модель: все буквы в алфавите A и, соответственно, все слова длины m равновероятны. Доказано, что среднее количество перекрытий P для случайных паттернов, состоящих из n слов длины m, линейно зависит от размера паттерна n и не зависит от длины слов в паттерне. В проведенных компьютерных экспериментах отношение P/n менялось в пределах от 0.33 до 1.06; теоретические оценки этого отношения для тех же паттернов не превосходят 1.67. Вторым видом паттернов, изученных в статье, являются паттерны, заданные матрицами позиционных весов из базы данных HOCOMOCO и пороговыми весами. Для этих паттернов отношение количества перекрытий к количеству слов в экспериментах менялось от 0.004 до 1, для более половины паттернов это отношение меньше 0.1.