Аноним

Последовательное сравнение нескольких строк: различия между версиями

Материал из WEGA
м
Строка 61: Строка 61:




Алгоритм Ву и Манбера [ ] рассматривает блоки длины i. Блоки такой длинны хэшируются при помощи функции h в значения меньше maxvalue. Функция сдвига shift[h(B)] определяется как минимальное значение из \P'\— j и imin - I + 1 с B = p'_l+1 : : : pij для 1 < i < k и 1 < j < jPi j. Значение I варьируется в зависимости от минимальной длины строк в <math>\mathcal{P}</math> и размера алфавита. Значение maxvalue варьируется в зависимости от объема доступной памяти.
Алгоритм Ву и Манбера [11] рассматривает блоки длины <math>\ell</math>. Блоки такой длинны хэшируются при помощи функции h в значения меньше ''maxvalue''. Значение функции сдвига ''shift''[h(B)] определяется как минимальное значение из <math>|P^i| - j</math> и <math>\ell min - \ell + 1</math> с <math>B = p^i_{j - \ell + 1}...p^i_j</math> для <math>1 \le i \le k</math> и <math>1 \le j \le |P^i|</math>. Значение <math>\ell</math> варьируется в зависимости от минимальной длины строк в <math>\mathcal{P}</math> и размера алфавита. Значение ''maxvalue'' варьируется в зависимости от объема доступной памяти.




На этапе поиска этого алгоритма производится чтение блоков B длины i. Если shift[h(B)] > 0, то выполняется сдвиг на длину shift[h(B)]. В противном случае при shift[h(B)] = 0 шаблоны, оканчивающиеся на блок B, проверяются в тексте один за другим. Первым сканируется блок timjn-i+i  timjn. Данный метод встроен в команду agrep [10].
На этапе поиска этого алгоритма производится чтение блоков B длины <math>\ell</math>. Если shift[h(B)] > 0, то выполняется сдвиг на длину shift[h(B)]. В противном случае при shift[h(B)] = 0 шаблоны, оканчивающиеся на блок B, проверяются в тексте один за другим. Первым сканируется блок <math>t_{\ell mjn - \ell + 1} ... t_{\ell mjn}</math>. Данный метод встроен в команду agrep [10].


== Применение ==
== Применение ==
4551

правка