форумы  помощь  поиск  регистрация  майллист  ВХОД  слежка

Вариант для распечатки		Пред. тема | След. тема
Форумы Программирование под UNIX (Public)
Изначальное сообщение		[Проследить за развитием треда]

"Поиск по подстроке"
Сообщение от robot on 27-Мрт-05, 22:06  (MSK)
Есть ли какие нибудь способы оптимизировать поиск по подстроке? Ничего не идёт в голову. К примеру поисковик filesearch.ru cудя по объёму файлов и скорости поиска ищет по подстроке очень быстро, я в мускуле не могу добиться таких результатов. Как это делается?
	Правка | Высказать мнение | Ответить | Рекомендовать в FAQ | Cообщить модератору | Наверх

Индекс форумов | Темы | Пред. тема | След. тема

Сообщения по теме

1. "Поиск по подстроке"
Сообщение от dev (??) on 30-Мрт-05, 15:59  (MSK)
>Есть ли какие нибудь способы оптимизировать поиск по подстроке? Ничего не идёт >в голову. К примеру поисковик filesearch.ru cудя по объёму файлов и >скорости поиска ищет по подстроке очень быстро, я в мускуле не >могу добиться таких результатов. Как это делается? Простейший способ: Создай таблицу с подстроками. create table origins (   id integer,   word varchar(50),   primary key (id) ); create table wordindex (   substr varchar(50),   origin integer,   index (substr) ); При добавлении в базу слова mytest надо добавить в эту таблицу строки (каждый раз удаляем первый символ): substr origin ------------- mytest 12345 ytest  12345 test   12345 est    12345 где 12345 - id оригинальной записи. Минимальную длину имеет смысл (но не обязательно) ограничить тем же значением, что и минимальную длину строки поиска - в данном примере 3. Теперь можно искать: для поиска подстроки "tes": select word from origins, wordindex where id=origin and substr like 'test%'; Обрати внимание, что % стоит только в конце, поэтому мускль может использовать index (substr). Если строка поиска встречается в искомом несколько раз, то в ответе будет соотв. количество одинаковых слов. Если тебе эта 'фича' не нужна - фильтруй.
Удалить	Правка | Высказать мнение | Ответить | Рекомендовать в FAQ | Cообщить модератору | Наверх

	2. "Поиск по подстроке"
	Сообщение от r4 (??) on 30-Мрт-05, 22:41  (MSK)
	Подобный алгоритм уже пришёл в голову, опробовал. По подстроке ищет действительно быстро, но с учётом что выражение хотя бы 4 байта в длину. При этом таблица раздувается в 10 раз. Получается, что полезных данных там может быть максимум 400мб, тк максимальый размер таблицы с полями переменной длины - 4гб. Что тоже не очень приятно. В то же время filesearch.ru работает очень быстро, при том что никаких ограничений на длину выражения у них нет. Как они это реализовали ума не приложу.
	Удалить	Правка | Высказать мнение | Ответить | Рекомендовать в FAQ | Cообщить модератору | Наверх

	3. "Поиск по подстроке"
	Сообщение от dev (??) on 31-Мрт-05, 14:31  (MSK)
	>Подобный алгоритм уже пришёл в голову, опробовал. По подстроке ищет действительно быстро, >но с учётом что выражение хотя бы 4 байта в длину. >При этом таблица раздувается в 10 раз. Получается, что полезных данных >там может быть максимум 400мб, тк максимальый размер таблицы с полями >переменной длины - 4гб. Что тоже не очень приятно. > В то же время filesearch.ru работает очень быстро, при том что >никаких ограничений на длину выражения у них нет. Как они это >реализовали ума не приложу. Давай посчитаем: имя, в среднем, 50 байт. Значит по данному способу требеутся порядка 50x50=2500 байт. У них в базе 51084692 файла. Итого ~120 гиг. Нормально для базы. Если мускль этого не держит - смени его. Вообще, способов может быть масса. Тут главное по-быстренькому сузить диапазон поиска, а потом можно использовать обычные запросы. При этом ориентироваться надо на средний, а не худший случай. Примеры: 1. Разбивать имя на части по слешу и обрабатывать их независимо - резко уменьшается длина слова. У них так и сделано. Получаем ~20 гиг базу. 2. Для каждого слова хранить встречающиеся в нем буквы и двухбуквенные сочетания. При поиске можно сразу отсечь лишнее. Будет ли это эффективно - надо проверять на практике. И ты уверен, что у тебя тоже будут десятки миллионов слов огромной длины? P.S.: гораздо интересней, как у них regexp'ы работают :)
	Удалить	Правка | Высказать мнение | Ответить | Рекомендовать в FAQ | Cообщить модератору | Наверх

	4. "Поиск по подстроке"
	Сообщение от r4 (??) on 31-Мрт-05, 19:08  (MSK)
	>Давай посчитаем: имя, в среднем, 50 байт. Значит по данному способу требеутся >порядка 50x50=2500 байт. >У них в базе 51084692 файла. Итого ~120 гиг. Нормально для базы. >Если мускль этого не держит - смени его. К сожалению аналогов мускулю по скорости нет и в ближайшем времени не придвидится. > >Вообще, способов может быть масса. Тут главное по-быстренькому сузить диапазон поиска, а >потом можно использовать обычные запросы. При этом ориентироваться надо на средний, >а не худший случай. Примеры: >1. Разбивать имя на части по слешу и обрабатывать их независимо - >резко уменьшается длина слова. У них так и сделано. Получаем ~20 >гиг базу. 1. Откуда информация что у них так и сделано?  2.Нам выгодны длинные слова, а не короткие. Динные сильнее сужают диапазон поиска. >2. Для каждого слова хранить встречающиеся в нем буквы и двухбуквенные сочетания. >При поиске можно сразу отсечь лишнее. Будет ли это эффективно - >надо проверять на практике.   Как это можно реализовать в mysql? >И ты уверен, что у тебя тоже будут десятки миллионов слов огромной >длины? У меня будет файловый поисковик. Соответственно длинна будет в среднем байт 10-15, но записей может быть очень много. > >P.S.: гораздо интересней, как у них regexp'ы работают :) это да. Но сначала понять бы как поиск по подстроке работает :)
	Удалить	Правка | Высказать мнение | Ответить | Рекомендовать в FAQ | Cообщить модератору | Наверх

	5. "Поиск по подстроке"
	Сообщение от dev (??) on 01-Апр-05, 13:13  (MSK)
	>К сожалению аналогов мускулю по скорости нет и в ближайшем времени не >придвидится. А ты проверь на своих данных. Я когда-то сравнивал мускль и постгрес на большой таблице (миллионы записей), вставка и поиск по 'str%'. Оба работали достаточно быстро. >1. Откуда информация что у них так и сделано?   Попробуй поискать у них чего-нибудь со слешем. >2.Нам выгодны длинные слова, а не короткие. Динные сильнее сужают диапазон поиска. Длинные - это какие? 100 символов или 20? >>2. Для каждого слова хранить встречающиеся в нем буквы и двухбуквенные сочетания. >>При поиске можно сразу отсечь лишнее. Будет ли это эффективно - >>надо проверять на практике. >  Как это можно реализовать в mysql? Создать таблицу - одна запись для каждого слова и столбец для каждой буквы и сочетания, куда записывать 0 или 1. При поиске посмотреть, какие сочетания встречаются и выбрать из этой таблицы соотв. слова. Потом искать в них. >>И ты уверен, что у тебя тоже будут десятки миллионов слов огромной >>длины? >У меня будет файловый поисковик. Соответственно длинна будет в среднем байт 10-15, >но записей может быть очень много. Ну так оцени размер _своей_ базы. Может, ничего лучше и искать не надо.
	Удалить	Правка | Высказать мнение | Ответить | Рекомендовать в FAQ | Cообщить модератору | Наверх

	6. "Поиск по подстроке"
	Сообщение от r4 (??) on 02-Апр-05, 13:02  (MSK)
	>А ты проверь на своих данных. Я когда-то сравнивал мускль и постгрес >на большой таблице (миллионы записей), вставка и поиск по 'str%'. Оба >работали достаточно быстро. Мускуль имеет очень хорошую поддержку и документацию. А чтобы изучить постгрес, нужно покупать специализированные книги. > >>1. Откуда информация что у них так и сделано?   >Попробуй поискать у них чего-нибудь со слешем. А ты попробуй поискать с пробелом. Тоже самое. У них любые символы не составляющие слово заменяются на *. Так же сделано и у меня. > >>2.Нам выгодны длинные слова, а не короткие. Динные сильнее сужают диапазон поиска. > >Длинные - это какие? 100 символов или 20? без разницы. если 100, то поиск вообще будет мгновенным. >Создать таблицу - одна запись для каждого слова и столбец для каждой >буквы и сочетания, куда записывать 0 или 1. При поиске посмотреть, >какие сочетания встречаются и выбрать из этой таблицы соотв. слова. Потом >искать в них. таблица будет поистине аццкая по объёму. исходя из этого я очень сомневаюсь что поиск по ней будет хоть сколько нибудь быстрым. >>>И ты уверен, что у тебя тоже будут десятки миллионов слов огромной >>>длины? >>У меня будет файловый поисковик. Соответственно длинна будет в среднем байт 10-15, >>но записей может быть очень много. > >Ну так оцени размер _своей_ базы. Может, ничего лучше и искать не >надо. Размер _моей_ базы планируется больше чем у filesearch. Поэтому так тщательно и подбираю алгоритм. если бы было миллиона три, я бы купил п4-3.2 и херачил бы перебором - разницы бы небыло.
	Удалить	Правка | Высказать мнение | Ответить | Рекомендовать в FAQ | Cообщить модератору | Наверх

Архив | Удалить

Индекс форумов | Темы | Пред. тема | След. тема

Пожалуйста, прежде чем написать сообщение, ознакомьтесь с данными рекомендациями.