 | Уровень сложности: средний Натан Хэррингтон, разработчик приложений, IBM
14.05.2008 Используйте Perl и векторно-пространственный поисковый механизм для поиска и отображения записей из LDAP-базы данных (Lightweight Directory Access Protocol). Используйте флективные буквы и цифры для создания подходящего векторного пространства из структурированных LDAP-данных. Автоматически корректируйте типографские и орфографические ошибки при отображении наиболее подходящего соответствия для любого введенного запроса.
Статьи, посвященные векторно-пространственному поиску, обычно начинаются с описания векторных пространств и того, как сформировать запрос в пространство термов (term space). Вместо этого давайте выполним обратную работу, используя следующий пример: для указанного запроса Nathen мы хотим получить соответствие элементов данных Nathan и Jonathan в данном порядке. Существующие подходы могут создавать регулярное выражение, базирующееся на основах слова, или метафоне (metaphone), и на других лингвистических производных искомого выражения. В нашем случае эффективные результаты поиска можно получить путем создания вектора для каждого символа в слове и возврата результатов, основанных на ближайшем соответствии в векторном пространстве. В данном случае результат Nathan будет выведен первым, потому что у него совпадают пять символов (векторов) из шести, а Jonathan будет выведен вторым, потому что имеет совпадение только пяти из восьми символов.
Исходный код и описания в данной статье дают упрощенное представление о векторных пространствах и операциях эффективного поиска в них. К счастью, у нас есть замечательный модуль Search::VectorSpace Мациежа Цегловски (Maciej Ceglowski), который эффективно инкапсулирует логику, математику и вспомогательную работу с векторными пространствами. Ссылки на информацию и исходные коды по всем вопросам теории и практики векторных пространств приведены в разделе "Ресурсы".
Методы векторно-пространственного поиска обычно подходят для текстов в свободной форме, содержащих определенное количество слов, что помогает выделить блок текста в векторном пространстве. C методом векторно-пространственного поиска наилучшим образом ассоциируются Web-страницы, отчеты по научным исследованиям и другие формы записей на естественном языке.
LDAP-данные обычно состоят из набора очень избыточных данных и набора уникальных компонентов данных. Однозначность фамилий (например, harrington по сравнению с herrington), телефонных номеров и других полей могут привести к двусмысленным результатам поиска, поскольку общее число векторов между запросом и набором данных очень мало. Традиционные векторно-пространственные подходы назначают такому слову как harrington один вектор. Однако подход, используемый в данной статье, назначает вектор каждому символу в слове. Способное пренебрегать орфографическими ошибками (обычными при поиске по имени), невосприимчивое к типографским ошибкам (например, 919-41 5-2042) разделение каждого алфавитно-цифрового символа в изменяемые формы слова является быстрым и легко управляемым способом использования LDAP-данных в механизме векторно-пространственного поиска.
Требования
Аппаратное обеспечение
Любой современный PC, выпущенный после 2000 года, должен обеспечить достаточно мощности для компиляции и выполнения кода, приведенного в данной статье. Однако большие наборы данных потребуют значительного объема оперативной памяти и производительности, если необходимо обеспечить время реакции меньше секунды. Время начального создания векторного пространства может быть большим, особенно для больших наборов данных. Операция поиска на самом деле является быстрой и растет линейно с ростом объема данных.
Программное обеспечение
Код основан на замечательном модуле VectorSpace Мациежа Цегловски. Необходимо загрузить модуль Search::VectorSpace из CPAN с предпочитаемого вами зеркального сайта. Обратите внимание, что модуль VectorSpace устанавливать не нужно. Просто загрузите архив, содержащий VectorSpace.pm, и разархивируйте его в рабочий каталог. Для работы с файлами данных LDAP необходим также модуль File::Find (стандартный для большинства дистрибутивов Perl).
Изменения в модуле Search::VectorSpace.pm
После загрузки модуля VectorSpace.pm необходимо сделать в нем небольшие изменения для поддержки расширения всех алфавитно-цифровых символов в слова в векторном пространстве. Измените подпрограмму get_words из модуля VectorSpace.pm так, как показано ниже.
Листинг 1. Подпрограмма VectorSpace.pm get_words
sub get_words {
# Отделить пробел и убрать пунктуацию
my ( $self, $text ) = @_;
my %doc_words;
my @words = map { stem($_) }
grep { !( exists $self->{'stop_list'}->{$_} ) }
map { lc($_) }
map { $_ =~/([a-z\-']+)/i}
split /\s+/, $text;
do { $_++ } for @doc_words{@words};
return %doc_words;
}
|
Удалите строку grep { !( exists $self->{'stop_list'}->{$_} )
} из блока map в подпрограмме для запрещения проверки stop_list.
Файлы данных LDAP
В данной статье используются LDAP-данные, извлеченные из корпоративного каталога нашей компании. Программа vectorSearch.pl, описанная ниже, ожидает, что файл данных будет иметь одну LDAP-запись. В листинге 2 показан пример файла данных LDAP в каталоге ldapData. Обратите внимание на то, что код примера в данной статье спроектирован так, чтобы предоставить вам соответствующее имя файла, ассоциированное с данным запросом. Для дальнейшей обработки этого файла и отображения соответствующей информации о контактах пользователя, названия должности или иных полей могут быть написаны другие программы.
Листинг 2. Пример файла данных LDAP
objectclass: person
alternatelocalityname: Research Triangle Park
notesemail: CN=Nathan J Harrington/OU=Raleigh/O=IBM@ibmus
jobresponsibilities: System Administrator, Applications Developer
phone: 919-415-2042
|
Программа vectorSearch.pl
Мы удалили список останова и извлекли некоторые LDAP-данные. Теперь все готово для начала поиска при помощи программы vectorSearch.pl. В листинге 3 показаны определения переменных и вызовы подпрограммы из заголовка программы.
Листинг 3. Заголовок основной программы vectorSearch.pl
#!/usr/bin/perl -w
# vectorSearch.pl - поиск ldap-данных с использованием Search::VectorSpace
use strict;
use VectorSpace;
use File::Find;
die "specify a directory of files, maximum matches" unless @ARGV == 2;
my %fileHash = ();
my %phHash = ();
my $maxMatch = $ARGV[1];
loadInflectives();
find(\&loadVectorSpace,"$ARGV[0]");
|
Давайте подробнее рассмотрим эти подпрограммы, начиная с loadInflectives. Для данного файла данных формата, показанного в листинге 4, подпрограмма loadInflectives создает алфавитно-цифровой фонетических хэш. Мы будем использовать этот хэш позже для преобразования слов в строку их фонетических алфавитных эквивалентов.
Листинг 4. Пример фонетического алфавитного файла данных
A Alpha
B Bravo
C Charlie
...
7 Seven
8 Eight
9 Nine
|
Подпрограмма loadInflectives показана в листинге 5. Нет ничего проще.
Листинг 5. Подпрограмма loadInflectives
sub loadInflectives
{
open(INF,"alphaNumericInflectives" ) or die "can't open phonetic alph bet";
while(my $inLine = <INF> )
{
chomp($inLine);
my ($letter, $name ) = split " ", lc($inLine);
$phHash{$letter} = $name;
}
close(INF);
}#loadInflectives
|
Подпрограмма loadVectorSpace является более сложной, а ее работа занимает наибольшую часть времени работы программы. Вызов подпрограммы loadVectorSpace в основном коде программы find(\&loadVectorSpace,"$ARGV[0]"); использует структуру обратного вызова модуля File::Find для выполнения кода loadVectorSpace с каждым файлом в указанном каталоге. Как показано ниже, каждая строка в каждом файле будет преобразована в модулированную алфавитно-цифровую строку. Эта строка передается затем в модуль VectorSpace, а данные структуры хэш-данных обеспечиваются ключами по имени файла для списка векторов внутри файла. Поиск этой структуры данных для результатов запросов будет выполняться в логике основной программы.
Листинг 6. Подпрограмма loadInflectives
sub loadVectorSpace
{
return if( $File::Find::name eq $File::Find::dir ); # следующий файл в каталоге
my @docs = ();
open( INF, "$ENV{PWD}/$File::Find::name") or
die "can't open file $ENV{PWD}/$File::Find::name";
while(my $line = <INF>)
{
next unless( $line =~ /:/ ); # пропустить строки без данных
my( undef, $line) = split ':', $line; # игнорировать имя поля
push @docs, buildInflectString($line);
}#while file read
close(INF);
$fileHash{$File::Find::name} = Search::VectorSpace->new(
docs => \@docs,threshold => .04
);
$fileHash{$File::Find::name}->build_index();
print "loaded: $File::Find::name\n";
}#loadVectorSpace
|
Обратите внимание на то, что модулированная алфавитно-цифровая строка создается при помощи вызова подпрограммы buildInflectString. Как показано в листинге 7, подпрограмма buildInflectString использует фонетический хэш, созданный ранее, для преобразования последовательности символов, например nathan, в модулированную строку формата "November Alpha Tango Hotel Alpha November". Это реализует нашу стратегию создания вектора по каждому символу в поле данных.
Листинг 7. Подпрограмма buildInflectString
sub buildInflectString
{
my $data = "";
# разделение пробелов для каждого символа в строке
for my $oneChar ( split //, lc("@_") )
{
# пропустить символ, отличный от a-z или 0-9 (не зависит от регистра)
next if( $oneChar !~ /([a-z]|[0-9])/i );
$data .= $phHash{$oneChar} . " ";
}#для каждой строки файла
return( $data );
}#buildInflectString
|
Теперь у нас есть полностью созданное векторное пространство для поиска, которое будет возвращать имена файлов, содержащих соответствующую запись LDAP-данных, где запрос совпадает.
Основная программа содержит логику запроса, сортировки и отображения для возврата совпадений. Она также применяет простой цикл для обработки запросов в командной строке. В листинге 8 показана логика основной программы.
Листинг 8. Логика основной программы vectorSearch.pl
print "Enter a query: \n";
while ( my $query = <STDIN> ) {
$query = buildInflectString( $query );
my %resHash = ();
for my $fKey( keys %fileHash )
{
my %results = $fileHash{$fKey}->search( $query );
# возвратить только первый результат из каждого файла
my ($topRes) = ( sort { $results{$b} <=> $results{$a} } keys %results );
$resHash{ sprintf("%0.2f", $results{$topRes}) } = $fKey;
}#для каждого имени файла
my $count = 0;
foreach my $resultKey ( reverse sort keys %resHash )
{
$count++;
print "Result: $resultKey $resHash{$resultKey}\n";
last if( $count == $maxMatch );
}#для каждого результата
print "Enter a query: \n";
}#while stdin
|
С запросом пользователя вызывается buildInflectString для создания алфавитно-цифровой модулированной строки для поиска в векторном пространстве. Каждый файл имеет свое собственное векторное пространство для поиска, а результаты отсортированы по номеру в каждом файле. Нам нужно только самое первое совпадение из каждого файла, поэтому мы извлекаем первую запись списка отсортированных пар ключ-значение и помещаем ее в переменную %resHash. После обработки всех файлов необходимо снова отсортировать полученный хэш для отображения наилучшего соответствия во всех доступных файлах.
Выполнение примеров vectorSearch.pl, search
Откройте командную строку и выполните команду perl vectorSearch.pl ldapData/ 5. Будет загружен каждый файл каталога ldapData, и вы увидите приглашение Enter a query. Попробуйте различные запросы и вариации этих запросов, чтобы прочувствовать, как работает система. Например, можно увидеть, что для 415-2042 и 41#5 2-042 выводятся те же самые результаты с записью Nathan Harrington на вершине отсортированного списка.
Для проверки автоматической корректировки орфографии как побочного продукта данного модулирования в векторно-пространственном методе попробуйте запрос nathen harrington или linda horrington. Из-за большого общего количества векторов между запросом и результатами, соответствующие файлы перечисляются в верхней части списка результатов поиска.
Заключение и варианты дальнейшей модификации
Представленный выше код позволит вам эффективно и быстро запрашивать структурированные данные, такие как основанную на LDAP информацию о сотрудниках. Обратите внимание на то, как извлечение первого результата из каждого файла является только одним из способов обработки результатов. Возможно, вы захотите извлечь все результаты из всех файлов и выполнить вторую сортировку или сделать подсчет на основе присутствия запрашиваемого слова в файле. Добавление модуляторов для знаков пунктуации (например, "Dash" для "-" или "AtSign" для "@") может принести пользу при обработке определенных типов данных, например, порядковых номеров сотрудников или почтовых адресов.
Модуль Мациежа Цегловски Search::VectorSpace и некоторые правила создания модулированного слова обеспечивают варианты, необходимые для выбора наилучшего сценария для вашего конкретного набора данных.
Загрузка | Описание | Имя | Размер | Метод загрузки |
|---|
| Исходный код | os-vectorldap-Space_0.1.zip | 1.3KB | HTTP |
|---|
Ресурсы Научиться
Получить продукты и технологии
- Разработайте ваш следующий проект с открытым исходным кодом, используя пробное программное обеспечение IBM, доступное для загрузки или на DVD.
- Загрузите оценочные версии продуктов IBM и используйте инструментальные средства разработки приложений и программы промежуточного уровня DB2®, Lotus®, Rational®, Tivoli® и WebSphere®.
Обсудить
Об авторе | | | Натан Хэррингтон (Nathan Harrington) работает ведущим программистом проекта Resource Locator в IBM. Четыре года он работает с Linux и инструментальными средствами с открытым исходным кодом в целях рационализации бизнеса IBM. |
Выскажите мнение об этой странице
| |
