Попинайте алгоритм поиска (научите как надо), пожалуйста

Модератор: Модераторы разделов

Ответить
azsx
Сообщения: 3684
ОС: calculate linux, debian, ubuntu

Попинайте алгоритм поиска (научите как надо), пожалуйста

Сообщение azsx »

Вкратце, я качаю сайты с интернета, чтобы искать по html коду. То есть в итоге, могу найти все сайты с заполненым description или подгружающие определенный js файл. Мне надо сделать на этих данных поиск, который выводил бы первые 1000 результатов "внезапно" и сразу в несколько потоков. Я уже попробовал поиск по триграммам в 1 таблице постгрес, всё плохо, скорость ужасная.
Сейчас я хочу сделать поиск по триграммам разделенным на файлы, хочу посоветоваться. Допустим есть файлы (название по сути триграмма, данные в файле).
ааа.txt:1,2,3,4,12;
ббб.txt:2,3,4,5,13;
ввв.txt:3,4,5,6,14;
ддд:1,3,5,7,15
Отмечу, очень часто номера действительно будут идти последовательно для популярных триграмм. Но не всегда.
Мне получить первую тысячу номеров, которые отвечают условию: есть (ааа и ббб) нет (ввв).То есть запрос должен вернуть только номера 1, 2, 12, 13. На сегодня у меня около 200 гб полусжатых html кодов уникальных страниц и миллионов 15 сайтов. Ну и куча ссылок в очереди. Какие у меня вопросы.
1. Есть три варианта сохранения триграмм (количество, чего там): 3511808 штук - почти весь ascii диапазон; 681472 штук - всё кроме ру букв; 238328 штук - всё, кроме ру букв и верхнего енгл регистра. С одной стороны хочется искать ру символы (анкор листы и ссылочное), но скорее всего работать будет всё это только под енгл и изначально ориентировано на поиск кода. К тому же, парсится весь интернет, а исключение я сделаю только для ру букв. Какой вариант выбрали бы Вы?
2. Я работал и с 60 миллионов файлов, меня не пугает разница в 600 тысяч и 200 тысяч. Какие минусы, кроме более активного юзанья диска есть у большого числа файлов?
3. Фишка файлов, по моему мнению, что я получу колоночную БД в том виде как я её понимаю. То есть у меня будет:
ааа.txt:1:4\n12;
ббб.txt:2:5\n13;
ввв.txt:3:6\n14;
ддд : 1 : 7\n15
Так как речь идет о миллионах записей, то экономия места будет приличная. Выборку мне номеров надо будет писать самостоятельно, то есть алгоритма ещё нет.
Не слишком ли сложно я задумал? Как можно сделать намного проще? Или как бы сделали Вы?
4. Точно ли делать на файлах? Может многие нормальные БД спокойно переварят 600 тысяч таблиц? Какую БД посоветуете?
зы
Sphinx установить не предлагайте. Первое, я хочу сам написать алгоритм, я программист на пхп и паскале или где? Второе, Всё таки он заточен под поиск по словам, а мне надо чтобы вырванные из контекста теги искало. Например, <h1 style="color:blue;">This is a Blue Heading</h1>
Спасибо сказали:
azsx
Сообщения: 3684
ОС: calculate linux, debian, ubuntu

Re: Попинайте алгоритм поиска (научите как надо), пожалуйста

Сообщение azsx »

хоть бы написали, ты туп и всё делаешь не правильно. А то ваще игнор :(
Спасибо сказали:
NickLion
Сообщения: 3408
Статус: аватар-невидимка
ОС: openSUSE Tumbleweed x86_64

Re: Попинайте алгоритм поиска (научите как надо), пожалуйста

Сообщение NickLion »

А зачем тысячи таблиц?
Таблица триграмм (T: id, text), таблица страниц (P: id, url, ...), таблица соотвествия триграмм и страниц (E: idT, idP).
И можно посмотреть как быстро выдаст запрос что-то вроде (условно написал):

Код: Выделить всё

idA = SELECT id FROM T WHERE T.text='ааа'
idB = SELECT id FROM T WHERE T.text='ббб'
idV = SELECT id FROM T WHERE T.text='ввв'
SELECT EA.idP FROM E AS EA INNER JOIN E AS EB ON EA.idP=EB.idP AND EA.idT=idA AND EB.idT=idB WHERE EA.idT NOT IN (SELECT idP FROM E AS EV WHERE EV.idT=idV)

Хранить номера страниц в текстовом файле — странный выбор. Лучше в бинарной форме. Если уж хочется в файлах.
Если поиск будет только по латинским буквам, то всего 17576 комбинации, или я не прав? Или интересуют и цифры, пробелы, символы?
Спасибо сказали:
azsx
Сообщения: 3684
ОС: calculate linux, debian, ubuntu

Re: Попинайте алгоритм поиска (научите как надо), пожалуйста

Сообщение azsx »

Хранить номера страниц в текстовом файле — странный выбор. Лучше в бинарной форме

да, буду хранить в бинарной форме. Написал числами для упрощения.
Таблица триграмм (T: id, text), таблица страниц (P: id, url, ...), таблица соотвествия триграмм и страниц (E: idT, idP).

Я использую такой метод для поиска анкоров и урлов с линков. То есть разбираю строки типа:

Код: Выделить всё

<a href='http://unixforum.org/index.php?showuser=31646' title='NickLion'>NickLion</a>

на три таблицы. Поиск с joinami экономит место, но намного медленее, чем поиск по одной таблице. При этом если это еще мало мало оправдно с урдами, то с триграммами будет ваще ппц. Есть триграммы, например bod (от body), <a> и прочие, которые есть почти на всех сайтах. Некторые сочетания почти уникальны и уж точно совокупность триграмм встречается в единичных случаях. Вы предлагаете создать вторую таблицу, а в результирующей использовать вместо триграмм целое (4 байта). А триграмма - это три байта и одна таблица.
---
Я плохо умею объяснять. Сейчас у меня таблица такакя:
id_shingl3 bigint NOT NULL DEFAULT nextval('shingl3_id_shingl3_seq1'::regclass),
text_shingl3 character(3),
md5_ind character(32)
---
Размер таблицы 7 гб, индексы 12 гб. Строк 9 190 985. Когда я буду переделывать, я заменю мд5 (32 байта) на номер (8 байт). А 3 байта в миллионах строк у меня исчезнет, они будут в имени файла. То есть как я понимаю будет очень солидная экономия по объему данных, соотвественно поиск станет быстрее.
Вашим же методом объем не уменьшится, только запросы станут сложнее для БД.
зы
забыл уточнить. И это всего 40 тысяч сайтов. А только спарсено миллионов 15, в интернете активно врут, что сайтов ваще 2 млрд. То есть мой тип поиска всё равно захлебнётся, он уже плохо работает без прогрева.
Или интересуют и цифры, пробелы, символы?

Как минимум все строчные енгл буквы и печатаемые спецсимволы до 127 кода. Числа я проверял эксперементально (считать я не умею, я учусь в универе в рф там математики не учат).
Спасибо сказали:
NickLion
Сообщения: 3408
Статус: аватар-невидимка
ОС: openSUSE Tumbleweed x86_64

Re: Попинайте алгоритм поиска (научите как надо), пожалуйста

Сообщение NickLion »

Ну, про использование самой триграммы как id соглашусь, не имеет смысла отдельную таблицу. Записи про файл и имя файла всё равно должны храниться где-то, так что "экономии" не будет (или она будет не значительной).
Далее учтите, что ваши файлы нужно будет потом сравнивать. Если сравнивать в лоб, то это O(m*N2), при выборке по m параметрам и среднего числа записей N в одном файле, что не очень оптимистично. Плюс затраты по памяти O(N), где временные данные будут. Если данные в файле хранить в упорядоченном виде, то можно уменьшить время до O(m*N) и память O(1), но если менять файл, то придётся переписывать достаточно много, поэтому зависит от того, насколько часто будут вноситься изменения в файлы.
Спасибо сказали:
azsx
Сообщения: 3684
ОС: calculate linux, debian, ubuntu

Re: Попинайте алгоритм поиска (научите как надо), пожалуйста

Сообщение azsx »

Как бы поступили Вы?
Если у меня сейчас 33 тысячи страниц занимают 7 + 12 гб, то 1 млрд страниц займут 500 террабайт. Почему я и искаю другой алгоритм, у меня критическая ошибка в старом алгоритме.
Спасибо сказали:
Ответить