Библиотека сайта rus-linux.net
Поиск текста (Часть I)
Источник: "Searching for Text (Part I)"Автор: Rene Pfeiffer,
Свободный пересказ на русском языке: Андрей Орлов, http://eaglenest.ru
Вы много работаете над чтением и написанием текста? Вы часто используете поисковые инструменты? У вас есть куча данных, расположенных на вашем веб или файл сервере? Для многих из нас это так. Как вы организуете коллекцию ваших текстовых данных? Используете ли директорию, индекс или базу данных? Если вы еще не решили, давайте рассмотрим несколько возможностей.
Документы и операции с текстом
Сосредоточимся на организации, индексировании и поиске текстовых данных. Этого вполне достаточно, так как многие поисковые запросы могут быть преобразованы в запросы на поиск текста. Обработка текста труднее, чем кажется, и стоит рассмотреть ее внимательно. Обратите внимание на различие между документами и собственно текстовыми данными: существует широкий выбор форматов документов. Некоторые из них хорошо описаны, другие нет. Некоторые имеют открытые спецификации, доступные для разработчиков, в то время как проприетарные форматы документов - частый барьер для обработки данных, но, к сожалению, их нельзя избежать.
Для начала данные нужно каким-либо образом организовать. Не имеет значения, будет это структура каталогов файлового сервера, на который будут скопированы данные, или просто список закладок в браузере. Главное, чтобы каждый отдельный документ был обозначен уникальным идентификатором или ссылкой. Это может быть Универсальный Локатор Ресурсов (URLs), или же путь к файлу. Кроме того, будет замечательно, если документы сгруппированы по категориям.
Обратите внимание на формат документов. Большинство индексирующих и поисковых инструментов могут обрабатывать только обычный текст, поэтому нужно найти способ преобразования в текст документов в различных форматах. Вот несколько примеров таких преобразований на шелле:
- pdftotext -q -eol unix -enc UTF-8 $IN - > $OUT
- Postscript
- pstotext $IN | iconv -f ISO-8859-1 -t UTF-8 -o $OUT -
- MS Word
- antiword $IN > $OUT
- HTML
- html2text -nobs -o $OUT $IN
- RTF
- unrtf --nopict --text $IN > $OUT
- MS Excel
- py_xls2txt $IN > $OUT
- Любой документ OpenOffice:
- ooo_as_text $IN > $OUT
Переменная $IN обозначает исходный документ, а переменная $OUT - путь к файлу. в котором должно быть размещено его преобразованное в текст содержимое. Текст может быть в различных кодировках, и чтобы успешно работать со всеми документами, полезно после преобразования конвертировать текст в кодировку UTF-8 (или другую кодировку Unicode). Преобразование в UTF-8 из любой национальной кодировки не вызывает потерь информации или каких-либо других проблем. Преобразование из UTF-8 в национальную кодировку приводит к частичным потерям символов (и, соответственно, информации), и поэтому не слишком интересно.
Существуют конвертеры для преобразования документов из формата MS Office, но этот формат не самый лучший выбор для хранения информации. Он пока еще проприетарный, а "свободная" спецификация Microsoft бесполезна: она полностью исключает коммерческое использование и, следовательно, вообще не является свободной. Хранение информации в таком формате несет множество опасностей - особенно, если производитель прекратит поддержку старых версий при обновлении программного обеспечения (такое уже случалось). Понимание этого ясного и очевидного предупреждения позволит изначально предотвратить множество проблем, учитывая его при организации коллекции документов.
Разработка способа организации данных самый важный шаг, после которого можно рассмотреть способы поиска и индексации.
Полнотекстовый поиск в MySQL
В разделе "Полнотекстовый поиск на естественном языке" руководства [1] описано создание и использование предоставляемых MySQL полнотекстовых индексов. С их помощью текстовые данные могут быть легко проиндексированы. Для примера создадим следующую таблицу:
CREATE DATABASE textsearch;
USE textsearch;
CREATE TABLE documents (
id INT UNSIGNED AUTO_INCREMENT NOT NULL PRIMARY KEY,
filename VARCHAR(255) CHARACTER SET utf8 COLLATE utf8_unicode_ci NOT NULL,
path VARCHAR(255) CHARACTER SET utf8 COLLATE utf8_unicode_ci NOT NULL,
type VARCHAR(255) CHARACTER SET utf8 COLLATE utf8_unicode_ci NOT NULL,
mtime TIMESTAMP NOT NULL DEFAULT CURRENT_TIMESTAMP,
content TEXT CHARACTER SET utf8 COLLATE utf8_unicode_ci NOT NULL,
FULLTEXT (filename),
FULLTEXT (content)
);
В таблице хранится имя файла, путь, тип файла и его содержимое, преобразованное в текст. Для большого дерева директорий размер поля path может оказаться слишком мал, но для простого примера его более чем достаточно. Каждый документ имеет уникальный ID, хранимый в поле id. Опция FULLTEXT() уведомляет MySQL что нужно создать полнотекстовый поисковый индекс по полям filename и content. К индексу можно добавить другие поля, но не для всех это нужно. Однако, может быть полезно добавить к индексу поле type.
Для тестирование потребуется несколько записей с текстовым содержимым, которые можно вставить такими командами:
INSERT INTO documents ( filename, path, type, content ) VALUES ( 'gpl.txt', '/home/pfeiffer', 'Text', 'This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation;' ); INSERT INTO documents ( filename, path, type, content ) VALUES ( 'fortune.txt', '/home/pfeiffer', 'Text', 'It was all so different before everything changed.' ); INSERT INTO documents ( filename, path, type, content ) VALUES ( 'lorem.txt', '/home/pfeiffer', 'Text', 'Lorem ipsum dolor sit amet, consectetuer adipiscin...' );
Теперь можно попробовать выполнить полнотекстовый поиск:
mysql> SELECT id,filename FROM documents WHERE MATCH(content) AGAINST('lorem');
+----+----------+
| id | filename |
+----+----------+
| 6 | test.txt |
+----+----------+
1 row in set (0.01 sec)
mysql>
Поиск выполняется конструкцией MATCH() AGAINST(). MySQL индицирует релевантность записи в таблице числом, называемом рангом. Кроме поиска, выражение MATCH() AGAINST() позволяет отобразить ранги:
mysql> SELECT id, filename, MATCH(content) AGAINST('lorem') FROM documents;
+----+-------------+---------------------------------+
| id | filename | MATCH(content) AGAINST('lorem') |
+----+-------------+---------------------------------+
| 1 | gpl.txt | 0 |
| 2 | fortune.txt | 0 |
| 3 | s3.txt | 0 |
| 4 | s4.txt | 0 |
| 5 | miranda.txt | 0 |
| 6 | test.txt | 0.75862580537796 |
+----+-------------+---------------------------------+
6 rows in set (0.00 sec)
mysql>
Конечно, в таблицу было добавлено немного больше текстов, чем написано в примере.
Правая колонка показывает ранг. Число больше нуля содержит только шестая строка, потому что во всех других текстах отсутствует слово "lorem". Можно добавить еще больше текстов и посмотреть на их ранг. Заметим, что MySQL при выполнении полнотекстовой индексации использует особую стратегию :
- Слова короче четырех символов не индексируются;
- Слова, которые появляются более чем в 50% строк текста не индексируются;
- Слова, перенесенные на новую строку, считаются как два слова;
- Любые неполные слова игнорируются;
- Движок базы данных поддерживает список общих англоязычных слов (стоп-слов), которые также игнорируются.
Обратите внимание - если поисковый запрос состоит исключительно из стоп-слов, то ни одной строки не будет найдено. Если нужен полнотекстовый поиск на языке, отличным от английского, то можно предоставить список стоп-слов для этого языка. В документации на MySQL [1] рассказано, как это сделать.
Возможен поиск более чем по одному слову: в этом случае слова в запросе разделяются запятыми:
SELECT id, filename, MATCH(content) AGAINST('lorem,ipsum') FROM documents;
Полнотекстовый поиск на PostgreSQL
Конечно, для полнотекстового поиска может использоваться и PostgreSQL: плагин, называемый Tsearch2, интегрирован в версию 8.3.0 сервера баз данных PostgreSQL и доступен для более ранних версий. Так же как и функции MySQL, плагин может быть настроен в соответствии с языком, на котором написаны индексируемые тексты.
При индексации текст должен преобразовываться в токены и для выполнения этого в PostgreSQL введены специальные объекты базы данных. Плагин Tsearch2 предоставляет парсеры текста для токенизации, словари для нормализации токенов и списки "стоп-слов", шаблоны настроек для переключения между парсерами или словарями, что позволяет использовать его для любого языка. Тем не менее, для создание новых объектов базы данных потребуется умение программировать на C.
Рассмотрим вышеприведенный пример для случая PostgreSQL версии 8.3.0 (если у вас более старая версия, установите Tsearch2):
CREATE TABLE documents (
id_documents serial,
filename character varying(254),
path character varying(254),
type character varying(254),
mtime timestamp with time zone,
content text );
CREATE INDEX documents_idx ON documents USING gin(to_tsvector('english',content));
В первую очередь создается таблица, затем - текстовый индекс GIN (Обобщенный Инвертированный Индекс). Этот тип индекса содержит различные лексемы (нормализованные слова). Функция to_tsvector(), используя английский парсер и словарь, преобразует текст, хранимый в колонке content, в эти лексемы.
Поисковый запрос выглядит примерно так:
lynx=> SELECT filename,mtime FROM documents WHERE to_tsvector(content) @@ to_tsquery('lorem');
filename | mtime
-----------+------------------------------
lorem.txt | 2008-02-26 12:15:16.34584+01
(1 row)
lynx=>
Здесь используется обычный SELECT и оператор сравнения с текстом @@. Этот оператор сравнивает аргументы и поисковую строку, преобразованные в лексемы с использованием функций to_tsvector() и to_tsquery(). Результаты, возвращенные оператором SELECT, показаны в примере. Их можно упорядочить при помощи ранжирования:
lynx=> SELECT filename,mtime,ts_rank(to_tsvector(content),to_tsquery('lorem'))
FROM documents WHERE to_tsvector(content) @@ to_tsquery('lorem');
filename | mtime | ts_rank
-----------+------------------------------+-----------
lorem.txt | 2008-02-26 12:15:16.34584+01 | 0.0607927
(1 row)
lynx=>
Одна из критических операций текстового поиска - токенизация, или преобразование строки в лексемы. Важно понимать алгоритмы, используемые PostgreSQL для выполнения этой операции. Рассмотрим следующий пример:
lynx=> SELECT alias, description, token FROM ts_debug('copy a complete database');
alias | description | token
-----------+-----------------+----------
asciiword | Word, all ASCII | copy
blank | Space symbols |
asciiword | Word, all ASCII | a
blank | Space symbols |
asciiword | Word, all ASCII | complete
blank | Space symbols |
asciiword | Word, all ASCII | database
(7 rows)
lynx=>
Здесь с помощью функции ts_debug() показан каждый токен, получаемый из текстовой строки, а также его классификация. Модуль текстового поиска понимает большинство общих текстовых конструкций, он может даже декодировать URL-ы:
lynx=> SELECT alias, description, token FROM ts_debug('http://linuxgazette.net/145/lg_tips.html');
alias | description | token
----------+---------------+-----------------------------------
protocol | Protocol head | http://
url | URL | linuxgazette.net/145/lg_tips.html
host | Host | linuxgazette.net
url_path | URL path | /145/lg_tips.html
(4 rows)
lynx=>
Здесь показаны токены, и их классификация как составных частей URL. Токены позволяют улучшить обработку поисковых запросов, поэтому текстовый поиск сравнивает токены, а не сами строки. По этой причине строка запроса должна быть токенизирована (функцией to_tsquery('lorem')).
Заключение
В статье представлены только два способа индексации текстовых данных. В действительности это лишь вершина айсберга: о полнотекстовом поиске можно рассказать значительно больше. MySQL и PostgreSQL предлагают удобные, готовые для использования алгоритмы, что позволяет легко реализовать поиск документов: с любой из этих баз данных можно использовать простой скрипт на Perl, который скормит им закладки вашего браузера и построит индекс содержимого веб-страниц, позволяющий использовать текстовый поиск. Существует много других доступных инструментов для индексирования и в следующей части этой серии будут представлены другие способы. Если для выполнения поиска или индексации вы используете что-то другое или более интересное, пожалуйста, напишите об этом.