Шаблон в непрерывной последовательности данных

Question

Предположим, у меня есть список событий. Например A, D, T, H, U, A, B, F, H, ...,

Мне нужно найти частые паттерны, которые встречаются в полной последовательности. В этой задаче мы не можем использовать традиционные алгоритмы, такие как a priori или fp, потому что они требуют отдельных наборов элементов. И я не могу разбить этот поток на меньшие множества.

Любая идея, какой алгоритм будет работать для меня?

---

РЕДАКТИРОВАТЬ

Например, для последовательности A, D, T, H, U, A, D, T, H, T, H, U, A, H, T, H и с min_support = 2,

Частые образцы будут

Of length 1 --> [A, D, T, H, U]
Of length 2 --> [AD, DT, TH, HU, UA, HT]
Of length 3 --> [ADT, DTH, THU, HUA]
Of length 4 --> [ADTH, THUA]
No sequences of length 5 and further

Answer 1

Вы можете попробовать алгоритм aho-corasick с подстановочным знаком и / или только со всеми подстроками. Aho-corasick - это по сути конечный автомат, ему нужен словарь, но затем он очень быстро находит несколько шаблонов в строке поиска. Вы можете построить конечный автомат с помощью поиска и поиска в ширину. Вот хороший пример с анимацией: http://blog.ivank.net/aho-corasick-algorithm-in-as3.html. Таким образом, вам нужно в основном 2 шага: построить конечный автомат и найти строку.

Answer 2

Это особый вариант частого майнинга наборов, известный как последовательный майнинг паттернов.

Если вы посмотрите на эту тему, вы найдете буквально десятки алгоритмов.

Есть GSP, SPADE, PrefixSpan и многое другое.

Answer 3

Вот простой алгоритм (в JavaScript), который будет генерировать количество всех подстрок.

Держите количество вхождений подстроки в словаре. Переберите каждую возможную подстроку в потоке, и, если она уже есть в словаре, увеличьте ее, в противном случае добавьте ее со значением 1.

var stream = 'FOOBARFOO';
var substrings = {};
var minimumSubstringLength = 2;

for (var i = 1; i <= stream.length; i++) {
    for (var j = 0; j <= i - minimumSubstringLength; j++) {
        var substring = stream.substring(j, i);
        substrings[substring] ? substrings[substring]++ : substrings[substring] = 1;
    }
}

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

Answer 4

Вы можете сгенерировать все возможные подстроки, например:

A
AD
ADT
ADTH
...
D
DT
DTH
...

Теперь вопрос в том, имеет ли значение порядок элементов меньших подстрок.

Если нет, вы можете попробовать запустить стандартные алгоритмы анализа ассоциаций.

Если да, то порядок имеет значение во всей последовательности и ее подпоследовательностях, что делает это проблемой обработки сигналов или временных рядов. Но даже если порядок имеет значение, мы можем продолжить анализ таким образом со всеми подстроками. Мы можем попытаться сопоставить их, точное совпадение или нечеткое совпадение и тому подобное.