Главная » Java, Структуры данных и алгоритмы » Алгоритмы шаблонного сопоставления

0

В классической задаче сравнения с шаблоном (pattern matching) или шаблонного сопоставления строк имеется текстовая строка Т длиной п и шаблонная строка Р длиной m и определяется, является ли Р подстрокой Т. Понятие «сравнения» состоит в том, что существует подстрока строки Т, начинающаяся с индекса / и совпадающая с Р посимвольно, так что T[i] = Р[0], T[i+ 1] = Р[ 1], T[i + m- 1] = P[m- 1]. То есть Р— Г[/…/ + m – 1]. Следовательно, результатом алгоритма шаблонного согласования будет либо указание на то, что в Гнет Р, либо целое число, обозначающее индекс начала подстроки Р в Т. Это точное описание работы метода indexOf Java-ioiacca String. Можно также определить все индексы, с которых начинается совпадение подстроки из Т со строкой Р.

Чтобы сделать понятие символьной строки более универсальным, не ограничимся использованием только символов из хорошо известной таблицы типа ASCII или Unicode. Вместо этого используем символ S для обозначения множества символов, или алфавит, из которого могут быть взяты символы строк Т и Р. Алфавит I может, естественно, оказаться подмножеством ASCII или Unicode, но может быть и более общим, а в некоторых случаях и ничем не ограниченным множеством, например, положительных целых чисел. Но поскольку большинство алгоритмов обработки текста испоАьзуется в приложениях, применяющих указанные системы символов, исходим из того, что размерность алфавита Е, обозначаемая И, является постоянным и конечным значением.

В этом разделе представлены три алгоритма сопоставления (по мере усложнения).

Источник: Гудрич М.Т. Г93 Структуры данных и алгоритмы в Java / М.Т. Гудрич, Р. Тамассия; Пер. с англ. A.M. Чернухо. — Мн.: Новое знание, 2003. — 671 е.: ил.

По теме:

  • Комментарии