Есть текст, длинной порядка 10^8 — 10^9 букв. Есть некоторая строка длинной порядка 3 букв. Есть гипотеза о том, что эта строка распределена в тексте не случайно, а образует кластеры.

Посему есть 2 задачи:
1) подтвердить или опровергнуть гипотезу о наличии кластеров,
2) найти локализацию всех кластеров данной строки в тексте.

С помощью, каких методов можно решить данные задачи?

Здравствуйте, serjjj, Вы писали:

S>Есть текст, длинной порядка 10^8 — 10^9 букв. Есть некоторая строка длинной порядка 3 букв. Есть гипотеза о том, что эта строка распределена в тексте не случайно, а образует кластеры.

S>Посему есть 2 задачи:
S>1) подтвердить или опровергнуть гипотезу о наличии кластеров,
S>2) найти локализацию всех кластеров данной строки в тексте.

Уточни что у тебя буква ? И порядка 3х букв это 3-4 буквы? Эту строку надо искать один раз или их таких строк целый набор?
И еще кластером ты называешь скопление твоей последовательности скажем >k штук в области <M символов или что-то другое?

Если у тебя алфавит ASCII 8bit на букву. ищем 4 байта подряд. искать надо всего 1 раз и кластер это k раз в отрезке M букв то:
пробигам по всему тексту последовательно и сравниваем *(int32*)data==*(int32*)sample и
паралельно циклично заполняем битовый вектор длинной M аккуратно выставляя 1 если совпало
и 0 если нет. добавляем в статистику этот бит и отнимаем тот что на M шагов был раньше.
Если кол-во бит больше k записывает что гипотиза выполнилась, да и каждое совпадение заносим
в список результатов.
за 1 проход находим то что хотели ( если хотели именно этого )

Поиск ведется одной стоки. Длинна строки 3 буквы, но это не суть важно. Кластер это скопление моей последовательности на неком участке. Критерий кластера: частота встречаемости последовательности на этом участке (кластере) >=p. При этом длина участка не является фиксированной (имеется только ограничение на минимальную длину). Таких кластеров в тексте может встретиться сколько угодно много, нужно найти координаты начала и конца каждого из них.

Например, средняя частота встречаемости строки в тексте 0.04, мне нужно найти все участки (кластеры) длинной не менее 200 букв, в которых частота встречаемости строки составляет не менее 0.1.

Проблема с доказательством гипотезы заключается в том, что в случайно сгенерированном тексте, чисто случайно будет некоторое количество таких кластеров. По сему нужно как-то доказать, что найденные кластеры в моем тексте не являются случайными для определенного уровня значимости (например для уровня значимости 0.99).

P.S.
p = количество вхождений строки / длина участка для поиска;
средняя частота встречаемости строки в тексте = количество вхождений строки / длинна текста

Здравствуйте, serjjj, Вы писали:

[]

По-моему, решается в лоб: ищешь все вхождения и запоминаешь их (включая доп. информацию), затем анализируешь полученные отрезки.

Здравствуйте, serjjj, Вы писали:

S>Поиск ведется одной стоки. Длинна строки 3 буквы, но это не суть важно. Кластер это скопление моей последовательности на неком участке. Критерий кластера: частота встречаемости последовательности на этом участке (кластере) >=p. При этом длина участка не является фиксированной (имеется только ограничение на минимальную длину). Таких кластеров в тексте может встретиться сколько угодно много, нужно найти координаты начала и конца каждого из них.
S>Например, средняя частота встречаемости строки в тексте 0.04, мне нужно найти все участки (кластеры) длинной не менее 200 букв, в которых частота встречаемости строки составляет не менее 0.1.
Тогда делаешь один проход выписываешь все вхождения твой ABC в массив int *x ( или vector<int> x )
// Для случайной строки ~1e9 из букв должно получиться порядка ~1e4 шт
после чего у тебя получается массив с координатами твоей строки в тексте причем элементы монотонно возрастают.
тогда можно выписать твои кластеры примерно так:

typedef float flt;
struct FindClusters {
    flt p0; int n,*x,M,L;
    FindClusters(int *x,int n) : x(x),n(n) { L=3; M=200; p0=0.04; }
    FindClusters& analyze() {
        int i=0, j=1;
        while ( j<n && (x[j]-x[i]+L)<M ) j++;
        for(;;) {
            while ( j<n && (j-i+1)<p0*(x[j]-x[i]+L) ) {
                j++; while ( (x[j]-x[i+1]+L)>M ) i++;
            }
            if (j>=n) break;
            output(x[i],x[j]+L,j-i+1); j++; 
        }
        return *this;
    }
    virtual void output(int h,int t,int k) { // h-head, t-tail, k-кол-во
        flt p=(flt)k/(t-h); // плотность на участке
        printf(": [%d,%d) p=%.3f\n",h,t,p);
    }
    FindClusters& setP0(flt P0) { p0=P0; return *this; }
    FindClusters& setM(int M) { this->M=M; return *this; }
};

Типа функцию FindClusters можно доопределить по мере необходимости. Перегрузив output.

int main(int argc, const char *argv[]) { 
    int x[]={1,20,500,550,570,700,900 }; int n=sizeof(x)/sizeof(*x);    
    FindClusters(x,n).setP0(0.01).analyze(); // вызывать можно примерно так
    return 0;
}

S>Проблема с доказательством гипотезы заключается в том, что в случайно сгенерированном тексте, чисто случайно будет некоторое количество таких кластеров. По сему нужно как-то доказать, что найденные кластеры в моем тексте не являются случайными для определенного уровня значимости (например для уровня значимости 0.99).
Вот всё таки интересно какой у тебя критерий для проверки гипотезы ? как ты уровень значимости считать будеш?
??? а почему бы просто не разбить твою строку на M участков и не посчитать моменты на них плотность, среднее, дисперсию и т.п. и анализировать их распределение если оно примерно одинаковое, то генерили случайно тем более в твоём случае все выборки достаточно большие.

Здравствуйте, serjjj, Вы писали:

S>Поиск ведется одной стоки. Длинна строки 3 буквы, но это не суть важно. Кластер это скопление моей последовательности на неком участке. Критерий кластера: частота встречаемости последовательности на этом участке (кластере) >=p. При этом длина участка не является фиксированной (имеется только ограничение на минимальную длину). Таких кластеров в тексте может встретиться сколько угодно много, нужно найти координаты начала и конца каждого из них.

S>Например, средняя частота встречаемости строки в тексте 0.04, мне нужно найти все участки (кластеры) длинной не менее 200 букв, в которых частота встречаемости строки составляет не менее 0.1.

как я понимаю, надо посчитать сначала минимальное кол-во вхождений в кластер для частоты и длины, т.е. принимая

частота = число_вхождений / длина кластера

получим число_вхождений_минимум = 200 * 0,1 = 20

делаем буфер смещений, который последовательно заполняем при очередном вхождении. как только буфер заполнен, смотри разность между первым и последним смещениями — если разность <= длина_кластера — длина строки + 1 = (200-3+1)=198 — т.е. все внутри одного кластера, радостно сообщаем усеру
попутно записываем пару — (смещение начала, длина, число вхождений) в список кластеров.

далее сдвигаем буфер. после чего продолжаем поиск, при очередном вхождении выполняем перечисленные выше действия. при этом, если очередное вхождение принадлежит предыдущему кластеру (т.е. смещение от начала предыдущего кластера меньше длины кластера) — увеличиваем соответственно длину этого кластера и число вхождений. далее сдвигаем буфер и снова по кругу.

довольно сумбурно, но идея, по-моему, ясна.

светлая мысль — не сдвигать буфер а использовать циклический.

S>Проблема с доказательством гипотезы заключается в том, что в случайно сгенерированном тексте, чисто случайно будет некоторое количество таких кластеров. По сему нужно как-то доказать, что найденные кластеры в моем тексте не являются случайными для определенного уровня значимости (например для уровня значимости 0.99).

S>P.S.
S>p = количество вхождений строки / длина участка для поиска;
S>средняя частота встречаемости строки в тексте = количество вхождений строки / длинна текста

далее по списку кластеров посмотреть какое распределение — увы, институтскую статистику подзабыл, но то что это делали — помню совершенно точно.

Здравствуйте, Leonidze, Вы писали:

L>делаем буфер смещений, который последовательно заполняем при очередном вхождении. как только буфер заполнен, смотри разность между первым и последним смещениями — если разность <= длина_кластера — длина строки + 1 = (200-3+1)=198 — т.е. все внутри одного кластера, радостно сообщаем усеру
L>попутно записываем пару — (смещение начала, длина, число вхождений) в список кластеров.

число элементов буфера равно минимальному кол-ву вхождений в кластер

Здравствуйте, serjjj, Вы писали:

S>Есть текст, длинной порядка 10^8 — 10^9 букв. Есть некоторая строка длинной порядка 3 букв. Есть гипотеза о том, что эта строка распределена в тексте не случайно, а образует кластеры.

S>Посему есть 2 задачи:
S>1) подтвердить или опровергнуть гипотезу о наличии кластеров,
S>2) найти локализацию всех кластеров данной строки в тексте.

S>С помощью, каких методов можно решить данные задачи?

Сильно напоминает аналогичную задачу из биоинформатики — CG islands. Там тоже необходимо искать кластеры (islands) пар CG. Решаеться при помощи Hidden Markov Model. Так же можно поискать что-то вроде "hidden markov model + dishonest casino".

Оффтоп конечно, но...

Народ, меньше "Игры Разума" смотреть надо.

Здравствуйте, Eternal, Вы писали:

E>Сильно напоминает аналогичную задачу из биоинформатики — CG islands. Там тоже необходимо искать кластеры (islands) пар CG. Решаеться при помощи Hidden Markov Model. Так же можно поискать что-то вроде "hidden markov model + dishonest casino".

О! А это уже интересно! Что можно почитать про эти методы? Применительно к cg-островкам? Реализации на C/C++, Java?

P.S. Вы биоинформатик?

Здравствуйте, serjjj, Вы писали:

S>Здравствуйте, Eternal, Вы писали:

E>>Сильно напоминает аналогичную задачу из биоинформатики — CG islands. Там тоже необходимо искать кластеры (islands) пар CG. Решаеться при помощи Hidden Markov Model. Так же можно поискать что-то вроде "hidden markov model + dishonest casino".

S>О! А это уже интересно! Что можно почитать про эти методы? Применительно к cg-островкам? Реализации на C/C++, Java?

S>P.S. Вы биоинформатик?

Я не биоинформатик. Просто в университете был такой вводный курс.

К сожалению, информации по этой теме в сети не много. Можно искать по ключевым словам из поста выше (естественно, всё на английском).

Хотите пример?
Допустим есть алфавит ABCDEFG. Ищем кластеры последовательностей BC. Есть 3 стейта: 1, 2, 3. Нас интересуют только 2 и 3.

ABCDEFGABCBCABCGGBCBCAABGEFABAABCBCGDBCBFBCADEFBCGGA
1111111123233232323231111111111232323232323111111111

Как видно, "одинокие" BC вначале и в конце проигнорированы.

Вот исходник (Python). Вам придётся подбирать свои коэффициенты переходов и выводов (transition and emission propability) конкретно для вашей задачи.
http://www.everfall.com/paste/id.php?nn7oce9a910q

Здравствуйте, Eternal, Вы писали:

> ...

Спасибо! Буду разбираться.