Re: Тема для холивора - индексация двумерных массивов

Лучше как в фортране  http://artamonov.ru/2009/02/17/column-oriented-databases/

Re: Тема для холивора - индексация двумерных массивов

Ссылка не про то :)

Хотя это тоже хорошая тема для холивара - "Заипали своим скулем ..." Ну, и чтоб два раза не вставать - является ли Оракль реляционной БД.

Re: Тема для холивора - индексация двумерных массивов

что значит индексация двумерных массивов? это делается через хеш. а вообще имхо принцип такой:

Системы хранения и быстрого извлечения данных Есть сервер с большим количеством текстовых файлов, например очень посещаемая 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 байт. Ну и соответственно так-же устроен поиск если не с начала буквы, т.е. полное индексирование, слово "подводный" например, где "вод" стоит в середине слова. и так этой тройкой бегать во всему слову, вариантов Cnk=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.

Re: Тема для холивора - индексация двумерных массивов

Естественно

Re: Тема для холивора - индексация двумерных массивов

Извиняюсь, значит меня просто не правильно поняли. Я не копал так глубоко - в хэши или ещё чего, просто есть двумерная матрица - в каком порядке лучше располагать индексы, колонка-ряд или ряд-колонка? Ну, или на уровне указателей *(i+j*N) - N это количество рядов или столбцов? Просто, в Фортране (и во всех других программах, которые используют фортрановские либы LAPACK,BLAS,ATLAS), первый индекс всегда означает положение в колонке, а второй в ряду. Может у авторов Фортрана и были аргументы в пользу такого решения, но это вступает в противоречие с привычкой, что первая цифра - это x координата (по-горизонтали), а вторая y (по-вертикали). Особенно это противоречие становится очевидным при обработке графических данных ;)

Re: Тема для холивора - индексация двумерных массивов

Ну, и n=row,m=col или m=row,n=col?