Здравствуйте

есть строки:

первая строка
вторая отличная строка
третья улетная строка
четвертая строка
и т.д.

таких строк миллионы

как посоветуете поступить, что бы в дальнейшем максимально быстро можно было выбрать все строки, в которых встречается например слово "улетная" или "строка" ?

на ум приходит только одно, один файл список фраз (то что вверху, оригинал)
второй файл, индексы (номера позиций) отдельных слов

есть идеи?
хочется именно максимально быстро выбирать из огромного числа строк (реально десятки миллионов)

может быть намекнет кто-нить 

заранее благодарю

Нужно уточнить задачу:

1. "Слово" состоит только из букв или из любых символов? Например, подстрока "вторая отличная" считается словом?
2. "Словом" является максимальная последовательность символов или фрагменты "слов" тоже считаются "словами"? Например, если есть слово "отличная", можно ли выделить из него слова "отличн", "личная", "на" и пр.?

Это сообщение отредактировал(а) AVA12 - 30.10.2009, 02:20

В строке может быть как буквы так и цифры, а так же . (точка) и , (запятая)
т.е. асолютно любые последовательности

выделить я тут затрудняюсь
главное что бы найти нужное слово в строке
т.е. если я потом буду искать все строки где есть слово "улетная"

то мне надо найти все типа:
улетная строка
супер пупер улетная строка
улетная бредятина

но не нужно брать

отлет птиц
улетнаястрока
улетные строки

Насколько я понимаю, нужно сократить число проверяемых строк. Первое, что приходит в голову - построить для каждой строки такой признак (индекс), который быстро позволит отсечь множество строк. Например,  пусть это будут все символы (строчные), входящие в строку (по одному), отсортированные по алфавиту. Для искомой подстроки строит такой же индекс, а далее ищем вхождения уже по индексам. Во первых их должно быть гораздо меньше, а во вторых - символы отсортированы, так что поиск может быть быстрым. На втором этапе проверяем строки с подходящими индексами. Вместо строчного индекса можно использовать битовый (по одному биту на символ). Тогда первичная проверка вообще пулей считаться будет - побитовое сравнение.

Если поиск работает в оффлайне, то в принципе можно построить массив суффиксов для всех строк разделенных каким нибудь терминальным символом. При поиске уже анализировать это целое слово или часть другого слова.

DooZ, ты так и не ответил на вопросы.

А использовать что-нибудь типа Xapian нет желания?

source777, 
А смысл крутить целый движок если достаточно написать нехитрый алгоритм поиска для конкретной задачи. 

Тут вариантов масса, можно элементарно добавить все слова в бинарное дерево и потом искать

2AVA12 вроде ответил, если насчет выделить, то надо именно найти "слово" т.е. все строки где встречается слово "слово",
слово номер 1 - подходит
лучшее слово тут - подходит
это такое слово - подходит
словоформа текста - не подходит (т.к. "слово" это часть слова "словоформа", а нам надо четко отделять "слово")

пока есть один варинт работает молниеносно
это составление индексов с позицией слова в основном текстовом файле

т.е. пример:
слово1 - тут перечислены позиции где встречается это слово (стартовая и конечная позиция)
и т.д.

минус один, размер индексов жуткий =)
при базе 6 мегабайт (текстовик), около 70к строк
индекс занимает места около 80 метров и порядка 6к файлов 

Добавлено через 54 секунды
ЗЫ. постойка индексов конечно в таком варианте долгая (относительно), но поиск просто моментальный
но этот вариант не устраивает т.к. кол-во файлов при скажем 100.000.000 слов будет жуткий

Добавлено через 1 минуту и 9 секунд
100.000.000 строк т.е (фраз)

Это inverted index. Большинство алгоритмов полнотекстового поиска используют его в том или ином виде.
Индекс можно сжать многими способами: например, давать позицию не по байтам, а по блокам фиксированного размера (страницам) — чтение страницы с диска все равно занимает больше времени, чем поиск подстроки в памяти и отсев ложных попаданий. В результате уменьшается как размер одиночной позиции, так и общее их число для слова. Для хранения индексов можно использовать целые переменной длины.

Я бы рекомендовал всё же воспользоваться готовой реализацией, будь то внешний индексатор (Lucene, Sphinx, Xapian) или встроенный в БД (SQLite, PostgreSQL).

Это сообщение отредактировал(а) Void - 2.11.2009, 13:34

sqlite пробывал
я на C# пишу щас, так вот sqlite не прошел проверку =) ооооочень медленный (с индексами)
а вот с Xapian проблема
не работает, библиотеки взял как положено (dll) не работает, скомпилировал под себя (не работает)
вот что выдает:



хотя в папке с исполняемым файлом лежат два файла:
XapianCSharp.dll (этот подключается в visual studio как библиотека)
_XapianSharp.dll - этот просто лежит т.к. подключить его не получается (VS ругается на него)

может кто подскажет что не так и как подружить этот xapian с С#, второй день бьюсь :-(

Попробуй в system32 кинуть, точно не могу сказать, привязки под .NET не пробовал.

2source777 бесполезно =( не помогло
я щас Lucene ковыряю, вроде то что нужно, правда документация на нее не очень удобная, некоторые вещи не понятны =(

насчет ошибся xapian не хватало библиотеки zlib.dll
очень помогла программа depends которая показывает какие библиотеки требует библиотека =)
буду разбираться теперь с xapian