4. Проиндексировать оставшиеся лексемы в массиве :

4.1. выбрать первую лексему массива ;

4.2. если в таблице проиндексированных лексем отсутствует строка вида , где – произвольное значение счётчика индексируемой лексемы , то добавить строку , иначе увеличить значение счётчика в найденной строке на единицу ;

4.3. если – последняя лексема в массиве , то перейти к п. 5, иначе перейти к следующей лексеме и повторить пункты 4.2 и 4.3.

5. Из таблицы проиндексированных лексем сформировать массив всех лексем пользователя с идентификатором , упорядоченный по убыванию соответствующих значений счётчиков.

6. Из таблицы проиндексированных лексем сформировать массив всех значений счётчиков лексем пользователя с идентификатором , упорядоченный по убыванию.

7. Осуществить поиск информации в базе данных по запросу (любым из существующих методов ИП). В результате сформировать массив результатов .

8. Упорядочить результаты по возрастанию значений , где – любая функция сходства и , убывающая при увеличении степени сходства своих аргументов (например, функция Левенштейна).

9. Вывести полученные результаты .

Блок-схема описанного алгоритма приведена на рисунке 2.1.

Рис. 2.1. Блок-схема алгоритма адаптивного поиска.

Отметим, что для использования описанного алгоритма в реальных системах необходимо дополнительно определить правила удаления проиндексированных лексем из базы данных с целью предотвращения её переполнения. Один из возможных подходов – ограничение максимально возможного числа индексируемых лексем на каждого пользователя.

В 8 пункте в качестве рекомендуется брать функцию Левенштейна или функцию Дамерау-Левенштейна.

Расстояние Левенштейна (функция Левенштейна) в теории информатики и компьютерной лингвистики является мерой разницы двух последовательностей символов (строк) относительно минимального количества операций вставки, удаления и замены, необходимых для перевода одной последовательности в другую. Например, чтобы перевести слово «конь» в слово «кот» необходимо совершить одну замену («н» на «т») и одну операцию удаления («ь»), соответственно дистанция Левенштейна в этом случае составляет 2.

Расстояние Дамерау-Левенштейна – это мера разницы двух строк символов, определяемая как минимальное количество операций вставки, удаления, замены и транспозиции (перестановки двух соседних символов), необходимых для перевода одной строки в другую. Является модификацией расстояния Левенштейна, отличается от него добавлением операции перестановки.

Выводы по главе 2

Разработан метод хранения предпочтений пользователей, полученных на основании предыдущих поисковых запросов. Описан алгоритм адаптивного поиска в базах данных. Данный алгоритм может быть использован для разработки на его основе библиотеки для осуществления адаптивного поиска в базах данных Web-приложений.

3. РАЗРАБОТКА ПРОГРАММНОЙ БИБЛИОТЕКИ

3.1. Проектирование

На базе описанного в предыдущей главе алгоритма была спроектирована и реализована на языке PHP программная библиотека для осуществления адаптивного поиска в базах данных Web-приложений. Данная библиотека позволяет осуществлять поиск текстовой информации в большинстве популярных баз данных, а именно: mSQL, Microsoft SQL Server, MySQL, Oracle, PostgreSQL, SQLite и InterBase.

При проектировании библиотеки был выбран объектно-ориентированный подход. Ключевыми объектами, выделенными в процессе проектирования, являются объект соединения с базой данных, объект результата и объект ошибки выполнения поискового запроса. UML-диаграмма основных классов, используемых в библиотеке, представлена на рисунке 3.1.

Класс DB является основным классом библиотеки. Ключевым понятием данного класса является DSN (data source name) – имя источника данных, представляющее собой строку или массив. DSN, заданный в виде строки, имеет следующий вид: phptype://username:password@protocol+hostspec/database?options.

Рассмотрим основные части DSN:

phptype – тип используемого драйвера базы данных (mssql, mysql и т. п.);

username – имя пользователя базы данных;

password – пароль пользователя;

protocol – коммуникационный протокол (tcp, unix и т. п.);

hostspec – спецификация хоста (имя хоста и номер порта);

database – имя базы данных для подключения;

options – дополнительные параметры, разделённые символом “&”.

Рис. 3.1. Диаграмма основных классов библиотеки.

Большинство частей DSN являются не обязательными и могут быть опущены, если база данных, которой осуществляется попытка подключения, это позволяет. Так, например, источник данных может быть описан строкой, представленной в одной из следующих форматов:

phptype://username:password@hostspec/database_name

phptype://username:password@hostspec

phptype://username@hostspec

phptype://hostspec/database

phptype://hostspec

phptype

Кроме того, DSN может быть задан с помощью ассоциативного массива, ключи которого носят те же имена, что и части строки DSN, описанные выше: phptype, username, password, protocol, hostspec, database. Номер порта указывается отдельно от имени хоста через элемент с ключом port. Дополнительные параметры подключения в этом случае должны быть указаны в параметре database и отделены от имени базы данных символом “?”. Для конвертирования DSN из массива в строку и обратно предусмотрены методы getDSNString() и parseDSN(). Данные методы класса позволяют разработчику указывать DSN в любом из двух возможных типов.

Основные методы класса, factory() и connect(), позволяют взаимодействовать с требуемым источником данных по его DSN. Метод connect(), в отличие от factory(), сразу же устанавливает соединение, не дожидаясь первого запроса к базе данных. Оба метода возвращают объект одного из наследников класса DB_common: DB_mssql, DB_mysql, DB_mysqli, DB_pgsql, DB_ibase или DB_oci8. Подобный подход позволяет легко расширять библиотеку.

Классы DB_result и DB_row формируют единый интерфейс для работы с результатами поисковой выдачи, не зависящий от типа используемого драйвера базы данных. Методы класса позволяют работать с результатом как с ассоциативным или нумерованным массивом. Кроме того, методы nextResult() и fetchRow() позволяют обрабатывать полученный результат строка за строкой и не хранить весь массив данных.

Поисковые методы объектов класса DB_common используют расширенный класс phpMorphy одноимённой библиотеки морфологического анализа, распространяемой бесплатно для некоммерческого использования. Методы phpMorphy позволяют решать следующие задачи: лемматизация (получение нормальной формы слова), получение всех форм слова, получение грамматической информации для слова (часть речи, падеж, спряжение и т. д.), изменение формы слова в соответствии с заданными грамматическими характеристиками, изменение формы слова по заданному образцу. Поддерживаемые в phpMorphy языки: русский, английский, немецкий, украинский, эстонский. Есть возможность добавить поддержку других языков. phpMorphy поддерживает все однобайтовые кодировки (windows-1251, iso-8859 и т. п.) и Unicode кодировки (utf-8, utf-16le/be, utf-32, ucs2, ucs4). По умолчанию библиотека работает с кодировкой UTF-8. phpMorphy использует для работы словарь. Поддерживаются словари AOT и myspell, свободно распространяемые, в том числе и для коммерческого использования. Словари представлены в двух видах: в исходном и бинарном. Исходный словарь представлен в виде XML файла и содержит основы слов, правила изменения и грамматическую информацию.

Для работы библиотеки требуется скомпилировать бинарный словарь. При компиляции используется словарь в исходном виде. Бинарный словарь обладает следующими особенностями: совместим c различными платформами, все данные представлены в заданной кодировке, в верхнем (по умолчанию) или нижнем регистре. Последняя особенность позволяет не тратить время на преобразование кодировки и регистра в реальном времени, а сделать это один раз на этапе компиляции.

Физически словарь представлен в виде нескольких файлов:

common_aut.ru – хранилище всех словоформ;

morph_data.bin – хранилище грамматической информации;

predict_aut.bin – хранилище окончаний для предсказания.

Именование файлов словаря производится в соответствии с шаблоном <имя_файла>.<язык>.bin, где <язык> – условный код языка, в виде ISO3166 кода страны и ISO639 кода языка, то есть ru_ru, en_en и т. п. Данный метод позволяет размещать в одном каталоге словари для нескольких языков.

Весь процесс поиска при работе с библиотекой состоит из трёх простых действий: подключения файла библиотеки, установки соединения с базой данных, например, с помощью метода DB::connect() и вызова метода поиска DB_Common::search() с указанием необходимых параметров. Пример работы с библиотекой приведён в листинге 3.1.

require_once 'DB.php';

// Источник данных

$dsn = 'mssql://login:pass@localhost/db_name';

// Установка соединения с базой данных

$db =& DB::connect($dsn);

// Поиск

$params = array('from' => 'table', 'where' => 'field');

$results = $db->search('Поисковый запрос', $params);

// Вывод результатов

while($r = $results->fetchRow())

echo $r['field'];

Листинг 3.1. Пример использования библиотеки.

Класс DB_error – вспомогательный класс для обработки возможных ошибок, возникающих в процессе работы с библиотекой. Объекты данного класса могут быть легко преобразованы в текстовые сообщения о возникшей ошибке, что существенно облегчает процесс отладки приложений, создаваемых на основе данной библиотеки. Пример обработки ошибок, возникающих при установке соединения с базой данных, приведён в листинге 3.2. Обработка ошибок, возникающих во время поиска, осуществляется аналогично.

require_once 'DB.php';

// Источник данных

$dsn = 'mssql://login:pass@localhost/db_name';

// Установка соединения с базой данных

$db =& DB::connect($dsn);

// Обработка ошибок

if (DB::isError($db))

echo $db->getMessage();

Листинг 3.2. Пример обработки ошибок.

Кодирование скриптов библиотеки осуществлялось на языке программирования PHP, интенсивно применяемом при разработке Web-приложений, в среде NetBeans.

3.2. Системные требования

Для использования библиотеки необходимо, чтобы сервер удовлетворял следующим системным требованиям:

1. наличие PHP версии 5.0 (или выше);

2. поддержка модуля mbstring.

Расширение веб-сервера mbstring позволяет использовать функции для работы с многобайтными строками. mbstring не входит в список расширений, устанавливаемых по умолчанию. Это значит, что изначально это расширение отключено. Для использования функций этого расширения необходимо явно включить модуль в настройках конфигурации веб-сервера.

3.3. Настройка параметров адаптивного поиска

Несмотря на то, что значения параметров по умолчанию подобраны таким образом, чтобы оптимизировать скорость работы библиотеки и не допустить чрезмерного роста таблицы индексируемых слов, может потребоваться изменить те или иные параметры. Значения параметров изменяются с помощью метода setOption() класса DB_common, принимающего два аргумента: название параметра и устанавливаемое значение. В идеале параметры адаптивного поиска должны подбираться, исходя из специфики конкретной задачи.

Дадим подробное описание изменяемых параметров адаптивного поиска. В скобках указаны значения по умолчанию.

users_words_table_name (adaptive_search_users_words) – имя таблицы в базе данных для хранения ключевых слов пользователей. Если во время поиска таблица с таким именем не будет найдена в базе данных, то она будет создана автоматически. Таким образом, указав специализированное имя, можно использовать уже имеющуюся в базе данных таблицу ключевых слов пользователей.

users_words_table_charset (utf8) – кодировка таблицы для хранения ключевых слов пользователей. По умолчанию используется UTF-8 (от англ. Unicode Transformation Format) – наиболее распространённая в настоящее время кодировка, реализующая представление Юникода, совместимое с 8-битным кодированием текста. В отличие от UTF-16, UTF-8 является самосинхронизирующейся кодировкой: при потере одного байта последующие байты будут раскодированы корректно.