"Монитор", #6.95 В. Максимов ‚ЂЂЂЂЂЂЂЂЂЂЂЂЂЂЂЂЂЂЂЂЂЂЂЂЂЂЂЂЂЂЂЂЂЂЂЂЂЂЂѓ Ѓ Алгоритмы поиска, или Ѓ Ѓ Как искать неизвестно что Ѓ „ЂЂЂЂЂЂЂЂЂЂЂЂЂЂЂЂЂЂЂЂЂЂЂЂЂЂЂЂЂЂЂЂЂЂЂЂЂЂЂ… - Скажите, пожалуйста, куда мне идти? - А куда ты хочешь попасть? - ответил Кот. - Мне все равно.. - сказала Алиса. - Тогда все равно, куда идти, - заметил Кот. - ..только бы попасть куда-нибудь, - пояснила Алиса. Л. Кэрролл. Алиса в стране Чудес Вам крупно не повезло, если вы точно знаете, где и что у вас лежит. Несчастный вы человек, ибо навсегда лишаетесь безумных прелестей поиска, вам никогда не придется метаться в поисках самого нужного документа, почтового адреса, телефона и еще неведомо чего в самый ответственный момент. Но не все потеряно. Стоит вам позабыть, что же именно необходимо найти, и вот тогда-то вы уже точно никогда это не найдете, и формула "теряя деньги, не теряйте времени" станет для вас так же, как и для всех смертных, особенно актуальной. Дабы избежать всеобщего разорения, видимо, и были созданы информационно-поисковые системы, призванные быстро и точно находить интересующую пользователя информацию. Требуется задать некоторый шаблон поиска, как правило, это - ключевое слово или выражение, обязательно присутствующее в документе, и из всего объема информации будут выделены только те ее элементы, которые содержат этот ключ. Остается только дожить до установки хотя бы 5-го CD-ROM и обнаружить необходимую информацию прежде, чем вы состаритесь. Но и это еще не все. Самое забавное в том, что совсем не обязательно вы что-нибудь найдете лишь потому, что не ошиблись в написании ключа поиска или не забыли (а, может быть, никогда и не знали) его точного написания. Кроме того, никто не гарантирует, что в просматриваемом информационном массиве нет опечаток или каких-либо других ошибок, появившихся, скажем, при передаче по каналам связи, и эта ошибка не приходится как раз на то выражение, по которому осуществляется поиск. В общем, сами понимаете. Не торопитесь рвать остатки растительности на голове. Проблема быстрого поиска в больших информационных массивах известна давно, и уже найдено много удачных решений, Рассмотрим некоторые из них, а также сравнительно новый алгоритм нечеткого поиска, который и позволяет "искать неизвестно что". О чем это мы бишь ? Первое, о чем следует позаботиться, приступая к решению какой-либо проблемы, это построить ее точное описание. Поступим именно так. Обычно информационный массив (текст), в котором производится поиск, и шаблон поиска принято представлять в виде последовательности алфовитно-цифровых символов. Будем придерживаться этого и мы, но на самом деле этими символами могут быть любые знаки или обозначения: буквы, цифры, формальная запись правил базы знаний, записи баз данных, строки программного кода, нотные знаки партитуры и так далее. Обозначим просматриваемый текст как T = t1 t2 t3 ... tn, а шаблон поиска как P = p1 p2 p3 ... pm, причем n, как правило, значительно больше m. Задача состоит в поиске всех вхождений P в T. Простейший алгоритм точного поиска Простейшее решение задачи состоит в последовательном сравнении, начиная с t1 и p1, символов T и P до тех пор, пока не будет обнаружено совпадение или несовпадение. В последнем случае следует вернуться к началу сравнения (t1), сдвинуться на один символ по тексту (теперь это будет t2), и повторить попытку. Сказанное можно проиллюстрировать следующим образом. Поиск производится по шаблону vivid в тексте vivi&dv&vivid, момент несовпадения символов шаблона и текста отмечается заглавной буквой. Получаем: vivi&dv&vivid viviD V viV V V V vI V vivid Здесь первые четыре символа совпадают, а пятый нет. Продолжать поиск, начиная с &, нельзя, поскольку третий и четвертый символы текста (vi) совпадают с началом шаблона и могут быть началом точного совпадения - надо проверять каждое начало, как показано на примере. Этот алгоритм требует выполнения не менее n-m+1 сравнений и работает медленно. Вместе с тем он весьма прост при программировании и позволяет проводить поиск с использованием шаблона любой длинны. Точный поиск по алгоритму Бойера-Мура Известно несколько способов улучшения описанного здесь простейшего решения. Наиболее известны два из них: алгоритм Бойера-Мура (Boyer-Moore) и алгоритм Кнута-Морриса-Пратта (Knuth-Morris-Pratt). В большинстве случаев при решении задач точного поиска алгоритм Бойера-Мура работает быстрее, поэтому остановимся именно на нем. Существует несколько модификаций данного алгоритма. Сравнение начинает проводится не между первым символом шаблона и первым символом текста, а между последним символом шаблона и m-тым символом текста (в рассмотренном примере - пятым). Мы должны будем сравнивать d и &; эти символы не совпадают, и шаблон сдвигается. Клбчевой момент здесь в том, что определяется символ текста, из-за которого произошло несовпадение (в нашем случае &), и устанавливается, в каком месте шаблона находится этот символ. В зависимости от этого принимается решение о величине сдвига. В рассмотренном примере & не содержится в шаблоне, поэтому можно спокойно сдвигать весь шаблон на m символов вправо. Следующее сравнение проводится между последним символом шаблона и десятым символом текста, то есть после сдвига на пять позиций. Десятый символ - i, в шаблоне он содержится на второй и четвертой позиции. Мы сдвигаем шаблон только на одну позицию, поскольку i в тексте может совпадать с четвертым сиволом шаблона. Теперь переходим к одиннадцатому символу текста (v). Он содержится в шаблоне в первой и третьей позициях; сдвигать шаблон нужно на два символа, что вычисляется как размер шаблона минус номер последней позиции символа текста, содержащегося в шаблоне. Это приводит нас к тринадцатому символу (d). На этот раз имеем совпадение символов d. Снова проверяется совпадение шаблона и текста, что в нашем случае выполняется. Если же совпадают последние несколько символов, а остальные нет, можно в этих условиях воспользоваться описанным ранее простейшим алгоритмом со сдвигом шаблона на один символ или применить какой-либо другой метод. Основное преимущество данного метода в том, что несовпадений бывает значительно больше, а это, в свою очередь, приводит к большим сдвигам. В рассмотренном примере при работе по алгоритму Бойера-Мура потребовалось всего восемь сравнений вместо двадцати при простейшем решении. Точный поиск по алгоритму СДВИГ-И Алгоритм поиска СДВИГ-И предложен сравнительно недавно и пока мало известен. Его опубликовали в 1992 году два исследователя из Аризонского университета и Bell Labs - Уди Манбер (Udi Manber) и Сан Ву (Sun Wu). Помимо того что алгоритм быстро работает и его просто программировать, он обладает уникальной особенностью: его можно легко, если не сказать элементарно, обобщить на случай нечеткого (приблизительного) поиска. Предположим, что отыскиваются не только все вхождения P в T, но и вхождения в T всех возможных префиксов шаблона P: P(1) = p1, P(2) = p1 p2, P(3) = p1 p2 p3 ... P(m) = p1 p2 p3 ... pm В рассматриваемом примере будем искать все вхождения пяти шаблонов: v, vi, viv, vivi и vivid. Построим таблицу, которая бы отражала для каждой позиции текста, является ли эта позиция концом каждого из рассматриваемых пяти шаблонов. Для каждой позиции текста получим битовый 5-элементный вектор-массив, в котором k-й бит равен 1, если эта позиция соответствует концу вхождения k-го префикса. В итоге имеем таблицу из m строк и n столбцов: vivi&dv&vivid v 1010001010100 i 0101000001010 v 0010000000100 i 0001000000010 d 0000000000001 Основной интерес представляет, разумеется, последняя строка, поскольку соответствует искомому вхождению шаблона в текст, но вскоре станет ясно, что и остальные строки не менее важны. Опишем проделанные операции. Пусть R - j-й столбец таблицы. Тогда R - j j битовый массив длиной m, в котором R [k] = 1, если первые j символов шаблона j точно совпадают с k символами текста, предшествующими T включительно, то j есть, если выполняется условие p ... p = t ... t . Остается научиться 1 k j-k+1 j строить эту таблицу быстро. Легко видеть, что j+1-й столбец таблицы зависит только от j-го столбца, шаблона и символа t . Например, совпадение в j+1 j+1 для viv будет выполняться только тогда, когда совпадение выполнялось для vi в j и t = v. Другими словами, j+1 / 1, если R [k-1] = 1 и p = t | j k j+1 R [ k ] = < j+1 | \ 0 - во всех других случаях При этом для всех k (1 <= k <= m) полагаем R [k] = 0 и для всех j 0 (0 <= j <= n) R [0] = 1. j Полученная рекурсия при программировании требует для вычисления каждого элемента таблицы всего одного условного оператора IF. Но и это не предел. Если длина шаблона не превышает 32, то тогда столбцы таблицы, которые, как мы помним, являются битовыми массивами, можно представить в виде 32-битовых машинных слов. В этом случае можно будет вычислять сразу весь столбец. Если рассмотреть, например, первые два столбца таблицы, то единицы во втором столбце могут появиться при одновременном выполнении двух условий: (a) единица может стоять только в позиции, соответствующей i в шаблоне (поскольку t2 = i), и только тогда, когда в первом столбце таблицы на этом месте также стоит единица (b). Первое условие (a) обеспечивает совпадение последних символов, а второе (b) - совпадение предыдущих. Для того чтобы прверить выполнение условия (b) достаточно просто сдвинуть вниз первый столбец. Для быстрой проверки выполнения условия (a) заренее для всех символов подготавливаются характеристические векторы длинной m. Характеристический вектор для символа i в нашем случае имеет единицы во второй и четвертой позициях (то есть позициях, в которых имеется данный символ) и нули во всех остальных - 01010. Характеристический вектор для v - 10100, для d - 00001, а для всех остальных символов алфавита характеристические векторы - 00000. Проверка условия (a) проводится путем сравнения полученного сдвигом вниз первого столбца (первый столбец 10000 становится после сдвига *1000) и характеристического вектора для i. Позиции, в которых единицы совпадают, получают также единичное значение, остальные обнуляются. Полученное значение становится вторым столбцом таблицы. Единственное исключение касается первой позиции, для которой условие (b) очевидно истинно, поскольку предыдущая позиция попросту отсутствует. Поэтому первая позиция при сдвиге всегда заполняется единицей. Таким образом, для третьего столбца (10100) после сдвига и дополнения единицей получаем 11010. Теперь после сравнения, то есть выполнения операции побитового AND, с характеристическим вектором для i (01010) получаем 01010. Итак, сначала мы построили таблицу, отражающую совпадения со всеми префиксами шаблона. Затем получили рекурсию, при помощи которой вычисляются элементы таблицы. Наконец, найден способ вычисления каждого столбца таблицы при помощи одного сдвига предыдущего столбца и одной операции побитового умножения. Таким образом, алгоритм требует не более n сравнений, причем сравнения состоят исключительно из битовых операций. Несмотря на кажущуюся сложность и запутанность алгоритма, программа получается на удивление простой. Ее фрагменты для 16-битовых машин на C (для лучшего понимания) приведены в конце статьи. Приведенные программы легко расширить для обработки более сложных шаблонов. Предположим, что вместо vivid требуется найти все слова из пяти букв, на второй и четвертой позициях которых находятся i. Единственное, что надо сделать, - немного изменить предварительную обработку и скорректировать таблицу характеристических векторов. Для этого на первой, третьей и пятой позициях во всех характаристических векторах надо поставить единицы. Это будет означать, как следует из описания алгоритма, что на этих позициях может находится любой символ. Если же потребуется исключить из рассмотрения, например, цифры, то их характеристические векторы следует положить равными нулю (00000). Самое же важное, как отмечалось, свойство приведенного алгоритма состоит в том, что его легко обобщить на случай приблизительного поиска. Приблизительный поиск Предположим, что в нашем примере требуется найти все вхождения vivid с возможно одной несовпадающей (измененной) буквой. Построим две таблицы: R1 = vivi&dv&vivid v 1010001010100 i 0101000001010 v 0010000000100 i 0001000000010 d 0000000000001 R2 = vivi&dv&vivid v 1111111111111 i 0101000101010 v 0010100010101 i 0001000001010 d 0000100000001 Первая таблица R1 совпадает с таблицей, описанной в предыдущем разделе, и построена тем же способом. Вторая таблица R2 похожа на первую, с той лишь разницей, что отражает как точные совпадения, так и совпадения при одном измененном символе. Рассмотрим сначала пятый столбец R2. Он отличается от пятого столбца R1 в первой, третьей и пятой позициях. Действительно, vivi& совпадает с шаблоном vivid с одним изменением, vi& совпадает с viv с одним изменением и & совпадает с v (первая строка R2 всегда целиком состоит из единиц). Совпадение vivi& с vivid при одном изменении обнаруживается по четвертому столбцу R1 как точное совпадение по vivi. И если имеется точное совпадение до последнего символа, тогда всегда существует не более одного совпадения с одной заменой, Таким образом, один из способов внесения дополнительных единиц в R2, то есть вычисления R2 по R1, состоит в сдвиге вниз предыдущего столбца R1 без выполнения операции AND. Рассмотрим теперь десятый столбец, в R2 он 11010. Во второй строке стоит единица (точное совпадение по vi), что обеспечивается выполнением сдвига. Четвертая строка соответствует совпадению v&vi с vivi, но здесь замена произошла прежде. Совпадение же обнаруживается по девятому столбцу таблицы R2 проверкой совпадения с одной заменой v&v и проверкой совпадения последнего символа (i). Обобщая, можно сказать, что все возможности учитываются только двумя дополнительными арифметическими операциями. Если для текущего символа текста имеет место точное совпадение или замена, то решение о совпадении принимается по сдвигу предыдущего столбца R1. Если же замена произошла раньше, то тогда решение принимается по сдвигу с дополнением единицей предыдущего столбца R2 и выполнению операции AND над ним и характеристическим вектором. Модифицированный текст на C, в котором допускается поиск с одной ошибкой замены, приведен в конце статьи. Теперь рассмотрим вставки и пропуски. Предшествующие вставки или пропуски уже учитываются предыдущим столбцом R2 и могут быть обнаружены при помощи тех же операций сдвига и побитового умножения, что и для предшествующих замен. Вставки в конце могут быть выявлены путем копирования предыдущего столбца R1 без сдвига, а пропуски - сдвигом текущего (нового) столбца R1. Например, третий столбец R2, учитывающий замены, вставки и пропуски, выглядел бы как 11110. Здесь четвертая единица появляется из совпадения vivi с viv исключением (пропуском) последней i, и это обнаруживается по сдвигу третьего столбца R1. Вторая единица может быть получена по-разному: из совпадения vi с viv после добавления последней v, что обнаруживается копированием второго столбца R1, или из совпадения vi с v с третьей позиции при отброшенной последней i. Короче говоря, замены, вставки и пропуски могут обрабатываться (и выявляться) при помощи всего четырех арифметических операций. Кроме того, если требуется, чтобы допускалось более одной ошибки, это не составит большой проблемы. Нужно всего-навсего ввести по одной дополнительной таблицн на каждую ошибку и проводить аналогичные преобразования одной талицы в другую. По существу данный алгоритм позволяет проводить поиск любого регулярного выражения с ошибками или без них. Описанный алгоритм приблизительного поиска реализован его авторами в утилите agrep, которая, помимо традиционных для этой утилиты возможностей, позволяет проводить приблизительный поиск с двумя заменами, вставками или пропусками в любом их сочитании. При этом допускается вводить приоритеты для каждого типа ошибок и задавать их количество. Полный текст утилиты можно получить по анонимному ftp на cs.arizona.edu по сети Relcom или любой другой, имеющей выход в Internet. Листинг программы #include #include #define WORD_SIZE 16 /* Разрядность слова процессора в битах */ #define ABC_SIZE 256 /* Размер используемого алфавита символов */ unsigned int M; /* Длина шаблона в символах */ unsigned int Bit[WORD_SIZE]; /* Вспомогательная диагональная матрица */ unsigned int CVTbl[ABC_SIZE]; /* Таблица характеристических символов */ void OkMatch( char *Text ) { /* Обрабатываем найденное совпадение. Параметр Text указывает на конец совпадения в просматриваемом тексте */ printf( " Found coincidence: \"%s\"\n", Text-M+1); } void BuildCVTbl( char *Pattern, unsigned int CVTbl[]) { int i; M = strlen( Pattern ); for( i=0; i> 1) | Bit0) & CVector; if( (R & EndPos) != 0 ) OkMatch( Text ); /* Совпадение обнаружено */ } } void FuzzyShiftAND( char *Text, unsigned CVTbl[]) { unsigned int R1, R2; /* Текущие столбцы таблиц */ unsigned int CVector; /* Характеристический вектор для текущего символа */ unsigned int Bit0; /* Младший бит */ unsigned int EndPos; /* Маска обнаружения совпадения */ EndPos = Bit[M-1]; Bit0 = Bit[0]; R1 = R2 = 0; for( ; *Text!='\0'; Text++) { CVector = CVTbl[ (unsigned char) *Text ]; R1 = (R1 >> 1) | Bit0; R2 = ((R2 >> 1) & CVector) | R1; R1 &= CVector; if( (R2 & EndPos) != 0 ) OkMatch( Text ); /* Совпадение обнаружено */ } } void main( void ) { char Pattern[] = "vivid"; /* Шаблон поиска */ char *Text = "vivi&dv&vivid"; /* Указатель на ASCII-буфер, в котом искать */ /* Строим таблицу характеристических векторов */ BuildCVTbl( Pattern, CVTbl); /* Осуществляем точный поиск */ printf( "Exact search\n" ); ExactShiftAND( Text, CVTbl); /* Осуществляем приблизительный поиск */ printf( "Fuzzy search\n" ); FuzzyShiftAND( Text, CVTbl); printf( "\n" ); }