Новые сообщения [новые:0]
Дайджест
Горячие темы
Избранное [новые:0]
Форумы
Пользователи
Статистика
Статистика нагрузки
Мод. лог
Поиск
|
|
18.11.2012, 16:40
|
|||
|---|---|---|---|
|
|||
Словарь пар "слово-позиция" |
|||
|
#18+
Добрый день! Уважаемые, стоит задача составить базу данных для всех слов текстового файла с 2мя полями: - слово файла - его позиция в файле Требуется это для дальнейшего быстрого поиска любого слова в файле. Вопрос: кто-нибудь знает хороший алгоритм?) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
18.11.2012, 18:33
|
|||
|---|---|---|---|
Словарь пар "слово-позиция" |
|||
|
#18+
SpokaneВопрос: кто-нибудь знает хороший алгоритм?) Только последовательный просмотр. Можно оптимизировать так, например: - ключ: слово - значение: список позиций (№ строки, позиция слова в строке) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
18.11.2012, 22:23
|
|||
|---|---|---|---|
|
|||
Словарь пар "слово-позиция" |
|||
|
#18+
SpokaneДобрый день! Уважаемые, стоит задача составить базу данных для всех слов текстового файла с 2мя полями: - слово файла - его позиция в файле Требуется это для дальнейшего быстрого поиска любого слова в файле. Вопрос: кто-нибудь знает хороший алгоритм?) std::multimap<std::string, unsigned int> ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
19.11.2012, 02:58
|
|||
|---|---|---|---|
Словарь пар "слово-позиция" |
|||
|
#18+
UsmanSpokaneВопрос: кто-нибудь знает хороший алгоритм?) Только последовательный просмотр.Ну зачем же? Дерево лучше. А хеш еще лучше. Последовательно проходим по файлу и помещаем каждое слово+позиция либо в дерево, либо просто позицию слова в хеш таблицу. В первом случае получишь O(log n) на последующем поиске, во втором O(1). Всяко лучше чем O(n). ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
19.11.2012, 21:20
|
|||
|---|---|---|---|
|
|||
Словарь пар "слово-позиция" |
|||
|
#18+
Так уж случилось, что производительность последовательного просмотра оказалась вполне приемлемой. Тем не менее, учту предложенные варианты, спасибо всем откликнувшимся! ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
19.11.2012, 21:28
|
|||
|---|---|---|---|
|
|||
Словарь пар "слово-позиция" |
|||
|
#18+
Кладу после просмотра пары "слово-позиция" в структуру похожую на словарь ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
20.11.2012, 00:02
|
|||
|---|---|---|---|
Словарь пар "слово-позиция" |
|||
|
#18+
Клади, клади. Но не забывай что в более полной постановке, задача полнотекстового поиска звучит по другому. А именно - найти множество файлов наиболее релевантных к поисковому выражению. Для твоей постановки хватит и обычного последовательного поска. Городить сверх-быстрые алгоритмы нужно только тогда когда ты будешь работать с этим (!) одним файлом с огромной скоростью отбивая тысячи транзакций поска в секунду. Есть у тебя такая постановка? Я думаю - нет. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
start [/forum/topic.php?fid=16&tablet=1&tid=1342041]: |
0ms |
get settings: |
8ms |
get forum list: |
14ms |
check forum access: |
2ms |
check topic access: |
2ms |
track hit: |
148ms |
get topic data: |
9ms |
get forum data: |
2ms |
get page messages: |
41ms |
get tp. blocked users: |
1ms |
| others: | 244ms |
| total: | 471ms |
| 0 / 0 |
