Гость
Войти | Профиль | Очистить
Целевая тема:
Создать новую тему:
Автор:
Действия ...
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Алгоритм поиска в тексте / 15 сообщений из 15, страница 1 из 1
02.08.2008, 15:41
    #35466847
текст
текст
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритм поиска в тексте
Имеется множество текстовых файлов.
Хочу сделат быстрый поиск текста через използовании индексов.
Цел что бы не сканит при каждом поиске все файлы (медлено), а използоват индекс.
Проблема - нужна идея как ето делается.
Если я ищу целое слово то более менее ясно. Делат список слов которые имеются в
файле и можно бысто найти в индексе есть ли искомое слово в файле.
Но если я хочу найти част слова - например ищу "оскв" а в файле
ест "москва" то как создат такой индекс? Подчасты слов очен болшое -
нереално всех записат в индексе.

Мой вопрос в том как ето делается? Быстро найти фрагмент текста в "индексе"
не преребирая весь файл? Алгоритм? Идея?
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
02.08.2008, 16:32
    #35466867
another-anonymous
another-anonymous
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритм поиска в тексте
Использовать БД или бесплатный поисковый движок.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
04.08.2008, 08:39
    #35467806
pirovindos
pirovindos
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритм поиска в тексте
Ищи части слов в том же словаре.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
04.08.2008, 09:10
    #35467854
Нахлобуч
Нахлобуч
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритм поиска в тексте
Lucene и его порты под необходимые платформы.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
04.08.2008, 11:04
    #35468201
текст
текст
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритм поиска в тексте
Мне интересен сам алгоритм. Как ето делается?

"Ищи части слов в том же словаре" - ето имеется ввиду индекс?
Если индекс содержит толко целые слова а я ищу части слова то мне надо сканит вес индекс.
То тогда толку в индекса никакого. Лучше искат в текстовом файле .

Кроме как сделат очень большой индекс со всеми частями слов мне ничего другого
не приходит в голову.

Так еще раз - какой алгоритм/индекс/идея что бы быстро искать част слова в
текстовом файле не перебирая вес файл?

(Искал в инете, но на идею не попал. По словам "поисковый движок" нашел много чего,
то толко сам продукт, а как ето работет не нашол).
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
04.08.2008, 11:22
    #35468270
Gatman
Gatman
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритм поиска в тексте
Делай индекс по буквам - чтобы каждая буква указывала на слово (или файл), которое содержит эту букву. Находишь ссылки на все слова, которые содержат бакву , потом букву с и т.д.. потом пересекаешь ссылки, и получаешь слова, которые содержат все эти буквы. ну а потом находишь вслова, где порадок букв совпадает

Пол года назад делал подобную систему (не для поиска слов, вообще). Система строилась на BPlusTree. Получалось при размере листа дерева в 1000 нодов для нахождения значений одного индекса из 1 млрд в худшем случае требовалось 30 сравнений (использовался бинарный поиск). Т.е. для поиска всез слов, состоящих из оскв, потребуется максимум 120 сравнений + пересечение полученного результата и поиск слов с правильным порядком букв
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
04.08.2008, 15:27
    #35469150
Dignat
Dignat
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритм поиска в тексте
Я для этих целей использовал SQLite, MySql и Clucene.
У каждого из них есть свои плюсы и недостатки.

Подробности ищи в инете по фразам: 'full text search' или 'полнотекстовый поиск'.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
04.08.2008, 16:22
    #35469294
sobolev
sobolev
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритм поиска в тексте
текстМне интересен сам алгоритм. Как ето делается?

"Ищи части слов в том же словаре" - ето имеется ввиду индекс?
Если индекс содержит толко целые слова а я ищу части слова то мне надо сканит вес индекс.
То тогда толку в индекса никакого. Лучше искат в текстовом файле .

Кроме как сделат очень большой индекс со всеми частями слов мне ничего другого
не приходит в голову.

Так еще раз - какой алгоритм/индекс/идея что бы быстро искать част слова в
текстовом файле не перебирая вес файл?

(Искал в инете, но на идею не попал. По словам "поисковый движок" нашел много чего,
то толко сам продукт, а как ето работет не нашол).

-- суффиксные деревья
-- суффиксные массивы
-- алгоритм Укконена
В некоторых источниках - позиционные деревья.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
04.08.2008, 17:45
    #35469537
mayton
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритм поиска в тексте
текстМой вопрос в том как ето делается? Быстро найти фрагмент текста в "индексе"
не преребирая весь файл? Алгоритм? Идея?

Тебе нужно просто искать фрагмент текста?

Используй Microsoft Indexing Service! Он входит в состав любой современной Винды.

Если хочешь изучить теорию и разобратся - спроси список литературы по теме text search.

Всего!
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
05.08.2008, 08:02
    #35470144
klen_
klen_
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритм поиска в тексте
определяете что искать, например, "длинное предложение" или "слово" или пару символов
(понятно, что чем короче фраза тем поиск будет работать быстрее)

далее переводите "искомое" в массив кодов, используя функцию ASC ,
потому что строчные переменные работают медленнее, чем integer или byte

Код: plaintext
1.
2.
3.
4.
5.
6.
открываете файл как двоичный

в цикле ...
	читаете часть файла, допустим 1Кб
	перебором элементов массива, ищете в этой части "искомое"
	допустим нашли, тогда выход из цикла
конец цикла

найденную часть переводите обратно в символы с помощью функции CHR
и показываете (или что там собираетесь с ней делать)

буквально за несколько секунд, в файле 100 Мб (допустим) можно найти слово (да и вообще не важно что).
Разумеется не стоит пренебрегать литературой, где изложены алгоритмы поиска.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
05.08.2008, 11:47
    #35470674
текст
текст
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритм поиска в тексте
Спасибо за ответы.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
07.08.2008, 01:27
    #35475045
mayton
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритм поиска в тексте
klen_..Даже не знаю, что сказать. Хочется встать и поаплодировать изобретателю алгоритмов.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
07.08.2008, 07:56
    #35475126
klen_
klen_
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритм поиска в тексте
и действительно
может какая системная dll есть, чтобы велосипед не изобретать
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
09.08.2008, 17:55
    #35479847
S.G.
S.G.
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритм поиска в тексте
mayton klen_..Даже не знаю, что сказать. Присоединяюсь :)

Хотя это:
klen_
Разумеется не стоит пренебрегать литературой, где изложены алгоритмы поиска.Если его переписать в виде
Код: plaintext
Разумеется надо начать с литературы, где изложены алгоритмы поиска.
вполне приемлемо :)
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
09.08.2008, 20:23
    #35479907
apapacy
apapacy
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритм поиска в тексте
klen_и действительно
может какая системная dll есть, чтобы велосипед не изобретать

Тут дело не только в деэльэльке. Система нужна Фантазия людей очень ограничена. И поиск они задают одинаковый. Например 4 млрд. пользователей Интернет за последние полчаса задали поиск Эмма_Уотсон_фото. Для каждого замаханетесь диэльэльки запускать.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Алгоритм поиска в тексте / 15 сообщений из 15, страница 1 из 1
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение  
Полит. конфиден.  
созд. / загр.: 513ms
Закрыть
start [/forum/topic.php?fid=16&mobile=1&tid=1345096]:
 0ms
get settings:
 6ms
get forum list:
 25ms
check forum access:
 3ms
check topic access:
 3ms
track hit:
 187ms
get topic data:
 8ms
get forum data:
 2ms
get page messages:
 45ms
get tp. blocked users:
 1ms
others: 233ms
total:  513ms
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]