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