ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2012
17
6)
и отличаются в
k
–1-
й небесконечной позиции
7)
1 2
:
сгенерировать_кандидат( ,
)
cand
P
P P
=
8)
если
null
cand
P
≠
,
то
9)
1
2
1
2
:
P
id id
cand
P s P s
P
P
=
=
10)
если
|
|
min_ sup,
cand
P m
≥
то
11)
проверить_шаблон
(
, ,
min_ sup)
cand k
P L
12)
k
:
=
k
+ 1
13)
вернуть
:
, 1
.
k
Ρ L
k T
= ∪ ∀ ≤ ≤
Рассмотрим двухфазный подход «сверху вниз», реализованный в
алгоритме STPMine 2. Первая фаза алгоритма STPMine 2 замещает каж-
дое положение в последовательности
S
идентификатором кластера, к
которому он принадлежит, или пустым значением (например, *), если
не принадлежит никакому кластеру. Следовательно, изначальная после-
довательность
S
преобразуется в символьную последовательность
S`
.
Алгоритм, предложенный Ж. Ханом и Я. Йином [9], можно ис-
пользовать для быстрого поиска всех частых шаблонов вида
0 1
1
, , ...,
T
r r
r
−
,
где
i
r
—
кластер в
i
R
или *. Тем не менее неизвестно,
являются ли результаты алгоритма, основанного на последовательно-
стях, реальными шаблонами, поскольку значение каждой небеско-
нечной позиции могут и не формировать кластер. Шаблоны
P`
,
гене-
рируемые этим алгоритмом, называются псевдошаблонами, посколь-
ку они могут быть ошибочными.
Для нахождения реальных шаблонов необходимо применить
некоторые изменения к исходному алгоритму. Во время создания де-
рева максимальных подшаблонов каждый узел хранится с идентифи-
каторами сегментов, которые соответствуют псевдошаблону узла.
Таким образом, один идентификатор сегмента идет только в один
узел дерева. Последовательность
S
может быть слишком большой,
чтобы содержаться в памяти. Для решения этой проблемы во время
сканирования последовательности
S
для каждого сегмента
s
выпол-
няются следующие действия:
1)
добавление сегмента в дерево максимальных подшаблонов, в
результате увеличивается счетчик шаблона кандидата;
2)
вставка записи вида < `. , .
P id s id
> в файл
F
,
где
P`.id
—
идентификатор узла, соответствующего данному псевдошаблону;
s.id
—
идентификатор сегмента. В конце файл
F
сортируется по
P`.id
,
чтобы собрать вместе идентификаторы сегментов, удовлетворяющих
одному и тому же (максимальному) псевдошаблону. Для каждого
псевдошаблона с хотя бы одним сегментом вставляется указатель на
положение в файле первого идентификатора сегмента.
Для каждого псевдошаблона с хотя бы
(
min_sup)
m
α α
=
сегмен-
тами вызывается функция проверки шаблона, чтобы получить потен-
циально правильные шаблоны.
Псевдокод алгоритма выглядит следующим образом: