Маска, я тебя знаю

Для чего нужна маска? Маска позволяет частично скрыть индивидуальность. Разные индивиды могут скрываться под маской. На карнавале, где носят маски, можно беззаботно веселиться, оставаясь неузнанным.

Маски широко используются в программировании, хотя роль маски здесь несколько иная. Маска позволяет из множества индивидуумов отобрать некоторых, тех, кто соответствует заданному образцу, называемому также шаблоном, паттерном (от английского pattern) или маской.

Как строятся маски? Пусть задан некоторый алфавит Т. Как построить маску, позволяющую из множества слов в алфавите Т отобрать слова, соответствующие маске? Маска строится из символов алфавита Т и специальных символов маски. Если маска построена только из символов алфавита Т, то такая маска ничего не маскирует. Ей соответствует единственное слово в алфавите Т, совпадающее с маской. Если разыскивается машина с известным номером АВ2345, то такая машина единственна, поскольку все номера уникальны. Мощь маски определяется ее специальными символами. Рассмотрим простейший специальный символ, обычно определяемый как знак вопроса - ?. Если этот символ встречается в маске, то ему соответствует любой символ в слове, сравниваемом с маской. Рассмотрим примеры. Пусть из шести символьного номера автомобиля вторая цифра неизвестна. В этом случае можно построить такую маску – АВ2?45. Четвертый символ замаскирован. Этой маске соответствует все слова в алфавите Т, начинающиеся с АВ2 и заканчивающиеся на 45. Число таких слов соответствует числу символов алфавита. Заметьте, специальному символу ? соответствует любой из символов алфавита, не только цифра. Сколько слов соответствует маске "?В2??5" ? Нетрудно понять, что таких слов N³, где N – мощность алфавита.

Какие слова соответствуют маске "к?к" ? Таких слов N. Это слова длины 3, начинающиеся и заканчивающиеся буквой "к", среди которых такие слова, как "кок", "кук", "как", "к9к" и другие. Заметьте, слово "кк" маске не соответствует, - символов должно быть 3!

Какие слова соответствуют маске "?а?а" ? Таких слов N². Это слова длины 4, среди которых такие слова, как "мама", "папа", "баба", "каша", но не "деда".

Заметьте, разным вхождениям специального символа "?" соответствуют разные символы алфавита, совпадения возможны, но не обязательны.

Еще один важный специальный символ маски – это символ "*". Этот символ маскирует все, что угодно. Любое слово, любой длины, в том числе пустое слово соответствует звездочке. Так что если в маске присутствует символ "*", то такой маске соответствует бесконечное множество слов. Символ звездочки крайне полезен, когда длина искомого слова может быть произвольна.

Пусть среди множества текстов требуется найти текст, содержащий слово "компьютер". Для поиска таких текстов (слов) достаточно задать маску "*компьютер*". Все тексты, содержащие это слово, будут удовлетворять маске.

Пусть среди множества текстов требуется найти текст, содержащий одновременно слова "компьютер" и "информатика". Для поиска таких текстов (слов) недостаточно задать маску "*компьютер*информатика*". Все тексты, содержащие эти два слова, идущие в указанном порядке, будут удовлетворять маске, но текст "информатика и компьютер" этой маске не удовлетворяет. Конечно, можно повторить поиск, задав маску "*информатика*компьютер*", изменив порядок вхождения искомых слов.

На экзамене по информатике любимые задачи на маски, связаны с поиском имен файлов. Начнем с простейшей задачи. Требуется найти имена всех файлов, созданных в приложении Word. Все такие файлы имеют самые разные имена, но одинаковое уточнение. Поэтому для поиска файлов, созданных в старом формате можно задать маску "*.doc". Для файлов, созданных в новом формате можно задать маску "*.docx". Маске "*.doc*" будут соответствовать все документы Word, как в новом, так и в старом формате, но не только они. Например, если встретится файл с уточнением "docf", то он также будет удовлетворять последней маске. Рассмотрим следующую задачу:

В каталоге находится 6 файлов:

maveric.map

maveric.mp3

taverna.mp4

revolver.mp4

vera.mp3

zveri.mp3

Определите, по какой из масок из каталога будет отобрана указанная группа файлов:

maveric.mp3

taverna.mp4

vera.mp3

zveri.mp3

1) *?ver*.m* 2) ?ver*.mp*

3) *?ver*.mp* 4) *ver?*.mp?

Решение: Из 6 имен файлов маске не соответствуют два - maveric.map и revolver.mp4. Первое имя имеет отличающееся уточнение. Поэтому маска ".mp?" отфильтрует имя с уточнением map, и примет все имена с уточнениями mp3 и mp4. Имя revolver.mp4 отфильтровать сложнее, этого нельзя сделать, анализируя уточнения. Чем же имя revolver отличается от других имен файлов? Можно заметить, что все имена, кроме revolver, содержат вхождение слова "ver". Поэтому маска "*ver*.mp?" дает решение поставленной задачи. Правда, в ответе такой маски нет, но есть маска "*ver?*.mp?", которая использует еще одну особенность имен отобранных файлов, - они содержат, по крайней мере, еще один символ. Заметьте, что первые три маски следует сразу же отбросить, поскольку они имеют вид "?ver", что не позволяет отобрать имя vera.mp3.

Для решения задач экзамена по информатике умения работать с двумя специальными символами маски, – "?" и "*", вполне достаточно. В программировании при построении масок используется и множество других полезных символов, облегчающих построение требуемого фильтра. Приведу несколько примеров таких полезных символов.

Специальному символу "d" соответствует одна из цифр из диапазона 0-9. При поиске среди номеров этим символом удобнее пользоваться, чем символом "?".

Специальному символу "w" соответствует либо цифра, либо буква алфавита латиницы и или кириллицы. При поиске среди имен, названий этим символом удобнее пользоваться, чем символом "?".

Специальная конструкция [аоу], где в квадратных скобках перечислены некоторые символы, позволяет задать, что в данном месте должен присутствовать один из символов, указанных в скобках. Так, маске "к[аоу]к" соответствуют только три слова – как, кок, и кук – и никакие другие