Фактически надо предварительно вычислить не сам массив граней, а его более слабый вариант. Обозначим через j позицию в паттерне р первого несовпадения. Тогда префикс паттерна р, который не требует проверки при следующем сравнении, — это наибольшая грань подстроки p[l..j — 1]. Поэтому следующей буквой для сравнения будет p[β[j — 1] + 1], где β[j — 1] — длина наибольшей грани подстроки p[1..j - 1], при этом, конечно, β[j - 1] < j - 1. Следовательно, в действительности для всех j принадлежащих 2..m + 1 надо вычислить β'[j] = β[j - 1] + 1, положив при этом β2'[1] =0. Отметим, что для
j >= 2 β[j — 1] + 1 < (j — 1) + 1 = j,
поэтому β'[j] < j. Если j = 1, тогда сравнивать нечего, и в этом случае необходимо изменить значение i, т. е. сдвинуть паттерн вдоль строки x. После этих пояснений мы можем записать алгоритм. Заметим, что оператор присвоения, выполняемый в результате несовпадения p[j] и x[i],соответствует сдвигу вправо вдоль строки х паттерна р на j - β'[j] позиций.
Алгоритм Кнута-Морриса-Пратта нахождение всех вхождений паттерна р в строку x:
i ← 1; j ← 1
while i ≤ n — m + j do
(i, j) ← match(i, j, m)
if j = m + 1 then output i - m
if j = 1 then i ← j + 1
else j ← β'[j]
Отметим, что в этом алгоритме процедура match (сравнить) выполняет сравнение "буква забуквой" слева направо начиная с заданной позиции j.
Алгоритм Кнута-Морриса-Пратта корректно вычисляет все вхождения заданного непустого паттерна р в заданную строку х.
3. Параллельные алгоритмы обработки больших данных имитационного моделирования
Пусть M – дискретная событийно-ориентированная модель некоторой системы, функционирующей во времени, Sim – симулятор (алгоритм, выполняющий сеанс имитационного моделирования), BD = Sim(M) – данные большого объема, порождаемые симулятором. Элементы данных могут быть представлены в виде (Statei, si), и естественным образом упорядочены по не убыванию параметра s – системного времени модели. Здесь si – момент системного времени, в который произошло i-е событие в модели, Statei – состояние системы в этот момент. Таким образом, BD может рассматриваться как последовательность (протокол) длины n, со значениями n для реальных моделей более 107.
Задача анализа результатов сеанса имитации – это задача разработки алгоритмов, исходными данными для которых являются длинные последовательности. В этих условиях даже алгоритмы квадратичной сложности требуют большого времени исполнения, не говоря уже об алгоритмах переборного характера. Существенное ускорение в реализации может быть достигнуто при использовании вычислительных систем с массовым параллелизмом или больших распределенных систем. [2]
В настоящей работе мы рассмотрим параллельные алгоритмы для вычисления расстояний Хемминга между последовательностями, а также поиск частного паттерна внутри длинной последовательности.
Зачастую имитационное моделирование применяется для сравнения двух систем. Такое сравнение можно провести через сравнение двух последовательностей BD1 и BD2 , порождаемых этими системами. Совпадение последовательностей, BD1 = BD2 , говорит о тождестве систем (в пределах, позволяющих их различать при данном исследовании). Различие может проявляться при отдельных событиях и тогда мерой различия систем можно считать различие (расстояние) между последовательностями. В литературе рассматриваются различные метрики. Мы рассмотрим параллельные алгоритмы вычисления расстояний Хемминга и алгоритм нахождения частного паттерна.
Вычисление расстояния Хемминга представляет собой «жесткий» вариант сравнения протоколов моделируемых систем: учитывается только совпадение или отличие в одинаковых позициях. При этом интуитивно подобные, но с разными начальными условиями, протоколы будут давать значительное расстояние Хемминга, увеличивающееся с длиной протокола. Хотя интуитивно ясно, что в таком случае расстояние не должно увеличиваться с увеличением длины протокола. Этих недостатков лишено расстояние Левенштейна, представляющее собой более гибкий вариант сравнения протоколов, к тому же не требующий равенства их длин. [3]
3.1 Алгоритм поиска расстояния Хемминга
Расстояния Хемминга может быть вычислено с использованием параллельно работающих p процессоров следующим образом:
class Mapper
method Map(pronum n, protocol s)
Emit(pronum n, protocol s)
class Reducer
method Reduce(pronum n, [s1 , s2])
D ← HammingDistance(s1 , s2)
Emit(1, D)
method Reduce2(1, [d1, d2, d3, … ])
Distance ← 0
for all d in [d1, d2, ....] do
Distance ← Distance + d
Emit('Hamming distance:', Distance)
Здесь HammingDistance(s1 , s2) — реализация последовательного поиска расстояния Хэмминга между протоколами s1 и s2.
Реализация данного алгоритма в таком виде позволяет нам воспользоваться преимуществами MapReduce. Поиск расстояния между двумя длинными протоколами разбивается на 3 этапа. Первый этап: функция map считывая построчно оба протокола, помечает их номерами, по которому они группируются для передачи в Reduce. Второй этап: поиск расстояний между короткими подпоследовательностями, который может выполняться параллельно на нескольких машинах. Третий этап: расчет суммы найденных расстояний.
Асимптотическая оценка сложности этого алгоритма складывается из суммы оценок выполнения всех Map и Reduce заданий, и равна
, (1)
где 
- количество параллельно выполняющихся map функций, 
- количество параллельно выполняющихся reduce функций, 
– длина протоколов, 
– длина считываемой map последовательности, настраиваемый параметр.
3.2 Алгоритм поиска частного паттерна.
Рассмотрим задачу поиска частного паттерна в протоколе, в контексте больших данных. Ниже приведён возможный алгоритм реализации данной задачи в терминах MapReduce.
class Mapper
method Map (pronum i, protocol S)
Match ← FindPattern(S, Pattern)
RequestPronum ← i + 1;
RequestPatternpose ← Match. PatternPose + Prolength — Match. Propose
Match. status ← Is;
Emit(i:Patternpose, Match)
Match. status ← Request;
Emit(RequestPronum:RequestPatternpose, Match)
class Reducer
method Reduce (Pronum:Patternpose, [Match1, Match2])
if (Match1 and Match2)
if ( Match1.Begin and not Match2.End) {
RequestPronum ← Match2.Pronum + 1
RequestPatternpose ← Match2.PatternPose + Prolength — Match2.Propose
Match1.status ← Is;
Emit(Match1.Propose:Match1.Patternpose, Match1)
Match1.status ← Request;
Emit(RequesrPronum:RequestPatternpose, Match1)
}
if (Match1.Begin and Match2.End) {
Match1.Complited ← TRUE
Match1.LastPronum ← Match2.Pronum
Emit(Match1.Propose, Match1)
}
if (not Match1.Begin and Match2.End) {
RequestPronum ← ProNum + 1
RequestPatternpose ← PatternPose + Prolength — Match2.Propose
Match1.status ← Is;
Emit(Match1.Propose + Match1.PatternPose, Match1)
Match1.status ← Is;
Emit(RequestPronum + RequestPatternPose, Match1)
Match2.status ← Is;
|
Из за большого объема этот материал размещен на нескольких страницах:
1 2 3 4 5 6 7 |
