Системы хранения и быстрого извлечения данных
Системы хранения и быстрого извлечения данных
|
Eсть сервер с большим количеством текстовых файлов, например очень посещаемая www_board. Само собой - большая посещаемость и постоянные запросы онлайн к базам данных дают на сервер большую нагрузку. Рассмотрим альтернативные возможность хранения данных, а так же поиска по ним. |
Допустим файл текстовый примерно такой:
begin.file вода огонь воздух сила тока, юзер, килограмм, метр, квантовые флуктуации, водка и пр. end.file
Из файла выбираются все слова на букву "в" и их позиция в файле, т.е. допустим "водка" стоит в файле на сотом байте. Функция seek позволяет перемещаться не читая файл, что долго, а сразу к нужному байту. Есть файл-хеш(массивов) "буква => цифры", позиций в файле: "все слова на букву "в" находятся там-то и там-то".
"в" 10 20000 30000 40000 50000 60000
т.е. слова на букву "в" стоят в файле на 10 байте, 20000 байте и т.д. И так по всем буквам. Это была первая буква "в" слове, дальше еще один хеш построить, по сторой букве, т.е. есть слова на букву "в" а среди этих влов есть позиции слов с "ва" "вб" "вв" "вг" "вд" "ве" и т.д. и скажем такое разбиение документа глубиной в слове до пятой или шестой буквы. Юзер ввел в форму слово "водка", программа ищет начала позиции всех слов начинающихся на букву "в", получает(если гигабайт текста) ссылки на 30 мегабайт слов, начинающихся на букву "в". Вторая буква в слове водка это "о". Т.е. поиск уже происходит в этих 30 мегах по букве "о"(выборка 30 мегов делим на 33, получаем на втором шаге мегабайт из изначального гигабайта, если считать что слова размещены в файле(файлах) равновероятно, т.е. слов на букву "а" столько же сколько и на букву "б", "д", "е" и т.д.), третья буква в слове водка "д". но, поиск уже происходит по тому мегабайту, который получился отсеиванием первых двух букв. Делим мегабайт на 33 буквы, получаем 30 килобайт слов, содержащих три буквы "вод". Далее по индукции доходим до последней буквы "а" в слове "водка".
Итого, чтоб не перебирать весь гиг информации, надо seek'ом перебрать за 5 приемов 30 мегабайт+1 мегабайт+30 килобайт+1 килобайт+30 байт+1 байт. Ну и соответственно так-же устроен поиск если не с начала буквы, т.е. полное индексирование, слово "подводный" например, где "вод" стоит в середине слова. и так этой тройкой бегать во всему слову, вариантов Cn k=n!/(n-k)!k!, где k - три буквы "вод" а n - девять букв слова "подводный".
Есть очень большой двоичный файл, который пронизан связами(чтобы удобно было ходить seek'у по ним). Его можно открывать и сдвигать байты, чтобы дописать нужный файл(который изменил пользователь на сервере). Т.е. отследить нитку для слова(или, что то-же самое, для целой странички). Ведь сначала будут выстраиваться параллельные связи и только в конце, если слово более 6-8 букв, будут разветвления в этой структуре. По идее, можно добится того, что редактировать файлы можно будет непосредственно в этом двоичном файле. Т.е. набираешь cd req(или cat /var/log/error.log | more или tail -f /var/log/error.log) и ты уже не в юниксовой файловой системе, а в этом файле, в котором стоит обработчик, такая-же консоль. А интерпретатор команд создает видимость, что ты сидишь в обычной директории и ворочаешь обычными файлами....
Что это дает? Довольно большую скорость доступа к очень большим текстовым архивам без применения базы данных, которая, как правило, держит индекс в памяти.
Поиск по маске слов.
Когда двое людей говорят о море, то сначало не ясно, о чем дальше пойдет речь, о рыбе, о кораблях, или о красивом вечернем прибое, а может и о отпуске. Далее из контекста разговора как правило в течении минуты можно разобратья о чем речь. Т.е. люди используют ассоциации и находят общий образный язык. Человеческий образ допустим море это отпуск. Однозначно ассоциируется с тем, какие круизы, какие корабли, какие гостинницы, пляж из гальки или из песка. Организованный отдых или дикарем. Вобщем при упоминании моря в таком контексте роджаются совершенно однозначные мысли.Или например в другом контексте. То-же самое море может ассоциироваться с красивым горным пейзажем, с какими-то воспоминаниями. Что упрется в поиск фотографий, к примеру, или, если постарше, то к исторической информации об этих местах.
Итак, ассоциация это набор понятий, все более и более сужающийся по мере продолжительности раговора. Собственно люди иногда и расходятся, когда не находят общего языка, так-же и с поисковиками, выдает не то, что нужно.
Изначально было широкое понятие море, которое включало в себя понятие отдыха, рыбы, интересных съемок Ива Кусто или арктических путешествий Нансена с Амундсеном, а может быть и путешествие Кука. Далее информация разделилась на покатегории, по человеческим ассоциаиям. Допустим море интеренсо как место отдыха, остальные гигабайты отсеялись. Место отдыха однозначно ассоциируется с красивыми видами, прогулками на катерах, ну и с поиском жилья. Т.е. человек невольно определяет круг вопросов, которые ему нужно решить, чтобы провести отпуск. Фактически, на простом разговорном языке мы уже произвели отсев нужной информации. И это не было релевантностью, которая есть максимальное число слов в данном документе.
Как сделать так, чтобы поисковая система сама отсеивала нужную информацию. Т.е. выдавала то, что необходимо. В первые минуты разговора между двумя людьми происходит знакомство их интересов, которые в подавляющем большинстве и определяют дальнейшие отношения. В первые минуты работы с поисковой системой происходит точно такое-же знакомство. Поисковик выдает резултьтаты. Нет того, что нужно, значит ухожу на другой поисковик. Предположим слово море выдает несколько ссылок: отдых, исследования океана, знаменитые путешествия(Моби Дик) и т.д.
Пользователь выбирает себе нужную категорию(как составить такие тематические категории автоматичекси, чуть ниже, это и есть поиск по маске слов), далее переходит на еще один вложенный уровень категорий, а в конечном итоге он интересуется путешествием Ниньи. Вышел с первого уровня на второй, где стоят ссылки: Тихий океан. Гречекие корабли, мифический остров Атлантида, Индийский океан, морские сражения(и все это отсортировано по алфавиту скажем) и т.д. Появилась структура запроса, начиная от знакомства с основной тематикой диалога. Эту структуру можно генерировать автоматически.
Допустим словосочетакие "Альберт Эйнштейн" однозначно ассоциируется с атомной бомбой, теорией относительности и скажем с преобразованиями лоренца, как конечный запрос. При вводе словосочетания "Альберт Эйнштейн" сразу выводится тематический рубрикатор в алфавитном порядке. Поиск анализирует разные документы на предмет совпадений разных слов. И чем больше документы походят друг на друга, тем ближе к одной тематике результаты, т.е. больший шанс попасть в данную категорию и в данную букву при кортировке по алфавиту. Чем больше различаются данные слова, тем больший шанс попасть в другую ссылку, другую букву. Т.е. происходит поиск не конкретного слова, а идет анализ результатов, оценивается степень их совпадения между собой. И чем больше процентов "похожести" слов по тематике, тем больше вероятность соотнести эти докуметы между собой. Т.е. идет своеобразное выстраивание документов по тематике, используя одинаковые слова, а слова тянут за собой ассоциации. Т.е. не один запрос, как сказал пользователь, а на самом деле внутри машины может произойти 100000 сравнений документов между собой, никакая база данных не потянет такой одновременный поиск. Иными словами при действиями с этими масками слов просиходит уже не сравнение конкрентых слов, а сравнени понятий, выражаемых этими словами. Ну а чем еще можно выразить какое-то отношение, помимо слов.
Структура этого дерева может быть реализована на хешах хешей, хешей массивов, массивов хешей, а быть может и хеши slice. Или взаимные комбинации, может быть хеши хешей размерности N.
Примеры работы
Поиск по степени совпадений слов в предложениях
Задача, сделать поисковик чтобы сортировал результаты по релевантности, или, что то-же самое, оценивал похожесть, степень одинаковости слов.Эту задачу более менее реализует приведенный ниже скрипт:
#!/usr/bin/perl -w
use locale;
%oo=("будет"=>1, "африка"=>1, "завтра"=>1);
$b="африка африка будет африка завтра";
$o="африка будет вчера зачем что-то";
$tw="африка небудет вчера будет завтра";
$tb="аляска аляска будет будет будет сегодня";
@m=($b, $o, $tb, $tw); rrand(\@m);
print join "\n", @m,"\n";
for $i(0 .. $#m){
$h{$i}{$1}++ while $m[$i]=~m!((\w[\w-]*){4,30})!g;
$vr{$i}=$m[$i];
}
for $r(keys %h){print "\n";
my (@ee, $u, $trr);
for $n(keys %{$h{$r}}){
do{
$t = join " " => $vr{$r};
$u+=1;
push @ee => $h{$r}{$n};
} if exists $oo{$n};
}
print "$t ",$u + $ee[0]-1,"\n";
}
sub rrand{
my $m = shift; my $i;
for($i=@$m; --$i;){
my $j = int rand($i+1);
net if $i==$j;
@$m[$i,$j] = @$m[$j,$i]
}
}
есть какой-то текст в переменнах $b,$o,$tw,$tb, загоняется все в массив.
Для отладки пишется подпрограмма rrand(), которая переставляет случаным образом элементы массива. Далее идет цикл, подсчитывающий частоты одинаковых слов в переменных и заносящий эти частоты в хеш хешей. В хеше хешей 1(т.к. нуумерация элементов массива была случаный образом изменена, то удобно обращаться через номер массива) содержатся предположим для переменной $b такие данные:
$b = "африка африка будет африка завтра";
$h{1}=(
"африка" => 3,
"будет" => 1,
"завтра" => 1
);
т.е. слово африка по частоте употребления в три раза больше в файле, что дает ему большие шансы вылезти в список перых результатов. Далее следуют слова будет и завтра, которые так-же играют немаловажную роль в поднятии ссылки наверх из результатов поискового запроса. Далее в цикле объявляется хеш(задача была сделать, а не память сэкономить), который будет выводить результаты запроса.
Далее идет цикл:
for $r(keys %h){print "\n";
my (@ee, $u, $trr);
for $n(keys %{$h{$r}}){
do{
$t = join " " => $vr{$r};
$u++;
push @ee => $h{$r}{$n};
} if exists $oo{$n};
}
print "$t ",$u + $ee[0]-1,"\n";
}
запрашиваем численное название хеша в переменную $r, считываем с еT помощью хеши хешей. Здесь функцией exists реализован поиск общих ключей в двух хешах: в хеше, поступающем на ввод, и текущем по шагу цикла хеше хешей. Если информация содержится в начальном втором хеше %vr, то запрашиваем еT $vr{$r}. Строчка $u++ отвечает за количество вхождений всех слов, заданных в запросе, в искомую строку(файл). Допустим на входе фраза "будет африка завтра", если хотя бы одно слово из этой фразы совпало со словом в очередной строке(ведь изначально строка была побита на частотный хеш) то локальная переменная $u увеличит свое значение на единичку. Если два слова в строке и в запросе одинаковы, то $u=2, если три - $u=3 и так далее, слов в запросе может быть любое количество. Далее идет строчка
push @ee => $h{$r}{$n};
которая заносит частоты слов(3,1,1 как было выше в примере) в текущей строке. Дальше идет сама exists и после неT разбираемся с весом повторяющихся слов и весом полных совпадений. Т.е. должно быть так, чтобы полное совпадение фразы имело большее значение, нежели чем неполное совпадение + пара повторов. Но функция федет себя по хитрому, допустим, если нужно найти специализированную информацию типа "Хеш хешей хешей хешей хешей массивов", то вес повторений слов будет больше, т.е. вклад члена $ee[0]-1(разница в единицах на случай непреднамеренного повтора) больше, чем $u. В то-же время частота повторений может запросто вывести наверх ссылку с словом, которому посвящен текст. Т.е. некий баланс для фраз, повторений и одиночных слов.
« Назад