Полезное для программистов:

Фриланс
Новости
Статьи
   
Рубрики:


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

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

Алгоритм поиска СДВИГ-И предложен в 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 достаточно слегка подкоректировать характеристические вектора для символов алфавита.

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






Просмотров: 3782

 

 

Новые статьи:


Популярные:
  1. Как сделать цикличным проигрывание MIDI-файла?
  2. Создание AVI файла из рисунков
  3. Как устройство "отключить в данной конфигурации"?
  4. Kто в данный момент присоединен через Сеть?
  5. Как узнать количество доступной памяти?
  6. Как реализовать в RichEdit разноцветный текст?
  7. Как скрыть свое приложение от ProcessViewer
  8. Как программно нажать/скрыть/показ кнопку "Start"?
  9. Модуль работы с ресурсами в PE файлах
10. Функции вызова диалоговых окон выбора
11. Проверка граматики средствами Word'а из Delphi.
12. Модуль для упрощенного вызова сообщений
13. Функции для записи и чтение своих данных в, ЕХЕ- файле
14. Рекурсивный просмотр директорий
15. Network Traffic Monitor
16. Разные модули
17. Универсальная функция для обращения к любым экспортируем функциям DLL
18. Библиотека от VladS
19. Протектор для UPX'а
20. Еще об ICQ, сообщения по контакт листу?
21. Использование открытых интерфейсов
22. Теория и практика использования RTTI
23. Работа с TApplication
24. Примеры использования Drag and Drop для различных визуальных компонентов
25. Что такое порт? Правила для работы с портами
26. Симфония на клавиатуре
27. Загрузка DLL
28. Исправление автоинкремента
29. Взаимодействие с чужими окнами
30. Проверить дубляжи в столбце


 

 

 
 
На главную