Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
Форум программистов > Алгоритмы > Как посоветуете индексировать? |
Автор: DooZ 30.10.2009, 00:47 |
Здравствуйте есть строки: первая строка вторая отличная строка третья улетная строка четвертая строка и т.д. таких строк миллионы как посоветуете поступить, что бы в дальнейшем максимально быстро можно было выбрать все строки, в которых встречается например слово "улетная" или "строка" ? на ум приходит только одно, один файл список фраз (то что вверху, оригинал) второй файл, индексы (номера позиций) отдельных слов есть идеи? хочется именно максимально быстро выбирать из огромного числа строк (реально десятки миллионов) может быть намекнет кто-нить ![]() заранее благодарю |
Автор: AVA12 30.10.2009, 02:19 |
Нужно уточнить задачу: 1. "Слово" состоит только из букв или из любых символов? Например, подстрока "вторая отличная" считается словом? 2. "Словом" является максимальная последовательность символов или фрагменты "слов" тоже считаются "словами"? Например, если есть слово "отличная", можно ли выделить из него слова "отличн", "личная", "на" и пр.? |
Автор: DooZ 30.10.2009, 05:40 |
В строке может быть как буквы так и цифры, а так же . (точка) и , (запятая) т.е. асолютно любые последовательности выделить я тут затрудняюсь главное что бы найти нужное слово в строке т.е. если я потом буду искать все строки где есть слово "улетная" то мне надо найти все типа: улетная строка супер пупер улетная строка улетная бредятина но не нужно брать отлет птиц улетнаястрока улетные строки |
Автор: Earnest 30.10.2009, 14:06 |
Насколько я понимаю, нужно сократить число проверяемых строк. Первое, что приходит в голову - построить для каждой строки такой признак (индекс), который быстро позволит отсечь множество строк. Например, пусть это будут все символы (строчные), входящие в строку (по одному), отсортированные по алфавиту. Для искомой подстроки строит такой же индекс, а далее ищем вхождения уже по индексам. Во первых их должно быть гораздо меньше, а во вторых - символы отсортированы, так что поиск может быть быстрым. На втором этапе проверяем строки с подходящими индексами. Вместо строчного индекса можно использовать битовый (по одному биту на символ). Тогда первичная проверка вообще пулей считаться будет - побитовое сравнение. |
Автор: aggressorus 30.10.2009, 15:41 |
Если поиск работает в оффлайне, то в принципе можно построить массив суффиксов для всех строк разделенных каким нибудь терминальным символом. При поиске уже анализировать это целое слово или часть другого слова. |
Автор: AVA12 30.10.2009, 18:02 |
DooZ, ты так и не ответил на вопросы. |
Автор: aggressorus 30.10.2009, 23:42 |
source777, А смысл крутить целый движок если достаточно написать нехитрый алгоритм поиска для конкретной задачи. Тут вариантов масса, можно элементарно добавить все слова в бинарное дерево и потом искать |
Автор: DooZ 2.11.2009, 12:51 |
2AVA12 вроде ответил, если насчет выделить, то надо именно найти "слово" т.е. все строки где встречается слово "слово", слово номер 1 - подходит лучшее слово тут - подходит это такое слово - подходит словоформа текста - не подходит (т.к. "слово" это часть слова "словоформа", а нам надо четко отделять "слово") пока есть один варинт работает молниеносно это составление индексов с позицией слова в основном текстовом файле т.е. пример: слово1 - тут перечислены позиции где встречается это слово (стартовая и конечная позиция) и т.д. минус один, размер индексов жуткий =) при базе 6 мегабайт (текстовик), около 70к строк индекс занимает места около 80 метров и порядка 6к файлов ![]() Добавлено через 54 секунды ЗЫ. постойка индексов конечно в таком варианте долгая (относительно), но поиск просто моментальный но этот вариант не устраивает т.к. кол-во файлов при скажем 100.000.000 слов будет жуткий Добавлено через 1 минуту и 9 секунд 100.000.000 строк т.е (фраз) |
Автор: Void 2.11.2009, 13:34 | ||
Это http://en.wikipedia.org/wiki/Inverted_index. Большинство алгоритмов полнотекстового поиска используют его в том или ином виде. Индекс можно сжать многими способами: например, давать позицию не по байтам, а по блокам фиксированного размера (страницам) — чтение страницы с диска все равно занимает больше времени, чем поиск подстроки в памяти и отсев ложных попаданий. В результате уменьшается как размер одиночной позиции, так и общее их число для слова. Для хранения индексов можно использовать http://en.wikipedia.org/wiki/Variable-length_quantity. Я бы рекомендовал всё же воспользоваться готовой реализацией, будь то внешний индексатор (Lucene, Sphinx, Xapian) или встроенный в БД (SQLite, PostgreSQL). |
Автор: DooZ 2.11.2009, 15:37 | ||
sqlite пробывал я на C# пишу щас, так вот sqlite не прошел проверку =) ооооочень медленный (с индексами) а вот с Xapian проблема не работает, библиотеки взял как положено (dll) не работает, скомпилировал под себя (не работает) вот что выдает:
хотя в папке с исполняемым файлом лежат два файла: XapianCSharp.dll (этот подключается в visual studio как библиотека) _XapianSharp.dll - этот просто лежит т.к. подключить его не получается (VS ругается на него) может кто подскажет что не так и как подружить этот xapian с С#, второй день бьюсь :-( |
Автор: source777 2.11.2009, 16:05 |
Попробуй в system32 кинуть, точно не могу сказать, привязки под .NET не пробовал. |
Автор: DooZ 2.11.2009, 17:58 |
2source777 бесполезно =( не помогло я щас Lucene ковыряю, вроде то что нужно, правда документация на нее не очень удобная, некоторые вещи не понятны =( |
Автор: DooZ 4.11.2009, 15:23 |
насчет ошибся xapian не хватало библиотеки zlib.dll очень помогла программа depends которая показывает какие библиотеки требует библиотека =) буду разбираться теперь с xapian |