Поиск.

Поиск подпоследовательности в массиве (простой).

Функция осуществляет поиск первого вхождения массива W в массив T, в результате функция выдает номер первого элемента в массиве T начиная с которого встречается массив W. В случае, если массив W не встречается в массиве T результат функции равен -1.

Поиск осуществляется методом простого перебора, поэтому скорость работы функции не высока, но зато не занимается дополнительной памяти, и алгоритм прост в использовании. Наверх

Поиск подпоследовательности в массиве (алгоритм Бойера - Мура - Хорспула) .

Функция осуществляет поиск первого вхождения массива W(размера m) в массив T, в результате функция выдает номер первого элемента в массиве T начиная с которого встречается массив W. В случае, если массив W не встречается в массиве T результат функции равен -1.

Вначале функция создает BMH-таблицу содержимое, которой зависит от искомого массива, а именно если число i не содержится в подмассиве W[1..m-1], то BMHTable[i]=m, если число i содержится в подмассиве W[1..m-1], то берется максимальный номер j, т.ч. W[j]=i и тогда BMHTable[i]=m-j. В дальнейшем таблица используется для "ускорения" прохода массива в котором осуществляется поиск, следующим образом: 1. Положим j=m; 2. Пусть k=m; i=j. Пока W[k]=T[j] и k>0, уменьшаем на единицу k и i; 3. Если k=0, значит массив W входит в массив T начиная с номера i+1 и ВЫХОД. 4. Увеличим значение j на BMHTable[T[j]] (действительно T[j] в массиве W может быть на расстоянии не меньшем, чем BMHTable[T[j]] от конца). 5. Если j ≤ n переходим к шагу 2, иначе ВЫХОД и массив W не содержится в массиве T.

Алгоритм оптимизирован по сравнению с предыдущим для случая длинного искомого массива с не одинаковыми элементами. Интересно, что алгоритм работает намного медленее предыдущего например в случае когда массив T состоит из одних нулей, а массив W имеет следующий вид: 1000000. Наверх

Поиск подпоследовательности в массиве (алгоритм Кнута-Морриса-Пратта).

Рассмотрим вначале функцию F которая определена на последовательностях X[1],...,X[k] следующим образом: рассмотрим все начала последовательности X одновременно являющиеся ее концами, и выберем из них самое длинное. (Не считая, конечно, самой последовательности X). Тогда F(X)= длине такой подпоследовательности.

Работа алгоритма заключается в вычислении функции F на последовательности полученной слиянием массивов W и T с использованием разделителя в качестве которого должен выступать элемент не содержащийся ни в первом ни во втором массивах: W[1],...,W[m],@,T[1],...,T[j]; j=1..n. Тогда, если значение F при некотором j равно m (длине последовательности W), то массив W содержится в массиве T, иначе нет.

В первой части алгоритма заполняется массив L, при этом L[i]=F(W[1],...W[i]). На этом стоит остановится подробнее, т.к. методика заполнения массива L является ключевой в данном алгоритме. Итак тривиально L[1]=0 (поскольку F - длина подпоследовательности). Далее, допустим мы заполнили массив L для элементов с первого по i-ый. Теперь необходимо определить значение L[i+1]=F(W[1],...,W[i],W[i+1]). Для этого положим вначале len=L[i]. По построению массива L мы знаем, что W[i-len+1]=W[1] ,..., W[i]=W[len], и если W[i+1]=W[len+1], то L[i+1]=L[i]+1, допустим это не так, т.е. W[i+1]W[len+1], значит надо уменьшить длину начального подмассива который мы рассматриваем, положим len_=L[len], тогда получаем W[i-len+1]=W[1]=W[len-len_+1]=W[i-len_+1],...,W[i-len+len_]=W[len_]=W[len]=W[i], или выписав только важные для нас соотношения: W[1]=W[i-len_+1],...,W[len_]=W[i], и осталось снова сравнить W[i+1] и W[len_+1], если они снова не равны положим len=len_; len_=L[len], продолжая этот процесс мы на некотором шаге получим либо len=0 и тогда L[i+1]=0, если W[i+1]W[1] и L[i+1]=1, если W[i+1]=W[1], либо равенство W[i+1]=W[len_+1] и значит L[i]=len_+1.

После заполнения массива L осуществляется вычисление функции F на массиве W[1],...,W[m],@,T[1],...,T[j]; j=1..n, воспользовавшись алгоритмом похожим на тот, что использовался в предыдущем абзаце, при этом разделитель как таковой не используется.

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

Поиск подпоследовательности в массиве (алгоритм СДВИГ-И).

Алгоритм описан в статье В. Максимова в журнале "Монитор", №6 за 1995 год, ссылку на элестронную версию статьи в гостевой книге предложил Valera, мне статья очень понравилась, если Вы интересуетесь алгоритмами поиска советую прочитать. Ссылку на статью повторяю: Алгоритмы поиска, или Как искать неизвестно что.

Теперь подробнее об алгоритме.

Алгоритм поиска СДВИГ-И предложен в 1992 году Уди Манбер (Udi Manber) и Сан Ву (Sun Wu). Помимо того что алгоритм быстро работает и его просто программировать, он обладает уникальной особенностью: его можно легко, если не сказать элементарно, обобщить на случай нечеткого (приблизительного) поиска.

Допустим мы ищем вхождения последовательности vivid в массив vivi&dv&vivid. Будем искать все вхождения пяти шаблонов: v, vi, viv, vivi и vivid. Построим таблицу, которая бы отражала для каждой позиции текста, является ли эта позиция концом каждого из рассматриваемых пяти шаблонов. Для каждой позиции текста получим битовый 5-элементный вектор-массив, в котором k-й бит равен 1, если эта позиция соответствует концу вхождения k-го префикса. В итоге имеем таблицу из m строк и n столбцов:

		vivi&dv&vivid
	v	1010001010100
	i	0101000001010
	v	0010000000100
	i	0001000000010
	d	0000000000001

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

Мы будем предполагать, что длина массива W не превышает 32, тогда любой столбец таблицы можно представить в виде двойного слова (тип dword или LongInt). Для построения таблицы вначале для каждого символа алфавита построим характеристический вектор (у нас символы соответствуют произвольному целому 0-255), т.е. построим массив CVTab: array [0..255] of dword, при этом элемент CVTab[i] в двоичном представлении имеет единицы в тех позициях, в которых i-ый символ встречается в массиве W, т.е. для нашего примера CVTab для символа v будет иметь единицы в первой и третьей позиции (101), для символа i во второй и четвертой (1010), для тех символов, которые отсутствуют в шаблоне, характеристический вектор будет равен нулю.

Далее на j-ом шаге строим столбец таблицы по следующему алгоритму: вначале осуществляем сдвиг "вниз" предыдущего (j-1) столбца таблицы, заполняя первый бит 1, затем берем логическое И для полученного столбца с характеристическим вектором символа стоящего на j-ой позиции в последовательности T, в которой осуществляем поиск. Так например строя 3-й столбец в нашем примере: вначале осуществляем сдвиг для второго столбца (00010 - 00101), а затем берем логическое "И" с вектором соответствующем символу i (00101 AND 00101 = 00101).

Нетрудно изменить алгоритм для осуществления поиска подпоследовательностей с неопределенным значением некоторых символов, например в нашем примере, если надо найти вхождения любой подпоследовательности из 5 элементов, у которой на 2 и 4 позиции стоят символы i достаточно слегка подкоректировать характеристические вектора для символов алфавита.

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

Поиск подпоследовательности в массиве (алгоритм Бойера - Мура).

Это еще один пример как можно ускорить проход по массиву T, в алгоритме Бойера - Мура - Хорспула мы использовали для этого таблицу BMHTable, которая создавалась на основе массива W, в данном алгоритме кроме нее (BMHTable здесь называется bm_bc) используется еще таблица bm_gs на которой мы остановимся чуть подробнее. Эта таблица имеет размер на 1 больший размера массива W, т.е. m+1, и позволяет при проходе по массиву T использовать частичные совпадения для ускорения прохода. Рассмотрим пример массив T=CATCGCAGAGAGTATACAGTACG, а массив W=GCAGAGAG. Посмотрим на первое сравнение

	C A T C G C A G A G A G T A T A C A G T A C G
	          !    
	G C A G A G A G

В случае алгоритма БМХ мы бы должны были сдвинуться только на 2 позиции (BMHTable[G]=2), но очевидно что этот сдвиг не достаточен поскольку мы вновь получим CG. Используя собранную заранее в таблицу bm_gs информацию о массиве W мы в данном алгоритме будем сдвигаться на 4 позиции тем самым увеличив скорость прохода. Таблица bm_gs для данного примера будет следующей:

	G C A G A G A G
	7 7 7 7 2 7 4 7 1

Получив не совпадение на 6 символе, мы выбираем величину сдвига равной bm_gs[7]=4. bm_gs[1] - используется в случае когда найдено полное совпадение, для сдвига на позицию с которой надо продолжить поиск. Использование двух таблиц для определения величины сдвига (bm_bc и bm_gs) позволяет брать максимум из величин.

Алгоритм построения вспомогательных таблиц проще всего посмотреть по блок-схеме.

Более подробное описание алгоритма есть в разделе "Поиск" на сайте algolist.da.ru, там лежит кусочный перевод статьи "Exact string matching algorithms". Наверх