Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Алгоритмы > Поиск закономерностей в последовательности

Автор: MastEdm 2.5.2010, 13:23

Добрый день.

Есть последовательность символов. В ней нужно попытаться найти закономерности. Интересуют закономерности типа циклов. В простейшем случае точные циклы (то есть точное совпадение символов). Посложнее: "циклы" вида

Код


f(x, a) = f(y, b) = ... = f(z, c),

где x, y, z - подпоследовательности исходной последовательности; a, b, c - некоторые произвольные числа; f - некоторая функция. В случае с точным циклом f(x, a) = x

Подскажите, в каком направлении копать?

Автор: esperanto 3.5.2010, 21:04

Наверное если вы спросите на более понятном языке, вам смогут помочь

Автор: MastEdm 3.5.2010, 21:44

Приведу пример:

Пусть есть последовательность: 'sdfaqwertyqwertyqwertydsdf'. Алгоритм должен найти в ней повторенную трижды подпоследовательность 'qwerty'. Это случай для "точного цикла" (в кавычках, потому что не знаю как это правильно называется)

А для такой последовательности: "zxabcaabcbabcdabceqw" - циклом будет подпоследовательность "abc*", где * - произвольный символ.

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

Автор: _Y_ 3.5.2010, 23:09

Может стоит покопать в направлении биоинформатики? Например применяется такой способ. Последовательности расставляются в виде заголовков по вертикали и горизонтали, отмечаются одинаковые символы.

Вот что получается в первом варианте:

Код


 sdfaqwertyqwertyqwertydsdf
sX----------------------X--
d-X--------------------X-X-
f--X----------------------X
a---X----------------------
q----X-----X-----X---------
w-----X-----X-----X--------
e------X-----X-----X-------
r-------X-----X-----X------
t--------X-----X-----X-----
y---------X-----X-----X----
q----X-----X-----X---------
w-----X-----X-----X--------
e------X-----X-----X-------
r-------X-----X-----X------
t--------X-----X-----X-----
y---------X-----X-----X----
q----X-----X-----X---------
w-----X-----X-----X--------
e------X-----X-----X-------
r-------X-----X-----X------
t--------X-----X-----X-----
y---------X-----X-----X----
d-X--------------------X-X-
sX----------------------X--
d-X--------------------X-X-
f--X----------------------X

Во втором варианте

Код


 zxabcaabcbabcdabceqw
zX-------------------
x-X------------------
a--X--XX---X---X-----
b---X---X-X-X---X----
c----X---X---X---X---
a--X--XX---X---X-----
a--X--XX---X---X-----
b---X---X-X-X---X----
c----X---X---X---X---
b---X---X-X-X---X----
a--X--XX---X---X-----
b---X---X-X-X---X----
c----X---X---X---X---
d-------------X------
a--X--XX---X---X-----
b---X---X-X-X---X----
c----X---X---X---X---
e-----------------X--
q------------------X-
w-------------------X

Потом смотришь последовательности из крестиков по диагонали. Где последовательность достаточной длины и с малым количеством пропусков, там и сходство.

Вот простейший Java код, который это делает:

Код


public class Temp {

    public static void main(String args[]) {            
        
        String stringIn = "zxabcaabcbabcdabceqw";
        String[] dataArray = stringIn.split("");
        
        String[][] results = new String[dataArray.length][dataArray.length];
        
        for(int r = 1; r < dataArray.length; r++){
            for(int c = 1; c < dataArray.length; c++){
                if(dataArray[r].equals(dataArray[c])){
                    results[r][c] = "X";
                } else {
                    results[r][c] = "-";
                }            
            }
        }
        
        System.out.println(" " + stringIn);
        for(int r = 1; r < dataArray.length; r++){
            System.out.print(dataArray[r]);
            for(int c = 1; c < dataArray.length; c++){
                System.out.print(results[r][c]);        
            }
            System.out.println();
        }
    }
}

Автор: MastEdm 4.5.2010, 09:02

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

Автор: _Y_ 4.5.2010, 10:17

Цитата(MastEdm @ 4.5.2010, 09:02)

но по-любому наверное можно соптимизировать

Наверное. Это же алгоритм в основном для визуализации. Что знал - доложил smile